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、最佳置換算法效果最佳不管在那組數據中，最佳置換算法的效果都是最佳的，旦都會比其它算法的性能高出不少。但通過課堂上的學習，我們知道這只是一種抱負化算法，但事實上卻難于實現(xiàn)，故重要用于算法評價參照。2、算法的性能總是最不好的這是由于算法每次總是從所有頁面中挑一個置換出去,但我們知道頁面的訪問存在著局部性的原理，并不是的,因此它的性能較差。3、最近最久未使用算法的性能較好。相較于先進先出和兩種clock算法，最近最久未使用算法的性能略好，我們測試一、實驗目的：設計和實現(xiàn)最佳置換算法、置換算法、先進先出置換算法、最近最久未使用置換算法、簡樸Clock置換算法及改善型Clock置換算法；通過支持頁面訪問序列發(fā)生實現(xiàn)有關算法的測試及性能比較。二、實驗內容：?虛擬內存頁面總數為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;.假如想繼續(xù)加大頁面訪問序列串的長度，請返回第2步，否則結束。三、實驗環(huán)境：操作系統(tǒng):Windows7的數據規(guī)模相對較小，相信假如采用更大規(guī)模的數據,其優(yōu)勢會更加明顯。當從課堂上我們知道要想在實際的應用中實現(xiàn)本算法，用軟件的方法速度太慢,影響程序執(zhí)行效率，假如采用硬件方法實現(xiàn)，則需要增長大量的硬件設備。4、先進先出與clock算法的性能基本相同這是由于兩種c1ock算法遍歷鏈表采用的就是FIFO的方法，而改善的c1ock算法相比于簡樸clock算法的優(yōu)勢重要體現(xiàn)在會根據是否被修改善行選擇，以減少寫回所花費的時間。十、實驗總結：這次實驗總體難度不是很大，需要實現(xiàn)的算法數R雖然不少，但基本思緒較為相似，因此實現(xiàn)起來也并不是十分困難。通過完畢這次實驗，除了加深了我對幾種策略的理解，鍛煉了我的編程能力，另一個巨大的收獲就是了解了一些生成測試數據的方法。為了使我們的測試數據更貼近現(xiàn)實，我們引入了工作集的概念,并根據實際使用情況的特點設計出盡也許符合實際情況的數生成方案。通過閱讀課件再加上自己的理解，我了解了老師的設計思緒，感覺這個思緒極其巧妙，設計中用到的方法和體現(xiàn)出的很多思想值得我們學習。十一、程序清單：#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°//定義循環(huán)鏈表數據結構I?intdata;?intflag；“//訪問位intmodify;。//修改位estructLNode*nexi;}LNode,*LinkList;//////////////////////////////////////////////////////////////////////////對循環(huán)鏈表的一些操作intCrcatList(LinkList&L)〃創(chuàng)建循環(huán)帶有頭結點的鏈表(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)//在循環(huán)鏈表中插入新的結點,從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)//沒有找到符合規(guī)定的結點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)?！ㄔO立鏈表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;?！ㄕ抑羖joP=p->next;“modify_num++;)if(p==L)(wTiodify_num=1；p=L->nexl；。while(p!=L)?！ǖ诙啋呙鐰=()并且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)?！ǖ谌啋呙鐰=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四、實驗設計：本實驗包含六種算法，基本內容相差不太，在實現(xiàn)方面并沒有用統(tǒng)一的數據結構實現(xiàn)，而是根據不同算法的特點用不同的數據結構來實現(xiàn)：1、最佳置換和置換所需操作不多，用整數數組模擬內存實現(xiàn)；2、先進先出置換和最近最久未使用置換具有隊列的特性，故用隊列模擬內存來實現(xiàn)；3、CLOCK置換和改善的CLOCK置換具有循環(huán)隊列的特性,故用循環(huán)隊列模擬內存實現(xiàn)；4、所有算法都是采用整數數組來模擬頁面訪問序列。五、數據結構設計：E-國yemianzhihuanclasses：□七LinkQueueQfrontQrear飛LNodeQdata“l(fā)agQmodifyQnext飛QNodeqdataqnext〃頁面訪問序列數組：intref[rejsize];//內存數組：intphy[phy_size];return1；)voidSet_LL_modify(LinkList&L,inti)?！ㄔO立鏈表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)?！牬鮑初始化(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指向隊列的第一個節(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在被引用數列中的下一個位置?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。。?！癴(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++)。//輸出內存狀態(tà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//定義循環(huán)鏈表數據結構(?intdata;Mmflag*//訪問位?intmodify產?！ㄐ薷奈籹tructLNode*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))?！óa生缺頁中斷,選擇最“老”的頁面被替換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=();?！擞浽L問位為。的頁面在內存中的位置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));?！ㄔO立時間種子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；?！ㄒ跃G色字體輸出中斷次數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