課程設(shè)計(jì)計(jì)算說明書

1、摘 要在地址映射過程中，若在頁面中發(fā)現(xiàn)所要訪問的頁面不再內(nèi)存中，則產(chǎn)生缺頁中斷。當(dāng)發(fā)生缺頁中斷時(shí)操作系統(tǒng)必須在內(nèi)存選擇一個(gè)頁面將其移出內(nèi)存，以便為即將調(diào)入的頁面讓出空間，而用來選擇淘汰哪一頁的規(guī)則叫做頁面置換算法。 在進(jìn)程運(yùn)行過程中，若其所要訪問的頁面不在內(nèi)存需把它們調(diào)入內(nèi)存，但內(nèi)存已無空閑空間時(shí)，為了保證該進(jìn)程能正常運(yùn)行，系統(tǒng)必須從內(nèi)存中調(diào)出一頁程序或數(shù)據(jù)，送磁盤的對(duì)換區(qū)中。但應(yīng)將哪個(gè)頁面調(diào)出，所以需要根據(jù)一定的算法來確定。 常用的算法有先進(jìn)先出置換算法（FIFO）,最近最久未使用置換算法（LRU）和最佳置換算法（OPT），該設(shè)計(jì)是在VC+6.0環(huán)境下分別用LRU和FIF

2、O來實(shí)現(xiàn)頁面置換算法的模擬程序，并測(cè)試。關(guān)鍵字：頁面；中斷；置換算法目 錄1.概述11.1需求分析11.2原理分析21.3設(shè)計(jì)相關(guān)知識(shí)32.總體設(shè)計(jì)43.詳細(xì)設(shè)計(jì)63.1地址轉(zhuǎn)換63.2先進(jìn)先出算法83.3最近最久未使用算法104.系統(tǒng)調(diào)試125.總結(jié)17參考文獻(xiàn)18致 謝19附錄201.概述分頁式虛擬存儲(chǔ)系統(tǒng)將作業(yè)信息的副本存放在磁盤中，不把作業(yè)的程序和數(shù)據(jù)全部裝入主存，僅裝入立即使用的頁面，在執(zhí)行過程中訪問到不在主存的頁面時(shí)，產(chǎn)生缺頁中斷，再把它們動(dòng)態(tài)地裝入。 虛擬存儲(chǔ)的基本思想是基于程序的局部性原理，僅把目前需要的部分程序加載到內(nèi)存，其余暫時(shí)不用的程序及數(shù)據(jù)還保留在輔存中。在進(jìn)

3、程運(yùn)行過程中，如果所要執(zhí)行的程序不在內(nèi)存，系統(tǒng)要將要執(zhí)行的程序段自動(dòng)調(diào)入內(nèi)存。此時(shí)如果內(nèi)存已滿，則要通過置換操作將暫時(shí)不用的程序段先調(diào)出到輔存，然后將所需的程序段調(diào)入內(nèi)存，繼續(xù)執(zhí)行該進(jìn)程。 虛擬存儲(chǔ)器的引入，實(shí)際上是利用了存儲(chǔ)管理中邏輯地址空間和物理地址空間的關(guān)系，將計(jì)算機(jī)的內(nèi)存和輔存結(jié)合起來，使得用戶感覺具有大容量的內(nèi)存，虛擬內(nèi)存在虛擬內(nèi)存在將邏輯地址轉(zhuǎn)換成物理地址時(shí)，必須通過一個(gè)內(nèi)存管理單元MMU（Memory Management Unit）來完成。  存儲(chǔ)管理一直是操作系統(tǒng)中的重要組成部分，因?yàn)轳T·諾依曼體系結(jié)構(gòu)就是建立在存儲(chǔ)

4、程序概念上的，訪問存儲(chǔ)器的操作占CPU時(shí)間的70%左右。計(jì)算機(jī)系統(tǒng)中的存儲(chǔ)器一般分為主存儲(chǔ)器（簡稱主存、內(nèi)存）和輔助存儲(chǔ)器（簡稱輔存）。由于CPU只能直接與內(nèi)存進(jìn)行通信，因此計(jì)算機(jī)系統(tǒng)的程序以及與該程序相關(guān)的數(shù)據(jù)，只有被裝入到內(nèi)存中才能有效地執(zhí)行。計(jì)算機(jī)系統(tǒng)能否高效地管理內(nèi)存空間，不僅直接反映存儲(chǔ)器的利用率，還會(huì)影響整個(gè)操作系統(tǒng)的性能。1.1需求分析由于純頁式存儲(chǔ)管理提高了內(nèi)存的利用效率，但并不為用戶提供虛存，并且會(huì)產(chǎn)生磁盤碎片問題。用戶程序?qū)⑹艿轿锢韮?nèi)存大小的限制。而虛存的存儲(chǔ)管理技術(shù)請(qǐng)求分頁存儲(chǔ)管理技術(shù)和請(qǐng)求分段技術(shù)，則很好的解決了這個(gè)問題。該設(shè)計(jì)虛擬實(shí)現(xiàn)請(qǐng)求分頁管理。 請(qǐng)求分頁

