1、摘 要 在linux中，為了提高內(nèi)存利用率，提供了內(nèi)外存進(jìn)程對(duì)換機(jī)制，內(nèi)存空間的分配和回收均以頁(yè)為單位進(jìn)行，一個(gè)進(jìn)程只需要將其一部分調(diào)入內(nèi)存便可運(yùn)行；當(dāng)操作系統(tǒng)發(fā)生缺頁(yè)中斷時(shí)，必須在內(nèi)存選擇一個(gè)頁(yè)面將其移出內(nèi)存，以便為即將調(diào)入的頁(yè)面讓出空間。因而引入一種用來(lái)選擇淘汰哪一頁(yè)的算法頁(yè)面置換算法。頁(yè)面置換算法是操作系統(tǒng)中虛擬存儲(chǔ)管理的一個(gè)重要部分。頁(yè)面置換算法在具有層次結(jié)構(gòu)存儲(chǔ)器的計(jì)算機(jī)中，為用戶提供一個(gè)比主存儲(chǔ)器容量大得多的可隨機(jī)訪問的地。常見的頁(yè)面置換算法有先來(lái)先服務(wù)算法(FIFO)，最近最久未使用算法(LRU)和最佳適應(yīng)算法(OPT)。關(guān)鍵字：操作系統(tǒng)；FIFO；LRU；OPT；Linux目

2、錄1 緒論11.1 設(shè)計(jì)任務(wù)11.2設(shè)計(jì)思想11.3設(shè)計(jì)特點(diǎn)11.4基礎(chǔ)知識(shí)21.4.1 先進(jìn)先出置換算法(FIFO)21.4.2 最近最久未使用算法(LRU)31.4.3最佳置換算法(OPT)32 各模塊偽代碼算法42.1偽代碼概念42.2偽代碼算法42.2.1主函數(shù)偽代碼算法42.2.2延遲時(shí)間函數(shù)偽代碼算法62.2.3 FIFO算法的偽代碼72.2.4 LRU算法的偽代碼72.2.5 OPT算法的偽代碼103 函數(shù)調(diào)用關(guān)系圖123.1函數(shù)聲明123.1.1主要算法函數(shù)123.1.2輔助函數(shù)123.2程序函數(shù)調(diào)用關(guān)系圖134 測(cè)試結(jié)果144.1數(shù)據(jù)初始化144.2頁(yè)面調(diào)度算法144.2.1

3、先進(jìn)先出算法154.2.2最近最久未使用LRU154.2.3最佳置換算法OPT175 源程序186 設(shè)計(jì)總結(jié)30參考文獻(xiàn)31致 謝321 緒論1.1 設(shè)計(jì)任務(wù) 1、了解UNIX的命令及使用格式，熟悉UNIX/LINUX的常用基本命令，練習(xí)并掌握UNIX提供的vi編輯器來(lái)編譯C程序，學(xué)會(huì)利用gcc、gdb編譯、調(diào)試C程序。 2、設(shè)計(jì)一個(gè)虛擬存儲(chǔ)區(qū)和內(nèi)存工作區(qū)，并使用最佳淘汰算法（OPT）、先進(jìn)先出算法（FIFO）、最近最久未使用算法（LRU）計(jì)算訪問命中率。（命中率頁(yè)面失效次數(shù)頁(yè)地址流長(zhǎng)度=1-缺頁(yè)率）1.2設(shè)計(jì)思想 在進(jìn)程運(yùn)行過程中，若期所有要訪問的頁(yè)面不在內(nèi)存，而需把它們調(diào)入內(nèi)存，但內(nèi)存已無(wú)

4、空閑空間時(shí)，為了保證進(jìn)程正常進(jìn)行，系統(tǒng)必須從內(nèi)存中調(diào)出一頁(yè)程序或數(shù)據(jù)送到磁盤的對(duì)換區(qū)中。但應(yīng)將哪個(gè)頁(yè)面調(diào)出，須根據(jù)一定的算法來(lái)確定。通常，把選擇換出頁(yè)面的算法稱為頁(yè)面置換算法。置換算法的好壞將直接影響到系統(tǒng)的性能。 不適當(dāng)?shù)乃惴赡軙?huì)導(dǎo)致進(jìn)程發(fā)生“抖動(dòng)”，即剛被換出的頁(yè)很快又要被訪問，需要將它重新調(diào)入，此時(shí)又需要再選一頁(yè)調(diào)出；而此剛被調(diào)出的頁(yè)很快又被訪問，有需將它調(diào)入，如此頻繁地更換頁(yè)面，以致一個(gè)進(jìn)程在運(yùn)行中把大部分的時(shí)間都花費(fèi)在頁(yè)面置換工作上。通過模擬實(shí)現(xiàn)請(qǐng)求頁(yè)式存儲(chǔ)管理的幾種基本頁(yè)面置換算法，了解虛擬存儲(chǔ)技術(shù)的特點(diǎn)，掌握虛擬存儲(chǔ)請(qǐng)求頁(yè)式存儲(chǔ)管理中幾種基本頁(yè)面置換算法的基本思想和實(shí)現(xiàn)過程，并

