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

1、操作系統(tǒng)實(shí)驗(yàn)報(bào)告課題：頁(yè)面淘汰算法專 業(yè)： 班 級(jí)： 學(xué) 號(hào)： 姓 名： 年 月 日目 錄一 實(shí)驗(yàn)?zāi)康?二 實(shí)驗(yàn)要求3三 背景知識(shí)3四 總體設(shè)計(jì)4五 詳細(xì)設(shè)計(jì)7六 運(yùn)行結(jié)果分析 9七 心得體會(huì)13八 參考文獻(xiàn) 14附：源代碼 15一、實(shí)驗(yàn)?zāi)康谋緦?shí)驗(yàn)主要對(duì)操作系統(tǒng)中請(qǐng)求分頁(yè)式內(nèi)存管理及其應(yīng)用的一些關(guān)鍵算法進(jìn)行模擬。學(xué)生通過(guò)設(shè)計(jì)與實(shí)現(xiàn)Clock算法，能夠加強(qiáng)對(duì)相應(yīng)理論的理解，并對(duì)了解操作系統(tǒng)內(nèi)部的基本處理原理與過(guò)程也有很多益處。利用簡(jiǎn)單的數(shù)據(jù)結(jié)構(gòu)，模擬實(shí)現(xiàn)操作系統(tǒng)中的頁(yè)面置換機(jī)制，通過(guò)寫(xiě)程序模擬實(shí)現(xiàn)上述三種內(nèi)存頁(yè)面置換算法，使學(xué)生進(jìn)一步掌握內(nèi)存頁(yè)面置換的方法。對(duì)操作系統(tǒng)中內(nèi)存的管理有一個(gè)實(shí)踐上的認(rèn)

2、識(shí)。1、用C語(yǔ)言編寫(xiě)OPT、FIFO、LRU三種置換算法。2、熟悉內(nèi)存分頁(yè)管理策略。3、了解頁(yè)面置換的算法。4、掌握一般常用的調(diào)度算法。5、根據(jù)方案使算法得以模擬實(shí)現(xiàn)。6、鍛煉知識(shí)的運(yùn)用能力和實(shí)踐能力。二、實(shí)驗(yàn)要求l 設(shè)計(jì)隨機(jī)頁(yè)面序號(hào)產(chǎn)生程序，并說(shuō)明隨機(jī)的性能和其性能可能對(duì)算法的影響l 編寫(xiě)頁(yè)面淘汰算法(FIFO、OPT、LRU)l 結(jié)果數(shù)據(jù)的顯示或提取l 結(jié)果數(shù)據(jù)的分析 幾點(diǎn)說(shuō)明：l 設(shè)計(jì)并繪制算法流程，附加說(shuō)明所需的數(shù)據(jù)結(jié)構(gòu)l 如何標(biāo)記時(shí)間的先后、最久的將來(lái)、最久未被使用l 描述Clock算法的基本原理、必要的數(shù)據(jù)結(jié)構(gòu)、算法執(zhí)行流程圖、編碼實(shí)現(xiàn)。1）初始化：輸入作業(yè)可占用的總頁(yè)框數(shù)，初始化

3、置空。2）輸入請(qǐng)求序列：輸入一個(gè)作業(yè)頁(yè)號(hào)訪問(wèn)請(qǐng)求序列，依次占用相應(yīng)頁(yè)框，直至全部占用；3）Clock算法：當(dāng)頁(yè)框全部占用后，對(duì)于后續(xù)新的頁(yè)號(hào)訪問(wèn)請(qǐng)求，執(zhí)行Clock算法，淘汰1個(gè)頁(yè)面后裝入新的頁(yè)號(hào)。4）顯示當(dāng)前分配淘汰序列：顯示淘汰的頁(yè)號(hào)序列。三、背景知識(shí)：在操作系統(tǒng)當(dāng)中，在進(jìn)程運(yùn)行過(guò)程中，若其訪問(wèn)的頁(yè)面不在內(nèi)存中而需把他們調(diào)入內(nèi)存，但內(nèi)存已無(wú)空閑空間時(shí)，為了保證該進(jìn)程能夠正常的運(yùn)行，系統(tǒng)必須從內(nèi)存中調(diào)出一頁(yè)程序或數(shù)據(jù)送到磁盤(pán)的兌換區(qū)中，但是應(yīng)該是哪個(gè)頁(yè)面被調(diào)出，需根據(jù)一定的算法來(lái)確定。通常，我們把這一類的算法稱為“頁(yè)面置換算法”，頁(yè)面置換算法執(zhí)行效率的高低，往往直接影響到操作系統(tǒng)的性能。內(nèi)存

