1、摘 要 在linux中，為了提高內存利用率，提供(tgng)了內外存進程對換機制，內存空間的分配和回收均以頁為單位進行，一個進程只需要將其一部分調入內存便可運行；當操作系統發生(fshng)缺頁中斷時，必須在內存選擇(xunz)一個頁面將其移出內存，以便為即將調入的頁面讓出空間。因而引入一種用來選擇淘汰哪一頁的算法頁面置換算法。 HYPERLINK /lemma/ShowInnerLink.htm?lemmaId=8061559 t /_blank 頁面置換算法是操作系統中虛擬存儲管理的一個重要部分。頁面置換算法在具有 HYPERLINK /lemma/ShowInnerLink.htm?le

2、mmaId=7999774&ss_c=ssc.citiao.link t /_blank 層次結構存儲器的 HYPERLINK /lemma/ShowInnerLink.htm?lemmaId=430164 t /_blank 計算機中，為用戶提供一個比 HYPERLINK /lemma/ShowInnerLink.htm?lemmaId=42463046&ss_c=ssc.citiao.link t /_blank 主存儲器容量大得多的可隨機訪問的地。常見的頁面置換算法有先來先服務算法(FIFO)，最近最久未使用算法(LRU)和最佳適應算法(OPT)。關鍵字：操作系統；FIFO；LRU；OP

3、T；Linux目 錄TOC o 1-3 h z u HYPERLINK l _Toc2721 1 緒論(xln) PAGEREF _Toc2721 1 HYPERLINK l _Toc10642 1.1 設計(shj)任務 PAGEREF _Toc10642 1 HYPERLINK l _Toc14254 1.2設計(shj)思想 PAGEREF _Toc14254 1 HYPERLINK l _Toc28605 1.3設計特點 PAGEREF _Toc28605 1 HYPERLINK l _Toc30425 1.4基礎知識 PAGEREF _Toc30425 2 HYPERLINK l _

4、Toc4190 1.4.1 先進先出置換算法(FIFO) PAGEREF _Toc4190 2 HYPERLINK l _Toc16689 1.4.2 最近最久未使用算法(LRU) PAGEREF _Toc16689 3 HYPERLINK l _Toc22721 1.4.3最佳置換算法(OPT) PAGEREF _Toc22721 3 HYPERLINK l _Toc28008 2 各模塊偽代碼算法 PAGEREF _Toc28008 4 HYPERLINK l _Toc20760 2.1偽代碼概念 PAGEREF _Toc20760 4 HYPERLINK l _Toc26122 2.2偽

5、代碼算法 PAGEREF _Toc26122 4 HYPERLINK l _Toc14429 2.2.1主函數偽代碼算法 PAGEREF _Toc14429 4 HYPERLINK l _Toc23133 2.2.2延遲時間函數偽代碼算法 PAGEREF _Toc23133 6 HYPERLINK l _Toc1063 2.2.3 FIFO算法的偽代碼 PAGEREF _Toc1063 7 HYPERLINK l _Toc11335 2.2.4 LRU算法的偽代碼 PAGEREF _Toc11335 7 HYPERLINK l _Toc24925 2.2.5 OPT算法的偽代碼 PAGEREF

6、 _Toc24925 10 HYPERLINK l _Toc2089 3 函數調用關系圖 PAGEREF _Toc2089 12 HYPERLINK l _Toc27786 3.1函數聲明 PAGEREF _Toc27786 12 HYPERLINK l _Toc29766 3.1.1主要算法函數 PAGEREF _Toc29766 12 HYPERLINK l _Toc16616 3.1.2輔助函數 PAGEREF _Toc16616 12 HYPERLINK l _Toc26672 3.2程序(chngx)函數調用關系圖 PAGEREF _Toc26672 13 HYPERLINK l _

7、Toc10751 4 測試(csh)結果 PAGEREF _Toc10751 14 HYPERLINK l _Toc31453 4.1數據(shj)初始化 PAGEREF _Toc31453 14 HYPERLINK l _Toc29227 4.2頁面調度算法 PAGEREF _Toc29227 14 HYPERLINK l _Toc11020 4.2.1先進先出算法 PAGEREF _Toc11020 15 HYPERLINK l _Toc4514 4.2.2最近最久未使用LRU PAGEREF _Toc4514 15 HYPERLINK l _Toc26959 4.2.3最佳置換算法OPT

