2023年面置换算法模拟实验报告

实验编号4名称页面置换算法模拟实验目的通过请求页式存储管理中页面置换算法模拟设计，以便:1、了解虚拟存储技术的特点2、掌握请求页式存储管理中页面置换算法实验内容与环节设计一个虚拟存储区和内存工作区，并使用FIF0和LRU算法计算访问命中率。〈程序设计,，先用srand()函数和rand()函数定义和产生指令序列,然后将指令序列变换成相应的页地址流，并针对不同的算法计算相应的命中率。〈程序1>include<windows.h>“Windows版，随机函数需要,GetCurrentProcessld()需要//#include<std1ib.h>//Linux版，随机函数srand和rand需要include<stdio.h>^//printf()需要defineTRUE1defineFALSE0#defineINVALID-1#defineNULL0。freepf^head=freepf_head—>next;00}else3pmt[page[i]].counter=1；eif(i%c1ear_period==0)sfor(j=0;j<tota1_vp;j++)叩mt[j].counter=0;°)printf(11NUR：%6.4f1oat)NoPageCount/320)；实验结果（写出结果，截图也可）请插，.江面长度。九16输出随机数：许输入分配的物理块水2〜6〉：41：PIFO页面置换2：LRU页面置换3：OPT页面置换请选择页面置换算法，

FIFOi2法页面置换情况如下:TOC\o"1-5"\h\z33000636005365073657116575不缺页9195701907219021不缺页66982464026不缺页164127641733417000555^0^9^0^3333313s5r?l缺页次数,13缺页率，0.8125000555^0^9^0^3333313s5r?lF不缺页919570195029502910261026142950291026102614不缺页

不缺页F77614F7761437613缺页次数,F7761437613缺页次数,13缺页率，。.8125OPT苴士苦心府况如下:3657159021S4S1F730007700555^0^0^0^03657159021S4S1F730007700555^0^0^0^03333177777902费4页页页4666赧»6静^^6

