页面置换算法模拟实验报告

1、实验编号4名称页面置换算法模拟实验目的通过请求页式存储治理中页面置换算法模拟设计,以便：1、了解虚拟存储技术的特点2、掌握请求页式存储治理中页面置换算法实验内容与步骤设计一个虚拟存储区和内存工作区,并使用FIFO和LRU算法计算访问命中率.<程序设计>先用srand()函数和rand()函数定义和产生指令序列,然后将指令序列变换成相应的页地址流,并针对不同的算法计算相应的命中率.程序1>#include<windows.h>/Windows版,随机函数需要,GetCurrentProcessId()需要/#include<stdlib.h>/Linux

2、版,随机函数srand和rand需要#include<stdio.h>/printf()需要# defineTRUE1# defineFALSE0# defineINVALID-1# defineNULL0# definetotal_instruction320共320条指令# definetotal_vp32虚存页共32页# defineclear_period50访问次数清零周期typedefstruct定义页表结构类型(页面映射表PMT)intpn,pfn,counter,time;/页号、页框号(块号)、一个周期内访问该页面的次数、访问时间PMT;PMTpmt32;type

3、defstructpfc_struct页面限制结构intpn,pfn;structpfc_struct*next;pfc_type;pfc_typepfc32;pfc_type*freepf_head,*busypf_head,*busypf_tail;/空闲页头指针,忙页头指针,忙页尾指针intNoPageCount;缺页次数intatotal_instruction;/指令流数组intpagetotal_instruction,offsettotal_instruction;每条指令的页和页内偏移voidinitialize(int);voidFIFO(int);先进先出voidLRU(i

4、nt);最近最久未使用voidNRU(int);最近最不经常使用/*main()*voidmain()inti,s;/srand(10*getpid();用进程号作为初始化随机数队列的种子/Linux版srand(10*GetCurrentProcessId();/用进程号作为初始化随机数的种子/Windows版s=rand()%320;/在0,319的指令地址之间随机选取一起点mfor(i=0;i<totalinstruction;i+=4)产生指令队列if(s<0|s>319)printf("wheni=%d,error,s=%dn",i,s);exi

5、t(0);ai=s;/任意选一指令访问点m.(将随机数作为指令地址m)ai+1=ai+1;/顺序执行下一条指令ai+2=rand()%(s+2);在0,m+1的前地址之间随机选取一地址,记为m'ai+3=ai+2+1;/顺序执行一条指令s=ai+2+(int)rand()%(320-ai+2);/在m',319的指令地址之间随机选取一起点if(ai+2>318)|(s>319)printf("a%d+2,anumberwhichis:%dands=%dn",i,ai+2,s);for(i=0;i<total_instruction;i+)/

6、将指令序列变成页地址流pagei=ai/10;offseti=ai%10;for(i=4;i<=32;i+)内存块分别为4块、5块、32块时的命中率printf("%2dpageframes",i);FIFO(i);/计算用FIFO置换时,有i个内存块时的命中率LRU(i);最近最久未使用NRU(i);最近最不经常使用printf("n");/*initialize()形参：内存块数功能：初始化*/voidinitialize(inttotal_pf)初始化相关数据结构,形参total_pf是用户进程的内存页面数inti;NoPageCount=0

7、;/缺页次数,初始化为0for(i=0;i<total_vp;i+)pmti.pn=i;/填逻辑页号pmti.pfn=INVALID;/物理页面号为-1pmti.counter=0;/置页面限制结构中的访问次数为0pmti.time=-1;置页面限制结构中的时间为-1二for(i=0;i<total_pf-1;i+)建立pfci-1和pfci之间的连接pfci.next=&pfci+1;pfci.pfn=i;pfctotal_pf-1.next=NULL;pfctotal_pf-1.pfn=total_pf-1;freepf_head=&pfc0;/页面队列的头指针

8、为pfc0/*FIFO算法形参：内存块数输出：命中率*/voidFIFO(inttotalpf)形参totalpf是用户进程的内存页面数inti;pfc_type*p;initialize(total_pf);初始化相关数据结构busypf_head=busypf_tail=NULL;for(i=0;i<total_instruction;i+)/访问每条指令if(pmtpagei.pfn=INVALID)缺页NoPageCount+=1;/失效做页)次数增1if(freepf_head=NULL)无空闲页面p=busypf_head->next;pmtbusypf_head-&g

