一分钟学会页面置换算法【OPT、FIFO、LRU、NUR】

程序执行期间，若程序所要访问的页面未在内存时，便发出缺页中断，中断处理程序首先保留CPU环境，转入缺页中断处理程序。查找页表，得到该页在外存的物理块后，如果内存未满，则将缺页调入内存并修改页表。

如果内存已满，则按照某种置换算法从内存中选出一页换出；如果该页未被修改过，可不必将该页写回磁盘；但如果此页已被修改，则必须将它写回磁盘，然后再把所缺的页调入内存，并修改页表中的相应表项，置其存在位为“1”，并将此页表项写入快表中。

最佳置换(OPT)算法选择的被淘汰页面，将是以后永不使用的，或许是在最长(未来)时间内不再被访问的页面；采用最佳置换算法可保证获得最低的缺页率。但是由于无法预知哪一个页面是未来最长时间内不再被访问的，因而该算法是无法实现的；

先进先出（FIFO）算法淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。

最近最久未使用（LRU）算法根据页面调入内存后的使用情况进行决策，选择最近最久未使用的页面予以淘汰；该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问一来所经历的时间T，当需要淘汰一个页面时，选择现有页面中T值最大的，即最近最久未使用的页面予以淘汰。

CLCOK算法又称为最近未使用算法（NUR） 每页设置一个访问位，再将内存中的所有页面都通过链接指针链接成一个循环队列；当某个页面被访问时，其访问位置1。淘汰时，检查其访问位，如果是0，就换出；若为1，则重新将它置0；再按FIFO算法检查下一个页面，到队列中的最后一个页面时，若其访问位仍为1，则再返回到队首再去检查第一个页面。

1．假设系统为某进程分配了四个物理块，页面使用走向为：7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1，分别采用OPT算法，FIFO算法，LRU算法，给出页面的置换过程，以及各自发生了几次页面置换？

OPT:4次；FIFO:6次；LRU:4次

2．打开“Microsoft Visual C++ 6.0”，输入相关代码，根据代码注释把空缺的FIFO算法补充完毕，对程序行进编译运行。给出你所填写的FIFO算法代码：

bc[p%blockCount]=pc[i]; p++;

3．根据提示输入上述相关数据，分别记录OPT算法、FIFO算法、LRU算法以及CLOCK算法运行结果：

（1）OPT算法：

（2）FIFO算法

（3）LRU算法

（4）CLOCK算法

——————————————————————————————————————————————————————————————————————————————————————

附上源代码：

#include using namespace std; void Print(int bc[],int blockCount){ for(int i=0; i=k){ k=a[i]; j=i; } } return j; } void LRU(int pc[],int bc[], int pageCount, int blockCount) { cout<<"1:LRU 置换算法"<=max){ max=k; blockIndex=j; } } bc[blockIndex]=pc[i]; } noPage++; cout<<"物理块情况:"; Print(bc, blockCount); } cout<>pageCount; int *pc=new int[pageCount]; cout<<"输入页面走向"<>pc[i]; } cout<<"输入物理块数"<>blockCount; cout<<"0:FIFO置换算法"<>n){ if(n==0){ int *bc=new int[blockCount]; FIFO(pc,bc,pageCount,blockCount); delete bc; } else if(n==1){ int *bc=new int[blockCount]; LRU(pc,bc,pageCount,blockCount); delete bc; } else if(n==2){ int *bc=new int[blockCount]; Optiomal(pc,bc,pageCount,blockCount); delete bc; } else if(n==3){ int *bc=new int[blockCount]; for(i=0; i

其实做人最重要的是自信，到哪儿都一样。————《叶问4》

云数据库 GaussDB(for Redis) 任务调度

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。