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