操作系统实验五报告-页面置换算法

实验五页面置换算法一、实验目的（1）进一步加深理解父子进程之间的关系及其并发执行。（2）理解内存页面调度的机理。（3）掌握页面置换算法及其实现方法。（4）培养综合运用所学知识的能力。（5）页面置换算法是虚拟存储管理实现的关键，通过本次试验理解内存页面调度的机制，在模拟实现FIFO、LRU等经典页面置换算法的基础上，理解虚拟存储实现的过程。（6）将不同的置换算法放在不同的子进程中加以模拟，培养综合运用所学知识的能力。二、实验内容程序涉及一个父进程和两个子进程。父进程使用rand()函数随机产生若干随机数，经过处理后，存于一数组Acess_Series[]中，作为内存页面访问的序列。两个子进程根据这个访问序列，分别采用FIFO和LRU两种不同的页面置换算法对内存页面进行调度。三、实验要求（1）这是一个综合性实验，要求在掌握父子进程并发执行机制和内存页面置换算法的基础上，能综合运用这两方面的知识，自行、独立编制程序。（2）每个子进程应能反映出页面置换的过程，并统计页面置换算法的命中或缺页情况。设缺页的次数为diseffect。总的页面访问次数为total_instruction。则：缺页率=disaffect/total_instruction命中率=1-disaffect/total_instruction（3）将为进程分配的内存页面数mframe作为程序的参数，通过多次运行程序，说明FIFO算法存在的Belady现象。四、程序流程图（1）程序流程父进程：①随机产生内存访问页面序列，存于数组Acess_Series[total_instruction]中②数据结构M_Frame的初始化③分别创建两个子进程。④等待子进程执行结束，退出。子进程：①读序列Acess_Series[]，若序列中已无下一个元素，转5）；否则，取出页面序列中的下一个元素作为下次要访问的页面；②如果待访问的页面在内存中（即在M_Frame[]中找到），则不发生缺页，命中率加1，转①，注意LRU算法中要调整该页在数组中的位置；③否则就要将这页调入内存，通过修改相应的数据结构M_Frame[]反映出来。首先看M_Frame[]中有无空闲页面，如果有，将待访问页面的页号以及被占用的信息写入数组中适当位置，并统计缺页情况，缺页次数diseffect加1，返回①；④如果M_Frame[]中的所有页面均被占满，则淘汰M_Frame[0]，装入待访问页，重新调整各页面在数组中的位置。并统计缺页情况，缺页次数diseffect加1，返回①；⑤所有页面均已访问完成，统计命中率或缺页率；（2）程序流程图五、数据结构数组Acess_Series[]中存放内存页面访问的序列：intAcess_Series[10];结构数组M_Frame[]记录为进程分配的内存页面的使用情况，在M_Frame[]中page_no记录页面号，flag记录页面是否缺页。structone_frame{intpage_no;charflag;};六、程序源代码#includestdio.h#includestdlib.h#includetime.h#includesys/types.h#includesys/stat.h#includeerror.h#includewait.h#includeunistd.h#includetime.hstructone_frame{intpage_no;charflag;};structone_frameM_Frame[3];structone_frameM_Memory[3];//内存页面intdiseffect;//缺页数inttotal_instruction;//访问总次数intAcess_Series[10];//访问序列intframe=10;voidInitialize();voidDisplay();voidFIFO();voidLRU();intmain(){inti;charselect;printf(Therandnumbersequenceofpage：\n);srand((unsigned)time(NULL));for(i=0;iframe;i++){Acess_Series[i]=rand()%9+1;printf(%d,Acess_Series[i]);}printf(\n);printf(Theresultis：\n);intx,y,fd[2];if((x=fork())==0){if((y=fork())==0)LRU();elseFIFO();}else;return0;}voidInitialize(){inti;diseffect=0;total_instruction=0;for(i=0;i3;i++)M_Memory[i].page_no=M_Frame[i].page_no=0;}voidDisplay(){inti;printf(%5d,Acess_Series[total_instruction]);for(i=0;i3;i++)printf(%5d,M_Memory[i].page_no);for(i=0;i3;i++)if(M_Memory[i].flag=='Y'){printf(Y);gotonext3;}printf(N);next3:printf(\n);}voidFIFO(){inti,j,exchange;Initialize();printf(\n\tFIFO\n);printf(------------------------------------\n);printf(SequenceDistributionPageMissing\n);for(j=0;jframe;j++){for(i=0;i3;i++)if(M_Frame[i].page_no==Acess_Series[total_instruction])gotonext1;diseffect++;exchange=M_Frame[2].page_no;M_Frame[2].page_no=M_Frame[1].page_no;M_Frame[1].page_no=M_Frame[0].page_no;M_Frame[0].page_no=Acess_Series[total_instruction];for(i=0;i3;i++){if(M_Memory[i].page_no==exchange){M_Memory[i].page_no=Acess_Series[total_instruction];M_Memory[i].flag='Y';break;}}next1:Display();for(i=0;i3;i++)M_Memory[i].flag='N';total_instruction++;}printf(FIFODiseffect=%f\n,(float)diseffect/(float)total_instruction);printf(FIFOEffect=%f\n,1-(float)diseffect/(float)total_instruction);printf(------------------------------------\n\n);}voidLRU(){inti,j,exchange;Initialize();printf(\tLRU\n);printf(------------------------------------\n);printf(SequenceDistributionPageMissing\n);for(j=0;jframe;j++){if(M_Frame[0].page_no==Acess_Series[total_instruction])gotonext2;if(M_Frame[1].page_no==Acess_Series[total_instruction]){exchange=M_Frame[1].page_no;M_Frame[1].page_no=M_Frame[0].page_no;M_Frame[0].page_no=exchange;gotonext2;}if(M_Frame[2].page_no==Acess_Series[total_instruction]){exchange=M_Frame[2].page_no;M_Frame[2].page_no=M_Frame[1].page_no;M_Frame[1].page_no=M_Frame[0].page_no;M_Frame[0].page_no=exchange;gotonext2;}diseffect++;exchange=M_Frame[2].page_no;M_Frame[2].page_no=M_Frame[1].page_no;M_Frame[1].page_no=M_Frame[0].page_no;M_Frame[0].page_no=Acess_Series[total_instruction];for(i=0;i3;i++){if(M_Memory[i].page_no==exchange){M_Memory[i].page_no=Acess_Series[total_instruction];M_Memory[i].flag='Y';break;}}next2:Display();for(i=0;i3;i++)M_Memory[i].flag='N';total_instruction++;}printf(FIFODiseffect=%f\n,(float)diseffect/(float)total_instruction);printf(FIFOEffect=%f\n,1-(float)diseffect/(float)total_instruction);printf(------------------------------------\n\n);}七、运行结果与说明