分頁(yè)系統(tǒng)課程設(shè)計(jì)計(jì)算說明書.doc

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

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

3、，如果所要執(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（memorymanagementunit）來完成。存儲(chǔ)管理一直是操作系統(tǒng)中的重要組成部分，因?yàn)轳T諾依曼體系結(jié)構(gòu)就是建立在存儲(chǔ)程序概念上的，訪問存儲(chǔ)器的操作占cpu時(shí)間的70%左右。計(jì)算機(jī)系統(tǒng)中的存儲(chǔ)器一般分為

4、主存儲(chǔ)器（簡(jiǎn)稱主存、內(nèi)存）和輔助存儲(chǔ)器（簡(jiǎn)稱輔存）。由于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需求分析由于純頁(yè)式存儲(chǔ)管理提高了內(nèi)存的利用效率，但并不為用戶提供虛存，并且會(huì)產(chǎn)生磁盤碎片問題。用戶程序?qū)⑹艿轿锢韮?nèi)存大小的限制。而虛存的存儲(chǔ)管理技術(shù)請(qǐng)求分頁(yè)存儲(chǔ)管理技術(shù)和請(qǐng)求分段技術(shù)，則很好的解決了這個(gè)問題。該設(shè)計(jì)虛擬實(shí)現(xiàn)請(qǐng)求分頁(yè)管理。請(qǐng)求分頁(yè)系統(tǒng)是在分頁(yè)系統(tǒng)的基礎(chǔ)上，增加了請(qǐng)求調(diào)頁(yè)功能和頁(yè)面置換功能所形成的頁(yè)式虛擬存儲(chǔ)系統(tǒng)。它允許只裝入

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

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

7、位表示該頁(yè)是否已經(jīng)調(diào)入內(nèi)存：外存地址用于指出該頁(yè)在外存上的地址，通常是物理塊號(hào)，供調(diào)入該頁(yè)時(shí)使用。在分頁(yè)虛擬存儲(chǔ)管理系統(tǒng)中，每當(dāng)要訪問的頁(yè)面不在內(nèi)存時(shí)，便產(chǎn)生一缺頁(yè)中斷，請(qǐng)求操作系統(tǒng)把所缺頁(yè)面調(diào)入內(nèi)存。如果內(nèi)存空間已被裝滿而又要裝入新頁(yè)時(shí)，必須按某種算法將內(nèi)存中的一些頁(yè)淘汰出去，以便調(diào)入新頁(yè)，這個(gè)工作稱為“頁(yè)面置換”。選擇被淘汰頁(yè)的方法稱為頁(yè)面置換算法。頁(yè)面置換算法的好壞，直接影響到系統(tǒng)的性能。一個(gè)好的頁(yè)面置換算法，應(yīng)具有較低的頁(yè)面更換頻率。先進(jìn)先出算法：這是最早出現(xiàn)的置換算法，該算法每次淘汰最先進(jìn)入內(nèi)存的頁(yè)。這種置換算法的優(yōu)點(diǎn)是：簡(jiǎn)單，易于實(shí)現(xiàn)。缺點(diǎn)是：效率不高，因?yàn)樵趦?nèi)存中駐留時(shí)間最長(zhǎng)的頁(yè)

8、不一定是最長(zhǎng)時(shí)間后才使用的頁(yè)。并且這種置換算法可能產(chǎn)生“抖動(dòng)”現(xiàn)象。最近最久未使用算法：該算法淘汰那些在一段時(shí)間最少使用的頁(yè)。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ǔ)器是只具有請(qǐng)求調(diào)入功能和置換功能，能從邏輯上對(duì)內(nèi)存容量進(jìn)行擴(kuò)充的一種存儲(chǔ)器系統(tǒng)。3虛擬存儲(chǔ)器的實(shí)現(xiàn)方式：分頁(yè)請(qǐng)求系統(tǒng)，它是在分頁(yè)系統(tǒng)的基礎(chǔ)上，增