4、頁(yè)面置換算法：1、 <1> 先進(jìn)先出調(diào)度算法（FIFO）先進(jìn)先出調(diào)度算法根據(jù)頁(yè)面進(jìn)入內(nèi)存的時(shí)間先后選擇淘汰頁(yè)面。本算法實(shí)現(xiàn)時(shí)需要將頁(yè)面按進(jìn)入內(nèi)存的時(shí)間先后組成一個(gè)隊(duì)列，每次置換掉最早進(jìn)入的頁(yè)面。這是最早出現(xiàn)的置換算法，該算法總是淘汰最先進(jìn)入內(nèi)存的頁(yè)面，即選擇在內(nèi)存中駐留時(shí)間最長(zhǎng)的頁(yè)面換出，予以淘汰。該算法實(shí)現(xiàn)簡(jiǎn)單只需把一個(gè)進(jìn)程已調(diào)入內(nèi)存的頁(yè)面，按先后次序鏈接成一個(gè)隊(duì)列，并設(shè)置一個(gè)指針，稱為替換指針，使它總是指向最老的頁(yè)面。但該算法與進(jìn)程實(shí)際運(yùn)行的規(guī)律不相適應(yīng)，因?yàn)樵谶M(jìn)程中，有些頁(yè)面經(jīng)常被訪問(wèn)，比如，含有全局變量、常用函數(shù)、例程等的頁(yè)面，F(xiàn)IFO算法并不能保證這些頁(yè)面不被淘汰。<

5、;2>最近最久未使用的置換算法（LRU）最近最久未使用的置換算法，是根據(jù)頁(yè)面調(diào)入內(nèi)存后的使用情況進(jìn)行決策的。由于無(wú)法預(yù)測(cè)各頁(yè)面將來(lái)的使用情況，只能利用“最近的過(guò)去”作為“最近的將來(lái)”的近似，因此，LRU 置換算法是選擇最近最久未使用的頁(yè)面予以淘汰。該算法賦予每個(gè)頁(yè)面一個(gè)訪問(wèn)字段，用來(lái)記錄一個(gè)頁(yè)面自上次被訪問(wèn)以來(lái)所經(jīng)歷的時(shí)間t,，當(dāng)須淘汰一個(gè)頁(yè)面時(shí)，選擇現(xiàn)有頁(yè)面中其t值最大的，即最近最久未使用的頁(yè)面予以淘汰。<3> 最佳置換算法（OPT）最佳置換算法是可以說(shuō)的一種理想的頁(yè)面置換算法，它是由Belady于1966 年提出的一種理論上的算法。其所選擇的被淘汰頁(yè)面，將是以后永不使用的

6、或許是在最長(zhǎng)(未來(lái))時(shí)間內(nèi)不再被訪問(wèn)的頁(yè)面。采用最佳置換算法，通?？杀ＷC獲得最低的缺頁(yè)率。但由于人目前還無(wú)法預(yù)知一個(gè)進(jìn)程在內(nèi)存的若干個(gè)頁(yè)面中，哪一個(gè)頁(yè)面是未來(lái)最長(zhǎng)時(shí)間內(nèi)不再被訪問(wèn)的，因而該算法是無(wú)法實(shí)現(xiàn)的，但可以利用此算法來(lái)評(píng)價(jià)其它算法。<4>時(shí)鐘頁(yè)面置換算法時(shí)鐘頁(yè)面置換算法是把所有的頁(yè)面都保存在一個(gè)類似鐘面的環(huán)形鏈表中，一個(gè)表針指向最老的頁(yè)面，如圖所示。 當(dāng)發(fā)生缺頁(yè)中斷時(shí)，算法首先檢查表針指向的頁(yè)面，如果它的R位是0就淘汰該頁(yè)面，并把新的頁(yè)面插入這個(gè)位置，然后把表針前移一個(gè)位置；如果R位是1就清除R位并把表針前移一個(gè)位置，重復(fù)這個(gè)過(guò)程直到找到了一個(gè)R位為0的頁(yè)面為止。四、 總體設(shè)

