虛擬存儲(chǔ)器管理系統(tǒng) 操作系統(tǒng)課程設(shè)計(jì)

1、目 錄第1章 設(shè)計(jì)任務(wù)分析. 111 虛擬存儲(chǔ)技術(shù)分析. 112 使用算法分析：. 2第2章 總設(shè)計(jì)方案. 52.1 置換算法思想. 522 LRU置換算法的硬件支持 . 5第3章 程序設(shè)計(jì)結(jié)構(gòu)圖. 731虛擬存儲(chǔ)管理器系統(tǒng)設(shè)計(jì)總框圖 . 732各模塊功能N-S 圖 .7第4章 程序測(cè)試結(jié)果. 12第5章 設(shè)計(jì)心得. 14第1章 設(shè)計(jì)任務(wù)分析本設(shè)計(jì)的目的是通過(guò)設(shè)計(jì)一個(gè)簡(jiǎn)單的虛擬存儲(chǔ)器管理系統(tǒng)來(lái)模擬實(shí)際的頁(yè)面調(diào)度算法與過(guò)程，以掌握這種有用的技術(shù)。要求將其輸入/輸出處理程序編成一個(gè)獨(dú)立的進(jìn)程模塊并與其它請(qǐng)求輸入/輸出的進(jìn)程并發(fā)運(yùn)行。并要求加入設(shè)備管理子模塊。11虛擬存儲(chǔ)技術(shù)分析虛擬存儲(chǔ)技術(shù)是隨著計(jì)

2、算機(jī)技術(shù)的發(fā)展而發(fā)展起來(lái)的。早在20世紀(jì)70年代，為了克服內(nèi)存容量小成本高而不適應(yīng)大型程序應(yīng)用需要的矛盾，人們開(kāi)發(fā)了虛擬內(nèi)存技術(shù)。隨著計(jì)算機(jī)技術(shù)及相關(guān)信息處理技術(shù)的不斷發(fā)展，人們對(duì)存儲(chǔ)的需求越來(lái)越大，單個(gè)大容量磁盤(pán)已不能適應(yīng)應(yīng)用的需要，虛擬存儲(chǔ)技術(shù)又有進(jìn)一步的發(fā)展，如在操作系統(tǒng)下將一組硬盤(pán)捆綁成帶區(qū)集（STRIP ）作為單個(gè)邏輯存儲(chǔ)單元供主機(jī)訪問(wèn)；磁盤(pán)冗余陣列（RAID ）技術(shù)將多個(gè)物理磁盤(pán)通過(guò)一定的邏輯關(guān)系集合起來(lái)，成為一個(gè)大容量的虛擬磁盤(pán)。從某種意義上講，SAN 本身也是虛擬存儲(chǔ)技術(shù)的應(yīng)用。所謂虛擬存儲(chǔ)技術(shù)，是指把多個(gè)物理上獨(dú)立存在的存儲(chǔ)體通過(guò)軟件或硬件的手段集中管理起來(lái)，形成一個(gè)邏輯上的

3、虛擬存儲(chǔ)單元供主機(jī)訪問(wèn)。這個(gè)虛擬邏輯單元的存儲(chǔ)容量是它所集中管理的各物理存儲(chǔ)體的存儲(chǔ)容量之和，而它的訪問(wèn)帶寬則在一定程度上接近各個(gè)物理存儲(chǔ)體的訪問(wèn)帶寬之和。虛擬存儲(chǔ)實(shí)際上是邏輯存儲(chǔ)，是一種智能、有效地管理存儲(chǔ)數(shù)據(jù)的方式。虛擬存儲(chǔ)克服了物理存儲(chǔ)的局限，它可以把物理設(shè)備變成完全不同的邏輯鏡像，呈現(xiàn)給用戶，既充分利用了物理設(shè)備的優(yōu)勢(shì)，如高性能、高可用，又打破了物理設(shè)備本身不可克服的局限性。從用戶角度看，使用存儲(chǔ)空間而不是使用物理存儲(chǔ)硬件，管理存儲(chǔ)空間而不是管理物理存儲(chǔ)部件，這就是虛擬存儲(chǔ)的概念。虛擬存儲(chǔ)技術(shù)不僅可以提高主機(jī)訪問(wèn)存儲(chǔ)設(shè)備的性能，同時(shí)對(duì)于存儲(chǔ)容量的擴(kuò)展是非常方便的，可以保護(hù)原有投資，實(shí)現(xiàn)

