操作系統(tǒng)常用頁(yè)面置換算法課程設(shè)計(jì).doc

.摘 要 在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ī)訪問(wèn)的地。常見(jiàn)的頁(yè)面置換算法有先來(lái)先服務(wù)算法(FIFO)，最近最久未使用算法(LRU)和最佳適應(yīng)算法(OPT)。關(guān)鍵字：操作系統(tǒng)；FIFO；LRU；OPT；Linux.目 錄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先進(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ì)算訪問(wèn)命中率。（命中率頁(yè)面失效次數(shù)頁(yè)地址流長(zhǎng)度=1-缺頁(yè)率）1.2設(shè)計(jì)思想 在進(jìn)程運(yùn)行過(guò)程中，若期所有要訪問(wèn)的頁(yè)面不在內(nèi)存，而需把它們調(diào)入內(nèi)存，但內(nèi)存已無(wú)空閑空間時(shí)，為了保證進(jìn)程正常進(jìn)行，系統(tǒng)必須從內(nèi)存中調(diào)出一頁(yè)程序或數(shù)據(jù)送到磁盤(pán)的對(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è)很快又要被訪問(wèn)，需要將它重新調(diào)入，此時(shí)又需要再選一頁(yè)調(diào)出；而此剛被調(diào)出的頁(yè)很快又被訪問(wèn)，有需將它調(diào)入，如此頻繁地更換頁(yè)面，以致一個(gè)進(jìn)程在運(yùn)行中把大部分的時(shí)間都花費(fèi)在頁(yè)面置換工作上。通過(guò)模擬實(shí)現(xiàn)請(qǐng)求頁(yè)式存儲(chǔ)管理的幾種基本頁(yè)面置換算法，了解虛擬存儲(chǔ)技術(shù)的特點(diǎn)，掌握虛擬存儲(chǔ)請(qǐng)求頁(yè)式存儲(chǔ)管理中幾種基本頁(yè)面置換算法的基本思想和實(shí)現(xiàn)過(guò)程，并比較它們的效率。改進(jìn)頁(yè)面置換算法,可以降低頁(yè)面失敗率,從而有效地提高系統(tǒng)性能。從理論上講，應(yīng)將那些以后不再會(huì)訪問(wèn)的頁(yè)面置換出來(lái)，或把那些在較長(zhǎng)時(shí)間內(nèi)不會(huì)再訪問(wèn)的頁(yè)面調(diào)出。目前已有多種置換算法，它們都試圖更接近于理論上的目標(biāo)。1.3設(shè)計(jì)特點(diǎn) 本設(shè)計(jì)作品主要用C語(yǔ)言編寫(xiě)而成，結(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)的物理塊個(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è)過(guò)程。我通過(guò)先查找該頁(yè)面是否在頁(yè)幀中存在，若不存在則需要頁(yè)面置換，通過(guò)刷新每個(gè)頁(yè)幀的time值來(lái)得到每次的最小值來(lái)進(jìn)行頁(yè)面的置換，最小值即代表著最近最少使用的頁(yè)面。 經(jīng)過(guò)測(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)行，并提示是否再進(jìn)行類似的操作，這樣給用戶帶來(lái)了操作的方便，大大提高了學(xué)生選課的效率還有就是提示語(yǔ)言既簡(jiǎn)潔又明確，層次分明等等；當(dāng)然也有缺點(diǎn)如程序仍然存在不合理的地方，例如程序某些部分輸入錯(cuò)誤不能立刻返回改正；信息表達(dá)方式不豐富，比較單一，缺少圖片、音樂(lè)等元化表達(dá)方式。 FIFO算法總是選擇在內(nèi)存駐留時(shí)間最長(zhǎng)的一頁(yè)將其淘汰。這種算法基于CPU按線性順序訪問(wèn)地址空間的這個(gè)假設(shè)上，許多時(shí)候，CPU不是按吸納型順序訪問(wèn)地址空間的。所以，那些在內(nèi)存中停留時(shí)間最長(zhǎng)的頁(yè)往往被訪問(wèn)到。這就造成FIFO算法的缺頁(yè)率不太理想。并且，F(xiàn)IFO還有一個(gè)缺點(diǎn)就是Belady奇異現(xiàn)象。實(shí)現(xiàn)FIFO算法無(wú)需硬件提供新的幫助，只采用循環(huán)數(shù)組管理駐留集即可。OPT算法被譽(yù)為“最佳算法”，因?yàn)樗蕴麓卧L問(wèn)距當(dāng)前最遠(yuǎn)的那些頁(yè)中序號(hào)最小的一頁(yè)。所以，OPT算法得出的缺頁(yè)率是最小的。但是，OPT算法在使用前必須先得知整個(gè)訪問(wèn)串，這很難實(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è)置一個(gè)指針，稱為替換指針，使它總是指向最老的頁(yè)面。但是該算法與進(jìn)程實(shí)際運(yùn)行的規(guī)律不相符合，因?yàn)樵谶M(jìn)程中，有些頁(yè)面經(jīng)常被訪問(wèn)。1.4.2 最近最久未使用算法(LRU) 選擇最近一段時(shí)間最長(zhǎng)時(shí)間沒(méi)有被訪問(wèn)過(guò)的頁(yè)面予以淘汰。LRU算法是根據(jù)頁(yè)面調(diào)入內(nèi)存后的使用情況進(jìn)行決策。由于無(wú)法預(yù)測(cè)各頁(yè)面將來(lái)的使用情況，采取“最近的過(guò)去”作為“最近的將來(lái)”的近似。選擇最近最久未使用的頁(yè)面予以淘汰。實(shí)現(xiàn)：賦予每個(gè)頁(yè)面一個(gè)方位字段，用來(lái)記錄一個(gè)頁(yè)面自上次被訪問(wèn)以來(lái)所經(jīng)歷的時(shí)間T，當(dāng)要淘汰一個(gè)頁(yè)面的，選擇現(xiàn)有頁(yè)面中其T值最大的，即最近最久未使用的頁(yè)面予以淘汰。1.4.3最佳置換算法(OPT)最佳置換算法所選擇的被淘汰掉的頁(yè)面，將是以后永久不再使用的，或許是在最長(zhǎng)（未來(lái)）時(shí)間內(nèi)不再被訪問(wèn)的頁(yè)面。采用最佳置算法，通?？杀ＷC獲得最低的缺頁(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í)間，并將最久不被訪問(wèn)的調(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)行計(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ě)形式指明算法職能。使用偽代碼，不用拘泥于具體實(shí)現(xiàn)。它是半角式化、不標(biāo)準(zhǔn)的語(yǔ)言?？梢园颜麄€(gè)算法運(yùn)行過(guò)程的結(jié)構(gòu)用接近自然語(yǔ)言的形式（可以使用任何一種你熟悉的文字，關(guān)鍵是把程序的意思表達(dá)出來(lái)）描述出來(lái)。2.2偽代碼算法2.2.1主函數(shù)偽代碼算法 該程序是按自上而下，自頂向下的設(shè)計(jì)思想進(jìn)行設(shè)計(jì)的。程序各個(gè)功能的實(shí)現(xiàn)之間的聯(lián)系采用函數(shù)調(diào)用與函數(shù)嵌套。main()函數(shù)是整個(gè)程序的入口，程序的開(kāi)始就是從這里開(kāi)始的，然后通過(guò)main()函數(shù)調(diào)用其他函數(shù)來(lái)實(shí)現(xiàn)各個(gè)功能。具體流程如圖2.2所示。圖2.2 主函數(shù)流程圖Begin /*算法開(kāi)始*/調(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)case 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 delay0while i124退格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)行。其具體流程如圖2.3所示。2.2.3 FIFO算法的偽代碼 begin 定義變量 while imSIZEpagei0memeryi, itimeiwhile jmSIZEmemeryjtempij while ipSIZEwhile jmSIZEif 新頁(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)前頁(yè)面是否在物理塊中，若在物理塊中，則繼續(xù)讀取下一個(gè)頁(yè)面。否則，將最先進(jìn)入物理塊的頁(yè)面寫(xiě)入到物理塊中。其主要執(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 imSIZE pageimemeryi, itimeiwhile jmSIZEmemeryjtempij while imSIZE前mSIZE個(gè)數(shù)直接放入while ipSIZE while jmSIZEif 新頁(yè)面號(hào)不在物理塊中k+判斷新頁(yè)面號(hào)是否在物理塊中if k=mSIZE 則，計(jì)算換出頁(yè)，記錄該頁(yè)進(jìn)入物理塊的時(shí)間否則，max=flag0flag1?0:1memeryjtempij調(diào)用 print(置換次數(shù))End圖2.5 LRU流程圖2.2.5 OPT算法的偽代碼 begin 定義變量 while imSIZEpageimemeryi, itimeiwhile jmSIZEmemeryjtempij 前mSIZE個(gè)數(shù)直接放入 while ipSIZEwhile jmSIZEif memeryj!=pagei判斷新頁(yè)面號(hào)是否在物理塊中k+if k=mSIZE 則，計(jì)算換出頁(yè)，記錄該頁(yè)進(jìn)入物理塊的時(shí)間否則，max=flag0flag1?0:1tempij=memeryj得到物理塊中各頁(yè)下一次訪問(wèn)時(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ì)其他算法效率的評(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ù)、數(shù)據(jù)加載函數(shù)和延遲時(shí)間函數(shù)，它們有的有形式參數(shù)，有的沒(méi)有，但是它們都是無(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ù)為入口，通過(guò)主函數(shù)main( )進(jìn)行調(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ì)算過(guò)程中，為了保證邏輯上合理，我們?cè)赾ompute( )函數(shù)中調(diào)用了mDelay( )時(shí)間延遲函數(shù)；main( )函數(shù)也調(diào)用了download( )數(shù)據(jù)加載函數(shù)，主要功能是加載用戶輸入的數(shù)據(jù)以供各種算法使用。在調(diào)用download( )過(guò)程中，也調(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)之間用空格(“ ”)隔開(kāi)。值得注意的是，物理塊個(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è)合適的頁(yè)面置換算法對(duì)提高內(nèi)存的利用率會(huì)有很大的幫助。當(dāng)用戶將數(shù)據(jù)初始化結(jié)束后，就要進(jìn)行頁(yè)面調(diào)度算法的選擇了。下面本書(shū)將逐一說(shuō)明先進(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，訪問(wèn)率為5%；LRU算法的缺頁(yè)次數(shù)為19，置換次數(shù)為16,缺頁(yè)率為19/20,訪問(wèn)率為5%；OPT算法的缺頁(yè)次數(shù)為14,置換次數(shù)為16,缺頁(yè)率為14/20，訪問(wèn)率為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è)面的訪問(wèn)時(shí)間。每當(dāng)使用頁(yè)面時(shí)，刷新訪問(wèn)時(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最佳置換算法OPT 用一維數(shù)組pagepSIZE存儲(chǔ)頁(yè)面號(hào)序列，memerymSIZE是存儲(chǔ)裝入物理塊中的頁(yè)面。數(shù)組tempmSIZE記錄物理塊中對(duì)應(yīng)頁(yè)面的最后訪問(wèn)時(shí)間。每當(dāng)發(fā)生缺頁(yè)時(shí)，就從物理塊中找出最后訪問(wèn)時(shí)間最大的頁(yè)面，調(diào)出該頁(yè)，換入所缺的頁(yè)面。具體計(jì)算結(jié)果如圖4.4所示。5 源程序#include #include #include /*全局變量*/int mSIZE; /*物理塊數(shù)*/int pSIZE; /*頁(yè)面號(hào)引用串個(gè)數(shù)*/static int memery10=0; /*物理塊中的頁(yè)號(hào)*/static 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);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,&pSIZE);puts(請(qǐng)依次輸入頁(yè)面號(hào)引用串(請(qǐng)用 隔開(kāi))：);for(i=0;ipSIZE;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;(ipSIZE)&(i);getch();system(cls); while (code!=4);getch();/*載入數(shù)據(jù)*/void download()int i;system(color 0D);printf(n);printf( 能不能給我一首歌的時(shí)間。 n);printf(n);printf(Loading.n);printf( );for(i=0;i51;i+)printf(b);for(i=0;i);printf(nFinish.nOK!已唱完.按任意鍵進(jìn)入置換算法選擇界面：);getch();/*設(shè)置延遲*/void mDelay(unsigned int Delay) unsigned int i; for(;Delay0;Delay-) for(i=0;i124;i+) printf( b); /*顯示設(shè)計(jì)者信息*/ void designBy()printf(n);printf( 研究題目：頁(yè)面置換算法 n);printf( 許可證號(hào)：13480144 n);printf( 版權(quán)所有：朱 強(qiáng) n);printf(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;(ipSIZE)&(i20*(k+1);i+)if(i+1)%20=0)|(i+1)%20)&(i=pSIZE-1)printf(%dn,pagei);elseprintf(%d ,pagei);for(j=0;jmSIZE;j+)for(i=20*k;(imSIZE+20*k)&(i=j)printf( |%d|,tempij);elseprintf( | |);for(i=mSIZE+20*k;(ipSIZE)&(i20*(k+1);i+)for(flag=0,l=0;lmSIZE;l+)if(tempil=tempi-1l)flag+;if(flag=mSIZE)/*頁(yè)面在物理塊中*/printf( );elseprintf( |%d|,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(訪問(wèn)命中率：%d%n,(pSIZE-(t+mSIZE)*100/pSIZE);printf(-n);/*計(jì)算過(guò)程延遲*/void compute()int i;printf(正在玩命計(jì)算，請(qǐng)稍候);for(i=1;i20;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; int time10=0; /*記錄進(jìn)入物理塊的時(shí)間*/ int i,j,k,m; int max=0; /*記錄換出頁(yè)*/ int count=0; /*記錄置換次數(shù)*/*前mSIZE個(gè)數(shù)直接放入*/ for(i=0;imSIZE;i+) memeryi=pagei; timei=i; for(j=0;jmSIZE;j+)tempij=memeryj; for(i=mSIZE;ipSIZE;i+) /*判斷新頁(yè)面號(hào)是否在物理塊中*/ for(j=0,k=0;jmSIZE;j+) if(memeryj!=pagei) k+; if(k=mSIZE) /*如果不在物理塊中*/ count+;/*計(jì)算換出頁(yè)*/ max=time0time1?0:1;for(m=2;mmSIZE;m+)if(timemtimemax)max=m; memerymax=pagei; timemax=i; /*記錄該頁(yè)進(jìn)入物理塊的時(shí)間*/ for(j=0;jmSIZE;j+)tempij=memeryj; else for(j=0;jmSIZE;j+)tempij=memeryj; compute();print(count);/*最近最久未使用置換算法*/void LRU() int memery10=0; int flag10=0; /*記錄頁(yè)面的訪問(wèn)時(shí)間*/ int i,j,k,m; int max=0; /*記錄換出頁(yè)*/ int count=0; /*記錄置換次數(shù)*/*前mSIZE個(gè)數(shù)直接放入*/ for(i=0;imSIZE;i+) memeryi=pagei; flagi=i; for(j=0;jmSIZE;j+)tempij=memeryj; for(i=mSIZE;ipSIZE;i+) /*判斷新頁(yè)面號(hào)是否在物理塊中*/ for(j=0,k=0;jmSIZE;j+) if(memeryj!=pagei) k+; else flagj=i; /*刷新該頁(yè)的訪問(wèn)時(shí)間*/ if(k=mSIZE) /*如果不在物理塊中*/ count+;/*計(jì)算換出頁(yè)*/ max=flag0flag1?0:1;for(m=2;mmSIZE;m+)if(flagmflagmax)max=m; memerymax=pagei; flagmax=i; /*記錄該頁(yè)的訪問(wèn)時(shí)間*/ for(j=0;jmSIZE;j+)tempij=memeryj; else for(j=0;jmSIZE;j+)tempij=memeryj; compute();print(count);/*最佳置換算法*/void OPT() int memery10=0; int next10=0; /*記錄下一次訪問(wèn)時(shí)間*/ int i,j,k,l,m; int max; /*記錄換出頁(yè)*/ int count=0; /*記錄置換次數(shù)*/*前mSIZE個(gè)數(shù)直接放入*/ for(i=0;imSIZE;i+) memeryi=pagei; for(j=0;jmSIZE;j+)tempij=memeryj; for(i=mSIZE;ipSIZE;i+) /*判斷新頁(yè)面號(hào)是否在物理塊中*/ for(j=0,k=0;jmSIZE;j+) if(memeryj!=pagei) k+; if(k=mSIZE) /*如果不在物理塊中*/ count+;/*得到物理快中各頁(yè)下一次訪問(wèn)時(shí)間*/for(m=0;mmSIZE;m+)for(l=i+1;l=next1?0:1;for(m=2;mnextmax)max=m;/*下一次訪問(wèn)時(shí)間都為p