搜索
操作系统课程设计LRU页面调度算法学号：姓名：学院：专业：班级：指导老师：日期：目录一、实验题目...........................................................................1二、课程设计的目的...............................................................1三、设计内容...........................................................................1四、设计要求...........................................................................1五、设计思想...........................................................................1六、主要数据结构及其说明...................................................2七、硬件支持...........................................................................3八、源程序文件.......................................................................3九、程序运行结果...................................................................7十、实验体会...........................................................................81一实验题目LRU页面调度算法二课程设计的目的操作系统课程设计是计算机专业重要的教学环节，它为学生提供了一个既动手又动脑，将课本上的理论知识和实际有机的结合一起，独立分析和解决实际问题的机会。1.进一步巩固和复习操作系统的基础知识。2.培养学生结构化程序、模块化程序设计的方法和能力。3.提高学生调试程序的技巧和软件设计的能力。4.提高学生分析问题、解决问题以及综合利用C语言进行程序设计的能力。三设计内容程序应模拟实现LRU算法思想，对n个页面实现模拟调度。四设计要求1．不同的功能使用不同的函数实现（模块化），对每个函数的功能和调用接口要注释清楚。对程序其它部分也进行必要的注释。2．对系统进行功能模块分析、画出总流程图和各模块流程图。3．用户界面要求使用方便、简洁明了、美观大方、格式统一。所有功能可以反复使用，最好使用菜单。4．通过命令行相应选项能直接进入某个相应菜单选项的功能模块。5．所有程序需调试通过。五设计思想最近最久未使用（LRU）页调度算法是选择最近最久未使用的页面予以淘汰。算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间，当所要访问的页面在内存块中时，就不淘汰页面，否则，淘汰页面中时间最长的，即淘汰最近最久未使用的页面。2yn算法流程图六主要数据结构及其说明程序执行是稳定的，高效的。在LRU算法中，要找出最近最久未使用的页面的话，就必须设置有关的访问记录项，且每一次访问这些记录项，叶面都必须更新这些记录项。这个记录项在此程序中为：typedefstructpage{开始输入页面号Init(b,c)Lru(a[i],b)输出queue[i]缺页次数和缺页率是否继续?结束3intnum;/*记录页面号*/inttime;/*记录调入内存时间*/}Page;//页面逻辑结构，结构为方便算法实现设计如此，显然要花费较大的系统开销（包括时间和空间上的），这也是实际系统中不采用LRU算法的直接原因，但由于其页面置换的优越性，实际系统中常使用LRU的近似算法。七硬件支持为了了解一个进程在内存中的各个页面各有多少时间未被进程访问，以及如何快速的知道哪一页是最近最久未使用的页面，须有两类硬件之一的支持：寄存器或栈。寄存器：为了记录某进程在内存中各页的使用情况，须为每个在内存中的页面配置一个移位寄存器。栈：可利用一个特殊的栈来保存当前使用的各个页面的页面号。每当进程访问某页面时，便将该页面的页面号从战中移出，将它压入栈顶。因此，栈顶始终是最新被访问页面的编号，而栈底则是最近最久未使用页面的页面号。八源程序文件#includestdio.h#includeconio.h#includestdlib.h#defineM3//物理块数#defineN10//页面数#defineMyprintf1printf(\t************************\t\t\n\n);//表格控制#defineMyprintf2printf(******************************\n\n);//表格控制typedefstructpage{intnum;/*记录页面号*/inttime;/*记录调入内存时间*/4}Page;//页面逻辑结构，结构为方便算法实现设计Pageb[M];//内存单元数intc[M][N];//暂保存内存当前的状态：缓冲区intqueue[100];//记录调入队列intK;//调入队列计数变量//初始化内存单元、缓冲区voidInit(Page*b,intc[M][N]){inti,j;for(i=0;iN;i++){b[i].num=-1;b[i].time=N-i-1;}for(i=0;iM;i++)for(j=0;jN;j++)c[i][j]=-1;}//取得在内存中停留最久的页面，默认状态下为最早调入的页面intGetMax(Page*b){inti;intmax=-1;inttag=0;for(i=0;iM;i++){if(b[i].timemax){max=b[i].time;tag=i;5}}returntag;}//判断页面是否已在内存中intEquation(intfold,Page*b){inti;for(i=0;iM;i++){if(fold==b[i].num)returni;}return-1;}//LRU核心部分voidLru(intfold,Page*b){inti;intval;val=Equation(fold,b);if(val=0){b[val].time=0;for(i=0;iM;i++)if(i!=val)b[i].time++;}else{queue[++K]=fold;//记录调入页面val=GetMax(b);b[val].num=fold;b[val].time=0;for(i=0;iM;i++)if(i!=val)b[i].time++;6}}//主程序voidmain(){start:K=-1;inti,j;inta[N];Myprintf1;printf(\n\t\t\t欢迎使用LRU页面调度算法\n\n);Myprintf1;printf(请输入所要访问的各个页面号：\n);for(i=0;iN;i++)scanf(%d,&a[i]);Init(b,c);//调用for(i=0;iN;i++){Lru(a[i],b);c[0][i]=a[i];//记录当前的内存单元中的页面for(j=0;jM;j++)c[j][i]=b[j].num;}//结果输出printf(内存状态为:\n);Myprintf2;for(j=0;jN;j++)printf(|%2d,a[j]);printf(|\n);Myprintf2;for(i=0;iM;i++)7{for(j=0;jN;j++){if(c[i][j]==-1)printf(|%2c,32);elseprintf(|%2d,c[i][j]);}printf(|\n);}Myprintf2;printf(\n调入队列为：);for(i=0;iK+1;i++)printf(%3d,queue[i]);printf(\n缺页次数为:%6d\n缺页率:%16.6f,K+1,(float)(K+1)/N);printf(\n是否继续!\ty?);chary;if(getch()=='y'){system(cls);printf(\n);gotostart;}elseprintf(\n);printf(程序结束\n);}九程序运行结果8十实验体会通过本次课程设计，对LRU页面调度算法有了更深入的理解和掌握，进一步的巩固和复习了操作系统中关于LRU页面调度算法的知识，进一步的了解了结构化、模块化程序设计的方法，提高了编写和调试程序的技巧，谢谢老师的细心指导。