1、操作系統(tǒng)實驗報告課題：頁面淘汰算法專 業(yè)：班 級：學 號：姓 名：一實驗目的 錯誤！未定義書簽。二實驗要求 3三背景知識 3四總體設計 4五詳細設計 錯誤！未定義書簽。六運行結果分析 9七心得體會 13八參考文獻14附：源代碼15一、實驗目的本實驗主要對操作系統(tǒng)中請求分頁式內存管理及其應用的一些關鍵算法進 行模擬。學生通過設計與實現(xiàn)Clock算法，能夠加強對相應理論的理解，并對了 解操作系統(tǒng)內部的基本處理原理與過程也有很多益處。利用簡單的數(shù)據(jù)結構，模擬實現(xiàn)操作系統(tǒng)中的頁面置換機制，通過寫程序模擬實現(xiàn)上述三種內存頁面置換 算法，使學生進一步掌握內存頁面置換的方法。 對操作系統(tǒng)中內存的管理有一個

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

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

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

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

6、后永不使用的或許 是在最長（未來）時間內不再被訪問的頁面。采用最佳置換算法，通常可保證獲得 最低的缺頁率。但由于人目前還無法預知一個進程在內存的若干個頁面中，哪一個頁面是未來最長時間內不再被訪問的， 因而該算法是無法實現(xiàn)的，但可以利用 此算法來評價其它算法。<4>時鐘頁面置換算法時鐘頁面置換算法是把所有的頁面都保存在一個類似鐘面的環(huán)形鏈表中，一個表 針指向最老的頁面，如圖所示口囚回“發(fā)生缺頁中斷時.檢 杳表針指向的頁面.根0回回臼據(jù)R位采取動作上R 二 (h淘汰頁面R=l(潔除R位并向的移動表計當發(fā)生缺頁中斷時，算法首先檢查表針指向的頁面，如果它的R位是0就淘汰該 頁面，并把新的頁

7、面插入這個位置，然后把表針前移一個位置；如果 R位是1 就清除R位并把表針前移一個位置，重復這個過程直到找到了一個 R位為0的頁 面為止。四、總體設計根據(jù)要求設計頁面淘汰算法的活動圖運行程序進入主頁面，在正上方，已經(jīng)通過隨機生成函數(shù)生成了頁面號，在其下方，顯示可選項：0、退出程序1、FIFO算法2、OPT算法3、 LRUB法。根據(jù)需要，選擇相應的法，程序自動生成頁面淘汰的先后順序，以及置換次數(shù)和缺頁次數(shù)，并打 印在下方，執(zhí)行完以后，再次進入主頁面，到輸入 0,退出程序。算法流程圖FIFO算法流程圖：OPT算法流程圖LRU#法流程圖:五、詳細設計（一）、設計思想1、 最佳置換算法（OPT）用數(shù)組

8、Temppages口存儲當前物理塊中頁面信息，數(shù)組 TimeArry存 儲當前在物理塊中的頁面的獲得內存時的時間，當頁面不在內存中時，根據(jù)當前已獲得物理塊數(shù)的頁面在所有的頁面當中將來不在請求內存 或者很少請求內存的情況進行置換2、 先進先出算法（FIFO）用數(shù)組Temppages口存儲當前物理塊中頁面信息，變量temp記錄內存 中物理塊頁面置換狀態(tài)，每進行一次置換，頁面置換狀態(tài)變化，便于 下一次的置換。3、 最近最久未使用算法（LRU）用數(shù)組Temppages口存儲當前物理塊中頁面信息，數(shù)組 TimeArry存 儲當前在物理塊中的頁面的獲得內存時的時間，當頁面不在內存中時，選才T TimeAr

9、ry口數(shù)組中值最小并且對應物理塊中的頁面進行置換。（二）、設計步驟首先根據(jù)程序要求，我們分別定義兩個宏，用以存放我們的物理塊數(shù) 目以及頁面數(shù)目，再定義一個結構體，用以物理塊的存儲，代碼如下：#define MemPageCount 4#define InstructionCount 20struct pageint serial; / 頁面號int time; /時間計數(shù)mempageMemPageCount;其次，建立主函數(shù)，根據(jù)程序需要，定義相應的變量，建立 switch語句，用以 算法的選擇，部分定義如下：int i,j,k,m,n; /指令頁面集合，可以考慮讓頁面指令集合隨機生成int

10、 instructionInstructionCount;int mem_counter; / 內存頁面集合計數(shù)器int switch_counter; /置換次數(shù)最后，根據(jù)算6流程圖，實現(xiàn)相應算法的代碼編寫。（三）、算法流程設計主函數(shù)流程：STEP1輸入分配的頁框數(shù)，頁面訪問次數(shù)和要訪問的頁面號序列STEP2:內存頁面初始化。內存中頁面的數(shù)據(jù)結構為單循環(huán)鏈表，含有頁號值 yehao和訪問位值a。開始時頁號均為-1 ,訪問位為0.STEP3測試數(shù)據(jù)。具體算法是依要訪問的頁面號，調用 find()函數(shù)查找是 否已經(jīng)存在于內存中。若存在，則修改其訪問位為1.若不存在，觸發(fā)缺頁中 斷，調用tihua

11、n()函數(shù)。最后，打印當前內存狀態(tài)。如此循環(huán)直至測試用都 訪問完畢。1)主要函數(shù)實現(xiàn)a) Makenode(double)函數(shù)：用于初始化一個節(jié)點。b) Find (double)函數(shù)：依據(jù)輸入的頁號，查詢內存中是否已存在此頁面。 若存在返回值1,不存在返回值0.c) Tihuan (double)函數(shù)：在發(fā)生缺頁中斷時，時鐘指針查找訪問位為0的頁面進行替換，指針掃過的頁面訪問位置0,新加入的頁面訪問位置1 替換后指針下移。d) Print_state()函數(shù)：打印當前內存中存在的頁面的狀態(tài)以及當前時鐘指針所指向的頁面位置。2)測試數(shù)據(jù)估計輸入：輸入分配的頁框數(shù)3輸入頁面訪問次數(shù)15輸入要訪問