5、系統(tǒng)是在分頁系統(tǒng)的基礎(chǔ)上，增加了請(qǐng)求調(diào)頁功能和頁面置換功能所形成的頁式虛擬存儲(chǔ)系統(tǒng)。它允許只裝入部分頁面的程序和數(shù)據(jù)，便啟動(dòng)運(yùn)行。以后，再通過調(diào)頁功能和頁面置換功能，陸續(xù)把即將要運(yùn)行的頁面調(diào)入內(nèi)存，同時(shí)把暫時(shí)不運(yùn)行的頁面換出到外存上，置換時(shí)以頁面為單位。實(shí)現(xiàn)將程序正在運(yùn)行時(shí)所需的但尚未在內(nèi)存的頁面調(diào)入內(nèi)存，再將內(nèi)存中暫時(shí)不用的頁面從內(nèi)存置換到外存磁盤上。為了實(shí)現(xiàn)請(qǐng)求分頁技術(shù)，頁表應(yīng)增加相應(yīng)的內(nèi)容，反映該頁是否在內(nèi)存，在外存的位置，和在內(nèi)存的時(shí)間的長短。各字段說明如下：  （1）狀態(tài)位：指示該頁是否已調(diào)入內(nèi)存。  （2）訪問字段：記錄本頁在被訪問的次數(shù)，或記錄最近已有多長時(shí)間

6、未被訪問。 修 改位：表示該頁面在調(diào)入內(nèi)存后是否被修改過。若未被修改，在替換該頁時(shí)就不需要再將該頁寫回到外存上，以減少系統(tǒng)的開銷和啟動(dòng)磁盤的次數(shù)；若已被修改，則必須將該頁重寫到外存上，以保證外存中所保留的始終是最新副本。  （3）外存地址：指出該頁在外存上的地址，通常是物理塊號(hào)。1.2原理分析分頁虛擬系統(tǒng)存儲(chǔ)管理方式是在分頁系統(tǒng)的基礎(chǔ)上，增加了請(qǐng)求調(diào)頁功能和頁面置換功能所形成的虛擬存儲(chǔ)器系統(tǒng)。在進(jìn)程裝入內(nèi)存時(shí)，并不是裝入全部頁面，而是裝入若干頁（一個(gè)或零個(gè)頁面）之后根據(jù)進(jìn)程運(yùn)行的需要，動(dòng)態(tài)裝入其他頁面。當(dāng)內(nèi)存空間已滿，而又需要裝入新的內(nèi)存時(shí)，則根據(jù)某種算法淘汰某個(gè)頁面，以便

7、騰出空間，裝入新的頁面。在分頁虛擬存儲(chǔ)管理時(shí)使用的頁表，是在原來頁表的基礎(chǔ)上發(fā)展起來的，包括以下內(nèi)容：頁號(hào)，物理塊號(hào)，狀態(tài)位，外存地址。其中狀態(tài)位表示該頁是否已經(jīng)調(diào)入內(nèi)存：外存地址用于指出該頁在外存上的地址，通常是物理塊號(hào)，供調(diào)入該頁時(shí)使用。在分頁虛擬存儲(chǔ)管理系統(tǒng)中，每當(dāng)要訪問的頁面不在內(nèi)存時(shí)，便產(chǎn)生一缺頁中斷，請(qǐng)求操作系統(tǒng)把所缺頁面調(diào)入內(nèi)存。如果內(nèi)存空間已被裝滿而又要裝入新頁時(shí)，必須按某種算法將內(nèi)存中的一些頁淘汰出去，以便調(diào)入新頁，這個(gè)工作稱為“頁面置換”。選擇被淘汰頁的方法稱為頁面置換算法。頁面置換算法的好壞，直接影響到系統(tǒng)的性能。一個(gè)好的頁面置換算法，應(yīng)具有較低的頁面更換頻率。先進(jìn)先出算

8、法：這是最早出現(xiàn)的置換算法，該算法每次淘汰最先進(jìn)入內(nèi)存的頁。這種置換算法的優(yōu)點(diǎn)是：簡單，易于實(shí)現(xiàn)。缺點(diǎn)是：效率不高，因?yàn)樵趦?nèi)存中駐留時(shí)間最長的頁不一定是最長時(shí)間后才使用的頁。并且這種置換算法可能產(chǎn)生“抖動(dòng)”現(xiàn)象。最近最久未使用算法：該算法淘汰那些在一段時(shí)間最少使用的頁。LRU算法是較好的一個(gè)算法，但是開銷太大，要求系統(tǒng)有較多的支持硬件，因而在實(shí)際應(yīng)用中，大多只采用LRU的近似算法。1.3設(shè)計(jì)相關(guān)知識(shí)1虛擬存儲(chǔ)器的引入：局部性原理：程序在執(zhí)行時(shí)在一較短時(shí)間內(nèi)僅限于某個(gè)部分；相應(yīng)的，它所訪問的存儲(chǔ)空間也局限于某個(gè)區(qū)域，它主要表現(xiàn)在以下兩個(gè)方面：時(shí)間局限性和空間局限性。2虛擬存儲(chǔ)器的定義： 虛擬存儲(chǔ)

9、器是只具有請(qǐng)求調(diào)入功能和置換功能，能從邏輯上對(duì)內(nèi)存容量進(jìn)行擴(kuò)充的一種存儲(chǔ)器系統(tǒng)。3虛擬存儲(chǔ)器的實(shí)現(xiàn)方式：分頁請(qǐng)求系統(tǒng)，它是在分頁系統(tǒng)的基礎(chǔ)上，增加了請(qǐng)求調(diào)頁功能、頁面置換功能所形成的頁面形式虛擬存儲(chǔ)系統(tǒng)。請(qǐng)求分段系統(tǒng)，它是在分段系統(tǒng)的基礎(chǔ)上，增加了請(qǐng)求調(diào)段及分段置換功能后，所形成的段式虛擬存儲(chǔ)系統(tǒng)。4. 頁面：是將一個(gè)進(jìn)程的邏輯地址空間分成若干個(gè)大小相等的區(qū)，稱為頁面或頁，并為各頁加以編號(hào)，從0開始。 頁框（頁幀）：把主存空間分成與頁面相同大小的若干個(gè)存儲(chǔ)區(qū)，稱為物理塊或頁框， 也同樣從0開始依次編號(hào)。頁表：將頁號(hào)和頁內(nèi)地址轉(zhuǎn)換成內(nèi)存地址，必須要有一個(gè)數(shù)據(jù)結(jié)構(gòu)，用來登記頁號(hào)和塊的對(duì)應(yīng)關(guān)系和有關(guān)

