闽南师范大学操作系统课程设计内存LRU页面置换算法的设计

闽南师范大学操作系统课程设计内存LRU页面置换算法的设计姓名：学号：系别：计算机学院专业：网络工程专业年级：13网络2班指导教师：全秀祥、闫格2016年5月15日目录一、课程设计项目介绍.............................31.1项目介绍...................错误!未定义书签。1.2设计目的...................................3二、总体设计.....................................42.1总体结构..................................42.2原理框图..................................42.2设计原理..................................4三、详细设计.....................................53.1数据结构..................................53.2程序流程图................................53.2代码及注释................................6四、运行结果....................................144.1运行及测试结果............................144.2使用说明书...............................16五、课程设计小结与心得体会......................175.1课设小结.................................175.2心得体会.................................18一、课程设计项目介绍1.1项目介绍-内容：实现教材4.8节中所描述的LRU置换算法-要求：假设系统采用固定分配局部置换策略，某进程的总页面数为8（分别以数字0－7来代表）；运行时，输入分配给该进程的页块数（如：3）和一个20位长的页面访问序列（如：12560,36536,56042,70435），输出缺页次数和缺页率。置换图如下所示：序列12560365365604270435111666666666666777332220005555554440005555333333300222444缺页√√√√√√√√√√√√√√√则缺页次数和缺页率为：缺页次数：15缺页率：15/20=0.751.2设计目的通过对内存页面置换算法的设计，深入理解虚拟存储管理的原理。二、总体设计2.1总体结构LRU页面置换算法自定义页面应用LRU算法EXIT2.2原理框图-1-1-11-1-112-1125Block2.3设计原理LRU：最近最久未使用置换算法。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的的时间Timer，当须淘汰一个页面时，选择离当前时间最近的一段时间内最久没有使用过的页先淘汰即选择现有页面中其Timer值最大的给予淘汰。该算法的主要出发点是，如果某页被访问了，则它可能马上还要被访问。或者反过来说，如果某页很长时间未被访问，则它在最近一段时间也不会被访问。三、详细设计3.1数据结构typedefstructpages//定义一个结构体其成员有页面号//content和被访问标记timer；voidInit(intQString[20])//初始化内存块intfindSpace(void)//查找是否有空闲内存intfindExist(intcurpage)//查找内存中是否有该页面intfindReplace(void)//查找应予置换的页面voiddisplay(void)//显示voidLRU(void)//LRU页面置换算法voidBlockClear(void)//清空3.2程序流程图开始页面走向存入数组QString[]中，内存块用page[]表示，初始化为0当前QString[]中i个元素是否已在内存QString[]是否有空i++YN把page[]中最近最久未使用的页面置换出去，i++把QString[]的内容直接装入最上面一个空内存块，i++YN输出当前内存块状态结束3.3代码及注释#includestdio.h#includestring.h#includeiostreamusingnamespacestd;intBsize=3;intPsize=20;typedefstructpages//定义一个结构体{intcontent;//页面号inttimer;//被访问标记}page;pageblock[8];//物理块pagepages[20];//页面号串voidInit(intQString[20]){//初始化inti;for(i=0;iBsize;i++){block[i].content=-1;block[i].timer=0;}for(i=0;iPsize;i++){pages[i].content=QString[i];pages[i].timer=0;}}intfindSpace(void){//查找是否有空闲内存inti;for(i=0;iBsize;i++)if(block[i].content==-1)returni;//找到空闲内存，返回BLOCK中位置return-1;}intfindExist(intcurpage){//查找内存中是否有该页面inti;for(i=0;iBsize;i++)if(block[i].content==pages[curpage].content)returni;//找到内存中有该页面，返回BLOCK中位置return-1;}intfindReplace(void){//查找应予置换的页面，被置换的页面的Timer值最大intpos=0,i;for(i=0;iBsize;i++)if(block[i].timer=block[pos].timer)pos=i;//找到应予置换页面，返回BLOCK中位置returnpos;}voiddisplay(void){//显示inti;for(i=0;iBsize;i++)if(block[i].content!=-1)coutblock[i].content;coutendl;}voidLRU(void){//LRU页面置换算法intexist,space,position,n=0,i,j;doublep=0,q=0;for(i=0;iPsize;i++){exist=findExist(i);if(exist!=-1){cout不缺页endl;block[exist].timer=0;n++;}else{//找到空闲分区space=findSpace();if(space!=-1){block[space]=pages[i];display();}else{//没有找到空闲分区，需找一个页面进行置换position=findReplace();block[position].timer=0;block[position]=pages[i];display();}}for(j=0;jBsize;j++)block[j].timer++;//BLOCK中所有页面TIMER++}coutendl缺页次数为：Psize-nendlendl;p=(Psize-n)*1.0/Psize;cout缺页率为：pendlendl;q=n*1.0/Psize;cout命中率为：qendlendl;}voidBlockClear(void){//清空inti;for(i=0;iBsize;i++){block[i].content=-1;block[i].timer=0;}}intmain(){intQString[20],i;coutendl;cout┏━━━━━━━━━━━━━━━━━━━━┓endl;cout┃┃endl;cout┃┃endl;cout┃请求页式存储管理中LRU算法的实现┃endl;cout┃┃endl;cout┃1.自定义页面┃endl;cout┃┃endl;cout┃2.应用LRU算法┃endl;cout┃┃endl;cout┃3.EXIT┃endl;cout┃┃endl;cout┃┃endl;cout┣━━━━━━━━━━━━━━━━━━━━┫endl;intselect;do{coutendl请输入你要进行的操作序号(1~3):;cinselect;if(select==1){coutendl请输入页块数(1-8)：;scanf(%d%*c,&Bsize);while(Bsize1||Bsize8){cout输入不符合要求，请重新输入：;scanf(%d%*c,&Bsize);}coutendl请输入进程数(1-20)：;scanf(%d%*c,&Psize);while(Psize1||Psize20){cout输入不符合要求，请重新输入：;scanf(%d%*c,&Psize);}coutendl请输入页面访问序列：;for(i=0;iPsize;i++)scanf(%d,&QString[i]);Init(QString);coutendlendl;cout|***************************************************************|endlendl;}elseif(select==2){coutendlLRU算法结果如下:endl;LRU();BlockClear();cout|***************************************************************|endlendl;}elseif(select==3){break;}}while(select==1||select==2||select==3);return0;}四、运行结果4.1运行及测试结果进程页块数：3，页面访问序列12560365365604270435进程页块数：4，页面访问序列32461364365624071435输入不在范围内的进程数和页块数4.2使用说明书打开终端，输入“g++-LRU.cpp-oLRU”之后，输入“./LRU”运行程序；出现主界面后可以看到三个功能选项，输入要操作的序列号即可；输入1，再输入相应的块数，进程数和页面访问序列即可进行自定义页面；输入2，就会利用LRU页面置换算法进行缺页次数、缺页率和命中率的计算；输入3，退出程序。五、课程设计小结与心得体会5.1课设小结通过本次操作系统课程设计，我对LRU页面置换算法有了全新的认识。拿到该课程设计题目时，我首先对这个题目进行了概要的分析、设计，分析出这个程序是干什么用的，应该实现什么功能，这些功能应该包含哪些函数。概要设计做好后，就要开始做详细设计，将做好的概要设计进行完善，把每个函数要实现的功能用伪代码写出来，并用流程图画出来，这样就能基本上知道每个程序应该如何实现它自身的功能，写源代码时思路就会更清晰。写源代码是将详细设计转化为C++代码的过程，详细设计做好后，只需在其基础上将一些简单的用汉语代替的语句用C++语句写出来，并完善概要设计和详细设计时未考虑到的功能，最终形成一个可执行的C++文件。我是根据上学期操作系统存储管理这一实验进行相应的更改和完善的，因此会相对简单一些。因为对C++掌握的不够熟练，所以有些输入语句还是用C的方式，这使代码整体看起来可能会有些繁琐。