2023年面置换算法实验报告2

页面置换算法

实验报告进入页：15TOC\o"1-5"\h\z161815进入页：工6161815进入页।19191817进入页：19191820进入页：18191820进入页：19191820进入页：20222120进入页：22>22120最佳置换算法缺页申断次数：7随机置换算法131215进入页：13131215进入页：15161215进入页：15181215进入页：19161917进入页：19161920随机置换算法缺页中断次数：12…*™*™™*先进先出置换算法TOC\o"1-5"\h\z131215进入页：13131215进入页：15121516进入页：15151618进入页：16151618进入页：19TOC\o"1-5"\h\z18191?进入页：19191720进入页：22222120先进先出置换算法缺页申断次数：1。"***************"最近最久未使用置换算法MX""""-fXMMX13_1215进入页：13121513进入页：15131615进入页：15TOC\o"1-5"\h\z131615进入页:15161815进入页：16181516题人页：19161719进入页；19172019先入页：1901819进入页:22TOC\o"1-5"\h\z212022进入页：15161215A：1A：0A：1进入页：15161815A：0A：1A：1进入页：16LG1815A：1A：1A：1页:19A：11917A：115A：019页:19页:191?A：020A：1卷入页:191820A：卷入页:191822A：0页:2021A：120A：1进入页,222221A：120n：iCLOCK置换算法缺页中断次数：8改进的CLOCK置换算法*官改页（内存中序首）:115A：1M：0A：1M：1A：1M：0进入页；13131215修改页（内存中序号）：1A：1M：0A：1M：1fi：lM：0进入页：15161215修改页（内存中序号）：A：1M:0A：02M：1fi：lM：1进入页।15161815修改页（内存中序号）«2A：0M：0A：1M：0A：1M：1进入页：16161815修改页（内存中序号）：2A：1M：0A：1M：0A：1M：1页：191917修改页（内存中序号）：。A：1M：1fi：lM：015A：0M：1•人页：19191?20修改页（内存中序号）：1A：1M：1A：0M：1A：1M：01人页：19191820修改页（内存中序号）：1A：1M：1A：1M：1A：1M：0进入页：22212022修改页（内存中序号）：2A：0M：0A：1M：0A：1M：1改进的CLOCK置换算法缺页中断次数：9总结：缺页率最佳置换35%随机置换60%先进先出置换50Z最近最久未使用置换45%CLOCK置换40Z改进CLOCK置换45%[Pressanykeytocontinue,九、实验结果分析：1、最佳置换算法效果最佳不管在那组数据中，最佳置换算法的效果都是最佳的，旦都会比其它算法的性能高出不少。但通过课堂上的学习，我们知道这只是一种抱负化算法，但事实上却难于实现，故重要用于算法评价参照。2、算法的性能总是最不好的这是由于算法每次总是从所有页面中挑一个置换出去,但我们知道页面的访问存在着局部性的原理，并不是的,因此它的性能较差。3、最近最久未使用算法的性能较好。相较于先进先出和两种clock算法，最近最久未使用算法的性能略好，我们测试一、实验目的：设计和实现最佳置换算法、置换算法、先进先出置换算法、最近最久未使用置换算法、简朴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<I,则为p生成一个新值，否则p=(p+1)modN;.假如想继续加大页面访问序列串的长度，请返回第2步，否则结束。三、实验环境：操作系统:Windows7的数据规模相对较小，相信假如采用更大规模的数据,其优势会更加明显。当从课堂上我们知道要想在实际的应用中实现本算法，用软件的方法速度太慢,影响程序执行效率，假如采用硬件方法实现，则需要增长大量的硬件设备。4、先进先出与clock算法的性能基本相同这是由于两种c1ock算法遍历链表采用的就是FIFO的方法，而改善的c1ock算法相比于简朴clock算法的优势重要体现在会根据是否被修改善行选择，以减少写回所花费的时间。十、实验总结：这次实验总体难度不是很大，需要实现的算法数R虽然不少，但基本思绪较为相似，因此实现起来也并不是十分困难。通过完毕这次实验，除了加深了我对几种策略的理解，锻炼了我的编程能力，另一个巨大的收获就是了解了一些生成测试数据的方法。为了使我们的测试数据更贴近现实，我们引入了工作集的概念,并根据实际使用情况的特点设计出尽也许符合实际情况的数生成方案。通过阅读课件再加上自己的理解，我了解了老师的设计思绪，感觉这个思绪极其巧妙，设计中用到的方法和体现出的很多思想值得我们学习。十一、程序清单：#include<iostrcam>inc1ude<windows.h>inc1ude<time.h>include<ma11oc.h>inc1ude<conio.h>usingnamespacestd：defineref_size20definephy_size3ntref[ref_size]；floatinterrupt[6]={0.0};//intref[ref_size]={0};intphy[phy_size];///h///h/1/1/m/h////////////////////////〃/〃/〃/mmnn//voidset_rand_num()//产生具有局部特性的数列(®cout<<”页面访问序列:"«endl；intp=12;®inte=4；®intm=4;ointi=0;intj=0;intn=0;0doub1et=0.6;nttemp;®for(i=0;i<m；i++,j++)leep(1000*i);srand(time(NULL));otemp=rand()%e+p;oref[j]=temp;^cout«ref;0}for(n=0;n<4;n++)。(oSleep(I000*n);®srand(time(NULL));◎doub1er=(double)(rand()%l0)/10.0;。//cout«r«end1;oif(r<t)p=p+int(l0*r);oelse9p=(p+l)%20;for(i=0;i<m；i++,j++)0{aS1eep(1000*i);srand(time(NULL));o®temp=rand()%e+p；。ref[j]=temp;cout«ref[j]«H";0)}cout«endl;)〃/〃〃///〃///////////////////////////////////〃〃//"〃//////typedefstructQNode。//定义队列数据结构®intdata;®structQNode*next;}QNode,*QueuePtr;typedefstruct{QueuePtrfront;。。〃头指针QueuePtrrea尾指针}LinkQueue；〃定义链表结点typedefstructLNode°//定义循环链表数据结构I®intdata;®intflag；“//访问位intmodify;。//修改位estructLNode*nexi;}LNode,*LinkList;//////////////////////////////////////////////////////////////////////////对循环链表的一些操作intCrcatList(LinkList&L)〃创建循环带有头结点的链表(L=(LinkList)malloc(sizeof(LNode));if(!L)exit(-l);&L->next=L;L—>f1ag=0;returnintExchange_LNode(LinkList&L,inte,inti)〃将链表L中序号为i的结点替换为内容为e的结点(if(L->next=L)exit(-1);®LinkListp,q;ointj=0;p=(LinkList)mal1oc(sizeof(LNode))；oq=(LinkList)malloc(sizeof(LNode));q->data=e;P=L;for(j=0；j<i;j++)//使p为待更换结点的前一个结点，故应保证，删除第一个非头结点时i=0,以此类推p=p->next;q->next=p->next->next；p->next=q;oq—>flag=l?//设立新结点的访问位为1®q->modify=0;〃设立新结点的修改位为0®return1;)intInsert_LNode(LinkList&L,inte)//在循环链表中插入新的结点,从L头结点开始依次向后插入{«>LinkListp,q;叩二(LinkList)ma1loc(sizeof(LNode))；q=(LinkList)maHoc(sizeof(LNode))；®q->data=e;oq->flag=l；。。//设立新结点的访问位为1q->modify=0；。//设立新结点的修改位为0°P=L;©while(p->next!=L)(®p=p->next；)6p->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(-1);LinkListp;p=(LinkList)mal1oc(sizeof(LNode));®if(!p)exit(-1)；p=L->next：W/p指向链表的第一个结点(非头结点)while(p!=L&&p->data!=e)p=p->next；i++；0)°if(p==L)//没有找到符合规定的结点oreturnfalse;»returntrue；)voidSearch_LL_Flag(LinkList&Ljnt&i)〃用i返回第一个flag为0的结点的位置，i=1表达第一个非头结点，以此类推(i=l；oLinkListp;p=(LinkList)mal1oc(sizeof(LNode));if(!p)exit(-l)；p=L->next;®while(p->f1ag!=())(。叩,flag=0//修改访问标志位为0叩=p・>next;ooif(p==L)00//跳过头结点9p=p->next；◎i++；oif(i==4)//跳过头结点。i=l;01»//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)。叩—>f]ag=];if(i==2)(°P=p->next；op->flag=l;Ioif(i==3)gp=p->next;。叩二p->next;gp->f1ag=1;}1intSearch_LL_ModifyClock(LinkList&L,int&modify_num)//找到改善的CLOCK算法所需要淘汰的页，用modify_num返回其位置modify_num=1;®if(L->next==L)exit(-l);LinkListp;p二(LinkList)maHoc(sizeof(LNode));if(!p)exit(—1);®p=L->next;“/p指向链表的第一个结点(非头结点)-while(p!=L)//第一轮扫描A=0并且M=()的结点oif(p—>f1ag==0&&p->modify==0)。break;。〃找至ljoP=p->next;“modify_num++;)if(p==L)(wTiodify_num=1；p=L->nexl；。while(p!=L)。〃第二轮扫描A=()并且M=1的结点，同时修改访问过的结点的访问位为0。｛°。if(p->f1ag!=0)o©p->flag=O;。。吒1seif(p—>modify==1)obreak;p=p->next;modify_num++;oif(p==L)(®modify_num=l；op=L->next;while(p!=L)。〃第三轮扫描A=0并且M=0的结点°{gif(p->fIag==0&&p->modify==0)。®break;ap=p->next;®»®modify_num++;°}oif(p==L)°(。modify_num=l；。p=L->next；8owhile(p!=L)°〃第四轮扫描A=0并且M=1的结点oo|。if(p->f1ag!=0)gp->f1ag=O;®e1seif(p—>modify==l)obreak;。，p=p->next；。modify_num++;软件：aVC++6.0四、实验设计：本实验包含六种算法，基本内容相差不太，在实现方面并没有用统一的数据结构实现，而是根据不同算法的特点用不同的数据结构来实现：1、最佳置换和置换所需操作不多，用整数数组模拟内存实现；2、先进先出置换和最近最久未使用置换具有队列的特性，故用队列模拟内存来实现；3、CLOCK置换和改善的CLOCK置换具有循环队列的特性,故用循环队列模拟内存实现；4、所有算法都是采用整数数组来模拟页面访问序列。五、数据结构设计：E-国yemianzhihuanclasses：□七LinkQueueQfrontQrear飞LNodeQdata“lagQmodifyQnext飞QNodeqdataqnext〃页面访问序列数组：intref[rejsize];//内存数组：intphy[phy_size];return1；)voidSet_LL_modify(LinkList&L,inti)。〃设立链表L中的序号为i的结点的modify标志为1;(LinkListp;®p=(LinkList)malloc(sizeof(LNode));if(!p)exit(-1);叩=L—>next;if(i=0)。p->modify=1;if(i==1)6(p=p->next;p->modify=1；}if(i==2)°(d9p=p->next；°p=p->next;*p->modify=1;intDestroyLinkList(LinkList&L)g〃删除链表，并释放链表空间{LinkListp,q;。p二(LinkList)ma1loc(sizeof(LNode));if(!p)exit(-l);q=(LinkList)mal1oc(sizeof(LNode));if(!q)exit(-1)；p=L->next;whi1e(p!=L)(®q=p->next;free(p);叩=q;I。free(q);®return1;)//////////////////////////////////////////////III///////////〃〃对队列的一些操作intIniiQueue(LinkQueue&Q)。〃队歹U初始化(Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));®if(!Q.front)exit(-l);aQ.front—>next=NULL；weturn1；)intEnQueue(LinkQueue&Q,inte)//插入元素e为Q的新的队尾元素(◎QueuePtrp;叩二(QueuePtr)malloc(sizeof(QNode));oif(!p)exit(-1);op->data=e；p->next=NULL;oQ.rear->next=p;»Q.rear=p；return1；)intDeQueue(LinkQueue&Q,int&e)//若队列不空，则删除Q的队头元素，用e返回其值(if(Q.front==Q.rear)rcturn-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;IboolSearchQueue(LinkQueue&Q,inte,int&i)〃寻找队列Q中结点data域等于e的结点，并用i返回其在Q中的位置(®i=1;®if(Q.front==Q.rear)exit(-l);QueuePtrp；p=(QueuePtr)ma11oc(sizeof(QNode));if(!p)exit(-l)；p=Q.front—>next;。//p指向队列的第一个节点(非头结点)whi1e(p!=NULL&&p->data!=e)(0p=p—>next;oi++；o}。if(!P)o®returnfaIse;eturntrue;1intDelMid_Queue(LinkQueue&Q,int&e)。//删除Q的中间元素，并用e返回其值if(Q.front==Q.rear)return-1;QueuePtrp；叩二(QueuePtr)malloc(sizeof(QNode));if(!p)exit(-l);p=Q.fronl->nexl;®e=p->next->data;®p->next=p->next->next;return1;}intDestroyQueue(LinkQueue&Q)的〃删除队列并释放空间(owhile(Q.front)(sQ.rear=Q.front->next；Mee(Q.front)；Q.front=Q.rear;°)oreturn1；)//////////////////////////////////////////////////////////////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()//////〃//〃/最佳置换算法ISetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND」NTENSITY|F0REGROUND_RED);coutvV"\n*****************秘***55c最佳置换算法*************************”<<end1;®SetConso1eTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUNDJNTENSITY|FOREGROUND_INTENSITY);//设立字体颜色为白色ftinti,j；®intnum_0,num_l,num_2,num_max；intinterrupt_num=0；//num_0=num_l=num_2=0;for(i=();i<phy_size;i++)〃前三个数进内存&phyLi]=ref[i]；for(i=0；i<phy_size;i++)。//输出最初的三个数®cout<<phy[i]«n\t";cout«end1；ofor(j=phy_size;j<ref_size;j++)(^SetConsoIeTexlAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND」NTENSITY|FOREGROUNDJNTENSITY);if(!(ref[j]==phy[O]||ref|j]=phy[1]||refLj]=phy[2])>//若产生缺页中断，选择最久不会被使用的页被替换00|onum_0=gctnum(phy[O],j+1);。num_1=getnum(phy[1],j+l);°。num_2=getnum(phy[2],j+l);“num_max=max1(num_0,num_l,num_2)；»®if(num_0==num_max)。。叩hy[O]=ref[j];else。。。“f(num_l==num_max)。Phy[1]=ref[j];。。照Ise。f(num_2==num_max)。。。phyl2]=ref[j];。。interrupt_num++;o。SetConsoleTextAttribute(GetSldHand1e(STD_OUTPUT_HANDLE),FOREGROUND」NTENSITYIFOREGROUND_BLUE);〃设立字体为蓝色)coutvv"进入页："<<ref[j]<<endl;

ofor(i=0；i<phy_size;i++)。//输出内存状态“，cout<<phgcout«end1«endl;}。SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_INTENSITY|FOREGROUND_GREEN);cout«"最佳置换算法缺页中断次数:n«interrupt_num«endl;//以绿色字体输出中断次数。intcrrupt[O]=((f1oat)intcrrupt_num/20.0)*100.0;)/////////////////////////////////////////////////////////////////////////////////////////////////////voidRAND()。/////////////置换算法SetConsoleTextAltribute(GetStdHandle(STD_OUTPUTHANDLE),FOREGROUND_INTENSITY|FOREGROUND_RED)；®cout<<\n*****************®cout<<\n*****************芳***55s置换算法************火***SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND,INTENSITY|FOREGROUND」NTENSITY);inti,j,temp;intinterrupt_num=0;0//num_0=num_l=num_2=0;Sleep(1000);srand(time(NULL));。“/设立时间种子®for(i=0；i<phy_size；i++)8Phy[i]=ref[i]；®for(i=O;i<phy_size；i++)cout«phy[i]«11\t"；cout<<end1;for(j=phy_size;j<ref_size；j++)etConso1eTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),F0REGROUNDJNTENSITY|FOREGROUND」NTENSITY)；if(!(ref[j]==Phy[0]llreffj]==phy[1]I|ref[j]==phy[2]))//产生缺页中断，选择页被替换00|。。temperand()%3;//cout«temp<<endl；8Phy[temp]=ref[j];»interrupt_num++;SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT.HANDLE),FOREGROUND_INTENSITY|FOREGROUND_BLUE);°)ocoutV<“进入页:“V<ref[j]vVendl;for(i=0;i<phy_size;i++)。cout«phy[i]<<"\tu；。»cout<<end1<<end1;®SetConso1eTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND」NTENSITYIFOREGROUND_GREEN);coutvv"置换算法缺页中断次数:"vvinteitupt_num«end1；。。//以绿色字体输出中断次数4»interrupt[l]=((float)interrupt_num/20.0)*100.0;)////////////////////////////////UHHU///////////////////////////////////////////////////////voidFIFO()(»SetConso1eTextAttribute(GetStdHandie(STD_OUTPUT—HANDLE),FOREGROUNDJNTENSITYIFOREGROUND_RED);cout«"\n***********************先进先出置换算法*************************"«endl：oSetConso1eTextAttribute(GetStdHandie(STD_OUTPUT_HANDLE),FOREGROUND」NTENSITY|FOREGR0UNDJNTENSITY)；LinkQueueL;QueucPtrp;inti,j,e,m;intintcrrupt_num=0;InitQueue(L);®fbr(i=0;i<phy_size;i++)。(oEnQueue(L,ref[i])；0)®p=(QueuePtr)mal1oc(sizeof(QNode))；//队列数据结构定义：typcdefstructQNode//定义队列数据结构(intdata;◎structQNode*next;}QNode,*QueuePtr；typedefstruct(QucuePtrfront?//头指针oQueuePtrrear：。。。//尾指针)LinkQueue；〃定义链表数据结构typedefstructLNode//定义循环链表数据结构(»intdata;Mmflag*//访问位»intmodify产。〃修改位structLNode*next;)LNode,*LinkList;op=L.front->next;for(j=0;p!=NULL&&j<phy_size;j++)//前三个数进内存(scout«p—>data<<n\r;®p=p->next；}cout«end1;®for(i=phy_size;i<ref_size;i++)(SetConsoleTextAttribute(GetStdHandle(STD_0UTPUT_HANDLE),FOREGROUND_1NTENSITYIFOREGROUND_INTENSITY);®if(!SearchQueue(L,ref[il，m))。//产生缺页中断，选择最先进入的页被替换00|。。。DeQueue(L,e);//cout<<e<<end1；o®EnQueue(L,ref[i])；。。interrupt_num++；。SetConsoleTextAttribute(GetStdHand1e(STD_OUTPUT_HANDLE),FOREGROUND_INTENSITY|FOREGROUND.BLUE);°!。cout<<"进入页:"vvref[i]«end1；。p=L.front—>next；for(j=0;p!=NULL&&j<phy_size；j++)cout<<p->data«"\t"；叩二p—>next;00}8cout«endl«endl;)SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUNDINTENSITY|FOREGROUNDGREEN);0coutvv”先进先出置换算法缺页中断次数:"<<interrupt_num«end1;//以绿色字体输出中断次数ainterrupt[21=((float)interrupt_num/20.0)*100.0;free(p)；DestroyQueue(L);}////////////////////////////////////////////////////////////////////////////////////////////////voidLRU()。。。//〃//〃/最近最久未使用算法{SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_INTENSITY|FOREGROUND_RED);cout<v"\n**********************最近最久未使用置换算法**********************”<〈endl;intQNode_num=0;SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_INTENSITY|FOREGROUNDJNTENSITY);®LinkQueueL;®QueuePtrp;®intij,e;intinterrupt_num=O;InitQueue(L);®fbr(i=O;i<phy_size；i++)(EnQueue(L,ref[i]);。}p二(QueuePtr)malloc(sizeof(QNode))；叩二L.front->next;for(j=0;p!=NULL&&j<phy_size•j++)°(ocout«p->data«"\tM;°p=p->next;®cout<<end1；for(i=phy_size;i<ref_size;i++)°{。SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),F0REGROUND_INTENSITYIFOREGR0UNDJNTENS1TY);if(!SearchQueue(L,ref[i],QNode_num))。〃产生缺页中断,选择最“老”的页面被替换oDeQueue(L,e);//cout«e<<end1;

000000interrupt_num++00interrupt_num++；。SetConso1eTextAttribute(GetStdHandle(STD.OUTPUT_HANDLE),FOREGR0UND」NTENSITY|FOREGROUND_BLUE);)elseif(QNode_num==l)〃假如接下来是内存中的第一个，则将它移到最后一个，即标志为最近使用的页(gEnQueue(L,ref[iJ);。。DeQueue(L,e);。}◎elseif((^?4℃10_仲11)==2)。//假如接下来是内存中的第二个，则将它删除，并在队列尾部添加相同元素，即标志为最近使用的页00|aoDelMid_Queue(L,e);。EnQueue(L,e);00}coutVv"进入页："«ref[i]<<endl;®p=L.front->next;°for(j=O;p!=NULL&&jvphy_size;j++)。//输出内存状况°{。。cout«p->data<<"\t"；000p=p->next;°)cout<<endl<<end1;°}aSetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND」NTENSITY|FOREGROUND_GREEN);cout<<"最近最久未使用置换算法缺页中断次数："<<interrupt_num«end1；。//以绿色字体输出中断次数®interrupt[3]=((float)interrupt_num/20.0)*100.0?◎DestroyQueue(L);ofree(p);)/////////////////////////////////////////////////////////////////////////////////////////////////////voidCLOCK()(oSetConso1eTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUNDJNTENSITY|FOREGROUND_RED)；ocout«"\n***********************cL0CK置换算法*************************”Vvend].。SetConsoleTextAttribute(GetStdHand1e(STD_OUTPUT_HANDLE),FOREGROUND_INTENSITY|FOREGROUND_INTENSITY)；®intinterrupt_num=0;»inti;AnlLNode_hit_num=0?〃标记带内存中与带进入页面相同的页面的位置intLNode_flag_num=();。〃标记访问位为。的页面在内存中的位置LinkListL;®CreatList(L);LinkListp;叩=(LinkList)malloc(sizeof(LNode));for(i=0;i<phy_size;i++)gInsert_LNode(L,ref[i])；if(L->next==L)exit(—1);叩=口>next;for(;p!=L;p=p->next)®cout<<p->data«"\tM;o//p->flag=l;)cout«end1;®p=L->next;whi1e(p!=L)6(8cout«nA：”<vp—>f1agp=p->next;°)ocout«endl«endl;for(i=phy_size;i<rsize;i++)SetConsoleTextAttribute(GetStdHand1e(STD_OUTPUT_HANDLE),FOREGROUND_INTENSITY|FOREGROUNDJNTENSITY);oif(!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++；oSetConsoleTextAttribute(GetStdHand1e(STD_OUTPUT_HANDLE),FOREGROUND_INTENSITY|FOREGROUND_BLUE)；°)®else。Set_LL_F1ag(L,LNode_hit_num);。coutV<"进入页:"<Vref[i]«endl；op=L->next；。for(;p!=L;p=p->next)do{ocout«p—>data«'*\t”;。//p->flag=l;1*cout«end1;op=L->next;owhi1e(p!=L)0(。。cout<<"A:"<<p—>f1ag«"\t'*;op=p->next;)ocout«endl«endl;oSetConso1eTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_INTENSITY|FOREGROUND_GREEN)；cout<<"CLOCK置换算法缺页中断次数："«interrupl_num«endl;。//以绿色字体输出中断次数®interrupt[4]=((float)interrupt_num/20.0)*100.0；。estroyLinkList(L);//free(L);)/////////////////////III////////////////////////////////////////////////////////////////////////voidModifiedC1ock()oSetConso1eTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUNDJNTENSITY|FOREGR0UND_RED)；℃out«”\n*******************改善的cLOCK置换算法*************************n«end1；SetConsoleTextAttribute(GetStdHandle(STD.OUTPUT_HANDLE),FOREGROUNDJNTENSITY|FOREGROUND_INTENSITY);®intintcrrupt_num=0；»inti,temp;intLNode_hit_num=0;intLNode_flag_num=0;®intLNode_modify_num=0；®LinkListL；®CreatList(L);®LinkListp；p=(LinkList)ma1loc(sizeof(LNode));for(i=0;i<phy_size；i++)(3Insert_LNode(L,ref]i]);°)*if(L—>next==L)exit(-l)；p=L->next;®for(;p!=L；p=p->next)(®cout<<p—>data<<H\t\tH;V/p->f1ag=l;}cout«endl；f1eep(1000);osrand(time(NULL))；//设立时间种子®temp=rand()%3；acout<<"修改页(内存中序号):"<Vtemp<Vend1;。Set_LL_modify(L,temp);p=L—>next;hi1e(p!=L){“cout«,,A:,,«p->flag«"\tM:M<<p->modify«M\tH;。。p=p->next;0)acout«end1<<end1;ofor(i=phy_size;i<ref_size;i++)SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND」NTENSITYIFOREGROUNDJNTENSITY);oif(!Search_LinkList(L,refEi],LNode_hit_num))00{。Search_LL_ModifyClock(L,LNode_modify_num);。。“/Search_LL_Flag(L,LNode_flag_num);oLNodc_modify_num;。Exchange_LNode(L,reffi],LNode_modify—num);。interrupt_num++；。®SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUNDJNTENSITY|FOREGR0UND_BLUE)；00}else。。Set_LL_F1ag(L,LNode_hit_num);MSe(ConsoleTextAttribute(Ge(StdHand1e(STD_OUTPUT_HANDLE),FOREGROUND_INTENSITY|FOREGROUND」NTENSITY)；ocout<v"进入页：'*«ref[i]<<endl；0p=L->next：«for(;p!=L；p=p->next)cout<<p->data«"\t\tM;//p—>flag=l；)六、重要函数说明:-日Globals9CLOCKQ.CreatList(LinkList&L]♦DelMid_Queue(LinkQueue&Q,int&e)9DeQueue(LinkQueue&Q,int&e)DestroyLinkList(LinkList&L)DestroyQueuefLinkQueue&Q].EnQueue(LinkQueue&Q,inte)QExchange_LNode(LinkList&Linte,inti)QFIFOQgetnum(inta,intb]InitQueuefLinkQueue&Q)0lnsert_LNode(LinkList&Linte)QLRU0".main。.maxi(inta,intb,intc)Modified_ClockOQORAQ令RANDQSearch_LinkList(UnkUst&L,inte,int&i)令Search二LL_Flag|LinkList&L,int&i]Search_LL_ModifyClock(LinkUst&LintSmodifynum)SearchQueue(LinkQueue&Q,inte,int&i)Set_LL_Flag(LinkList&Linti)Set_LL_modify(LinkList&L,inti]setrandnumQI、voidset_rand_num()〃产生具有局部特性的数列；2、intExchange_LNode(LinkList&L,inte,inli)//将链表L中序号为i的结点替换为内容为e的结点；3^boolSearch_LinkList(LinkList&L,inte,inl&i)〃找到链表L中内容为e的结点，并用i返回其位置，i=l表达第一个非头结点，依次类推；4、voidSearch_LL_F1ag(LinkLisl&L,int&i)//用i返回第一个f1ag为0的结点的位置,i=1表达第•个非头结点，以此类推：5、voidSet_LL_F1ag(LinkList&L,inti)〃设立链表L中的序号为i的结点的flag标志为1;6^intSearch_LL_ModifyClock(LinkList&L,inl&modify_num)〃找到改善的CLOCK算法所需要淘汰的页，用modify_num返回其位置:8cout«end1；Sleep(lOOO)；。srand(time(NULL));。〃设立时间种子otemp=rand()%3；©cout<<"修改页(内存中序号):,,«temp«endl;。Set_LL_modify(L,temp);oop=L->next;owhile(p!=L)。cout<<"A:n«p->f1ag<<"\tM："«p->modify<<"\t"；p=p->next；00}cout«endl<<end1;°)-SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGR0UND_INTENSITY|FOREGROUND_GREEN);ocoutVv”改善的CLOCK置换算法缺页中断次数:"Winterrupt_num«end1；。〃以绿色字体输出中断次数nterrupt[5]=((float)interrupt_num/20.0)*100.0;estroyLinkList(L);。//free(L)；)/uh//////11n/////////////////////////////1nun/uh/〃/〃〃////〃/////////////////////////intmain()cout«"\n\nn<<end1;ocoutVv"************************页面置换算法*****************************\n"«end1,coutvv”******北京交通大学--计科1104(进修生)■一房皓一13410801***********\n\n"<<endl；set_ra