4、不影響正常數(shù)據(jù)訪問(wèn)的前提下的動(dòng)態(tài)擴(kuò)容。虛擬存儲(chǔ)技術(shù)為實(shí)際應(yīng)用帶來(lái)的好處主要體現(xiàn)在以下幾個(gè)方面：1）虛擬存儲(chǔ)技術(shù)使網(wǎng)絡(luò)系統(tǒng)存儲(chǔ)部分的重要指標(biāo)單個(gè)邏輯單元的存儲(chǔ)容量和訪問(wèn)帶寬相對(duì)單個(gè)物理存儲(chǔ)體大大提高，適應(yīng)了網(wǎng)絡(luò)應(yīng)用特別是視頻網(wǎng)絡(luò)應(yīng)用的需要。2）在虛擬存儲(chǔ)環(huán)境下，無(wú)論后端物理存儲(chǔ)體是什么設(shè)備，服務(wù)器及其應(yīng)用系統(tǒng)看到的都是其熟悉的存儲(chǔ)設(shè)備的邏輯鏡像。即使物理存儲(chǔ)體發(fā)生變化，其邏輯鏡像也不發(fā)生變化，應(yīng)用系統(tǒng)無(wú)需關(guān)心后端存儲(chǔ)，只需專注于管理存儲(chǔ)空間，使得存儲(chǔ)管理變得輕松簡(jiǎn)單，便于靈活配置。3）虛擬存儲(chǔ)是一種智能化的系統(tǒng)，它允許客戶以透明有效的方式在磁盤(pán)或磁帶上存儲(chǔ)數(shù)據(jù)，使客戶的存儲(chǔ)系統(tǒng)容納更多的數(shù)據(jù)，也