10、信息，這樣的數(shù)據(jù)結(jié)構(gòu)稱為頁表。5頁面置換算法：常用的頁面置換算法有OPT、FIFO、LRU、Clock、LFU、PBA等。2.總體設(shè)計(jì)分頁存儲(chǔ)管理方式提高了內(nèi)存的利用率，分段存儲(chǔ)管理方式方便了用戶的使用。結(jié)合兩者的優(yōu)點(diǎn)，將分頁存儲(chǔ)管理和分段存儲(chǔ)管理方式組合在一起，形成了段頁式存儲(chǔ)管理方式。在段頁式存儲(chǔ)管理方式中內(nèi)存分為大小相同的塊，每個(gè)作業(yè)地址空間按照邏輯關(guān)系分成若干段，并為每個(gè)段賦予一個(gè)段名，每段可以獨(dú)立從0編址，每段按內(nèi)存塊大小分成頁，每段分配與其頁數(shù)相同的內(nèi)存塊，內(nèi)存塊可以連續(xù)也可以不連續(xù)。系統(tǒng)為每段建立頁表記錄每頁對(duì)應(yīng)的塊，同時(shí)還為該程序建立段表記錄每段對(duì)應(yīng)的頁表。由段頁式存儲(chǔ)管理方式

11、的基本原理可以知道，為了訪問段頁式的地址空間，邏輯地址由三部分組成：段號(hào)S，段內(nèi)頁號(hào)P和頁內(nèi)地址d。（1）硬件地址變換在段頁式存儲(chǔ)管理系統(tǒng)中，為了實(shí)現(xiàn)地址變換，配置一段表寄存器，在該寄存器中存放段表的始址和段長。地址變換時(shí)，首先利用段號(hào)和段長進(jìn)行比較，如果段號(hào)小于段長，則沒有越界，于是利用段表寄存器中的段表始址和段號(hào)求出該段的段表中的位置，從中得到該段的頁表始址，并利用邏輯地址中的段內(nèi)頁號(hào)得到該頁對(duì)應(yīng)的頁表的位置，從中讀出該頁所對(duì)應(yīng)的物理塊，把物理塊號(hào)和頁內(nèi)地址送物理地址寄存器，構(gòu)成物理地址。作業(yè)業(yè)執(zhí)行時(shí),指令中的邏輯地址指出參加運(yùn)算的操作數(shù)(或指令)地址中的頁號(hào)和頁內(nèi)偏移量。硬件地址轉(zhuǎn)換機(jī)構(gòu)

12、按頁號(hào)查頁表。若該頁的標(biāo)志為1 ,則表示該頁已在主存,從而找到該頁對(duì)應(yīng)的主存塊號(hào)。 根據(jù)關(guān)系式: 絕對(duì)地址=塊號(hào)*塊的長度+頁內(nèi)偏移量 計(jì)算出欲訪問的主存地址。由于頁號(hào)為2的整次冪,所以只要將塊號(hào)與頁內(nèi)偏移量相拼接,放入主存地址寄存器即可。按照該地址取指令或取操作數(shù),完成指定的操作。設(shè)計(jì)一個(gè)”地址變換”程序,模擬硬件地址變化過程。當(dāng)訪問的頁在主存時(shí),則形成絕對(duì)地址后,不去模擬指令的執(zhí)行,而是輸出被轉(zhuǎn)換的地址。當(dāng)訪問的頁不在主存時(shí),輸出”該頁不在主存,產(chǎn)生缺頁中斷”,以表示產(chǎn)生一次缺頁中斷。（2）頁面置換算法a先進(jìn)先出置換算法（FIFO）：是最簡單的頁面置

13、換算法。這種算法的基本思想是：當(dāng)需要淘汰一個(gè)頁面時(shí)，總是選擇駐留主存時(shí)間最長的頁面進(jìn)行淘汰，即先進(jìn)入主存的頁面先淘汰。其理由是：最早調(diào)入主存的頁面不再被使用的可能性最大。b最近最久未使用（LRU）算法：這種算法的基本思想是：利用局部性原理，根據(jù)一個(gè)作業(yè)在執(zhí)行過程中過去的頁面訪問歷史來推測(cè)未來的行為。它認(rèn)為過去一段時(shí)間里不曾被訪問過的頁面，在最近的將來可能也不會(huì)再被訪問。所以，這種算法的實(shí)質(zhì)是：當(dāng)需要淘汰一個(gè)頁面時(shí)，總是選擇在最近一段時(shí)間內(nèi)最久不用的頁面予以淘汰。開 始進(jìn)入硬件地址變換算法進(jìn)入頁面置換算法輸入指令輸入指令的邏輯地址退出產(chǎn)生隨機(jī)序列LRU算法FIFO算法進(jìn)程序列號(hào)總體設(shè)計(jì)模塊圖如下

