操作系統(tǒng)課設(shè)-LRU-OPT

1、武漢理工大學(xué)操作系統(tǒng)課程設(shè)計學(xué) 號： 01209103401課 程 設(shè) 計題 目請求頁式管理缺頁中斷模擬設(shè)計-LRU、OPT學(xué) 院計算機科學(xué)與技術(shù)學(xué)院專 業(yè)計算機科學(xué)與技術(shù)專業(yè)班 級計算機0901班姓 名指導(dǎo)教師王紅霞2012年1月11日課程設(shè)計任務(wù)書學(xué)生姓名： 專業(yè)班級： 計算機0901班 指導(dǎo)教師： 王紅霞 工作單位： 計算機科學(xué)與技術(shù)學(xué)院 題 目: 請求頁式管理缺頁中斷模擬設(shè)計- LRU、OPT初始條件：1預(yù)備內(nèi)容：閱讀操作系統(tǒng)的內(nèi)存管理章節(jié)內(nèi)容，了解有關(guān)虛擬存儲器、頁式存儲管理等概念，并體會和了解缺頁和頁面置換的具體實施方法。2實踐準(zhǔn)備：掌握一種計算機高級語言的使用。要求完成的主要任務(wù)

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

3、，簡要說明該方法）；v）對實驗題的評價和改進意見，請你推薦設(shè)計題目。時間安排：設(shè)計安排一周：周1、周2：完成程序分析及設(shè)計。周2、周3：完成程序調(diào)試及測試。周4、周5：驗收，撰寫課程設(shè)計報告。（注意事項：嚴禁抄襲，一旦發(fā)現(xiàn)，抄與被抄的一律按0分記）指導(dǎo)教師簽名： 年 月 日系主任（或責(zé)任教師）簽名： 年 月 日請求頁式管理缺頁中斷模擬設(shè)計 -LRU、OPT1 設(shè)計目的與功能1.1 設(shè)計目的鞏固并加深對虛擬存儲器、請求頁式存儲管理等概念的理解，掌握請求頁式管理中的置換算法的基本思想。并針對LRU(最近最久未使用頁面置換算法)，以及OPT(理想型淘汰算法)兩種算法，利用高級語言，設(shè)計出相應(yīng)的模擬程

4、序。結(jié)合設(shè)計的程序，在理論聯(lián)系實際的基礎(chǔ)上，分析各個頁面置換算法的優(yōu)缺點。以及在對課程的整體把握上，提升對操作系統(tǒng)這門課程的全面認識。1.2 設(shè)計功能本次課程設(shè)計需要實現(xiàn)LRU和OPT兩種置換算法。能夠?qū)崿F(xiàn)以下功能：1） 能夠輸入給作業(yè)分配的內(nèi)存塊數(shù)；2） 能夠輸入給定的頁面，并計算發(fā)生缺頁的次數(shù)以及缺頁率； 3） 缺頁時，如果發(fā)生頁面置換，輸出淘汰的頁號。在實現(xiàn)以上功能的前提下，程序也應(yīng)該達到正確性、可讀性、健壯性、效率與地存儲量要求等算法的5個特性。2 設(shè)計需求分析2.1 需求分析2.1.1 請求頁式管理的實現(xiàn)請求頁式管理是在靜態(tài)頁式管理的基礎(chǔ)上發(fā)展起來的，它允許只裝入部分頁面的程序和數(shù)據(jù)

5、，便啟動運行。此后，再通過調(diào)頁功能和頁面置換功能，陸續(xù)把即將要運行的頁面調(diào)入內(nèi)存，同時把暫時不運行的頁面換出到外存上，置換時以頁面為單位。為了能實現(xiàn)請求調(diào)頁和置換功能，系統(tǒng)必須提供必要的硬件支持和相應(yīng)的軟件。其中硬件支持包括：1） 請求分頁的頁表機制，它是在純分頁的頁表機制上增加若干項而形成的，作為請求分頁的數(shù)據(jù)結(jié)構(gòu)；2） 缺頁中斷機構(gòu)，當(dāng)要訪問的頁面尚未調(diào)入內(nèi)存時，便產(chǎn)生一缺頁中斷，以請求OS將所缺的頁調(diào)入內(nèi)存；3） 地址變換機構(gòu)，它同樣是在純分頁地址變換機構(gòu)的基礎(chǔ)上形成的。2.1.2 置換算法分析請求頁式管理中的置換算法在內(nèi)存中沒有空閑頁時被調(diào)用，它的目的是選出一個被淘汰的頁面。如果內(nèi)存中