8、 PAGEREF _Toc26959 17 HYPERLINK l _Toc17063 5 源程序 PAGEREF _Toc17063 18 HYPERLINK l _Toc12996 6 設計總結 PAGEREF _Toc12996 30 HYPERLINK l _Toc5510 參考文獻 PAGEREF _Toc5510 31 HYPERLINK l _Toc612 致 謝 PAGEREF _Toc612 321 緒論(xln)1.1 設計(shj)任務 1、了解(lioji)UNIX的命令及使用格式，熟悉UNIX/LINUX的常用基本命令，練習并掌握UNIX提供的vi編輯器來編譯C程序，

9、學會利用gcc、gdb編譯、調試C程序。 2、設計一個虛擬存儲區和內存工作區，并使用最佳淘汰算法（OPT）、先進先出算法（FIFO）、最近最久未使用算法（LRU）計算訪問命中率。（命中率頁面失效次數頁地址流長度=1-缺頁率）1.2設計思想 在進程運行過程中，若期所有要訪問的頁面不在內存，而需把它們調入內存，但內存已無空閑空間時，為了保證進程正常進行，系統必須從內存中調出一頁程序或數據送到磁盤的對換區中。但應將哪個頁面調出，須根據一定的算法來確定。通常，把選擇換出頁面的算法稱為頁面置換算法。置換算法的好壞將直接影響到系統的性能。 不適當的算法可能會導致進程發生“抖動”，即剛被換出的頁很快又要被訪

10、問，需要將它重新調入，此時又需要再選一頁調出；而此剛被調出的頁很快又被訪問，有需將它調入，如此頻繁地更換頁面，以致一個進程在運行中把大部分的時間都花費在頁面置換工作上。通過 HYPERLINK /lemma/ShowInnerLink.htm?lemmaId=249700 t /_blank 模擬實現請求頁式 HYPERLINK /lemma/ShowInnerLink.htm?lemmaId=276803&ss_c=ssc.citiao.link t /_blank 存儲管理的幾種 HYPERLINK /lemma/ShowInnerLink.htm?lemmaId=221511 t /_b

11、lank 基本頁面置換算法，了解 HYPERLINK /lemma/ShowInnerLink.htm?lemmaId=70229363&ss_c=ssc.citiao.link t /_blank 虛擬存儲技術的特點，掌握 HYPERLINK /lemma/ShowInnerLink.htm?lemmaId=170727&ss_c=ssc.citiao.link t /_blank 虛擬存儲請求頁式存儲管理中幾種基本頁面置換算法的基本思想和實現過程，并比較它們的 HYPERLINK /lemma/ShowInnerLink.htm?lemmaId=2155315 t /_blank 效率。改

12、進頁面置換算法,可以降低頁面失敗率,從而有效地提高系統性能。從理論上講，應將那些以后不再會訪問的頁面置換出來，或把那些在較長時間內不會再訪問的頁面調出。目前已有多種置換算法，它們都試圖更接近于理論上的目標。1.3設計特點 本設計作品主要用C語言編寫而成，結構簡單，語言易懂，條理清晰。本作品兼容性也非常的高，可以在各種可以編譯C語言的編譯軟件上運行，并能夠在cygwin中運行，經多次調試，暫時未發現有何不足。本程序的另一個優點是，程序可以計算大數量數據。如，本程序可以計算的最大物理塊個數達到了10000個，用戶輸入的頁面引用串個數也能達到10000個以上。但是，實際生活中系統的物理塊個數一般不會

13、達到10000個。因此，我們在提示用戶輸入頁面引用串個數是，只提示最大輸入100個。但是代碼不足在于使用到了較多的static全局變量使得整個代碼質量不是很好，而且也只是簡單的根據算法設計來模擬實現整個過程。我通過先查找該頁面是否在頁幀中存在，若不存在則需要頁面置換，通過刷新每個頁幀的time值來得到每次的最小值來進行頁面的置換，最小值即代表著最近最少使用的頁面。 經過測試，這個系統已經達到了題目中的全部要求。這個程序有很多優點有一個是界面簡明，簡潔明了的程序菜單(ci dn)；一個是智能化的模塊設計，減少了許多人工操作，如功能模塊操作結束后，均會返回主菜單進行下一模板的運行，并提示是否再進行