14、圖2.1圖2.1總體設(shè)計(jì)模塊圖3.詳細(xì)設(shè)計(jì)3.1地址轉(zhuǎn)換（1）分頁式虛擬存儲(chǔ)系統(tǒng)是把作業(yè)信息的副本存放在磁盤上，當(dāng)作業(yè)被選中時(shí)，可把作業(yè)的開始幾頁先裝入主存且啟動(dòng)執(zhí)行。為此，在為作業(yè)建立頁表時(shí)，應(yīng)說明哪些頁已在主存，哪些頁尚未裝入主存，其中，標(biāo)志-用來表示對(duì)應(yīng)頁是否已經(jīng)裝入主存，標(biāo)志位=1，則表示該頁已經(jīng)在主存，標(biāo)志位=0，則表示該頁尚未裝入主存。主存塊號(hào)-用來表示已經(jīng)裝入主存的頁所占的塊號(hào)，在磁盤上的位置-用來指出作業(yè)副本的每一頁被存放在磁盤上的位置。（2）作業(yè)執(zhí)行時(shí)，指令中的邏輯地址指出了參加運(yùn)算的操作存放的頁號(hào)和單元號(hào)，硬件的地址轉(zhuǎn)換機(jī)構(gòu)按頁號(hào)查頁表，若該頁對(duì)應(yīng)標(biāo)志為“1”，則表示該頁已

15、在主存，這時(shí)根據(jù)關(guān)系式： 絕對(duì)地址=塊號(hào)×塊長+單元號(hào)。計(jì)算出欲訪問的主存單元地址。如果塊長為2的冪次，則可把塊號(hào)作為高地址部分，把單元號(hào)作為低地址部分，兩者拼接而成絕對(duì)地址。若訪問的頁對(duì)應(yīng)標(biāo)志為“0”，則表示該頁不在主存，這時(shí)硬件發(fā)“缺頁中斷”信號(hào)，由操作系統(tǒng)按該頁在磁盤上的位置，把該頁信息從磁盤讀出裝入主存后再重新執(zhí)行這條指令。（3）設(shè)計(jì)一個(gè)“地址轉(zhuǎn)換”程序來模擬硬件的地址轉(zhuǎn)換工作。當(dāng)訪問的頁在主存時(shí)，則形成絕對(duì)地址，但不去模擬指令的執(zhí)行，而用輸出轉(zhuǎn)換后的地址來代替一條指令的執(zhí)行。當(dāng)訪問的頁不在主存時(shí)，則輸出“產(chǎn)生缺頁”，表示產(chǎn)生了一次缺頁中斷。（4）地址變換過程：當(dāng)進(jìn)程要訪問某

16、個(gè)邏輯地址中的數(shù)據(jù)時(shí)，分頁地址變換機(jī)構(gòu)會(huì)自動(dòng)將邏輯地址分為頁號(hào)和頁內(nèi)地址兩部分，再以頁號(hào)為索引去檢索頁表，查找操作由硬件執(zhí)行。在執(zhí)行檢索之前，先將頁號(hào)與頁表寄存器中的頁表長度進(jìn)行比較，如果頁號(hào)大于或等于頁表長度，則表示本次所訪問的地址已超越進(jìn)程的地址空間。于是，這一錯(cuò)誤將被系統(tǒng)發(fā)現(xiàn)并產(chǎn)生一地址越界中斷。若沒有出現(xiàn)越界錯(cuò)誤，則將頁表始址與頁號(hào)和頁表項(xiàng)長度的乘積相加，便得到該表項(xiàng)在頁表中的位置，于是可從中得到該頁的物理塊號(hào)，將之裝入物理地址寄存器中。與此同時(shí)，再將邏輯地址寄存器中的頁內(nèi)地址直接送入物理地址寄存器的塊內(nèi)地址字段中，這樣便完成了從邏輯地址到物理地址的轉(zhuǎn)換。開始取一條指令取指令中訪問的頁

17、號(hào)查頁表該頁標(biāo)志=1？形成絕對(duì)地址輸出絕對(duì)地址輸出“該頁不在主存”發(fā)生缺頁中斷有后續(xù)指令？結(jié)束取下一條指令YYNN圖3.1地址變換圖3.2先進(jìn)先出算法該算法總是淘汰最先進(jìn)入內(nèi)存的頁面，即選擇在內(nèi)存中駐留時(shí)間最久的頁面予以淘汰。該算法實(shí)現(xiàn)簡單，只需把一個(gè)進(jìn)程已調(diào)入內(nèi)存的頁面，按照先后次序鏈接成一個(gè)隊(duì)列，并設(shè)置一個(gè)指針，稱為替換指針，使它總指向最老的頁面。但該算法與進(jìn)程實(shí)際運(yùn)行的規(guī)律不相適應(yīng)，因?yàn)樵谶M(jìn)程中，有些頁面經(jīng)常被訪問，比如，含有全局變量、常用函數(shù)、例程等的頁面，F(xiàn)IFO算法并不能保證這些頁面不被淘汰。（1）在分頁式虛擬存儲(chǔ)系統(tǒng)中，當(dāng)硬件發(fā)出“缺頁中斷”后，引出操作系統(tǒng)來處理這個(gè)中斷事件。如

18、果主存中已經(jīng)沒有空閑塊，則可用FIFO頁面調(diào)度算法把該作業(yè)中最先進(jìn)入主存的一頁調(diào)出，存放到磁盤上，然后再把當(dāng)前要訪問的頁裝入該塊。調(diào)出和裝入后都要修改頁表中對(duì)應(yīng)頁的標(biāo)志。（2）FIFO頁面調(diào)度算法總是淘汰該作業(yè)中最先進(jìn)入主存的那一頁，因此可以用一個(gè)數(shù)組來表示該作業(yè)已在主存的頁面。假定作業(yè)被選中時(shí)，把開始的m個(gè)頁面裝入主存，則數(shù)組的元素可定為m個(gè)。例如： P0，P1，.，Pm-1其中每一個(gè)Pi（i=0，1，.，m-1）表示一個(gè)在主存中的頁面號(hào)。它們的初值為：P0:=0，P1:=1，.，Pm-1:=m-1用一指針k指示當(dāng)要裝入新頁時(shí)，應(yīng)淘汰的頁在數(shù)組中的位置，k的初值為“0”。當(dāng)產(chǎn)生缺頁中斷后，操