5、比較它們的效率。改進(jìn)頁(yè)面置換算法,可以降低頁(yè)面失敗率,從而有效地提高系統(tǒng)性能。從理論上講，應(yīng)將那些以后不再會(huì)訪問的頁(yè)面置換出來(lái)，或把那些在較長(zhǎng)時(shí)間內(nèi)不會(huì)再訪問的頁(yè)面調(diào)出。目前已有多種置換算法，它們都試圖更接近于理論上的目標(biāo)。1.3設(shè)計(jì)特點(diǎn) 本設(shè)計(jì)作品主要用C語(yǔ)言編寫而成，結(jié)構(gòu)簡(jiǎn)單，語(yǔ)言易懂，條理清晰。本作品兼容性也非常的高，可以在各種可以編譯C語(yǔ)言的編譯軟件上運(yùn)行，并能夠在cygwin中運(yùn)行，經(jīng)多次調(diào)試，暫時(shí)未發(fā)現(xiàn)有何不足。本程序的另一個(gè)優(yōu)點(diǎn)是，程序可以計(jì)算大數(shù)量數(shù)據(jù)。如，本程序可以計(jì)算的最大物理塊個(gè)數(shù)達(dá)到了10000個(gè)，用戶輸入的頁(yè)面引用串個(gè)數(shù)也能達(dá)到10000個(gè)以上。但是，實(shí)際生活中系統(tǒng)的

6、物理塊個(gè)數(shù)一般不會(huì)達(dá)到10000個(gè)。因此，我們?cè)谔崾居脩糨斎腠?yè)面引用串個(gè)數(shù)是，只提示最大輸入100個(gè)。但是代碼不足在于使用到了較多的static 全局變量使得整個(gè)代碼質(zhì)量不是很好，而且也只是簡(jiǎn)單的根據(jù)算法設(shè)計(jì)來(lái)模擬實(shí)現(xiàn)整個(gè)過程。我通過先查找該頁(yè)面是否在頁(yè)幀中存在，若不存在則需要頁(yè)面置換，通過刷新每個(gè)頁(yè)幀的time值來(lái)得到每次的最小值來(lái)進(jìn)行頁(yè)面的置換，最小值即代表著最近最少使用的頁(yè)面。 經(jīng)過測(cè)試，這個(gè)系統(tǒng)已經(jīng)達(dá)到了題目中的全部要求。這個(gè)程序有很多優(yōu)點(diǎn)有一個(gè)是界面簡(jiǎn)明，簡(jiǎn)潔明了的程序菜單；一個(gè)是智能化的模塊設(shè)計(jì)，減少了許多人工操作，如功能模塊操作結(jié)束后，均會(huì)返回主菜單進(jìn)行下一模板的運(yùn)行，

7、并提示是否再進(jìn)行類似的操作，這樣給用戶帶來(lái)了操作的方便，大大提高了學(xué)生選課的效率還有就是提示語(yǔ)言既簡(jiǎn)潔又明確，層次分明等等；當(dāng)然也有缺點(diǎn)如程序仍然存在不合理的地方，例如程序某些部分輸入錯(cuò)誤不能立刻返回改正；信息表達(dá)方式不豐富，比較單一，缺少圖片、音樂等元化表達(dá)方式。 FIFO算法總是選擇在內(nèi)存駐留時(shí)間最長(zhǎng)的一頁(yè)將其淘汰。這種算法基于CPU按線性順序訪問地址空間的這個(gè)假設(shè)上，許多時(shí)候，CPU不是按吸納型順序訪問地址空間的。所以，那些在內(nèi)存中停留時(shí)間最長(zhǎng)的頁(yè)往往被訪問到。這就造成FIFO算法的缺頁(yè)率不太理想。并且，F(xiàn)IFO還有一個(gè)缺點(diǎn)就是Belady奇異現(xiàn)象。實(shí)現(xiàn)FIFO算法無(wú)需硬件提供新的幫助，

