操作系统实验5 页面置换算法.doc

操作系统实验报告计算机0703班200729实验5 页面置换算法1、 实验题目：页面置换算法（请求分页）2、 实验目的： 进一步理解父子进程之间的关系。1） 理解内存页面调度的机理。2） 掌握页面置换算法的实现方法。3） 通过实验比较不同调度算法的优劣。4） 培养综合运用所学知识的能力。 页面置换算法是虚拟存储管理实现的关键，通过本次试验理解内存页面调度的机制，在模拟实现FIFO、LRU等经典页面置换算法的基础上，比较各种置换算法的效率及优缺点，从而了解虚拟存储实现的过程。将不同的置换算法放在不同的子进程中加以模拟，培养综合运用所学知识的能力。3、 实验内容及要求 这是一个综合型实验，要求在掌握父子进程并发执行机制和内存页面置换算法的基础上，能综合运用这两方面的知识，自行编制程序。程序涉及一个父进程和两个子进程。父进程使用rand()函数随机产生若干随机数，经过处理后，存于一数组Acess_Series中，作为内存页面访问的序列。两个子进程根据这个访问序列，分别采用FIFO和LRU两种不同的页面置换算法对内存页面进行调度。要求：1） 每个子进程应能反映出页面置换的过程，并统计页面置换算法的命中或缺页情况。设缺页的次数为diseffect。总的页面访问次数为total_instruction。缺页率 = disaffect/total_instruction命中率 = 1- disaffect/total_instruction2）将为进程分配的内存页面数mframe 作为程序的参数，通过多次运行程序，说明FIFO算法存在的Belady现象。四、程序流程图 5、 程序源代码、文档注释及文字说明#include#include#include#include#include#include#include#includemain()int p1,p2;int i,j,k,t,m,kk,r1,r2;int temp1,temp2,temp3;int diseffect1=0;int diseffect2=0; int k1=0;int k2=0; int f1=0;int f2=0;float f; int Access_series8; struct one_frame int page_no; char flag; ; int mframe=5; struct one_frame M_Frame5;for(i=0;imframe;i+) M_Framei.page_no=-1; printf(yemian: ); for(i=0;i8;i+) /产生随机数 Access_seriesi=rand()%8+1; printf(%d ,Access_seriesi);printf(n); while(p1=fork()=-1); if(p1=0) for(j=0;j8;j+) r1=Access_seriesj; /读入一个逻辑页面 for(k=0;kk1;k+) /查找页面是否已存在于物理页面 if(r1!=M_Framek.page_no) continue; else printf(have found!n);for(i=0;ik1;i+) /存在则显示，并标记，返回读入逻辑页面 printf(%d ,M_Framei);printf(n);f1=1;break; if(f1=0) diseffect1+; /若不存在，发生缺页，则失效率加1 if(k1mframe) /物理页面没有分配满 M_Framek1.page_no=r1; /分配一个空的物理页面 M_Framek1.flag=Y; k1+; for(i=0;i8;i+)printf(%d ,Access_seriesi);printf(n); printf(diseffect!);printf( %dn,diseffect1); for(i=0;ik1;i+) printf(%d ,M_Framei);printf(n); else temp1=M_Frame0.page_no; /物理页面表已满 for(i=1;i5;i+) M_Framei-1=M_Framei;M_Frame4.page_no=r1; /淘汰最早进入的M_Frame0 /并将所读的逻辑页面调入 for(i=0;i8;i+)printf(%d ,Access_seriesi);printf(n); printf(diseffect! %dn,diseffect1); printf(lose %dn,temp1); for(i=0;ik1;i+) printf(%d ,M_Framei);printf(n); f1=0; f=diseffect1/8.0; /统计缺页率 printf(diseffect rate of FIFO %fn,f); exit(0); wait(0); for(i=0;imframe;i+) M_Framei.page_no=-1; while(p2=fork()=-1) ; /创建子进程2 if(p2=0) for(m=0;m8;m+) r2=Access_seriesm; /读入逻辑页 for(kk=0;kkk2;kk+) if(r2!=M_Framekk.page_no) /首先在物理页面中查找 continue; else printf(have found!n); /找到 for(t=kk+1;tk2;t+) /调整数组顺序，使刚被访问的页面在最后的位置 M_Framet-1.page_no=M_Framet.page_no; M_Framet-1.page_no=r2; for(i=0;ik2;i+) printf(%d ,M_Framei.page_no);printf(n); f2=1; break; if(f2=0) /没有找到，发生缺页 diseffect2+; /缺页率加1 if(k2mframe) /物理页面还没有分配完 M_Framek2.page_no=r2; /选择空页面分配 M_Framek2.flag=Y;k2+; for(i=0;i8;i+)printf(%d ,Access_seriesi);printf(n); printf(diseffect! %dn,diseffect2); for(i=0;ik2;i+) printf(%d ,M_Framei);printf(n); else /淘汰最近最久未访问的M_Frame0 temp3=M_Frame0.page_no; for(i=1;imframe;i+) M_Framei-1.page_no=M_Framei.page_no; M_Framemframe-1.page_no=r2; /将当前页调入for(i=0;i8;i+)printf(%d ,Access_seriesi);printf(n); printf(diseffect %dn,diseffect2); printf(lose %dn,temp3); for(i=0;ik2;i+) printf(%d ,M_Framei);printf(n); f2=0; f=diseffect2/8.0; /统计失效率 printf(diseffect rate of LRU %fn,f);exit(0); 6、 运行结果及其说明FIFO：8，7，2，4缺页调入，2，8