19、作系統(tǒng)選擇Pk所指出的頁面調(diào)出，然后執(zhí)行：Pk:=要裝入頁的頁號(hào) k:=(k+1) mod m再由裝入程序把要訪問的一頁信息裝入到主存中。重新啟動(dòng)剛才那條指令執(zhí)行。（3）FIFO 頁面調(diào)度算法總是淘汰該作業(yè)中最先進(jìn)入主存的那一頁，因此可以用一個(gè)數(shù)組來表示該作業(yè)已在主存的頁面。假定作業(yè)被選中時(shí)，把開始的m 個(gè)頁面裝入主存，則數(shù)組的元素可定為m 個(gè)。（4）優(yōu)點(diǎn)：對(duì)每個(gè)進(jìn)程來說都是公平的。對(duì)于長作業(yè)來說比較有利，但對(duì)于短作業(yè)來說需要等待很長的時(shí)間。 缺點(diǎn)：FIFO算法從表面上看對(duì)所有作業(yè)都是公平的，但實(shí)際上當(dāng)一個(gè)長作業(yè)排在就緒隊(duì)列前面時(shí)，就會(huì)使排在其后的許多短作業(yè)等待很長的時(shí)間。所以，這種

20、算法不利于短作業(yè)，致使短作業(yè)的等待時(shí)間可能要遠(yuǎn)遠(yuǎn)超出它運(yùn)行的時(shí)間入口初始化數(shù)據(jù)i指向下一個(gè)頁面頁面是否存在物理塊是否有空閑先進(jìn)先出的頁面作為淘汰頁i<頁面長度計(jì)算缺頁率，并輸出數(shù)據(jù)結(jié)束將頁面放空到空閑的物理塊處YY圖3.2先來先服務(wù)算法圖3.3最近最久未使用算法（1）算法的基本思想：當(dāng)需要淘汰某一頁時(shí)，選擇離當(dāng)前時(shí)間最近的一段時(shí)間內(nèi)最久沒有使用過的頁先淘汰。該算法的主要出發(fā)點(diǎn)是，如果某頁被訪問了，則它可能馬上還被訪問?；蛘叻催^來說，如果某頁很長時(shí)間未被訪問，則它在最近一段時(shí)間不會(huì)被訪問。（2）在分頁式虛擬存儲(chǔ)系統(tǒng)中，當(dāng)硬件發(fā)出“缺頁中斷”后，引出操作系統(tǒng)來處理這個(gè)中斷事件。如果主存中已經(jīng)

21、沒有空閑塊，則可用LRU頁面調(diào)度算法把該作業(yè)中最先進(jìn)入主存的一頁調(diào)出，存放到磁盤上，然后再把當(dāng)前要訪問的頁裝入該塊。調(diào)出和裝入后都要修改頁表中對(duì)應(yīng)頁的標(biāo)志。（3）LRU頁面調(diào)度算法總是淘汰該作業(yè)中距現(xiàn)在最久沒有訪問過的那一頁，因此可以用一個(gè)數(shù)組來表示該作業(yè)已在主存的頁面。數(shù)組中的第一個(gè)元素總是指出當(dāng)前剛訪問的頁號(hào)，因此最久沒被訪問的頁總是由最后一個(gè)元素指出。入口初始化數(shù)據(jù)i指向下一個(gè)頁面頁面是否存在物理塊是否有空閑最近最久未使用的頁面作為淘汰頁i<頁面長度計(jì)算缺頁率，并輸出數(shù)據(jù)結(jié)束將頁面放空到空閑的物理塊處YY圖3.3最近最久未使用算法圖4.系統(tǒng)調(diào)試調(diào)試分析：調(diào)試是整個(gè)程序編寫過程中十分

22、重要也是很困難的一部分，在這個(gè)過程中用了不少的時(shí)間進(jìn)行程序的調(diào)試，在調(diào)試過程中遇到的相關(guān)問題如下：一、語法錯(cuò)誤1、語句的最后忘記了加上“；”，使程序發(fā)生錯(cuò)誤。2、把“<<”與“>>”寫反，以及字符與字符串的操作問題，這些是比較簡單的錯(cuò)誤，很容易分辨出來，并改正之。3、函數(shù)的返回值問題，也是比較容易找出并解決的問題。二、邏輯錯(cuò)誤1、最大的一個(gè)問題就是兩個(gè)算法的正確實(shí)現(xiàn)，在程序的編寫時(shí)，兩個(gè)程序是分開進(jìn)行編寫的，分別執(zhí)行起來沒有什么問題，但是把兩個(gè)程序融合在一起后，卻出現(xiàn)了問題，即在執(zhí)行完成一個(gè)算法后再執(zhí)行另外一個(gè)算法時(shí)，開始的數(shù)據(jù)是緊接著上次算法結(jié)果的數(shù)據(jù)進(jìn)行實(shí)驗(yàn)的。這個(gè)

