請求頁式管理缺頁中斷模擬設計--FIFO、OPT課 程 設 計

1、武漢理工大學計算機操作系統(tǒng)教程課程設計報告書請求頁式管理缺頁中斷模擬設計-fifo、opt課 程 設 計題 目請求頁式管理缺頁中斷模擬設計-fifo、opt學 院計算機科學與技術專 業(yè)計算機科學與技術班 級姓 名指導教師2009年1月9日課程設計任務書學生姓名： 王 瑤 專業(yè)班級： 計算機0605 指導教師： 劉 洪 星 工作單位： 計算機科學與技術學院 題 目: 請求頁式管理缺頁中斷模擬設計-fifo、opt初始條件：1預備內容：閱讀操作系統(tǒng)的內存管理章節(jié)內容，了解有關虛擬存儲器、頁式存儲管理等概念，并體會和了解缺頁和頁面置換的具體實施方法。2實踐準備：掌握一種計算機高級語言的使用。要求完成

2、的主要任務: （包括課程設計工作量及其技術要求，以及說明書撰寫等具體要求）1實現(xiàn)指定淘汰算法。能夠處理以下的情形： 能夠輸入給作業(yè)分配的內存塊數(shù)； 能夠輸入給定的頁面，并計算發(fā)生缺頁的次數(shù)以及缺頁率； 缺頁時，如果發(fā)生頁面置換，輸出淘汰的頁號。2設計報告內容應說明： 需求分析； 功能設計（數(shù)據(jù)結構及模塊說明）； 開發(fā)平臺及源程序的主要部分； 測試用例，運行結果與運行情況分析； 自我評價與總結：i）你認為你完成的設計哪些地方做得比較好或比較出色；ii）什么地方做得不太好，以后如何改正；iii）從本設計得到的收獲（在編寫，調試，執(zhí)行過程中的經驗和教訓）；iv）完成本題是否有其他方法（如果有，簡要說

3、明該方法）；v）對實驗題的評價和改進意見，請你推薦設計題目。時間安排：設計安排一周：周1、周2：完成程序分析及設計。周2、周3：完成程序調試及測試。周4、周5：驗收、撰寫課程設計報告。（注意事項：嚴禁抄襲，一旦發(fā)現(xiàn)，一律按0分記）請求頁式管理缺頁中斷模擬設計fifo、opt1課程設計目的與功能 1.1設計目的 結合操作系統(tǒng)所學內存頁式管理章節(jié)，掌握虛擬內存設計的重要性，熟悉和掌握請求分頁式存儲管理的實現(xiàn)原理，通過分析、設計和實現(xiàn)頁式虛擬存儲管理缺頁中斷的模擬系統(tǒng)，重點掌握當請求頁面不在內存而內存塊已經全部被占用時的替換算法（主要通過fifo和opt實現(xiàn)），并考察替換算法的評價指標缺頁次數(shù)和缺頁

4、率，得到淘汰的頁面次序。高級語言設計并實現(xiàn)出的結果程序要能夠很好地顯示頁面調入和替換詳細信息。1.2初始條件及可發(fā)環(huán)境 1.2.1初始條件 1預備內容：閱讀操作系統(tǒng)的內存管理章節(jié)內容，了解有關虛擬存儲器、頁式存儲管理等概念，并體會和了解缺頁和頁面置換的具體實施方法。2實踐準備：掌握一種計算機高級語言的使用。 1.2.2開發(fā)環(huán)境 （1）使用系統(tǒng)：windows xp（2）使用語言：c+（3）開發(fā)工具：visual c+ 6.01.3功能實現(xiàn) 設計的結果程序能實現(xiàn)fifo、opt算法模擬頁式存儲管理缺頁中斷，主要能夠處理以下的情形：(1) 用戶能夠輸入給定分配的內存塊數(shù)；(2) 用戶輸入給定的頁面

