LRU页面调度算法实现

1、LRU页面调度算法实现学院计算机科学与技术专业计算机科学与技术学号学生姓名指导教师2014年 3月 16 日目录1.22.23.24.25.36.47.58.99.1010.11LRU页调度算法实现一 实验要求：1不同的功能使用不同的函数实现（模块化），对每个函数的功能和调用接口要注释清楚。对程序其它部分也进行必要的注释。2对系统进行功能模块分析、画出总流程图和各模块流程图。3用户界面要求使用方便、简洁明了、美观大方、格式统一。所有功能可以反复使用，最好使用菜单。4通过命令行相应选项能直接进入某个相应菜单选项的功能模块。5所有程序需调试通过。二 实验目的：将课本上的理论知识和实际有机的结合起来

2、，独立分析和解决实际问题的机会。 进一步巩固和复习操作系统的基础知识。培养学生结构化程序、模块化程序设计的方法和能力。 提高学生调试程序的技巧和软件设计的能力。 提高学生分析问题、解决问题以及综合利用 C 语言进行程序设计的能力。三 实验容：程序应模拟实现 LRU 算法思想，对 n 个页面实现模拟调度。四 相关知识：1虚拟存储器的引入：局部性原理：程序在执行时在一较短时间仅限于某个部分；相应的，它所访问的存储空间也局限于某个区域，它主要表现在以下两个方面：时间局限性和空间局限性。2虚拟存储器的定义：虚拟存储器是只具有请求调入功能和置换功能，能从逻辑上对存容量进行扩充的一种存储器系统。3虚拟存储

3、器的实现方式：分页请求系统，它是在分页系统的基础上，增加了请求调页功能、页面置换功能所形成的页面形式虚拟存储系统。请求分段系统，它是在分段系统的基础上， 增加了请求调段及分段置换功能后，所形成的段式虚拟存储系统。五实验原理：目前有许多页面调度算法， 本实验主要涉及最近最久未使用调度算法。 本实验使用页面调度算法时作如下假设， 进程在创建时由操作系统为之分配一个固定数目物理页， 执行过程中物理页的数目和位置不会改变。 也即进程进行页面调度时只能在分到的几个物理页中进行。LRU基本思想：LRU 是 Least Recently Used 的缩写，即最近最少使用页面置换算法，是为虚拟页式存储管理服务

4、的。关于操作系统的存管理，如何节省利用容量不大的存为最多的进程提供资源，一直是研究的重要方向。而存的虚拟存储管理，是现在最通用，最成功的方式在存有限的情况下， 扩展一部分外存作为虚拟存， 真正的存只存储当前运行时所用得到信息。这无疑极扩充了存的功能， 极提高了计算机的并发度。 虚拟页式存储管理，则是将进程所需空间划分为多个页面， 存中只存放当前所需页面，其余页面放入外存的管理方式。LRU算法的提出，是基于这样一个事实：在前面几条指令中使用频繁的页面很可能在后面的几条指令中频繁使用。 反过来说，已经很久没有使用的页面很可能在未来较长的一段时间不会被用到。 这个，就是著名的局部性原理比存速度还要快

5、的 cache，也是基于同样的原理运行的。因此，我们只需要在每次调换时，找到最近最少使用的那个页面调出存。这就是 LRU算法的全部容。实验中是用一维数组 pagepSIZE 存储页面号序列， memerymSIZE是存储装入物理块中的页面。数组 flag10 标记页面的访问时间。每当使用页面时，刷新访问时间。发生缺页时，就从物理块中页面标记最小的一页，调出该页，换入所缺的页面。六 流程图：如下页所示开始载入页号序列，从第0 个得到页号将页号放入物理块中，编号加1引用串编号大于物理块数 ?页号在物理块中 ?根据选择的置换算法完成置换页号序列载完 ?结束图 1 实验流程图七 源代码#include