23、問題困擾了我好長時(shí)間，直到現(xiàn)在還沒有很好的解決掉，程序只能分別執(zhí)行一次，如果再進(jìn)行執(zhí)行的話，就會(huì)出現(xiàn)問題。自己的編程技術(shù)不好，程序編的也很繁瑣，但是基本的要求已經(jīng)實(shí)現(xiàn)了，希望這次的實(shí)驗(yàn)是自己動(dòng)手的一個(gè)開始，自己應(yīng)該更加努力，再接再厲。2、在這次課程設(shè)計(jì)中，遇到了一些困難，例如怎么實(shí)現(xiàn)各種算法，如何進(jìn)行函數(shù)調(diào)用及對(duì)數(shù)據(jù)的限制操作等，在遇到這些困難的時(shí)候，我們會(huì)去查閱資料，仔細(xì)看書，嘗試用不同的方法解決，在各種方法中選擇一種最好的方法，有的時(shí)候會(huì)碰到不知道如何實(shí)現(xiàn)的函數(shù)，我就盡量去和同學(xué)去調(diào)試它。整個(gè)調(diào)試過程中主要是這么幾個(gè)問題，其余的是一些小問題，很容易的就調(diào)試出來了。（1）進(jìn)入界面：選項(xiàng)1為地

24、址變換算法，選項(xiàng)2為頁面置換算法圖4.1主界面（2）進(jìn)入硬件地址變換算法：選擇；進(jìn)入之后共有輸入指令和進(jìn)入置換頁面算法兩個(gè)選項(xiàng)，當(dāng)輸入1時(shí)就可以進(jìn)行地址變換了。圖4.2地址變換界面（3）輸入選擇1后，系統(tǒng)自動(dòng)生成頁號(hào)，標(biāo)記位，外存地址和主存號(hào)，再輸入邏輯地址，系統(tǒng)即可算出物理地址，并給出詳細(xì)信息：頁面號(hào)，主存號(hào)和偏移量圖4.3地址變換圖（4）當(dāng)輸入的邏輯地址超出地址范圍時(shí)就產(chǎn)生了缺頁中斷，顯示該頁不在主存內(nèi)圖4.4缺頁中斷圖（5）退回到主界面選擇2進(jìn)入頁面置換算法，有3個(gè)選擇：產(chǎn)生隨機(jī)序列號(hào)，先進(jìn)先出算法和最近最久未使用算法圖4.5進(jìn)入頁面置換算法界面（6）選擇1產(chǎn)生隨機(jī)進(jìn)程序列號(hào)：即可產(chǎn)生一

25、組無規(guī)則的隨意的進(jìn)程序列號(hào)圖4.6產(chǎn)生進(jìn)程序列號(hào)圖（7）產(chǎn)生隨機(jī)序列號(hào)后，選擇2進(jìn)入最近最久未使用算法，將產(chǎn)生內(nèi)存狀態(tài)并自動(dòng)顯示調(diào)入隊(duì)列，缺頁次數(shù)和缺頁率圖4.8最近最久未使用算法圖（8）選擇3先進(jìn)先出算法，就可產(chǎn)生算法表和缺頁次數(shù)圖4.8先進(jìn)先出算法圖5.總結(jié)對(duì)于C+初學(xué)者來說，這一抽象的編程語言的確有些晦澀難懂，尤其是其中的一些細(xì)節(jié)部分，在課設(shè)過程時(shí)稍有不慎就會(huì)出錯(cuò)。好在C+實(shí)踐編程給我們提供了一個(gè)很好的運(yùn)用所學(xué)知識(shí)來提高自己編程能力的機(jī)會(huì)，編程過程中需要的是細(xì)心和耐心，另外，完備和熟絡(luò)的基礎(chǔ)知識(shí)也很重要。一個(gè)較為復(fù)雜的程序通常需要串聯(lián)多種語句、定義多個(gè)變量，這樣就很容易出現(xiàn)問題，包括一些

26、語法錯(cuò)誤和運(yùn)行錯(cuò)誤，所以調(diào)試很重要，每當(dāng)出現(xiàn)的結(jié)果和預(yù)想的不一樣或是效果不是很好時(shí)就需要調(diào)試了。調(diào)試過程是一個(gè)完善程序的過程，也是一個(gè)提升自己編程能力的過程，在不斷的檢查與修改中，自己的編程能力才會(huì)不斷提升，只有這樣，最終的程序才會(huì)趨于簡單、正確，避免冗長、復(fù)雜。對(duì)于這次編程實(shí)踐，我總結(jié)了以下心得：1、不懂的部分多與小組成員交流，上網(wǎng)查資料；2、把復(fù)雜程序按照功能進(jìn)行分解，分解成一個(gè)個(gè)模塊，一個(gè)模塊一個(gè)功能，避免大程序；3、多寫注釋，當(dāng)遇到錯(cuò)誤時(shí)可以方便的找出問題所在；4、要記得判斷可能出現(xiàn)運(yùn)行異常的地方。經(jīng)過本次程序設(shè)計(jì)，暴露出本團(tuán)隊(duì)的很多問題，首先是知識(shí)掌握水平不一，作為組長因自身水平不高

27、，果斷決定所有變量及函數(shù)名采用拼音縮寫。然后是隊(duì)員編出的程序無法完美兼容，顯示出我們溝通的缺乏。同時(shí)也表現(xiàn)出我們知識(shí)的欠缺，對(duì)于置換算法，地址變換及頁表的使用，了解的是在有限，仍需要不斷學(xué)習(xí)，書本上的東西跟本無法完成一個(gè)程序。每次報(bào)錯(cuò)我們需要根據(jù)錯(cuò)誤修改，改不了的就上網(wǎng)查找原因,還有好多好多的瑕疵。但是不得不承認(rèn)，經(jīng)過本次課題設(shè)計(jì)，也表現(xiàn)出隊(duì)員們的很多優(yōu)點(diǎn)，思維縝密，查漏補(bǔ)缺，集體的力量是偉大，通過大家的討論，總能得到一個(gè)好的解決方案。參考文獻(xiàn)1 湯子瀛，哲鳳屏.計(jì)算機(jī)操作系統(tǒng)M.西安：西安電子科技大學(xué)學(xué)出版社.1996年2王萬森.計(jì)算機(jī)操作系統(tǒng)原理M.北京：高等教育出版社.2001年3周長林

