计算机操作系统实验三页面置换算法模拟实验

计算机工程学院 实验报告书 课程名：《 操作系统原理A 》
题 目：
虚拟存储器管理 页面置换算法模拟实验 班 级：
学 号：
姓 名：
评语：
成绩：
指导教师：
批阅时间：
年 月 日 一、实验目的与要求 1. 目的：
请求页式虚存管理是常用的虚拟存储管理方案之一。通过请求页式虚存管理中对页面置换算法的模拟，有助于理解虚拟存储技术的特点，并加深对请求页式虚存管理的页面调度算法的理解。

2. 要求：
本实验要求使用C语言编程模拟一个拥有若干个虚页的进程在给定的若干个实页中运行、并在缺页中断发生时分别使用FIFO和LRU算法进行页面置换的情形。其中虚页的个数可以事先给定（例如10个），对这些虚页访问的页地址流（其长度可以事先给定，例如20次虚页访问）可以由程序随机产生，也可以事先保存在文件中。要求程序运行时屏幕能显示出置换过程中的状态信息并输出访问结束时的页面命中率。程序应允许通过为该进程分配不同的实页数，来比较两种置换算法的稳定性。

二、实验说明 1．设计中虚页和实页的表示 本设计利用C语言的结构体来描述虚页和实页的结构。

pn pfn time pn pfn next 虚页结构 实页结构 在虚页结构中，pn代表虚页号，因为共10个虚页，所以pn的取值范围是0—9。pfn代表实页号，当一虚页未装入实页时，此项值为-1；
当该虚页已装入某一实页时，此项值为所装入的实页的实页号pfn。time项在FIFO算法中不使用，在LRU中用来存放对该虚页的最近访问时间。

在实页结构中中，pn代表虚页号，表示pn所代表的虚页目前正放在此实页中。pfn代表实页号，取值范围（0—n-1）由动态指派的实页数n所决定。next是一个指向实页结构体的指针，用于多个实页以链表形式组织起来，关于实页链表的组织详见下面第4点。

2．关于缺页次数的统计 为计算命中率，需要统计在20次的虚页访问中命中的次数。为此，程序应设置一个计数器count，来统计虚页命中发生的次数。每当所访问的虚页的pfn项值不为-1，表示此虚页已被装入某实页内，此虚页被命中，count加1。最终命中率=count/20*100%。

3．LRU算法中“最近最久未用”页面的确定 为了能找到“最近最久未用”的虚页面，程序中可引入一个时间计数器countime，每当要访问一个虚页面时，countime的值加1，然后将所要访问的虚页的time项值设置为增值后的当前countime值，表示该虚页的最后一次被访问时间。当LRU算法需要置换时，从所有已分配实页的虚页中找出time值为最小的虚页就是“最近最久未用”的虚页面，应该将它置换出去。

4．算法中实页的组织 因为能分配的实页数n是在程序运行时由用户动态指派的，所以应使用链表组织动态产生的多个实页。为了调度算法实现的方便，可以考虑引入free和busy两个链表：free链表用于组织未分配出去的实页，首指针为free_head，初始时n个实页都处于free链表中；
busy链表用于组织已分配出去的实页，首指针为busy_head，尾指针为busy_tail，初始值都为null。当所要访问的一个虚页不在实页中时，将产生缺页中断。此时若free链表不为空，就取下链表首指针所指的实页，并分配给该虚页。若free链表为空，则说明n个实页已全部分配出去，此时应进行页面置换：对于FIFO算法要将busy_head 所指的实页从busy链表中取下，分配给该虚页，然后再将该实页插入到busy链表尾部；
对于LRU算法则要从所有已分配实页的虚页中找出time值为最小的虚页，将该虚页从装载它的那个实页中置换出去，并在该实页中装入当前正要访问的虚页。

