LRU页面调度算法实现

./LRU页面调度算法实现学院计算机科学与技术专业计算机科学与技术学号学生姓名指导教师2014.目录实验要求…………………2实验目的…………………2实验容…………………2相关知识…………………2实验原理…………………3流程图……………………4源代码……………………5运行结果…………………9实验心得…………………1010.参考文献…………………11LRU页调度算法实现一实验要求：1．不同的功能使用不同的函数实现〔模块化,对每个函数的功能和调用接口要注释清楚。对程序其它部分也进行必要的注释。2．对系统进行功能模块分析、画出总流程图和各模块流程图。3．用户界面要求使用方便、简洁明了、美观大方、格式统一。所有功能可以反复使用,最好使用菜单。4．通过命令行相应选项能直接进入某个相应菜单选项的功能模块。5．所有程序需调试通过。二实验目的：将课本上的理论知识和实际有机的结合起来,独立分析和解决实际问题的机会。进一步巩固和复习操作系统的基础知识。培养学生结构化程序、模块化程序设计的方法和能力。提高学生调试程序的技巧和软件设计的能力。提高学生分析问题、解决问题以及综合利用C语言进行程序设计的能力。三实验容：程序应模拟实现LRU算法思想,对n个页面实现模拟调度。四相关知识：1．虚拟存储器的引入：局部性原理：程序在执行时在一较短时间仅限于某个部分；相应的,它所访问的存储空间也局限于某个区域,它主要表现在以下两个方面：时间局限性和空间局限性。2．虚拟存储器的定义：虚拟存储器是只具有请求调入功能和置换功能,能从逻辑上对存容量进行扩充的一种存储器系统。3．虚拟存储器的实现方式：分页请求系统,它是在分页系统的基础上,增加了请求调页功能、页面置换功能所形成的页面形式虚拟存储系统。请求分段系统,它是在分段系统的基础上,增加了请求调段及分段置换功能后,所形成的段式虚拟存储系统。五．实验原理：目前有许多页面调度算法,本实验主要涉及最近最久未使用调度算法。本实验使用页面调度算法时作如下假设,进程在创建时由操作系统为之分配一个固定数目物理页,执行过程中物理页的数目和位置不会改变。也即进程进行页面调度时只能在分到的几个物理页中进行。LRU基本思想：LRU是LeastRecentlyUsed的缩写,即最近最少使用页面置换算法,是为虚拟页式存储管理服务的。关于操作系统的存管理,如何节省利用容量不大的存为最多的进程提供资源,一直是研究的重要方向。而存的虚拟存储管理,是现在最通用,最成功的方式——在存有限的情况下,扩展一部分外存作为虚拟存,真正的存只存储当前运行时所用得到信息。这无疑极扩充了存的功能,极提高了计算机的并发度。虚拟页式存储管理,则是将进程所需空间划分为多个页面,存中只存放当前所需页面,其余页面放入外存的管理方式。LRU算法的提出,是基于这样一个事实：在前面几条指令中使用频繁的页面很可能在后面的几条指令中频繁使用。反过来说,已经很久没有使用的页面很可能在未来较长的一段时间不会被用到。这个,就是著名的局部性原理——比存速度还要快的cache,也是基于同样的原理运行的。因此,我们只需要在每次调换时,找到最近最少使用的那个页面调出存。这就是LRU算法的全部容。实验中是用一维数组page[pSIZE]存储页面号序列,memery[mSIZE]是存储装入物理块中的页面。数组flag[10]标记页面的访问时间。每当使用页面时,刷新访问时间。发生缺页时,就从物理块中页面标记最小的一页,调出该页,换入所缺的页面。六流程图：如下页所示

开始