28、，左萬歷. 計(jì)算機(jī)操作系統(tǒng)教程M.北京：高等教育出版社.1994年4黃廷輝，王宇英.計(jì)算機(jī)操作系統(tǒng)實(shí)踐教程M.北京：清華大學(xué)出版社. 2007年5月5殷兆麟.計(jì)算機(jī)操作系統(tǒng)M.北京：清華大學(xué)出版社.2007年3月6張堯?qū)W，史美林，張高.計(jì)算機(jī)操作系統(tǒng)教程M.北京：清華大學(xué)出版社.1993年致 謝在編寫程序的過程中，我們得到了馬老師的精心指導(dǎo)以及孜孜不倦的教誨，在老師的指導(dǎo)下，我們的能力得到了提高，同時(shí)養(yǎng)成了科學(xué)、嚴(yán)謹(jǐn)?shù)淖黠L(fēng)和習(xí)慣，在此，我們對(duì)老師的精心栽培表示衷心的感謝！ 在課設(shè)的這幾天中感謝同學(xué)和搭檔的幫忙，我才能夠完成課設(shè)任務(wù)，同時(shí)感謝學(xué)校的大力支持。首先得感謝馬老師這幾天的指導(dǎo)，在此表示

29、衷心的感謝！其次也感謝那些在我們不懂得時(shí)候給予我們幫助的同學(xué)。起初，我們剛開始設(shè)計(jì)時(shí)，對(duì)內(nèi)容掌握度根本就不夠，通過了4天的上機(jī)實(shí)習(xí)及課后的查閱資料、詢問同學(xué)才對(duì)自己的程序有了系統(tǒng)的認(rèn)識(shí)及完成程序的設(shè)計(jì)思路，并在大家的幫助下完成了本次課程設(shè)計(jì)的全部內(nèi)容，看著自己做出來的東西心中莫名的開心，在這次過程中也歷練了自己的耐心及學(xué)習(xí)方法?？傊谶@次實(shí)習(xí)中獲益匪淺。對(duì)馬老師再次表示感謝！附錄#include<iostream>#include<process.h>#include<stdlib.h>#include <ctime>#include<co

30、nio.h> #include<stdio.h>#include<string.h>using namespace std;#define Myprintf printf("|-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-|n") /*表格控制*/ #define bsize 4 /物理塊大小#define psize 16 /進(jìn)程大小void chushihua();/初始化函數(shù)void ymzh();void yemianzhihuan();void changeaddr(struct Page p,int logadd

31、r);void dizhizhuanhuan();void menu();int wang();int yemianliu32=0;/全局變量數(shù)組，地址流int p; struct Pageint pno;/頁號(hào)int flag;/標(biāo)志位int cno;/主存號(hào)int modf;/修改位int addr;/外存地址Page; /全局變量p是一共有多少地址流typedef struct page1 int num; /*記錄頁面號(hào)*/ int time; /*記錄調(diào)入內(nèi)存時(shí)間*/ Page1; /* 頁面邏輯結(jié)構(gòu)，結(jié)構(gòu)為方便算法實(shí)現(xiàn)設(shè)計(jì)*/ Page1 bbsize; /*內(nèi)存單元數(shù)*/ int

32、 cbsizepsize; /*暫保存內(nèi)存當(dāng)前的狀態(tài)：緩沖區(qū)*/ int queue100; /*記錄調(diào)入隊(duì)列*/ int K; /*調(diào)入隊(duì)列計(jì)數(shù)變量*/ int phbbsize=0; /物理塊標(biāo)號(hào)int propsize=0; /進(jìn)程序列號(hào)int flagbsize = 0; /進(jìn)程等待次數(shù)(存放最久未被使用的進(jìn)程標(biāo)志)int i = 0, j = 0,k = 0; /i表示進(jìn)程序列號(hào),j表示物理塊號(hào)int m = -1, n = -1; /物理塊空閑和進(jìn)程是否相同判斷標(biāo)志int max = -1,maxflag = 0; /標(biāo)記替換物理塊進(jìn)程下標(biāo)int count = 0; /統(tǒng)計(jì)頁面缺