9、加了請(qǐng)求調(diào)頁(yè)功能、頁(yè)面置換功能所形成的頁(yè)面形式虛擬存儲(chǔ)系統(tǒng)。請(qǐng)求分段系統(tǒng)，它是在分段系統(tǒng)的基礎(chǔ)上，增加了請(qǐng)求調(diào)段及分段置換功能后，所形成的段式虛擬存儲(chǔ)系統(tǒng)。4. 頁(yè)面：是將一個(gè)進(jìn)程的邏輯地址空間分成若干個(gè)大小相等的區(qū)，稱為頁(yè)面或頁(yè)，并為各頁(yè)加以編號(hào)，從0開始。 頁(yè)框（頁(yè)幀）：把主存空間分成與頁(yè)面相同大小的若干個(gè)存儲(chǔ)區(qū)，稱為物理塊或頁(yè)框， 也同樣從0開始依次編號(hào)。頁(yè)表：將頁(yè)號(hào)和頁(yè)內(nèi)地址轉(zhuǎn)換成內(nèi)存地址，必須要有一個(gè)數(shù)據(jù)結(jié)構(gòu)，用來登記頁(yè)號(hào)和塊的對(duì)應(yīng)關(guān)系和有關(guān)信息，這樣的數(shù)據(jù)結(jié)構(gòu)稱為頁(yè)表。5頁(yè)面置換算法：常用的頁(yè)面置換算法有opt、fifo、lru、clock、lfu、pba等。2.總體設(shè)計(jì)分頁(yè)存儲(chǔ)管

10、理方式提高了內(nèi)存的利用率，分段存儲(chǔ)管理方式方便了用戶的使用。結(jié)合兩者的優(yōu)點(diǎn)，將分頁(yè)存儲(chǔ)管理和分段存儲(chǔ)管理方式組合在一起，形成了段頁(yè)式存儲(chǔ)管理方式。在段頁(yè)式存儲(chǔ)管理方式中內(nèi)存分為大小相同的塊，每個(gè)作業(yè)地址空間按照邏輯關(guān)系分成若干段，并為每個(gè)段賦予一個(gè)段名，每段可以獨(dú)立從0編址，每段按內(nèi)存塊大小分成頁(yè)，每段分配與其頁(yè)數(shù)相同的內(nèi)存塊，內(nèi)存塊可以連續(xù)也可以不連續(xù)。系統(tǒng)為每段建立頁(yè)表記錄每頁(yè)對(duì)應(yīng)的塊，同時(shí)還為該程序建立段表記錄每段對(duì)應(yīng)的頁(yè)表。由段頁(yè)式存儲(chǔ)管理方式的基本原理可以知道，為了訪問段頁(yè)式的地址空間，邏輯地址由三部分組成：段號(hào)s，段內(nèi)頁(yè)號(hào)p和頁(yè)內(nèi)地址d。（1）硬件地址變換在段頁(yè)式存儲(chǔ)管理系統(tǒng)中，為

11、了實(shí)現(xiàn)地址變換，配置一段表寄存器，在該寄存器中存放段表的始址和段長(zhǎng)。地址變換時(shí)，首先利用段號(hào)和段長(zhǎng)進(jìn)行比較，如果段號(hào)小于段長(zhǎng)，則沒有越界，于是利用段表寄存器中的段表始址和段號(hào)求出該段的段表中的位置，從中得到該段的頁(yè)表始址，并利用邏輯地址中的段內(nèi)頁(yè)號(hào)得到該頁(yè)對(duì)應(yīng)的頁(yè)表的位置，從中讀出該頁(yè)所對(duì)應(yīng)的物理塊，把物理塊號(hào)和頁(yè)內(nèi)地址送物理地址寄存器，構(gòu)成物理地址。作業(yè)業(yè)執(zhí)行時(shí),指令中的邏輯地址指出參加運(yùn)算的操作數(shù)(或指令)地址中的頁(yè)號(hào)和頁(yè)內(nèi)偏移量。硬件地址轉(zhuǎn)換機(jī)構(gòu)按頁(yè)號(hào)查頁(yè)表。若該頁(yè)的標(biāo)志為1,則表示該頁(yè)已在主存,從而找到該頁(yè)對(duì)應(yīng)的主存塊號(hào)。根據(jù)關(guān)系式:絕對(duì)地址=塊號(hào)*塊的長(zhǎng)度+頁(yè)內(nèi)偏移量計(jì)算出欲訪問的主

