页面调度算法

操作系统课程设计报告题目：页式虚拟存储器管理：页面调度算法学院：班级：姓名：学号：指导教师：一、实验目的：页式虚拟存储器实现的一个难点是设计页面调度（置换）算法，即将新页面调入内存时，如果内存中所有的物理页都已经分配出去，就要按某种策略来废弃某个页面，将其所占据的物理页释放出来，供新页面使用。本实验的目的是通过编程实现几种常见的页面调度（置换）算法，加深读者对页面思想的理解。二、实验原理：1先进先出调度算法（FIFO）先进先出调度算法根据页面进入内存的时间先后选择淘汰页面，先进入内存的页面先淘汰，后进入内存的后淘汰。本算法实现时需要将页面按进入内存的时间先后组成一个队列，每次调度队首页面予以淘汰。2最近最少调度算法（LRU）先进先出调度算法没有考虑页面的使用情况，大多数情况下性能不佳。根据程序执行的局部性特点，程序一旦访问了某些代码和数据，则在一段时间内会经常访问他们，因此最近最少用调度在选择淘汰页面时会考虑页面最近的使用，总是选择在最近一段时间以来最少使用的页面予以淘汰。算法实现时需要为每个页面设置数据结构记录页面自上次访问以来所经历的时间。3最近最不常用调度算法（LFU）由于程序设计中经常使用循环结构，根据程序执行的局部性特点，可以设想在一段时间内经常被访问的代码和数据在将来也会经常被访问，显然这样的页面不应该被淘汰。最近最不常用调度算法总是根据一段时间内页面的访问次数来选择淘汰页面，每次淘汰访问次数最少的页面。算法实现时需要为每个页面设置计数器，记录访问次数。计数器由硬件或操作系统自动定时清零。（2）缺页调度次数和缺页中断率、缺页置换率计算：缺页中断次数是缺页时发出缺页中断的次数。缺页中断率=缺页中断次数/总的页面引用次数*100%。缺页调度次数是调入新页时需要进行页面调度的次数。缺页置换率=缺页调度次数/总的页面引用次数*100%。三、应用VC++6.0四、算法分析：FIFO先进先出调度算法：当页面框满时，最早进来的页面调出。LRU最近最少使用调度算法：当页面框满时，最近最少使用的页面调出。LFU最近最不常用调度算法：当页面框满时，最近最不常用的页面调出。1、使用includefstream.h头文件，这是文件输入输出库函数。includestdlib.h头文件做异常处理。2、建立页面类pageclasspage{public:intpagenumber;//页面号intR;//此页面被调入时间inthit;//命中次数page(){//初始化为0pagenumber=0;R=0;//此页面被调入时间，初次调入为零。每次调度R值加1；若命中则变回0；hit=0;}3、建立类Node定义指针classNode{public:pagedata;Node*link;};4、队列结点类定义Queue，页的信息排成队列。classQueue{public:intnum;//队列中元素个数Node*front;//指向头节点指针Node*rear;//指向尾节点指针public:Queue(){//构造函数front=NULL;rear=NULL;num=0;}~Queue();//析构函数，释放空间voidadd(pageadd_data);//入队pageputout();//出队voidExchange(pagedata);//若队列中含有此页，则将此页与队尾交换位置boollook(pagedatas);//查看是否有相同项voidoutput();//输出矩阵pageChooseOut(pageN1);//将队中某项出对};5、定义算法类AlgorithmclassAlgorithm{public:Node*next0;inttotal;//缺页的总页数inttotal_hit;//命中次数public:Algorithm(){total=0;total_hit=0;//命中总共次数//初始化为零}6、定义三个调度算法函数：voidFIFO(intT_data[],intT_num);//先进先出算法voidLRU(intT_data[],intT_num);//最近最少使用调度算法voidLFU(intT_data[],intT_num);//最近最不常用调度算法,每次浏览的页面入队，页面号不同。当使用LFU算法时先查找队列中是否有该项，若有则出队为此保留以前的命中次数};7、具体的算法实现函数Queue::~Queue(){Node*next;while(front){……}}pageQueue::ChooseOut(pageN1){//将队中某项出队Node*next;next=front;pageex;Node*next2;next2=front;while(next-data.pagenumber!=N1.pagenumber){……}if(next==front){……}if(next==rear){while(next2-link-data.pagenumber!=N1.pagenumber){……}rear=next2;rear-link=NULL;next-link=front;front=next;ex=putout();returnex;}while(next2-link-data.pagenumber!=N1.pagenumber){……}…………}voidQueue::add(pageadd_data){//入队Node*p=newNode;p-data=add_data;p-link=NULL;if(front==NULL){……;}else{……}num=num+1;}pageQueue::putout(){//出队……if(num==0){……}//若队空则报错……}voidQueue::Exchange(pagedatas){//若队列中含有此页，则将此页与队尾交换位置……while(next-data.pagenumber!=datas.pagenumber){……}if(next==front){……}if(next==rear)return;while(next2-link-data.pagenumber!=datas.pagenumber){……}…………}boolQueue::look(pagedatas){//查看是否有相同项Node*looknext;looknext=front;while(looknext!=NULL){if(datas.pagenumber==looknext-data.pagenumber){returntrue;}looknext=looknext-link;}returnfalse;}voidQueue::output(){//输出矩阵Node*next;next=front;while(next!=NULL){if(next-data.pagenumber==-1){……}else{……}next=next-link;}coutendl;}8、先进先出算法：当页面框满时，最早进来的页面调出。voidAlgorithm::FIFO(intT_data[],intT_num){//先进先出算法QueueQ1;//内存中的页面QueueQ2;//被置换出去的页面QueueFIFO_Q;//将文档中的数构成的矩阵转到队列中Node*next;pageout;pageT_x;//-------for(inti=0;i=T_num;i++){//将文档中的数构成的矩阵转到队列中T_x.pagenumber=T_data[i];FIFO_Q.add(T_x);}…………coutFIFO算法:endl;cout每次淘汰的页面号:;Q2.output();coutendl;cout缺页中断次数:totalendl;cout缺页中断率:(double)total/(total+total_hit)endl;cout缺页中断次数:total-3endl;cout缺页中断率:(double)(total-3)/(total+total_hit)endl;}9、最近最少使用调度算法，当页面框满时，最近最少使用的页面调出。voidAlgorithm::LRU(intT_data[],intT_num){//最近最少使用调度算法QueueQ1;//内存中的页面QueueQ2;//被置换出去的页面QueueFIFO_Q;//将文档中的数构成的矩阵转到队列中Node*next;pageout;pageT_x;//-------for(inti=0;i=T_num;i++){//将文档中的数构成的矩阵转到队列中T_x.pagenumber=T_data[i];FIFO_Q.add(T_x);}//-------next=FIFO_Q.front;while(next!=NULL){…………coutLRU算法:endl;cout每次淘汰的页面号:;Q2.output();coutendl;cout缺页中断次数totalendl;cout缺页中断率(double)total/(total+total_hit)endl;cout缺页中断次数total-3endl;cout缺页中断率(double)(total-3)/(total+total_hit)endl;}//------------------------------------------------------------------------------------------------10、最近最不常用调度算法，当页面框满时，最近最不常用的页面调出。voidAlgorithm::LFU(intT_data[],intT_num){//最近最不常用调度算法,每次浏览的页面入队，页面号不同。当使用LFU算法时先查找队列中是否有该项，若有则出队。QueueQ1;//内存中的页面QueueQ2;//被置换出去的页面QueueF_Q;//将文档中的数构成的矩阵转到队列中Node*next,*next2;pageout;pageT_x;intmin;//----------------------------------------------------------------------for(inti=0;i=T_num;i++)//将文档中的数构成的矩阵转到队列中{T_x.pagenumber=T_data[i];F_Q.add(T_x);}//----------------------------------------------------------------------next=F_Q.front;while(next!=NULL){…………coutLFU算法:endl;cout每次淘汰的页面号:endl;Q2.output();coutendl;cout缺页中断次数totalendl;cout缺页中断率(double)total/(total+total_hit)endl;cout缺页中断次数total-3endl;cout缺页中断率(double)(total-3)/(total+total_hit)endl;}7、主函数voidmain(){intx;while(x!=0){cout1:FIFO算法;2:LRU算法;3:LFU算法;endl;cout4:应用全部算法;0:退出;endlendlendl;cout请输入您要选择的算法序号:;inti=0;AlgorithmA1;pagep1;A1.total=0;A1.total_hit=0;cinx;if(x==0)break;intT_data[2