頁(yè)面置換算法實(shí)驗(yàn)報(bào)告

頁(yè)面置換算法

實(shí)驗(yàn)報(bào)告、實(shí)驗(yàn)?zāi)康模涸O(shè)計(jì)和實(shí)現(xiàn)最佳置換算法、隨機(jī)置換算法、先進(jìn)先出置換算法、最近最久未使用置換算法、簡(jiǎn)單Clock置換算法及改進(jìn)型Clock置換算法；通過(guò)支持頁(yè)面訪問(wèn)序列隨機(jī)發(fā)生實(shí)現(xiàn)有關(guān)算法的測(cè)試及性能比較。二、 實(shí)驗(yàn)內(nèi)容：虛擬內(nèi)存頁(yè)面總數(shù)為N,頁(yè)號(hào)從0到N-1物理內(nèi)存由M個(gè)物理塊組成?頁(yè)面訪問(wèn)序列串是一個(gè)整數(shù)序列，整數(shù)的取值范圍為0到N-1。頁(yè)面訪問(wèn)序列串中的每個(gè)元素p表示對(duì)頁(yè)面p的一次訪問(wèn)頁(yè)表用整數(shù)數(shù)組或結(jié)構(gòu)數(shù)組來(lái)表示口符合局部訪問(wèn)特性的隨機(jī)生成算法確定虛擬內(nèi)存的尺寸N,工作集的起始位置p,工作集中包含的頁(yè)數(shù)e，工作集移動(dòng)率m(每處理m個(gè)頁(yè)面訪問(wèn)則將起始位置p+1)，以及一個(gè)范圍在0和1之間的值t；生成m個(gè)取值范圍在p和p+e間的隨機(jī)數(shù)，并記錄到頁(yè)面訪問(wèn)序列串中；生成一個(gè)隨機(jī)數(shù)r,0WrW1；如果r<t,則為p生成一個(gè)新值，否則p=(p+1)modN；如果想繼續(xù)加大頁(yè)面訪問(wèn)序列串的長(zhǎng)度,請(qǐng)返回第2步,否則結(jié)束。三、 實(shí)驗(yàn)環(huán)境：操作系統(tǒng)：Windows7軟件：VC++6.0四、實(shí)驗(yàn)設(shè)計(jì)：本實(shí)驗(yàn)包含六種算法,基本內(nèi)容相差不太,在實(shí)現(xiàn)方面并沒(méi)有用統(tǒng)一的數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn),而是根據(jù)不同算法的特點(diǎn)用不同的數(shù)據(jù)結(jié)構(gòu)來(lái)實(shí)現(xiàn)：1、 最佳置換和隨機(jī)置換所需操作不多,用整數(shù)數(shù)組模擬內(nèi)存實(shí)現(xiàn)；2、 先進(jìn)先出置換和最近最久未使用置換具有隊(duì)列的特性,故用隊(duì)列模擬內(nèi)存來(lái)實(shí)現(xiàn)；3、 CLOCK置換和改進(jìn)的CLOCK置換具有循環(huán)隊(duì)列的特性,故用循環(huán)隊(duì)列模擬內(nèi)存實(shí)現(xiàn)；4、 所有算法都是采用整數(shù)數(shù)組來(lái)模擬頁(yè)面訪問(wèn)序列。五、數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì):-^yemianzhihuanclassesj-弋LinkQueue總frontfjrear-弋LNode識(shí)data0flag0modify識(shí)next-七QNode少data(?next〃頁(yè)面訪問(wèn)序列數(shù)組：intref[ref_size];〃內(nèi)存數(shù)組：intphy[phy_size];〃隊(duì)列數(shù)據(jù)結(jié)構(gòu)定義：typedefstructQNode〃定義隊(duì)列數(shù)據(jù)結(jié)構(gòu){intdata;structQNode*next;}QNode,*QueuePtr;typedefstruct{QueuePtrfront; 〃頭指針QueuePtrrear; 〃尾指針}LinkQueue;〃定義鏈表數(shù)據(jù)結(jié)構(gòu)typedefstructLNode〃定義循環(huán)鏈表數(shù)據(jù)結(jié)構(gòu){intdata;intflag; 〃訪問(wèn)位intmodify; 〃修改位structLNode*next;}LNode,*LinkList;六、主要函數(shù)說(shuō)明:-_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() 〃產(chǎn)生具有局部特性的隨機(jī)數(shù)列；2、 intExchange_LNode(LinkList&L,inte,inti)//將鏈表L中序號(hào)為i的結(jié)點(diǎn)替換為內(nèi)容為e的結(jié)點(diǎn)；3、 boolSearch_LinkList(LinkList&L,inte,int&i)//找到鏈表L中內(nèi)容為e的結(jié)點(diǎn)，并用i返回其位置，i=l表示第一個(gè)非頭結(jié)點(diǎn)，依次類推；4、 voidSearch_LL_Flag(LinkList&L,int&i"用i返回第一個(gè)flag為0的結(jié)點(diǎn)的位置,i=1表示第一個(gè)非頭結(jié)點(diǎn)，以此類推；5、 voidSet_LL_Flag(LinkList&L,inti)〃設(shè)置鏈表L中的序號(hào)為i的結(jié)點(diǎn)的flag標(biāo)志為1；6、 intSearch_LL_ModifyClock(LinkList&L,int&modify_num)〃找到改進(jìn)的CLOCK算法所需要淘汰的頁(yè)，用modify_num返回其位置；此函數(shù)根據(jù)書(shū)上給的思路，第一遍掃描A=0且M=0的頁(yè)面予以淘汰，若失敗，則進(jìn)行第二輪掃描A=0且M=1的頁(yè)面，第二輪掃描時(shí)將所有訪問(wèn)過(guò)的頁(yè)面的訪問(wèn)位A置0;若失敗則重復(fù)上述兩部；7、 voidSet_LL_modify(LinkList&L,inti)〃設(shè)置鏈表L中的序號(hào)為i的結(jié)點(diǎn)的modify標(biāo)志為1；8、boolSearchQueue(LinkQueue&Q,inte,int&i) 〃尋找隊(duì)列Q中結(jié)點(diǎn)data域等于e的結(jié)點(diǎn)，并用i返回其在Q中的位置；

9、9、intgetnum(inta,intb)〃用b返回元素a在被引用數(shù)列中的下一個(gè)位置10、voidORA()〃實(shí)現(xiàn)最佳置換算法，包括判斷頁(yè)面是否在內(nèi)存中、頁(yè)面進(jìn)內(nèi)存、輸出內(nèi)存狀態(tài)等內(nèi)容;〃隨機(jī)置換算法〃先進(jìn)先出算法〃最近最久未使用算法11〃隨機(jī)置換算法〃先進(jìn)先出算法〃最近最久未使用算法12、 voidFIFO()13、 voidLRU()實(shí)現(xiàn)最近最久未使用算法的思想是：判斷待進(jìn)入內(nèi)存的頁(yè)面，如果與內(nèi)存中的第一個(gè)頁(yè)面相同，則將它移到最后一個(gè)，即標(biāo)志為最近使用的頁(yè)；如果與內(nèi)存中的第二個(gè)頁(yè)面相同，則將它刪除，并在隊(duì)列尾部添加相同元素，即標(biāo)志為最近使用的頁(yè);14、voidCLOCK() 〃實(shí)現(xiàn)CLOCK算法15、 voidModified_Clock()//實(shí)現(xiàn)改進(jìn)的CLOCK算法16、intmain() 〃主函數(shù)，調(diào)用實(shí)現(xiàn)各算法的6個(gè)主要函數(shù)，并輸出各算法的缺頁(yè)率。七、實(shí)驗(yàn)問(wèn)題回答:1、 FIFO算法是否比隨機(jī)置換算法優(yōu)越？答：FIFO算法比隨機(jī)置換算法優(yōu)越，但優(yōu)勢(shì)并不明顯。2、 LRU算法比FIFO算法優(yōu)越多少？答：LRU算法FIFO算法的效率要高5%-10%，有理論知識(shí)可知，頁(yè)面訪問(wèn)序列具有局部性，而FIFO算法并不符合實(shí)際情況。3、 LRU算法和Optimal算法有何差距？答：LRU算法是所有算法中效率最接近Optimal算法的算法，由理論知識(shí)可知，Optimal算法是理想的算法，現(xiàn)實(shí)中幾乎不可能實(shí)現(xiàn)，只能作為一種測(cè)評(píng)標(biāo)準(zhǔn)，LRU算法是效率較高的可實(shí)現(xiàn)置換算法，但其硬件要求較高，如果規(guī)模較小，則略顯麻煩。4、 Clock算法和LRU算法有何差距？答：Clock算法和LRU算法從結(jié)果看來(lái)差距不大，Clock算法是使用軟件的方式實(shí)現(xiàn)LRU算法中硬件的功能，從而在執(zhí)行效率上會(huì)稍遜色些。八、實(shí)驗(yàn)過(guò)程結(jié)果截圖:實(shí)驗(yàn)結(jié)果截圖測(cè)評(píng)一：頁(yè)面訪問(wèn)序列:12 15 13 151B17 16 18 18 171E18 18 21 201G22 21 23 21

總結(jié)；缺頁(yè)率LI35^u1隨機(jī)萱換00k--■*進(jìn)先岀置換砂i頁(yè)近最久未使用置換40^t^LOGK置喚45x戰(zhàn)進(jìn)CLOCKS^457.1jPpessanykeytocontinueH測(cè)評(píng)二:n面訪問(wèn)序列:15 15 13 1516 1514 16 15 14 13 14 14 17 16 14 20 20 222Ba”佳萱換總結(jié)，缺貝率30x隨機(jī)置換40x先:井先出萱換45z最近最久未使用置喚35xclockW4^35X甘進(jìn)CLOCK置換35kPressanyJseytoicontinue測(cè)評(píng)三:頁(yè)面訪間序列:ia12ibuitisiuisibiy17iyzuiyin mmu22總結(jié):缺頁(yè)率”隹萱換35/C隨機(jī)直換60x先進(jìn)先岀置換50x頁(yè)近最久未使用置換45xCLOCK置換40X改講CLOC喟揉45xPressanykeytocontinue—實(shí)驗(yàn)過(guò)程截圖（注：只截取第三次測(cè)評(píng)，藍(lán)色字體表示產(chǎn)生缺頁(yè)中斷）于：咬衣懾二學(xué)朝愜作慈頁(yè)面^^^Debug^emidnzhihuan.exe- [=|叵|亠』n囪首扌年算［師“耳3CMKW耳耳JO<師“耳3CMKW耳耳JOC>：M師“耳卜n北京交通大學(xué)--計(jì)科“昶（注修土）--房?-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險(xiǎn)V瓦13\L2 12 15陡入頁(yè)?151G 12 15陡入頁(yè)匚15\L6 IS 15

肚人頁(yè)：15嚇 1R150H頁(yè)；161G 1815H頁(yè)；191?1817主二耳191?1820辻\頁(yè)：181?182B応5⑷1?1820肚人頁(yè):20Q2 2123H耳222221F=l丿4-嚴(yán).4〒午'1t234-3=-丄說(shuō)L、J土4嚴(yán)任且次異詁嗽以1爼認(rèn)姒：/~r隨機(jī)置按算法士13 12 15辻人貝：13 12 1E討兒耳151S 12 1E進(jìn)八幣1519 12 1G進(jìn)人耳191& 19 20陡機(jī)宣換算吃缺頁(yè)中斷伙數(shù)；12TOC\o"1-5"\h\z:KENJ（垃耳（耳沌NW迪：KENJ（垃耳N胃專三）井三總出曽扌奐官］；十KNKJCNNHKNKH耳K胃耳耳NJtJCNNHjCNW13 12 15進(jìn)入頁(yè):1313 12 15進(jìn)入頁(yè)；1512 15 16進(jìn)入頁(yè):151S 16 18進(jìn)入頁(yè):1615 1& 1S陡入頁(yè):燈TOC\o"1-5"\h\z18 19 ￡7田衛(wèi)：H19 17 26陡人貝：22Q2 21 2Q注進(jìn)先岀置換算法缺頁(yè)中斷枕數(shù)：10K“mx—KXXXKX最近最靈未使用置換算法UK—XXK—XXXK13 12陡入頁(yè).131512 1513肚入頁(yè)=1513 161513 16 15進(jìn)入耳1516 18 15進(jìn)入兀18 15 16進(jìn)入耳191A 17 19進(jìn)入頁(yè):1917 20 19進(jìn)入耳1?NU 1H 17進(jìn)入頁(yè)：22212022近最久天使圧置換算法缺頁(yè)中斷次數(shù)：空13 1215A：1 A：1ft：l進(jìn)入頁(yè)；13101215a：i fi：iA：1進(jìn)入頁(yè)；飾1f> 12ISA：1 A：0ft：l進(jìn)入頁(yè):15161815A：0 A：1ft：l辺入頁(yè)：16it ia15A：1 A：1ft:l

講人頁(yè)’1919 17A：1 A：1ISA：0進(jìn)入頁(yè)：1919 1?26A：1A：0A：1J曲入頁(yè)：1919 1826A：1A：1A：1進(jìn)入頁(yè).20222126A：1A：1進(jìn)入頁(yè)：22222126A：1A：1□MK直換算祛缺貝匚斷枕數(shù)：級(jí)**改違的CLOCK置換算法樓改頁(yè)（內(nèi)存中序呂）：1A：1 H：@ A：1 M：1ISA：iM：0進(jìn)入貝：13 「修改頁(yè)（內(nèi)存巾序號(hào)）；1A:1 N:tlfi:1 M:1 ft:1M:R甘.入.頁(yè)’15修改貝（內(nèi)存中號(hào)號(hào)）：2r：in-mr：mn：iisa：in：i辻入頁(yè)：飾16 丄& 15修改頁(yè)〔內(nèi)莊巾序號(hào)）；2A：nH:fifl：1M:Rfi:1進(jìn)入頁(yè)：1616 18 15修改貝（內(nèi)仔屮序號(hào)）：2觸丄 N詢 fis± M=0 AsiM：1Msl惟入頁(yè)：1919 17修改頁(yè)〔內(nèi)存屮序號(hào)）：?n：im：in：in：015f\-QM：1憧人貝：I?19 丄7於改頁(yè)（內(nèi)存中序號(hào)）：勺A：1 M：1 A：0 M：12BA：1M：0陡入頁(yè)；I?19 18陽(yáng)改頁(yè)（內(nèi)存中序號(hào)）：iP：1 M：1 A：1 M：120fi：lM：0憾入頁(yè)：22G1 20 22修改貝〔內(nèi)存屮序呂）:2m；on：iM：efi=±m(xù)=ik進(jìn)的CLOCK置換算去缺頁(yè)中斷次數(shù)：9缺仄窣隨機(jī)置換60X*進(jìn)先岀置換看近最久未使用置換45x置換k進(jìn)CLOC1｛置換45x[Pressanykeytocontinue—九、實(shí)驗(yàn)結(jié)果分析:1、 最佳置換算法效果最佳不論在那組數(shù)據(jù)中，最佳置換算法的效果都是最好的，且都會(huì)比其它算法的性能高出不少。但通過(guò)課堂上的學(xué)習(xí)，我們知道這只是一種理想化算法，但實(shí)際上卻難于實(shí)現(xiàn)，故主要用于算法評(píng)價(jià)參照。2、 隨機(jī)算法的性能總是最不好的這是由于隨機(jī)算法每次總是從所有頁(yè)面中隨機(jī)挑一個(gè)置換出去，但我們知道頁(yè)面的訪問(wèn)存在著局部性的原理，并不是隨機(jī)的，因此它的性能較差。3、 最近最久未使用算法的性能較好相較于先進(jìn)先出和兩種clock算法，最近最久未使用算法的性能略好，我們測(cè)試的數(shù)據(jù)規(guī)模相對(duì)較小，相信如果采用更大規(guī)模的數(shù)據(jù)，其優(yōu)勢(shì)會(huì)更加明顯。當(dāng)從課堂上我們知道要想在實(shí)際的應(yīng)用中實(shí)現(xiàn)本算法，用軟件的方法速度太慢，影響程序執(zhí)行效率，如果采用硬件方法實(shí)現(xiàn)，則需要增加大量的硬件設(shè)備。4、 先進(jìn)先出與clock算法的性能基本相同這是由于兩種clock算法遍歷鏈表采用的就是FIFO的方法，而改進(jìn)的clock算法相比于簡(jiǎn)單clock算法的優(yōu)勢(shì)主要體現(xiàn)在會(huì)根據(jù)是否被修改進(jìn)行選擇，以減少寫(xiě)回所花費(fèi)的時(shí)間。十、實(shí)驗(yàn)總結(jié)：這次實(shí)驗(yàn)總體難度不是很大，需要實(shí)現(xiàn)的算法數(shù)目雖然不少，但基本思路較為相似，因此實(shí)現(xiàn)起來(lái)也并不是十分困難。通過(guò)完成這次實(shí)驗(yàn)，除了加深了我對(duì)幾種策略的理解，鍛煉了我的編程能力，另一個(gè)巨大的收獲就是了解了一些生成測(cè)試數(shù)據(jù)的方法。為了使我們的測(cè)試數(shù)據(jù)更貼近現(xiàn)實(shí)，我們引入了工作集的概念，并根據(jù)實(shí)際使用情況的特點(diǎn)設(shè)計(jì)出盡可能符合實(shí)際情況的隨機(jī)數(shù)生成方案。通過(guò)閱讀課件再加上自己的理解，我了解了老師的設(shè)計(jì)思路，感覺(jué)這個(gè)思路極其巧妙，設(shè)計(jì)中用到的方法和體現(xiàn)出的很多思想值得我們學(xué)習(xí)。十一、程序清單：#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()//產(chǎn)生具有局部特性的隨機(jī)數(shù)列{coutvv"頁(yè)面訪問(wèn)序列："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//定義隊(duì)列數(shù)據(jù)結(jié)構(gòu){intdata;structQNode*next;}QNode,*QueuePtr;typedefstruct{QueuePtrfront; //頭指針QueuePtrrear; //尾指針}LinkQueue;//定義鏈表結(jié)點(diǎn)typedefstructLNode//定義循環(huán)鏈表數(shù)據(jù)結(jié)構(gòu){intdata;intflag; //訪問(wèn)位intmodify; //修改位structLNode*next;}LNode,*LinkList;//////////////////////////////////////////////////////////////////////////對(duì)循環(huán)鏈表的一些操作intCreatList(LinkList&L)〃創(chuàng)建循環(huán)帶有頭結(jié)點(diǎn)的鏈表{L=(LinkList)malloc(sizeof(LNode));if(!L)exit(-1);L->next=L;L->flag=0;return1;}intExchange_LNode(LinkList&L,inte,inti)//將鏈表L中序號(hào)為i的結(jié)點(diǎn)替換為內(nèi)容為e的結(jié)點(diǎn){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為待更換結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)，故應(yīng)保證，刪除第一個(gè)非頭結(jié)點(diǎn)時(shí)i=0，以此類推p=p->next;q->next=p->next->next;p->next=q;q->flag=1; //設(shè)置新結(jié)點(diǎn)的訪問(wèn)位為1q->modify=0; //設(shè)置新結(jié)點(diǎn)的修改位為0return1;}intInsert_LNode(LinkList&L,inte)//在循環(huán)鏈表中插入新的結(jié)點(diǎn)，從L頭結(jié)點(diǎn)開(kāi)始依次向后插入{LinkListp,q;p=(LinkList)malloc(sizeof(LNode));q=(LinkList)malloc(sizeof(LNode));q->data=e;q->flag=1; //設(shè)置新結(jié)點(diǎn)的訪問(wèn)位為1q->modify=0; //設(shè)置新結(jié)點(diǎn)的修改位為0p=L;while(p->next!=L){p=p->next;}p->next=q;q->next=L;return1;}boolSearch_LinkList(LinkList&L,inte,int&i)〃找到鏈表L中內(nèi)容為e的結(jié)點(diǎn)，并用i返回其位置，i=l表示第一個(gè)非頭結(jié)點(diǎn)，依次類推{i=l;if(L->next==L)exit(-l);LinkListp;p=(LinkList)malloc(sizeof(LNode));if(!p)exit(-l);p=L->next;//p指向鏈表的第一個(gè)結(jié)點(diǎn)(非頭結(jié)點(diǎn))while(p!=L&&p->data!=e){p=p->next;i++;}if(p==L) //沒(méi)有找到符合要求的結(jié)點(diǎn)returnfalse;returntrue;}voidSearch_LL_Flag(LinkList&L,int&i)〃用i返回第一個(gè)flag為0的結(jié)點(diǎn)的位置,i=1表示第一個(gè)非頭結(jié)點(diǎn)，以此類推{i=1;LinkListp;p=(LinkList)malloc(sizeof(LNode));if(!p)exit(-1);p=L->next;while(p->flag!=0){p->flag=0; //修改訪問(wèn)標(biāo)志位為0p=p->next;if(p==L) //跳過(guò)頭結(jié)點(diǎn)p=p->next;i++;if(i==4) //跳過(guò)頭結(jié)點(diǎn)i=1;//return1;voidSet_LL_Flag(LinkList&L,inti)//設(shè)置鏈表L中的序號(hào)為i的結(jié)點(diǎn)的flag標(biāo)志為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)〃找到改進(jìn)的CLOCK算法所需要淘汰的頁(yè)，用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指向鏈表的第一個(gè)結(jié)點(diǎn)(非頭結(jié)點(diǎn))while(p!=L) 〃第一輪掃描A=0并且M=0的結(jié)點(diǎn){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的結(jié)點(diǎn)，同時(shí)修改訪問(wèn)過(guò)的結(jié)點(diǎn)的訪問(wèn)位為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的結(jié)點(diǎn){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的結(jié)點(diǎn){if(p->flag!=0)p->flag=0;elseif(p->modify==1)break;p=p->next;modify_num++;}}}return1;}voidSet_LL_modify(LinkList&L,inti)//設(shè)置鏈表L中的序號(hào)為i的結(jié)點(diǎn)的modify標(biāo)志為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;}////////////////////////////////////////////////////////////////對(duì)隊(duì)列的一些操作intInitQueue(LinkQueue&Q) //隊(duì)列初始化{Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));if(!Q.front)exit(-1);Q.front->next=NULL;return1;}intEnQueue(LinkQueue&Q,inte) //插入元素e為Q的新的隊(duì)尾元素{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)//若隊(duì)列不空，則刪除Q的隊(duì)頭元素，用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)//尋找隊(duì)列Q中結(jié)點(diǎn)data域等于e的結(jié)點(diǎn)，并用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指向隊(duì)列的第一個(gè)節(jié)點(diǎn)(非頭結(jié)點(diǎn))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) //刪除隊(duì)列并釋放空間{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在被引用數(shù)列中的下一個(gè)位置{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);〃設(shè)置字體顏色為白色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++)//前三個(gè)數(shù)進(jìn)內(nèi)存phy[i]=ref[i];for(i=0;i<phy_size;i++) //輸出最初的三個(gè)數(shù)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]))//若產(chǎn)生缺頁(yè)中斷，選擇最久不會(huì)被使用的頁(yè)被替換{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);〃設(shè)置字體為藍(lán)色}coutvv"進(jìn)入頁(yè)："vvref[j]vvendl;

for(i=0;i<phy_size;i++) //輸出內(nèi)存狀態(tài)cout<<phy[i]<<"\t";cout<<endl<<endl;}SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_INTENSITY|FOREGROUND_GREEN);coutvv"最佳置換算法缺頁(yè)中斷次數(shù)："vvinterrupt_numvvendl;//以綠色字體輸出中斷次數(shù)interrupt[0]=((float)interrupt_num/20.0)*100.0;}/////////////////////////////////////////////////////////////////////////////////////////////////////voidRAND() /////////////隨機(jī)置換算法{SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGRO<<endl;UND_INTENSITY|FOREGROUND_RED);cout<<"\n***********************隨機(jī)置換算法<<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)); //設(shè)置時(shí)間種子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])) //產(chǎn)生缺頁(yè)中斷，隨機(jī)選擇頁(yè)被替換{temp=rand()%3;//cout<<temp<<endl;phy[temp]=ref[j];interrupt_num++;SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_INTENSITY|FOREGROUND_BLUE);

}coutvv"進(jìn)入頁(yè)："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"隨機(jī)置換算法缺頁(yè)中斷次數(shù)："vvinterrupt_numvvendl;//以綠色字體輸出中斷次數(shù)interrupt[1]=((float)interrupt_num/20.0)*100.0;}///////////////////////////////////////////////////////////////////////////////////////////////voidFIFO(){SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGRO出置換算法UND_INTENSITY|FOREGROUND_RED);coutvv"\n***********************先進(jì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++)〃前三個(gè)數(shù)進(jìn)內(nèi)存{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))//產(chǎn)生缺頁(yè)中斷，選擇最先進(jìn)入的頁(yè)被替換{DeQueue(L,e);//cout<<e<<endl;EnQueue(L,ref[i]);interrupt_num++;SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_INTENSITY|FOREGROUND_BLUE);}coutvv"進(jìn)入頁(yè):"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"先進(jìn)先出置換算法缺頁(yè)中斷次數(shù)："vvinterrupt_numvvendl;//以綠色字體輸出中斷次數(shù)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)) //產(chǎn)生缺頁(yè)中斷，選擇最“老”的頁(yè)面被替換{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)//如果接下來(lái)是內(nèi)存中的第一個(gè)，則將它移到最后一個(gè)，即標(biāo)志為最近使用的頁(yè){EnQueue(L,ref[i]);DeQueue(L,e);}elseif(QNode_num==2)//如果接下來(lái)是內(nèi)存中的第二個(gè)，則將它刪除并在隊(duì)列尾部添加相同元素，即標(biāo)志為最近使用的頁(yè){DelMid_Queue(L,e);EnQueue(L,e);}coutvv"進(jìn)入頁(yè):"vvref[i]vvendl;p=L.front->next;for(j=0;p!=NULL&&j<phy_size;j++)//輸出內(nèi)存狀況cout<<p->data<<"\t";p=p->next;}cout<<endl<<endl;}SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_INTENSITY|FOREGROUND_GREEN);coutvv"最近最久未使用置換算法缺頁(yè)中斷次數(shù)："vvinterrupt_numvvendl;//以綠色字體輸出中斷次數(shù)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; //標(biāo)記帶內(nèi)存中與帶進(jìn)入頁(yè)面相同的頁(yè)面的位置intLNode_flag_num=0; //標(biāo)記訪問(wèn)位為0的頁(yè)面在內(nèi)存中的位置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);〃找到第一個(gè)flag標(biāo)志為0的結(jié)點(diǎn)，其序號(hào)記錄在LNode_flag_num中LNode_flag_num--;Exchange_LNode(L,ref[i],LNode_flag_num);〃將鏈表L中序號(hào)為L(zhǎng)Node_flag_num的結(jié)點(diǎn)替換為內(nèi)容為ref[i]的結(jié)點(diǎn)interrupt_num++;SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_INTENSITY|FOREGROUND_BLUE);}elseSet_LL_Flag(L,LNode_hit_num);coutvv"進(jìn)入頁(yè):"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置換算法缺頁(yè)中斷次數(shù):"<<interrupt_num<<endl; //以綠色字體輸出中斷次數(shù)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*******************改進(jì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)); //設(shè)置時(shí)間種子temp=rand()%3;coutvv"修改頁(yè)(