7、計(jì)l 根據(jù)要求設(shè)計(jì)頁(yè)面淘汰算法的活動(dòng)圖 運(yùn)行程序進(jìn)入主頁(yè)面，在正上方，已經(jīng)通過(guò)隨機(jī)生成函數(shù)生成了頁(yè)面號(hào)，在其下方，顯示可選項(xiàng)：0、退出程序1、FIFO算法2、OPT算法3、LRU算法。根據(jù)需要，選擇相應(yīng)的法，程序自動(dòng)生成頁(yè)面淘汰的先后順序，以及置換次數(shù)和缺頁(yè)次數(shù)，并打印在下方，執(zhí)行完以后，再次進(jìn)入主頁(yè)面，到輸入0，退出程序。l 算法流程圖Ø FIFO算法流程圖：Ø OPT算法流程圖Ø LRU算法流程圖：五、 詳細(xì)設(shè)計(jì)（一）、設(shè)計(jì)思想1、 最佳置換算法(OPT)用數(shù)組Temppages存儲(chǔ)當(dāng)前物理塊中頁(yè)面信息，數(shù)組TimeArry存儲(chǔ)當(dāng)前在物理塊中的頁(yè)面的獲得內(nèi)存時(shí)

8、的時(shí)間，當(dāng)頁(yè)面不在內(nèi)存中時(shí)，根據(jù)當(dāng)前已獲得物理塊數(shù)的頁(yè)面在所有的頁(yè)面當(dāng)中將來(lái)不在請(qǐng)求內(nèi)存或者很少請(qǐng)求內(nèi)存的情況進(jìn)行置換2、 先進(jìn)先出算法(FIFO)用數(shù)組Temppages存儲(chǔ)當(dāng)前物理塊中頁(yè)面信息，變量temp記錄內(nèi)存中物理塊頁(yè)面置換狀態(tài)，每進(jìn)行一次置換，頁(yè)面置換狀態(tài)變化，便于下一次的置換。3、 最近最久未使用算法(LRU)用數(shù)組Temppages存儲(chǔ)當(dāng)前物理塊中頁(yè)面信息，數(shù)組TimeArry存儲(chǔ)當(dāng)前在物理塊中的頁(yè)面的獲得內(nèi)存時(shí)的時(shí)間，當(dāng)頁(yè)面不在內(nèi)存中時(shí)，選擇TimeArry數(shù)組中值最小并且對(duì)應(yīng)物理塊中的頁(yè)面進(jìn)行置換。（二）、設(shè)計(jì)步驟首先根據(jù)程序要求，我們分別定義兩個(gè)宏，用以存放我們的物理塊數(shù)

9、目以及頁(yè)面數(shù)目，再定義一個(gè)結(jié)構(gòu)體，用以物理塊的存儲(chǔ)，代碼如下：#define MemPageCount 4 #define InstructionCount 20 struct page int serial; /頁(yè)面號(hào) int time; /時(shí)間計(jì)數(shù)mempageMemPageCount;其次，建立主函數(shù)，根據(jù)程序需要，定義相應(yīng)的變量，建立switch語(yǔ)句，用以算法的選擇，部分定義如下：int i,j,k,m,n;/指令頁(yè)面集合,可以考慮讓頁(yè)面指令集合隨機(jī)生成int instructionInstructionCount;int mem_counter; /內(nèi)存頁(yè)面集合計(jì)數(shù)器int swit

10、ch_counter; /置換次數(shù)最后，根據(jù)算法流程圖，實(shí)現(xiàn)相應(yīng)算法的代碼編寫(xiě)。（三）、算法流程設(shè)計(jì)主函數(shù)流程:STEP1:輸入分配的頁(yè)框數(shù)，頁(yè)面訪問(wèn)次數(shù)和要訪問(wèn)的頁(yè)面號(hào)序列STEP2:內(nèi)存頁(yè)面初始化。內(nèi)存中頁(yè)面的數(shù)據(jù)結(jié)構(gòu)為單循環(huán)鏈表，含有頁(yè)號(hào)值yehao和訪問(wèn)位值a。開(kāi)始時(shí)頁(yè)號(hào)均為-1，訪問(wèn)位為0.STEP3：測(cè)試數(shù)據(jù)。具體算法是依要訪問(wèn)的頁(yè)面號(hào)，調(diào)用find()函數(shù)查找是否已經(jīng)存在于內(nèi)存中。若存在，則修改其訪問(wèn)位為1.若不存在，觸發(fā)缺頁(yè)中斷，調(diào)用tihuan()函數(shù)。最后，打印當(dāng)前內(nèi)存狀態(tài)。如此循環(huán)直至測(cè)試串都訪問(wèn)完畢。1) 主要函數(shù)實(shí)現(xiàn)a) Makenode(double)函數(shù)：用于初始

