页面置换实验报告

操作系统课程设计专题：页面置换算法任务：设计一个虚拟存储区和内存工作区,编程序演示下述算法的具体实现过程,并计算访问命中率：要求设计主界面以灵活选择某算法，且以下算法都要实现1）先进先出算法（FIFO）2）最近最久未使用算法（LRU）3）最佳置换算法（OPT）思想：1.最佳置换算法：最佳置换算法是一种理论上的算法，其所选择的被淘汰页面，将是以后永不使用的，或者是在最长（未来）时间内不再被访问的页面。采用最佳置换算法，通常可保证获得最低的缺页率。701203042303212017017772222444000000077700000333222221111100001111000333332222212.先进先出页面置换算法:这是最早出现的置换算法。该算法总是淘汰最先进入内存的页面，即使选择在内存中驻留时间最久的页面予以淘汰。该算法实现简单，只需把一个进程已调入内存的页面，按先后次序连接成一个队列，并设置一个指针，成为替换指针，使它总是指向最老的页面。但该算法与进程实际运行的规律不相适应，因为在进程中，有些页面经常被访问，所以先进先出算法并不能保证这些页面不被淘汰。701203042303212017017772222444000111111100000000033333300000001113332222222227773.最近最久未使用置换算法：最久最久未使用的页面置换算法，是根据页面调入的先后的使用情况进行决策的。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来经历的时间t，当须淘汰一个页面时，选择现有页面中其t值最大的，即使最近最久未使用的页面予以淘汰。最近最久未使用算法70120304230321201701777222222222222227770000000444000000000000111333333331111111任务目的：1．通过模拟实现请求页式存储管理的几种基本页面置换算法，了解虚拟储技术的特点。2．通过对页面、页表、地址转换和页面置换过程的模拟，加深对请求调页系统的原理和实现过程的理解。3．掌握虚拟存储请求页式存储管理中几种基本页面置换算法的基本思想和实现过程，并比较它们的效率。方案：输入页面序列，缺页时按FIFO、LRU、OPT的策略进行页面置换，输出置换情况和缺页次数。假设页面数不超过pSIZE。process[20]表示简化了的页表，只包含页号序列。mSIZE表示分配给该进程的块数。Count用来表示置换次数。初始化：输入分配的块数mSIZE，输入页面序列，存放于数组process[20]中。按照循环，依次查找页面是否存在于页表中，不存在则置换页面，初始为0，变化同上。格式化依次输出访问下一个页面后的页表，然后输出缺页中断总次数框图：程序：#includestdio.h#includestdlib.h#definemSIZE3#definepSIZE20staticintmemery[mSIZE]={0,0,0};staticintprocess[pSIZE]={0};voidFIFO();voidLRU();voidOPT();intmain(){intcode,password;get();do{printf(---------------------------------------------------\n);printf(|***********|\n);printf(|1.FIFO*****|\n);printf(|**************************|\n);printf(|2.LRU*******|\n);printf(|********|\n);printf(|3.OPT************|\n);printf(|*******|\n);printf(|4.EXIT***************|\n);printf(-------------------------------------------*-------\n);printf(enteryourchoice:);scanf(%d,&code);switch(code){case1:{FIFO();}break;case2:{LRU();}break;case3:{OPT();}break;case4:{}break;}}while(code!=4);system(PAUSE);return0;}get(){inti,n;for(i=0;i20;i++){printf(process[%d]=,i);scanf(%d,&process[i]);}printf(\n);}voidFIFO(){intmemery[mSIZE]={0,0,0};inttime[mSIZE]={0,0,0};inti,j,k;intmax=0;intcount=0;for(i=0;ipSIZE;i++){printf(%d,process[i]);}printf(\n);for(i=0;imSIZE;i++){memery[i]=process[i];time[i]=i;for(j=0;jmSIZE;j++){printf(%d,memery[j]);}printf(\n);}/*前mSIZE个数直接放入*/for(i=mSIZE;ipSIZE;i++){for(j=0,k=0;jmSIZE;j++){if(memery[j]!=process[i])k++;}/*判断新页面号是否在物理块中*/if(k==mSIZE)/*如果都不在物理块中*/{count++;if(time[0]time[1])max=0;elsemax=1;if(time[2]time[max])max=2;memery[max]=process[i];time[max]=i;for(j=0;jmSIZE;j++){printf(%d,memery[j]);}printf(\n);}else{for(j=0;jmSIZE;j++){printf(%d,memery[j]);}printf(\n);}}printf(time:%d\n,count);printf(minzhonglv=%d%,(20-count)*100/20);getch();}voidLRU(){intmemery[mSIZE]={0,0,0};intflag[mSIZE]={0,0,0};inti,j,k;intmax=0,maxflag=0;intcount=0;for(i=0;ipSIZE;i++){printf(%d,process[i]);}printf(\n);for(i=0;imSIZE;i++){memery[i]=process[i];flag[i]=i;for(j=0;jmSIZE;j++){printf(%d,memery[j]);}printf(\n);}/*前mSIZE个数直接放入*/for(i=mSIZE;ipSIZE;i++){for(j=0,k=0;jmSIZE;j++){if(memery[j]!=process[i])k++;elseflag[j]=i;}/*判断新页面号是否在物理块中*/if(k==mSIZE)/*如果都不在物理块中*/{count++;if(flag[0]flag[1])max=0;elsemax=1;if(flag[2]flag[max])max=2;memery[max]=process[i];flag[max]=i;for(j=0;jmSIZE;j++){printf(%d,memery[j]);}printf(\n);}else{for(j=0;jmSIZE;j++){printf(%d,memery[j]);}printf(\n);}}printf(time:%d\n,count);printf(minzhonglv=%d%,(20-count)*100/20);getch();}voidOPT(){intmemery[mSIZE]={0,0,0};intnext[mSIZE]={0};inti,j,k,l;intcount=0,maxnext,max;for(i=0;ipSIZE;i++){printf(%d,process[i]);}printf(\n);for(i=0;imSIZE;i++){memery[i]=process[i];for(j=0;jmSIZE;j++){printf(%d,memery[j]);}printf(\n);}/*前mSIZE个数直接放入*/for(i=mSIZE;ipSIZE;i++){for(j=0,k=0;jmSIZE;j++){if(memery[j]!=process[i])k++;}/*判断新页面号是否在物理块中*/if(k==mSIZE)/*如果都不在物理块中*/{count++;for(l=i+1;lpSIZE;l++){if(memery[0]==process[l]){next[0]=l;gotolin1;}}next[0]=l;gotolin1;lin1:for(l=i+1;lpSIZE;l++){if(memery[1]==process[l]){next[1]=l;gotolin2;}}next[1]=l;gotolin2;lin2:for(l=i+1;lpSIZE;l++){if(memery[2]==process[l]){next[2]=l;gotolin3;}}next[2]=l;gotolin3;lin3:if(next[0]=next[1])max=0;elsemax=1;if(next[2]=next[max])max=2;memery[max]=process[i];for(j=0;jmSIZE;j++){printf(%d,memery[j]);}printf(\n);}else{for(j=0;jmSIZE;j++){printf(%d,memery[j]);}printf(\n);}}printf(time=%d\n,count);printf(minzhonglv=%d%,(20-count)*100/20);getch();}文档：运行环境WIN-TC先输入页面号选择界面输入选择1：FIFO运行结果：输入选择2：LRU运行结果：输入选择3：OPT运行结果：九、总结：通过这次试验，更加熟悉了最佳置换算法、先进先出算法和最近最未使用算法。掌握分页式存储管理的基本概念和试验方法。在实验过程中OPT置换算法编写时遇到困难，但是去复习了下C语言熟悉了GOTO语句后终于写出。还知道编程很锻炼自己的逻辑思维能力，使自己在课程设计中得到锻炼。