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

.摘 要 在linux中，為了提高內(nèi)存利用率，提供了內(nèi)外存進程對換機制，內(nèi)存空間的分配和回收均以頁為單位進行，一個進程只需要將其一部分調(diào)入內(nèi)存便可運行；當操作系統(tǒng)發(fā)生缺頁中斷時，必須在內(nèi)存選擇一個頁面將其移出內(nèi)存，以便為即將調(diào)入的頁面讓出空間。因而引入一種用來選擇淘汰哪一頁的算法頁面置換算法。頁面置換算法是操作系統(tǒng)中虛擬存儲管理的一個重要部分。頁面置換算法在具有層次結(jié)構(gòu)存儲器的計算機中，為用戶提供一個比主存儲器容量大得多的可隨機訪問的地。常見的頁面置換算法有先來先服務(wù)算法(FIFO)，最近最久未使用算法(LRU)和最佳適應(yīng)算法(OPT)。關(guān)鍵字：操作系統(tǒng)；FIFO；LRU；OPT；Linux.目 錄1 緒論11.1 設(shè)計任務(wù)11.2設(shè)計思想11.3設(shè)計特點11.4基礎(chǔ)知識21.4.1 先進先出置換算法(FIFO)21.4.2 最近最久未使用算法(LRU)31.4.3最佳置換算法(OPT)32 各模塊偽代碼算法42.1偽代碼概念42.2偽代碼算法42.2.1主函數(shù)偽代碼算法42.2.2延遲時間函數(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 測試結(jié)果144.1數(shù)據(jù)初始化144.2頁面調(diào)度算法144.2.1先進先出算法154.2.2最近最久未使用LRU154.2.3最佳置換算法OPT175 源程序186 設(shè)計總結(jié)30參考文獻31致 謝321 緒論1.1 設(shè)計任務(wù) 1、了解UNIX的命令及使用格式，熟悉UNIX/LINUX的常用基本命令，練習(xí)并掌握UNIX提供的vi編輯器來編譯C程序，學(xué)會利用gcc、gdb編譯、調(diào)試C程序。 2、設(shè)計一個虛擬存儲區(qū)和內(nèi)存工作區(qū)，并使用最佳淘汰算法（OPT）、先進先出算法（FIFO）、最近最久未使用算法（LRU）計算訪問命中率。（命中率頁面失效次數(shù)頁地址流長度=1-缺頁率）1.2設(shè)計思想 在進程運行過程中，若期所有要訪問的頁面不在內(nèi)存，而需把它們調(diào)入內(nèi)存，但內(nèi)存已無空閑空間時，為了保證進程正常進行，系統(tǒng)必須從內(nèi)存中調(diào)出一頁程序或數(shù)據(jù)送到磁盤的對換區(qū)中。但應(yīng)將哪個頁面調(diào)出，須根據(jù)一定的算法來確定。通常，把選擇換出頁面的算法稱為頁面置換算法。置換算法的好壞將直接影響到系統(tǒng)的性能。 不適當?shù)乃惴赡軙?dǎo)致進程發(fā)生“抖動”，即剛被換出的頁很快又要被訪問，需要將它重新調(diào)入，此時又需要再選一頁調(diào)出；而此剛被調(diào)出的頁很快又被訪問，有需將它調(diào)入，如此頻繁地更換頁面，以致一個進程在運行中把大部分的時間都花費在頁面置換工作上。通過模擬實現(xiàn)請求頁式存儲管理的幾種基本頁面置換算法，了解虛擬存儲技術(shù)的特點，掌握虛擬存儲請求頁式存儲管理中幾種基本頁面置換算法的基本思想和實現(xiàn)過程，并比較它們的效率。改進頁面置換算法,可以降低頁面失敗率,從而有效地提高系統(tǒng)性能。從理論上講，應(yīng)將那些以后不再會訪問的頁面置換出來，或把那些在較長時間內(nèi)不會再訪問的頁面調(diào)出。目前已有多種置換算法，它們都試圖更接近于理論上的目標。1.3設(shè)計特點 本設(shè)計作品主要用C語言編寫而成，結(jié)構(gòu)簡單，語言易懂，條理清晰。本作品兼容性也非常的高，可以在各種可以編譯C語言的編譯軟件上運行，并能夠在cygwin中運行，經(jīng)多次調(diào)試，暫時未發(fā)現(xiàn)有何不足。本程序的另一個優(yōu)點是，程序可以計算大數(shù)量數(shù)據(jù)。如，本程序可以計算的最大物理塊個數(shù)達到了10000個，用戶輸入的頁面引用串個數(shù)也能達到10000個以上。但是，實際生活中系統(tǒng)的物理塊個數(shù)一般不會達到10000個。因此，我們在提示用戶輸入頁面引用串個數(shù)是，只提示最大輸入100個。但是代碼不足在于使用到了較多的static全局變量使得整個代碼質(zhì)量不是很好，而且也只是簡單的根據(jù)算法設(shè)計來模擬實現(xiàn)整個過程。我通過先查找該頁面是否在頁幀中存在，若不存在則需要頁面置換，通過刷新每個頁幀的time值來得到每次的最小值來進行頁面的置換，最小值即代表著最近最少使用的頁面。 經(jīng)過測試，這個系統(tǒng)已經(jīng)達到了題目中的全部要求。這個程序有很多優(yōu)點有一個是界面簡明，簡潔明了的程序菜單；一個是智能化的模塊設(shè)計，減少了許多人工操作，如功能模塊操作結(jié)束后，均會返回主菜單進行下一模板的運行，并提示是否再進行類似的操作，這樣給用戶帶來了操作的方便，大大提高了學(xué)生選課的效率還有就是提示語言既簡潔又明確，層次分明等等；當然也有缺點如程序仍然存在不合理的地方，例如程序某些部分輸入錯誤不能立刻返回改正；信息表達方式不豐富，比較單一，缺少圖片、音樂等元化表達方式。 FIFO算法總是選擇在內(nèi)存駐留時間最長的一頁將其淘汰。這種算法基于CPU按線性順序訪問地址空間的這個假設(shè)上，許多時候，CPU不是按吸納型順序訪問地址空間的。所以，那些在內(nèi)存中停留時間最長的頁往往被訪問到。這就造成FIFO算法的缺頁率不太理想。并且，F(xiàn)IFO還有一個缺點就是Belady奇異現(xiàn)象。實現(xiàn)FIFO算法無需硬件提供新的幫助，只采用循環(huán)數(shù)組管理駐留集即可。OPT算法被譽為“最佳算法”，因為他淘汰下次訪問距當前最遠的那些頁中序號最小的一頁。所以，OPT算法得出的缺頁率是最小的。但是，OPT算法在使用前必須先得知整個訪問串，這很難實現(xiàn)。因此，OPT算法知識一種概念中的算法。LRU算法的實現(xiàn)耗費較高，并且需要硬件的支持，但是效果較好。就缺頁率而言，OPT算法最佳，F(xiàn)IFO算法最差。1.4基礎(chǔ)知識1.4.1 先進先出置換算法(FIFO) FIFO算法是最早出現(xiàn)的算法。該算法總是淘汰最先進入內(nèi)存的頁面，即選擇在內(nèi)存駐留時間最久的頁面予以淘汰。該算法實現(xiàn)簡單，只需要把一個進程已調(diào)入內(nèi)存的頁面按先來后次序鏈接成一個隊列，并設(shè)置一個指針，稱為替換指針，使它總是指向最老的頁面。但是該算法與進程實際運行的規(guī)律不相符合，因為在進程中，有些頁面經(jīng)常被訪問。1.4.2 最近最久未使用算法(LRU) 選擇最近一段時間最長時間沒有被訪問過的頁面予以淘汰。LRU算法是根據(jù)頁面調(diào)入內(nèi)存后的使用情況進行決策。由于無法預(yù)測各頁面將來的使用情況，采取“最近的過去”作為“最近的將來”的近似。選擇最近最久未使用的頁面予以淘汰。實現(xiàn)：賦予每個頁面一個方位字段，用來記錄一個頁面自上次被訪問以來所經(jīng)歷的時間T，當要淘汰一個頁面的，選擇現(xiàn)有頁面中其T值最大的，即最近最久未使用的頁面予以淘汰。1.4.3最佳置換算法(OPT)最佳置換算法所選擇的被淘汰掉的頁面，將是以后永久不再使用的，或許是在最長（未來）時間內(nèi)不再被訪問的頁面。采用最佳置算法，通?？杀ＷC獲得最低的缺頁率。本模擬算法中，最佳頁面置換算法實現(xiàn)所采用的思想是：循環(huán)讀入每個頁表項，若該頁表在內(nèi)存中，則讀取下一個頁表項。若頁表不存在內(nèi)存中：一種情況是內(nèi)存不滿，則將頁表放入內(nèi)存中；若內(nèi)存塊已滿，剛分別計算內(nèi)存中各個頁表再次被使用的時間，并將最久不被訪問的調(diào)出，放入當前讀入頁表項。.2 各模塊偽代碼算法 根據(jù)程序提示，用戶先將需要計算的頁面號引用串，物理塊數(shù)量和引用串個數(shù)輸入到文件流中。待程序加載數(shù)據(jù)完成后，用戶繼續(xù)選擇頁面置換算法的類型，程序根據(jù)用戶輸入的信息來判斷采用哪一種算法進行計算。結(jié)構(gòu)如圖2.1所示。圖 2.1 總體結(jié)構(gòu)圖2.1偽代碼概念 偽代碼（英語：pseudocode），又稱為虛擬代碼，是高層次描述算法的一種方法。使用偽代碼的目的是讓被描述的算法可以容易地以任何一種編程語言（Pascal，C，Java，etc）實現(xiàn)。因此，偽代碼必須結(jié)構(gòu)清晰、代碼簡單、可讀性好，介于自然語言與編程語言之間。以編程語言的書寫形式指明算法職能。使用偽代碼，不用拘泥于具體實現(xiàn)。它是半角式化、不標準的語言?？梢园颜麄€算法運行過程的結(jié)構(gòu)用接近自然語言的形式（可以使用任何一種你熟悉的文字，關(guān)鍵是把程序的意思表達出來）描述出來。2.2偽代碼算法2.2.1主函數(shù)偽代碼算法 該程序是按自上而下，自頂向下的設(shè)計思想進行設(shè)計的。程序各個功能的實現(xiàn)之間的聯(lián)系采用函數(shù)調(diào)用與函數(shù)嵌套。main()函數(shù)是整個程序的入口，程序的開始就是從這里開始的，然后通過main()函數(shù)調(diào)用其他函數(shù)來實現(xiàn)各個功能。具體流程如圖2.2所示。圖2.2 主函數(shù)流程圖Begin /*算法開始*/調(diào)用designBy()顯示出設(shè)計者信息Scanf mSIZE，pSIZE，page100 /*mSIZE表示物理塊，pSIZE表示頁面號引用串個數(shù)，page100表示一個引用串的頁面號*/do Printf pageiScanf code /*code是一個標記，用來判斷用戶輸入是否符合要求*/Switch(code)case 1: FIFO() /*先進先出算法*/case 2: LRU() /*最近最久未使用算法*/case 3: OPT() /*最佳置換算法*/case 4: exit(0) /*退出程序*/default: 重新輸入while(code!=4)Getch（用戶輸入）End2.2.2延遲時間函數(shù)偽代碼算法begin變量定義while delay0while i124退格end圖2.3 延遲時間函數(shù)流程圖 延遲時間函數(shù)主要由兩個for循環(huán)構(gòu)成。延遲時間函數(shù)在程序中主要起延遲時間的作用，相當于一個定時器，給程序數(shù)據(jù)加載，數(shù)據(jù)處理等提供時間保證。使程序能夠正常的進行。其具體流程如圖2.3所示。2.2.3 FIFO算法的偽代碼 begin 定義變量 while imSIZEpagei0memeryi, itimeiwhile jmSIZEmemeryjtempij while ipSIZEwhile jmSIZEif 新頁面號不在物理塊中k+if k=mSIZE 則，計算換出頁，記錄該頁進入物理塊的時間否則，tempij=memeryjprint 置換次數(shù)End FIFO算法是操作系統(tǒng)中最簡單最容易實現(xiàn)的一種頁面置換算法，它的實現(xiàn)主要運用了兩個循環(huán)結(jié)構(gòu)。第一個循環(huán)的功能是將頁面串中的前mSIZE頁面直接放入物理塊中；第二個循環(huán)主要判斷當前頁面是否在物理塊中，若在物理塊中，則繼續(xù)讀取下一個頁面。否則，將最先進入物理塊的頁面寫入到物理塊中。其主要執(zhí)行流程如圖2.4所示。2.2.4 LRU算法的偽代碼 LRU算法是將最近進入物理塊且未使用的頁面首先換出物理塊。LRU函數(shù)主要也運用了兩個循環(huán)來實現(xiàn)其算法，首先將前mSIZE個頁面置換到物理塊中，然后再按具體算法進行置換頁面。其執(zhí)行流程如圖2.5所示。圖2.4 FIFO流程圖 begin 定義變量 while imSIZE pageimemeryi, itimeiwhile jmSIZEmemeryjtempij while imSIZE前mSIZE個數(shù)直接放入while ipSIZE while jmSIZEif 新頁面號不在物理塊中k+判斷新頁面號是否在物理塊中if k=mSIZE 則，計算換出頁，記錄該頁進入物理塊的時間否則，max=flag0flag1?0:1memeryjtempij調(diào)用 print(置換次數(shù))End圖2.5 LRU流程圖2.2.5 OPT算法的偽代碼 begin 定義變量 while imSIZEpageimemeryi, itimeiwhile jmSIZEmemeryjtempij 前mSIZE個數(shù)直接放入 while ipSIZEwhile jmSIZEif memeryj!=pagei判斷新頁面號是否在物理塊中k+if k=mSIZE 則，計算換出頁，記錄該頁進入物理塊的時間否則，max=flag0flag1?0:1tempij=memeryj得到物理塊中各頁下一次訪問時間if memerym=page1退出循環(huán)nextm=1調(diào)用 print(置換次數(shù))End OPT算法是將內(nèi)存中最長時間內(nèi)不會用的頁面置換出去，這種算法的優(yōu)點是系統(tǒng)利用率，內(nèi)存利用率都非常的高。但是這種算法目前無法實現(xiàn)，因為實際中，系統(tǒng)根本無法預(yù)知哪一個頁面最先執(zhí)行，哪一個頁面最后執(zhí)行，各個頁面的執(zhí)行順序都無法確定根本就不能確定頁面換出的次序。OPT算法主要用于對其他算法效率的評估。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()三種，它們都是無返回值類型，不帶任何參數(shù)。各個函數(shù)的具體聲明情況如下：void FIFO(); /*先來先服務(wù)調(diào)度算法函數(shù)*/返回值類型：無返回值形參：無void LRU(); /*最近最久未使用算法函數(shù)*/返回值類型：無返回值形參：無void OPT(); /*最佳調(diào)度算法函數(shù)*/返回值類型：無返回值形參：無3.1.2輔助函數(shù)輔助函數(shù)是為了實現(xiàn)某些功能而特意設(shè)置的一些輔助函數(shù)。本程序主要有顯示引用串函數(shù)、顯示設(shè)計者信息函數(shù)、數(shù)據(jù)加載函數(shù)和延遲時間函數(shù)，它們有的有形式參數(shù)，有的沒有，但是它們都是無返回值類型的函數(shù)。各個函數(shù)的具體聲明情況如下：void print(unsigned int t); /*顯示引用串函數(shù)*/返回值類型：無返回值形參：無符號整型void designBy(); /*顯示設(shè)計者信息*/返回值類型：無返回值形參：無void download(); /*數(shù)據(jù)加載*/返回值類型：無返回值形參：無void mDelay(unsigned int Delay); /*延遲時間*/返回值類型：無返回值形參：無符號整型3.2程序函數(shù)調(diào)用關(guān)系圖 程序以main( )函數(shù)為入口，通過主函數(shù)main( )進行調(diào)用其他函數(shù)，以此實現(xiàn)函數(shù)的各個功能。在本程序中，main( )函數(shù)調(diào)用了designBy( )函數(shù)，用以顯示設(shè)計者信息；main( )函數(shù)還分別調(diào)用了FIFO( )、LRU( )和OPT( )三種算法函數(shù)，實現(xiàn)三種算法。FIFO( )、LRU( )和OPT( )又分別調(diào)用了print( )和compute( )函數(shù)，print( )顯示了用戶輸入的頁面引用串，compute( )則主要計算了用戶選擇的算法的結(jié)果。在計算過程中，為了保證邏輯上合理，我們在compute( )函數(shù)中調(diào)用了mDelay( )時間延遲函數(shù)；main( )函數(shù)也調(diào)用了download( )數(shù)據(jù)加載函數(shù)，主要功能是加載用戶輸入的數(shù)據(jù)以供各種算法使用。在調(diào)用download( )過程中，也調(diào)用了時間延遲函數(shù)mDelay( )。具體函數(shù)調(diào)用關(guān)系如圖3.1所示。圖3.1 函數(shù)調(diào)用關(guān)系4 測試結(jié)果4.1數(shù)據(jù)初始化 用戶根據(jù)程序提示，按照要求輸入相應(yīng)的數(shù)據(jù)。例如，本次測試中我們設(shè)置物理塊個數(shù)為4，頁面引用串個數(shù)為20，一個頁面號引用串中各個頁面號之間用空格(“ ”)隔開。值得注意的是，物理塊個數(shù)可以是幾個，幾十個，甚至幾百個，但是考慮到系統(tǒng)的效率，一般取物理塊個數(shù)在10個以內(nèi)；頁面號引用串個數(shù)也和物理塊個數(shù)一樣，頁面引用串個數(shù)取100個以內(nèi)。用戶輸入情況如圖4.1所示。圖 4.1 界面初始化4.2頁面調(diào)度算法 選擇一個合適的頁面置換算法對提高內(nèi)存的利用率會有很大的幫助。當用戶將數(shù)據(jù)初始化結(jié)束后，就要進行頁面調(diào)度算法的選擇了。下面本書將逐一說明先進先出算法FIFO、最近最久未使用LRU和最佳置換算法的具體調(diào)試情況。 用戶輸入的頁面引用串為：2 12 43 2 15 23 21 2 4 23 21 20 32 3 21 23 20 2 32 12，物理塊個數(shù)為：4，頁面號引用串個數(shù)為：20。FIFO算法的缺頁次數(shù)為19，置換次數(shù)為16，缺頁率為19/20，訪問率為5%；LRU算法的缺頁次數(shù)為19，置換次數(shù)為16,缺頁率為19/20,訪問率為5%；OPT算法的缺頁次數(shù)為14,置換次數(shù)為16,缺頁率為14/20，訪問率為30%。4.2.1先進先出算法 由操作系統(tǒng)維護一個所有當前在內(nèi)存中的頁面的鏈表，最新進入的頁面放在表尾，最久進入的頁面放在表頭。當發(fā)生缺頁中斷時，淘汰表頭的頁面并把新調(diào)入的頁面加到表尾。具體計算結(jié)果如圖4.2所示。圖 4.2 FIFO算法4.2.2最近最久未使用LRU 用一維數(shù)組pagepSIZE存儲頁面號序列，memerymSIZE是存儲裝入物理塊中的頁面。數(shù)組temp10標記頁面的訪問時間。每當使用頁面時，刷新訪問時間。發(fā)生缺頁時，就從物理塊中頁面標記最小的一頁，調(diào)出該頁，換入所缺的頁面。具體計算結(jié)果如圖4.3所示。圖 4.3 LRU算法圖 4.4 OPT算法4.2.3最佳置換算法OPT 用一維數(shù)組pagepSIZE存儲頁面號序列，memerymSIZE是存儲裝入物理塊中的頁面。數(shù)組tempmSIZE記錄物理塊中對應(yīng)頁面的最后訪問時間。每當發(fā)生缺頁時，就從物理塊中找出最后訪問時間最大的頁面，調(diào)出該頁，換入所缺的頁面。具體計算結(jié)果如圖4.4所示。5 源程序#include #include #include /*全局變量*/int mSIZE; /*物理塊數(shù)*/int pSIZE; /*頁面號引用串個數(shù)*/static int memery10=0; /*物理塊中的頁號*/static int page100=0; /*頁面號引用串*/static int temp10010=0; /*輔助數(shù)組*/*置換算法函數(shù)*/void FIFO();/先進先出置換算法void LRU();/最近最久未使用算法void OPT();/最佳置換算法/*輔助函數(shù)*/void print(unsigned int t);void designBy();/顯示設(shè)計者信息void download();/數(shù)據(jù)加載void mDelay(unsigned int Delay);/延遲時間/*主函數(shù)*/void main() int i,k,code;system(color 0F);designBy();printf(請按任意鍵進行初始化操作. n);printf(n);printf( );getchar();system(cls);system(color 0B);printf(請輸入物理塊的個數(shù)：);scanf(%d,&mSIZE);printf(請輸入頁面號引用串的個數(shù)(P=100)：);scanf(%d,&pSIZE);puts(請依次輸入頁面號引用串(請用 隔開)：);for(i=0;ipSIZE;i+) scanf(%5d,&pagei);download();system(cls);system(color 0E); do puts(輸入的頁面號引用串為：);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( 能不能給我一首歌的時間。 n);printf(n);printf(Loading.n);printf( );for(i=0;i51;i+)printf(b);for(i=0;i);printf(nFinish.nOK!已唱完.按任意鍵進入置換算法選擇界面：);getch();/*設(shè)置延遲*/void mDelay(unsigned int Delay) unsigned int i; for(;Delay0;Delay-) for(i=0;i124;i+) printf( b); /*顯示設(shè)計者信息*/ void designBy()printf(n);printf( 研究題目：頁面置換算法 n);printf( 許可證號：13480144 n);printf( 版權(quán)所有：朱 強 n);printf(n);/*顯示頁面號引用串*/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)/*頁面在物理塊中*/printf( );elseprintf( |%d|,tempij);/*每行顯示20個*/if(i%20=0)continue;printf(n);printf(-n);printf(缺頁次數(shù)：%dtt,t+mSIZE);printf(缺頁率：%d/%dn,t+mSIZE,pSIZE);printf(置換次數(shù)：%dtt,t);printf(訪問命中率：%d%n,(pSIZE-(t+mSIZE)*100/pSIZE);printf(-n);/*計算過程延遲*/void compute()int i;printf(正在玩命計算，請稍候);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);/*先進先出頁面置換算法*/void FIFO() int memery10=0; int time10=0; /*記錄進入物理塊的時間*/ int i,j,k,m; int max=0; /*記錄換出頁*/ int count=0; /*記錄置換次數(shù)*/*前mSIZE個數(shù)直接放入*/ for(i=0;imSIZE;i+) memeryi=pagei; timei=i; for(j=0;jmSIZE;j+)tempij=memeryj; for(i=mSIZE;ipSIZE;i+) /*判斷新頁面號是否在物理塊中*/ for(j=0,k=0;jmSIZE;j+) if(memeryj!=pagei) k+; if(k=mSIZE) /*如果不在物理塊中*/ count+;/*計算換出頁*/ max=time0time1?0:1;for(m=2;mmSIZE;m+)if(timemtimemax)max=m; memerymax=pagei; timemax=i; /*記錄該頁進入物理塊的時間*/ 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; /*記錄頁面的訪問時間*/ int i,j,k,m; int max=0; /*記錄換出頁*/ int count=0; /*記錄置換次數(shù)*/*前mSIZE個數(shù)直接放入*/ for(i=0;imSIZE;i+) memeryi=pagei; flagi=i; for(j=0;jmSIZE;j+)tempij=memeryj; for(i=mSIZE;ipSIZE;i+) /*判斷新頁面號是否在物理塊中*/ for(j=0,k=0;jmSIZE;j+) if(memeryj!=pagei) k+; else flagj=i; /*刷新該頁的訪問時間*/ if(k=mSIZE) /*如果不在物理塊中*/ count+;/*計算換出頁*/ max=flag0flag1?0:1;for(m=2;mmSIZE;m+)if(flagmflagmax)max=m; memerymax=pagei; flagmax=i; /*記錄該頁的訪問時間*/ 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; /*記錄下一次訪問時間*/ int i,j,k,l,m; int max; /*記錄換出頁*/ int count=0; /*記錄置換次數(shù)*/*前mSIZE個數(shù)直接放入*/ for(i=0;imSIZE;i+) memeryi=pagei; for(j=0;jmSIZE;j+)tempij=memeryj; for(i=mSIZE;ipSIZE;i+) /*判斷新頁面號是否在物理塊中*/ for(j=0,k=0;jmSIZE;j+) if(memeryj!=pagei) k+; if(k=mSIZE) /*如果不在物理塊中*/ count+;/*得到物理快中各頁下一次訪問時間*/for(m=0;mmSIZE;m+)for(l=i+1;l=next1?0:1;for(m=2;mnextmax)max=m;/*下一次訪問時間都為p