6、 <stdio.h>#include <stdlib.h>int mSIZE; /*物理块数 */int pSIZE; /*页面号引用串个数 */int memory10=-1,-1,-1,-1,-1,-1,-1,-1,-1,-1; /*int page100=0; /*页面号引用串 */int temp10010;物理块中的页号*/void Delay();void LRU();void design();void display(int m);void main()int i,j,code;design();printf("请按任意键进行初始化操作.n&q

7、uot;);printf(" n"); printf(" >>>");getchar();system("cls");printf("请输入物理块的个数 (M<=10)： ");scanf("%d",&mSIZE);printf(" 请输入页面号引用串的个数 (P<=100) ："); scanf("%d",&pSIZE);puts(" 请依次输入页面号引用串：");for(i=0;i<

8、;pSIZE;i+)scanf("%1d",&pagei);for(i=0;i<100;i+)for(j=0;j<10;j+)tempij=-1;system("cls");doprintf("* * * * * * * * * * * * * * * * * * * * *n");printf("*请选择页面调度算法： tttprintf("* - n");*n");printf("* 1.最近最久未使用 (LRU) *n");printf("

9、* 0.退出*n");printf("* * * * * * * * * * * * * * * * * * * * * *n");printf("请选择操作： bb");scanf("%d",&code);switch(code)case 1:LRU();system("pause");system("cls");break;case 0:printf("使用 !n");printf("n");exit(0);default:print

10、f("输入错误，请重新输入：");printf("按任意键重新选择置换算法：>>>");getchar();system("cls");while (code!=2);getchar();void design()printf("printf("printf("printf("页面调度算法班级 :11 非师学号 :n");n"); n"); n");printf("n");void display(int m)int

11、i,j,k;for(k=0;k<pSIZE;k+)printf("%d",pagek);printf("n");for(j=0;j<mSIZE;j+)for(i=0;i<pSIZE;i+)if(tempij=-1)printf("");elseprintf("|%d| ",tempij);printf("n");printf("-n");printf("缺页次数： %dtt",m+mSIZE);printf("缺页率： %d%n

12、",(m+mSIZE)*100/pSIZE);printf("访问次数： %dtt",pSIZE-(m+mSIZE);printf("访问命中率： %d%n",(pSIZE-(m+mSIZE)*100/pSIZE);printf("-n");/* 最近最久未使用置换算法*/void LRU()int memory10=-1,-1,-1,-1,-1,-1,-1,-1,-1,-1;int flag10=0; /*记录进入物理块的时间 */int i,j,m;int max=0; /*记录换出页 */int count=0; /*

13、记录置换次数 */int t=1;/用来记录已经存入数的物理块数；memory0=page0;temp00=page0;for(i=1;i<pSIZE;i+)for(j=0;j<mSIZE;j+)if(pagei=memoryj)flagj=i;break;if(pagei=memoryj)continue;if(pagei!=memoryj)/不在物理块中if(t<mSIZE)for(int k=0;k<mSIZE;k+)if(memoryk=-1)memoryk=pagei;flagk=i;t+;break;for(j=0;j<mSIZE;j+)tempij=

14、memoryj;if(t=mSIZE)t+;continue;if(t>=mSIZE) /物理块中已满count+;max=flag0<flag1?0:1;for(m=2;m<mSIZE;m+)if(flagm<flagmax)max=m;memorymax=pagei;flagmax=i; / 记录该页进入物理块的时间 for(j=0;j<mSIZE;j+)tempij=memoryj;display(count);八 运行结果运行环境 Visual C+ 6.01. 进入界面2. 算法演示结果：3退出程序：九 实验心得通过此次的实验，我更加了解了全局替换策略，了解到先进先出页面替换算法总是淘汰最先调入主存的页面，淘汰主存中驻留时间最长的页面。了解到最近最少使用页面替换算法淘汰的页面实在最近一段时间最久未被访问的那一页。在整体上加深了我对虚拟存储管理的理解，构建了一个系统的存储管理体系。当然在实验过程中，我也遇到了一