2023年面置換算法實驗報告2

頁面置換算法

實驗報告進入頁：15TOC\o"1-5"\h\z161815進入頁：工6161815進入頁?19191817進入頁：19191820進入頁：18191820進入頁：19191820進入頁：20222120進入頁：22>22120最佳置換算法缺頁申斷次數(shù)：7隨機置換算法131215進入頁：13131215進入頁：15161215進入頁：15181215進入頁：19161917進入頁：19161920隨機置換算法缺頁中斷次數(shù)：12…*?*??*先進先出置換算法TOC\o"1-5"\h\z131215進入頁：13131215進入頁：15121516進入頁：15151618進入頁：16151618進入頁：19TOC\o"1-5"\h\z18191?進入頁：19191720進入頁：22222120先進先出置換算法缺頁申斷次數(shù)：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置換算法缺頁中斷次數(shù)：8改進的CLOCK置換算法*官改頁（內(nèi)存中序首）:115A：1M：0A：1M：1A：1M：0進入頁；13131215修改頁（內(nèi)存中序號）：1A：1M：0A：1M：1fi：lM：0進入頁：15161215修改頁（內(nèi)存中序號）：A：1M:0A：02M：1fi：lM：1進入頁?15161815修改頁（內(nèi)存中序號）?2A：0M：0A：1M：0A：1M：1進入頁：16161815修改頁（內(nèi)存中序號）：2A：1M：0A：1M：0A：1M：1頁：191917修改頁（內(nèi)存中序號）：。A：1M：1fi：lM：015A：0M：1?人頁：19191?20修改頁（內(nèi)存中序號）：1A：1M：1A：0M：1A：1M：01人頁：19191820修改頁（內(nèi)存中序號）：1A：1M：1A：1M：1A：1M：0進入頁：22212022修改頁（內(nèi)存中序號）：2A：0M：0A：1M：0A：1M：1改進的CLOCK置換算法缺頁中斷次數(shù)：9總結(jié)：缺頁率最佳置換35%隨機置換60%先進先出置換50Z最近最久未使用置換45%CLOCK置換40Z改進CLOCK置換45%[Pressanykeytocontinue,九、實驗結(jié)果分析：1、最佳置換算法效果最佳不管在那組數(shù)據(jù)中，最佳置換算法的效果都是最佳的，旦都會比其它算法的性能高出不少。但通過課堂上的學(xué)習(xí)，我們知道這只是一種抱負化算法，但事實上卻難于實現(xiàn)，故重要用于算法評價參照。2、算法的性能總是最不好的這是由于算法每次總是從所有頁面中挑一個置換出去,但我們知道頁面的訪問存在著局部性的原理，并不是的,因此它的性能較差。3、最近最久未使用算法的性能較好。相較于先進先出和兩種clock算法，最近最久未使用算法的性能略好，我們測試一、實驗?zāi)康模涸O(shè)計和實現(xiàn)最佳置換算法、置換算法、先進先出置換算法、最近最久未使用置換算法、簡樸Clock置換算法及改善型Clock置換算法；通過支持頁面訪問序列發(fā)生實現(xiàn)有關(guān)算法的測試及性能比較。二、實驗內(nèi)容：?虛擬內(nèi)存頁面總數(shù)為N,頁號從0到N—1?物理內(nèi)存由M個物理塊組成?頁面訪問序列串是一個整數(shù)序列，整數(shù)的取值范圍為0到N—1。頁面訪問序列串中的每個元素p表達對頁面P的一次訪問?頁表用整數(shù)數(shù)組或結(jié)構(gòu)數(shù)組來表達□符合局部訪問特性的生成算法.擬定虛擬內(nèi)存的尺寸N,工作集的起始位置p,工作集中包含的頁數(shù)e,工作集移動率m(每解決m個頁面訪問則將起始位置P+1),以及一個范圍在0和1之間的值t；.生成m個取值范圍在p和p+e間的數(shù)，并記錄到頁面訪問序列串中；.生成一個數(shù)r,0WrW1;.假如r<I,則為p生成一個新值，否則p=(p+1)modN;.假如想繼續(xù)加大頁面訪問序列串的長度，請返回第2步，否則結(jié)束。三、實驗環(huán)境：操作系統(tǒng):Windows7的數(shù)據(jù)規(guī)模相對較小，相信假如采用更大規(guī)模的數(shù)據(jù),其優(yōu)勢會更加明顯。當(dāng)從課堂上我們知道要想在實際的應(yīng)用中實現(xiàn)本算法，用軟件的方法速度太慢,影響程序執(zhí)行效率，假如采用硬件方法實現(xiàn)，則需要增長大量的硬件設(shè)備。4、先進先出與clock算法的性能基本相同這是由于兩種c1ock算法遍歷鏈表采用的就是FIFO的方法，而改善的c1ock算法相比于簡樸clock算法的優(yōu)勢重要體現(xiàn)在會根據(jù)是否被修改善行選擇，以減少寫回所花費的時間。十、實驗總結(jié)：這次實驗總體難度不是很大，需要實現(xiàn)的算法數(shù)R雖然不少，但基本思緒較為相似，因此實現(xiàn)起來也并不是十分困難。通過完畢這次實驗，除了加深了我對幾種策略的理解，鍛煉了我的編程能力，另一個巨大的收獲就是了解了一些生成測試數(shù)據(jù)的方法。為了使我們的測試數(shù)據(jù)更貼近現(xiàn)實，我們引入了工作集的概念,并根據(jù)實際使用情況的特點設(shè)計出盡也許符合實際情況的數(shù)生成方案。通過閱讀課件再加上自己的理解，我了解了老師的設(shè)計思緒，感覺這個思緒極其巧妙，設(shè)計中用到的方法和體現(xiàn)出的很多思想值得我們學(xué)習(xí)。十一、程序清單：#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()//產(chǎn)生具有局部特性的數(shù)列(?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。//定義隊列數(shù)據(jù)結(jié)構(gòu)?intdata;?structQNode*next;}QNode,*QueuePtr;typedefstruct{QueuePtrfront;。?！^指針QueuePtrrea尾指針}LinkQueue；〃定義鏈表結(jié)點typedefstructLNode°//定義循環(huán)鏈表數(shù)據(jù)結(jié)構(gòu)I?intdata;?intflag；“//訪問位intmodify;。//修改位estructLNode*nexi;}LNode,*LinkList;//////////////////////////////////////////////////////////////////////////對循環(huán)鏈表的一些操作intCrcatList(LinkList&L)〃創(chuàng)建循環(huán)帶有頭結(jié)點的鏈表(L=(LinkList)malloc(sizeof(LNode));if(!L)exit(-l);&L->next=L;L—>f1ag=0;returnintExchange_LNode(LinkList&L,inte,inti)〃將鏈表L中序號為i的結(jié)點替換為內(nèi)容為e的結(jié)點(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為待更換結(jié)點的前一個結(jié)點，故應(yīng)保證，刪除第一個非頭結(jié)點時i=0,以此類推p=p->next;q->next=p->next->next；p->next=q;oq—>flag=l?//設(shè)立新結(jié)點的訪問位為1?q->modify=0;〃設(shè)立新結(jié)點的修改位為0?return1;)intInsert_LNode(LinkList&L,inte)//在循環(huán)鏈表中插入新的結(jié)點,從L頭結(jié)點開始依次向后插入{?>LinkListp,q;叩二(LinkList)ma1loc(sizeof(LNode))；q=(LinkList)maHoc(sizeof(LNode))；?q->data=e;oq->flag=l；。。//設(shè)立新結(jié)點的訪問位為1q->modify=0；。//設(shè)立新結(jié)點的修改位為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中內(nèi)容為e的結(jié)點，并用i返回其位置，i=l表達第一個非頭結(jié)點，依次類推(i=l；?if(L->next==L)exit(-1);LinkListp;p=(LinkList)mal1oc(sizeof(LNode));?if(!p)exit(-1)；p=L->next：W/p指向鏈表的第一個結(jié)點(非頭結(jié)點)while(p!=L&&p->data!=e)p=p->next；i++；0)°if(p==L)//沒有找到符合規(guī)定的結(jié)點oreturnfalse;?returntrue；)voidSearch_LL_Flag(LinkList&Ljnt&i)〃用i返回第一個flag為0的結(jié)點的位置，i=1表達第一個非頭結(jié)點，以此類推(i=l；oLinkListp;p=(LinkList)mal1oc(sizeof(LNode));if(!p)exit(-l)；p=L->next;?while(p->f1ag!=())(。叩,flag=0//修改訪問標(biāo)志位為0叩=p?>next;ooif(p==L)00//跳過頭結(jié)點9p=p->next；◎i++；oif(i==4)//跳過頭結(jié)點。i=l;01?//return1；voidSet_LL_Flag(LinkList&L,inti)?！ㄔO(shè)立鏈表L中的序號為i的結(jié)點的flag標(biāo)志為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指向鏈表的第一個結(jié)點(非頭結(jié)點)-while(p!=L)//第一輪掃描A=0并且M=()的結(jié)點oif(p—>f1ag==0&&p->modify==0)。break;?！ㄕ抑羖joP=p->next;“modify_num++;)if(p==L)(wTiodify_num=1；p=L->nexl；。while(p!=L)。〃第二輪掃描A=()并且M=1的結(jié)點，同時修改訪問過的結(jié)點的訪問位為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)?！ǖ谌啋呙鐰=0并且M=0的結(jié)點°{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的結(jié)點oo|。if(p->f1ag!=0)gp->f1ag=O;?e1seif(p—>modify==l)obreak;。，p=p->next；。modify_num++;軟件：aVC++6.0四、實驗設(shè)計：本實驗包含六種算法，基本內(nèi)容相差不太，在實現(xiàn)方面并沒有用統(tǒng)一的數(shù)據(jù)結(jié)構(gòu)實現(xiàn)，而是根據(jù)不同算法的特點用不同的數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)：1、最佳置換和置換所需操作不多，用整數(shù)數(shù)組模擬內(nèi)存實現(xiàn)；2、先進先出置換和最近最久未使用置換具有隊列的特性，故用隊列模擬內(nèi)存來實現(xiàn)；3、CLOCK置換和改善的CLOCK置換具有循環(huán)隊列的特性,故用循環(huán)隊列模擬內(nèi)存實現(xiàn)；4、所有算法都是采用整數(shù)數(shù)組來模擬頁面訪問序列。五、數(shù)據(jù)結(jié)構(gòu)設(shè)計：E-國yemianzhihuanclasses：□七LinkQueueQfrontQrear飛LNodeQdata“l(fā)agQmodifyQnext飛QNodeqdataqnext〃頁面訪問序列數(shù)組：intref[rejsize];//內(nèi)存數(shù)組：intphy[phy_size];return1；)voidSet_LL_modify(LinkList&L,inti)?！ㄔO(shè)立鏈表L中的序號為i的結(jié)點的modify標(biāo)志為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中結(jié)點data域等于e的結(jié)點，并用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指向隊列的第一個節(jié)點(非頭結(jié)點)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在被引用數(shù)列中的下一個位置?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);//設(shè)立字體顏色為白色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++)〃前三個數(shù)進內(nèi)存&phyLi]=ref[i]；for(i=0；i<phy_size;i++)。//輸出最初的三個數(shù)?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])>//若產(chǎn)生缺頁中斷，選擇最久不會被使用的頁被替換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。。?！癴(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);〃設(shè)立字體為藍色)coutvv"進入頁："<<ref[j]<<endl;