14、類似的操作，這樣給用戶帶來了操作的方便，大大提高了學生選課的效率還有就是提示語言既簡潔又明確，層次分明等等；當然也有缺點如程序仍然存在不合理的地方，例如程序某些部分輸入錯誤不能立刻返回改正；信息表達方式不豐富，比較單一，缺少圖片、音樂等元化表達方式。 FIFO算法總是選擇在內存駐留時間最長的一頁將其淘汰。這種算法基于CPU按線性順序訪問地址空間的這個假設上，許多時候，CPU不是按吸納型順序訪問地址空間的。所以，那些在內存中停留時間最長的頁往往被訪問到。這就造成FIFO算法的缺頁率不太理想。并且，FIFO還有一個缺點就是Belady奇異現象。實現FIFO算法無需硬件提供新的幫助，只采用循環數組管

15、理駐留集即可。OPT算法被譽為“最佳算法”，因為他淘汰下次訪問距當前最遠的那些頁中序號最小的一頁。所以，OPT算法得出的缺頁率是最小的。但是，OPT算法在使用前必須先得知整個訪問串，這很難實現。因此，OPT算法知識一種概念中的算法。LRU算法的實現耗費(hofi)較高，并且需要硬件的支持，但是效果較好。就缺頁率而言，OPT算法最佳，FIFO算法最差。1.4基礎知識1.4.1 先進先出置換(zhhun)算法(FIFO) FIFO算法是最早出現的算法。該算法總是淘汰最先進入內存的頁面，即選擇在內存駐留時間最久的頁面予以淘汰。該算法實現簡單，只需要把一個進程已調入內存的頁面按先來后次序鏈接成一個隊列

16、，并設置一個指針，稱為替換指針，使它總是指向最老的頁面。但是該算法與進程實際運行的規律不相符合，因為在進程中，有些頁面經常被訪問。1.4.2 最近最久未使用算法(LRU) 選擇最近一段時間最長時間沒有被訪問過的頁面予以淘汰。LRU算法是根據頁面調入內存后的使用情況進行決策。由于無法預測各頁面將來的使用情況，采取“最近的過去”作為“最近的將來”的近似。選擇最近最久未使用的頁面予以淘汰。實現：賦予每個頁面一個方位字段，用來記錄一個頁面自上次被訪問以來所經歷的時間T，當要淘汰一個頁面的，選擇現有頁面中其T值最大的，即最近最久未使用的頁面予以淘汰。1.4.3最佳(zu ji)置換算法(OPT)最佳置換

17、算法所選擇的被淘汰掉的頁面，將是以后(yhu)永久不再使用的，或許是在最長（未來）時間內不再被訪問的頁面。采用最佳置算法，通常可保證獲得最低的缺頁率。本模擬算法中，最佳頁面置換算法實現所采用的思想是：循環讀入每個頁表項，若該頁表在內存中，則讀取下一個頁表項。若頁表不存在內存中：一種情況是內存不滿，則將頁表放入內存中；若內存塊已滿，剛分別計算內存中各個頁表再次被使用的時間，并將最久不被訪問的調出，放入當前讀入頁表項。2 各模塊(m kui)偽代碼算法 根據程序提示，用戶先將需要(xyo)計算的頁面號引用串，物理塊數量和引用串個數輸入到文件流中。待程序加載數據完成后，用戶繼續選擇頁面置換算法的類型

18、，程序根據用戶輸入的信息來判斷采用哪一種算法進行計算。結構如圖2.1所示。圖 2.1 總體(zngt)結構圖2.1偽代碼概念 偽代碼（英語：pseudocode），又稱為虛擬代碼，是高層次描述算法的一種方法。使用偽代碼的目的是讓被描述的算法可以容易地以任何一種 HYPERLINK /lemma/ShowInnerLink.htm?lemmaId=609078&ss_c=ssc.citiao.link t /_blank 編程語言（Pascal，C，Java，etc）實現。因此，偽代碼必須結構清晰、代碼簡單、可讀性好，介于 HYPERLINK /lemma/ShowInnerLink.htm?l

19、emmaId=8435979&ss_c=ssc.citiao.link t /_blank 自然語言與編程語言之間。以編程語言的書寫形式指明算法職能。使用偽代碼，不用拘泥于具體實現。它是半角式化、不標準的語言。可以把整個算法運行過程的結構用接近自然語言的形式（可以使用任何一種你熟悉的文字，關鍵是把程序的意思表達出來）描述出來。2.2偽代碼算法2.2.1主函數偽代碼算法 該程序是按自上而下，自頂向下的設計思想進行設計的。程序各個功能的實現之間的聯系采用函數調用與函數嵌套。main()函數是整個程序的入口，程序的開始就是從這里開始的，然后通過main()函數調用其他函數來實現各個功能。具體流程如圖

