实验三 页面调度算法

1、陕西理工孽侏Shaanxi University of Technology实验报告院（系）:数学与计算机科学学院专业班级：学 号：姓 名：实验地点：实验日期： 年 月 日课程名称实验项目名称实验学时实验类型操作系统页面调度算法2设计一、实验目的及要求通过本实验可以加深理解有关虚拟存储器的工作原理，进一步体会和了解页 面替换算法的具体实现方法。二、实验环境PC /Windows 系统/Visual C+6.0三、实验内容实现三种算法：先进先出；OPT； LRU页面序列从指定的文本文件(TXT文件)中取出输出：第一行：每次淘汰的页面号，第二行：显示缺页的总次数/*全局变量*/int mSIZE;

2、 /* 物理块数*/int pSIZE; /*页面号引用串个数*/static int memery10 = 0; /* 物理块中的页号*/static int page100 = 0; /* 页面号引用串 */static int temp10010 = 0; /* 辅助数组*/*置换算法函数*/void FIFO();void LRU();void OPT();/*辅助函数*/void print(unsigned int t);void designBy();void download();void mDelay(unsigned int Delay);/*先进先出页面置换算法*/voi

3、d FIFO()(int memery10 = 0;int time10 = 0; /*记录进入物理块的时间*/int i,j,k,m;int max=0; /*记录换出页*/int count=0; /*记录置换次数*/*前mSIZE个数直接放入*/for(i=0;imSIZE;i+)(memeryi=pagei;timei=i;for(j=0;jmSIZE;j+)tempij=memeryj;for(i=mSIZE;ipSIZE;i+)(/*判断新页面号是否在物理块中*/for(j=0,k=0;jmSIZE;j+)(if(memeryj!=pagei)k+;if(k=mSIZE) /*如果

4、不在物理块中*/(count+;/*计算换出页*/max=time0time1?0:1;for(m=2;mmSIZE;m+)if(timemtimemax)max=m;memerymax=pagei;timemax=i; /*记录该页进入物理块的时间*/for(j=0;jmSIZE;j+)tempij=memeryj;else(for(j=0;jmSIZE;j+)tempij=memeryj;compute();print(count);/*最近最久未使用置换算法*/void LRU()(int memery10 = 0;int flag10 = 0; /*记录页面的访问时间*/int i,j

5、,k,m;int max=0; /*记录换出页*/int count=0; /*记录置换次数*/*前mSIZE个数直接放入*/for(i=0;imSIZE;i+)(memeryi=pagei;flagi=i;for(j=0;jmSIZE;j+)tempij=memeryj;for(i=mSIZE;ipSIZE;i+)(/*判断新页面号是否在物理块中*/for(j=0,k=0;jmSIZE;j+)(if(memeryj!=pagei)k+;elseflagj=i; /*刷新该页的访问时间*/if(k=mSIZE) /*如果不在物理块中*/(count+;/*计算换出页*/max=flag0fla

6、g1?0:1;for(m=2;mmSIZE;m+)if(flagmflagmax)max=m;memerymax=pagei;flagmax=i; /*记录该页的访问时间*/for(j=0;jmSIZE;j+)tempij=memeryj;elsefor(j=0;jmSIZE;j+)tempij=memeryj;compute();print(count);/*最佳置换算法*/void OPT()(int memery10 = 0;int next10 = 0; /*记录下一次访问时间*/int i,j,k,l,m;int max; /*记录换出页*/int count=0; /*记录置换次数

7、*/*前mSIZE个数直接放入*/for(i=0;imSIZE;i+)(memeryi=pagei;for(j=0;jmSIZE;j+)tempij=memeryj;for(i=mSIZE;ipSIZE;i+)(/*判断新页面号是否在物理块中*/for(j=0,k=0;jmSIZE;j+)(if(memeryj!=pagei)k+;if(k=mSIZE) /*如果不在物理块中*/(count+;/*得到物理快中各页下一次访问时间*/ for(m=0;mmSIZE;m+)(for(l=i+1;l=next1?0:1;for(m=2;mnextmax)max=m;/*下一次访问时间都为pSIZE，

8、则置换物理块中第一个*/ memerymax=pagei;for(j=0;jmSIZE;j+)tempij=memeryj;elsefor(j=0;jmSIZE;j+)tempij=memeryj;compute();print(count);四、实验步骤页面置换：在地址映射过程中，若在页面中发现所要访问的页面不在内存中，则产生缺页中 断。当发生缺页中断时，如果操作系统内存中没有空闲页面，则操作系统必须在内存选择一 个页面将其移出内存，以便为即将调入的页面让出空间。而用来选择淘汰哪一页的规则叫做页面置换算法：最佳置换算法(OPT)(理想置换算法)：从主存中移出永远不再需要的页面；如无这 样的页

9、面存在，则选择最长时间不需要访问的页面。于所选择的被淘汰页面将是以后永不使 用的，或者是在最长时间内不再被访问的页面，这样可以保证获得最低的缺页率。先进先出置换算法（FIFO）:是最简单的页面置换算法。这种算法的基本思想是：当需 要淘汰一个页面时，总是选择驻留主存时间最长的页面进行淘汰，即先进入主存的页面先淘 汰。其理由是：最早调入主存的页面不再被使用的可能性最大。最近最久未使用（LRU）算法：这种算法的基本思想是：利用局部性原理，根据一个作 业在执行过程中过去的页面访问历史来推测未来的行为。它认为过去一段时间里不曾被访问 过的页面，在最近的将来可能也不会再被访问。所以，这种算法的实质是:当需要淘汰一个页