请求页式存储管理的页面置换算法

《操作系统》实验报告实验五请求页式存储管理的页面置换算法实验目的：通过请求页式存储管理中页面置换算法模拟程序，了解虚拟存储技术的特点，掌握请求页式存储管理的页面置换算法。实验属性：设计实验内容：1.通过随机数产生一个指令序列，共320条指令，指令的地址按下述原则生产：50％的指令是顺序执行的；25％的指令是均匀分布在前地址部分；25％的指令是均匀分布在后地址部分。2.将指令序列变换成为页地址流：设页面大小为1K；用户内存容量为4页到32页；用户虚存容量为32K。在用户虚存中，按每K存放10条指令排列虚存地址，即320条指令在虚存中的存放方式为：第0条至第9条指令为第0页；第10条至19条指令为第1页；…第310条至319条指令为第31页。3.计算并输出下述各种算法在不同内存容量下的命中率。(1)先进先出算法（FIFO）(2)最近最少使用算法（LRU）(3)最佳使用算（OPT）命中率＝１－页面失效次数／页地址流长度本实验中，页地址流长度为320，页面失效次数为每次访问相应指令时，该指令所对应的页不在内存的次数。实验思路：关于随机数的产生办法，首先要初始化设置随机数，产生序列的开始点，可通过下列语句实现：srand(400)；(1)计算随机数，产生320条指令序列m＝160；for(i＝0；i＜80；i++＝{j＝i﹡4；a[j]＝m；a[j+1]＝m+1；a[j+2]＝a[j]﹡1.0﹡rand()/32767；a[j+3]＝a[j+2]+1m＝a[j+3]+(319-a[j+3])﹡1.0﹡rand()/32767；}(2)将指令序列变换成为页地址流for(k＝0；k＜320；k++){pt＝a[k]/10；pd=a[k]%10；…}(3)计算不同算法的命中率rate＝1-1.0﹡U/320；其中U为缺页中断次数，320是页地址流长度。(4)输出格式kfifo1ru40.230.25…321.01.0实验内容：实现程序：主要的数据结构：voidbuild();intsearchpb();intsearchpro();voidOptimal();voidFIFO();voidLRU();voidempty();voidmain();主程序:#includestdio.h#includestdlib.h#includestring.h#definebsize4//物理块大小#definepsize16//进程大小intphb[bsize]={0};//物理块标号intpro[psize]={0};//进程序列号intflag[bsize]={0};//进程等待次数(存放最久未被使用的进程标志)inti=0,j=0,k=0;//i表示进程序列号,j表示物理块号intm=-1,n=-1;//物理块空闲和进程是否相同判断标志intmax=-1,maxflag=0;//标记替换物理块进程下标intcount=0;//统计页面缺页次数//随机产生序列号函数voidbuild(){printf(随机产生一个进程序列号为：\n);inti=0;for(i=0;ipsize;i++){pro[i]=10*rand()/(RAND_MAX+1)+1;printf(%d,pro[i]);}printf(\n);}//查找空闲物理块intsearchpb(){for(j=0;jbsize;j++){if(phb[j]==0){m=j;returnm;break;}}return-1;}//查找相同进程intsearchpro(){for(j=0;jbsize;j++){if(phb[j]==pro[i]){n=j;returnj;}}return-1;}//初始化内存voidempty(){for(i=0;ibsize;i++)phb[i]=0;count=0;//计数器置零}//先进先出页面置换算法voidFIFO(){for(i=0;ipsize;i++){m=searchpb();n=searchpro();//找flag值最大的for(j=0;jbsize;j++){if(flag[j]maxflag){maxflag=flag[j];max=j;}}if(n==-1)//不存在相同进程{if(m!=-1)//存在空闲物理块{phb[m]=pro[i];//进程号填入该空闲物理块count++;flag[m]=0;for(j=0;j=m;j++){flag[j]++;}m=-1;}else//不存在空闲物理块{phb[max]=pro[i];flag[max]=0;for(j=0;jbsize;j++){flag[j]++;}max=-1;maxflag=0;count++;}}else//存在相同的进程{phb[n]=pro[i];for(j=0;jbsize;j++){flag[j]++;}n=-1;}for(j=0;jbsize;j++){printf(%d,phb[j]);}printf(\n);}printf(缺页次数为：%d\n,count);printf(\n);}//主函数*voidmain(){intsel;do{printf(\t\t\t--------------------------------------\t\t\t);printf(\t\t\t☆☆^-^欢迎进入操作系统界面^-^☆☆\t\t\t);printf(\t\t\t--------------------------------------\t\t\t\n);printf(\t\t\t☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆\t\t\t);printf(\t\t\t☆虚拟内存☆\t\t\t);printf(\t\t\t☆--------------------------------☆\t\t\t);printf(\t\t\t☆1、产生随机序列☆\t\t\t);printf(\t\t\t☆--------------------------------☆\t\t\t);printf(\t\t\t☆2、最佳置换算法(OPT)☆\t\t\t);printf(\t\t\t☆--------------------------------☆\t\t\t);printf(\t\t\t☆3、先进先出(FIFO)☆\t\t\t);printf(\t\t\t☆--------------------------------☆\t\t\t);printf(\t\t\t☆4、最久未使用(LRU)☆\t\t\t);printf(\t\t\t☆--------------------------------☆\t\t\t);printf(\t\t\t☆5、三种算法的比较☆\t\t\t);printf(\t\t\t☆--------------------------------☆\t\t\t);printf(\t\t\t☆0、退出(Exit)☆\t\t\t);printf(\t\t\t☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆\t\t\t\n);printf(请选择所要执行的操作(0/1/2/3/4/5):);scanf(%d,&sel);switch(sel){case0:printf(\t\t\t^-^再见！^-^\t\t\t\n);system(pause);break;case1:build();break;case2:printf(最佳置换算法\n);Optimal();empty();break;case3:printf(先进先出算法\n);FIFO();empty();break;case4:printf(最久未使用算法\n);LRU();empty();break;case5:printf(最佳置换算法\n);Optimal();empty();printf(先进先出算法\n);FIFO();empty();printf(最久未使用算法\n);LRU();empty();break;default:printf(请输入正确的选项号！);printf(\n\n);break;}}while(sel!=0);}实验结果：图1图2图3实验总结：1．请求页式存储管理的实现原理：请求分页虚拟存储管理是将进程信息的副本存放在副主存储器中，当它被调度投入运行时，并不把程序和数据全部装入主存，仅装入当前使用的页面，进程执行过程中访问不在主存的页面时，再把所需信息动态地装入。当需要执行某条指令或使用某个数据而发现他们不在主存时，产生缺页异常，系统从磁盘中把此指令或数据所在的页面装入，保证用不到的页面不会被装入主存。2．写出这三种页面置换算法的实现思想。(1)最佳置换算法(OPT):当要调入一页而必须淘汰旧页时应该淘汰以后不再访问的页或距现在最长时间后要访问的页面。(2)先进先出(FIFO):基于程序总是按线性顺序来访问物理空间这一假设，总是淘汰最先调入主存的页面，即淘汰在主存中驻留时间最长的页面，认为驻留时间最长的页不再使用的可能性较大。(3)最久未使用(LRU):最近最少使用页面替换算法淘汰的页面是在最近一段时间内最久未被访问的那一页，基于程序的局部性原理来考虑，认为那些刚被使用过的页面可能还要立即被使用，而那些在较长时间内未被使用的页面可能不会立即使用。3．对不同算法的性能进行评价。(1)最佳置换算法(OPT):这种算法产生的缺页数最少，却需要预测程序的页面引用串，这是无法预知的，不可能对程序的运行过程作出精确的断言，不过理论可用作衡量各种具体算法的标准。(2)先进先出(FIFO):这种算法较易实现，比较适用于具有线性顺序特性的程序，而对其他特性的程序则效率不高；缺页中断率为最佳算法的2~3倍；增加可用主存块的数量会导致更多的缺页。(3)最久未使用(LRU):最近最久未被使用算法的实现需要硬件支持，关键是确定页面最后访问以来所经历的时间。