8、只采用循環(huán)數(shù)組管理駐留集即可。OPT算法被譽(yù)為“最佳算法”，因?yàn)樗蕴麓卧L問距當(dāng)前最遠(yuǎn)的那些頁(yè)中序號(hào)最小的一頁(yè)。所以，OPT算法得出的缺頁(yè)率是最小的。但是，OPT算法在使用前必須先得知整個(gè)訪問串，這很難實(shí)現(xiàn)。因此，OPT算法知識(shí)一種概念中的算法。LRU算法的實(shí)現(xiàn)耗費(fèi)較高，并且需要硬件的支持，但是效果較好。就缺頁(yè)率而言，OPT算法最佳，F(xiàn)IFO算法最差。1.4基礎(chǔ)知識(shí)1.4.1 先進(jìn)先出置換算法(FIFO) FIFO算法是最早出現(xiàn)的算法。該算法總是淘汰最先進(jìn)入內(nèi)存的頁(yè)面，即選擇在內(nèi)存駐留時(shí)間最久的頁(yè)面予以淘汰。該算法實(shí)現(xiàn)簡(jiǎn)單，只需要把一個(gè)進(jìn)程已調(diào)入內(nèi)存的頁(yè)面按先來(lái)后次序鏈接成一個(gè)隊(duì)列，并設(shè)置一

9、個(gè)指針，稱為替換指針，使它總是指向最老的頁(yè)面。但是該算法與進(jìn)程實(shí)際運(yùn)行的規(guī)律不相符合，因?yàn)樵谶M(jìn)程中，有些頁(yè)面經(jīng)常被訪問。1.4.2 最近最久未使用算法(LRU) 選擇最近一段時(shí)間最長(zhǎng)時(shí)間沒有被訪問過的頁(yè)面予以淘汰。 LRU算法是根據(jù)頁(yè)面調(diào)入內(nèi)存后的使用情況進(jìn)行決策。由于無(wú)法預(yù)測(cè)各頁(yè)面將來(lái)的使用情況，采取“最近的過去”作為“最近的將來(lái)”的近似。選擇最近最久未使用的頁(yè)面予以淘汰。實(shí)現(xiàn)：賦予每個(gè)頁(yè)面一個(gè)方位字段，用來(lái)記錄一個(gè)頁(yè)面自上次被訪問以來(lái)所經(jīng)歷的時(shí)間T，當(dāng)要淘汰一個(gè)頁(yè)面的，選擇現(xiàn)有頁(yè)面中其T值最大的，即最近最久未使用的頁(yè)面予以淘汰。1.4.3最佳置換算法(OPT)最佳置換算法所選擇的

10、被淘汰掉的頁(yè)面，將是以后永久不再使用的，或許是在最長(zhǎng)（未來(lái)）時(shí)間內(nèi)不再被訪問的頁(yè)面。采用最佳置算法，通常可保證獲得最低的缺頁(yè)率。本模擬算法中，最佳頁(yè)面置換算法實(shí)現(xiàn)所采用的思想是：循環(huán)讀入每個(gè)頁(yè)表項(xiàng)，若該頁(yè)表在內(nèi)存中，則讀取下一個(gè)頁(yè)表項(xiàng)。若頁(yè)表不存在內(nèi)存中：一種情況是內(nèi)存不滿，則將頁(yè)表放入內(nèi)存中；若內(nèi)存塊已滿，剛分別計(jì)算內(nèi)存中各個(gè)頁(yè)表再次被使用的時(shí)間，并將最久不被訪問的調(diào)出，放入當(dāng)前讀入頁(yè)表項(xiàng)。2 各模塊偽代碼算法 根據(jù)程序提示，用戶先將需要計(jì)算的頁(yè)面號(hào)引用串，物理塊數(shù)量和引用串個(gè)數(shù)輸入到文件流中。待程序加載數(shù)據(jù)完成后，用戶繼續(xù)選擇頁(yè)面置換算法的類型，程序根據(jù)用戶輸入的信息來(lái)判斷采用哪一種算法進(jìn)