11、化一個(gè)節(jié)點(diǎn)。b) Find（double）函數(shù)：依據(jù)輸入的頁(yè)號(hào)，查詢內(nèi)存中是否已存在此頁(yè)面。若存在返回值1，不存在返回值0.c) Tihuan（double）函數(shù)：在發(fā)生缺頁(yè)中斷時(shí)，時(shí)鐘指針查找訪問(wèn)位為0的頁(yè)面進(jìn)行替換，指針掃過(guò)的頁(yè)面訪問(wèn)位置0，新加入的頁(yè)面訪問(wèn)位置1。替換后指針下移。d) Print_state()函數(shù)：打印當(dāng)前內(nèi)存中存在的頁(yè)面的狀態(tài)以及當(dāng)前時(shí)鐘指針?biāo)赶虻捻?yè)面位置。2) 測(cè)試數(shù)據(jù)估計(jì)輸入：輸入分配的頁(yè)框數(shù)3輸入頁(yè)面訪問(wèn)次數(shù)15輸入要訪問(wèn)的頁(yè)面號(hào)序列3 4 2 6 4 3 7 4 3 6 3 4 8 4 6輸出（僅最后一項(xiàng)）：3) 結(jié)果分析以下是clock算法對(duì)應(yīng)輸入頁(yè)面號(hào)序

12、列3 4 2 6 4 3 7 4 3 6 3 4 8 4 6的分析表六、 運(yùn)行結(jié)果分析：a) 開(kāi)始界面2、 采用隨機(jī)數(shù)產(chǎn)生的結(jié)果2、采用自定義頁(yè)面信息產(chǎn)生結(jié)果自定義頁(yè)面數(shù)為：15 物理塊數(shù)為：4頁(yè)面序列為：1 2 3 4 5 6 7 8 9 4 5 6 7 0 8根據(jù)結(jié)果，我們不難發(fā)現(xiàn)，OPT算法，是三種算法中性能最好的，它的置換次數(shù)最少，LRU次之，不過(guò)性能最差的還是FIFO，由于缺頁(yè)率=缺頁(yè)次數(shù)/總的頁(yè)面數(shù)，所以我們不難發(fā)現(xiàn)，隨著物理塊數(shù)的增加，缺頁(yè)率都相應(yīng)有所增加，但是OPT算法的增加較為明顯，即產(chǎn)生了belady現(xiàn)象。七、心得體會(huì)： 這次課程設(shè)計(jì)，讓我對(duì)算法的編寫(xiě)更加的熟練，同時(shí)更加了

13、解頁(yè)面置換的相關(guān)算法，也提高了我對(duì)算法設(shè)計(jì)的嚴(yán)密性，對(duì)以后的程序設(shè)計(jì)有很大幫助。我們不僅對(duì)常用的算法進(jìn)行了編寫(xiě)，還對(duì)一些理想的算法也進(jìn)行了編寫(xiě)，并且通過(guò)適當(dāng)?shù)姆椒ǎ靡粤蓑?yàn)證。就該程序而言，隨機(jī)性使得程序出現(xiàn)了更多的可能性，為我們驗(yàn)證算法提供很大的方便，電腦自動(dòng)分配，大大的節(jié)約了我們的時(shí)間，但是我們通過(guò)實(shí)驗(yàn)不難發(fā)現(xiàn)，如果所設(shè)的頁(yè)面項(xiàng)目過(guò)大，也會(huì)影響我們算法的性能執(zhí)行效率。對(duì)我們所涉及的算法，讓我有很大的感觸。在FIFO 算法中，無(wú)論有無(wú)發(fā)生缺頁(yè)或者置換，都需要對(duì)每個(gè)在內(nèi)存中的頁(yè)面的time 值進(jìn)行增加操作，以保持最先進(jìn)入的那個(gè)頁(yè)面的time 值是最大的；一個(gè)新進(jìn)來(lái)的頁(yè)面，其time值設(shè)置為0。