12、存地址。由于頁(yè)號(hào)為2的整次冪,所以只要將塊號(hào)與頁(yè)內(nèi)偏移量相拼接,放入主存地址寄存器即可。按照該地址取指令或取操作數(shù),完成指定的操作。設(shè)計(jì)一個(gè)”地址變換”程序,模擬硬件地址變化過程。當(dāng)訪問的頁(yè)在主存時(shí),則形成絕對(duì)地址后,不去模擬指令的執(zhí)行,而是輸出被轉(zhuǎn)換的地址。當(dāng)訪問的頁(yè)不在主存時(shí),輸出”該頁(yè)不在主存,產(chǎn)生缺頁(yè)中斷”,以表示產(chǎn)生一次缺頁(yè)中斷。（2）頁(yè)面置換算法a先進(jìn)先出置換算法（fifo）：是最簡(jiǎn)單的頁(yè)面置換算法。這種算法的基本思想是：當(dāng)需要淘汰一個(gè)頁(yè)面時(shí)，總是選擇駐留主存時(shí)間最長(zhǎng)的頁(yè)面進(jìn)行淘汰，即先進(jìn)入主存的頁(yè)面先淘汰。其理由是：最早調(diào)入主存的頁(yè)面不再被使用的可能性最大。b最近最久未使用（lr

13、u）算法：這種算法的基本思想是：利用局部性原理，根據(jù)一個(gè)作業(yè)在執(zhí)行過程中過去的頁(yè)面訪問歷史來推測(cè)未來的行為。它認(rèn)為過去一段時(shí)間里不曾被訪問過的頁(yè)面，在最近的將來可能也不會(huì)再被訪問。所以，這種算法的實(shí)質(zhì)是：當(dāng)需要淘汰一個(gè)頁(yè)面時(shí)，總是選擇在最近一段時(shí)間內(nèi)最久不用的頁(yè)面予以淘汰。開 始進(jìn)入硬件地址變換算法進(jìn)入頁(yè)面置換算法輸入指令輸入指令的邏輯地址退出產(chǎn)生隨機(jī)序列l(wèi)ru算法fifo算法進(jìn)程序列號(hào)總體設(shè)計(jì)模塊圖如下圖2.1圖2.1總體設(shè)計(jì)模塊圖3.詳細(xì)設(shè)計(jì)3.1地址轉(zhuǎn)換（1）分頁(yè)式虛擬存儲(chǔ)系統(tǒng)是把作業(yè)信息的副本存放在磁盤上，當(dāng)作業(yè)被選中時(shí)，可把作業(yè)的開始幾頁(yè)先裝入主存且啟動(dòng)執(zhí)行。為此，在為作業(yè)建立頁(yè)表時(shí)

14、，應(yīng)說明哪些頁(yè)已在主存，哪些頁(yè)尚未裝入主存，其中，標(biāo)志-用來表示對(duì)應(yīng)頁(yè)是否已經(jīng)裝入主存，標(biāo)志位=1，則表示該頁(yè)已經(jīng)在主存，標(biāo)志位=0，則表示該頁(yè)尚未裝入主存。主存塊號(hào)-用來表示已經(jīng)裝入主存的頁(yè)所占的塊號(hào)，在磁盤上的位置-用來指出作業(yè)副本的每一頁(yè)被存放在磁盤上的位置。（2）作業(yè)執(zhí)行時(shí)，指令中的邏輯地址指出了參加運(yùn)算的操作存放的頁(yè)號(hào)和單元號(hào)，硬件的地址轉(zhuǎn)換機(jī)構(gòu)按頁(yè)號(hào)查頁(yè)表，若該頁(yè)對(duì)應(yīng)標(biāo)志為“1”，則表示該頁(yè)已在主存，這時(shí)根據(jù)關(guān)系式： 絕對(duì)地址=塊號(hào)塊長(zhǎng)+單元號(hào)。計(jì)算出欲訪問的主存單元地址。如果塊長(zhǎng)為2的冪次，則可把塊號(hào)作為高地址部分，把單元號(hào)作為低地址部分，兩者拼接而成絕對(duì)地址。若訪問的頁(yè)對(duì)應(yīng)標(biāo)志