12、的頁面號序列3 4 2 6 4 3 7 4 3 6 3 4 8 4 6輸出(僅最后一項)：頁面號 訪問位頁面號訪問位61頁面號訪問位81C loc k指針所在位置見面號為43)結果分析以下是clock算法對應輸入頁面號序歹U 3 4 2 6 4 3 7 4 3 6 3 4 8 4 6分析表引用q串P426437436348433A666+64A4444-什內存 a44什什41 1+X 66666+22133+333-3+3+88是否跳/頁J JJJJJ68六、運行結果分析:a）開始界面請按任意鍵進行初始化操作.:為為: 為別數(shù)續(xù) 數(shù)次繼 面號理犍物意 A省省用任 >缺缺可按自定義頁數(shù)和號

13、t,使用黑認埴產(chǎn)生結果請輸入你的選擇:2、采用隨機數(shù)產(chǎn)生的結果請按任意鍵進行初始化操作.-為為=為別數(shù)續(xù)數(shù)既繼面號理鍵至物意4省省用任K缺般K使用默認值產(chǎn)生結果2、自定義頁數(shù)和支號請輸入你的選擇請選擇覆：工為F1F。先進先出）2為LRIK最近最久未使用）3為OPT最佳置換算法， 4三洞法一起實現(xiàn)FIF。先進先出算法結果顯示10為為甯frn數(shù)數(shù)217 面E1032、采用自定義頁面信息產(chǎn)生結果 自定義頁面數(shù)為：15物理塊數(shù)為：4頁面序列為：1 2 3 4 5 6 7 8 9 4 5 6 7 0 8自定義頁面數(shù)和頁號7 8 9234 5 6 7 0 S4 5 6 7H 94 567 0 8請選擇昊苣

14、：工為FIFO先進先出2為LRIK最近最久未使用33為OPT最佳置換算法 4三福法一起實現(xiàn)N 15 /V 54 143 7 : 152數(shù)；*，:= ,i塊為別為： 數(shù)；理數(shù)分數(shù)續(xù) 面匚廚面甚繼 9改4理鍵 人入修義義物意 籥否定定用任 請請是自自可按根據(jù)結果，我們不難發(fā)現(xiàn)，OPT算法，是三種算法中性能最好的，它的置 換次數(shù)最少，LRU次之，不過性能最差的還是 FIFO,由于缺頁率=缺頁次數(shù)/ 總的頁面數(shù)，所以我們不難發(fā)現(xiàn)，隨著物理塊數(shù)的增加，缺頁率都相應有所增 加，但是OPT»法的增加較為明顯，即產(chǎn)生了 belady現(xiàn)象。七、心得體會：這次課程設計，讓我對算法的編寫更加的熟練，同時更

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

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

17、就是 最近最久沒有被訪問的頁面。上述兩種算法，是我們在進程調度中使用最多的兩種， 你可能會問？為 什么要使用進程調度，因為當我們的程序在運行時，若所訪問的頁面不再內 存而需把它調入內存，但內存已無空閑空間，這時，為了保證該程序能正常 運行，系統(tǒng)就必須從內存中調出一頁程序或數(shù)據(jù)送到磁盤的兌換區(qū)中，但應將那個頁面調出，我們就必須根據(jù)一定的算法來實現(xiàn)。 所以，一個頁面置換 算法的好壞，將直接影響到我們系統(tǒng)的性能。相比較而言，我們最常用的是 LRIM法，因為它是根據(jù)頁面調入內存后的使用情況就行決策的，比FIFOB法要好很多。通過與其他算法白比較，加深對clock算法的理解，也了解了他們的異同之 處。C