14、當(dāng)然，該算法也可以通過(guò)隊(duì)列結(jié)構(gòu)來(lái)實(shí)現(xiàn)，利用隊(duì)列的先進(jìn)先出（FIFO）特性完成，無(wú)需設(shè)置time字段。distance 用于記錄內(nèi)存物理塊集合中每個(gè)頁(yè)面距離再次被使用的頁(yè)面跨度，缺省值為9999，如果某個(gè)頁(yè)面在后續(xù)指令集合中不再出現(xiàn)，則用最大值9999 缺省取代；如果頁(yè)面再次被使用，則兩次使用所跨的頁(yè)面數(shù)，為頁(yè)面跨度。用最大頁(yè)面跨度表示以后永不使用或未來(lái)最長(zhǎng)時(shí)間內(nèi)不再被訪問(wèn)。在LRU 算法中，無(wú)論是否發(fā)生缺頁(yè)或者置換，除了命中（剛剛被訪問(wèn)過(guò)的頁(yè)面）頁(yè)面time 值清零之外，其它所有內(nèi)存中的頁(yè)面的time 值都加一，以保證最近剛剛被訪問(wèn)的頁(yè)面的time 值最小，相應(yīng)time 值最大的頁(yè)面就是最近最

15、久沒(méi)有被訪問(wèn)的頁(yè)面。上述兩種算法，是我們?cè)谶M(jìn)程調(diào)度中使用最多的兩種，你可能會(huì)問(wèn)？為什么要使用進(jìn)程調(diào)度，因?yàn)楫?dāng)我們的程序在運(yùn)行時(shí)，若所訪問(wèn)的頁(yè)面不再內(nèi)存而需把它調(diào)入內(nèi)存，但內(nèi)存已無(wú)空閑空間，這時(shí)，為了保證該程序能正常運(yùn)行，系統(tǒng)就必須從內(nèi)存中調(diào)出一頁(yè)程序或數(shù)據(jù)送到磁盤(pán)的兌換區(qū)中，但應(yīng)將那個(gè)頁(yè)面調(diào)出，我們就必須根據(jù)一定的算法來(lái)實(shí)現(xiàn)。所以，一個(gè)頁(yè)面置換算法的好壞，將直接影響到我們系統(tǒng)的性能。相比較而言，我們最常用的是LRU算法，因?yàn)樗歉鶕?jù)頁(yè)面調(diào)入內(nèi)存后的使用情況就行決策的，比FIFO算法要好很多。通過(guò)與其他算法的比較，加深對(duì)clock算法的理解,也了解了他們的異同之處。Clock算法其實(shí)是一種改進(jìn)的

16、第二次機(jī)會(huì)算法，它通過(guò)設(shè)置訪問(wèn)位，找到最早最不常訪問(wèn)的頁(yè)面，即標(biāo)號(hào)為0的頁(yè)面。之所以叫clock算法，依我理解是將內(nèi)存中的排列順序附上時(shí)間的概念，clock指針掃過(guò)的頁(yè)面要將他們1置0就是基于這個(gè)思想，因?yàn)樗麄兌际菦](méi)被訪問(wèn)的，且在時(shí)鐘上的排列按照訪問(wèn)時(shí)間順序。這樣就保證了每次替換的都是最早進(jìn)來(lái)的且不最常訪問(wèn)的頁(yè)面。八、參考文獻(xiàn)【1】計(jì)算機(jī)操作系統(tǒng)（第三版） 湯小丹、梁紅兵、湯子瀛、哲鳳屏等 西安電子科技大學(xué)出版社 2007-05  【2】 C+ Primer中文版（第4版） （美）Stanley B. Lippman 等 著  李師賢 等 譯. 人民郵電出版社,

17、2006-03-01【3】 C+ Primer習(xí)題解答（第4版） 蔣愛(ài)軍，李師賢，梅曉勇 著 人民郵電出版社 2007-02-01【4】 現(xiàn)代操作系統(tǒng)（原書(shū)第3版）塔嫩鮑姆 （Tanenbaum.A.S），陳向群，馬洪兵 著 機(jī)械工業(yè)出版社 2009-07-01【5】計(jì)算機(jī)操作系統(tǒng)教程 張堯?qū)W，史美林，張高 清華大學(xué)出版社 2006-10-01【6】 數(shù)據(jù)結(jié)構(gòu)（STL框架） 王曉東 著 清華大學(xué)出版社 2009-09-01附：源代碼#include <stdio.h>#include <stdlib.h>#include <time.