15、為“0”，則表示該頁(yè)不在主存，這時(shí)硬件發(fā)“缺頁(yè)中斷”信號(hào)，由操作系統(tǒng)按該頁(yè)在磁盤上的位置，把該頁(yè)信息從磁盤讀出裝入主存后再重新執(zhí)行這條指令。（3）設(shè)計(jì)一個(gè)“地址轉(zhuǎn)換”程序來模擬硬件的地址轉(zhuǎn)換工作。當(dāng)訪問的頁(yè)在主存時(shí)，則形成絕對(duì)地址，但不去模擬指令的執(zhí)行，而用輸出轉(zhuǎn)換后的地址來代替一條指令的執(zhí)行。當(dāng)訪問的頁(yè)不在主存時(shí)，則輸出“產(chǎn)生缺頁(yè)”，表示產(chǎn)生了一次缺頁(yè)中斷。（4）地址變換過程：當(dāng)進(jìn)程要訪問某個(gè)邏輯地址中的數(shù)據(jù)時(shí)，分頁(yè)地址變換機(jī)構(gòu)會(huì)自動(dòng)將邏輯地址分為頁(yè)號(hào)和頁(yè)內(nèi)地址兩部分，再以頁(yè)號(hào)為索引去檢索頁(yè)表，查找操作由硬件執(zhí)行。在執(zhí)行檢索之前，先將頁(yè)號(hào)與頁(yè)表寄存器中的頁(yè)表長(zhǎng)度進(jìn)行比較，如果頁(yè)號(hào)大于或等于頁(yè)

16、表長(zhǎng)度，則表示本次所訪問的地址已超越進(jìn)程的地址空間。于是，這一錯(cuò)誤將被系統(tǒng)發(fā)現(xiàn)并產(chǎn)生一地址越界中斷。若沒有出現(xiàn)越界錯(cuò)誤，則將頁(yè)表始址與頁(yè)號(hào)和頁(yè)表項(xiàng)長(zhǎng)度的乘積相加，便得到該表項(xiàng)在頁(yè)表中的位置，于是可從中得到該頁(yè)的物理塊號(hào)，將之裝入物理地址寄存器中。與此同時(shí)，再將邏輯地址寄存器中的頁(yè)內(nèi)地址直接送入物理地址寄存器的塊內(nèi)地址字段中，這樣便完成了從邏輯地址到物理地址的轉(zhuǎn)換。開始取一條指令取指令中訪問的頁(yè)號(hào)查頁(yè)表該頁(yè)標(biāo)志=1？形成絕對(duì)地址輸出絕對(duì)地址輸出“該頁(yè)不在主存”發(fā)生缺頁(yè)中斷有后續(xù)指令？結(jié)束取下一條指令yynn圖3.1地址變換圖3.2先進(jìn)先出算法該算法總是淘汰最先進(jìn)入內(nèi)存的頁(yè)面，即選擇在內(nèi)存中駐留時(shí)