开始载入页号序列,从第0个得到页号将页号放入物理块中,编号加1引用串编号大于物理块数?页号在物理块中?结束根据选择的置换算法完成置换页号序列载完?图1实验流程图七源代码#include<stdio.h>#include<stdlib.h>intmSIZE;/*物理块数*/intpSIZE;/*页面号引用串个数*/intmemory[10]={-1,-1,-1,-1,-1,-1,-1,-1,-1,-1};/*物理块中的页号*/intpage[100]={0};/*页面号引用串*/inttemp[100][10];voidDelay<>;voidLRU<>;voiddesign<>;voiddisplay<intm>;voidmain<>{inti,j,code;design<>; printf<"请按任意键进行初始化操作...\n">; printf<"┗━━━━━━━━━━━━━━━━━━━━━━━\n">;printf<">>>">; getchar<>; system<"cls">; printf<"请输入物理块的个数<M<=10>：">; scanf<"%d",&mSIZE>;printf<"请输入页面号引用串的个数<P<=100>：">; scanf<"%d",&pSIZE>; puts<"请依次输入页面号引用串：">; for<i=0;i<pSIZE;i++>scanf<"%1d",&page[i]>; for<i=0;i<100;i++> for<j=0;j<10;j++> temp[i][j]=-1; system<"cls">;do{ printf<"**********************\n">;printf<"*请选择页面调度算法：\t\t\t*\n">; printf<"*\n">;printf<"*1.最近最久未使用<LRU>*\n">; printf<"*0.退出*\n">; printf<"**********************\n">;printf<"请选择操作：[]\b\b">;scanf<"%d",&code>;switch<code>{case1:LRU<>; system<"pause">;system<"cls">;break;case0: printf<"┃使用!┃\n">; printf<"┗━━━━━━━━━━━━━━━━┛\n">;exit<0>; default: printf<"输入错误,请重新输入：">;}printf<"按任意键重新选择置换算法：>>>">; getchar<>; system<"cls">;}while<code!=2>; getchar<>;}voiddesign<>{ printf<"┏━━━━━━━━━━━━━━━━━━━━━━━┓\n">; printf<"┃页面调度算法┃\n">;printf<"┃班级:11非师┃\n">; printf<"┃学号:┃\n">; printf<"┣━━━━━━━━━━━━━━━━━━━━━━━┫\n">;}voiddisplay<intm>{ inti,j,k;for<k=0;k<pSIZE;k++> { printf<"%d",page[k]>; } printf<"\n">; for<j=0;j<mSIZE;j++> { for<i=0;i<pSIZE;i++> { if<temp[i][j]==-1> printf<"">; else printf<"|%d|",temp[i][j]>; } printf<"\n">; } printf<"\n">; printf<"缺页次数：%d\t\t",m+mSIZE>; printf<"缺页率：%d%%\n",<m+mSIZE>*100/pSIZE>; printf<"访问次数：%d\t\t",pSIZE-<m+mSIZE>>; printf<"访问命中率：%d%%\n",<pSIZE-<m+mSIZE>>*100/pSIZE>; printf<"\n">; }/*最近最久未使用置换算法*/voidLRU<>{intmemory[10]={-1,-1,-1,-1,-1,-1,-1,-1,-1,-1};intflag[10]={0};/*记录进入物理块的时间*/ inti,j,m;intmax=0;/*记录换出页*/intcount=0;/*记录置换次数*/intt=1;//用来记录已经存入数的物理块数； memory[0]=page[0]; temp[0][0]=page[0];for<i=1;i<pSIZE;i++>{ for<j=0;j<mSIZE;j++> { if<page[i]==memory[j]> { flag[j]=i; break; } } if<page[i]==memory[j]> continue; if<page[i]!=memory[j]>//不在物理块中 { if<t<mSIZE> { for<intk=0;k<mSIZE;k++> { if<memory[k]==-1> { memory[k]=page[i]; flag[k]=i; t++; break; } } for<j=0;j<mSIZE;j++> temp[i][j]=memory[j]; } if<t==mSIZE> { t++; continue; } if<t>=mSIZE>//物理块中已满{count++;max=flag[0]<flag[1]?0:1; for<m=2;m<mSIZE;m++> if<flag[m]<flag[max]> max=m;memory[max]=page[i];flag[max]=i;//记录该页进入物理块的时间for<j=0;j<mSIZE;j++> temp[i][j]=memory[j];} } } display<count>;}八运行结果运行环境——VisualC++6.01.进入界面2.算法演示结果：3．退出程序：九实验心得通过此次的实验,我更加了解了全局替换策略,了解到先进先出页面替换算法总是淘汰最先调入主存的页面,淘汰主存中驻留时间最长的页面。了解到最近最少使用页面替换算法淘汰的页面实在最近一段时间最久未被访问的那一页