LRU页面调度算法实现

1、-/LRU页调度算法实现计算机科学与技术业计算机科学与技术指导教师姓名2014年3月15日、设计目的、内容与要求为学生提供了一个既动手 独立分析和解决实际问题（一）目的： 操作系统课程设计是计算机专业重要的教学环节， 又动脑，将课本上的理论知识和实际有机的结合起来， 的机会。进一步巩固和复习操作系统的基础知识。 培养学生结构化程序、模块化程序设计的方法和能力。 提高学生调试程序的技巧和软件设计的能力。 提高学生分析问题、解决问题以及综合利用 C 语言进行程序设计的能力。 内容：（1）（2）（3）（4）程序应模拟实现LRU算法思想，对n个页面实现模拟调度。（三）要求：2.3.1. 不同的功能使用

2、不同的函数实现 （模块化），对每个函数的功能和调用接口要 注释清楚。对程序其它部分也进行必要的注释。 对系统进行功能模块分析、画出总流程图和各模块流程图。 用户界面要求方便、简洁明了、美丽大方、格式统一。所有功能可以反复使 用，最好使用菜单。4.通过命令相应选项能直接进入某个相应菜单选项的功能模块。 所有程序需调试通过。二、算法的基本思想LRU是Least Recently Used 近期最少使用算法。内存管理的一种页面置换算法，对于在内存中但又不用的数据块（内存块） 叫做LRU Oracle会根据哪些数据属于LRU而将其移出内存而腾出空间来加载另 外的数据。什么是LRU算法？ LRU是Lea

3、st Recently Used 的缩写，即最少使用页面 置换算法，是为虚拟页式存储管理服务的。 关于操作系统的内存管理， 如何节省 利用容量不大的内存为最多的进程提供资源， 一直是研究的重要方向。 而内存的 虚拟存储管理，是现在最通用，最成功的方式 在内存有限的情况下，扩展 一部分外存作为虚拟内存， 真正的内存只存储当前运行时所用得到信息。 这无疑 极大地扩充了内存的功能，极大地提高了计算机的并发度。虚拟页式存储管理， 则是将进程所需空间划分为多个页面， 内存中只存放当前所需页面， 其余页面放 入外存的管理方式。程序中用到了 if, switch选择语句，和for循环语句进行编程。If 语句

4、基本格式为：If （表达式）语句 1else语句 2Switch语句基本格式为:Switch （表达式）case常量表达式1;语句序列1case常量表达式2；语句序列2三、主要功能模块流程图(1)主菜单流程图：(2) main函数流程图:进入主菜单是否输入为-N2T自定义块数和 进程数显示进程数和 块数进入LRU算法退岀TYTYT(3)LRU程序流程图:N找到最久的页面, 更新时间，置换C开始 J开始丿gr页数是否已 kt 满？ 丿更新时间(4)自定义函数流程图:四、系统测试(1)显示主菜单:HKMHMH 欢迎逬入主券面请亲页去壽储管理申JRU算法的实现n餐*W»1-23- 札自定义

5、进程数和块数显示用户自定义LRU算拄EMIT»W-*»#-197 I fII IZ J YI 1 I I 'P I r |_ I I _ _J_ 卜 L _r_I L_l II |m tj it _冃 I请求贡式存储t理中LRU算法的实现i.血3.4.自定义进程数和块数显示用£自定义MfiU算法EXIT4tMHr(2)选择1:MMKKMICMHttMtlMMKMMttM 口MM ICMH ttM KKM 江贰口 ttM KHM KMgWa MM KM口口页式诸存管理-LRU算法自定义进程数和块数请樣次输入页号引用串.狞问用空格隔开江2 3 4 5 2输人你

6、的选择"24：(3) 选择3:laa输入你的选译心小3949为为；：为为；數数为対数数为22255552 次总111444E & 面拱10 页按丄修改块数，按2返回主菜单Ves一一1. No一一2(4) 选择1:音输入霄曼慘改块的数巨:(4)输入要修改块的:五、结论通过这两周的课设，我不仅复习了 C语言的相关知识，还对操作系统有了进 一步的理解和掌握。实验中，通过 LRU（最近最久未使用）算法实现了页面调度 模拟实验。LRU与其他几种调度算法在原理上既有区别又有联系。要想充分掌握 LRU算法，也要会使用其他几种算法。虽然在程序设计中，出现了一些错误，但是经过同学的帮助和辅导老

7、师的细 心指导，我已经将错误纠正了。使程序达到预想的结果，能够实现简单的页面调 度。通过此次实验，我发现自己在编程方面还有许多不足的地方，以后要多加动手编写，提高自己的编程能力。最后感谢同学的帮助和辅导老师的悉心指导，使我顺利完成此次实验。六、源程序#i nclude <stdio.h>#i nclude <stdlib.h>#in elude <time.h>#defi ne Maxsize 50void XiugaikuaishuO;void In itio n();void Zidi ngyi();void ShowCustomer();void Sh

8、owResult();void ShowNot();void LRU();int me nu_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();br

9、eak;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"

10、);printf("*n");doprintf("n 输入你的选择 (14):"); scanf("%d",&n);while(n<1|n>4);return(n);void Zidingyi()int i;n");system("cls"); printf("*n"); printf(" 页式储存管理 -LRU 算法 printf("*n"); printf(" 自定义进程数和块数 n");printf("

11、; 请输入进程数： ");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;/记录置换

12、次数 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

13、 = Time0;int flag = 0;for(j = 1 ; j < physicalblock ; j+) if(min > Timej)min = Timej;/ 找到最久的页面 flag = j; Timeflag = i;/ 记录时间 Fuzhuflag = pagesi; ShowResult();%.2lfn",re1);%.2lfn",1-re1);%d n",ReplacePages+physicalblock); printf(" 页面总数为： %dn",pageNum); printf(" 置换次

14、数为： %dn",ReplacePages); double re1 = (double)ReplacePages)/(double)pageNum); printf(" 置换率为： printf(" 命中率为： printf(" 缺页次数为：double re2 = (double)(ReplacePages+physicalblock)/(double)pageNum); printf(" 缺页率为： %.2lfn",re2); printf("*n"); printf(" 按 1修改块数，按 2 返

15、回主菜单printf(" printf(" int la; scanf("%d",&la); if(la=1) Yes-1，No-2n");n");n");Xiugaikuaishu(); elseprintf("*n");printf("n");system("cls");void ShowResult()/ 显示每次换页后的结果int i;for(i = 0 ; i < physicalblock ; i+)printf(" %d&quo

16、t;,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(&qu

17、ot;*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 = physicalblo