33、頁次數(shù)void chushihua()/初始化函數(shù)int t;srand(time(0);/隨機(jī)產(chǎn)生指令序列 p=12+rand()%32;cout<<"地址流序列："cout<<endl;for(int i=0;i<p;i+)t=1+rand()%9;yemianliui=t;/將隨機(jī)產(chǎn)生的指令數(shù)存入頁面流for( i=p-1;i>=0;i-)cout<<yemianliui<<" "cout<<endl;void ymzh()chushihua(); yemianzhihuan(

34、);void yemianzhihuan()int a;printf(" - n");printf(" - 歡迎使用分頁模擬實(shí)驗(yàn)系統(tǒng) - n");printf(" - n");printf(" n");printf(" 1.進(jìn)入硬件地址變換算法 n");printf(" - n");printf(" 2.進(jìn)入頁面置換算法 n");printf(" n");printf("請(qǐng)輸入您的選擇:");switch(a)cas

35、e 1:ymzh();break;case 2: wang();break;default:cout<<"輸入有誤，請(qǐng)重新輸入！"<<endl;break;void changeaddr(struct Page p,int logaddr)/地址變換int j=logaddr/64;/對(duì)應(yīng)的塊號(hào)int k=logaddr%64;/對(duì)應(yīng)的偏移量int flag=0;int addr;for(int i=0;i<8;i+)if(pi.pno=j)/找到對(duì)應(yīng)的頁號(hào)if(pi.flag=1)/頁面標(biāo)志為1addr=o*64+k;cout<

36、;<"物理地址為: "<<addr<<endl;cout<<"詳細(xì)信息: "<<"t頁面號(hào)："<<pi.pno<<"t主存號(hào):"<<o<<"t偏移量："<<k<<endl;flag=1;break;if(flag=0)cout<<"該頁不在主存,產(chǎn)生缺頁中斷"<<endl; void dizhizhuanhuan()i

37、nt a;int ins;/指令邏輯地址struct Page p8;p0.pno=0;p0.flag=1;o=5;p0.modf=1;p0.addr=011;p1.pno=1;p1.flag=1;o=8;p1.modf=1;p1.addr=012;p2.pno=2;p2.flag=1;o=9;p2.modf=0;p2.addr=013;p3.pno=3;p3.flag=1;o=10;p3.modf=0;p3.addr=015;p4.pno=4;p4.flag=0;p4.addr=017;p5.pno=5;p5.flag=0;p5.addr=025;p6

38、.pno=6;p6.flag=0;p6.addr=212;p7.pno=7;p7.flag=0;p7.addr=213;printf("ttt-ttt");printf("ttt-歡迎進(jìn)入硬件地址變換界面-ttt");printf("ttt-tttn");printf("ttt ttt"); printf("ttt 1、輸入指令 ttt");printf("ttt -ttt"); printf("ttt 2、進(jìn)入頁面置換算法 ttt");printf(&q

39、uot;ttt -ttt");printf("ttt 0、退出(Exit) ttt"); printf("ttt tttn");while(a!=0) cout<<endl<<"請(qǐng)輸入您的選擇:"cin>>a;cout<<"頁號(hào) "<<"標(biāo)記位 "<<"外存地址 "<<"主存號(hào)"<<endl;for(int i=0;i<8;i+) cout<

40、;<pi.pno<<"t"<<pi.flag<<"t"<<pi.addr<<"t"if(pi.flag)cout<<o;cout<<endl; switch(a)case 0:printf("ttt- 再見！- tttn");break;case 1:cout<<"請(qǐng)輸入指令的邏輯地址："cin>>ins;changeaddr(p,ins);break;case 2:sys

41、tem("CLS");a=wang();break;default:cout<<"輸入有誤，請(qǐng)重新輸入！"<<endl;break;void menu()int a; printf("ttt-ttt");printf("ttt-歡迎使用分頁模擬實(shí)驗(yàn)系統(tǒng)-ttt");printf("ttt-tttn");printf("ttt ttt"); printf("ttt 1、進(jìn)入硬件地址變換算法 ttt");printf("ttt

42、 -ttt"); printf("ttt 2、進(jìn)入頁面置換算法 ttt");printf("ttt -ttt");printf("ttt 0、退出(Exit) ttt"); printf("ttt tttn"); printf("請(qǐng)選擇所要執(zhí)行的操作:"); scanf("%d",&a);switch(a)case 0:printf("ttt- 再見！- tttn");break;case 1:dizhizhuanhuan();break

43、;case 2:wang();break;default:cout<<"輸入有誤，請(qǐng)重新輸入！"<<endl;break;void main() menu();/*/隨機(jī)產(chǎn)生序列號(hào)函數(shù)int* build()printf("隨機(jī)產(chǎn)生一個(gè)進(jìn)程序列號(hào)為：n");int i = 0; for(i=0; i<psize; i+) proi = 10*rand()/(RAND_MAX+1)+1; printf("%d ",proi); printf("n"); return(pro);/*/查找

44、空閑物理塊int searchpb()for(j=0; j<bsize; j+) if(phbj = 0) m = j; return m; break;return -1;/*/查找相同進(jìn)程int searchpro()for(j = 0; j < bsize; j+) if(phbj = proi) n = j; return j;return -1;/*/初始化內(nèi)存void empty()for(i=0;i<bsize;i+)phbi=0; count=0; /計(jì)數(shù)器置零/*/先進(jìn)先出頁面置換算法void FIFO() for(i = 0; i<psize; i+

45、) m=searchpb(); n=searchpro();/找flag值最大的 for(j = 0; j < bsize;j+) if(flagj>maxflag) maxflag = flagj; max = j; if(n = -1) /不存在相同進(jìn)程 if(m != -1) /存在空閑物理塊 phbm = proi; /進(jìn)程號(hào)填入該空閑物理塊 count+; flagm = 0; for(j = 0;j <= m; j+) flagj+; m = -1; else /不存在空閑物理塊 phbmax = proi; flagmax = 0; for(j = 0;j &l

46、t; bsize; j+) flagj+; max = -1; maxflag = 0; count+; else /存在相同的進(jìn)程 phbn = proi; for(j = 0;j < bsize; j+) flagj+; n = -1; for(j = 0 ;j < bsize; j+) printf("%d ",phbj); printf("n"); printf("缺頁次數(shù)為：%dn",count);printf("n");/*初始化內(nèi)存單元、緩沖區(qū)*/ void Init(Page1 *b,i

47、nt cbsizepsize) int i,j; for(i=0;i<psize;i+) bi.num=-1; bi.time=psize-i-1; for(i=0;i<bsize;i+) for(j=0;j<psize;j+) cij=-1; /*取得在內(nèi)存中停留最久的頁面,默認(rèn)狀態(tài)下為最早調(diào)入的頁面*/ int GetMax(Page1 *b) int i; int max=-1; int tag=0; for(i=0;i<bsize;i+) if(bi.time>max) max=bi.time; tag=i; return tag; /*判斷頁面是否已在內(nèi)存中*/ int Equation(int fold,Page1 *b) int i; for(i=0;i<bsize;i+) if (fold=bi.num) return i; return -1; /