18、lock算法其實是一種改進的第二次機會算法，它通過設置訪問位，找 到最早最不常訪問的頁面，即標號為0的頁面。之所以叫clock算法，依我理 解是將內存中的排列順序附上時間的概念，clock指針掃過的頁面要將他們1 置0就是基于這個思想，因為他們都是沒被訪問的，且在時鐘上的排列按照 訪問時間順序。這樣就保證了每次替換的都是最早進來的且不最常訪問的貢 面。八、參考文獻【1】計算機操作系統(tǒng)（第三版）湯小丹、梁紅兵、湯子瀛、哲鳳屏等西安電子科技大學出版社2007-05【2】C+Primer中文版（第4版） （美）Stanley B. Lippman 等 著 李師賢 等 譯.人民郵電出版社，2006-0

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

20、e 100int pageNum = 0;/全局變量頁面數(shù)int pagesM_size;/存儲頁號int TemppagesM_size;/ 輔助數(shù)組int TimeArryM_size;/ 記錄頁在內存中的 時間int method;/產(chǎn)生結果的方法int AlgorithmStyle; / 輔助變量，用于選擇算法類型int Block;/ 記錄物理塊數(shù)int start;/ 輔助變量void Inition（）/初始化函數(shù)int i;int t = time（NULL）;/ 產(chǎn)生隨機數(shù)種 子srand(t);/ 用t初始化隨機數(shù)種子pageNum = rand()%10+8;/ 隨機產(chǎn)生

21、4-14之內的整數(shù)，保證頁面數(shù)在4-14之內for(i = 0 ; i < pageNum ; i+) pagesi = rand()%10+1;/ 初始化 頁號，初始 值在1-10之內Block = 4;/初始化物理塊數(shù)位3void printDefaltResult()/缺省參數(shù)顯示int i;printf("缺省頁面數(shù)為：dn",pageNum);printf("缺省頁號分別為：");for(i = 0 ; i < pageNum ; i+) printf("%d ",pagesi);printf("n&q

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

23、n",Block);printf("按任意鍵繼續(xù):n");getchar();)void printUserInfo()/顯示個人信息(system("color 0B");printf(" 1n");printf(" |頁面淘汰算法I n");printf(" |學號：I n");printf(" |班級：I n");printf(" |姓名：I 'n");printf(" |1n");printf("按任

24、意鍵開始操作:");getchar();system("cls");system("color 0B");)void ChioceDealmethod()/ 選擇解決問題的方法"1"選擇缺省值，"2"選擇自定 義值(n");printf(" |1、使用默認值產(chǎn)生結果2、自定義頁數(shù)和頁號I n");printf(" 11 n請輸入你的選擇:n");scanf("%d",&method);system("color 0F&

25、quot;);void PrintNotW讓houtPages()顯示一定不用換頁的部分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+

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

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

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

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

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

31、;printf("缺頁次數(shù)為： %d ，頁面總數(shù)為： %d",WithOutPages+Block,pageNum);re = (double)(W讓hOutPages+Block)/(double)pageNum);printf("%.2lfn",re);void OPTDealQuestion()int i,j,l;int WithOutPages = 0;/ 記錄缺頁數(shù)printf("OPT(最佳置換算法)結果顯示：n");PrintNotW計houtPages();for(i = start ; i<pageNum ;

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

33、min = TimeArry0;int flag = 0;for(j = 1 ; j < Block ; j+)if(TimeArryj > min) min = TimeArryj;flag = j；Temppagesflag = pagesi;TimeArryflag = i;PrintResult();，置換率為:，缺頁率為:printf("置換次數(shù)為： %d ，頁面總數(shù)為： %d ",WithOutPages,pageNum);double re = (double)W讓hOutPages)/(double)pageNum);printf("%

34、.2lfn",re);printf("缺頁次數(shù)為： %d ，頁面總數(shù)為： %d",WithOutPages+Block,pageNum);re = (double)(W讓hOutPages+Block)/(double)pageNum);printf("%.2lfn",re); void ChioceAlgorithm(int AlgorithmStyle) switch(AlgorithmStyle)case 1:FIFODealQuestion();/break;case 2:LRUDealQuestion();/break;case 3:OPTDealQuestion();/break;case 4:FIFODealQuestion();/LRUDealQuestion();/先進先出算法解決問題最近最久未使用算法解決問題最佳置換算法解決問題先進先出算法解決問題最近最久未使用算法解決問題OPTDealQuestion();/ 最佳置換算法解決問題 break; )void D