20、2.2所示。圖2.2 主函數(hnsh)流程圖Begin /*算法(sun f)開始*/調用(dioyng)designBy()顯示出設計者信息Scanf mSIZE，pSIZE，page100 /*mSIZE表示物理塊，pSIZE表示頁面號引用串個數，page100表示一個引用串的頁面號*/do Printf pageiScanf code /*code是一個標記，用來判斷用戶輸入是否符合要求*/Switch(code)case 1: FIFO() /*先進先出算法*/case 2: LRU() /*最近最久未使用算法*/case 3: OPT() /*最佳置換算法*/case 4: exi

21、t(0) /*退出程序*/default: 重新輸入while(code!=4)Getch（用戶輸入）End2.2.2延遲時間函數(hnsh)偽代碼算法begin變量(binling)定義while delay0while i124退格end圖2.3 延遲時間函數(hnsh)流程圖 延遲時間函數主要由兩個for循環構成。延遲時間函數在程序中主要起延遲時間的作用，相當于一個定時器，給程序數據加載，數據處理等提供時間保證。使程序能夠正常的進行。其具體流程如圖2.3所示。2.2.3 FIFO算法的偽代碼 begin 定義變量 while imSIZEpagei0memeryi, itimeiwhil

22、e jmSIZEmemeryjtempij while ipSIZEwhile jmSIZEif 新頁面號不在物理(wl)塊中k+if k=mSIZE 則，計算換出頁，記錄該頁進入(jnr)物理塊的時間否則(fuz)，tempij=memeryjprint 置換次數End FIFO算法是操作系統中最簡單最容易實現的一種頁面置換算法，它的實現主要運用了兩個循環結構。第一個循環的功能是將頁面串中的前mSIZE頁面直接放入物理塊中；第二個循環主要判斷當前頁面是否在物理塊中，若在物理塊中，則繼續讀取下一個頁面。否則，將最先進入物理塊的頁面寫入到物理塊中。其主要執行流程如圖2.4所示。2.2.4 LRU

23、算法的偽代碼 LRU算法是將最近進入物理塊且未使用的頁面首先換出物理塊。LRU函數主要也運用了兩個循環來實現其算法，首先將前mSIZE個頁面置換到物理塊中，然后再按具體算法進行置換頁面。其執行流程如圖2.5所示。圖2.4 FIFO流程圖 begin 定義(dngy)變量 while imSIZE pageimemeryi, itimeiwhile jmSIZEmemeryjtempij while imSIZE前mSIZE個數直接(zhji)放入while ipSIZE while jmSIZEif 新頁面號不在物理(wl)塊中k+判斷新頁面號是否在物理塊中if k=mSIZE 則，計算換出頁

24、，記錄該頁進入物理塊的時間否則，max=flag0flag1?0:1memeryjtempij調用(dioyng) print(置換次數)End圖2.5 LRU流程圖2.2.5 OPT算法(sun f)的偽代碼 begin 定義(dngy)變量 while imSIZEpageimemeryi, itimeiwhile jmSIZEmemeryjtempij 前mSIZE個數直接放入 while ipSIZEwhile jmSIZEif memeryj!=pagei判斷(pndun)新頁面號是否在物理塊中k+if k=mSIZE 則，計算(j sun)換出頁，記錄該頁進入物理塊的時間否則(fu

25、z)，max=flag0flag1?0:1tempij=memeryj得到物理塊中各頁下一次訪問時間if memerym=page1退出循環nextm=1調用 print(置換次數)End OPT算法是將內存中最長時間內不會用的頁面置換出去，這種算法的優點是系統利用率，內存利用率都非常的高。但是這種算法目前無法實現，因為實際中，系統根本無法預知哪一個頁面最先執行，哪一個頁面最后執行，各個頁面的執行順序都無法確定根本就不能確定頁面換出的次序。OPT算法主要用于對其他算法效率的評估。OPT函數的執行情況如圖2.6所示。圖2.6 OPT流程圖3 函數調用關系(gun x)圖3.1函數(hnsh)聲明