6、有足夠的空閑頁面存放調(diào)入的頁，則不必使用置換算法。本次設(shè)計使用最近最久未使用頁面置換算法(least recently used，LRU)和理想型淘汰算法(optional replacement algorithm，OPT)。2.1.2.1 LRU置換算法最近最久未使用頁面置換算法(least recently used，LRU)，該算法的基本思想是：當(dāng)需要淘汰某一頁時，選擇離當(dāng)前時間最近的一段時間內(nèi)最久沒有使用過的頁先淘汰。該算法的主要出發(fā)點是，如果某頁被訪問了，則它可能馬上還要被訪問，或者如果某頁很長時間未被訪問，則它在最近一段時間也不會被訪問。2.1.2.2 OPT置換算法理想型淘汰算

7、法(optional replacement algorithm，OPT)，該算法淘汰在訪問串中將來再也不出現(xiàn)的或者是在離當(dāng)前最遠的位置上出現(xiàn)的頁，這樣淘汰掉該頁將不會造成因需要訪問該頁又立即把它調(diào)入的現(xiàn)象。這種算法難以實現(xiàn)，因為它要求必須預(yù)先知道每一個進程的訪問串。請求頁式管理的具體實現(xiàn)過程如圖1所示。2.2 數(shù)據(jù)結(jié)構(gòu)及功能框圖2.2.1 數(shù)據(jù)結(jié)構(gòu)程序是以基本的變量和結(jié)構(gòu)體實現(xiàn)，在兩種算法中有大量的代碼重用，故采用宏定義(#define LO(wname)等，使代碼更加簡化。/- - - - - - - - - - - 基本數(shù)據(jù)變量說明- - - - - - - - - - - - - in

8、t input; /輸入的頁面數(shù)int num; /內(nèi)存塊允許裝入頁面數(shù)int *in; /準(zhǔn)備調(diào)入的頁面序列 int *memory; /用來記錄進入內(nèi)存的頁面信息struct pageint Pnumber; /頁面的頁號int Mnumber; /在內(nèi)存中對應(yīng)的塊號int stayin; /是否在內(nèi)存中;page PtotalN; /對N個頁面進行操作開始結(jié)束請求頁面序列是否結(jié)束頁面是否在內(nèi)存中內(nèi)存塊是否已滿選擇要調(diào)入頁面放入未被占用的內(nèi)存塊中,修改頁表利用算法,選擇應(yīng)該替換的頁面并修改YYYNNN圖1 請求頁式管理實現(xiàn)過程/- - - - - - - - - - - 基本操作的函數(shù)原型

9、說明- - - - - - - - - - - - - void LRU(); /實現(xiàn)LRU算法的函數(shù)void OPT(); /實現(xiàn)OPT算法的函數(shù)int getLRU(int page); /LRU中頁面置換函數(shù)，對給定的頁page,替換頁框中的頁int getOPT(int page); /OPT中頁面置換函數(shù)，對給定的頁page,替換頁框中的頁#define LO(wname); /對LRU和OPT中的前num個頁的公操作處理#define get(smblx,smbly,smblz); /頁面置換過程的公操作，用smblx等變量替換 2.2.2 程序功能框圖程序中首先輸入頁面的數(shù)目存入

10、input中，輸入頁框的數(shù)目存入num中，在按次序輸入頁面號碼，存入in數(shù)組中。程序給出選擇，當(dāng)進行LRU模塊時，LRU模塊對頁面進行分配，當(dāng)出現(xiàn)缺頁調(diào)用getLRU()進行缺頁處理，而OPT模塊與之類似。程序功能框圖如圖2。Main()getOPT (int page)getLRU(int page)OPT()LRU()圖2 程序功能框圖3 源程序的主要部分3.1 源程序簡介本次設(shè)計中LRU以及OPT算法中頁面置換的思想，分別對照頁框的內(nèi)容，向前查找最久未被使用的頁面號和向后查找最后被使用的頁面號，將其替換之。在設(shè)計的思想上可以轉(zhuǎn)化為以當(dāng)前即將調(diào)入的頁面為中心，LRU為向前查找離中心最遠的頁

11、號，而OPT為向后查找離中心最遠的頁號。這樣在方法上有了共同之處，以此可以通過對相同的代碼進行宏定義。3.2 源程序核心代碼3.2.1 main函數(shù)代碼main函數(shù)實現(xiàn)對各輸入數(shù)據(jù)及待數(shù)據(jù)結(jié)構(gòu)的初始化，以及通過選擇來調(diào)用LRU或OPT算法。偽代碼如下：int main() /頁號、塊號、頁面順序的輸入，以及初始化等工作。while(true) /部分全局變量的初始化工作，每次循環(huán)需重新開始 char chose;cout請您選擇：1、LRU算法endl;cout 2、OPT算法endl;cout 3、退出endl; cout*chose;if(chose!=1&chose!=2)break;s

12、witch(chose)case 1:LRU();break;case 2:OPT();break; cout*endl;3.2.2 LRU及OPT函數(shù)代碼LRU和OPT的主要思想有許多共同之處，所以通過宏定義，來實現(xiàn)程序的共同功能。程序中都是通過LO宏來實現(xiàn)的，區(qū)別在于傳遞的參數(shù)不同，即LRU函數(shù)調(diào)用getLRU()子函數(shù)。而OPT函數(shù)調(diào)用getOPT()函數(shù)。void LRU() coutLRU替換算法過程如下:endl; LO(LRU); /通過LO宏，傳遞LRU給get#wname(int page)，即getLRU(int page)void OPT() coutOPT替換算法過程如

13、下:endl; LO(OPT); /通過LO宏，傳遞OPT給get#wname(int page)，即getOPT(int page)3.2.3 LO（wname）宏的代碼LO宏是用來對LRU和OPT的置換進行公處理的，即在內(nèi)存塊未滿，或者不需要發(fā)生置換時兩者的代碼是相同的，而唯一不同在于缺頁中斷處理函數(shù)，getLRU(int page)或者getOPT(int page)。所以，通過宏定義，把不同的代碼作為參數(shù)傳遞，來實現(xiàn)不同函數(shù)的功能。偽代碼如下：#define LO(wname)int i,missTime=0,replace=0,full=0,page=0; /i 為循環(huán)控制變量，mi

14、ssTime為缺頁次數(shù)/replace代表置換的頁框號full為控制變量，page為頁面數(shù)do /實現(xiàn)塊未滿時的頁面分配，LRU和OPT相同while(full!=num);for( i=page;iinput;i+)if(Ptotalini.stayin =1) coutini號頁已在頁框中，endl;elsemissTime+;replace=get#wname(i); /根據(jù)傳遞的參數(shù)不同，調(diào)度不同的函數(shù)，返回頁框號 /進行頁面替換coutendl經(jīng)統(tǒng)計：缺頁次數(shù)：missTime次缺頁率double(missTime)/input*100%=0,=0,等 return getNum;

15、/返回頁框號 int getOPT(int page) get(+,); /get宏，傳遞的參數(shù)為+,等 return getNum; /返回頁框號3.2.5 get(smblx,smbly,smblz)宏的代碼getLRU和getOPT的搜索算法在思想上相似，即前者向前搜索頁第一次出現(xiàn)的申請序號，而后者是向后搜索接下來第一次出現(xiàn)的申請序號，所以用get宏來對相同代碼進行公操作，偽代碼如下：#define get(smblx,smbly,smblz) for(i=0;inum;i+)for(int j=0;j10;j+)if(Ptotalj.Mnumber=i)for(int t=page#s

16、mblx 1;t#smbly;t#smblx#smblx) /宏填充部分，填充內(nèi)容如上 /向前或后找出該頁第一次申請的序號for(i=0;inum;i+)if(geti#smblz getgetNum) /返回將要被置換的頁號，存入到getNUM中g(shù)etNum=i; 4 測試4.1測試用例設(shè)計請求分頁管理系統(tǒng)中，有一用戶作業(yè)，它一次要訪問的頁的序列是：2 3 2 1 5 2 4 5 3 2 5 2 共12頁，若分配給作業(yè)可以使用的主存空間供3個物理塊，則LRU和OPT的置換算法的頁面分配如表1和表2。表1 LRU頁面置換算法LRU2 32152453252頁1222222223333頁2333

17、55555555頁3111444222判斷共產(chǎn)生7次缺頁中斷，淘汰頁號分別為：3， 1 ，2， 4 缺頁率：58.33%表2 OPT頁面置換算法OPT2 32152453252頁1222222444222頁233333333333頁3155555555判斷共產(chǎn)生6次缺頁中斷，淘汰頁號分別為： 1 ，2 ，4 缺頁率：50%4.2 運行結(jié)果及情況分析根據(jù)測試用例，對結(jié)果進行測試分析，以下為程序的分析過程。1) 程序首先需要輸入頁面數(shù)、頁框數(shù)，然后給出頁面請求序列，最后可以對頁面置換算法進行選擇（LRU和OPT的選擇），在每執(zhí)行完一次后，程序會繼續(xù)給出選擇界面，方面兩種算法過程和結(jié)果的對照。程序的

