操作系统页面置换算法代码

《操作系统页面置换算法代码》由会员分享，可在线阅读，更多相关《操作系统页面置换算法代码（33页珍藏版）》请在装配图网上搜索。

1、通达学院课程设计I报告（2018/2019学年第2学期）题目：页面置换算法专业计算机科学与技术学生姓名班级学号指导教师指导单位计算机学院日期指导教师成绩评定表学生姓名班级学号专业计算机科学与技术评分内容评分标准优秀良好中等差平时成绩认真对待课程设计，遵守实验室规定，上机不迟到早退，不做和设计无关的事设计成果设计的科学、合理性功能丰富、符合题目要求界面友好、外观漂亮、大方程序功能执行的正确性程序算法执行的效能设计报告设计报告正确合理、反映系统设计流程文档内容详实程度文档格式规范、排版美观验收答辩简练、准确阐述设计内容，能准确有条理回答各 种问题，系统演示顺利。评分等级指导教师简短评语指导教师签名

2、日期备注评分等级有五种：优秀、良好、中等、及格、不及格页面置换算法一、课题内容和要求通过实现页面置换的四种算法，理解虚拟存储器的概念、实现方法，页面分配 的总体原则、进程运行时系统是怎样选择换出页面的 ，并分析四种不同的算法 各自的优缺点是哪些。以下算法都要实现：1）最佳置换算法（OPT）：将以后永不使用的或许是在最长（未来）时间内不再被访 问的页面换出。2）先进先出算法（FIFO）：淘汰最先进入内存的页面，即选择在内存中驻留时间 最久的页面予以淘汰。3）最近最久未使用算法（LRU）:淘汰最近最久未被使用的页面。4）最不经常使用算法（LFU）设计要求：1、编写算法，实现页面置换算法；2、针对内

3、存地址引用串，运行页面置换算法进行页面置换；3、算法所需的各种参数由输入产生 （手工输入或者随机数产生）；4、输出内存驻留的页面集合，缺页次数以及缺页率；二、需求分析通过这次实验，加深对虚拟内存页面置换概念的理解，进一步掌握先进先出FIFO、最佳置换OPI和最近最久未使用LRU页面置换算法及最不经常使用算法 LFU的 实现方法。通过已知最小物理块数、页面个数、页面访问序列、及采用置换方式可以得出页面置换的缺页次数和缺页率，及每次缺页时物理块中存储！(1) 输入的形式页面序列物理块数、页面数、页面序列(2) 输出的形式驻留页面集合、缺页数、缺页率注：如果命中用*表示，为空用-1表示(3) 程序所

4、能达到的功能模拟先进先出FIFO、最佳置换OPI、最近最久未使用LRU页面置换算法和最不 经常使用算法LFU的工作过程。假设内存中分配给每个进程的最小物理块数为 m,在进程运行过程中要访问的页面个数为n,页面访问序列为P1,，Pr分别利用不同的页面置换算法调度进程的页面访问序列，给出页面访问序列的置换过程，计 算每种算法缺页次数和缺页率。测试数据,包括正确的输入及其输出结果和含有错误的输入及其输出结果。三、概要设计说明本程序中用到的所有抽象数据类型的定义、主程序的流程以及各程序模块之间的层次(调用)关系。int mSIZE; /* 物理块数 */int pSIZE; /*页面号引用串个数*/s

5、tatic int memery10=0; /*物理块中的页号 */static int page100=0; /* 页面号引用串 */static int temp10010=0; /*辅助数组 */*置换算法函数*/void FIFO();void LRU();void OPT();void LFU();/*输出格式控制函数*/void print(un sig ned int t);流程图如下：FIFOLRU算法OPT算法LFU算法输出格式控制函数主函数调用FIFO算法是最简单的页面置换算法。FIFO页面置换算法为每个页面记录了调到 内存的时间，当必须置换页面时会选择最旧的页面。注意，并

6、不需要记录调入 页面的确切时间，可以定义一个数，来管理所有的内存页面。置换是队列的首 个页面。然后加1，当这个数达到物理块数的值了 ，清零从头开始。LRU使用最近的过去作为不远将来的近似，那么可以置换最长时间没有使用的 页。这种方法称为最近最少使用算法。LRU置换将每个页面与它的上次使用的 时间关联起来。当需要置换页面时，LRU选择最长时间没有使用的页面。这种 策略可当作在时间上向后看而不是向前看的最优页面置换OPT是用一维数组page存储页面号序列，memery是存储装入物理块中的页 面。数组next记录物理块中对应页面的最后访问时间。每当发生缺页时，就 从物理块中找出最后访问时间最大的页面