26、3.1.1主要算法(sun f)函數主要算法函數包括FIFO()、LRU()和OPT()三種，它們都是無返回值類型，不帶任何參數。各個函數的具體聲明情況如下：void FIFO(); /*先來先服務調度算法函數*/返回值類型：無返回值形參：無void LRU(); /*最近最久未使用算法函數*/返回值類型：無返回值形參：無void OPT(); /*最佳調度算法函數*/返回值類型：無返回值形參：無3.1.2輔助函數輔助函數是為了實現某些功能而特意設置的一些輔助函數。本程序主要有顯示引用串函數、顯示設計者信息函數、數據加載函數和延遲時間函數，它們有的有形式參數，有的沒有，但是它們都是無返回值類型

27、的函數。各個函數的具體聲明情況如下：void print(unsigned int t); /*顯示引用串函數*/返回值類型：無返回值形參：無符號整型void designBy(); /*顯示設計者信息*/返回值類型：無返回值形參：無void download(); /*數據加載*/返回值類型：無返回值形參：無void mDelay(unsigned int Delay); /*延遲時間*/返回值類型：無返回值形參：無符號整型3.2程序函數調用關系圖 程序以main( )函數為入口，通過主函數main( )進行調用其他函數，以此實現函數的各個功能。在本程序中，main( )函數調用了desig

28、nBy( )函數，用以顯示設計者信息；main( )函數還分別調用了FIFO( )、LRU( )和OPT( )三種算法函數，實現三種算法。FIFO( )、LRU( )和OPT( )又分別調用了print( )和compute( )函數，print( )顯示了用戶輸入的頁面引用串，compute( )則主要計算了用戶選擇的算法的結果。在計算過程中，為了保證邏輯上合理，我們在compute( )函數中調用了mDelay( )時間延遲函數；main( )函數也調用了download( )數據加載函數，主要功能是加載用戶輸入的數據以供各種算法使用。在調用download( )過程中，也調用了時間延遲函

29、數mDelay( )。具體函數調用關系如圖3.1所示。圖3.1 函數調用關系(gun x)4 測試(csh)結果4.1數據(shj)初始化 用戶根據程序提示，按照要求輸入相應的數據。例如，本次(bn c)測試中我們設置物理塊個數為4，頁面引用串個數為20，一個頁面號引用串中各個頁面號之間用空格(“ ”)隔開。值得注意的是，物理塊個數可以是幾個，幾十個，甚至幾百個，但是考慮到系統的效率，一般取物理塊個數在10個以內；頁面號引用串個數也和物理塊個數一樣，頁面引用串個數取100個以內。用戶輸入情況如圖4.1所示。圖 4.1 界面初始化4.2頁面調度算法 選擇一個合適的頁面置換算法對提高內存的利用率會

30、有很大的幫助。當用戶將數據初始化結束后，就要進行頁面調度算法的選擇了。下面本書將逐一說明先進先出算法FIFO、最近最久未使用LRU和最佳置換算法的具體調試情況。 用戶輸入的頁面引用串為：2 12 43 2 15 23 21 2 4 23 21 20 32 3 21 23 20 2 32 12，物理塊個數為：4，頁面號引用串個數為：20。FIFO算法的缺頁次數為19，置換次數為16，缺頁率為19/20，訪問率為5%；LRU算法的缺頁次數為19，置換次數為16,缺頁率為19/20,訪問率為5%；OPT算法的缺頁次數為14,置換次數為16,缺頁率為14/20，訪問率為30%。4.2.1先進先出算法(

31、sun f) 由操作系統維護一個所有當前在內存中的頁面的鏈表，最新進入的頁面放在表尾，最久進入的頁面放在表頭。當發生(fshng)缺頁中斷時，淘汰表頭的頁面并把新調入的頁面加到表尾。具體(jt)計算結果如圖4.2所示。圖 4.2 FIFO算法4.2.2最近最久未使用LRU 用一維數組pagepSIZE存儲頁面號序列，memerymSIZE是存儲裝入物理塊中的頁面。數組temp10標記頁面的訪問時間。每當使用頁面時，刷新訪問時間。發生缺頁時，就從物理塊中頁面標記最小的一頁，調出該頁，換入所缺的頁面。具體計算結果如圖4.3所示。圖 4.3 LRU算法(sun f)圖 4.4 OPT算法(sun f

32、)4.2.3最佳(zu ji)置換算法OPT 用一維數組pagepSIZE存儲頁面號序列，memerymSIZE是存儲裝入物理(wl)塊中的頁面。數組tempmSIZE記錄物理塊中對應頁面的最后訪問時間。每當發生缺頁時，就從物理塊中找出最后訪問時間最大的頁面，調出該頁，換入所缺的頁面。具體計算結果如圖4.4所示。5 源程序#include #include #include /*全局變量*/int mSIZE; /*物理(wl)塊數*/int pSIZE; /*頁面(y min)號引用串個數*/static int memery10=0; /*物理(wl)塊中的頁號*/static int p