18、輸入界面如圖3所示；圖3 輸入界面 2) 在輸入界面中輸入1，則程序調(diào)用LRU頁面替換算法，則程序的頁面分配過程，缺頁率，缺頁次數(shù)會被一一列出，從過程可以看出，頁面替換的順序為3,1,2,4，這與用例的正確結(jié)果吻合，達到了算法的目的，具體情況如圖4所示：圖4 LRU替換算法過程和結(jié)果3）當(dāng)輸入2時，程序調(diào)用OPT算法，程序的頁面分配情況，缺頁次數(shù)及缺頁率如圖5所示，從圖中可以看出，程序中被替換掉的頁面分別為1,2,4，這也和用例吻合，得出了正確的結(jié)果，OPT算法的缺頁次數(shù)為6，缺頁率為50%。圖5 OPT替換算法過程和結(jié)果小結(jié)：從程序的運行結(jié)果和輸出情況可以看出，程序有良好的交互界面，有正確的

19、結(jié)果，并且有一定的健壯性，如對于用例中的2 3 2，程序在沒有在未用完頁框的情況下直接給第三次請求的2號頁分配一個新頁框，這說明程序有嚴謹?shù)倪壿嫴襟E。5 評價和總結(jié)5.1 自我評價本次課程設(shè)計用時用高級語言模擬系統(tǒng)中的頁面置換算法，從整體上達到了設(shè)計的目的和要求。我的設(shè)計思路是首先，要對問題有一個整體而全面的認識，抓住問題的核心所在；其次，要針對問題，主要是核心癥結(jié)，給出設(shè)計思想，這時可以查閱書籍或搜尋網(wǎng)上資料，輔助自己對的問題理解，以確保設(shè)計思想的正確性；再次，解決核心問題，在此基礎(chǔ)之上，為設(shè)計豐滿羽翼，達到算法所要求的5個特性：正確性、可讀性、健壯性、效率與地存儲量要求；最后，對程序反復(fù)調(diào)

