請求頁式管理缺頁中斷模擬設(shè)計--lru、opt

學(xué)號課程設(shè)計題目請求頁式管理缺頁中斷模擬設(shè)計LRU、OPT學(xué)院計算機科學(xué)與技術(shù)學(xué)院專業(yè)班級姓名指導(dǎo)教師課程設(shè)計任務(wù)書學(xué)生姓名指導(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ù)（包括課程設(shè)計工作量及其技術(shù)要求，以及說明書撰寫等具體要求）1實現(xiàn)指定淘汰算法。能夠處理以下的情形能夠輸入給作業(yè)分配的內(nèi)存塊數(shù)；能夠輸入給定的頁面，并計算發(fā)生缺頁的次數(shù)以及缺頁率；缺頁時，如果發(fā)生頁面置換，輸出淘汰的頁號。2設(shè)計報告內(nèi)容應(yīng)說明需求分析；功能設(shè)計（數(shù)據(jù)結(jié)構(gòu)及模塊說明）；開發(fā)平臺及源程序的主要部分；測試用例，運行結(jié)果與運行情況分析；自我評價與總結(jié)I）你認為你完成的設(shè)計哪些地方做得比較好或比較出色；II）什么地方做得不太好，以后如何改正；III）從本設(shè)計得到的收獲（在編寫，調(diào)試，執(zhí)行過程中的經(jīng)驗和教訓(xùn)）；IV）完成本題是否有其他方法（如果有，簡要說明該方法）；時間安排設(shè)計安排一周周1、周2完成程序分析及設(shè)計。周2、周3完成程序調(diào)試及測試。周4、周5驗收、撰寫課程設(shè)計報告。（注意事項嚴(yán)禁抄襲，一旦發(fā)現(xiàn)，一律按0分記）指導(dǎo)教師簽名年月日系主任（或責(zé)任教師）簽名年月日請求頁式管理缺頁中斷模擬設(shè)計LRU、OPT1設(shè)計目的與功能11設(shè)計目的鞏固并加深對虛擬存儲器、請求頁式存儲管理等概念的理解，掌握請求頁式管理中的置換算法的基本思想。并針對LRU最近最久未使用頁面置換算法，以及OPT理想型淘汰算法兩種算法，利用高級語言，設(shè)計出相應(yīng)的模擬程序。結(jié)合設(shè)計的程序，在理論聯(lián)系實際的基礎(chǔ)上，分析各個頁面置換算法的優(yōu)缺點。以及在對課程的整體把握上，提升對操作系統(tǒng)這門課程的全面認識。12設(shè)計功能本次課程設(shè)計需要實現(xiàn)LRU和OPT兩種置換算法。能夠?qū)崿F(xiàn)以下功能1）能夠輸入給作業(yè)分配的內(nèi)存塊數(shù)；2）能夠輸入給定的頁面，并計算發(fā)生缺頁的次數(shù)以及缺頁率；3）缺頁時，如果發(fā)生頁面置換，輸出淘汰的頁號。2設(shè)計需求分析21需求分析211請求頁式管理的實現(xiàn)請求頁式管理是在靜態(tài)頁式管理的基礎(chǔ)上發(fā)展起來的，它允許只裝入部分頁面的程序和數(shù)據(jù)，便啟動運行。此后，再通過調(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ǔ)上形成的。212置換算法分析請求頁式管理中的置換算法在內(nèi)存中沒有空閑頁時被調(diào)用，它的目的是選出一個被淘汰的頁面。如果內(nèi)存中有足夠的空閑頁面存放調(diào)入的頁，則不必使用置換算法。本次設(shè)計使用最近最久未使用頁面置換算法LEASTRECENTLYUSED，LRU和理想型淘汰算法OPTIONALREPLACEMENTALGORITHM，OPT。LRU置換算法最近最久未使用頁面置換算法LEASTRECENTLYUSED，LRU，該算法的基本思想是當(dāng)需要淘汰某一頁時，選擇離當(dāng)前時間最近的一段時間內(nèi)最久沒有使用過的頁先淘汰。該算法的主要出發(fā)點是，如果某頁被訪問了，則它可能馬上還要被訪問，或者如果某頁很長時間未被訪問，則它在最近一段時間也不會被訪問。OPT置換算法理想型淘汰算法OPTIONALREPLACEMENTALGORITHM，OPT，該算法淘汰在訪問串中將來再也不出現(xiàn)的或者是在離當(dāng)前最遠的位置上出現(xiàn)的頁，這樣淘汰掉該頁將不會造成因需要訪問該頁又立即把它調(diào)入的現(xiàn)象。這種算法難以實現(xiàn)，因為它要求必須預(yù)先知道每一個進程的訪問串。22數(shù)據(jù)結(jié)構(gòu)及功能框圖基本數(shù)據(jù)變量說明INTINPUT/輸入的頁面數(shù)INTNUM/內(nèi)存塊允許裝入頁面數(shù)INTIN/準(zhǔn)備調(diào)入的頁面序列INTMEMORY/用來記錄進入內(nèi)存的頁面信息STRUCTPAGEINTPNUMBER/頁面的頁號INTMNUMBER/在內(nèi)存中對應(yīng)的塊號INTSTAYIN/是否在內(nèi)存中PAGEPTOTALN/對N個頁面進行操作基本操作的函數(shù)原型說明VOIDLRU/實現(xiàn)LRU算法的函數(shù)VOIDOPT/實現(xiàn)OPT算法的函數(shù)請求頁式管理實現(xiàn)過程3源程序的主要部分31源程序簡介本次設(shè)計中LRU以及OPT算法中頁面置換的思想，分別對照頁框的內(nèi)容，向前查找最久未被使用的頁面號和向后查找最后被使用的頁面號，將其替換之。在設(shè)計的思想上可以轉(zhuǎn)化為以當(dāng)前即將調(diào)入的頁面為中心，LRU為向前查找離中心最遠的頁號，而OPT為向后查找離中心最遠的頁號。32源程序核心代碼開始結(jié)束請求頁面序列是否結(jié)束頁面是否在內(nèi)存中內(nèi)存塊是否已滿選擇要調(diào)入頁面放入未被占用的內(nèi)存塊中,修改頁表利用算法,選擇應(yīng)該替換的頁面并修改YYYNNN321MAIN函數(shù)代碼MAIN函數(shù)實現(xiàn)對各輸入數(shù)據(jù)及待數(shù)據(jù)結(jié)構(gòu)的初始化，以及通過選擇來調(diào)用LRU或OPT算法。偽代碼如下INTMAIN/頁號、塊號、頁面順序的輸入，以及初始化等工作。WHILETRUE/部分全局變量的初始化工作，每次循環(huán)需重新開始CHARCHOSECOUTCHOSEIFCHOSE1SWITCHCHOSECASE1LRUBREAKCASE2OPTBREAKCOUT0,0,/GET宏，傳遞的參數(shù)為,等RETURNGETNUM/返回頁框號325GETSMBLX,SMBLY,SMBLZ宏的代碼GETLRU和GETOPT的搜索算法在思想上相似，即前者向前搜索頁第一次出現(xiàn)的申請序號，而后者是向后搜索接下來第一次出現(xiàn)的申請序號，所以用GET宏來對相同代碼進行公操作，偽代碼如下DEFINEGETSMBLX,SMBLY,SMBLZFORI0IINCLUDEUSINGNAMESPACESTDINTINPUT,NUM,IN,MEMORYSTRUCTPAGEINTPNUMBERINTMNUMBERINTSTAYINPAGEPTOTAL10VOIDLRUVOIDOPTINTGETLRUINTPAGEINTGETOPTINTPAGEINTMAINCOUTINPUTCOUTNUMINNEWINTINPUTMEMORYNEWINTNUMCOUTTEMPINITEMPCOUTCHOSEIFCHOSE1SWITCHCHOSECASE1LRUBREAKCASE2OPTBREAKCOUT0,RETURNGETNUMVOIDLRUCOUT“LRU替換算法過程如下“ENDLLOLRUVOIDOPTCOUT“OPT替換算法過程如下“ENDLLOOPT本科生課程設(shè)計成績評定表序號評分項目滿分實