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

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

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

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

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

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

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

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

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

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

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

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

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

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

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