11、行計(jì)算。結(jié)構(gòu)如圖2.1所示。圖 2.1 總體結(jié)構(gòu)圖2.1偽代碼概念 偽代碼（英語(yǔ)：pseudocode），又稱為虛擬代碼，是高層次描述算法的一種方法。使用偽代碼的目的是讓被描述的算法可以容易地以任何一種編程語(yǔ)言（Pascal，C，Java，etc）實(shí)現(xiàn)。因此，偽代碼必須結(jié)構(gòu)清晰、代碼簡(jiǎn)單、可讀性好，介于自然語(yǔ)言與編程語(yǔ)言之間。以編程語(yǔ)言的書寫形式指明算法職能。使用偽代碼，不用拘泥于具體實(shí)現(xiàn)。它是半角式化、不標(biāo)準(zhǔn)的語(yǔ)言。可以把整個(gè)算法運(yùn)行過程的結(jié)構(gòu)用接近自然語(yǔ)言的形式（可以使用任何一種你熟悉的文字，關(guān)鍵是把程序的意思表達(dá)出來(lái)）描述出來(lái)。2.2偽代碼算法2.2.1主函數(shù)偽代碼算法 該程序是按自上而

12、下，自頂向下的設(shè)計(jì)思想進(jìn)行設(shè)計(jì)的。程序各個(gè)功能的實(shí)現(xiàn)之間的聯(lián)系采用函數(shù)調(diào)用與函數(shù)嵌套。main()函數(shù)是整個(gè)程序的入口，程序的開始就是從這里開始的，然后通過main()函數(shù)調(diào)用其他函數(shù)來(lái)實(shí)現(xiàn)各個(gè)功能。具體流程如圖2.2所示。圖2.2 主函數(shù)流程圖Begin /*算法開始*/調(diào)用designBy()顯示出設(shè)計(jì)者信息Scanf mSIZE，pSIZE，page100 /*mSIZE表示物理塊，pSIZE表示頁(yè)面號(hào)引用串個(gè)數(shù)，page100表示一個(gè)引用串的頁(yè)面號(hào)*/do Printf pageiScanf code /*code是一個(gè)標(biāo)記，用來(lái)判斷用戶輸入是否符合要求*/Switch(code)ca

13、se 1: FIFO() /*先進(jìn)先出算法*/case 2: LRU() /*最近最久未使用算法*/case 3: OPT() /*最佳置換算法*/case 4: exit(0) /*退出程序*/default: 重新輸入while(code!=4)Getch（用戶輸入）End2.2.2延遲時(shí)間函數(shù)偽代碼算法begin變量定義while delay>0while i<124退格end圖2.3 延遲時(shí)間函數(shù)流程圖 延遲時(shí)間函數(shù)主要由兩個(gè)for循環(huán)構(gòu)成。延遲時(shí)間函數(shù)在程序中主要起延遲時(shí)間的作用，相當(dāng)于一個(gè)定時(shí)器，給程序數(shù)據(jù)加載，數(shù)據(jù)處理等提供時(shí)間保證。使程序能夠正常的進(jìn)行。其具體流程如

14、圖2.3所示。2.2.3 FIFO算法的偽代碼 begin 定義變量 while i<mSIZEpagei0memeryi, itimeiwhile j<mSIZEmemeryjtempij while i<pSIZEwhile j<mSIZEif 新頁(yè)面號(hào)不在物理塊中k+if k=mSIZE 則，計(jì)算換出頁(yè)，記錄該頁(yè)進(jìn)入物理塊的時(shí)間否則，tempij=memeryjprint 置換次數(shù)End FIFO算法是操作系統(tǒng)中最簡(jiǎn)單最容易實(shí)現(xiàn)的一種頁(yè)面置換算法，它的實(shí)現(xiàn)主要運(yùn)用了兩個(gè)循環(huán)結(jié)構(gòu)。第一個(gè)循環(huán)的功能是將頁(yè)面串中的前mSIZE頁(yè)面直接放入物理塊中；第二個(gè)循環(huán)主要判斷當(dāng)前

15、頁(yè)面是否在物理塊中，若在物理塊中，則繼續(xù)讀取下一個(gè)頁(yè)面。否則，將最先進(jìn)入物理塊的頁(yè)面寫入到物理塊中。其主要執(zhí)行流程如圖2.4所示。2.2.4 LRU算法的偽代碼 LRU算法是將最近進(jìn)入物理塊且未使用的頁(yè)面首先換出物理塊。LRU函數(shù)主要也運(yùn)用了兩個(gè)循環(huán)來(lái)實(shí)現(xiàn)其算法，首先將前mSIZE個(gè)頁(yè)面置換到物理塊中，然后再按具體算法進(jìn)行置換頁(yè)面。其執(zhí)行流程如圖2.5所示。圖2.4 FIFO流程圖 begin 定義變量 while i<mSIZE pageimemeryi, itimeiwhile j<mSIZEmemeryjtempij while i<mSIZE前mSIZE個(gè)數(shù)直接放入w