17、間最久的頁(yè)面予以淘汰。該算法實(shí)現(xiàn)簡(jiǎn)單，只需把一個(gè)進(jìn)程已調(diào)入內(nèi)存的頁(yè)面，按照先后次序鏈接成一個(gè)隊(duì)列，并設(shè)置一個(gè)指針，稱為替換指針，使它總指向最老的頁(yè)面。但該算法與進(jìn)程實(shí)際運(yùn)行的規(guī)律不相適應(yīng)，因?yàn)樵谶M(jìn)程中，有些頁(yè)面經(jīng)常被訪問，比如，含有全局變量、常用函數(shù)、例程等的頁(yè)面，fifo算法并不能保證這些頁(yè)面不被淘汰。（1）在分頁(yè)式虛擬存儲(chǔ)系統(tǒng)中，當(dāng)硬件發(fā)出“缺頁(yè)中斷”后，引出操作系統(tǒng)來處理這個(gè)中斷事件。如果主存中已經(jīng)沒有空閑塊，則可用fifo頁(yè)面調(diào)度算法把該作業(yè)中最先進(jìn)入主存的一頁(yè)調(diào)出，存放到磁盤上，然后再把當(dāng)前要訪問的頁(yè)裝入該塊。調(diào)出和裝入后都要修改頁(yè)表中對(duì)應(yīng)頁(yè)的標(biāo)志。（2）fifo頁(yè)面調(diào)度算法總是淘汰

18、該作業(yè)中最先進(jìn)入主存的那一頁(yè)，因此可以用一個(gè)數(shù)組來表示該作業(yè)已在主存的頁(yè)面。假定作業(yè)被選中時(shí)，把開始的m個(gè)頁(yè)面裝入主存，則數(shù)組的元素可定為m個(gè)。例如： p0，p1，.，pm-1其中每一個(gè)pi（i=0，1，.，m-1）表示一個(gè)在主存中的頁(yè)面號(hào)。它們的初值為：p0:=0，p1:=1，.，pm-1:=m-1用一指針k指示當(dāng)要裝入新頁(yè)時(shí)，應(yīng)淘汰的頁(yè)在數(shù)組中的位置，k的初值為“0”。當(dāng)產(chǎn)生缺頁(yè)中斷后，操作系統(tǒng)選擇pk所指出的頁(yè)面調(diào)出，然后執(zhí)行：pk:=要裝入頁(yè)的頁(yè)號(hào) k:=(k+1) mod m再由裝入程序把要訪問的一頁(yè)信息裝入到主存中。重新啟動(dòng)剛才那條指令執(zhí)行。（3）fifo 頁(yè)面調(diào)度算法總是淘汰該作

19、業(yè)中最先進(jìn)入主存的那一頁(yè)，因此可以用一個(gè)數(shù)組來表示該作業(yè)已在主存的頁(yè)面。假定作業(yè)被選中時(shí)，把開始的m 個(gè)頁(yè)面裝入主存，則數(shù)組的元素可定為m 個(gè)。（4）優(yōu)點(diǎn)：對(duì)每個(gè)進(jìn)程來說都是公平的。對(duì)于長(zhǎng)作業(yè)來說比較有利，但對(duì)于短作業(yè)來說需要等待很長(zhǎng)的時(shí)間。缺點(diǎn)：fifo算法從表面上看對(duì)所有作業(yè)都是公平的，但實(shí)際上當(dāng)一個(gè)長(zhǎng)作業(yè)排在就緒隊(duì)列前面時(shí)，就會(huì)使排在其后的許多短作業(yè)等待很長(zhǎng)的時(shí)間。所以，這種算法不利于短作業(yè)，致使短作業(yè)的等待時(shí)間可能要遠(yuǎn)遠(yuǎn)超出它運(yùn)行的時(shí)間入口初始化數(shù)據(jù)i指向下一個(gè)頁(yè)面頁(yè)面是否存在物理塊是否有空閑先進(jìn)先出的頁(yè)面作為淘汰頁(yè)i頁(yè)面長(zhǎng)度計(jì)算缺頁(yè)率，并輸出數(shù)據(jù)結(jié)束將頁(yè)面放空到空閑的物理塊處yy圖3