il不不1不不不3缺页次数，I®缺页率,0.625总结（收获，未实现的环节）这次操作系统课程设计，让我们对操作系统有了更深的结识，一方面操作系统是一管理电脑硬件与软件资源的程序,同时也是计算机系统内核与基石。操作系统是一个庞大的管理控制程序，大体涉及5个方面的管理功能:进程与解决机管理、作业管理、存储管理、设备管理、文献管理。我们这次课程设计的题目是页面置换算法,是属于存储器管理。在进程运营过程中,若其访问的页面不在内存而需把它们调入内存，但内存以无空闲空间时，为了保证该进程能正常的运营,系统必须从内存中调出一页程序或数据送磁盘的兑换区中，但应将哪个页面调出,需根据一定的算法来拟定。通常，把选择换成页面的算法称为页面置换算法。通过本次课程设计，我们对页面置换算法的了解更加的深刻。重要有以下置换算法：OPT（最佳置换算法）、FIFO（先进先出置换算法）、LRU（最近最久未使用算法）。每种算法都有各自的优缺陷，OPT算法是实际中不能实现的，但是可以运用该算法去评价其它算法；FIFO算法与进程实际运营的规律不相合用，由于在进程中,有些页面经常被访问;LRU算法是根据页面调入内存后的使用情况进行决策的。在这次课程设计中，碰到了一些困难，例如怎么实现各种算法，如何进行函数调用及对数据的限制操作等,在碰到这些困难的时候，我们会去查阅资料，仔细看书，尝试用不同的方法解决，在各种方法中选择一种最佳的方法，有的时候会碰到不知道如何实现的函数，我们会查看MSDN,这次是用的C++语言做的，每一步都是自己独立完毕的，这次课程设计我最大的收获是学以致用，通过这次设计我们看到了自己学习的能力，我们相信在以后的学习中，会更加的努力上进。最后，还非常感谢辛劳的操作系统老师，一方面，由于他辛劳的为我们讲解操作系统这门课，让我们对操作系统有了一定的了解，为这次课程设计奠定了良好的基础，另一方面,还要感谢他认真指导我们的这次课程设计，给了我们这次总体运用自己能力的机会，我们坚信:只要功夫深，铁杵磨成针。definetota1_instraction320。。//共320条指令definetotal—vp32。。〃虚存页共32页defineclear_period50。。//访问次数清零周期typedefstruet{//定义页表结构类型(页面映射表PMT)“ntpn,pfn,counter,time;//页号、页框号(块号)、一个周期内访问该页面的次数、访问时间}PMT；PMTpmt[32];typedefstructpfc_struct{〃页面控制结构“ntpn,pfn;ostructpfe_struct*next;}pfc_type;Pfc_typepfc[32];pfc.type*freePLhead,*busypf_head,*busypf_tail;//空闲页头指针，，忙页头指针，忙页尾指针intNoPageCount;〃缺页次数inta[total__instruction];//指令流数组intpage[tota1—instruetion],offset[total_instruetion];//每条指令的页和页内偏移voidinitia1ize(int);voidFIFO(int);//先进先出voidLRU(int);〃最近最久未使用voidNRU(int);〃最近最不经常使用***************************************************************************main()******************************************************************voidmain(){inti,s;V/srand(10*getpid());//用进程号作为初始化随机数队列的种子。“Linux版6srand(10*GetCurrentProcessId())；〃用进程号作为初始化随机数的种子//Windows版0。s=rand()%320；//在[0,319]的指令地址之间随机选取一起点mfor(i=0;i<total_instruction；i+=4){〃产生指令队列oif(s<0||s>319){叩rintf("wheni==%d,error,s==%d\nn,i,s)；exit(0);6)8a[i]=s；〃任意选一指令访问点m。(将随机数作为指令地址m)。a[i+l]=a[i]+l；//顺序执行下一条指令-a[i+2]=rand()%(s+2);〃在[0,m+l]的前地址之间随机选取一地址，记为a[i+3]=a[i+2]+1;〃顺序执行一条指令。s=a[i+2]+(int)rand()%(320-a[i+2]);//在[m-319]的指令地址之间随机选取一起点moif((a[i+2]>318)||(s>319))printf(Ha[%d+2,anumberwhichis：%dands二%d\n\i,a[i+2],s);。for(i=0;i<total_instruction;i++){//将指令序列变成页地址流PageLi]=aLi]/10;®offset[i]=a[i]%10;0)for(i=4;iv=32;i++){//内存块分别为4块、5块、...32块时的命中率printf(u%2dpageframesn,i);oFIFO(i);〃计算用FIFO置换时，有i个内存块时的命中率»LRU⑴;〃最近最久未使用NRU(i);//最近最不经常使用叩rintf(“\n");)/*1*IIII*1*■1**1*IIiI*t*III|I/*不***半***牛大不不不不不不不不大大拳拳大不举不军大牛不大不不半半半不大*不半不不不半半不大半不**不大不不*不不不不不不不**********initialize()形参：内存块数功能：初始化**************************************************************************Ivoidinitia1ize(inttota1_pf)//初始化相关数据结构，形参tota1_pf是用户进程的内存页面数(nti;NoPageCount=0；//缺页次数,初始化为0for(i=0；i<tota1_vp；i++){3pmt[i].pn=i;//填逻辑页号pmt[i].pfn=INVALID;//物理页面号为-1oopmt[i].counter=0;〃置页面控制结构中的访问次数为0叩mt[i].time=-1;〃置页面控制结构中的时间为-1for(i=0;i<total_pf-1;i++){〃建立pfc[i-1]和pfc[i]之间的连接gpfc[i].next=&pfc[i+1];pfc[i].pfn=i;)叩fc[total],next=NULL;pfc[total_pf-1].pfn=total—pf—1;6freepf_head=&pfc[0];//页面队列的头指针为pfc[0])/III*1*I|*1**2*IIIIIII/半火亭不不举亭亭大军不小不亭亭大军不举大举大不亭军大不火举牛斗不斗不举不火大军不不大不※不举不不亭不大不军大不军斗小牛举斗斗不不本************FIFO算法形参：内存块数输出：命中率拳不AA不大拳拳拳拳不***大举*亭*亭*大牛**拳拳拳半半半半不不不不不大*不半大牛不*举不半*拳不不大牛斗举半大7>7，7，7*7*7*7，*!>■!>7>7>7>7>7，7，7^7*I/rj*rj*/voidFIFO(inttotal_pf)〃形参total_Pf是用户进程的内存页面数inti;pfc_type*p;initia1ize(total_Pf)；〃初始化相关数据结构ebusypf_head=busypf_tai1=NULL;for(i=0;i<total_instruction;i++){//访问每条指令3if(pmt[page[i]].pfn==INVALID){〃缺页3oNoPageCount+=1;〃失效(缺页)次数增1^if(freepf_head==NULL){〃无空闲页面op=busypf_head->next；eopmt[busypf_head->pn].pfn=INVALID;“^freepf_head=busypf_head;//释放忙页面队列的第一个页面ogfreepfLhead->next=NULL;ebusypf_head=p;}p=freepf_head->next;〃按FIFO方式调新页面入内存ofreepf_head->next=NULL;freepf_head—>pn=page[i];ooopmt[page[i]].pfn=freepf_head->pfn；aif(busypfLtaiI==NULL)busypf_head=busypf_tail=freepf_head;8。eIse{8obusypf_tai1->next=freepChead；//free页面减少一个busypfLtail=freepf_head;bbb}肃reepf_head=p;°}°}叩rintf(nFIFO：%6.4f;l-(float)NoPageCount/320);)/********************************************************1**2*I*1**1**£*.R.Rrj*•门•卜,.、..、^7^.R.R•卜LRU算法(最近最久未使用)形参:内存块数输出:命中率*****************************************************************************/voidLRU(inttotal_pf)//形参total_pf是给用户进程的内存块数“ntmin,minj,i,j,present_time;initialize(total_pf);present_time=0;sfor(i=0;i<total_instruction;i++){oif(pmt[page[i]].pfn==INVALID){〃页面失效8。NoPageCount++；。if(freepfLhead==NULL){//无空闲页面gmin=32767;“for(j=0;j<total_vp；j++)〃找出time的最小值。if(min>pmt|j].time&&pmt[j].pfn!=INVALID){。。。min=pmt[j].time;6°minj=j;00}^>freepf_head=&pfc[pmt[minj].pfn];〃腾出一个单元。。pmt[minj].pfn=INVALID;o。pmt[minj],time-1;e。freepf_head—>next=NULL；eg}3叩mt[page[i]].pfn=freepf_head—>pfn;〃有空闲页面，改为有效bopmt[page[i]].time=present_time;。freepjhead=freepjhead—>next;//减少一个free页面-Isepmt[page[i]].time=present_time;//更新该页面的访问时间（并非真的时间，而是循环次数，每执行一条指令，时间加1）present_time++；〃当前时间加1°）叩rintf("LRU:%6.4fn,1-(float)NoPageCount/320);I********************************************************