頁面置換算法實驗報告

頁面置換算法

實驗報告、實驗目的：設計和實現最佳置換算法、隨機置換算法、先進先出置換算法、最近最久未使用置換算法、簡單Clock置換算法及改進型Clock置換算法；通過支持頁面訪問序列隨機發(fā)生實現有關算法的測試及性能比較。二、 實驗內容：虛擬內存頁面總數為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；如果想繼續(xù)加大頁面訪問序列串的長度,請返回第2步,否則結束。三、 實驗環(huán)境：操作系統：Windows7軟件：VC++6.0四、實驗設計：本實驗包含六種算法,基本內容相差不太,在實現方面并沒有用統一的數據結構實現,而是根據不同算法的特點用不同的數據結構來實現：1、 最佳置換和隨機置換所需操作不多,用整數數組模擬內存實現；2、 先進先出置換和最近最久未使用置換具有隊列的特性,故用隊列模擬內存來實現；3、 CLOCK置換和改進的CLOCK置換具有循環(huán)隊列的特性,故用循環(huán)隊列模擬內存實現；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〃定義循環(huán)鏈表數據結構{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()〃實現最佳置換算法，包括判斷頁面是否在內存中、頁面進內存、輸出內存狀態(tài)等內容;〃隨機置換算法〃先進先出算法〃最近最久未使用算法11〃隨機置換算法〃先進先出算法〃最近最久未使用算法12、 voidFIFO()13、 voidLRU()實現最近最久未使用算法的思想是：判斷待進入內存的頁面，如果與內存中的第一個頁面相同，則將它移到最后一個，即標志為最近使用的頁；如果與內存中的第二個頁面相同，則將它刪除，并在隊列尾部添加相同元素，即標志為最近使用的頁;14、voidCLOCK() 〃實現CLOCK算法15、 voidModified_Clock()//實現改進的CLOCK算法16、intmain() 〃主函數，調用實現各算法的6個主要函數，并輸出各算法的缺頁率。七、實驗問題回答:1、 FIFO算法是否比隨機置換算法優(yōu)越？答：FIFO算法比隨機置換算法優(yōu)越，但優(yōu)勢并不明顯。2、 LRU算法比FIFO算法優(yōu)越多少？答：LRU算法FIFO算法的效率要高5%-10%，有理論知識可知，頁面訪問序列具有局部性，而FIFO算法并不符合實際情況。3、 LRU算法和Optimal算法有何差距？答：LRU算法是所有算法中效率最接近Optimal算法的算法，由理論知識可知，Optimal算法是理想的算法，現實中幾乎不可能實現，只能作為一種測評標準，LRU算法是效率較高的可實現置換算法，但其硬件要求較高，如果規(guī)模較小，則略顯麻煩。4、 Clock算法和LRU算法有何差距？答：Clock算法和LRU算法從結果看來差距不大，Clock算法是使用軟件的方式實現LRU算法中硬件的功能，從而在執(zhí)行效率上會稍遜色些。八、實驗過程結果截圖:實驗結果截圖測評一：頁面訪問序列:12 15 13 151B17 16 18 18 171E18 18 21 201G22 21 23 21

總結；缺頁率LI35^u1隨機萱換00k--■*進先岀置換砂i頁近最久未使用置換40^t^LOGK置喚45x戰(zhàn)進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田衛(wèi)：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(xù)=ik進的CLOCK置換算去缺頁中斷次數：9缺仄窣隨機置換60X*進先岀置換看近最久未使用置換45x置換k進CLOC1｛置換45x[Pressanykeytocontinue—九、實驗結果分析:1、 最佳置換算法效果最佳不論在那組數據中，最佳置換算法的效果都是最好的，且都會比其它算法的性能高出不少。但通過課堂上的學習，我們知道這只是一種理想化算法，但實際上卻難于實現，故主要用于算法評價參照。2、 隨機算法的性能總是最不好的這是由于隨機算法每次總是從所有頁面中隨機挑一個置換出去，但我們知道頁面的訪問存在著局部性的原理，并不是隨機的，因此它的性能較差。3、 最近最久未使用算法的性能較好相較于先進先出和兩種clock算法，最近最久未使用算法的性能略好，我們測試的數據規(guī)模相對較小，相信如果采用更大規(guī)模的數據，其優(yōu)勢會更加明顯。當從課堂上我們知道要想在實際的應用中實現本算法，用軟件的方法速度太慢，影響程序執(zhí)行效率，如果采用硬件方法實現，則需要增加大量的硬件設備。4、 先進先出與clock算法的性能基本相同這是由于兩種clock算法遍歷鏈表采用的就是FIFO的方法，而改進的clock算法相比于簡單clock算法的優(yōu)勢主要體現在會根據是否被修改進行選擇，以減少寫回所花費的時間。十、實驗總結：這次實驗總體難度不是很大，需要實現的算法數目雖然不少，但基本思路較為相似，因此實現起來也并不是十分困難。通過完成這次實驗，除了加深了我對幾種策略的理解，鍛煉了我的編程能力，另一個巨大的收獲就是了解了一些生成測試數據的方法。為了使我們的測試數據更貼近現實，我們引入了工作集的概念，并根據實際使用情況的特點設計出盡可能符合實際情況的隨機數生成方案。通過閱讀課件再加上自己的理解，我了解了老師的設計思路，感覺這個思路極其巧妙，設計中用到的方法和體現出的很多思想值得我們學習。十一、程序清單：#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//定義循環(huán)鏈表數據結構{intdata;intflag; //訪問位intmodify; //修改位structLNode*next;}LNode,*LinkList;//////////////////////////////////////////////////////////////////////////對循環(huán)鏈表的一些操作intCreatList(LinkList&L)〃創(chuàng)建循環(huán)帶有頭結點的鏈表{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)//在循環(huán)鏈表中插入新的結點，從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指向隊列的第一個節(jié)點(非頭結點)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++) //輸出內存狀態(tà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"修改頁(