实验报告四[共9页]

1、实验四存储管理常用页面置换算法模拟实验一、实验目的通过模拟实现请求页式存储管理的几种基本页面置换算法，了解虚拟存储技术的特点，掌握虚拟存储请求页式存储管理中几种基本页面置换算法的基本思想和实现过程，并比较它们的效率。二、实验内容设计一个虚拟存储区和内存工作区，并使用下述算法计算访问命中率。1、最佳淘汰算法（ OPT）2、先进先出的算法（ FIFO）3、最近最久未使用算法（ LRU）4、最不经常使用算法（ LFU）5、最近未使用算法（ NUR）命中率页面失效次数页地址流长度三、实验过程 1. 进入 LINUX 系统。打开虚拟机，在 vi 中编写程序，在终端输入文件名（gccxx.c ），输入执行

2、指令，屏幕上无反应，按下 C后，显示最终结果。2、页面置换算法当 CPU接收到缺页中断信号，中断处理程序先保存现场，分析中断原因，转入缺页中断处理程序。该程序通过查找页表，得到该页所在外存的物理块号。如果此时内存未满，能容纳新页，则启动磁盘 I/O 将所缺之页调入内存，然后修改页表。如果内存已满，则须按某种置换算法从内存中选出一页准备换出，是否重新写盘由页表的修改位决定，然后将缺页调入，修改页表。利用修改后的页表，去形成所要访问数据的物理地址，再去访问内存数据。整个页面的调入过程对用户是透明的。常用的页面置换算法有1、最佳置换算法（ Optimal ）2、先进先出法（ FisrtInFirst

3、Out ）3、最近最久未使用（ LeastRecentlyUsed ）4、最不经常使用法（ LeastFrequentlyUsed ）5、最近未使用法（ NoUsedRecently）3. 运行结果:四、回答问题1、为什么 OPT在执行时会有错误产生？当需要淘汰一个内存页面时， 这种算法力图选择该进程内存各个页面中永远不再需要的页，若找不到，则选择最久以后才会用到的页。这种算法有最小的缺页率。问题是它需要知道运行进程今后的整个访问踪迹，这往往难以做到，因而它只有理论上的意义。OPTimalreplacement（OPT）它是一种理想化的算法，性能最好，但在实际上难于实现。即选择那些永不使用的，

4、或者是在最长时间内不再被访问的页面置换出去。但是要确定哪一个页面是未来最长时间内不再被访问的，目前来说是很难估计的，所以该算法通常用来评价其它算法。五、实验总结从几种算法的命中率看， OPT最高，其次为 NUR相对较高，而 FIFO与 LRU相差无几，最低的是 LFU。但每个页面执行结果会有所不同。最佳置换算法 (Optimal) ，其所选择的被淘汰页面， 将是以后永不使用的或许是在最长 ( 未来) 时间内不再被访问的页面。采用最佳置换算法，通常可保证获得最低的缺页率。但由于人目前还无法预知一个进程在内存的若干个页面中，哪一个页面是未来最长时间内不再被访问的，因而该算法是无法实现的，便可以利用

5、此算法来评价其它算法。先进先出 (FIFO) 页面置换算法：这是最早出现的置换算法。该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。该算法实现简单只需把一个进程已调入内存的页面，按先后次序链接成一个队列，并设置一个指针，称为替换指针，使它总是指向最老的页面。LRU置换算法：最少使用 (LFU:LeastFrequentlyUsed) 置换算法：在采用该算法时， 应为在内存中的每个页面设置一个移位寄存器骼来记录该页面被访问的频率。该置换算法选择在最近时期使用最少的页面为淘汰页。FIFO置换算法性能之所以较差， 是因为它所依据的条件是各个页面调入内存的时间，而页面调入的

6、先后并不能反映页面的使用情况。最近最久未使用（ LRU）置换算法，是根据页面调入内存后的使用情况进行决策的。由于无法预测各页面将来的使用情况，只能利用 “ 最近的过去 ”作为 “最近的将来 ”的近似，因此，LRU置换算法是选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段， 用来记录一个页面自上次被访问以来所经历的时间 t, ，当须淘汰一个页面时，选择现有页面中其 t 值最大的，即最近最久未使用的页面予以淘汰。六、参考程序#defineTRUE1#defineFALSE0#defineINVALID-1#defineNULL0#definetotal_instruction320

7、/* 指令流长 */#definetotal_vp32/* 虚页长*/#defineclear_period50/* 清0周期*/typedefstruct/* 页面结构 */intpn,pfn,counter,time;pl_type;pl_typepltotal_vp;/* 页面结构数组 */structpfc_struct/* 页面控制结构 */intpn,pfn;structpfc_struct*next;typedefstructpfc_structpfc_type;pfc_typepfctotal_vp,*freepf_head,*busypf_head,*busypf_tail;

