LRU页面调度算法实现

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

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

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

4、和 for 循环语句进行编程。If 语句基本格式为：If （表达式）语句 1else感谢下载载精品语句 2Switch 语句基本格式为：Switch ( 表达式 )case常量表达式 1；语句序列 1case常量表达式 2；语句序列 2三、主要功能模块流程图（ 1）主菜单流程图 :Init ；I=0I <blockYPrintf( “%d” ,Fuzhui;)I +NPrintf( “ n” )(2)main 函数流程图：感谢下载载开始进入主菜单是否输入为“ 1”精品是否输入为是否输入为是否输入为NNN“2”“3”“4”YYYY自定义块数和显示进程数和进入 LRU 算法退出进程数块数N结

5、束(3)LRU 程序流程图：感谢下载载精品开始页数是否已满？NY该页是否在物找到最久的页面，N退出 LRU 算法理块中更新时间，置换Y更新时间结束（ 4）自定义函数流程图：Init ；I=0I <pageNumYPagesi=rand()%100;I +NGetchar90;四、系统测试感谢下载载精品（ 1）显示主菜单：（ 2）选择 1：（ 3）选择 3：感谢下载载精品（ 4）选择 1：（ 4）输入要修改块的：感谢下载载精品五、结论通过这两周的课设，我不仅复习了C 语言的相关知识，还对操作系统有了进一步的理解和掌握。实验中，通过LRU（最近最久未使用）算法实现了页面调度模拟实验。 LRU

6、 与其他几种调度算法在原理上既有区别又有联系。要想充分掌握 LRU 算法，也要会使用其他几种算法。虽然在程序设计中， 出现了一些错误， 但是经过同学的帮助和辅导老师的细心指导，我已经将错误纠正了。 使程序达到预想的结果， 能够实现简单的页面调度。通过此次实验， 我发现自己在编程方面还有许多不足的地方，以后要多加动手编写，提高自己的编程能力。最后感谢同学的帮助和辅导老师的悉心指导，使我顺利完成此次实验。六、源程序#include <stdio.h>#include <stdlib.h>感谢下载载精品#include <time.h>#define Maxsiz

7、e 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_sel

8、ect()感谢下载载精品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");p

9、rintf("*3.LRU 算法*n");printf("*4.EXIT*n");感谢下载载精品printf("*n");printf("*n");doprintf("n输入你的选择(14):");scanf("%d",&n);while(n<1|n>4);return(n);void Zidingyi()int i;system("cls");printf("*n");printf("页式储存管理-LRU

10、 算法n");printf("*n");printf("-自定义进程数和块数-n");printf("请输入进程数：");scanf("%d",&pageNum);getchar();printf("请输入块数：");scanf("%d",&physicalblock );感谢下载载精品getchar();printf("请依次输入页号引用串(中间用空格隔开):");for(i = 0 ; i < pageNum ; i+)

11、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; /该页在内存中Ti

12、me j = i;/更新时间感谢下载载精品break;if(key = 0)/若该页不在内存中ReplacePages+;/ 缺页次数加1int min = Time0;int flag = 0;for(j = 1 ; j < physicalblock ; j+)if(min > Timej)min = Timej;/ 找到最久的页面flag = j;Timeflag = i;/记录时间Fuzhuflag = pagesi;ShowResult();printf("页面总数为：%dn",pageNum);感谢下载载精品printf("置换次数为： %

13、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&q

14、uot;,re2);printf("*n");printf("-按 1 修改块数，按2 返回主菜单 -n");printf("n");printf("Yes-1 ，No-2n");int la;scanf("%d",&la);if(la=1)Xiugaikuaishu();elseprintf("*n");printf("-n");system("cls");感谢下载载精品void ShowResult()/显示每次换页后的结果

15、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 ShowCu

16、stomer()/显示用户自定义的进程数和块数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 ; i < Fz ; i