3页面置换算法

1、页面置换管理【实验目的】通过本次实验加深对存储管理的理解，掌握最佳置换算法、先进先出置换算法、LRU置换算法；通过缺页率比较各种置换算法的优劣。【实验内容】设计一个虚拟存储区和内存工作区，编程序演示下述算法的具体实现过程，并计算访问命中率。要求设计主界面以灵活选择某算法，且以下算法都要实现1）最佳置换算法（OPT）:将以后永不使用的或许是在最长（未来）时间内不再被访问的页面换出。2）先进先出算法（FIFO）:淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。3）最近最久未使用算法（LRU）:淘汰最近最久未被使用的页面。【实验要求】1）定义为进程分配的物理块数；2）定义进程运行所

2、需访问的页串；3）模拟三种页面置换算法；4）计算页面置换算法的命中率；5）比较三种算法的优劣。先进先出算法（FIFO）最简单的页面置换算法是先入先出（FIFO）法。这种算法的实质是，总是选择在主存中停留时间最长（即最老）的一页置换，即先进入内存的页，先退出内存。理由是：最早调入内存的页，其不再被使用的可能性比刚调入内存的可能性大。建立一个FIFO队列，收容所有在内存中的页。被置换页面总是在队列头上进行。当一个页面被放入内存时，就把它插在队尾上。这种算法只是在按线性顺序访问地址空间时才是理想的，否则效率不高。因为那些常被访问的页，往往在主存中也停留得最久，结果它们因变“老”而不得不被置换出去。F

3、IFO的另一个缺点是，它有一种异常现象，即在增加存储块的情况下，反而使缺页中断率增加了。当然，导致这种异常现象的页面走向实际上是很少见的。该算法将所有使用的内存页面构成一个循环列队，每次置换时将队列中的队首唤出，队首指针后移一位即可，算法容易实现牡丹石最先进入内存的野末必将来就不用再到，甚至可能很快就会用到，所以不能保证有效的缺页率，算法性能较差。最近最久未使用算法（LRUFIFO算法和OPT算法之间的主要差别是，FIFO算法利用页面进入内存后的时间长短作为置换依据，而OPT算法的依据是将来使用页面的时间。如果以最近的过去作为不将来的近似，那么就可以把过去最长一段时间里不曾被使用的页面置换掉。

4、它的实质是，当需要置换一页时，选择在最近一段时间里最久没有使用过的页面予以置换。这种算法就称为最久未使用算法（LeastRecentlyUsedLRU。因实现LRU算法必须有大量硬件支持，还需要一定的软件开销。所以实际实现的都是一种简单有效的LRU近似算法。一种LRU近似算法是最近未使用算法（NotRecentlyUsed,NUR。它在存储分块表的每一表项中增加一个引用位，操作系统定期地将它们置为0o当某一页被访问时，由硬件将该位置1。过一段时间后，通过检查这些位可以确定哪些页使用过，哪些页自上次置0后还未使用过。就可把该位是0的页淘汰出去，因为在最近一段时间里它未被访问过。最佳置换算法（OP

5、T最佳置换（OptimalReplacement）是在理论上提出的一种算法。其实质是：当调入新的一页而必须预先置换某个老页时，所选择的老页是将来不再被使用，或者是在最远的将来才被访问。采用这种页面置换算法，保证有最少的缺页率。但是最优页面置换算法的实现是困难的，因为它需要人们预先就知道一个进程整个运行过程中页面走向的全部情况。不过，这个算法可用来衡量（如通过模拟实验分析或理论分析）其他算法的优劣。该算法能保证有最低的缺页率，所以称为最佳置换算法，但是该算法紧紧是一种理想状况下的算法，因为在进程实际运行过程中，将来会执行到那儿页是不可预知的，所以无法选择该置换那个页出去。因此，本算法在实际中无法

6、使用，只能作为一种标准来衡量其他算法的性能【程序代码】1、先进先出算法（FIFO）#include<stdio.h>#include<stdlib.h>#definemSIZE3#definepSIZE8staticintmemerymSIZE=0;staticintprocesspSIZE=0;/staticintprocesspSIZE=2,3,2,1,524,5,3,2,5,2;/staticintprocesspSIZE=7,10,1,2,10,3,10,4,2,3,10,3,2,1,2,10,1,7,10,1;voidbuild();/生成一个随机数序列voi

7、dFIFO();/最近最久未使用(LRU)置换算法intmain(intargc,char*argv)printf("产生随机序列如下：n");build();printf("先进先出(FIFO)页面置换算法n");FIFO();system("PAUSE");return0;voidbuild()inti=0;for(i=0;i<pSIZE;i+)processi=(int)(1O.O*rand()/(RAND_MAX+1.0)+1);printf("%d",processi);printf("n

8、");voidFIFO()inttimemSIZE=0;inti=0,j=0;intm=-1,n=-1;intmax=-1,maxtime=0;intcount=0;for(i=0;ivpSIZE;i+)/找第一个空闲的物理块for(j=0;jvmSIZE;j+)if(memeryj=0)m=j；break;/找与进程相同的标号for(j=0;j<mSIZE;j+)if(memeryj=processi)n=j;/找time值最大的for(j=0;j<mSIZE;j+)if(timej>maxtime)maxtime=timej;max=j;if(n=-1)/不存在

9、相同进程if(m!=-1)/存在空闲物理块memerym=processi;timem=0;for(j=0;j<=m;j+)timej+;m=-1;else/不存在空闲物理块memerymax=processi;timemax=0;for(j=0;j<mSIZE;j+)timej+;max=-1;maxtime=0;count+;else/存在相同的进程memeryn=processi;for(j=0;j<mSIZE;j+)timej+;n=-1;for(j=0;j<mSIZE;j+)printf("%d",memeryj);printf("

10、;n");printf("页面换算次数为：%dn",count);2、最近最久未使用算法(LRU#include<stdio.h>#include<stdlib.h>#definemSIZE3#definepSIZE8staticintmemerymSIZE=0;staticintprocesspSIZE=0;/staticintprocesspSIZE=2,3,2,1,524,5,3,2,5,2;/staticintprocesspSIZE=7,10,1,2,10,3,10,4,2,3,10,3,2,1,2,10,1,7,10,1;voi

11、dbuild();/生成一个随机数序列voidLRU();/最近最久未使用(LRU)置换算法intmain(intargc,char*argv)printf("产生随机序列如下：n");build();printf("最近最久未使用(LRU)置换算法n");LRU();system("PAUSE");return0;voidbuild()inti=0;for(i=0;ivpSIZE;i+)processi=(int)(10.0*rand()/(RAND_MAX+1.0)+1);printf("%d",process

12、i);printf("n");voidLRU()intflagmSIZE=0;inti=0,j=0;intm=-1,n=-1;intmax=-1,maxflag=0;intcount=0;for(i=0;i<pSIZE;i+)/找第一个空闲的物理块for(j=0;jvmSIZE;j+)if(memeryj=0)m=j;break;/找与进程相同的标号for(j=0;j<mSIZE;j+)if(memeryj=processi)n=j；/找flag值最大的for(j=0;j<mSIZE;j+)if(flagj>maxflag)maxflag=flagj;max=j;if(n=-1)/不存在相同进程if(m!=-1)/存在空闲物理块memerym=processi;flagm=0;for(j=0;j<=m;j+)flagj+;m=-1;else/不存在空闲物理块memerymax=processi;flagmax=0;for(j=0;j<mSIZE;j+)flagj+;max=-1;maxflag=0;count+;else/存在相同的进程memeryn=processi;flagn=0;i