操作系统课程设计(LRU算法)完整版内含代码

1、 操作系统课程设计 LRU页面调度算法 学 号： 姓 名： 学 院： 专 业： 班 级： 指导老师： 日 期： 目 录 一、实验题目1二、课程设计的目的1三、设计内容1四、设计要求1五、设计思想1六、主要数据结构及其说明2七、硬件支持3八、源程序文件3九、程序运行结果7十、实验体会8一 实验题目 LRU页面调度算法二 课程设计的目的 操作系统课程设计是计算机专业重要的教学环节，它为学生提供了一个既 动手又动脑，将课本上的理论知识和实际有机的结合一起，独立分析和解 决实际问题的机会。1.进一步巩固和复习操作系统的基础知识。2. 培养学生结构化程序、模块化程序设计的方法和能力。3.提高学生调试程序

2、的技巧和软件设计的能力。4.提高学生分析问题、解决问题以及综合利用C语言进行程序设计的能力。三 设计内容 程序应模拟实现LRU算法思想，对n个页面实现模拟调度。四 设计要求1不同的功能使用不同的函数实现（模块化），对每个函数的功能和调用接口要注释清楚。对程序其它部分也进行必要的注释。2对系统进行功能模块分析、画出总流程图和各模块流程图。3用户界面要求使用方便、简洁明了、美观大方、格式统一。所有功能可以反复使用，最好使用菜单。4通过命令行相应选项能直接进入某个相应菜单选项的功能模块。5所有程序需调试通过。五 设计思想最近最久未使用（LRU）页调度算法是选择最近最久未使用的页面予以淘汰。算法赋予每

3、个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间，当所要访问的页面在内存块中时，就不淘汰页面，否则，淘汰页面中时间最长的，即淘汰最近最久未使用的页面。 Lru(ai,b) Init(b,c) 输入页面号 开始输出queuei 缺页次数和缺页率是否继 续? y n 结束 算法流程图 六 主要数据结构及其说明程序执行是稳定的，高效的。在LRU算法中，要找出最近最久未使用的页面的话，就必须设置有关的访问记录项，且每一次访问这些记录项，叶面都必须更新这些记录项。这个记录项在此程序中为：typedef struct pageint num;/*记录页面号*/int time;/*记录调入

4、内存时间*/Page;/页面逻辑结构，结构为方便算法实现设计 如此，显然要花费较大的系统开销（包括时间和空间上的），这也是实际系统中不采用LRU算法的直接原因，但由于其页面置换的优越性，实际系统中常使用LRU的近似算法。七 硬件支持 为了了解一个进程在内存中的各个页面各有多少时间未被进程访问，以及如何快速的知道哪一页是最近最久未使用的页面，须有两类硬件之一的支持：寄存器或栈。寄存器：为了记录某进程在内存中各页的使用情况，须为每个在内存中的页面配置一个移位寄存器。栈：可利用一个特殊的栈来保存当前使用的各个页面的页面号。每当进程访问某页面时，便将该页面的页面号从战中移出，将它压入栈顶。因此，栈顶始

5、终是最新被访问页面的编号，而栈底则是最近最久未使用页面的页面号。八 源程序文件 #include<stdio.h> #include<conio.h> #include<stdlib.h> #define M 3 /物理块数 #define N 10 /页面数 #define Myprintf1 printf("t*ttnn");/表格控制 #define Myprintf2 printf("*nn");/表格控制 typedef struct page int num;/*记录页面号*/int time;/*记录调入

6、内存时间*/ Page;/页面逻辑结构，结构为方便算法实现设计Page bM;/内存单元数int cMN;/暂保存内存当前的状态：缓冲区int queue100;/记录调入队列int K;/调入队列计数变量/初始化内存单元、缓冲区void Init(Page *b,int cMN) int i,j; for(i=0;i<N;i+) bi.num=-1; bi.time=N-i-1; for(i=0;i<M;i+) for(j=0;j<N;j+) cij=-1;/取得在内存中停留最久的页面，默认状态下为最早调入的页面int GetMax(Page *b) int i; int

7、max=-1; int tag=0; for(i=0;i<M;i+) if(bi.time>max) max=bi.time; tag=i; return tag;/判断页面是否已在内存中int Equation(int fold,Page *b) int i; for(i=0;i<M;i+) if(fold=bi.num) return i; return -1;/LRU核心部分void Lru(int fold,Page *b) int i; int val; val=Equation(fold,b); if(val>=0) bval.time=0; for(i=0

8、;i<M;i+) if(i!=val) bi.time+; else queue+K=fold;/记录调入页面 val=GetMax(b); bval.num=fold; bval.time=0; for(i=0;i<M;i+) if(i!=val) bi.time+; /主程序void main() start:K=-1; int i,j; int aN; Myprintf1; printf("nttt欢迎使用LRU页面调度算法nn"); Myprintf1; printf("请输入所要访问的各个页面号：n"); for(i=0;i<

9、N;i+) scanf("%d",&ai);Init(b,c); /调用 for(i=0;i<N;i+) Lru(ai,b); c0i=ai; /记录当前的内存单元中的页面 for(j=0;j<M;j+) cji=bj.num; /结果输出printf("内存状态为:n");Myprintf2; for(j=0;j<N;j+) printf("|%2d",aj);printf("|n");Myprintf2; for(i=0;i<M;i+) for(j=0;j<N;j+) if

10、(cij=-1) printf("|%2c",32); else printf("|%2d",cij); printf("|n"); Myprintf2; printf("n调入队列为："); for(i=0;i<K+1;i+) printf("%3d",queuei); printf("n缺页次数为:%6dn缺页率:%16.6f",K+1,(float)(K+1)/N); printf("n是否继续!t y?"); char y; if(getch()='y') system("cls"); printf("n"); goto start; else printf(&qu