學(xué)號(hào)課程設(shè)計(jì)題目請(qǐng)求頁(yè)式管理缺頁(yè)中斷模擬設(shè)計(jì)LRU、隨機(jī)淘汰算法學(xué)院計(jì)算機(jī)學(xué)院專業(yè)班級(jí)姓名指導(dǎo)教師課程設(shè)計(jì)任務(wù)書(shū)學(xué)生姓名指導(dǎo)教師工作單位計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院題目請(qǐng)求頁(yè)式管理缺頁(yè)中斷模擬設(shè)計(jì)LRU、隨機(jī)淘汰算法初始條件1預(yù)備內(nèi)容閱讀操作系統(tǒng)的內(nèi)存管理章節(jié)內(nèi)容，了解有關(guān)虛擬存儲(chǔ)器、頁(yè)式存儲(chǔ)管理等概念，并體會(huì)和了解缺頁(yè)和頁(yè)面置換的具體實(shí)施方法。2實(shí)踐準(zhǔn)備掌握一種計(jì)算機(jī)高級(jí)語(yǔ)言的使用。要求完成的主要任務(wù)（包括課程設(shè)計(jì)工作量及其技術(shù)要求，以及說(shuō)明書(shū)撰寫(xiě)等具體要求）1實(shí)現(xiàn)指定淘汰算法。能夠處理以下的情形能夠輸入給作業(yè)分配的內(nèi)存塊數(shù)；能夠輸入給定的頁(yè)面，并計(jì)算發(fā)生缺頁(yè)的次數(shù)以及缺頁(yè)率；缺頁(yè)時(shí)，如果發(fā)生頁(yè)面置換，輸出淘汰的頁(yè)號(hào)。2設(shè)計(jì)報(bào)告內(nèi)容應(yīng)說(shuō)明需求分析；功能設(shè)計(jì)（數(shù)據(jù)結(jié)構(gòu)及模塊說(shuō)明）；開(kāi)發(fā)平臺(tái)及源程序的主要部分；測(cè)試用例，運(yùn)行結(jié)果與運(yùn)行情況分析；自我評(píng)價(jià)與總結(jié)I）你認(rèn)為你完成的設(shè)計(jì)哪些地方做得比較好或比較出色；II）什么地方做得不太好，以后如何改正；III）從本設(shè)計(jì)得到的收獲（在編寫(xiě)，調(diào)試，執(zhí)行過(guò)程中的經(jīng)驗(yàn)和教訓(xùn)）；IV）完成本題是否有其他方法（如果有，簡(jiǎn)要說(shuō)明該方法）；時(shí)間安排設(shè)計(jì)安排一周周1、周2完成程序分析及設(shè)計(jì)。周2、周3完成程序調(diào)試及測(cè)試。周4、周5驗(yàn)收、撰寫(xiě)課程設(shè)計(jì)報(bào)告。（注意事項(xiàng)嚴(yán)禁抄襲，一旦發(fā)現(xiàn)，一律按0分記）指導(dǎo)教師簽名年月日系主任（或責(zé)任教師）簽名年月日請(qǐng)求頁(yè)式管理缺頁(yè)中段模擬設(shè)計(jì)LRU、隨機(jī)淘汰算法1概述11原理頁(yè)式存儲(chǔ)管理把內(nèi)存分割成大小相等位置固定的若干區(qū)域，叫內(nèi)存頁(yè)面，內(nèi)存的分配以“頁(yè)”為單位，一個(gè)程序可以占用不連續(xù)的頁(yè)面，邏輯頁(yè)面的大小和內(nèi)存頁(yè)面的大小相同，內(nèi)外存的交換也以頁(yè)為單位進(jìn)行，頁(yè)面交換時(shí)，先查詢快表，若快表中找不到所需頁(yè)面再去查詢頁(yè)表，若頁(yè)表中仍未找到說(shuō)明發(fā)生了缺頁(yè)中斷，需先將所需頁(yè)面調(diào)入內(nèi)存再進(jìn)行存取。12目的通過(guò)分析、設(shè)計(jì)和實(shí)現(xiàn)頁(yè)式虛擬存儲(chǔ)管理缺頁(yè)中斷的模擬系統(tǒng)，熟悉和掌握請(qǐng)求分頁(yè)式存儲(chǔ)管理的實(shí)現(xiàn)過(guò)程，重點(diǎn)掌握當(dāng)請(qǐng)求頁(yè)面不在內(nèi)存而內(nèi)存塊已經(jīng)全部被占用時(shí)的替換算法，熟悉常見(jiàn)替換算法的原理和實(shí)現(xiàn)過(guò)程，并利用替換算法的評(píng)價(jià)指標(biāo)缺頁(yè)次數(shù)和缺頁(yè)率，來(lái)對(duì)各種替換算法進(jìn)行評(píng)價(jià)比較。2需求分析用一種計(jì)算機(jī)高級(jí)語(yǔ)言來(lái)實(shí)現(xiàn)請(qǐng)求頁(yè)式管理缺頁(yè)中段模擬設(shè)計(jì)的LRU和隨機(jī)淘汰算法，設(shè)計(jì)要求如下（1）能夠輸入給作業(yè)分配的內(nèi)存塊數(shù)；（2）能夠輸入給定的頁(yè)面調(diào)用次序；（3）缺頁(yè)時(shí)，如果發(fā)生頁(yè)面置換，輸出淘汰的頁(yè)號(hào)。（4）能統(tǒng)計(jì)頁(yè)面調(diào)用缺頁(yè)次數(shù)和缺頁(yè)率請(qǐng)求分頁(yè)流程圖2功能設(shè)計(jì)21數(shù)據(jù)結(jié)構(gòu)（1）用結(jié)構(gòu)體定義頁(yè)表表項(xiàng)STRUCTPAGEINTBLOCKID/塊號(hào)INTSTATUS/狀態(tài)，1為空閑,1為占用開(kāi)始選擇調(diào)入頁(yè)面號(hào)是否在內(nèi)存中是調(diào)入內(nèi)存內(nèi)存塊是否有空閑是選擇空閑物理塊使用頁(yè)面替換算法，替換已有頁(yè)面是是否還有請(qǐng)求頁(yè)面否結(jié)束（2）用結(jié)構(gòu)體定義內(nèi)存塊表項(xiàng)STRUCTBLOCKINTPAGEID/塊內(nèi)存放頁(yè)號(hào)INTSTATUS/是否空閑,1為空閑,1為占用2算法中涉及到的主要變量DEFINEMAX_BLOCK50DEFINEMAX_PAGE100INTPAGEMAX_PAGE/記錄頁(yè)的走向BOOLINSIDEMAX_PAGE/記錄是否缺頁(yè)，缺FALSEINTREPLACEMAX_PAGE/記錄替換次序,無(wú)替換為1，有替換為被替換頁(yè)號(hào)BLOCKBLOCKMAX_BLOCK/記錄物理塊PAGEPAGETABLEMAX_PAGE/記錄頁(yè)表INTPAGENUM/頁(yè)面?zhèn)€數(shù)INTPAGESUM/實(shí)際頁(yè)調(diào)用次數(shù)INTBLOCKSUM/實(shí)際塊數(shù)INTLACKSUM/缺頁(yè)次數(shù)FLOATLACKRATE/缺頁(yè)率INTRESULTTABLEMAX_PAGEMAX_BLOCK/用于存放程序執(zhí)行過(guò)程狀態(tài)表22模塊說(shuō)明3LRU淘汰算法VOIDLRU1、查看當(dāng)前頁(yè)面是否在內(nèi)存中，如果是則記錄當(dāng)前頁(yè)面調(diào)用狀態(tài)，將相應(yīng)的值賦給記錄狀態(tài)數(shù)組，返回2、當(dāng)前頁(yè)面不在內(nèi)存中，判斷內(nèi)存中是否存在空閑塊，如果有空閑塊，將當(dāng)前頁(yè)面調(diào)入內(nèi)存中，并更新頁(yè)表、塊表，以及記錄狀態(tài)數(shù)組中返回3、如果當(dāng)前內(nèi)存塊滿，且當(dāng)前頁(yè)面不在內(nèi)存中。使用最久最近未使用算法，在當(dāng)前內(nèi)存塊內(nèi)的頁(yè)中向前查找，最久未使用的權(quán)值最大，將權(quán)值最大的頁(yè)面號(hào)和所在內(nèi)存號(hào)返回使用當(dāng)前頁(yè)面替換權(quán)值最大的頁(yè)面，并更新頁(yè)表和塊表以及記錄狀態(tài)數(shù)組，返回4隨機(jī)淘汰算法VOIDRANDOM1、查看當(dāng)前頁(yè)面是否在內(nèi)存中，如果是則記錄當(dāng)前頁(yè)面調(diào)用狀態(tài)，將相應(yīng)的值賦給記錄狀態(tài)數(shù)組，返回2、當(dāng)前頁(yè)面不在內(nèi)存中，判斷內(nèi)存中是否存在空閑塊，如果有空閑塊，將當(dāng)前頁(yè)面調(diào)入內(nèi)存中，并更新頁(yè)表、塊表，以及記錄狀態(tài)數(shù)組中返回3、如果當(dāng)前內(nèi)存塊滿，且當(dāng)前頁(yè)面不在內(nèi)存中。使用隨機(jī)算法，隨機(jī)選擇一個(gè)內(nèi)存塊，將所選擇的內(nèi)存塊內(nèi)頁(yè)面的的頁(yè)面號(hào)和所在內(nèi)存號(hào)返回使用當(dāng)前頁(yè)面替換權(quán)值最大的頁(yè)面，并更新頁(yè)表和塊表以及記錄狀態(tài)數(shù)組，返回3開(kāi)發(fā)平臺(tái)及源程序主要部分31開(kāi)發(fā)平臺(tái)（1）使用系統(tǒng)WINDOWS7（2）使用語(yǔ)言C（3）開(kāi)發(fā)工具VISUALSTUDIO201032源程序主要部分最近最久未使用算法VOIDLRU/最近最久未使用INTPFORP0P0PIFBLOCKBPAGEIDPAGEPWEIGHTPBREAKIFWEIGHTFLAGIFFLAG1LRURESULTLACKSUM,LACKRATEPRINTTABLEELSEIFFLAG0RANDOMRESULTLACKSUM,LACKRATEPRINTTABLEELSECOUTFLAGIFFLAG0BREAKRETURN04調(diào)試報(bào)告41測(cè)試用例給定內(nèi)存物理塊數(shù)為3給定頁(yè)面數(shù)為5輸入的頁(yè)面號(hào)序列為12341251234542運(yùn)行結(jié)果及分析最近最久未使用淘汰算法的運(yùn)行結(jié)果如下隨機(jī)淘汰算法的運(yùn)行結(jié)果如下5總結(jié)在本次操作系統(tǒng)課程設(shè)計(jì)，我使用C實(shí)現(xiàn)請(qǐng)求頁(yè)式管理缺頁(yè)中斷模擬設(shè)計(jì)的隨機(jī)和LRU淘汰算法。在了解了虛擬存儲(chǔ)器和頁(yè)式存儲(chǔ)管理的有關(guān)內(nèi)容的基礎(chǔ)上，掌握了隨機(jī)和LRU淘汰算法的核心思想及算法的執(zhí)行流程。然后結(jié)合所掌握的C編程方法和技巧，編寫(xiě)正確的算法，模擬出請(qǐng)求頁(yè)式缺頁(yè)中斷的隨機(jī)和LRU淘汰算法。算法的設(shè)計(jì)主要是要把請(qǐng)求頁(yè)式管理的執(zhí)行步驟理解清晰，然后根據(jù)請(qǐng)求頁(yè)式管理的結(jié)構(gòu)，設(shè)計(jì)出符合實(shí)際的數(shù)據(jù)結(jié)構(gòu)，如頁(yè)表和塊表以及記錄狀態(tài)使用的數(shù)組等，然后根據(jù)執(zhí)行流程模擬出各個(gè)算法。LRU算法的執(zhí)行過(guò)程還是比較清晰的，我通過(guò)對(duì)內(nèi)存中內(nèi)存塊的頁(yè)，按照當(dāng)前的頁(yè)面順序向前查找，記錄此頁(yè)上次執(zhí)行的順序號(hào)。遍歷所有內(nèi)存塊后，執(zhí)行順序號(hào)最小的即為權(quán)值最大的，將此頁(yè)的頁(yè)號(hào)和所在內(nèi)存塊號(hào)返回，替換。隨機(jī)算法比較簡(jiǎn)單，使用隨機(jī)算法，在內(nèi)存塊中隨機(jī)選擇塊號(hào)，替換出內(nèi)存。本次的課程設(shè)計(jì)讓我鞏固了操作系統(tǒng)的相關(guān)知識(shí)，加深了對(duì)課本上理論知識(shí)的理解深度，特別是對(duì)請(qǐng)求式頁(yè)式管理的理解。在編寫(xiě)程序之前，我查閱了有關(guān)請(qǐng)求頁(yè)式管理的相關(guān)資料，對(duì)請(qǐng)求頁(yè)式管理的數(shù)據(jù)結(jié)構(gòu)有了更加清晰的認(rèn)識(shí)，這直接關(guān)系到程序編寫(xiě)的正確性，因?yàn)槌绦虻倪\(yùn)行結(jié)果正確并不代表程序完全正確，只用在使用了正確的數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)上運(yùn)行結(jié)果正確才算是正確的程序。但是在編寫(xiě)的過(guò)程中還是遇到了類似的問(wèn)題，由于對(duì)頁(yè)表的理解不夠深入，最開(kāi)始編寫(xiě)的程序雖然能夠得到正確的結(jié)果，但是沒(méi)有正確的頁(yè)表，就不算是模擬了請(qǐng)求頁(yè)式管理。后來(lái)我又修改了數(shù)據(jù)結(jié)構(gòu)，增加了頁(yè)表，這使得我的程序更加的完善了。在修改程序的時(shí)候，我發(fā)現(xiàn)雖然修改了數(shù)據(jù)結(jié)構(gòu)，但是并未對(duì)其他部分的程序有太大的影響，這得益于程序功能的模塊劃分。在編寫(xiě)程序的時(shí)候，我盡量將程序細(xì)化，劃分成小的模塊，比如我將程序劃分為初始化數(shù)據(jù)結(jié)構(gòu)、頁(yè)式管理算法執(zhí)行、總程序流程控制三個(gè)模塊，其中算法執(zhí)行模塊中，我又分了算法基本流程、計(jì)算權(quán)值、打印狀態(tài)轉(zhuǎn)移表三個(gè)模塊。每個(gè)模塊之間功能相對(duì)獨(dú)立，這樣就使得程序的結(jié)構(gòu)比較清晰，維護(hù)性比較好。所以我修改了數(shù)據(jù)結(jié)構(gòu)并未對(duì)其他部分的程序造成太大的影響。這些實(shí)踐中得到的知識(shí)將轉(zhuǎn)化為一種能力為我以后的發(fā)展做能力支撐。