5、，并計算發(fā)生缺頁的次數(shù)、缺頁率及淘汰頁面次序；(3) 程序可隨機生成頁面序列，或用戶輸入；2需求分析及設計說明 2.1需求分析 由于純頁式存儲管理提高了內存的利用效率，但并不為用戶提供虛存，并且會產生磁盤碎片問題。用戶程序將受到物理內存大小的限制。而虛存的存儲管理技術請求分頁存儲管理技術和請求分段技術，則很好的解決了這個問題。該設計虛擬實現(xiàn)請求分頁管理（只實現(xiàn)fifo和opt）。請求分頁系統(tǒng)是在分頁系統(tǒng)的基礎上，增加了請求調頁功能和頁面置換功能所形成的頁式虛擬存儲系統(tǒng)。它允許只裝入部分頁面的程序和數(shù)據(jù)，便啟動運行。以后，再通過調頁功能和頁面置換功能，陸續(xù)把即將要運行的頁面調入內存，同時把暫時不

6、運行的頁面換出到外存上，置換時以頁面為單位。實現(xiàn)將程序正在運行時所需的但尚未在內存的頁面調入內存，再將內存中暫時不用的頁面從內存置換到外存磁盤上。為了實現(xiàn)請求分頁技術，頁表應增加相應的內容，反映該頁是否在內存，在外存的位置，和在內存的時間的長短。請求分頁中的頁表如表1：表1虛擬頁號物理塊號狀態(tài)位輔存地址訪問字段修改位各字段說明如下：狀態(tài)位：指示該頁是否已調入內存。訪問字段：記錄本頁在被訪問的次數(shù)，或記錄最近已有多長時間未被訪問。修改位：表示該頁面在調入內存后是否被修改過。若未被修改，在替換該頁時就不需要再將該頁寫回到外存上，以減少系統(tǒng)的開銷和啟動磁盤的次數(shù)；若已被修改，則必須將該頁重寫到外存上

