课程设计-页面置换算法模拟-最近最久未使用（LRU） 

课程设计（论文）题目：页面置换算法模拟—最近最久未使用（LRU）院（系）：信息与控制工程系专业班级：计算机2012姓名：孙奇学号：201206060223指导教师：曾应员2015年1月23日西安建筑科技大学华清学院课程设计（论文）任务书专业班级：计算机1201班学生姓名：孙奇指导教师（签名）：曾应员一、课程设计（论文）题目页面置换算法模拟-最近最久未使用（LRU）算法：编写一个页面置换算法程序，采用最近最久未使用（LRU）置换算法，在需要页面调出时，选择在最近时期使用最久未使用的页面作为淘汰页。二、本次课程设计（论文）应达到的目的操作系统课程实践性比较强。课程设计是加强学生实践能力的一个强有力手段。课程设计要求学生在完成程序设计的同时能够写出比较规范的设计报告。严格实施课程设计这一环节，对于学生基本程序设计素养的培养和软件工作者工作作风的训练，将起到显著的促进作用。本题目要达到目的：通过对页面、页表、地址转换和页面置换过程的模拟，加深对请求调页系统的原理和实现过程的理解。三、本次课程设计（论文）任务的主要内容和要求（包括原始数据、技术参数、设计要求等）1）假设每个页面中可存放10条指令，分配给作业的内存块数为4。2）模拟一个作业的执行过程，该作业共有320条指令，即它的地址空间为32页，目前它的所有页都还未调入内存。在模拟过程中，如果所访问的指令已在内存，则显示其物理地址，并转下一条指令。如果所访问的指令还未装入内存，则发生缺页，此时需记录缺页的次数，并将相应页调入内存。如果4个内存块均已装入该作业，则需进行页面置换，最后显示其物理地址，并转下一条指令。在所有320指令执行完毕后，请计算并显示作业运行过程中发生的缺页率。3）置换算法：最近最久未使用（LRU）置换算法四、应收集的资料及主要参考文献：操作系统经典算法的编程实现资料非常丰富，可以在图书馆找书籍或在因特网上找资料，都很容易找到，但是大部分代码是不全的，不能直接运行，希望大家只是把它当参考，编码还是自己做。参考文献：【1】汤小丹、梁红兵、哲凤屏、汤子瀛编著.计算机操作系统（第三版）.西安：西安电子科技大学出版社，2007.5 【2】史美林编.计算机操作系统教程.北京：清华大学出版社，1999.11【3】徐甲同编著.操作系统教程.西安：西安电子科技大学出版社，1996.8 【4】Clifford，A.Shaffer编著.数决结构与算法分析(C++版).北京：电子工业出版社，2005.7【5】蒋立翔编著.C++程序设计技能百练.北京：中国铁道出版社，2004.1五、审核批准意见教研室主任（签字）设计总说明本次课程设计是在学习完《操作系统教程》后，进行的一次全面的综合训练，通过课程设计，让计算机专业的学生更好的掌握操作系统的原理以及实现方法，加深对操作系统基础理论和重要算法的理解，加强对学生的动手能力。课程设计要求是通过对页面，页表地址转换和页面置换过程的模拟，加深对请求调页系统的原理和实现过程的理解。同时此次课程设计的主要内容有以下三点：1）假设每个页面中可存放10条指令，分配给作业的内存块数为4。2）模拟一个作业的执行过程，该作业共有320条指令，即它的地址空间为32页，目前它的所有页都还未调入内存。在模拟过程中，如果所访问的指令已在内存，则显示其物理地址，并转下一条指令。如果所访问的指令还未装入内存，则发生缺页，此时需记录缺页的次数，并将相应页调入内存。如果4个内存块均已装入该作业，则需进行页面置换，最后显示其物理地址，并转下一条指令。在所有320指令执行完毕后，请计算并显示作业运行过程中发生的缺页率3）页面置换算法-最近最久未使用（LRU）算法关键字：页面置换，最近最久未使用，看未来等目录1.设计目的 42.问题描述 53.需求分析 6HYPERLINK5.详细设计 106.调试分析 167.使用说明 178.设计总结 179.参考文献 18HYPERLINK";}}cout<<endl;cout<<"命中率："<<n-(K+1)<<"/"<<n<<endl;}功能模块介绍5-4主函数图1主菜单模块程序中必须有的，负责调度函数的各个功能，是各个功能的纽带，负责整个程序的运行，2显示模块主要包含显示函数，用于显示主菜单，显示操作内容比如进程数，物理块数，显示每次换页后的结果函数,，此函数是显示在LRU算法的执行过程中每次换页的情况。显示一定不用换页的函数、：此函数是显示最近使用过的页面，即不用换页的结果。3判断模块包括数据输入判断，用来判断输入数据是否合理以及，进入算法判断，判断是否进入算法，还是退出程序，4lru模块计算缺页的主要函数，以及记录缺页次数，计算缺页率。6调试分析1实例测试数据1010241008内存状态111111111100000000022222844444具体数据见下图2算法改进设想本程序有缺陷，不能再次一自定义的形式输入，要想输入还需要人为输入要想进行的下一组数据，改进方法，设计重输入机制，用户可以在选择面板上重新输入想要进行的下一组数据，可以添加一个报错机制，当你输入的超过规定的进程数时会出现报错。在这个系统中我没有添加，因为当用户输入时会根据自己想要的进程数输入，要是不给加以控制会浪费内存。7使用说明7-2示例图示例图说明随机输入一个数，产生320个随机数然后将三百二十个随机数调入内存物理块数为四产生三十二页计算缺页率（因数据太多只截取部分）8设计总结页面置换算法理解比较容易，要求实现的是LRU算法的实现。分配到我的lru算法，没有去编写只是写出了大概的思路和算法框图。其实这算法的程序编写比较容易，虽然不全是自己编写的，一部分是参考的网上的例题，但是通过对每一语句的理解，自己弄懂了整个程序的执行原理。但是，在编写过程中自己还是遇到了一些问题。没有明白320条指令的意思经过改进知道了并改写了程序。编程的时候觉得程序的函数定义有辅助函数，当我在定义这个辅助函数有困难，因为里面的函数要相互联系，编程时没有考虑好整体算法思路，所以报错机制没有做好，我以后再做是会事先做好整体的设计在着手编写。最大的一个问题就是算法的正确实现，在程序的编写时自己的编程技术不好，程序编的也很繁琐，但是基本的要求已经实现了，希望这次的实验是自己动手的一个开始，自己应该更加努力，再接再厉。9.参考文献【1】汤小丹、梁红兵、哲凤屏、汤子瀛编著.计算机操作系统（第三版）.西安：西安电子科技大学出版社，2007.5 【2】史美林编.计算机操作系统教程.北京：清华大学出版社，1999.11【3】徐甲同编著.操作系统教程.西安：西安电子科技大学出版社，1996.8 【4】Clifford，A.Shaffer编著.数决结构与算法分析(C++版).北京：电子工业出版社，2005.7【5】蒋立翔编著.C++程序设计技能百练.北京：中国铁道出版社，2004.110．程序源代码#include<iostream.h>#include<stdlib.h>#include<conio.h>#include<stdio.h>#defineBsize4typedefstructBLOCK//声明一种新类型--物理块类型{intpagenum;//页号intaccessed;//访问字段，其值表示多久未被访问}BLOCK;intpc;//程序计数器，用来记录指令的序号intn;//缺页计数器，用来记录缺页的次数staticinttemp[320];//用来存储320条随机数BLOCKblock[Bsize];//定义一大小为4的物理块数组//*************************************************************voidinit();//程序初始化函数intfindExist(intcurpage);//查找物理块中是否有该页面intfindSpace();//查找是否有空闲物理块intfindReplace();//查找应予置换的页面voiddisplay();//显示voidsuijishu();//产生320条随机数,显示并存储到temp[320]voidpagestring();//显示调用的页面队列voidLRU();//LRU算法//voidinit(){for(inti=0;i<Bsize;i++){block[i].pagenum=-1;block[i].accessed=0;pc=n=0;if((i+1)%10==0)cout<<endl;}}//intfindExist(intcurpage)//查找物理块中是否有该页面{for(inti=0;i<Bsize;i++){if(block[i].pagenum==curpage)returni;//检测到内存中有该页面，返回block中的位置}return-1;}intfindSpace()//查找是否有空闲物理块{for(inti=0;i<Bsize;i++){if(block[i].pagenum==-1)returni;//找到空闲的block，返回block中的位置}return-1;}intfindReplace()//查找应予置换的页面{intpos=0;for(inti=0;i<Bsize;i++){if(block[i].accessed>block[pos].accessed)pos=i;//找到应予置换页面，返回BLOCK中位置}returnpos;}voiddisplay(){for(inti=0;i<Bsize;i++){if(block[i].pagenum!=-1){printf("%02d",block[i].pagenum);}}cout<<endl;}voidsuijishu(){intflag=0;printf("请输入一个0~320之间的随机数：\n");scanf("%d",&pc);printf("按照要求产生的320个随机数：\n");for(inti=0;i<320;i++){temp[i]=pc;if(flag%2==0)pc=++pc%320;//顺序执行下一条指令，即序号为m+1的指令 if(flag==1)pc=rand()%(pc-1);//通过随机数，跳转到前地址部分[0,m-1]中的某条指令处，其序号为m1 if(flag==3)pc=pc+1+(rand()%(320-(pc+1)));//通过随机数，