18、h>#define M_size 100int pageNum = 0;/全局變量頁(yè)面數(shù)int pagesM_size;/存儲(chǔ)頁(yè)號(hào)int TemppagesM_size;/輔助數(shù)組int TimeArryM_size;/記錄頁(yè)在內(nèi)存中的時(shí)間int method;/產(chǎn)生結(jié)果的方法int AlgorithmStyle; /輔助變量，用于選擇算法類型int Block;/記錄物理塊數(shù)int start;/輔助變量void Inition()/初始化函數(shù)int i;int t = time(NULL);/產(chǎn)生隨機(jī)數(shù)種子srand(t);/用t初始化隨機(jī)數(shù)種子pageNum = rand()%10

19、+8;/隨機(jī)產(chǎn)生4-14之內(nèi)的整數(shù)，保證頁(yè)面數(shù)在4-14之內(nèi)for(i = 0 ; i < pageNum ; i+)pagesi = rand()%10+1;/初始化頁(yè)號(hào)，初始值在1-10之內(nèi)Block = 4;/初始化物理塊數(shù)位3void printDefaltResult()/缺省參數(shù)顯示int i;printf("缺省頁(yè)面數(shù)為: %dn",pageNum);printf("缺省頁(yè)號(hào)分別為: ");for(i = 0 ; i < pageNum ; i+)printf("%d ",pagesi);printf(&qu

20、ot;n");printf("可用物理塊數(shù)為: %dn",Block);printf("按任意鍵繼續(xù):");getchar();void PrintCustomInfo()/顯示用戶自定義參數(shù)int i;printf("自定義頁(yè)面數(shù)為: %dn",pageNum);printf("自定義頁(yè)號(hào)分別為: ");for(i = 0 ; i < pageNum ; i+)printf("%d ",pagesi);printf("n");printf("可用物

21、理塊數(shù)為: %dn",Block);printf("按任意鍵繼續(xù):n");getchar();void printUserInfo()/顯示個(gè)人信息system("color 0B");printf("n");printf(" 頁(yè)面淘汰算法 n");printf(" 學(xué)號(hào)： n");printf(" 班級(jí)： n");printf(" 姓名： n");printf("n");printf("按任意鍵開(kāi)始操作:"

22、;);getchar();system("cls");system("color 0B");void ChioceDealmethod()/選擇解決問(wèn)題的方法"1"選擇缺省值，"2"選擇自定義值printf("n");printf("1、使用默認(rèn)值產(chǎn)生結(jié)果 2、自定義頁(yè)數(shù)和頁(yè)號(hào) n");printf("n 請(qǐng)輸入你的選擇:n");scanf("%d",&method);system("color 0F");v

23、oid PrintNotWithoutPages()/顯示一定不用換頁(yè)的部分start = Block;int i,j,k=0,key = 0;for(i = 0 ; i < start ; i+)int flag = 0;for(j = 0 ; j <= i-1 ; j+)if(Temppagesj = pagesi)TimeArryj = i;flag = 1;start = start+1;key+;if(flag = 0)TimeArryk = i;Temppagesk = pagesi;k+;for(j = 0 ; j <= i-key ; j+)printf(&q

24、uot; %-7d",Temppagesj);printf("n");void PrintResult()/顯示每次換頁(yè)后的結(jié)果int i;for(i = 0 ; i < Block ; i+)printf(" %-7d",Temppagesi);printf("n");void FIFODealQuestion()/先進(jìn)先出算法int i,j;int WithOutPages = 0;/記錄缺頁(yè)數(shù)printf("FIFO(先進(jìn)先出算法)結(jié)果顯示：n");PrintNotWithoutPages()

25、;int temp = 0;for(i = start ; i < pageNum ; i+)if(temp = Block)temp = 0;int key = 0 ;for(j = 0 ; j < Block ; j+)/判斷該頁(yè)是否在物理塊中if(Temppagesj = pagesi)key = 1;break;if(key = 0)/如果不在Temppagestemp = pagesi;temp+;WithOutPages+;PrintResult();printf("置換次數(shù)為： %d ,頁(yè)面總數(shù)為： %d ,置換率為: ",WithOutPages

26、,pageNum);double re = (double)WithOutPages)/(double)pageNum);printf("%.2lfn",re);printf("缺頁(yè)次數(shù)為： %d ,頁(yè)面總數(shù)為： %d ,缺頁(yè)率為: ",WithOutPages+Block,pageNum);re = (double)(WithOutPages+Block)/(double)pageNum);printf("%.2lfn",re);void LRUDealQuestion()/最近最久未使用算法int i,j;int WithOutP