20、試，盡己所能把算法精簡改進。就設(shè)計優(yōu)點來談，首先程序的思想與計算機操作系統(tǒng)頁面置換算法（LRU,OPT）的思想吻合，這樣確保了程序的正確性和可讀性，并且從本質(zhì)上體會到頁面置換算法思想的精髓所在；其次，程序中的大部分的數(shù)據(jù)結(jié)構(gòu)僅僅為簡單的變量和結(jié)構(gòu)體數(shù)組，沒有冗雜的指針和鏈表，使程序用盡量簡單的方法實現(xiàn)了盡量多的功能；最后，針對LRU和OPT算法中思想的相似處，我采用了宏定義，不僅大大優(yōu)化了代碼使最后的代碼大量的減少，而且使兩種算法的區(qū)別明顯的體現(xiàn)出來，易于對兩種置換算法的仔細斟酌、比較。本次課程設(shè)計的缺點為實驗的平臺仍是控制臺程序（DOS環(huán)境），所以在以后的設(shè)計中，將嘗試VC界面程序。5.2

21、收獲和改進本次課設(shè)的收獲分為兩點：在對課程內(nèi)容上，從模擬缺頁中斷頁面置換算法中進一步理解了操作系統(tǒng)原理，對這門課程有了更深的認識，并且激起了想進一步了解如windows操作系統(tǒng)(windows核心編程)的興趣；在對編程技巧方面，從了解MFC后，對MFC中的宏定義有了一定的了解和認識，發(fā)現(xiàn)宏定義也是一種巧妙的封裝方法。本程序中兩次使用了宏定義，程序在編譯的過程會將代碼插入到宏調(diào)用處，但在程序的讀者看來，程序會更加的精簡、明了，易于對比。程序從設(shè)計技巧來說還有許多其他的方法，如對于LRU算法可以用隊列來記錄頁面置換的順序，而與之對應(yīng)的OPT算法則可以棧來記錄接下來要調(diào)入頁面的次序。在記錄LRU（最