ofor(i=0；i<phy_size;i++)。//輸出內(nèi)存狀態(tài)“，cout<<phgcout?end1?endl;}。SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_INTENSITY|FOREGROUND_GREEN);cout?"最佳置換算法缺頁中斷次數(shù):n?interrupt_num?endl;//以綠色字體輸出中斷次數(shù)。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));?！?設(shè)立時間種子?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]))//產(chǎn)生缺頁中斷，選擇頁被替換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"置換算法缺頁中斷次數(shù):"vvinteitupt_num?end1；。。//以綠色字體輸出中斷次數(shù)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))；//隊列數(shù)據(jù)結(jié)構(gòu)定義：typcdefstructQNode//定義隊列數(shù)據(jù)結(jié)構(gòu)(intdata;◎structQNode*next;}QNode,*QueuePtr；typedefstruct(QucuePtrfront?//頭指針oQueuePtrrear：。。。//尾指針)LinkQueue；〃定義鏈表數(shù)據(jù)結(jié)構(gòu)typedefstructLNode//定義循環(huán)鏈表數(shù)據(jù)結(jié)構(gòu)(?intdata;Mmflag*//訪問位?intmodify產(chǎn)。〃修改位structLNode*next;)LNode,*LinkList;op=L.front->next;for(j=0;p!=NULL&&j<phy_size;j++)//前三個數(shù)進內(nèi)存(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))。//產(chǎn)生缺頁中斷，選擇最先進入的頁被替換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”先進先出置換算法缺頁中斷次數(shù):"<<interrupt_num?end1;//以綠色字體輸出中斷次數(shù)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))?！óa(chǎn)生缺頁中斷,選擇最“老”的頁面被替換oDeQueue(L,e);//cout?e<<end1;