27、ages = 0;/記錄缺頁(yè)數(shù)printf("LRU(最近最久未使用算法)結(jié)果顯示：n");PrintNotWithoutPages();for(i = start ; i < pageNum; i+)int key = 0;for(j = 0 ; j < Block ; j+)/判斷該頁(yè)是否在物理塊中if(Temppagesj = pagesi)key = 1;TimeArryj = i;/更新時(shí)間break;if(key = 0)/若該頁(yè)不在內(nèi)存中WithOutPages+;int min = TimeArry0;int flag = 0;for(j = 1

28、 ; j < Block ; j+)if(min > TimeArryj)min = TimeArryj;/找到最久的頁(yè)面flag = j;TimeArryflag = i;/記錄時(shí)間Temppagesflag = pagesi;PrintResult();printf("置換次數(shù)為： %d ,頁(yè)面總數(shù)為： %d ,置換率為: ",WithOutPages,pageNum);double re = (double)WithOutPages)/(double)pageNum);printf("%.2lfn",re);printf("缺

29、頁(yè)次數(shù)為： %d ,頁(yè)面總數(shù)為： %d ,缺頁(yè)率為: ",WithOutPages+Block,pageNum);re = (double)(WithOutPages+Block)/(double)pageNum);printf("%.2lfn",re);void OPTDealQuestion()int i,j,l;int WithOutPages = 0;/記錄缺頁(yè)數(shù)printf("OPT(最佳置換算法)結(jié)果顯示：n");PrintNotWithoutPages();for(i = start ; i<pageNum ; i+)int

30、 key = 0;for(j = 0 ; j < Block ; j+ )/判斷該頁(yè)是否在內(nèi)存中if(Temppagesj=pagesi)TimeArryj = i;key = 1;break;if(key = 0)/如果該頁(yè)不在內(nèi)存中WithOutPages+;/缺頁(yè)數(shù)加1/得到各物理塊下一次訪問(wèn)的時(shí)間for(j = 0 ; j < Block ; j+)for(l = i+1; l < pageNum ; l+)if(Temppagesj=pagesl)break;TimeArryj = l;/得到下一次訪問(wèn)時(shí)間最長(zhǎng)的一個(gè)頁(yè)面，將當(dāng)前頁(yè)與其換掉int min = Time

31、Arry0;int flag = 0;for(j = 1 ; j < Block ; j+)if(TimeArryj > min)min = TimeArryj;flag = j;Temppagesflag = pagesi;TimeArryflag = i;PrintResult();printf("置換次數(shù)為： %d ,頁(yè)面總數(shù)為： %d ,置換率為: ",WithOutPages,pageNum);double re = (double)WithOutPages)/(double)pageNum);printf("%.2lfn",re)

32、;printf("缺頁(yè)次數(shù)為： %d ,頁(yè)面總數(shù)為： %d ,缺頁(yè)率為: ",WithOutPages+Block,pageNum);re = (double)(WithOutPages+Block)/(double)pageNum);printf("%.2lfn",re);void ChioceAlgorithm(int AlgorithmStyle)switch(AlgorithmStyle)case 1:FIFODealQuestion();/先進(jìn)先出算法解決問(wèn)題break;case 2:LRUDealQuestion();/最近最久未使用算法解決問(wèn)題break;case 3:OPTDealQuestion();/最佳置換算法解決問(wèn)題break;case 4:FIFODealQuestion();/先進(jìn)先出算法解決問(wèn)題LRUDealQuestion();/最近最久未使用算法解決問(wèn)題OPTDealQuestion();/最佳置換算法解決問(wèn)題break;void DefaltDeal()/默認(rèn)解決printf("n"