22、近最久未使用）時，也可以用NUM*NUM的二階數(shù)組來記錄等。5.3 評價和意見本次課程設(shè)計是對操作系統(tǒng)這門課程理論知識的映射，不同的題目是對不同知識模塊進行模擬，在實踐的基礎(chǔ)上加深了對操作系統(tǒng)理論的認識，在某種程度上得到了提高。對本次課程設(shè)計的意見如下：因為操作系統(tǒng)這門課程中并沒有直接涉及到某個操作系統(tǒng)（Windows、Linux等）的設(shè)計過程的講解，課程內(nèi)容過于理論化，而在課程設(shè)計的過程中題目過于細節(jié)化，從而對操作系統(tǒng)失去總體觀念。希望課程設(shè)計中題目應(yīng)當(dāng)為兩個不同的知識點，在一定程度上加深難度，也擴充了理解的知識面。6 參考文獻1 張堯?qū)W，計算機操作系統(tǒng)教程，清華大學(xué)出版社，2005年6月2

23、 閔聯(lián)營，c+程序設(shè)計教程武漢理工大學(xué)出版社，2005年7月3 王艷平，Windows 程序設(shè)計（第二版），人民郵電出版社，2010年2月附：源代碼#include#includeusing namespace std;int input,num,*in,*memory; struct pageint Pnumber;int Mnumber;int stayin;page Ptotal10; void LRU();void OPT();int getLRU(int page);int getOPT(int page);int main()cout*endl; cout請輸入準(zhǔn)備調(diào)入頁面的數(shù)目:

24、input; cout請輸入物理塊數(shù)目num;in= new intinput; memory=new intnum; cout請依次輸入input個頁面號(0-9)endl; int i,temp; for( i=0;itemp;ini=temp; cout*endl;while(true) for(int n=0;n10;n+) Ptotaln.Pnumber=n;Ptotaln.Mnumber=-1;Ptotaln.stayin =0;for(i=0;inum;i+) memoryi=-1; char chose;coutendl;cout請您選擇：1、LRU算法endl;cout 2、

25、OPT算法endl;cout 3、退出endl; cout*chose;if(chose!=1&chose!=2)break;switch(chose)case 1:LRU();break;case 2:OPT();break; cout*endl;delete in;delete memory;return 0;#define LO(wname)int i,missTime=0,replace=0,full=0,page=0;do if(Ptotalinpage.stayin =1)coutinpage號頁已在頁框中，endl;page+;if(page=input)break;else c

26、ontinue;elsemissTime+;coutinpage號頁不在頁框中，將其調(diào)入full號頁框中，endl;memoryfull=inpage;for(int j=0;j10;j+)if( Ptotalj.Mnumber= full) Ptotalj.Mnumber=-1; Ptotalj.stayin=0;break;Ptotalinpage.stayin=1;Ptotalinpage.Mnumber=full; full+;page+;if(page=input) break;while(full!=num);for( i=page;iinput;i+)if(Ptotalini.stayin =1)coutini號頁已在頁框中，endl;elsemissTime+;repla