20、.2先來先服務(wù)算法圖3.3最近最久未使用算法（1）算法的基本思想：當(dāng)需要淘汰某一頁(yè)時(shí)，選擇離當(dāng)前時(shí)間最近的一段時(shí)間內(nèi)最久沒有使用過的頁(yè)先淘汰。該算法的主要出發(fā)點(diǎn)是，如果某頁(yè)被訪問了，則它可能馬上還被訪問?；蛘叻催^來說，如果某頁(yè)很長(zhǎng)時(shí)間未被訪問，則它在最近一段時(shí)間不會(huì)被訪問。（2）在分頁(yè)式虛擬存儲(chǔ)系統(tǒng)中，當(dāng)硬件發(fā)出“缺頁(yè)中斷”后，引出操作系統(tǒng)來處理這個(gè)中斷事件。如果主存中已經(jīng)沒有空閑塊，則可用lru頁(yè)面調(diào)度算法把該作業(yè)中最先進(jìn)入主存的一頁(yè)調(diào)出，存放到磁盤上，然后再把當(dāng)前要訪問的頁(yè)裝入該塊。調(diào)出和裝入后都要修改頁(yè)表中對(duì)應(yīng)頁(yè)的標(biāo)志。（3）lru頁(yè)面調(diào)度算法總是淘汰該作業(yè)中距現(xiàn)在最久沒有訪問過的那一頁(yè)

21、，因此可以用一個(gè)數(shù)組來表示該作業(yè)已在主存的頁(yè)面。數(shù)組中的第一個(gè)元素總是指出當(dāng)前剛訪問的頁(yè)號(hào)，因此最久沒被訪問的頁(yè)總是由最后一個(gè)元素指出。入口初始化數(shù)據(jù)i指向下一個(gè)頁(yè)面頁(yè)面是否存在物理塊是否有空閑最近最久未使用的頁(yè)面作為淘汰頁(yè)i頁(yè)面長(zhǎng)度計(jì)算缺頁(yè)率，并輸出數(shù)據(jù)結(jié)束將頁(yè)面放空到空閑的物理塊處yy圖3.3最近最久未使用算法圖4.系統(tǒng)調(diào)試調(diào)試分析：調(diào)試是整個(gè)程序編寫過程中十分重要也是很困難的一部分，在這個(gè)過程中用了不少的時(shí)間進(jìn)行程序的調(diào)試，在調(diào)試過程中遇到的相關(guān)問題如下：一、語法錯(cuò)誤1、語句的最后忘記了加上“；”，使程序發(fā)生錯(cuò)誤。2、把“”寫反，以及字符與字符串的操作問題，這些是比較簡(jiǎn)單的錯(cuò)誤，很容易分

22、辨出來，并改正之。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è)問題困擾了我好長(zhǎng)時(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ì)中，遇到了一些困難