8、intdiseffect,atotal_instruction;intpagetotal_instruction,offsettotal_instruction;intinitialize(int);intFIFO(int);intLRU(int);intLFU(int);intNUR(int);intOPT(int);intmain()ints,i,j;srand(10*getpid();/* 由于每次运行时进程号不同，故可用来作为初始化随机数队列的“种子” */s=(float)319*rand()/32767/32767/2+1;/for(i=0;itotal_instruction;i

9、+=4)/* 产生指令队列 */if(s319)printf(Wheni=%d,Error,s=%dn,i,s);exit(0);ai=s;/* 任选一指令访问点 m*/ai+1=ai+1;/* 顺序执行一条指令 */ai+2=(float)ai*rand()/32767/32767/2;/* 执行前地址指令 m*/ai+3=ai+2+1;/* 顺序执行一条指令 */s=(float)(318-ai+2)*rand()/32767/32767/2+ai+2+2;if(ai+2318)|(s319)printf(a%d+2,anumberwhichis:%dands=%dn,i,ai+2,s);

10、for(i=0;itotal_instruction;i+)/* 将指令序列变换成页地址流 */pagei=ai/10;offseti=ai%10;for(i=4;i=32;i+)/* 用户内存工作区从 4个页面到32个页面*/printf(-%2dpageframes-n,i);FIFO(i);LRU(i);LFU(i);NUR(i);OPT(i);return0;intinitialize(total_pf)/* 初始化相关数据结构 */inttotal_pf;/* 用户进程的内存页面数 */inti;diseffect=0;for(i=0;itotal_vp;i+)pli.pn=i;pl

11、i.pfn=INVALID;/* 置页面控制结构中的页号，页面为空 */pli.counter=0;pli.time=-1;/* 页面控制结构中的访问次数为 0，时间为-1*/for(i=0;itotal_pf-1;i+)pfci.next=&pfci+1;pfci.pfn=i;/* 建立pfci-1 和pfci 之间的链接 */pfctotal_pf-1.next=NULL;pfctotal_pf-1.pfn=total_pf-1;freepf_head=&pfc0;/* 空页面队列的头指针为 pfc0*/return0;intFIFO(total_pf)/* 先进先出算法 */inttot

12、al_pf;/* 用户进程的内存页面数 */inti,j;pfc_type*p;initialize(total_pf);/* 初始化相关页面控制用数据结构 */busypf_head=busypf_tail=NULL;/* 忙页面队列头，队列尾链接 */for(i=0;inext;plbusypf_head-pn.pfn=INVALID;freepf_head=busypf_head;/* 释放忙页面队列的第一个页面 */freepf_head-next=NULL;busypf_head=p;p=freepf_head-next;/* 按FIFO方式调新页面入内存页面 */freepf_he

13、ad-next=NULL;freepf_head-pn=pagei;plpagei.pfn=freepf_head-pfn;if(busypf_tail=NULL)busypf_head=busypf_tail=freepf_head;elsebusypf_tail-next=freepf_head;/*free 页面减少一个 */busypf_tail=freepf_head;freepf_head=p;printf(FIFO:%6.4fn,1-(float)diseffect/320);return0;intLRU(total_pf)/* 最近最久未使用算法 */inttotal_pf;i

14、ntmin,minj,i,j,present_time;initialize(total_pf);present_time=0;for(i=0;itotal_instruction;i+)if(plpagei.pfn=INVALID)/* 页面失效*/diseffect+;if(freepf_head=NULL)/* 无空闲页面 */min=32767;for(j=0;jplj.time&plj.pfn!=INVALID)min=plj.time;minj=j;freepf_head=&pfcplminj.pfn;/ 腾出一个单元plminj.pfn=INVALID;plminj.time=-

15、1;freepf_head-next=NULL;plpagei.pfn=freepf_head-pfn;/ 有空闲页面 , 改为有效plpagei.time=present_time;freepf_head=freepf_head-next;/ 减少一个free 页面elseplpagei.time=present_time;/ 命中则增加该单元的访问次数present_time+;printf(LRU:%6.4fn,1-(float)diseffect/320);return0;intNUR(total_pf)/* 最近未使用算法 */inttotal_pf;inti,j,dp,cont_f

16、lag,old_dp;pfc_type*t;initialize(total_pf);dp=0;for(i=0;itotal_instruction;i+)if(plpagei.pfn=INVALID)/* 页面失效*/diseffect+;if(freepf_head=NULL)/* 无空闲页面 */cont_flag=TRUE;old_dp=dp;while(cont_flag)if(pldp.counter=0&pldp.pfn!=INVALID)cont_flag=FALSE;elsedp+;if(dp=total_vp)dp=0;if(dp=old_dp)for(j=0;jnext=

17、NULL;plpagei.pfn=freepf_head-pfn;freepf_head=freepf_head-next;elseplpagei.counter=1;if(i%clear_period=0)for(j=0;jtotal_vp;j+)plj.counter=0;printf(NUR:%6.4fn,1-(float)diseffect/320);return0;intOPT(total_pf)/* 最佳置换算法 */inttotal_pf;inti,j,max,maxpage,d,disttotal_vp;pfc_type*t;initialize(total_pf);for(i

18、=0;itotal_instruction;i+)/printf(InOPTfor1,i=%dn,i);/i=86;i=176;206;250;220,221;192,193,194;258;274,275,276,277,278;if(plpagei.pfn=INVALID)/* 页面失效*/diseffect+;if(freepf_head=NULL)/* 无空闲页面 */for(j=0;jtotal_vp;j+)if(plj.pfn!=INVALID)distj=32767;/* 最大 距离*/elsedistj=0;d=1;for(j=i+1;jtotal_instruction;j+)if(plpagej.pfn!=INVALID)distpagej=d;d+;max=-1;for(j=0;jtotal_vp;j+)if(maxnext=NULL;plmaxpage.pfn=INVALID;plpagei.pfn=freepf_head-p