7、，以保證外存中所保留的始終是最新副本。外存地址：指出該頁在外存上的地址，通常是物理塊號。在本設計中模擬fifo、opt系統(tǒng)的實現(xiàn)中，只需要用到虛擬頁號，物理塊號和中斷位。頁表可用一個結構體的數(shù)組實現(xiàn)。請求分頁的具體實現(xiàn)過程如圖1圖1請求分頁流程圖 2.2設計說明 2.2.1算法分析在進程運行過程中，若其所要訪問的頁面不在內存，需要把它們調入內存，但內存已無空閑已空閑空間時，為了保證該進程能正常運行，系統(tǒng)必須從內存中調出一頁程序或數(shù)據(jù)，送磁盤的對換區(qū)。但應將哪個頁面調出，必須根據(jù)替換算法來確定。該設計采用的是常見置換算法中的先進先出(fifo)、理想型淘汰算法opt(optimal replac

8、ement algorithm）。詳細算法原理如下：fifo(先進先出算法)基本思想：總是選擇在內存駐留時間最長的一頁將其淘汰，因為最早調入內存的頁，不再被使用的可能性比近期調入內存的大。該算法實現(xiàn)簡單，只需要把一個進程調入內存的頁面，按先后次序連結成一個隊列，并設置一個指針，稱為替換指針，使它總是指向最老的頁面。但是該算法與進程實際運行的規(guī)律不相適應，因為在進程中，有些頁面經常被訪問，比如有全局變量、常用函數(shù)，例程等的頁面，fifo算法并不能保證這些頁面不被淘汰。使用fifo替換算法效率比較低，可能會比理想型算法要多出一倍。低的原因是：基于處理器按線性順序訪問地址空間這一假設。事實上，許多時

9、候，處理器不是按線性順序訪問地址空間的。例如，執(zhí)行循環(huán)結構的程序段。使用fifo算法時，在未給進程或作業(yè)分配足夠它所需要的頁面數(shù)時，有時會出現(xiàn)分配的頁面數(shù)增，缺頁次數(shù)反而增加的現(xiàn)象（belady現(xiàn)象）。 例如針對請求序列：1 2 3 4 1 2 5 1 2 3 4 5，若分配3個可用內存塊，使用fifo算法，一共會缺頁9次，缺頁率：75%；而如果分配4個可用內存塊，則一共會缺頁10次，缺頁率：83.3%。opt(理想型淘汰算法)基本思想：當要調入一新頁而必須淘汰一舊頁時，所淘汰的頁是以后不再使用的，或者是以后相當長的時間內不會使用的。采用理想型替換算法，通?？杀ＷC獲得最低的缺頁率。但是由于人們

10、目前無法預知一個進程在內存的若干個頁面中，哪個頁面是未來最長時間內不再被訪問的，因而該算法是無法實現(xiàn)的，但是在模擬設計中，由于是事先給定一個頁面序列，即知道各個時刻以前和以后的頁面出現(xiàn)情況，所以可實現(xiàn)該算法。在實際系統(tǒng)中，雖無法實現(xiàn)理想型淘汰算法，但是可用它來評價其他替換算法。2.2.2數(shù)據(jù)結構模擬設計時，頁表沒項記錄的數(shù)據(jù)類型用結構體定義。整該頁表用數(shù)組模擬。結構體有三個成員：int page_num 表示頁面號；int memory_num表示頁面所對應的內存塊號；int is_in_memory是存在狀態(tài)位標志，表示頁面是否在內存，0表示不在內存，1表示在內存。在每一個算法函數(shù)中都要初始

11、化頁表，否則，后面的算法會受前面算法結果的影響。struct pageint page_num; /表示頁面號int memory_num; /表示頁面所對應的內存塊號int is_in_memory;/ 是存在狀態(tài)位標志，表示頁面是否在內存，0 表示不在內存，1表示在內存;page page_table初始值; for(int i=0;i10;i+) /初始化頁表： page-tablei.page_num=i;page_tablei.memory_num=-1; /初始化，內存塊號為-1，即沒在內存塊中。page_tablei.is_in_memory =0; /初始化時，各頁面均不在內存

12、 頁面請求序列：int *page_array= new intinputsize。 內存在程序中模擬內存存放頁面號：int *memory=new intmemorysize 2.2.3函數(shù)實現(xiàn) control()函數(shù)是class control的構造函數(shù)，用來初始化頁表、內存(調用initial()函數(shù))。提示并接受用戶輸入等待調入頁面數(shù)page_size，可用物理塊數(shù)memory_size，并隨機生成請求頁面，或用戶自己輸入。然后調用fifo()、opt()函數(shù)實現(xiàn)按不同替換算法調入頁面進內存。void fifo()函數(shù)實現(xiàn)先進先出的替換算法調入頁面。void opt()函數(shù)實現(xiàn)理想型替

13、換算法。3程序的主要模塊說明 3.1 control類封裝內存管理3.1.1 fifo替換算法實現(xiàn)偽函數(shù)void control:fifo()control:init(); 初始化頁表等 do if(當前頁在內存)else（當前頁不在內存，直接加載進入物理塊）缺頁累積；加載當前頁進入內存；修改頁表置當前頁在頁表的是否在內存標志為1。將該頁在內存的位置對應。while(內存物理塊沒有加載滿);/內存物理塊已經加載滿了； for(剩下的頁面循環(huán))if(當前頁在內存)else(當前頁不在內存)缺頁累積。替換頁面；修改頁表置當前頁在頁表的是否在內存標志為1。將該頁在內存的位置對應。利用算法得到下次替換

14、的物理塊號。輸出缺頁次，缺頁率，淘汰頁面次序。 3.1.2 opt替換算法實現(xiàn)偽函數(shù) void control:opt()control:init();/初始化頁表等 for(對每個頁表循環(huán)處理) for(檢查每個物理塊) if (如果該頁在內存物理塊中) 置判別標志為1 if(如果該頁不在內存，并且物理快放滿) 缺頁累加并權值數(shù)組每個記錄元素清零 for(物理塊每個元素檢查) for(從該頁后面的那個頁開始計算權值)權值累加; 得到最大權值所在的物理塊，即是下次需要替換的頁 替換該頁，加入內存 if(該頁不在內存，并且內存物理塊沒有滿) 缺頁累加 直接加載進內存 輸出缺頁次、缺頁率和淘汰頁號

15、次序。 3.2 main函數(shù) 利用頁式管理control類建立一個對象，來實現(xiàn)fifo、opt。4使用說明及運行分析 4.1使用說明及運行 運行程序根據(jù)提示輸入調入頁面數(shù)和可使用的物理塊數(shù)，再選擇是用戶輸入還是計算機隨機產生頁面號。觀察頁面調度過程，處理完各頁面后，統(tǒng)計并顯示缺頁次數(shù)、缺頁率和淘汰頁面號次序。 4.2測試實例和運行結果4.2.1 fifo算法 輸入給定的頁面數(shù)：10輸入給作業(yè)分配內存的物理塊數(shù)：3隨機生成頁面請求序列，如圖2：0 1 7 3 9 0 6 9 8 7 圖2運行結果如圖3 圖3 4.2.2 opt算法 輸入給定的頁面數(shù)：15輸入給作業(yè)分配內存的物理塊數(shù)：3隨機生成頁

16、面請求序列，如圖4：0 1 7 3 9 0 6 9 8 7 圖4 運行結果如圖5 圖5 4.4結論與分析 從運行結果看出程序能滿足模型設計的要求，提示用戶對請求序列的大小和可用內存數(shù)量進行限制，并提示用戶輸入請求序列號，或系統(tǒng)隨機生成序列，按照不同的替換算法處理并且顯示請求頁面的調入和替換情況。通過以上運行，比較各種算法的缺頁次數(shù)和缺頁率，可以看出opt替換算法具有最小的缺頁率。雖理論上最優(yōu)，但是實際卻無法實現(xiàn)該算法。5自我評價與總結在完成了模擬系統(tǒng)的設計和實現(xiàn)后，覺得自己確實獲益匪淺。首先，值得肯定的是：能夠一開始就清晰分析了程序的設計流程及實現(xiàn)要求與原理，利用流程圖，較好地理解了請求分頁的

17、工作流程；倆個主要算法設計較合理，實現(xiàn)容易；結果顯示清楚，能較好的反映各請求頁面的存在和替換信息。此外還借助c+語言的類class封裝的方法將頁式管理整個操作封裝起來，容易補充，數(shù)據(jù)更安全，有益于繼承，使功能更強大。然而，設計不足的地方也是存在的：模擬系統(tǒng)中，用的是一個數(shù)組(數(shù)據(jù)分配連續(xù))來模擬內存空間而實際系統(tǒng)請求分頁存儲管理時，所分配的內存是不連續(xù)的，或許可能用鏈表的形式可以改進；另外，在設計opt算法時，語句嵌套太多，不利于程序的閱讀，而且參數(shù)和標志的變量的設計不太合理，也加深了程序不利于閱讀。最后，沒能實現(xiàn)內存很直觀的調度過程的呈現(xiàn)。其次，在設計過程中，為了較好地完成設計，也參閱和回憶

18、結合了其他相關知識，操作系統(tǒng)相關知識為主要架構，高級語言c+知識為工具。此過程的學習，豐富和鞏固了操作系統(tǒng)的理論知識，對課堂上不明確和不懂的知識，如請求分頁的工作流程，都得到了很好補充學習，同時也增加了c+語言本身的應用能力，極大提高了自身學習該門語言的熱情。懂得了編譯、調試過程中錯誤的判斷與矯正，積累了不少經驗。再其次，想補充的是其他可用算法的實現(xiàn)：請求分頁內存管理的頁面替換還可以用lru(最近最久未使用頁面置換算法)和輪轉法（round robin）。lru的基本思想是：當需要淘汰某一頁時，選擇離當前時間最近的一段時間內最久沒有使用過的頁先淘汰。即當需要淘汰一頁時，選擇最長時間未使用的頁。

19、它是基于假設：如果某頁被訪問，它可能馬上還要被訪問；相反，如果某頁長時間未被訪問，它可能最近也不可能被訪問。就是本質上與opt算法相反的過程。最后，個人認為課程設計的范圍還可以放的更廣些，例如就實現(xiàn)內存頁式（或段式）的管理，可以一起包含些內容，如地址的轉換，空間的分配與回收，和虛存調度等，這樣可以更概括的，更有邏輯，更全面的加深對計算機各個邏輯塊的工作原理。附錄：f1參考文獻1張堯學，史美林編著計算機操作系統(tǒng)教程（第三版）清華大學出版社2006 2閔聯(lián)營，何克右主編c+程序設計教程武漢理工大學出版社2005f2源代碼以下文件在control.h中#include#include/格式化輸出#i

20、nclude/隨機數(shù)的頭文件using namespace std;struct pageint page_num; /頁面號int memory_num; /頁面對應的內存物理塊號int is_in_memory; /狀態(tài)標志，判斷頁面是否在內存;class controlpublic:control();/構造函數(shù)control();/析構函數(shù)void init();/初始化函數(shù)，對頁表，物理塊進行初始化void fifo();void opt();void print();輸出在物理塊中當前存在的頁號private:page page_table10;/創(chuàng)建頁表大小有10項int pag

21、e_size,memory_size;/輸入的頁面數(shù)和內存物理塊數(shù)int *page_array,*memory;/請求頁面的輸入序列，和模擬內存用來存放序列號;void control:init()for(int i=0;i10;i+)page_tablei.page_num=i;page_tablei.memory_num=-1;page_tablei.is_in_memory=0;for(i=0;imemory_size;i+)memoryi=-1;control:control()int select1 ,select2;/分別指示是隨機產生序列或用戶輸入和選擇哪種替換算法char c

22、hoice;cout輸入給定的頁面數(shù)：page_size;cout輸入給作業(yè)分配內存的物理塊數(shù)memory_size;page_array=new intpage_size;memory=new intmemory_size;loop: cout -endl;cout 0.用戶輸入請求序列 1.隨機生成請求序列endl; cout -select1;if(select1=1)cout隨機生成頁面請求序列（0-10）endl;int temp1;for(int i=0;ipage_size;i+)temp1=rand()%10;couttemp1 ;page_arrayi=temp1;coute

23、ndl;else if(select1=0)int temp2;cout輸入page_size個請求頁面號（0-10）endl;for(int i=0;itemp2;page_arrayi=temp2;else exit(0);cout請選擇使用那種替換算法：0、退出 1、fifo 2、optselect2;if(select2=1) control:fifo();else if(select2=2) control:opt();else exit(0); coutchoice;if(choice=y | choice=y) goto loop;else exit(0);control:con

24、trol() delete page_array; delete memory;void control:print()for(int q=0;qmemory_size;q+)coutmemoryq ;void control:fifo()cout-fifo-endl;control:init();int *save=new intpage_size;int count=0;int times=0;/記錄缺頁次數(shù)int first_inmemory=0;/記錄最先被占用的物理塊號，裝有最先進入內存的頁面號int is_full=0;/記錄物理塊是否已被占滿，當is_full=memory_si

25、ze時表示已經裝滿，如果再缺頁則發(fā)生替換 int page=0;/記錄將要訪問的頁面號control:print(); do/當內存沒有放滿if(page_tablepage_arraypage.is_in_memory=1)coutsetw(8)page_arraypage 已經在內存！endl;page+;control:print();if(page=page_size) break;else continue;elsetimes+;coutsetw(8)page_arraypage 不在內存，直接加載頁面!endl; memoryis_full=page_arraypage;contr

26、ol:print();for(int j=0;j10;j+)if(page_tablej.memory_num=is_full) /該物理地址已經被占用 page_tablej.memory_num=-1; page_tablej.is_in_memory=0;break;page_tablepage_arraypage.is_in_memory=1;page_tablepage_arraypage.memory_num=is_full;is_full+; page+;if(page=page_size) break;while(is_full!=memory_size);for(int i=

27、page;ipage_size;i+)/當內存已經放滿，需要替換if(page_tablepage_arrayi.is_in_memory=1)coutsetw(8)page_arrayi 已經在內存!endl;control:print();continue;elsetimes+;memoryfirst_inmemory=page_arrayi;for(int j=0;j10;j+)if(page_tablej.memory_num=first_inmemory)coutsetw(8)page_arrayi 不在內存，替換頁面：jendl;savecount+=j;page_tablej.m

28、emory_num=-1; page_tablej.is_in_memory=0;break;control:print();page_tablepage_arrayi.is_in_memory=1;page_tablepage_arrayi.memory_num=first_inmemory;first_inmemory=(first_inmemory+1)%memory_size;cout 頁面處理完成endl缺頁次數(shù)：timesendl;cout缺頁率：double(times)/page_size*100%endl;cout淘汰頁號的序列為：;for(i=0;icount;i+) coutsavei;cout結束endl;cout-endl;void control:opt()cout-opt-endl;control:init();int *change_page=new intpage_size;int *weight=new int memory_size; for(i=0;ipage_size;i+) chan