23、，例如怎么實(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為地址變換算法，選項(xiàng)2為頁(yè)面置換算法圖4.1主界面（2）進(jìn)入硬件地址變換算法：選擇；進(jìn)入之后共有輸入指令和進(jìn)入置換頁(yè)面算法兩個(gè)選項(xiàng)，當(dāng)輸入1時(shí)就可以進(jìn)行地址變換了。圖4.2地址變換界面（3）輸入選擇1后，系統(tǒng)自動(dòng)生成頁(yè)號(hào)，標(biāo)記位，外存地址和主存號(hào)，再輸入邏輯地址，系統(tǒng)即可算

24、出物理地址，并給出詳細(xì)信息：頁(yè)面號(hào)，主存號(hào)和偏移量圖4.3地址變換圖（4）當(dāng)輸入的邏輯地址超出地址范圍時(shí)就產(chǎn)生了缺頁(yè)中斷，顯示該頁(yè)不在主存內(nèi)圖4.4缺頁(yè)中斷圖（5）退回到主界面選擇2進(jìn)入頁(yè)面置換算法，有3個(gè)選擇：產(chǎn)生隨機(jī)序列號(hào)，先進(jìn)先出算法和最近最久未使用算法圖4.5進(jìn)入頁(yè)面置換算法界面（6）選擇1產(chǎn)生隨機(jī)進(jìn)程序列號(hào)：即可產(chǎn)生一組無規(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ì)列，缺頁(yè)次數(shù)和缺頁(yè)率圖4.8最近最久未使用算法圖（8）選擇3先進(jìn)先出算法，就可產(chǎn)生算法表和缺頁(yè)次數(shù)圖4.8先進(jìn)先出算法圖5.總結(jié)對(duì)于c+

25、初學(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)問題，包括一些語法錯(cuò)誤和運(yùn)行錯(cuò)誤，所以調(diào)試很重要，每當(dāng)出現(xiàn)的結(jié)果和預(yù)想的不一樣或是效果不是很好時(shí)就需要調(diào)試了。調(diào)試過程是一個(gè)完善程序的過程，也是一個(gè)提升自己編程能力的過程，在不斷的檢查與修改中，自己的編程能力才會(huì)不斷提升，只有這樣，最終的程序才會(huì)趨于簡(jiǎn)單、正確，避免冗長(zhǎng)、復(fù)雜。對(duì)于這

26、次編程實(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í)掌握水平不一，作為組長(zhǎng)因自身水平不高，果斷決定所有變量及函數(shù)名采用拼音縮寫。然后是隊(duì)員編出的程序無法完美兼容，顯示出我們溝通的缺乏。同時(shí)也表現(xiàn)出我們知識(shí)的欠缺，對(duì)于置換算法，地址變換及頁(yè)表的使用，了解的是在有限，仍需要不斷學(xué)習(xí)，書本上的東西跟本無法完成一個(gè)程序。每次報(bào)錯(cuò)我們需要根據(jù)錯(cuò)誤修改，改不了的就上網(wǎng)

27、查找原因,還有好多好多的瑕疵。但是不得不承認(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周長(zhǎng)林，左萬歷. 計(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.北京：清華大

28、學(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)，在此表示衷心的感謝！其次也感謝那些在我們不懂得時(shí)候給予我們幫助的同學(xué)。起初，我們剛開始設(shè)計(jì)時(shí)，對(duì)內(nèi)容掌握度根本就不夠，通過了4天的上機(jī)實(shí)習(xí)及課后的查閱資料、詢問同學(xué)才對(duì)自己的程序有了系統(tǒng)的認(rèn)識(shí)及完成程序的設(shè)計(jì)思路，并在大家的幫助下完成了本次課程設(shè)計(jì)的全部?jī)?nèi)容，看著自己做出來的東

29、西心中莫名的開心，在這次過程中也歷練了自己的耐心及學(xué)習(xí)方法?？傊谶@次實(shí)習(xí)中獲益匪淺。對(duì)馬老師再次表示感謝！附錄#include#include#include#include #include #include#includeusing namespace std;#define myprintf printf(|-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-|n) /*表格控制*/ #define bsize 4 /物理塊大小#define psize 16 /進(jìn)程大小void chushihua();/初始化函數(shù)void ymzh();void yemianzhihu

30、an();void changeaddr(struct page p,int logaddr);void dizhizhuanhuan();void menu();int wang();int yemianliu32=0;/全局變量數(shù)組，地址流int p; struct pageint pno;/頁(yè)號(hào)int flag;/標(biāo)志位int cno;/主存號(hào)int modf;/修改位int addr;/外存地址page; /全局變量p是一共有多少地址流typedef struct page1 int num; /*記錄頁(yè)面號(hào)*/ int time; /*記錄調(diào)入內(nèi)存時(shí)間*/ page1; /* 頁(yè)面邏

31、輯結(jié)構(gòu)，結(jié)構(gòu)為方便算法實(shí)現(xiàn)設(shè)計(jì)*/ page1 bbsize; /*內(nèi)存單元數(shù)*/ int 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,m

32、axflag = 0; /標(biāo)記替換物理塊進(jìn)程下標(biāo)int count = 0; /統(tǒng)計(jì)頁(yè)面缺頁(yè)次數(shù)void chushihua()/初始化函數(shù)int t;srand(time(0);/隨機(jī)產(chǎn)生指令序列 p=12+rand()%32;cout地址流序列：;coutendl;for(int i=0;i=0;i-)coutyemianliui ;coutendl;void ymzh()chushihua(); yemianzhihuan();void yemianzhihuan()int a;printf( - n);printf( - 歡迎使用分頁(yè)模擬實(shí)驗(yàn)系統(tǒng) - n);printf( - n);p

33、rintf( n);printf( 1.進(jìn)入硬件地址變換算法 n);printf( - n);printf( 2.進(jìn)入頁(yè)面置換算法 n);printf( n);printf(請(qǐng)輸入您的選擇:);switch(a)case 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(i

34、nt i=0;i8;i+)if(pi.pno=j)/找到對(duì)應(yīng)的頁(yè)號(hào)if(pi.flag=1)/頁(yè)面標(biāo)志為1addr=o*64+k;cout物理地址為: addrendl;cout詳細(xì)信息: t頁(yè)面號(hào)：pi.pnot主存號(hào):ot偏移量：kendl;flag=1;break;if(flag=0)cout該頁(yè)不在主存,產(chǎn)生缺頁(yè)中斷endl; void dizhizhuanhuan()int a;int ins;/指令邏輯地址struct page p8;p0.pno=0;p0.flag=1;o=5;p0.modf=1;p0.addr=011;p1.pno=1;p1.fl

35、ag=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.pno=6;p6.flag=0;p6.addr=212;p7.pno=7;p7.flag=0;p7.addr=213;printf(ttt-ttt);printf(ttt-歡迎進(jìn)入硬件地址變換界面

36、-ttt);printf(ttt-tttn);printf(ttt ttt); printf(ttt 1、輸入指令 ttt);printf(ttt -ttt); printf(ttt 2、進(jìn)入頁(yè)面置換算法 ttt);printf(ttt -ttt);printf(ttt 0、退出(exit) ttt); printf(ttt tttn);while(a!=0) coutendla;cout頁(yè)號(hào) 標(biāo)記位 外存地址 主存號(hào)endl;for(int i=0;i8;i+) coutpi.pnotpi.flagtpi.addrt;if(pi.flag)o;coutendl; switc

37、h(a)case 0:printf(ttt- 再見！- tttn);break;case 1:coutins;changeaddr(p,ins);break;case 2:system(cls);a=wang();break;default:cout輸入有誤，請(qǐng)重新輸入！endl;break;void menu()int a; printf(ttt-ttt);printf(ttt-歡迎使用分頁(yè)模擬實(shí)驗(yàn)系統(tǒng)-ttt);printf(ttt-tttn);printf(ttt ttt); printf(ttt 1、進(jìn)入硬件地址變換算法 ttt);printf(ttt -ttt); printf(tt

38、t 2、進(jìn)入頁(yè)面置換算法 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;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è)

39、進(jìn)程序列號(hào)為：n);int i = 0; for(i=0; ipsize; i+) proi = 10*rand()/(rand_max+1)+1; printf(%d ,proi); printf(n); return(pro);/*/查找空閑物理塊int searchpb()for(j=0; jbsize; 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;/*/

40、初始化內(nèi)存void empty()for(i=0;ibsize;i+)phbi=0; count=0; /計(jì)數(shù)器置零/*/先進(jìn)先出頁(yè)面置換算法void fifo() for(i = 0; ipsize; i+) m=searchpb(); n=searchpro();/找flag值最大的 for(j = 0; j 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+)

41、flagj+; m = -1; else /不存在空閑物理塊 phbmax = proi; flagmax = 0; for(j = 0;j 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(缺頁(yè)次數(shù)為：%dn,count);printf(n);/*初始化內(nèi)存單元、緩沖區(qū)*/ void init(page1 *b,int cbsizepsize) int i,j; for(i=0;ipsize;i+) bi.num=-1;