页面置换算法实验报告

页面置换算法

实验报告、实验目的：设计和实现最佳置换算法、随机置换算法、先进先出置换算法、最近最久未使用置换算法、简单Clock置换算法及改进型Clock置换算法；通过支持页面访问序列随机发生实现有关算法的测试及性能比较。二、 实验内容：虚拟内存页面总数为N,页号从0到N-1物理内存由M个物理块组成•页面访问序列串是一个整数序列，整数的取值范围为0到N-1。页面访问序列串中的每个元素p表示对页面p的一次访问页表用整数数组或结构数组来表示口符合局部访问特性的随机生成算法确定虚拟内存的尺寸N,工作集的起始位置p,工作集中包含的页数e，工作集移动率m(每处理m个页面访问则将起始位置p+1)，以及一个范围在0和1之间的值t；生成m个取值范围在p和p+e间的随机数，并记录到页面访问序列串中；生成一个随机数r,0WrW1；如果r<t,则为p生成一个新值，否则p=(p+1)modN；如果想继续加大页面访问序列串的长度,请返回第2步,否则结束。三、 实验环境：操作系统：Windows7软件：VC++6.0四、实验设计：本实验包含六种算法,基本内容相差不太,在实现方面并没有用统一的数据结构实现,而是根据不同算法的特点用不同的数据结构来实现：1、 最佳置换和随机置换所需操作不多,用整数数组模拟内存实现；2、 先进先出置换和最近最久未使用置换具有队列的特性,故用队列模拟内存来实现；3、 CLOCK置换和改进的CLOCK置换具有循环队列的特性,故用循环队列模拟内存实现；4、 所有算法都是采用整数数组来模拟页面访问序列。五、数据结构设计:-^yemianzhihuanclassesj-弋LinkQueue总frontfjrear-弋LNode识data0flag0modify识next-七QNode少data(?next〃页面访问序列数组：intref[ref_size];〃内存数组：intphy[phy_size];〃队列数据结构定义：typedefstructQNode〃定义队列数据结构{intdata;structQNode*next;}QNode,*QueuePtr;typedefstruct{QueuePtrfront; 〃头指针QueuePtrrear; 〃尾指针}LinkQueue;〃定义链表数据结构typedefstructLNode〃定义循环链表数据结构{intdata;intflag; 〃访问位intmodify; 〃修改位structLNode*next;}LNode,*LinkList;六、主要函数说明:-_JGlobals.CLOCK0.CreatList(LinkList&L]4DelMidQueuefLinkQueueSQ,int电DeQueuefLinkQucuc屋Q,int£e]DestroyLinkLisl(LinkList&L].DestroyQueue(LinkQueue&Q).EnQueuefLinkQueue&Qfinte]ExchangeLNode(LinkList8Lint也inti].FIFOQ4getnum[inta,intb)4lnitQucuc[LinkQueue&Q)Insert_LNode[LinkList inte]LRUO4mainQmaxi(inta,inth,intc)Modified_ClockO.ORA0iRANDOSe3rch_LinkList[LinkList&Linte,int&i].Se3rch_LL_Flag(Linl(List&Lint&i).Search_LL_ModifyClock(LinkListSL,intSmodifynum]ScarchQueue[LinkQucuc&Q,inte,int&i)Set_LL_Fl3g(LinkListinti]4Set_LL_modify(LinkListflLinti]电setrandnumQ1、voidset_rand_num() 〃产生具有局部特性的随机数列；2、 intExchange_LNode(LinkList&L,inte,inti)//将链表L中序号为i的结点替换为内容为e的结点；3、 boolSearch_LinkList(LinkList&L,inte,int&i)//找到链表L中内容为e的结点，并用i返回其位置，i=l表示第一个非头结点，依次类推；4、 voidSearch_LL_Flag(LinkList&L,int&i"用i返回第一个flag为0的结点的位置,i=1表示第一个非头结点，以此类推；5、 voidSet_LL_Flag(LinkList&L,inti)〃设置链表L中的序号为i的结点的flag标志为1；6、 intSearch_LL_ModifyClock(LinkList&L,int&modify_num)〃找到改进的CLOCK算法所需要淘汰的页，用modify_num返回其位置；此函数根据书上给的思路，第一遍扫描A=0且M=0的页面予以淘汰，若失败，则进行第二轮扫描A=0且M=1的页面，第二轮扫描时将所有访问过的页面的访问位A置0;若失败则重复上述两部；7、 voidSet_LL_modify(LinkList&L,inti)〃设置链表L中的序号为i的结点的modify标志为1；8、boolSearchQueue(LinkQueue&Q,inte,int&i) 〃寻找队列Q中结点data域等于e的结点，并用i返回其在Q中的位置；

9、9、intgetnum(inta,intb)〃用b返回元素a在被引用数列中的下一个位置10、voidORA()〃实现最佳置换算法，包括判断页面是否在内存中、页面进内存、输出内存状态等内容;〃随机置换算法〃先进先出算法〃最近最久未使用算法11〃随机置换算法〃先进先出算法〃最近最久未使用算法12、 voidFIFO()13、 voidLRU()实现最近最久未使用算法的思想是：判断待进入内存的页面，如果与内存中的第一个页面相同，则将它移到最后一个，即标志为最近使用的页；如果与内存中的第二个页面相同，则将它删除，并在队列尾部添加相同元素，即标志为最近使用的页;14、voidCLOCK() 〃实现CLOCK算法15、 voidModified_Clock()//实现改进的CLOCK算法16、intmain() 〃主函数，调用实现各算法的6个主要函数，并输出各算法的缺页率。七、实验问题回答:1、 FIFO算法是否比随机置换算法优越？答：FIFO算法比随机置换算法优越，但优势并不明显。2、 LRU算法比FIFO算法优越多少？答：LRU算法FIFO算法的效率要高5%-10%，有理论知识可知，页面访问序列具有局部性，而FIFO算法并不符合实际情况。3、 LRU算法和Optimal算法有何差距？答：LRU算法是所有算法中效率最接近Optimal算法的算法，由理论知识可知，Optimal算法是理想的算法，现实中几乎不可能实现，只能作为一种测评标准，LRU算法是效率较高的可实现置换算法，但其硬件要求较高，如果规模较小，则略显麻烦。4、 Clock算法和LRU算法有何差距？答：Clock算法和LRU算法从结果看来差距不大，Clock算法是使用软件的方式实现LRU算法中硬件的功能，从而在执行效率上会稍逊色些。八、实验过程结果截图:实验结果截图测评一：页面访问序列:12 15 13 151B17 16 18 18 171E18 18 21 201G22 21 23 21

总结；缺页率LI35^u1随机萱换00k--■*进先岀置换砂i頁近最久未使用置换40^t^LOGK置唤45x战进CLOCKS^457.1jPpessanykeytocontinueH测评二:n面访问序列:15 15 13 1516 1514 16 15 14 13 14 14 17 16 14 20 20 222Ba”佳萱换总结，缺贝率30x随机置换40x先:井先出萱换45z最近最久未使用置唤35xclockW4^35X甘进CLOCK置换35kPressanyJseytoicontinue测评三:页面访间序列:ia12ibuitisiuisibiy17iyzuiyin mmu22总结:缺页率”隹萱换35/C随机直换60x先进先岀置换50x頁近最久未使用置换45xCLOCK置换40X改讲CLOC喟揉45xPressanykeytocontinue—实验过程截图（注：只截取第三次测评，蓝色字体表示产生缺页中断）于：咬衣懾二学朝惬作慈页面^^^Debug^emidnzhihuan.exe- [=|叵|亠』n囱首扌年算［师“耳3CMKW耳耳JO<师“耳3CMKW耳耳JOC>：M师“耳卜n北京交通大学--计科“昶（注修土）--房®-lO4iG801"«xxxx«x«"x勺向访|口1序刿：TOC\o"1-5"\h\zp121S门1AIK1HIS1A19 17 19 23 19 1A1922512fi 22N减W耳）CNKW耳）C N减W耳）CNKW耳）C13 12 15险V瓦13\L2 12 15陡入页•151G 12 15陡入页匚15\L6 IS 15

肚人页：15吓 1R150H页；161G 1815H页；191?1817主二耳191?1820辻\页：181?182B応5⑷1?1820肚人页:20Q2 2123H耳222221F=l丿4-严.4〒午'1t234-3=-丄说L、J土4严任且次异诂嗽以1爼认姒：/~r随机置按算法士13 12 15辻人贝：13 12 1E讨儿耳151S 12 1E进八币1519 12 1G进人耳191& 19 20陡机宣换算吃缺页中断伙数；12TOC\o"1-5"\h\z:KENJ（垃耳（耳沌NW迪：KENJ（垃耳N胃专三）井三总出曽扌奂官］；十KNKJCNNHKNKH耳K胃耳耳NJtJCNNHjCNW13 12 15进入页:1313 12 15进入页；1512 15 16进入页:151S 16 18进入页:1615 1& 1S陡入页:灯TOC\o"1-5"\h\z18 19 £7田卫：H19 17 26陡人貝：22Q2 21 2Q注进先岀置换算法缺页中断枕数：10K“mx—KXXXKX最近最灵未使用置换算法UK—XXK—XXXK13 12陡入页.131512 1513肚入页=1513 161513 16 15进入耳1516 18 15进入兀18 15 16进入耳191A 17 19进入页:1917 20 19进入耳1?NU 1H 17进入页：22212022近最久天使圧置换算法缺页中断次数：空13 1215A：1 A：1ft：l进入页；13101215a：i fi：iA：1进入页；饰1f> 12ISA：1 A：0ft：l进入页:15161815A：0 A：1ft：l辺入页：16it ia15A：1 A：1ft:l

讲人页’1919 17A：1 A：1ISA：0进入页：1919 1?26A：1A：0A：1J曲入页：1919 1826A：1A：1A：1进入页.20222126A：1A：1进入页：22222126A：1A：1□MK直换算祛缺贝匚断枕数：级**改违的CLOCK置换算法樓改页（内存中序吕）：1A：1 H：@ A：1 M：1ISA：iM：0进入贝：13 「修改页（内存巾序号）；1A:1 N:tlfi:1 M:1 ft:1M:R甘.入.页’15修改贝（内存中号号）：2r：in-mr：mn：iisa：in：i辻入页：饰16 丄& 15修改页〔内莊巾序号）；2A：nH:fifl：1M:Rfi:1进入页：1616 18 15修改贝（内仔屮序号）：2触丄 N询 fis± M=0 AsiM：1Msl惟入页：1919 17修改页〔内存屮序号）：»n：im：in：in：015f\-QM：1憧人贝：I?19 丄7於改页（内存中序号）：勺A：1 M：1 A：0 M：12BA：1M：0陡入页；I?19 18陽改页（內存中序号）：iP：1 M：1 A：1 M：120fi：lM：0憾入页：22G1 20 22修改贝〔内存屮序吕）:2m；on：iM：efi=±m=ik进的CLOCK置换算去缺页中断次数：9缺仄窣随机置换60X*进先岀置换看近最久未使用置换45x置换k进CLOC1｛置换45x[Pressanykeytocontinue—九、实验结果分析:1、 最佳置换算法效果最佳不论在那组数据中，最佳置换算法的效果都是最好的，且都会比其它算法的性能高出不少。但通过课堂上的学习，我们知道这只是一种理想化算法，但实际上却难于实现，故主要用于算法评价参照。2、 随机算法的性能总是最不好的这是由于随机算法每次总是从所有页面中随机挑一个置换出去，但我们知道页面的访问存在着局部性的原理，并不是随机的，因此它的性能较差。3、 最近最久未使用算法的性能较好相较于先进先出和两种clock算法，最近最久未使用算法的性能略好，我们测试的数据规模相对较小，相信如果采用更大规模的数据，其优势会更加明显。当从课堂上我们知道要想在实际的应用中实现本算法，用软件的方法速度太慢，影响程序执行效率，如果采用硬件方法实现，则需要增加大量的硬件设备。4、 先进先出与clock算法的性能基本相同这是由于两种clock算法遍历链表采用的就是FIFO的方法，而改进的clock算法相比于简单clock算法的优势主要体现在会根据是否被修改进行选择，以减少写回所花费的时间。十、实验总结：这次实验总体难度不是很大，需要实现的算法数目虽然不少，但基本思路较为相似，因此实现起来也并不是十分困难。通过完成这次实验，除了加深了我对几种策略的理解，锻炼了我的编程能力，另一个巨大的收获就是了解了一些生成测试数据的方法。为了使我们的测试数据更贴近现实，我们引入了工作集的概念，并根据实际使用情况的特点设计出尽可能符合实际情况的随机数生成方案。通过阅读课件再加上自己的理解，我了解了老师的设计思路，感觉这个思路极其巧妙，设计中用到的方法和体现出的很多思想值得我们学习。十一、程序清单：#include<iostream>#include<windows.h>#include<time.h>#include<malloc.h>#include<conio.h>usingnamespacestd;#defineref_size20#definephy_size3intref[ref_size];floatinterrupt[6]={0.0};//intref[ref_size]={0};intphy[phy_size];//////////////////////////////////////////////////////////////////voidset_rand_num()//产生具有局部特性的随机数列{coutvv"页面访问序列："vvendl;intp=12;inte=4;intm=4;inti=0;intj=0;intn=0;doublet=0.6;inttemp;for(i=0;ivm;i++,j++){Sleep(1000*i);srand(time(NULL));temp=rand()%e+p;ref[j]=temp;cout<<ref[j]<<"";}for(n=0;n<4;n++){Sleep(1000*n);srand(time(NULL));doubler=(double)(rand()%10)/10.0;//cout<<r<<endl;if(r<t)p=p+int(10*r);elsep=(p+1)%20;for(i=0;i<m;i++,j++){Sleep(1000*i);srand(time(NULL));temp=rand()%e+p;ref[j]=temp;cout<<ref[j]<<"";}}cout<<endl;}////////////////////////////////////////////////////////////////typedefstructQNode//定义队列数据结构{intdata;structQNode*next;}QNode,*QueuePtr;typedefstruct{QueuePtrfront; //头指针QueuePtrrear; //尾指针}LinkQueue;//定义链表结点typedefstructLNode//定义循环链表数据结构{intdata;intflag; //访问位intmodify; //修改位structLNode*next;}LNode,*LinkList;//////////////////////////////////////////////////////////////////////////对循环链表的一些操作intCreatList(LinkList&L)〃创建循环带有头结点的链表{L=(LinkList)malloc(sizeof(LNode));if(!L)exit(-1);L->next=L;L->flag=0;return1;}intExchange_LNode(LinkList&L,inte,inti)//将链表L中序号为i的结点替换为内容为e的结点{if(L->next==L)exit(-1);LinkListp,q;intj=0;p=(LinkList)malloc(sizeof(LNode));q=(LinkList)malloc(sizeof(LNode));q->data=e;p=L;for(j=0;jvi;j++)〃使p为待更换结点的前一个结点，故应保证，删除第一个非头结点时i=0，以此类推p=p->next;q->next=p->next->next;p->next=q;q->flag=1; //设置新结点的访问位为1q->modify=0; //设置新结点的修改位为0return1;}intInsert_LNode(LinkList&L,inte)//在循环链表中插入新的结点，从L头结点开始依次向后插入{LinkListp,q;p=(LinkList)malloc(sizeof(LNode));q=(LinkList)malloc(sizeof(LNode));q->data=e;q->flag=1; //设置新结点的访问位为1q->modify=0; //设置新结点的修改位为0p=L;while(p->next!=L){p=p->next;}p->next=q;q->next=L;return1;}boolSearch_LinkList(LinkList&L,inte,int&i)〃找到链表L中内容为e的结点，并用i返回其位置，i=l表示第一个非头结点，依次类推{i=l;if(L->next==L)exit(-l);LinkListp;p=(LinkList)malloc(sizeof(LNode));if(!p)exit(-l);p=L->next;//p指向链表的第一个结点(非头结点)while(p!=L&&p->data!=e){p=p->next;i++;}if(p==L) //没有找到符合要求的结点returnfalse;returntrue;}voidSearch_LL_Flag(LinkList&L,int&i)〃用i返回第一个flag为0的结点的位置,i=1表示第一个非头结点，以此类推{i=1;LinkListp;p=(LinkList)malloc(sizeof(LNode));if(!p)exit(-1);p=L->next;while(p->flag!=0){p->flag=0; //修改访问标志位为0p=p->next;if(p==L) //跳过头结点p=p->next;i++;if(i==4) //跳过头结点i=1;//return1;voidSet_LL_Flag(LinkList&L,inti)//设置链表L中的序号为i的结点的flag标志为1；{LinkListp;p=(LinkList)malloc(sizeof(LNode));if(!p)exit(-1);p=L->next;if(i==1)p->flag=1;if(i==2){p=p->next;p->flag=1;}if(i==3){p=p->next;p=p->next;p->flag=1;}}intSearch_LL_ModifyClock(LinkList&L,int&modify_num)〃找到改进的CLOCK算法所需要淘汰的页，用modify_num返回其位置{modify_num=1;if(L->next==L)exit(-1);LinkListp;p=(LinkList)malloc(sizeof(LNode));if(!p)exit(-1);p=L->next; //p指向链表的第一个结点(非头结点)while(p!=L) 〃第一轮扫描A=0并且M=0的结点{if(p->flag==0&&p->modify==0)break;//找到p=p->next;modify_num++;}if(p==L){modify_num=1;p=L->next;while(p!=L) 〃第二轮扫描A=0并且M=1的结点，同时修改访问过的结点的访问位为0{if(p->flag!=0)p->flag=0;elseif(p->modify==1)break;p=p->next;modify_num++;}}if(p==L){modify_num=1;p=L->next;while(p!=L) 〃第三轮扫描A=0并且M=0的结点{if(p->flag==0&&p->modify==0)break;p=p->next;modify_num++;}if(p==L){modify_num=1;p=L->next;while(p!=L) 〃第四轮扫描A=0并且M=1的结点{if(p->flag!=0)p->flag=0;elseif(p->modify==1)break;p=p->next;modify_num++;}}}return1;}voidSet_LL_modify(LinkList&L,inti)//设置链表L中的序号为i的结点的modify标志为1；{LinkListp;p=(LinkList)malloc(sizeof(LNode));if(!p)exit(-1);p=L->next;if(i==0)p->modify=1;if(i==1){p=p->next;p->modify=1;}if(i==2){p=p->next;p=p->next;p->modify=1;}}intDestroyLinkList(LinkList&L) //删除链表，并释放链表空间{LinkListp,q;p=(LinkList)malloc(sizeof(LNode));if(!p)exit(-1);q=(LinkList)malloc(sizeof(LNode));if(!q)exit(-1);p=L->next;while(p!=L){q=p->next;free(p);p=q;}free(q);return1;}////////////////////////////////////////////////////////////////对队列的一些操作intInitQueue(LinkQueue&Q) //队列初始化{Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));if(!Q.front)exit(-1);Q.front->next=NULL;return1;}intEnQueue(LinkQueue&Q,inte) //插入元素e为Q的新的队尾元素{QueuePtrp;p=(QueuePtr)malloc(sizeof(QNode));if(!p)exit(-1);p->data=e;p->next=NULL;Q.rear->next=p;Q.rear=p;return1;}intDeQueue(LinkQueue&Q,int&e)//若队列不空，则删除Q的队头元素，用e返回其值{if(Q.front==Q.rear)return-1;QueuePtrp;p=(QueuePtr)malloc(sizeof(QNode));p=Q.front->next;e=p->data;Q.front->next=p->next;if(Q.rear==p)Q.rear=Q.front;free(p);return1;}boolSearchQueue(LinkQueue&Q,inte,int&i)//寻找队列Q中结点data域等于e的结点，并用i返回其在Q中的位置{i=1;if(Q.front==Q.rear)exit(-1);QueuePtrp;p=(QueuePtr)malloc(sizeof(QNode));if(!p)exit(-1);p=Q.front->next;//p指向队列的第一个节点(非头结点)while(p!=NULL&&p->data!=e){p=p->next;i++;}if(!p)returnfalse;returntrue;}intDelMid_Queue(LinkQueue&Q,int&e) //删除Q的中间元素，并用e返回其值{if(Q.front==Q.rear)return-1;QueuePtrp;p=(QueuePtr)malloc(sizeof(QNode));if(!p)exit(-1);p=Q.front->next;e=p->next->data;p->next=p->next->next;return1;}intDestroyQueue(LinkQueue&Q) //删除队列并释放空间{while(Q.front){Q.rear=Q.front->next;free(Q.front);Q.front=Q.rear;}return1;}//////////////////////////////////////////////////////////////intmax1(inta,intb,intc)//返回a,b,c中的最大值{if(a<b)a=b;if(a<c)a=c;returna;}intgetnum(inta,intb) //用b返回元素a在被引用数列中的下一个位置{for(;b<ref_size;b++){if(a==ref[b])break;}returnb;}voidORA() /////////////最佳置换算法{SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_INTENSITY|FOREGROUND_RED);cout<<"\n***********************最佳置换算法SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_INTENSITYIFOREGROUND_INTENSITY);〃设置字体颜色为白色inti,j;intnum_0,num_1,num_2,num_max;intinterrupt_num=0;//num_0=num_1=num_2=0;for(i=0;i<phy_size;i++)//前三个数进内存phy[i]=ref[i];for(i=0;i<phy_size;i++) //输出最初的三个数cout<<phy[i]<<"\t";cout<<endl;for(j=phy_size;j<ref_size;j++){SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_INTENSITY|FOREGROUND_INTENSITY);if(!(ref[j]==phy[0]||ref[j]==phy[1]||ref[j]==phy[2]))//若产生缺页中断，选择最久不会被使用的页被替换{num_0=getnum(phy[0],j+1);num_1=getnum(phy[1],j+1);num_2=getnum(phy[2],j+1);num_max=max1(num_0,num_1,num_2);if(num_0==num_max)phy[0]=ref[j];elseif(num_1==num_max)phy[1]=ref[j];elseif(num_2==num_max)phy[2]=ref[j];interrupt_num++;SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_INTENSITYIFOREGROUND_BLUE);〃设置字体为蓝色}coutvv"进入页："vvref[j]vvendl;

for(i=0;i<phy_size;i++) //输出内存状态cout<<phy[i]<<"\t";cout<<endl<<endl;}SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_INTENSITY|FOREGROUND_GREEN);coutvv"最佳置换算法缺页中断次数："vvinterrupt_numvvendl;//以绿色字体输出中断次数interrupt[0]=((float)interrupt_num/20.0)*100.0;}/////////////////////////////////////////////////////////////////////////////////////////////////////voidRAND() /////////////随机置换算法{SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGRO<<endl;UND_INTENSITY|FOREGROUND_RED);cout<<"\n***********************随机置换算法<<endl;If彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_INTENSITY|FOREGROUND_INTENSITY);inti,j,temp;intinterrupt_num=0;//num_0=num_1=num_2=0;Sleep(1000);srand(time(NULL)); //设置时间种子for(i=0;i<phy_size;i++)phy[i]=ref[i];for(i=0;i<phy_size;i++)cout<<phy[i]<<"\t";cout<<endl;for(j=phy_size;j<ref_size;j++){SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_INTENSITY|FOREGROUND_INTENSITY);if(!(ref[j]==phy[0]||ref[j]==phy[1]||ref[j]==phy[2])) //产生缺页中断，随机选择页被替换{temp=rand()%3;//cout<<temp<<endl;phy[temp]=ref[j];interrupt_num++;SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_INTENSITY|FOREGROUND_BLUE);

}coutvv"进入页："vvref[j]vvendl;for(i=0;i<phy_size;i++)cout<<phy[i]<<"\t";cout<<endl<<endl;}SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_INTENSITY|FOREGROUND_GREEN);coutvv"随机置换算法缺页中断次数："vvinterrupt_numvvendl;//以绿色字体输出中断次数interrupt[1]=((float)interrupt_num/20.0)*100.0;}///////////////////////////////////////////////////////////////////////////////////////////////voidFIFO(){SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGRO出置换算法UND_INTENSITY|FOREGROUND_RED);coutvv"\n***********************先进先出置换算法SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_INTENSITY|FOREGROUND_INTENSITY);LinkQueueL;QueuePtrp;inti,j,e,m;intinterrupt_num=0;InitQueue(L);for(i=0;ivphy_size;i++){EnQueue(L,ref[i]);}p=(QueuePtr)malloc(sizeof(QNode));p=L.front->next;for(j=0;p!=NULL&&jvphy_size;j++)〃前三个数进内存{coutvvp->datavv"\t";p=p->next;}coutvvendl;for(i=phy_size;ivref_size;i++){SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_INTENSITY|FOREGROUND_INTENSITY);