三、程序流程图 四、主要程序清单 #include <stdio.h> #include <stdlib.h> /*全局变量*/ int mSIZE; /*物理块数*/ int pSIZE; /*页面号引用串个数*/ static int memery[10]={0}; /*物理块中的页号*/ static int page[100]={0}; /*页面号引用串*/ static int temp[100][10]={0}; /*辅助数组*/ /*置换算法函数*/ void FIFO(); void LRU(); void OPT(); /*辅助函数*/ void print(unsigned int t); void designBy(); void download(); void mDelay(unsigned int Delay); /*主函数*/ void main() { int i,k,code; printf(“请输入物理块的个数(M<=10)：“); scanf(“%d“,&mSIZE); printf(“请输入页面号引用串的个数(P<=100)：“); scanf(“%d“,&pSIZE); puts(“请依次输入页面号引用串(连续输入，无需隔开)：“); for(i=0;i<pSIZE;i++) scanf(“%1d“,&page[i]); download(); do { puts(“输入的页面号引用串为：“); for(k=0;k<=(pSIZE-1)/20;k++) { for(i=20*k;(i<pSIZE)&&(i<20*(k+1));i++) { if(((i+1)%20==0)||(((i+1)%20)&&(i==pSIZE-1))) printf(“%d＼n“,page[i]); else printf(“%d “,page[i]); } } printf(“* * * * * * * * * * * * * * * * * * * * * * *＼n“); printf(“* 请选择页面置换算法：＼t＼t＼t *＼n“); printf(“* -----------------------------------------*＼n“); printf(“* 1.先进先出(FIFO) 2.最近最久未使用(LRU) *＼n“); printf(“* 3.退出 *＼n“); printf(“* * * * * * * * * * * * * * * * * * * * * * *＼n“); printf(“请选择操作：[ ]＼b＼b“); scanf(“%d“,&code); switch(code) { case 1: FIFO(); break; case 2: LRU(); break; case 3: OPT(); break; case 4: system(“cls“); //system(“color 0A“); exit(0); default: printf(“输入错误，请重新输入：“); } printf(“按任意键重新选择置换算法：>>>“); getchar(); } while (code!=4); getchar(); } /*载入数据*/ void download() { printf(“＼nFinish.＼n载入成功!“); } /*设置延迟*/ void mDelay(unsigned int Delay) { unsigned int i; for(;Delay>0;Delay--) { for(i=0;i<124;i++) { printf(“ ＼b“); } } } /*显示设计者信息*/ void print(unsigned int t) { int i,j,k,l; int flag; for(k=0;k<=(pSIZE-1)/20;k++) { for(i=20*k;(i<pSIZE)&&(i<20*(k+1));i++) { if(((i+1)%20==0)||(((i+1)%20)&&(i==pSIZE-1))) printf(“%d＼n“,page[i]); else printf(“%d “,page[i]); } for(j=0;j<mSIZE;j++) { for(i=20*k;(i<mSIZE+20*k)&&(i<pSIZE);i++) { if(i>=j) printf(“ |%d|“,temp[i][j]); else printf(“ | |“); } for(i=mSIZE+20*k;(i<pSIZE)&&(i<20*(k+1));i++) { for(flag=0,l=0;l<mSIZE;l++) if(temp[i][l]==temp[i-1][l]) flag++; if(flag==mSIZE)/*页面在物理块中*/ printf(“ “); else printf(“ |%d|“,temp[i][j]); } /*每行显示20个*/ if(i%20==0) continue; printf(“＼n“); } } printf(“----------------------------------------＼n“); printf(“缺页次数：%d＼t＼t“,t+mSIZE); printf(“缺页率：%d/%d＼n“,t+mSIZE,pSIZE); printf(“置换次数：%d＼t＼t“,t); printf(“访问命中率：%d%%＼n“,(pSIZE-(t+mSIZE))*100/pSIZE); printf(“----------------------------------------＼n“); } /*计算过程延迟*/ void compute() { int i; printf(“正在进行相关计算，请稍候“); for(i=0;i++<30;printf(“＼b“)); for(i=0;i++<30;printf(“ “)); for(i=0;i++<30;printf(“＼b“)); } /*先进先出页面置换算法*/ void FIFO() { int memery[10]={0}; int time[10]={0}; /*记录进入物理块的时间*/ int i,j,k,m; int max=0; /*记录换出页*/ int count=0; /*记录置换次数*/ /*前mSIZE个数直接放入*/ for(i=0;i<mSIZE;i++) { memery[i]=page[i]; time[i]=i; for(j=0;j<mSIZE;j++) temp[i][j]=memery[j]; } for(i=mSIZE;i<pSIZE;i++) { /*判断新页面号是否在物理块中*/ for(j=0,k=0;j<mSIZE;j++) { if(memery[j]!=page[i]) k++; } if(k==mSIZE) /*如果不在物理块中*/ { count++; /*计算换出页*/ max=time[0]<time[1]?0:1; for(m=2;m<mSIZE;m++) if(time[m]<time[max]) max=m; memery[max]=page[i]; time[max]=i; /*记录该页进入物理块的时间*/ for(j=0;j<mSIZE;j++) temp[i][j]=memery[j]; } else { for(j=0;j<mSIZE;j++) temp[i][j]=memery[j]; } } compute(); print(count); } /*最近最久未使用置换算法*/ void LRU() { int memery[10]={0}; int flag[10]={0}; /*记录页面的访问时间*/ int i,j,k,m; int max=0; /*记录换出页*/ int count=0; /*记录置换次数*/ /*前mSIZE个数直接放入*/ for(i=0;i<mSIZE;i++) { memery[i]=page[i]; flag[i]=i; for(j=0;j<mSIZE;j++) temp[i][j]=memery[j]; } for(i=mSIZE;i<pSIZE;i++) { /*判断新页面号是否在物理块中*/ for(j=0,k=0;j<mSIZE;j++) { if(memery[j]!=page[i]) k++; else flag[j]=i; /*刷新该页的访问时间*/ } if(k==mSIZE) /*如果不在物理块中*/ { count++; /*计算换出页*/ max=flag[0]<flag[1]?0:1; for(m=2;m<mSIZE;m++) if(flag[m]<flag[max]) max=m; memery[max]=page[i]; flag[max]=i; /*记录该页的访问时间*/ for(j=0;j<mSIZE;j++) temp[i][j]=memery[j]; } else { for(j=0;j<mSIZE;j++) temp[i][j]=memery[j]; } } compute(); print(count); } /*最佳置换算法*/ void OPT() { int memery[10]={0}; int next[10]={0}; /*记录下一次访问时间*/ int i,j,k,l,m; int max; /*记录换出页*/ int count=0; /*记录置换次数*/ /*前mSIZE个数直接放入*/ for(i=0;i<mSIZE;i++) { memery[i]=page[i]; for(j=0;j<mSIZE;j++) temp[i][j]=memery[j]; } for(i=mSIZE;i<pSIZE;i++) { /*判断新页面号是否在物理块中*/ for(j=0,k=0;j<mSIZE;j++) { if(memery[j]!=page[i]) k++; } if(k==mSIZE) /*如果不在物理块中*/ { count++; /*得到物理快中各页下一次访问时间*/ for(m=0;m<mSIZE;m++) { for(l=i+1;l<pSIZE;l++) if(memery[m]==page[l]) break; next[m]=l; } /*计算换出页*/ max=next[0]>=next[1]?0:1; for(m=2;m<mSIZE;m++) if(next[m]>next[max]) max=m; /*下一次访问时间都为pSIZE,则置换物理块中第一个*/ memery[max]=page[i]; for(j=0;j<mSIZE;j++) temp[i][j]=memery[j]; } } if(k==mSIZE) /*如果不在物理块中*/ { count++; /*得到物理快中各页下一次访问时间*/ for(m=0;m<mSIZE;m++) { for(l=i+1;l<pSIZE;l++) if(memery[m]==page[l]) break; next[m]=l; } /*计算换出页*/ max=next[0]>=next[1]?0:1; for(m=2;m<mSIZE;m++) if(next[m]>next[max]) max=m; /*下一次访问时间都为pSIZE,则置换物理块中第一个*/ memery[max]=page[i]; for(j=0;j<mSIZE;j++) temp[i][j]=memery[j]; } } 五、程序运行结果 ①FIFO ②LRU 六、实验体会 在做该次作业的时候，通过对课本相关内容的温习，以及对自己在网络上找到的一些资源的了解。我对操作系统中页面调度的算法有了很大程度的了解，加深了对课程上知识的理解，也懂得了如何在程序中将这些算法实现，在程序中基本上实现了所要求的算法以及相关的性能分析，基本上实现了课程的要求。   这次作业也暴露了自己在某些方面的不足之处，自己的语言功底有一定的不足，以及一开始对某个算法不够熟悉，将算法实现设计的比较复杂，此次自己的程序存在一些思想上的漏洞，反映出此次程序设计的要求有了一定的限制。