33、age100=0; /*頁面號引用串*/static int temp10010=0; /*輔助數組*/*置換算法函數*/void FIFO();/先進先出置換算法void LRU();/最近最久未使用算法void OPT();/最佳置換算法/*輔助函數*/void print(unsigned int t);void designBy();/顯示設計者信息void download();/數據加載void mDelay(unsigned int Delay);/延遲時間/*主函數*/void main() int i,k,code;system(color 0F);designBy();pr

34、intf(請按任意鍵進行初始化操作. n);printf(n);printf( );getchar();system(cls);system(color 0B);printf(請輸入物理塊的個數：);scanf(%d,&mSIZE);printf(請輸入頁面號引用串的個數(P=100)：);scanf(%d,&pSIZE);puts(請依次輸入頁面號引用串(請用 隔開)：);for(i=0;ipSIZE;i+) scanf(%5d,&pagei);download();system(cls);system(color 0E); do puts(輸入的頁面(y min)號引用串為：);for(k

35、=0;k=(pSIZE-1)/20;k+)for(i=20*k;(ipSIZE)&(i);getch();system(cls); while (code!=4);getch();/*載入數據(shj)*/void download()int i;system(color 0D);printf(n);printf( 能不能給我一首歌的時間(shjin)。 n);printf(n);printf(Loading.n);printf( );for(i=0;i51;i+)printf(b);for(i=0;i);printf(nFinish.nOK!已唱完.按任意鍵進入置換算法選擇(xunz)界面：

36、);getch();/*設置延遲*/void mDelay(unsigned int Delay) unsigned int i; for(;Delay0;Delay-) for(i=0;i124;i+) printf( b); /*顯示設計者信息*/ void designBy()printf(n);printf( 研究題目：頁面置換算法 n);printf( 許可證號：13480144 n);printf( 版權所有：朱 強 n);printf(n);/*顯示頁面(y min)號引用串*/void print(unsigned int t)int i,j,k,l;int flag;for(

37、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

38、)flag+;if(flag=mSIZE)/*頁面(y min)在物理塊中*/printf( );elseprintf( |%d|,tempij);/*每行顯示(xinsh)20個*/if(i%20=0)continue;printf(n);printf(n);printf(缺頁次數：%dtt,t+mSIZE);printf(缺頁率：%d/%dn,t+mSIZE,pSIZE);printf(置換次數：%dtt,t);printf(訪問命中率：%d%n,(pSIZE-(t+mSIZE)*100/pSIZE);printf(n);/*計算(j sun)過程延遲*/void compute()int

39、 i;printf(正在(zhngzi)玩命計算，請稍候);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);/*先進先出頁面置換(zhhun)算法*/void FIFO() int memery10=0; int time10=0; /*記錄進入物理塊的時間*/ int i,j,k,m; int max=0; /*記錄換出頁*/ int count=0; /*記錄置

40、換次數*/*前mSIZE個數直接放入*/ 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+;/*計算(j sun)換出頁*/ max=time0time1?0:1;for(m=2;mmSIZE;m+)if(timemtimemax)max=m; memery

41、max=pagei; timemax=i; /*記錄該頁進入物理(wl)塊的時間*/ for(j=0;jmSIZE;j+)tempij=memeryj; else for(j=0;jmSIZE;j+)tempij=memeryj; compute();print(count);/*最近(zujn)最久未使用置換算法*/void LRU() int memery10=0; int flag10=0; /*記錄頁面的訪問時間*/ int i,j,k,m; int max=0; /*記錄換出頁*/ int count=0; /*記錄置換次數*/*前mSIZE個數直接放入*/ for(i=0;imSI

42、ZE;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) /*如果(rgu)不在物理塊中*/ count+;/*計算(j sun)換出頁*/ max=flag0flag1?0:1;for(m=2;mmSIZE;m+)if(flagmflagmax)max=m; memery

43、max=pagei; flagmax=i; /*記錄(jl)該頁的訪問時間*/ 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; /*記錄置換次數*/*前mSIZE個數直接放入*/ 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) /*如果(rgu)不在物理塊中*/ count+;/*得到物理快中各頁下一次訪問(fngwn)時間*/for(m=0;mmSIZE;