7、，调出该页，换入所缺的页面。若物 理块中的页面都不再使用，则每次都置换物理块中第一个位置的页面。LFU是用一个一维数组time记录每个物理块被访问的次数，当物理块满且发生 置换的时候，将最小的time数组上位置的数置换出来，如果一样就置换第一个 数。四、详细设计1、输出格式控制函数：void print(un sig ned int t)int flag;for(k=0;k=(pSIZE-1)/30;k+)/k为行数for(i=30*k;(ipSIZE) &(i30*(k+1);i+)/开头字符串输出if(i+1)%30=0)|(i+1)%30)&(i=pSIZE-1)prin tf(%dn,

8、pagei);elseprin tf(%d ”,pagei);for(j=0;jmSIZE;j+)/历次置换情况输出for(i=0;i=j)/物理块未占满的情况prin tf( |%d|,tempij);elseprin tf( | |);for(i=2+30*k;(ipSIZE)&(i30*(k+1);i+)for(flag=0,l=0;lmSIZE;l+)if(tempil=tempi-1l)flag+;if(flag=mSIZE)/*页面在物理块中*/prin tf( |*|);elseprin tf( |%d|,tempij);if(i%30=0)con ti nue;prin tf(

9、n);printf(n);printf(缺页次数:%dtt,t);printf(缺页率:%.2f%n,(float)t/pSIZE*100);printf(n);2、FIFO 算法:void FIFO()int memery10=-1, -1 , -1 , -1 , -1;int i,j,k,m;int max=O; /* 记录换出页*/int count=0; /*记录置换次数*/for(i=0;ipSIZE;i+)/*判断新页面号是否在物理块中*/for(j=0,k=0;jmSIZE;j+)if(memeryj!=pagei)k+;if(k=mSIZE) /* 如果不在物理块中*/coun

10、 t+;/*计算换出页*/memerymax=pagei;max+;if(max=mSIZE)max=0;for(j=0;jmSIZE;j+)tempi j=memeryj;printf(FIFO 算法:”);prin t(co un t);3、LRU算法：void LRU()int memery10=-1, -1 , -1 , -1 , -1;int flag1O=O; /*记录页面的访问时间*/int i,j,k,m,c=0;int max=0; /* 记录换出页*/int count=0; /*记录置换次数*/for(i=0;ipSIZE;i+)/*判断新页面号是否在物理块中*/for(

11、j=0,k=0;jmSIZE;j+)k+;elseflagj=i; /*刷新该页的访问时间*/if(k=mSIZE) /* 如果不在物理块中*/coun t+;/*计算换出页*/if(memerymSIZE-1=0)memeryc=pagei;flagc=i;c+;elsemax=flag0flag1?0:1;for(m=2;mmSIZE;m+)if(flagmflagmax)max=m;memerymax=pagei;flagmax=i; /*记录该页的访问时间*/for(j=0;jmSIZE;j+)tempi j=memery j;printf(LRU 算法:”);prin t(co un

12、 t);4、OPT算法：void OPT()int memery10=-1, -1 , -1 , -1 , -1;int next10=0; /*记录下一次访问时间 */int i,j,k,l,m,c=0;int max; /*记录换出页*/int count=0; /*记录置换次数*/for(i=0;ipSIZE;i+)/*判断新页面号是否在物理块中*/for(j=0,k=0;jmSIZE;j+)if(memeryj!=pagei)k+;if(k=mSIZE) /* 如果不在物理块中*/coun t+;if(memerymSIZE-1=0)memeryc=pagei;c+;else,l最大的

13、被替换*/*得到物理快中各页下一次访问时间for(m=0;mmSIZE;m+)for(l=i+1;l=next1?0:1;for(m=2;m nextmax) max=m; memerymax=pagei;for(j=0;jmSIZE;j+)tempi j=memeryj;printf(OPT 算法:);prin t(co un t);5、LFU算法：void LFU()int memery10=-1, -1 , -1 , -1 , -1;int time10=0;int i,j,k,l,m,c=O; int ma x;int coun t=0;/*记录访问次数*/*记录换出页*/*记录置换次

14、数*/for(i=0;ipSIZE;i+)/*判断新页面号是否在物理块中*/for(j=0,k=0;jmSIZE;j+)if(memeryj!=pagei)k+;elsetime j+;if(k=mSIZE) /* 如果不在物理块中*/coun t+;if(memerymSIZE-1=0)memeryc=pagei;timec+;C+；else/*计算换出页，次数少的被置换*/max=time0=time1?0:1;for(m=2;mmSIZE;m+) if(timemtimemax) max=m; memerymax=pagei;for(j=0;jmSIZE;j+)tempi j=memer

15、yj;printf(LFU 算法:);prin t(co un t);五、测试数据及其结果分析测试数据：(1)页面个数:10最小物理块数:3页面序列：1212682413页面个数:20最小物理块数:3页面序列：诂怖入恂岬堆刃-10 : 3甯嫡入贡血号数隹UlOOh 10晞论扰输入贞血号引用申(戦输入.无需隔开1212682413e-dle:zBlJ上0Start Mrt3 4 1=-_8 4 1缺页狀数：7缺页率盘70.00%irmtuirri电品 tl 0x0axmcziiticiii time : 11. 073 smrm m:pjbLPi.Tri.Hr=irM ” i.m” u 丄4my

16、- = .一Ftocw *nu理匸啊 vithi0 f0 urit匸仙,* EiMSi：0D FAFJlJigj数据二截图： E;炸寡;旳収ffll网錢色w-阴输人辆理块熬训21。）： 3嘴入员閒占薙败=100）： 20厳依戏输入页面片川用ff （直媒输入 无需隔Jf）：贡面SU-c -图5六、调试过程中的问题(1)算法缺陷问题1、原来代码规定了前mSIZE个数据是直接放入数组的，但是通过多组数据的测 试发现当前mSIZE个数据中有重复的数据时，算法并不能判定命中，而是判定 缺页，这显然是错误的。于是重新思考数据放入问题，认为只有第一个数据可 以直接放入，从第二个开始就要进行循环判断，于是对四

17、项算法进行改进，加 入一个物理块数组最后一个值是否为初始值的判断条件进行循环解决了问题。2、最初物理块数组的初始值是定为0,之前是通过判断物理块数组的最后一个值是否为初值判断是否进行置换的，但是当数据中有0值就会干扰这个判断条 件，思考页面号为0也是客观存在的，所以这又是一个bug。然后我就令初值 为-1，页面号为负当然是不可能的，可是当我把赋值0改为-1，再运行时，又 出现两个算法计算出错。经过多次排查，我认为算法主体是正确的，最终发现是因为赋初始值出错的问题。因为赋0时，数组整体都为0，但赋-1时只是第一 个数据是-1，而不是数组全体。这是一个低级错误，最后我通过对数组全体赋 值-1解决了

18、问题（2）输出界面冋题输出界面我是通过一个输出格式控制函数来控制，这方面的问题比较难以发现，因为输出结果出错，我一般对算法函数进行排查，忽略了输出控制函数。1、 一开始如果命中我是用空格来代替，发现并不直观。于是我将空格改为|*| ，这样既和数据集合统一了 ，观察也更加直观。还有就是物理块未被全部占 用时，页面集合会有-1产生，虽说是正确的，但我觉得不太美观，于是我加了 一段代码，把-1用|代替，这样看上去就能知道物理块未被全部占用。2、当页面号数过大时，输出的页面集合缺失，经过查找错误，发现是换行控制 条件有问题，经过增加换行的列数解决了这个问题。七、参考文献和查阅的资料1、 （C 语言中文

19、网）2、操作系统教程人民邮电出版社八、程序设计总结这个程序的主要思想就是要实现换页、怎么样输出淘汰的序列、计算缺页次数 和缺页率。在程序中主要就是将在访冋串中将来再也不出现的或是在离当前最 远的位置上出现的页淘汰掉。当距离相等的时候就比较使用的次数，淘汰使用次数较少的那页。该过程共有四个页面置换算法函数及输出格式控制的函数当主函数调用任意其中函数时来实现其算法。通过这次课程设计的实践，我能够熟练的掌握一些关于内存分配管理的一些算 法。而在实现FIFO算法后，由于没能掌握LRU算法的过程导致实现时花了很多 时间。在调试的过程中也出现的大多是关于内存分配和数组地址越界的问题，比如关于循环时各个数的

20、递增，还有就是显示给个数组的内容等问题。就因为 这些问题，多次造成了淘汰序列出错。在以后的实验中我会注意的。本次实验我也更加体会到模块化的重要性，当输出出错时，逐模块排查不仅提高了效率，也节省了精力。九、源代码附录#in elude #in elude int mSIZE; /* 物理块数 */int pSIZE; /*页面号引用串个数*/static int memery10=0; /*物理块中的页号 */static int page100=0; /*页面号引用串 */static int temp10010=0; /*辅助数组 */*置换算法函数*/void FIFO();void LR

21、U();void OPT();void LFU();/*输出格式控制函数*/ void print(un sig ned int t);void mai n()int i,k;system(color 0E);printf(请输入物理块数(M=10): ”)；scan f(%d,&mSIZE);printf(请输入页面号数(P=100):);scan f(%d,&pSIZE);无需隔开)：);puts(请依次输入页面号引用串(连续输入,for(i=0;ipSIZE;i+)scan f(%1d,&pagei);system(cls);system(color OF);FIFO();LRU();O

22、PT();LFU();void print(un sig ned int t) int i,j,k,l;int flag;for(k=0;k=(pSIZE-1)/30;k+)/k 为行数for(i=30*k;(ipSIZE) &(i30*(k+1);i+)if(i+1)%30=0)|(i+1)%30)&( i=pSIZE-1)prin tf(%dn,pagei);elseprin tf(%d ”,pagei);for(j=0;jmSIZE;j+)/历次置换情况输出for(i=0;i=j)prin tf( |%d|,tempij);elseprin tf( | |);/开头字符串输出/物理块未占

23、满的情况for(i=2+30*k;(ipSIZE)&(i30*(k+1);i+)for(flag=0,l=0;lmSIZE;l+)if(tempil=tempi-1l)flag+;if(flag=mSIZE)/*页面在物理块中*/prin tf( |*|);elseprin tf( |%d|,tempij);if(i%30 = 0)con ti nue;prin tf(n);printf(n);printf(缺页次数:%dtt,t);printf(缺页率:%.2f%n,(float)t/pSIZE*100);printf(n);/*先进先出页面置换算法*/ void FIFO()int mem

24、ery10=-1,-1,-1,-1,-1;int i,j,k,m;int max=0; /* 记录换出页*/int count=0; /* 记录置换次数*/for(i=0;ipSIZE;i+)/*判断新页面号是否在物理块中*/for(j=0,k=0;jmSIZE;j+)if(memeryj!=pagei)k+;if(k=mSIZE) /* 如果不在物理块中*/coun t+;/*计算换出页*/memerymax=pagei;max+;if(max=mSIZE)max=O;for(j=0;jmSIZE;j+)tempi j=memeryj;printf(FIFO 算法:”);prin t(co

25、un t);/*最近最久未使用置换算法*/void LRU()int memery10=-1,-1,-1,-1,-1;int flag10=0; /*记录页面的访问时间*/int i,j,k,m,c=0;int max=0; /* 记录换出页*/int count=0; /* 记录置换次数*/*判断新页面号是否在物理块中 */for(j=0,k=0;jmSIZE;j+)if(memeryj!=pagei)k+;elseflagj=i; /*刷新该页的访问时间*/if(k=mSIZE) /* 如果不在物理块中*/coun t+;/*计算换出页*/if(memerymSIZE-1=-1)memer

26、yc=pagei;flagc=i;c+;elsemax=flag0flag1?0:1;if(flagmflagmax)max=m;memerymax=pagei;flagmax=i; /* 记录该页的访问时间*/for(j=0;jmSIZE;j+)tempi j=memeryj;printf(LRU 算法:”);prin t(co un t);void OPT()int memery10=-1,-1,-1,-1,-1;int next10=0; /* 记录下一次访问时间 */int i,j,k,l,m,c=0;int max; /*记录换出页*/int count=0; /*记录置换次数*/f

27、or(i=0;ipSIZE;i+)/*判断新页面号是否在物理块中*/for(j=0,k=0;jmSIZE;j+)if(memeryj!=pagei)k+;if(k=mSIZE) /* 如果不在物理块中*/coun t+;if(memerymSIZE-1=-1)memeryc=pagei;c+;else,l最大的被替换*/*得到物理快中各页下一次访问时间for(m=0;m=next1?0:1;for(m=2;m nextmax) max=m;memerymax=pagei; for(j=0;jmSIZE;j+)tempi j=memeryj;printf(OPT 算法:);prin t(co u

28、n t);void LFU()int memery10=-1,-1,-1,-1,-1;int time10=0;/*记录访问次数*/int i,j,k,l,m,c=O;int max;/*记录换出页*/int count=0;/*记录置换次数*/for(i=0;ipSIZE;i+)/*判断新页面号是否在物理块中*/for(j=0,k=0;jmSIZE;j+)if(memeryj!=pagei)k+;elsetime j+;if(k=mSIZE) /* 如果不在物理块中*/coun t+;if(memerymSIZE-1=-1)memeryc=pagei;timec+;C+；else/*计算换出页，次数少的被置换*/max=time0=time1?0:1;for(m=2;mmSIZE;m+) if(timemtimemax) max=m; memerymax=pagei;for(j=0;jmSIZE;j+)tempi j=memeryj;printf(LFU 算法:);prin t(co un t);