实验三页面置换算法实验

《操作系统原理》实验报告实验三页面置换算法实验专业：计算机科学与技术学号：030840204姓名：简郸实验日期：2010-5-22一、实验目的通过模拟实现请求页式存储管理的几种基本页面置换算法，了解虚拟存储技术的特点，掌握虚拟存储请求页式存储管理中几种基本页面置换算法的基本思想和实现过程，并比较它们的效率。二、实验要求设计一个虚拟存储区和内存工作区，并使用下述算法计算访问命中率。1．最佳淘汰算法（OPT）2．先进先出的算法（FIFO）3．最近最久未使用算法（LRU）三、实验方法内容1.算法设计思路1．假设分给一作业的内存块数为4，每条指令占一个存储单元，每个页面中可存放10条指令；2．设计一个程序，模拟一作业的执行过程。设该作业共有160条指令，即它的地址空间为16页，最初作业的所有页面都还未调入内存。在模拟过程中，如果所访问的指令已经在内存，则显示其物理地址，并转下一条指令。如果所访问的指令尚未装入内存，则发生缺页，此时需记录缺页的次数，并将相应页调入内存。如果4个内存块中均已装入该作业的虚页面，则需进行页面置换；在所有160条指令执行完毕后，请计算并显示作业运行过程中发生的缺页率。3．作业中指令的访问次序要求按下述原则生成：具体的实施办法是：(1)在[0，159]之间随机选取一条起始执行指令，其序号为m；(2)顺序执行两条指令，即序号为m+1、m+2的指令；(3)通过随机数，跳转到前地址部分[0，m-1]中的某条指令处，其序号为m1；(4)顺序执行两条指令，即序号为m1+1，m1+2的指令；(5)通过随机数，跳转到后地址部分[m1+3，159]中的某条指令处，其序号为m2；(6)顺序执行两条指令，即序号为m2+1，m2+2的指令；若m2+2159只执行一条指令；(7)重复“跳转到前地址部分、顺序执行、跳转到后地址部分、顺序执行”的过程，直至执行完全部160条指令2.算法流程图3.算法中用到的数据结构4.主要的常量变量5.主要模块四、实验代码#includestdlib.h#includeiostream.h#includetime.h#includestdio.h#definetotal_instruction200/*指令流长*/#defineM16/*实际页数*/#defineN4//可用页面数structPro{intnum,time;};inta[total_instruction];intpage[N];voidInput(Prop[total_instruction]){intm,i,m1,m2;srand((unsignedint)time(NULL));m=rand()%160;//for(i=0;itotal_instruction;)/*产生指令队列*/{if(m0||m159){printf(Wheni==%d,Error,m==%d\n,i,m);exit(0);}a[i]=m;/*任选一指令访问点m*/a[i+1]=a[i]+1;a[i+2]=a[i]+2;/*顺序执行两条指令*/intm1=rand()%m;/*执行前地址指令m1*/a[i+3]=m1;a[i+4]=m1+1;a[i+5]=m1+2;/*顺序执行两条指令*///s=(158-a[i+5])*rand()/32767/32767/2+a[i+5]+2;m2=rand()%(157-m1)+m1+3;a[i+6]=m2;if((m2+2)159){a[i+7]=m2+1;i+=8;}else{a[i+7]=m2+1;a[i+8]=m2+2;i=i+9;}m=rand()%m2;}for(i=0;itotal_instruction;i++)/*将指令序列变换成页地址流*/{p[i].num=a[i]/10;p[i].time=0;}}voidprint(Pro*page1)//打印当前的页面{Pro*page=newPro[N];page=page1;for(inti=0;iN;i++)coutpage[i].num;coutendl;}intSearch(inte,Pro*page1){Pro*page=newPro[N];page=page1;for(inti=0;iN;i++)if(e==page[i].num)returni;return-1;}intMax(Pro*page1){Pro*page=newPro[N];page=page1;inte=page[0].time,i=0;while(iN)//找出离现在时间最长的页面{if(epage[i].time)e=page[i].time;i++;}for(i=0;iN;i++)if(e==page[i].time)returni;return-1;}intCompfu(Pro*page1,inti,intt,Prop[M]){Pro*page=newPro[N];page=page1;intcount=0;for(intj=i;jM;j++){if(page[t].num==p[j].num)break;elsecount++;}returncount;}intmain(){Prop[total_instruction];Pro*page=newPro[N];charc;intt=0;floatn=0;Input(p);do{for(inti=0;iN;i++)//初试化页面基本情况{page[i].num=0;page[i].time=2-i;}i=0;coutf:FIFO页面置换endl;coutl:LRU页面置换endl;couto:OPT页面置换endl;cout按其它键结束endl;cinc;if(c=='f')//FIFO页面置换{n=0;cout页面置换情况:endl;while(itotal_instruction){if(Search(p[i].num,page)=0)i++;//找到相同的页面else{if(t==N)t=0;else{n++;//page[t].num=p[i].num;print(page);t++;}}}cout缺页次数：n缺页率：n/total_instructionendl;}if(c=='l')//LRU页面置换{n=0;cout页面置换情况:endl;while(itotal_instruction){intk;k=t=Search(p[i].num,page);if(t=0)page[t].time=0;else{n++;t=Max(page);page[t].num=p[i].num;page[t].time=0;}if(t==0){page[t+1].time++;page[t+2].time++;}if(t==1){page[2].time++;page[0].time++;}if(t==2){page[1].time++;page[0].time++;}if(k==-1)print(page);i++;}cout缺页次数：n缺页率：n/total_instructionendl;}if(c=='o')//OPT页面置换{n=0;while(itotal_instruction){if(Search(p[i].num,page)=0)i++;else{inttemp=0,cn;for(t=0;tN;t++){if(tempCompfu(page,i,t,p)){temp=Compfu(page,i,t,p);cn=t;}}page[cn]=p[i];n++;print(page);i++;}}cout缺页次数：n缺页率：n/total_instructionendl;}}while(c=='f'||c=='l'||c=='o');return0;}五、实验结果1.执行结果