16、hile i<pSIZE while j<mSIZEif 新頁(yè)面號(hào)不在物理塊中k+判斷新頁(yè)面號(hào)是否在物理塊中if k=mSIZE 則，計(jì)算換出頁(yè)，記錄該頁(yè)進(jìn)入物理塊的時(shí)間否則，max=flag0<flag1?0:1memeryjtempij調(diào)用 print(置換次數(shù))End圖2.5 LRU流程圖2.2.5 OPT算法的偽代碼 begin 定義變量 while i<mSIZEpageimemeryi, itimeiwhile j<mSIZEmemeryjtempij 前mSIZE個(gè)數(shù)直接放入 while i<pSIZEwhile j<mSIZEif me

17、meryj!=pagei判斷新頁(yè)面號(hào)是否在物理塊中k+if k=mSIZE 則，計(jì)算換出頁(yè)，記錄該頁(yè)進(jìn)入物理塊的時(shí)間否則，max=flag0<flag1?0:1tempij=memeryj得到物理塊中各頁(yè)下一次訪問時(shí)間if memerym=page1退出循環(huán)nextm=1調(diào)用 print(置換次數(shù))End OPT算法是將內(nèi)存中最長(zhǎng)時(shí)間內(nèi)不會(huì)用的頁(yè)面置換出去，這種算法的優(yōu)點(diǎn)是系統(tǒng)利用率，內(nèi)存利用率都非常的高。但是這種算法目前無(wú)法實(shí)現(xiàn)，因?yàn)閷?shí)際中，系統(tǒng)根本無(wú)法預(yù)知哪一個(gè)頁(yè)面最先執(zhí)行，哪一個(gè)頁(yè)面最后執(zhí)行，各個(gè)頁(yè)面的執(zhí)行順序都無(wú)法確定根本就不能確定頁(yè)面換出的次序。OPT算法主要用于對(duì)其他算法效率

18、的評(píng)估。OPT函數(shù)的執(zhí)行情況如圖2.6所示。圖2.6 OPT流程圖3 函數(shù)調(diào)用關(guān)系圖3.1函數(shù)聲明3.1.1主要算法函數(shù)主要算法函數(shù)包括FIFO()、LRU()和OPT()三種，它們都是無(wú)返回值類型，不帶任何參數(shù)。各個(gè)函數(shù)的具體聲明情況如下：void FIFO(); /*先來(lái)先服務(wù)調(diào)度算法函數(shù)*/返回值類型：無(wú)返回值形參：無(wú)void LRU(); /*最近最久未使用算法函數(shù)*/返回值類型：無(wú)返回值形參：無(wú)void OPT(); /*最佳調(diào)度算法函數(shù)*/返回值類型：無(wú)返回值形參：無(wú)3.1.2輔助函數(shù)輔助函數(shù)是為了實(shí)現(xiàn)某些功能而特意設(shè)置的一些輔助函數(shù)。本程序主要有顯示引用串函數(shù)、顯示設(shè)計(jì)者信息函數(shù)

19、、數(shù)據(jù)加載函數(shù)和延遲時(shí)間函數(shù)，它們有的有形式參數(shù)，有的沒有，但是它們都是無(wú)返回值類型的函數(shù)。各個(gè)函數(shù)的具體聲明情況如下：void print(unsigned int t); /*顯示引用串函數(shù)*/返回值類型：無(wú)返回值形參：無(wú)符號(hào)整型void designBy(); /*顯示設(shè)計(jì)者信息*/返回值類型：無(wú)返回值形參：無(wú)void download(); /*數(shù)據(jù)加載*/返回值類型：無(wú)返回值形參：無(wú)void mDelay(unsigned int Delay); /*延遲時(shí)間*/返回值類型：無(wú)返回值形參：無(wú)符號(hào)整型3.2程序函數(shù)調(diào)用關(guān)系圖 程序以main( )函數(shù)為入口，通過主函數(shù)main( )進(jìn)行

20、調(diào)用其他函數(shù)，以此實(shí)現(xiàn)函數(shù)的各個(gè)功能。在本程序中，main( )函數(shù)調(diào)用了designBy( )函數(shù)，用以顯示設(shè)計(jì)者信息；main( )函數(shù)還分別調(diào)用了FIFO( )、LRU( )和OPT( )三種算法函數(shù)，實(shí)現(xiàn)三種算法。FIFO( )、LRU( )和OPT( )又分別調(diào)用了print( )和compute( )函數(shù)，print( )顯示了用戶輸入的頁(yè)面引用串，compute( )則主要計(jì)算了用戶選擇的算法的結(jié)果。在計(jì)算過程中，為了保證邏輯上合理，我們?cè)赾ompute( )函數(shù)中調(diào)用了mDelay( )時(shí)間延遲函數(shù)；main( )函數(shù)也調(diào)用了download( )數(shù)據(jù)加載函數(shù)，主要功能是加載用

