LRU页面调度算法实现学院计算机科学与技术专业计算机科学与技术学号学生姓名指导教师姓名2014年3月16 日目录1.实验要求 (2)2.实验目的 (2)3.实验内容 (2)4.相关知识 (2)5.实验原理 (3)6.流程图 (4)7.源代码 (5)8.运行结果 (9)9.实验心得 (10)10.参考文献 (11)LRU页调度算法实现一实验要求：1．不同的功能使用不同的函数实现（模块化），对每个函数的功能和调用接口要注释清楚。
对程序其它部分也进行必要的注释。
2．对系统进行功能模块分析、画出总流程图和各模块流程图。
3．用户界面要求使用方便、简洁明了、美观大方、格式统一。
所有功能可以反复使用，最好使用菜单。
4．通过命令行相应选项能直接进入某个相应菜单选项的功能模块。
5．所有程序需调试通过。
二实验目的：将课本上的理论知识和实际有机的结合起来，独立分析和解决实际问题的机会。
进一步巩固和复习操作系统的基础知识。
培养学生结构化程序、模块化程序设计的方法和能力。
提高学生调试程序的技巧和软件设计的能力。
提高学生分析问题、解决问题以及综合利用C 语言进行程序设计的能力。
三实验内容：程序应模拟实现LRU 算法思想，对n个页面实现模拟调度。
四相关知识：1．虚拟存储器的引入：局部性原理：程序在执行时在一较短时间内仅限于某个部分；相应的，它所访问的存储空间也局限于某个区域，它主要表现在以下两个方面：时间局限性和空间局限性。
2．虚拟存储器的定义：虚拟存储器是只具有请求调入功能和置换功能，能从逻辑上对内存容量进行扩充的一种存储器系统。
3．虚拟存储器的实现方式：分页请求系统，它是在分页系统的基础上，增加了请求调页功能、页面置换功能所形成的页面形式虚拟存储系统。
请求分段系统，它是在分段系统的基础上，增加了请求调段及分段置换功能后，所形成的段式虚拟存储系统。
五．实验原理：目前有许多页面调度算法，本实验主要涉及最近最久未使用调度算法。
本实验使用页面调度算法时作如下假设，进程在创建时由操作系统为之分配一个固定数目物理页，执行过程中物理页的数目和位置不会改变。
也即进程进行页面调度时只能在分到的几个物理页中进行。
LRU基本思想：LRU是Least Recently Used的缩写，即最近最少使用页面置换算法，是为虚拟页式存储管理服务的。
关于操作系统的内存管理，如何节省利用容量不大的内存为最多的进程提供资源，一直是研究的重要方向。
而内存的虚拟存储管理，是现在最通用，最成功的方式——在内存有限的情况下，扩展一部分外存作为虚拟内存，真正的内存只存储当前运行时所用得到信息。
这无疑极大地扩充了内存的功能，极大地提高了计算机的并发度。
虚拟页式存储管理，则是将进程所需空间划分为多个页面，内存中只存放当前所需页面，其余页面放入外存的管理方式。
LRU算法的提出，是基于这样一个事实：在前面几条指令中使用频繁的页面很可能在后面的几条指令中频繁使用。
反过来说，已经很久没有使用的页面很可能在未来较长的一段时间内不会被用到。
这个，就是著名的局部性原理——比内存速度还要快的cache，也是基于同样的原理运行的。
因此，我们只需要在每次调换时，找到最近最少使用的那个页面调出内存。
这就是LRU算法的全部内容。
实验中是用一维数组page[pSIZE]存储页面号序列，memery[mSIZE]是存储装入物理块中的页面。
数组flag[10]标记页面的访问时间。
每当使用页面时，刷新访问时间。
发生缺页时，就从物理块中页面标记最小的一页，调出该页，换入所缺的页面。
六流程图：图1 实验流程图七源代码#include <stdio.h>#include <stdlib.h>int mSIZE; /*物理块数*/int pSIZE; /*页面号引用串个数*/int memory[10]={-1,-1,-1,-1,-1,-1,-1,-1,-1,-1}; /*物理块中的页号*/ int page[100]={0}; /*页面号引用串*/int temp[100][10];void Delay();void LRU();void design();void display(int m);void main(){int i,j,code;design();printf(" 请按任意键进行初始化操作... \n");printf("┗━━━━━━━━━━━━━━━━━━━━━━━\n"); printf(" >>>");getchar();system("cls");printf("请输入物理块的个数(M<=10)：");scanf("%d",&mSIZE);printf("请输入页面号引用串的个数(P<=100)：");scanf("%d",&pSIZE);puts("请依次输入页面号引用串：");for(i=0;i<pSIZE;i++)scanf("%1d",&page[i]);for(i=0;i<100;i++)for(j=0;j<10;j++)temp[i][j]=-1;system("cls");do{printf("* * * * * * * * * * * * * * * * * * * * **\n");printf("* 请选择页面调度算法：\t\t\t *\n");printf("* --------------------------------------- \n");printf("* 1.最近最久未使用(LRU) *\n");printf("* 0.退出 *\n");printf("* * * * * * * * * * * * * * * * * * * * * *\n");printf("请选择操作：[ ]\b\b");scanf("%d",&code);switch(code){case 1:LRU();system("pause");system("cls");break;case 0:printf("┃谢谢使用! ┃\n");printf("┗━━━━━━━━━━━━━━━━┛\n");exit(0);default:printf("输入错误，请重新输入：");}printf("按任意键重新选择置换算法：>>>");getchar();system("cls");}while (code!=2);getchar();}void design(){printf("┏━━━━━━━━━━━━━━━━━━━━━━━┓\n");printf("┃页面调度算法┃\n"); printf("┃班级:11非师┃ \n");printf("┃学号:20111202005 ┃\n");printf("┣━━━━━━━━━━━━━━━━━━━━━━━┫\n");}void display(int m){int i,j,k;for(k=0;k<pSIZE;k++){printf("%d ",page[k]);}printf("\n");for(j=0;j<mSIZE;j++){for(i=0;i<pSIZE;i++){if(temp[i][j]==-1)printf(" ");elseprintf("|%d| ",temp[i][j]);}printf("\n");}printf("----------------------------------------\n");printf("缺页次数：%d\t\t",m+mSIZE);printf("缺页率：%d%%\n",(m+mSIZE)*100/pSIZE);printf("访问次数：%d\t\t",pSIZE-(m+mSIZE));printf("访问命中率：%d%%\n",(pSIZE-(m+mSIZE))*100/pSIZE);printf("----------------------------------------\n");}/*最近最久未使用置换算法*/void LRU(){int memory[10]={-1,-1,-1,-1,-1,-1,-1,-1,-1,-1};int flag[10]={0}; /*记录进入物理块的时间*/int i,j,m;int max=0; /*记录换出页*/int count=0; /*记录置换次数*/int t=1; //用来记录已经存入数的物理块数；memory[0]=page[0];temp[0][0]=page[0];for(i=1;i<pSIZE;i++){for(j=0;j<mSIZE;j++){if(page[i]==memory[j]){flag[j]=i;break;}}if(page[i]==memory[j])continue;if(page[i]!=memory[j])//不在物理块中{if(t<mSIZE){for(int k=0;k<mSIZE;k++){if(memory[k]==-1){memory[k]=page[i];flag[k]=i;t++;break;}}for(j=0;j<mSIZE;j++)temp[i][j]=memory[j];}if(t==mSIZE){t++;continue;}if(t>=mSIZE) //物理块中已满{count++;max=flag[0]<flag[1]?0:1;for(m=2;m<mSIZE;m++)if(flag[m]<flag[max])max=m;memory[max]=page[i];flag[max]=i; //记录该页进入物理块的时间 for(j=0;j<mSIZE;j++)temp[i][j]=memory[j];}}}display(count);}八运行结果运行环境——Visual C++ 6.01.进入界面2.算法演示结果：3．退出程序：九实验心得通过此次的实验，我更加了解了全局替换策略，了解到先进先出页面替换算法总是淘汰最先调入主存的页面，淘汰主存中驻留时间最长的页面。