LRU页面调度算法实现

LRU页调度算法实现学 院 计算机科学与技术 专 业 计算机科学与技术 学 号 学 生 姓 名 指导教师姓名 2014年3月15日一、设计目的、内容与要求（一）目的： 操作系统课程设计是计算机专业重要的教学环节，为学生提供了一个既动手又动脑，将课本上的理论知识和实际有机的结合起来，独立分析和解决实际问题的机会。（1）进一步巩固和复习操作系统的基础知识。（2）培养学生结构化程序、模块化程序设计的方法和能力。（3）提高学生调试程序的技巧和软件设计的能力。（4）提高学生分析问题、解决问题以及综合利用C语言进行程序设计的能力。（二）内容： 程序应模拟实现LRU算法思想，对n个页面实现模拟调度。（三）要求：1. 不同的功能使用不同的函数实现（模块化），对每个函数的功能和调用接口要注释清楚。对程序其它部分也进行必要的注释。2. 对系统进行功能模块分析、画出总流程图和各模块流程图。3. 用户界面要求方便、简洁明了、美丽大方、格式统一。所有功能可以反复使用，最好使用菜单。4. 通过命令相应选项能直接进入某个相应菜单选项的功能模块。所有程序需调试通过。2、 算法的基本思想 LRU是Least Recently Used 近期最少使用算法。 内存管理的一种页面置换算法，对于在内存中但又不用的数据块（内存块）叫做LRU，Oracle会根据哪些数据属于LRU而将其移出内存而腾出空间来加载另外的数据。什么是LRU算法？ LRU是Least Recently Used的缩写，即最少使用页面置换算法，是为虚拟页式存储管理服务的。关于操作系统的内存管理，如何节省利用容量不大的内存为最多的进程提供资源，一直是研究的重要方向。而内存的虚拟存储管理，是现在最通用，最成功的方式 在内存有限的情况下，扩展一部分外存作为虚拟内存，真正的内存只存储当前运行时所用得到信息。这无疑极大地扩充了内存的功能，极大地提高了计算机的并发度。虚拟页式存储管理，则是将进程所需空间划分为多个页面，内存中只存放当前所需页面，其余页面放入外存的管理方式。程序中用到了if，switch选择语句，和for循环语句进行编程。If语句基本格式为：If （表达式）语句1else语句2Switch语句基本格式为：Switch (表达式)case 常量表达式1；语句序列1case 常量表达式2；语句序列2 三、主要功能模块流程图（1）主菜单流程图:(2)main函数流程图：(3)LRU程序流程图：（4）自定义函数流程图：四、系统测试（1）显示主菜单：（2）选择1：（3）选择3：（4）选择1：（4）输入要修改块的：五、结论 通过这两周的课设，我不仅复习了C语言的相关知识，还对操作系统有了进一步的理解和掌握。实验中，通过LRU（最近最久未使用）算法实现了页面调度模拟实验。LRU与其他几种调度算法在原理上既有区别又有联系。要想充分掌握LRU算法，也要会使用其他几种算法。虽然在程序设计中，出现了一些错误，但是经过同学的帮助和辅导老师的细心指导，我已经将错误纠正了。使程序达到预想的结果，能够实现简单的页面调度。通过此次实验，我发现自己在编程方面还有许多不足的地方，以后要多加动手编写，提高自己的编程能力。最后感谢同学的帮助和辅导老师的悉心指导，使我顺利完成此次实验。六、源程序#include #include #include #define Maxsize 50void Xiugaikuaishu();void Inition(); void Zidingyi(); void ShowCustomer(); void ShowResult(); void ShowNot();void LRU();int menu_select(); /菜单函数int pageNum = 0; int pagesMaxsize;/存储页号int FuzhuMaxsize;/辅助数组int TimeMaxsize;/记录页在内存中的时间int physicalblock;/记录物理块数int Fz;/辅助变量int main()for(;) switch(menu_select() case 1: Zidingyi(); break; case 2: ShowCustomer(); break; case 3: LRU(); break; case 4: exit(0); return 0;int menu_select() int n; printf(*欢迎进入主界面*n);printf(* 请求页式存储管理中LRU算法的实现 *n);printf(* *n);printf(* 1.自定义进程数和块数 *n);printf(* 2.显示用户自定义 *n);printf(* 3.LRU算法 *n); printf(* 4.EXIT *n);printf(* *n);printf(*n);doprintf(n输入你的选择(14):); scanf(%d,&n); while(n4); return(n); void Zidingyi() int i;system(cls);printf(*n);printf( 页式储存管理-LRU算法 n);printf(*n);printf(-自定义进程数和块数-n);printf(请输入进程数：);scanf(%d,&pageNum);getchar();printf(请输入块数：);scanf(%d,&physicalblock ); getchar();printf(请依次输入页号引用串(中间用空格隔开):);for(i = 0 ; i pageNum ; i+)scanf(%d,&pagesi);void LRU()int i,j;int ReplacePages = 0;/记录置换次数printf(*n);printf(-LRU算法结果显示-n);printf(n);ShowNot();for(i = Fz ; i pageNum; i+)int key = 0;for(j = 0 ; j physicalblock ; j+)/判断该页是否在物理块中if(Fuzhuj = pagesi) key = 1; /该页在内存中Timej = i;/更新时间break;if(key = 0)/若该页不在内存中ReplacePages+; /缺页次数加1int min = Time0;int flag = 0;for(j = 1 ; j Timej)min = Timej;/找到最久的页面flag = j;Timeflag = i;/记录时间Fuzhuflag = pagesi;ShowResult();printf(页面总数为：%dn,pageNum); printf(置换次数为：%dn,ReplacePages);double re1 = (double)ReplacePages)/(double)pageNum);printf(置换率为： %.2lfn,re1);printf(命中率为： %.2lfn,1-re1);printf(缺页次数为：%d n,ReplacePages+physicalblock);double re2 = (double)(ReplacePages+physicalblock)/(double)pageNum);printf(缺页率为： %.2lfn,re2);printf(*n);printf(-按1修改块数，按2返回主菜单-n); printf( n); printf( Yes-1，No-2 n);int la;scanf(%d,&la);if(la=1)Xiugaikuaishu(); elseprintf(*n);printf(-n);system(cls); void ShowResult()/显示每次换页后的结果int i;for(i = 0 ; i physicalblock ; i+)printf( %d,Fuzhui);printf(n);void Xiugaikuaishu()system(cls);printf(*n);printf(-请输入需要修改块的数目-n);int a;scanf(%d,&a);physicalblock = a;ShowCustomer();/显示自定义页面信息LRU();void ShowCustomer()/显示用户自定义的进程数和块数 system(cls);int i;printf(*n);printf(-显示-n);printf(进程数为: %dn,pageNum);printf(页号分别为: );for(i = 0 ; i pageNum ; i+)printf(%d ,pagesi);printf(n);printf(可用物理块数为: %dn,physicalblock);printf(*n);printf(-按任意键可返回主菜单-n);getchar();void ShowNot()/显示一定不用换页的部分Fz = physicalblock;int i,j,k=0,key = 0;for(i = 0 ;