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

1、操作系统实验报告计算机0703班200729实验5 页面置换算法1、 实验题目：页面置换算法（请求分页）2、 实验目的： 进一步理解父子进程之间的关系。1） 理解内存页面调度的机理。2） 掌握页面置换算法的实现方法。3） 通过实验比较不同调度算法的优劣。4） 培养综合运用所学知识的能力。 页面置换算法是虚拟存储管理实现的关键，通过本次试验理解内存页面调度的机制，在模拟实现FIFO、LRU等经典页面置换算法的基础上，比较各种置换算法的效率及优缺点，从而了解虚拟存储实现的过程。将不同的置换算法放在不同的子进程中加以模拟，培养综合运用所学知识的能力。3、 实验内容及要求 这是一个综合型实验，要求在掌

2、握父子进程并发执行机制和内存页面置换算法的基础上，能综合运用这两方面的知识，自行编制程序。程序涉及一个父进程和两个子进程。父进程使用rand()函数随机产生若干随机数，经过处理后，存于一数组Acess_Series中，作为内存页面访问的序列。两个子进程根据这个访问序列，分别采用FIFO和LRU两种不同的页面置换算法对内存页面进行调度。要求：1） 每个子进程应能反映出页面置换的过程，并统计页面置换算法的命中或缺页情况。设缺页的次数为diseffect。总的页面访问次数为total_instruction。缺页率 = disaffect/total_instruction命中率 = 1- disa

3、ffect/total_instruction2）将为进程分配的内存页面数mframe 作为程序的参数，通过多次运行程序，说明FIFO算法存在的Belady现象。四、程序流程图 5、 程序源代码、文档注释及文字说明#include<stdio.h>#include<sys/types.h>#include<stdlib.h>#include<sys/stat.h>#include<fcntl.h>#include<error.h>#include<wait.h>#include<unistd.h>m

4、ain()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;i<mframe;i+) M_Framei.page_no=-1; printf(&quo

5、t;yemian: "); for(i=0;i<8;i+) /产生随机数 Access_seriesi=rand()%8+1; printf("%d ",Access_seriesi);printf("n"); while(p1=fork()=-1); if(p1=0) for(j=0;j<8;j+) r1=Access_seriesj; /读入一个逻辑页面 for(k=0;k<k1;k+) /查找页面是否已存在于物理页面 if(r1!=M_Framek.page_no) continue; else printf("

6、;have found!n");for(i=0;i<k1;i+) /存在则显示，并标记，返回读入逻辑页面 printf("%d ",M_Framei);printf("n");f1=1;break; if(f1=0) diseffect1+; /若不存在，发生缺页，则失效率加1 if(k1<mframe) /物理页面没有分配满 M_Framek1.page_no=r1; /分配一个空的物理页面 M_Framek1.flag='Y' k1+; for(i=0;i<8;i+)printf("%d &quo

7、t;,Access_seriesi);printf("n"); printf("diseffect!");printf(" %dn",diseffect1); for(i=0;i<k1;i+) printf("%d ",M_Framei);printf("n"); else temp1=M_Frame0.page_no; /物理页面表已满 for(i=1;i<5;i+) M_Framei-1=M_Framei;M_Frame4.page_no=r1; /淘汰最早进入的M_Frame0

8、 /并将所读的逻辑页面调入 for(i=0;i<8;i+)printf("%d ",Access_seriesi);printf("n"); printf("diseffect! %dn",diseffect1); printf("lose %dn",temp1); for(i=0;i<k1;i+) printf("%d ",M_Framei);printf("n"); f1=0; f=diseffect1/8.0; /统计缺页率 printf("dis

9、effect rate of FIFO %fn",f); exit(0); wait(0); for(i=0;i<mframe;i+) M_Framei.page_no=-1; while(p2=fork()=-1) ; /创建子进程2 if(p2=0) for(m=0;m<8;m+) r2=Access_seriesm; /读入逻辑页 for(kk=0;kk<k2;kk+) if(r2!=M_Framekk.page_no) /首先在物理页面中查找 continue; else printf("have found!n"); /找到 for(t

10、=kk+1;t<k2;t+) /调整数组顺序，使刚被访问的页面在最后的位置 M_Framet-1.page_no=M_Framet.page_no; M_Framet-1.page_no=r2; for(i=0;i<k2;i+) printf("%d ",M_Framei.page_no);printf("n"); f2=1; break; if(f2=0) /没有找到，发生缺页 diseffect2+; /缺页率加1 if(k2<mframe) /物理页面还没有分配完 M_Framek2.page_no=r2; /选择空页面分配 M_

11、Framek2.flag='Y'k2+; for(i=0;i<8;i+)printf("%d ",Access_seriesi);printf("n"); printf("diseffect! %dn",diseffect2); for(i=0;i<k2;i+) printf("%d ",M_Framei);printf("n"); else /淘汰最近最久未访问的M_Frame0 temp3=M_Frame0.page_no; for(i=1;i<mframe

12、;i+) M_Framei-1.page_no=M_Framei.page_no; M_Framemframe-1.page_no=r2; /将当前页调入for(i=0;i<8;i+)printf("%d ",Access_seriesi);printf("n"); printf("diseffect %dn",diseffect2); printf("lose %dn",temp3); for(i=0;i<k2;i+) printf("%d ",M_Framei);printf("n"); f2=0; f=diseffect2/8.0; /统计失效率 printf("diseffect rate of LRU %fn",f);exit(0);