21、戶輸入的數(shù)據(jù)以供各種算法使用。在調(diào)用download( )過程中，也調(diào)用了時(shí)間延遲函數(shù)mDelay( )。具體函數(shù)調(diào)用關(guān)系如圖3.1所示。圖3.1 函數(shù)調(diào)用關(guān)系4 測(cè)試結(jié)果4.1數(shù)據(jù)初始化 用戶根據(jù)程序提示，按照要求輸入相應(yīng)的數(shù)據(jù)。例如，本次測(cè)試中我們?cè)O(shè)置物理塊個(gè)數(shù)為4，頁(yè)面引用串個(gè)數(shù)為20，一個(gè)頁(yè)面號(hào)引用串中各個(gè)頁(yè)面號(hào)之間用空格(“ ”)隔開。值得注意的是，物理塊個(gè)數(shù)可以是幾個(gè)，幾十個(gè)，甚至幾百個(gè)，但是考慮到系統(tǒng)的效率，一般取物理塊個(gè)數(shù)在10個(gè)以內(nèi)；頁(yè)面號(hào)引用串個(gè)數(shù)也和物理塊個(gè)數(shù)一樣，頁(yè)面引用串個(gè)數(shù)取100個(gè)以內(nèi)。用戶輸入情況如圖4.1所示。圖 4.1 界面初始化4.2頁(yè)面調(diào)度算法 選擇一個(gè)

22、合適的頁(yè)面置換算法對(duì)提高內(nèi)存的利用率會(huì)有很大的幫助。當(dāng)用戶將數(shù)據(jù)初始化結(jié)束后，就要進(jìn)行頁(yè)面調(diào)度算法的選擇了。下面本書將逐一說明先進(jìn)先出算法FIFO、最近最久未使用LRU和最佳置換算法的具體調(diào)試情況。 用戶輸入的頁(yè)面引用串為：2 12 43 2 15 23 21 2 4 23 21 20 32 3 21 23 20 2 32 12，物理塊個(gè)數(shù)為：4，頁(yè)面號(hào)引用串個(gè)數(shù)為：20。FIFO算法的缺頁(yè)次數(shù)為19，置換次數(shù)為16，缺頁(yè)率為19/20，訪問率為5%；LRU算法的缺頁(yè)次數(shù)為19，置換次數(shù)為16,缺頁(yè)率為19/20,訪問率為5%；OPT算法的缺頁(yè)次數(shù)為14,置換次數(shù)為16,缺頁(yè)率為14/20，訪

23、問率為30%。4.2.1先進(jìn)先出算法 由操作系統(tǒng)維護(hù)一個(gè)所有當(dāng)前在內(nèi)存中的頁(yè)面的鏈表，最新進(jìn)入的頁(yè)面放在表尾，最久進(jìn)入的頁(yè)面放在表頭。當(dāng)發(fā)生缺頁(yè)中斷時(shí)，淘汰表頭的頁(yè)面并把新調(diào)入的頁(yè)面加到表尾。具體計(jì)算結(jié)果如圖4.2所示。圖 4.2 FIFO算法4.2.2最近最久未使用LRU 用一維數(shù)組pagepSIZE存儲(chǔ)頁(yè)面號(hào)序列，memerymSIZE是存儲(chǔ)裝入物理塊中的頁(yè)面。數(shù)組temp10標(biāo)記頁(yè)面的訪問時(shí)間。每當(dāng)使用頁(yè)面時(shí)，刷新訪問時(shí)間。發(fā)生缺頁(yè)時(shí)，就從物理塊中頁(yè)面標(biāo)記最小的一頁(yè)，調(diào)出該頁(yè)，換入所缺的頁(yè)面。具體計(jì)算結(jié)果如圖4.3所示。圖 4.3 LRU算法圖 4.4 OPT算法4.2.3最佳置換算法O