if(!SearchQueue(L,ref[i],m))//产生缺页中断，选择最先进入的页被替换{DeQueue(L,e);//cout<<e<<endl;EnQueue(L,ref[i]);interrupt_num++;SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_INTENSITY|FOREGROUND_BLUE);}coutvv"进入页:"vvref[i]vvendl;p=L.front->next;for(j=0;p!=NULL&&j<phy_size;j++){cout<<p->data<<"\t";p=p->next;}cout<<endl<<endl;}SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_INTENSITY|FOREGROUND_GREEN);coutvv"先进先出置换算法缺页中断次数："vvinterrupt_numvvendl;//以绿色字体输出中断次数interrupt[2]=((float)interrupt_num/20.0)*100.0;free(p);DestroyQueue(L);}////////////////////////////////////////////////////////////////////////////////////////////////voidLRU() /////////最近最久未使用算法{SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_INTENSITY|FOREGROUND_RED);coutvv"\n**********************最近最久未使用置换算法coutvv"\n**********************最近最久未使用置换算法vvendl;vvendl;If彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、intQNode_num=0;SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_INTENSITY|FOREGROUND_INTENSITY);LinkQueueL;QueuePtrp;inti,j,e;intinterrupt_num=0;InitQueue(L);for(i=0;ivphy_size;i++)EnQueue(L,ref[i]);}p=(QueuePtr)malloc(sizeof(QNode));p=L.front->next;for(j=0;p!=NULL&&j<phy_size;j++){cout<<p->data<<"\t";p=p->next;}cout<<endl;for(i=phy_size;i<ref_size;i++){SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_INTENSITY|FOREGROUND_INTENSITY);if(!SearchQueue(L,ref[i],QNode_num)) //产生缺页中断，选择最“老”的页面被替换{DeQueue(L,e);//cout<<e<<endl;EnQueue(L,ref[i]);interrupt_num++;SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_INTENSITY|FOREGROUND_BLUE);}elseif(QNode_num==1)//如果接下来是内存中的第一个，则将它移到最后一个，即标志为最近使用的页{EnQueue(L,ref[i]);DeQueue(L,e);}elseif(QNode_num==2)//如果接下来是内存中的第二个，则将它删除并在队列尾部添加相同元素，即标志为最近使用的页{DelMid_Queue(L,e);EnQueue(L,e);}coutvv"进入页:"vvref[i]vvendl;p=L.front->next;for(j=0;p!=NULL&&j<phy_size;j++)//输出内存状况cout<<p->data<<"\t";p=p->next;}cout<<endl<<endl;}SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_INTENSITY|FOREGROUND_GREEN);coutvv"最近最久未使用置换算法缺页中断次数："vvinterrupt_numvvendl;//以绿色字体输出中断次数interrupt[3]=((float)interrupt_num/20.0)*100.0;DestroyQueue(L);free(p);}/////////////////////////////////////////////////////////////////////////////////////////////////////voidCLOCK(){SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_INTENSITY|FOREGROUND_RED);coutvv"\n***********************CLOCK置换算法*************************"vvendl;SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_INTENSITY|FOREGROUND_INTENSITY);intinterrupt_num=0;inti;intLNode_hit_num=0; //标记带内存中与带进入页面相同的页面的位置intLNode_flag_num=0; //标记访问位为0的页面在内存中的位置LinkListL;CreatList(L);LinkListp;p=(LinkList)malloc(sizeof(LNode));for(i=0;ivphy_size;i++){Insert_LNode(L,ref[i]);}if(L->next==L)exit(-1);p=L->next;for(;p!=L;p=p->next){coutvvp->datavv"\t";//p->flag=1;}coutvvendl;p=L->next;while(p!=L)cout<<"A:"<<p->flag<<"\t";p=p->next;}cout<<endl<<endl;for(i=phy_size;i<ref_size;i++){SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_INTENSITY|FOREGROUND_INTENSITY);if(!Search_LinkList(L,ref[i],LNode_hit_num)){Search_LL_Flag(L,LNode_flag_num);〃找到第一个flag标志为0的结点，其序号记录在LNode_flag_num中LNode_flag_num--;Exchange_LNode(L,ref[i],LNode_flag_num);〃将链表L中序号为LNode_flag_num的结点替换为内容为ref[i]的结点interrupt_num++;SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_INTENSITY|FOREGROUND_BLUE);}elseSet_LL_Flag(L,LNode_hit_num);coutvv"进入页:"vvref[i]vvendl;p=L->next;for(;p!=L;p=p->next){cout<<p->data<<"\t";//p->flag=1;}cout<<endl;p=L->next;while(p!=L){cout<<"A:"<<p->flag<<"\t";p=p->next;}cout<<endl<<endl;}SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_INTENSITY|FOREGROUND_GREEN);cout<<"CLOCK置换算法缺页中断次数:"<<interrupt_num<<endl; //以绿色字体输出中断次数interrupt[4]=((float)interrupt_num/20.0)*100.0;DestroyLinkList(L);//free(L);}////////////////////////////////////////////////////////////////////////////////////////////////voidModified_Clock(){SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_INTENSITY|FOREGROUND_RED);cout<<"\n*******************改进的CLOCK置换算法*************************"<<endl;SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_INTENSITY|FOREGROUND_INTENSITY);intinterrupt_num=0;inti,temp;intLNode_hit_num=0;intLNode_flag_num=0;intLNode_modify_num=0;LinkListL;CreatList(L);LinkListp;p=(LinkList)malloc(sizeof(LNode));for(i=0;i<phy_size;i++){Insert_LNode(L,ref[i]);}if(L->next==L)exit(-1);p=L->next;for(;p!=L;p=p->next){cout<<p->data<<"\t\t";//p->flag=1;}cout<<endl;Sleep(1000);srand(time(NULL)); //设置时间种子temp=rand()%3;coutvv"修改页(