9、t;pn.pfn=INVALID;freepf_head=busypf_head;释放忙页面队歹U的第一个页面freepf_head->next=NULL;busypf_head=p;p=freepf_head->next;/按FIFO方式调新页面入内存freepf_head->next=NULL;freepf_head->pn=pagei;pmtpagei.pfn=freepf_head->pfn;if(busypf_tail=NULL)busypf_head=busypf_tail=freepf_head;elsebusypf_tail->next=fr

10、eepf_head;/free页面减少一个busypf_tail=freepf_head;freepf_head=p;printf("FIFO:%6.4f",1-(float)NoPageCount/320);/*LRU算法(最近最久未使用)形参：内存块数输出：命中率*/voidLRU(inttotalpf)/形参totalpf是给用户进程的内存块数intmin,minj,i,j,present_time;initialize(total_pf);present_time=0;for(i=0;i<total_instruction;i+)if(pmtpagei.pfn

11、=INVALID)页面失效NoPageCount+;if(freepf_head=NULL)无空闲页面min=32767;for(j=0;j<totalvp;j+)/找出time的最小值if(min>pmtj.time&&pmtj.pfn!=INVALID)min=pmtj.time;minj=j;freepf_head=&pfcpmtminj.pfn;腾出个单元pmtminj.pfn=INVALID;pmtminj.time=-1;freepf_head->next=NULL;pmtpagei.pfn=freepf_head->pfn;有空闲页

12、面,改为有效pmtpagei.time=present_time;freepf_head=freepf_head->next;减少一个free页面elsepmtpagei.time=present_time;更新该页面的访问时间(并非真的时间,而是循环次数,每执行一条指令,时间加1presenttime+;当前时间力口1printf("LRU:%6.4f",1-(float)NoPageCount/320);/*NRU算法最近最不经常使用形参：内存块数输出：命中率*/voidNRU(inttotal_pf)inti,j,dp,cont_flag,old_dp;init

13、ialize(total_pf);dp=0;for(i=0;i<total_instruction;i+)if(pmtpagei.pfn=INVALID)缺页NoPageCount+;if(freepfhead=NULL)无空闲页面cont_flag=TRUE;old_dp=dp;while(cont_flag)if(pmtdp.counter=0&&pmtdp.pfn!=INVALID)cont_flag=FALSE;if(dp=old_dp)for(j=0;j<total_vp;j+)pmtj.counter=0;lfreepf_head=&pfcpmt

14、dp.pfn;pmtdp.pfn=INVALID;freepf_head->next=NULL;pmtpagei.pfn=freepfhead->pfn;freepf_head=freepf_head->next;Ielsepmtpagei.counter=1;if(i%clear_period=0)for(j=0;j<total_vp;j+)pmtj.counter=0;printf("NUR:%6.4f",1-(float)NoPageCount/320);|实验结果写生结果,截图也可情输A币而长唐4B辆出随机小Y3654?159H211一八,隔

15、人分配的物理按鬲之白>工:MFIF.曲面置挣页面宜梆负面置界清选持页面置挂法,F】FO违法页面苜由清况如下:总结收获,未实现的步骤这次操作系统课程设计,让我们对操作系统有了更深的熟悉,首先操作系统是一治理电脑硬件与软件资源的程序,同时也是计算机系统内核与基石.操作系统是一个庞大的治理限制程序,大致包括5个方面的治理功能：进程与处理机管理、作业治理、存储治理、设备治理、文件治理.我们这次课程设计的题目是页面置换算法,是属于存储器治理.在进程运行过程中,假设其访问的页面不在内存而需把它们调入内存,但内存以无空闲空间时,为了保证该进程能正常的运行,系统必须从内存中调出一页程序或数据送磁盘的兑换

16、区中,但应将哪个页面调出,需根据一定的算法来确定.通常,把选择换成页面的算法称为页面置换算法.通过本次课程设计,我们对页面置换算法的了解更加的深刻.主要有以下置换算法：OPT最正确置换算法、FIFO先进先出置换算法、LRU最近最久未使用算法.每种算法都有各自的优缺点,OPT算法是实际中不能实现的,但是可以利用该算法去评价其它算法；FIFO算法与进程实际运行的规律不相适用,由于在进程中,有些页面经常被访问；LRU算法是根据页面调入内存后的使用情况进行决策的.在这次课程设计中,遇到了一些困难,例如怎么实现各种算法,如何进行函数调用及对数据的限制操作等,在遇到这些困难的时候,我们会去查阅资料,仔细看书,尝试用不同的方法解决,在各种