24、PT 用一維數(shù)組pagepSIZE存儲(chǔ)頁(yè)面號(hào)序列，memerymSIZE是存儲(chǔ)裝入物理塊中的頁(yè)面。數(shù)組tempmSIZE記錄物理塊中對(duì)應(yīng)頁(yè)面的最后訪問時(shí)間。每當(dāng)發(fā)生缺頁(yè)時(shí)，就從物理塊中找出最后訪問時(shí)間最大的頁(yè)面，調(diào)出該頁(yè)，換入所缺的頁(yè)面。具體計(jì)算結(jié)果如圖4.4所示。5 源程序#include <stdio.h>#include <stdlib.h>#include <conio.h>/*全局變量*/int mSIZE; /*物理塊數(shù)*/int pSIZE; /*頁(yè)面號(hào)引用串個(gè)數(shù)*/static int memery10=0; /*物理塊中的頁(yè)號(hào)*/stati

25、c int page100=0; /*頁(yè)面號(hào)引用串*/static int temp10010=0; /*輔助數(shù)組*/*置換算法函數(shù)*/void FIFO();/先進(jìn)先出置換算法void LRU();/最近最久未使用算法void OPT();/最佳置換算法/*輔助函數(shù)*/void print(unsigned int t);void designBy();/顯示設(shè)計(jì)者信息void download();/數(shù)據(jù)加載void mDelay(unsigned int Delay);/延遲時(shí)間/*主函數(shù)*/void main() int i,k,code;system("color 0F&q

26、uot;);designBy();printf("請(qǐng)按任意鍵進(jìn)行初始化操作. n");printf("n");printf(" >>>");getchar();system("cls");system("color 0B");printf("請(qǐng)輸入物理塊的個(gè)數(shù)：");scanf("%d",&mSIZE);printf("請(qǐng)輸入頁(yè)面號(hào)引用串的個(gè)數(shù)(P<=100)：");scanf("%d"

27、;,&pSIZE);puts("請(qǐng)依次輸入頁(yè)面號(hào)引用串(請(qǐng)用" "隔開)：");for(i=0;i<pSIZE;i+) scanf("%5d",&pagei);download();system("cls");system("color 0E"); do puts("輸入的頁(yè)面號(hào)引用串為：");for(k=0;k<=(pSIZE-1)/20;k+)for(i=20*k;(i<pSIZE)&&(i<20*(k+1);i+)

28、if(i+1)%20=0)|(i+1)%20)&&(i=pSIZE-1)printf("%dn",pagei);elseprintf("%d ",pagei);printf("* * * * * * * * * * * * * * * * * * * * * * *n"); printf("* 請(qǐng)選擇頁(yè)面置換算法：ttt *n");printf("* - *n"); printf("* 1.先進(jìn)先出(FIFO) 2.最近最久未使用(LRU) *n");prin