000000interrupt_num++00interrupt_num++；。SetConso1eTextAttribute(GetStdHandle(STD.OUTPUT_HANDLE),FOREGR0UND」NTENSITY|FOREGROUND_BLUE);)elseif(QNode_num==l)〃假如接下來是內(nèi)存中的第一個，則將它移到最后一個，即標(biāo)志為最近使用的頁(gEnQueue(L,ref[iJ);。。DeQueue(L,e);。}◎elseif((^?4℃10_仲11)==2)。//假如接下來是內(nèi)存中的第二個，則將它刪除，并在隊列尾部添加相同元素，即標(biāo)志為最近使用的頁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++)。//輸出內(nèi)存狀況°{。。cout?p->data<<"\t"；000p=p->next;°)cout<<endl<<end1;°}aSetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND」NTENSITY|FOREGROUND_GREEN);cout<<"最近最久未使用置換算法缺頁中斷次數(shù)："<<interrupt_num?end1；。//以綠色字體輸出中斷次數(shù)?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?〃標(biāo)記帶內(nèi)存中與帶進入頁面相同的頁面的位置intLNode_flag_num=();?！?biāo)記訪問位為。的頁面在內(nèi)存中的位置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標(biāo)志為0的結(jié)點,其序號記錄在LNode_flag_num中。LNode_flag_num—；Exchange_LNode(L,ref[i],LNode_flag_num)；//將鏈表L中序號為LNode_flag_num的結(jié)點替換為內(nèi)容為ref[i]的結(jié)點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置換算法缺頁中斷次數(shù)："?interrupl_num?endl;。//以綠色字體輸出中斷次數(shù)?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))；//設(shè)立時間種子?temp=rand()%3；acout<<"修改頁(內(nèi)存中序號):"<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；)六、重要函數(shù)說明:-日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()〃產(chǎn)生具有局部特性的數(shù)列；2、intExchange_LNode(LinkList&L,inte,inli)//將鏈表L中序號為i的結(jié)點替換為內(nèi)容為e的結(jié)點；3^boolSearch_LinkList(LinkList&L,inte,inl&i)〃找到鏈表L中內(nèi)容為e的結(jié)點，并用i返回其位置，i=l表達第一個非頭結(jié)點，依次類推；4、voidSearch_LL_F1ag(LinkLisl&L,int&i)//用i返回第一個f1ag為0的結(jié)點的位置,i=1表達第?個非頭結(jié)點，以此類推：5、voidSet_LL_F1ag(LinkList&L,inti)〃設(shè)立鏈表L中的序號為i的結(jié)點的flag標(biāo)志為1;6^intSearch_LL_ModifyClock(LinkList&L,inl&modify_num)〃找到改善的CLOCK算法所需要淘汰的頁，用modify_num返回其位置:8cout?end1；Sleep(lOOO)；。srand(time(NULL));?！ㄔO(shè)立時間種子otemp=rand()%3；?cout<<"修改頁(內(nèi)存中序號):,,?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置換算法缺頁中斷次數(shù):"Winterrupt_num?end1；?！ㄒ跃G色字體輸出中斷次數(shù)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”******北京交通大學(xué)--計科1104(進修生)■一房皓一13410801***********\n\n"<<endl；set_ra