5、使更多的用戶可以共享同一個(gè)系統(tǒng)。虛擬存儲(chǔ)器的效率是系統(tǒng)性能評(píng)價(jià)的重要內(nèi)容，它與主存容量、頁(yè)面大小、命中率，程序局部性和替換算法等因素有關(guān)。12使用算法分析：1 什么是先進(jìn)先出淘汰算法？該算法總是淘汰最先進(jìn)入內(nèi)存的頁(yè)面，即懸著在內(nèi)存中駐留時(shí)間最久的頁(yè)面予以淘汰。2 實(shí)現(xiàn)方法系統(tǒng)保留一張次序表，該表記錄了作業(yè)程序的各頁(yè)面進(jìn)入主存的先后次序。 ·用數(shù)組作次序表可在主存中建立一個(gè)m(m是分配給該作業(yè)的存儲(chǔ)塊數(shù) 個(gè)元素的頁(yè)號(hào)表和一個(gè)調(diào)換指針。如下圖所示： ·用存儲(chǔ)分塊表作次序表該次序表以塊號(hào)為序，依次各塊的分配情況。這里假定m 4，且4，5，1，2頁(yè)以依次裝入2，6，7，4各存儲(chǔ)塊中

6、。此時(shí)存儲(chǔ)分塊表如下圖所示： （a ）替換以前 1 什么是最久未使用淘汰算法？當(dāng)需要淘汰一頁(yè)時(shí)，總是選擇最長(zhǎng)時(shí)間未被使用的那一頁(yè)淘汰。2 實(shí)現(xiàn)方法·用硬件實(shí)現(xiàn)此算法每一頁(yè)可以設(shè)置一個(gè)R 位的寄存器；每次訪問(wèn)一頁(yè)時(shí)，將該頁(yè)所對(duì)應(yīng)的寄存器的最左一位置1；每隔時(shí)間t 將所有的R 位寄存器右移一位。這樣，在T Rt 時(shí)間內(nèi)，方問(wèn)過(guò)的頁(yè)多對(duì)應(yīng)的寄存器R 內(nèi)時(shí)一個(gè)不全為0的整數(shù)，而沒(méi)有訪問(wèn)過(guò)的頁(yè)相對(duì)應(yīng)的R 之值為0。當(dāng)缺頁(yè)中斷時(shí)，選擇R 值最小的那頁(yè)進(jìn)行淘汰。·用頁(yè)號(hào)棧實(shí)現(xiàn)此算法設(shè)立一個(gè)頁(yè)號(hào)棧，使棧頂元素為剛北訪問(wèn)的頁(yè)面，而棧底元素為最久未被訪問(wèn)的頁(yè)面。每當(dāng)訪問(wèn)頁(yè)面時(shí)，該頁(yè)號(hào)棧需進(jìn)行調(diào)

7、整。一個(gè)頁(yè)面被訪問(wèn)過(guò)，就立即將它的頁(yè)號(hào)記在頁(yè)號(hào)棧的頂部，而將棧中原有的頁(yè)號(hào)依次下移。如果棧中原有的頁(yè)號(hào)中有與新記入頂部的頁(yè)號(hào)相重者，則將該重號(hào)抽出，且將頁(yè)號(hào)棧內(nèi)容進(jìn)行緊湊壓縮。1 什么是最佳淘汰算法？當(dāng)需要淘汰一頁(yè)時(shí)，將選擇以后永不使用的或許是在最長(zhǎng)(未來(lái) 時(shí)間內(nèi)不再被訪問(wèn)的頁(yè)面。2 算法優(yōu)勢(shì)采用最佳置換算法，通?？杀ＷC獲得最低的缺頁(yè)率。但由于人目前還無(wú)法預(yù)知一個(gè)進(jìn)程在內(nèi)存的若干個(gè)頁(yè)面中，哪一個(gè)頁(yè)面是未來(lái)最長(zhǎng)時(shí)間內(nèi)不再被訪問(wèn)的，因而該算法是無(wú)法實(shí)現(xiàn)的，便可以利用此算法來(lái)評(píng)價(jià)其它算法。第2章 總設(shè)計(jì)方案2.1 置換算法思想這是最早出現(xiàn)的置換算法。該算法總是淘汰最先進(jìn)入內(nèi)存的頁(yè)面，即選擇在內(nèi)存中駐

8、留時(shí)間最久的頁(yè)面予以淘汰。該算法實(shí)現(xiàn)簡(jiǎn)單只需把一個(gè)進(jìn)程已調(diào)入內(nèi)存的頁(yè)面，按先后次序鏈接成一個(gè)隊(duì)列，并設(shè)置一個(gè)指針，稱為替換指針，使它總是指向最老的頁(yè)面。22 LRU置換算法的硬件支持為了記錄某個(gè)進(jìn)程在內(nèi)存中各頁(yè)的使用情況，須為每個(gè)在內(nèi)存中的頁(yè)面配置一個(gè)移位寄存器，可表示為R=Rn-1Rn-2Rn-3R2R1R0 當(dāng)進(jìn)程訪問(wèn)某物理塊時(shí)，要將相應(yīng)寄存器的Rn-1位置成1。此時(shí)，定時(shí)信號(hào)將每隔一定時(shí)間(例如100ms 將寄存器右移一位。如果我們把n 位寄存器的數(shù)看作是一個(gè)整數(shù)，那么具有最小數(shù)值的寄存器所對(duì)應(yīng)的頁(yè)面，就是最近最久未使用的頁(yè)面。如圖1示出了某進(jìn)程在內(nèi)存中具有8個(gè)頁(yè)面，為每個(gè)內(nèi)存頁(yè)面配置一

9、個(gè)8位寄存器時(shí)的LRU 訪問(wèn)情況。這里，把8個(gè)內(nèi)存頁(yè)面的序號(hào)分別定為18。由圖可以看出，第7個(gè)內(nèi)存頁(yè)面的R 值最小，當(dāng)發(fā)生缺頁(yè)時(shí)首先將它置換出去。 可利用一個(gè)特殊的棧來(lái)保存當(dāng)前使用的各個(gè)頁(yè)面的頁(yè)面號(hào)。每當(dāng)進(jìn)程訪問(wèn)某頁(yè)面時(shí)，便將頁(yè)面的頁(yè)面號(hào)從棧中移出，將它壓入棧頂。因此，棧頂始終是最新被訪問(wèn)頁(yè)面的編號(hào)民，而棧底則是最近最久未使用的頁(yè)面的頁(yè)面號(hào)。第3章 程序設(shè)計(jì)結(jié)構(gòu)圖31虛擬存儲(chǔ)管理器系統(tǒng)設(shè)計(jì)總框圖 系統(tǒng)功能描述：通過(guò)設(shè)計(jì)操作系統(tǒng)中虛擬存儲(chǔ)管理系統(tǒng)解決存儲(chǔ)容量和存取速度矛盾，是管理存儲(chǔ)設(shè)備的有效方法。使用FIFO ，LRU ，OPT ，三種置換算法置換頁(yè)面進(jìn)行比較，選擇適合虛擬存儲(chǔ)管理系統(tǒng)理想的調(diào)

10、度算法。32各模塊功能N-S 圖尋找時(shí)間最長(zhǎng)的頁(yè)面功能模塊：算法思想：通過(guò)尋找時(shí)間最長(zhǎng)的頁(yè)面，為進(jìn)行FIFO ，LRU,ORT 三種調(diào)度算法運(yùn)算提供前提條件。主要參數(shù)功能 :Pro *page 用來(lái)指向調(diào)入內(nèi)存最長(zhǎng)時(shí)間的頁(yè)面Max(函數(shù)N-S 圖 內(nèi)存頁(yè)面輸入功能模塊：算法思想：通過(guò)輸入內(nèi)存頁(yè)面，選擇調(diào)度功能，并輸入正確頁(yè)面流文件名，顯示讀入的頁(yè)面流，如文件不符，則顯示“錯(cuò)誤，文件打不開(kāi)，請(qǐng)檢查文件名”。 指針頁(yè)面移動(dòng)功能模塊：算法思想：通過(guò)指針移動(dòng)進(jìn)行頁(yè)面置換的工作。 FIFO 功能模塊：算法思想：該算法總是淘汰最先進(jìn)入內(nèi)存的頁(yè)面，即選擇在內(nèi)存中駐留時(shí)間最久的頁(yè)面予以淘汰。該算法實(shí)現(xiàn)簡(jiǎn)單只需

11、把一個(gè)進(jìn)程已調(diào)入內(nèi)存的頁(yè)面，按先后次序鏈接成一個(gè)隊(duì)列，并設(shè)置一個(gè)指針，稱為替換指針，使它總是指向最老的頁(yè)面。 LRU 功能模塊：算法思想：最近最久未使用（LRU ）置換算法，是根據(jù)頁(yè)面調(diào)入內(nèi)存后的使用情況進(jìn)行決策的。由于無(wú)法預(yù)測(cè)各頁(yè)面將來(lái)的使用情況，只能利用“最近的過(guò)去”作為“最近的將來(lái)”的近似，因此，LRU 置換算法是選擇最近最久未使用的頁(yè)面予以淘汰。該算法賦予每個(gè)頁(yè)面一個(gè)訪問(wèn)字段，用來(lái)記錄一個(gè)頁(yè)面自上次被訪問(wèn)以來(lái)所經(jīng)歷的時(shí)間t, ，當(dāng)須淘汰一個(gè)頁(yè)面時(shí)，選擇現(xiàn)有頁(yè)面中其t 值最大的，即最近最久未使用的頁(yè)面予以淘汰。 OPT 算法思想：選擇的被淘汰頁(yè)面，將是以后永不使用的或許是在最長(zhǎng)(未來(lái) 時(shí)

12、間內(nèi)不再被訪問(wèn)的頁(yè)面。采用最佳置換算法，通?？杀ＷC獲得最低的缺頁(yè)率。但由于人目前還無(wú)法預(yù)知一個(gè)進(jìn)程在內(nèi)存的若干個(gè)頁(yè)面中，哪一個(gè)頁(yè)面是未來(lái)最長(zhǎng)時(shí)間內(nèi)不再被訪問(wèn)的，因而該算法是無(wú)法實(shí)現(xiàn)的，便可以利用此算法來(lái)評(píng)價(jià)其它算法。 第4章 程序測(cè)試結(jié)果 第5章 設(shè)計(jì)心得通過(guò)近一個(gè)月的課程設(shè)計(jì), 加深了對(duì)操作系統(tǒng)的認(rèn)識(shí), 了解了操作系統(tǒng)中各種資源分配算法的實(shí)現(xiàn), 特別是對(duì)虛擬存儲(chǔ), 頁(yè)面置換有了深入的了解, 并能夠用高級(jí)語(yǔ)言進(jìn)行模擬演示。這次的操作系統(tǒng)大作業(yè)的工作量比較大，我投入了很多的時(shí)間和精力才完成了系統(tǒng)的設(shè)計(jì)。不過(guò)這些付出都是值得的，因?yàn)槲沂斋@了更多。首先，我必須要了解虛擬內(nèi)存的特性，通過(guò)到圖書(shū)館找資料

13、，翻閱書(shū)本和網(wǎng)上搜索，理解到虛擬頁(yè)式管理的基本原理是系統(tǒng)自動(dòng)地將作業(yè)的地址空間分頁(yè)，將系統(tǒng)的主存空間分塊，頁(yè)與塊等大小，在作業(yè)運(yùn)行前，只把初始需要的一部分頁(yè)面裝入內(nèi)存塊里，運(yùn)行中需要訪問(wèn)自己地址空間中的當(dāng)前不在內(nèi)存的頁(yè)面時(shí)產(chǎn)生缺頁(yè)中斷，由缺頁(yè)中斷服務(wù)程序?qū)⑺璧捻?yè)面調(diào)入內(nèi)存，若此時(shí)內(nèi)存中沒(méi)有空閑物理塊安置請(qǐng)求調(diào)入的新頁(yè)面，則系統(tǒng)按預(yù)定的置換策略自動(dòng)選擇一個(gè)或一些在內(nèi)存的頁(yè)面，把它們換出到外存。還有研究了主存頁(yè)面的分配策略和頁(yè)面調(diào)入時(shí)機(jī)。這對(duì)之后的算法編寫(xiě)有很大的幫助。其后，是要熟悉各算法的思想，我重新復(fù)習(xí)了操作系統(tǒng)頁(yè)面調(diào)度中OPT 、FIFO 、LRU 的算法，上網(wǎng)查閱各算法的資料，經(jīng)過(guò)一段時(shí)

14、間的研究，我開(kāi)始編寫(xiě)算法的程序。雖然了解了各算法的思想，但到編寫(xiě)起程序來(lái)，還是有一點(diǎn)難度，又需要再?gòu)?fù)習(xí)C+的部分語(yǔ)法，如文件流的輸入輸出，因?yàn)閷?duì)課堂知識(shí)只是了解，但實(shí)踐中有些不常用的命令很容易會(huì)遺忘。開(kāi)始時(shí)還是毫無(wú)頭緒，參考到一些資料和網(wǎng)上有關(guān)的代碼，經(jīng)過(guò)跟組員研究后，試著寫(xiě)一段測(cè)試一段地，逐漸把程序完善。在此過(guò)程中，兩種頁(yè)面置換算法FIFO 和LRU 理解起來(lái)相當(dāng)容易，但在實(shí)際編程實(shí)現(xiàn)的時(shí)候需要注意各種細(xì)節(jié)，需要耐心細(xì)致，實(shí)際編程中遇到一些細(xì)節(jié)上的小問(wèn)題確實(shí)需要仔細(xì)考慮才行。另外，先進(jìn)先出頁(yè)面置換和LRU 算法兩者各有特點(diǎn)，但是實(shí)踐起來(lái)卻很大，使自己對(duì)頁(yè)面置換算法有了新的認(rèn)識(shí)。在我做預(yù)設(shè)計(jì)的時(shí)候因?yàn)檫€沒(méi)有完善好程序的功能，所以這方面我的工作做得不夠完美，不夠具體，在詳細(xì)設(shè)計(jì)和編程中，我們都修復(fù)了這些缺點(diǎn)并進(jìn)行了改善，像界面變得更美化些，程序上變得更簡(jiǎn)潔些容易修改些。然后是設(shè)計(jì)功能及界面，參考了許多相關(guān)的程序代碼和書(shū)本的資料，以及按照指導(dǎo)書(shū)的要求，我初步設(shè)計(jì)了個(gè)輪廓，功能方面也只能按理想化設(shè)計(jì)，因?yàn)槲从袑?shí)際操作到，還不能預(yù)計(jì)到一些實(shí)際性的問(wèn)題。在本次實(shí)驗(yàn)中，通過(guò)瀏覽、閱