29、tf("* 3.最佳(OPT) 4.退出 *n");printf("* * * * * * * * * * * * * * * * * * * * * * *n"); printf("請(qǐng)選擇操作： bb"); scanf("%d",&code); switch(code) case 1: FIFO(); break; case 2: LRU(); break; case 3: OPT(); break; case 4:system("cls");system("color 0A

30、");designBy(); /*顯示設(shè)計(jì)者信息后退出*/printf("謝謝使用頁(yè)面置換算法演示器! n");printf("n"); exit(0);default:printf("輸入錯(cuò)誤，請(qǐng)重新輸入："); printf("按任意鍵重新選擇置換算法：>>>");getch();system("cls"); while (code!=4);getch();/*載入數(shù)據(jù)*/void download()int i;system("color 0D&quo

31、t;);printf("n");printf(" 能不能給我一首歌的時(shí)間。 n");printf("n");printf("Loading.n");printf(" ");for(i=0;i<51;i+)printf("b");for(i=0;i<50;i+)mDelay(pSIZE+mSIZE)/2);printf(">");printf("nFinish.nOK!已唱完.按任意鍵進(jìn)入置換算法選擇界面：>>>

32、");getch();/*設(shè)置延遲*/void mDelay(unsigned int Delay) unsigned int i; for(;Delay>0;Delay-) for(i=0;i<124;i+) printf(" b"); /*顯示設(shè)計(jì)者信息*/ void designBy()printf("n");printf(" 研究題目：頁(yè)面置換算法 n");printf(" 許可證號(hào)：13480144 n");printf(" 版權(quán)所有：朱 強(qiáng) n");printf

33、("n");/*顯示頁(yè)面號(hào)引用串*/void print(unsigned int t)int i,j,k,l;int flag;for(k=0;k<=(pSIZE-1)/20;k+)for(i=20*k;(i<pSIZE)&&(i<20*(k+1);i+)if(i+1)%20=0)|(i+1)%20)&&(i=pSIZE-1)printf("%dn",pagei);elseprintf("%d ",pagei);for(j=0;j<mSIZE;j+)for(i=20*k;(i&

34、lt;mSIZE+20*k)&&(i<pSIZE);i+)if(i>=j)printf(" |%d|",tempij);elseprintf(" | |");for(i=mSIZE+20*k;(i<pSIZE)&&(i<20*(k+1);i+)for(flag=0,l=0;l<mSIZE;l+)if(tempil=tempi-1l)flag+;if(flag=mSIZE)/*頁(yè)面在物理塊中*/printf(" ");elseprintf(" |%d|",

35、tempij);/*每行顯示20個(gè)*/if(i%20=0)continue;printf("n");printf("-n");printf("缺頁(yè)次數(shù)：%dtt",t+mSIZE);printf("缺頁(yè)率：%d/%dn",t+mSIZE,pSIZE);printf("置換次數(shù)：%dtt",t);printf("訪問命中率：%d%n",(pSIZE-(t+mSIZE)*100/pSIZE);printf("-n");/*計(jì)算過程延遲*/void comput

36、e()int i;printf("正在玩命計(jì)算，請(qǐng)稍候");for(i=1;i<20;i+)mDelay(15);if(i%4=0)printf("bbbbbb bbbbbb");elseprintf(".");for(i=0;i+<30;printf("b");for(i=0;i+<30;printf(" ");for(i=0;i+<30;printf("b");/*先進(jìn)先出頁(yè)面置換算法*/void FIFO() int memery10=0; in

37、t time10=0; /*記錄進(jìn)入物理塊的時(shí)間*/ int i,j,k,m; int max=0; /*記錄換出頁(yè)*/ int count=0; /*記錄置換次數(shù)*/*前mSIZE個(gè)數(shù)直接放入*/ for(i=0;i<mSIZE;i+) memeryi=pagei; timei=i; for(j=0;j<mSIZE;j+)tempij=memeryj; for(i=mSIZE;i<pSIZE;i+) /*判斷新頁(yè)面號(hào)是否在物理塊中*/ for(j=0,k=0;j<mSIZE;j+) if(memeryj!=pagei) k+; if(k=mSIZE) /*如果不在物理

38、塊中*/ count+;/*計(jì)算換出頁(yè)*/ max=time0<time1?0:1;for(m=2;m<mSIZE;m+)if(timem<timemax)max=m; memerymax=pagei; timemax=i; /*記錄該頁(yè)進(jìn)入物理塊的時(shí)間*/ for(j=0;j<mSIZE;j+)tempij=memeryj; else for(j=0;j<mSIZE;j+)tempij=memeryj; compute();print(count);/*最近最久未使用置換算法*/void LRU() int memery10=0; int flag10=0; /

39、*記錄頁(yè)面的訪問時(shí)間*/ int i,j,k,m; int max=0; /*記錄換出頁(yè)*/ int count=0; /*記錄置換次數(shù)*/*前mSIZE個(gè)數(shù)直接放入*/ for(i=0;i<mSIZE;i+) memeryi=pagei; flagi=i; for(j=0;j<mSIZE;j+)tempij=memeryj; for(i=mSIZE;i<pSIZE;i+) /*判斷新頁(yè)面號(hào)是否在物理塊中*/ for(j=0,k=0;j<mSIZE;j+) if(memeryj!=pagei) k+; else flagj=i; /*刷新該頁(yè)的訪問時(shí)間*/ if(k=m

40、SIZE) /*如果不在物理塊中*/ count+;/*計(jì)算換出頁(yè)*/ max=flag0<flag1?0:1;for(m=2;m<mSIZE;m+)if(flagm<flagmax)max=m; memerymax=pagei; flagmax=i; /*記錄該頁(yè)的訪問時(shí)間*/ for(j=0;j<mSIZE;j+)tempij=memeryj; else for(j=0;j<mSIZE;j+)tempij=memeryj; compute();print(count);/*最佳置換算法*/void OPT() int memery10=0; int next1

41、0=0; /*記錄下一次訪問時(shí)間*/ int i,j,k,l,m; int max; /*記錄換出頁(yè)*/ int count=0; /*記錄置換次數(shù)*/*前mSIZE個(gè)數(shù)直接放入*/ for(i=0;i<mSIZE;i+) memeryi=pagei; for(j=0;j<mSIZE;j+)tempij=memeryj; for(i=mSIZE;i<pSIZE;i+) /*判斷新頁(yè)面號(hào)是否在物理塊中*/ for(j=0,k=0;j<mSIZE;j+) if(memeryj!=pagei) k+; if(k=mSIZE) /*如果不在物理塊中*/ count+;/*得到物理快中各頁(yè)下一次