第4章__存儲管理ppt課件計(jì)算機(jī)操作系統(tǒng)第三版

1、第4章 存儲管理,4.1 概述 4.2 分區(qū)存儲管理方案 4.3 頁式存儲管理 4.4 段式存儲管理 4.5 段頁式存儲管理 4.6 交換技術(shù)與覆蓋技術(shù) 4.7 虛擬存儲 4.8 高速緩沖存儲器 4.9 內(nèi)存管理實(shí)例分析 習(xí)題,4.1 概 述,存儲器是計(jì)算機(jī)系統(tǒng)中的重要組成部分，隨著計(jì)算機(jī)技術(shù)的飛速發(fā)展和內(nèi)存價(jià)格的降低，現(xiàn)代計(jì)算機(jī)中的內(nèi)存也在不斷增加，已經(jīng)達(dá)到GB的范圍。,4.1.1 存儲體系 存儲器的功能是保存指令和數(shù)據(jù)，它的發(fā)展方向是高速、大容量和小體積，諸如內(nèi)存在訪問速度方面的發(fā)展有DRAM、SDRAM、SRAM等技術(shù)；而磁盤技術(shù)的發(fā)展方向主要在大容量方面，比如接口標(biāo)準(zhǔn)、存儲密度等。,存

2、儲組織的功能是在存儲技術(shù)和CPU尋址技術(shù)許可的范圍內(nèi)組織合理的存儲結(jié)構(gòu)，其依據(jù)是訪問速度的匹配關(guān)系、容量要求和價(jià)格。常見的存儲結(jié)構(gòu)有兩種：“寄存器內(nèi)存外存”結(jié)構(gòu)和“寄存器快速緩存內(nèi)存外存”結(jié)構(gòu)。 圖4.1所示的是“寄存器快速緩存內(nèi)存外存”結(jié)構(gòu)。,圖4.1 存儲層次結(jié)構(gòu),從源程序到程序執(zhí)行,編譯：編譯程序 由編譯程序（Compiler）將用戶源代碼編譯成若干個(gè)目標(biāo)模塊。 鏈接：鏈接程序 由鏈接程序（Linker）將編譯后形成的一組目標(biāo)模塊，以及它們所需要的庫函數(shù)鏈接在一起，形成裝入模塊。 裝入：裝入程序 由裝入程序（Loader）將裝入模塊復(fù)制到內(nèi)存中。,庫,地址空間的概念,物理（絕對）地址程序

3、執(zhí)行 每個(gè)內(nèi)存單元的固定順序地址（編號）。 邏輯（相對）地址裝入（匯編編譯） 被鏈接裝配（或匯編、編譯）后的目標(biāo)模塊所限定的地址的集合； 相對于某個(gè)基準(zhǔn)量（通常為：0）的編址。,4.1.2 地址重定位 可執(zhí)行文件的建立過程是：源程序編譯目標(biāo)模塊(多個(gè)目標(biāo)模塊或程序庫) 鏈接可執(zhí)行文件。當(dāng)程序執(zhí)行時(shí)由操作系統(tǒng)裝入內(nèi)存而成為進(jìn)程。 對程序員來說，數(shù)據(jù)的存放地址是由符號決定的，故稱為符號名地址，或者稱為名地址。,當(dāng)程序被裝入內(nèi)存時(shí)，程序的邏輯地址被轉(zhuǎn)換成內(nèi)存的物理地址，稱為地址重定位。 在可執(zhí)行文件裝入時(shí)需要解決可執(zhí)行文件中地址(指令和數(shù)據(jù))和內(nèi)存地址的對應(yīng)問題。這是由操作系統(tǒng)中的裝入程序Loade

4、r來完成的，如圖4.2所示。,圖4.2 地址重定位,1絕對裝入(absolute loading) 在可執(zhí)行文件中記錄內(nèi)存地址，裝入時(shí)直接定位于上述內(nèi)存地址的方式稱為絕對裝入(或者稱為固定地址再定位)。 在這種方式下，程序的地址再定位是在執(zhí)行之前被確定的，也就是在編譯、鏈接時(shí)直接制定程序在執(zhí)行時(shí)訪問的實(shí)際存儲器地址。這樣，程序的地址空間和內(nèi)存地址空間是一一對應(yīng)的。單片機(jī)或者單用戶系統(tǒng)常采用這種方式。 固定地址再定位的優(yōu)點(diǎn)是裝入過程簡單；缺點(diǎn)是過于依賴于硬件結(jié)構(gòu)，不適合多道程序系統(tǒng)。,2可重定位裝入(relocatable loading) 可重定位裝入方式是指在可執(zhí)行文件中，列出各個(gè)需要重定位

5、的地址單元和相對地址值，裝入時(shí)再根據(jù)所定位的內(nèi)存地址去修改每個(gè)重定位地址項(xiàng)，添加相應(yīng)的偏移量。 一個(gè)有相對地址空間的程序裝入到物理地址空間時(shí)，由于兩個(gè)空間不一致，就需要進(jìn)行地址變換，或稱地址映射，即地址的再定位。 地址再定位有兩種方式：靜態(tài)再定位和動態(tài)再定位。,1) 靜態(tài)再定位 靜態(tài)再定位是指當(dāng)程序執(zhí)行時(shí)，由裝入程序運(yùn)行重定位程序，根據(jù)作業(yè)在內(nèi)存重分配的起始地址，將可執(zhí)行的目標(biāo)代碼裝入到指定內(nèi)存中。所謂靜態(tài)，是指地址定位完成后，在程序的執(zhí)行期間將不會再發(fā)生變化。靜態(tài)再定位是在程序執(zhí)行之前進(jìn)行地址再定位的，這一工作通常是由裝配程序完成的。,靜態(tài)重定位示意圖,靜態(tài)地址再定位的優(yōu)點(diǎn)是：無需硬件地址變

6、化機(jī)構(gòu)支持，容易實(shí)現(xiàn)；無需硬件支持，它只要求程序本身是可再定位的；它只對那些要修改的地址部分做出某種標(biāo)識，再由專門設(shè)計(jì)的程序來完成。在早期的操作系統(tǒng)中大多數(shù)都采用這種方法。 靜態(tài)地址再定位的缺點(diǎn)是：必須給作業(yè)分配一個(gè)連續(xù)的存儲區(qū)域，該存儲區(qū)不能分布在內(nèi)存的不同區(qū)域；在作業(yè)的執(zhí)行期間不能擴(kuò)充存儲空間，也不能在內(nèi)存中移動，因而不能重新分配內(nèi)存，不利于內(nèi)存的有效利用；多個(gè)用戶很難共享內(nèi)存中的同一程序，如若共享同一程序，則各用戶必須使用自己的副本。,2) 動態(tài)再定位 動態(tài)地址再定位是在程序執(zhí)行期間，在每次存儲訪問之前進(jìn)行的。程序在裝入內(nèi)存時(shí)，并不修改程序的邏輯地址值，而是在訪問物理內(nèi)存之前，再實(shí)時(shí)地將

7、邏輯地址轉(zhuǎn)換成物理地址。在這種情況下，其實(shí)現(xiàn)機(jī)制要依賴硬件地址變換機(jī)構(gòu)，即通過基地址寄存器BR、變址寄存器VR計(jì)算出指令的有效地址，再利用硬件機(jī)構(gòu)實(shí)現(xiàn)地址變換，如圖4.3所示。,圖4.3 動態(tài)地址再定位的原理,從圖4.3中可以看出：當(dāng)程序開始執(zhí)行時(shí)，系統(tǒng)將程序在內(nèi)存的起始地址送入BR中。執(zhí)行指令時(shí)，系統(tǒng)將邏輯地址與BR中的起始地址相加，從而得到物理地址。 動態(tài)地址再定位的優(yōu)點(diǎn)是：程序在執(zhí)行期間可以換入和換出內(nèi)存，這樣可以緩解內(nèi)存緊張的矛盾；可以把內(nèi)存中的碎片集中起來，以充分利用空間；不必給程序分配連續(xù)的內(nèi)存空間，可以較好地利用較小的內(nèi)存塊；若干用戶可以共享同一程序。,動態(tài)地址再定位的缺點(diǎn)：需要

8、附加的硬件支持，而且實(shí)現(xiàn)存儲管理的軟件算法比較復(fù)雜。,3動態(tài)運(yùn)行期裝入 動態(tài)運(yùn)行期裝入(dynamic run-time loading)是指在可執(zhí)行文件中記錄虛擬內(nèi)存地址，在裝入和執(zhí)行時(shí)通過硬件地址變換機(jī)構(gòu)完成虛擬地址到實(shí)際內(nèi)存地址的變換。 動態(tài)運(yùn)行期裝入的優(yōu)點(diǎn)是：操作系統(tǒng)可以將一個(gè)程序分散存放于不連續(xù)的內(nèi)存空間，可以通過移動程序來實(shí)現(xiàn)共享；能夠支持程序執(zhí)行中產(chǎn)生的地址引用，如指針變量(而不僅是生成可執(zhí)行文件時(shí)的地址引用)。 動態(tài)運(yùn)行期裝入的缺點(diǎn)是：需要硬件支持(通常是CPU)，操作系統(tǒng)的實(shí)現(xiàn)比較復(fù)雜。,4.1.3 鏈接 1鏈接方法 常見的鏈接方法有靜態(tài)鏈接和動態(tài)鏈接兩種。 1) 靜態(tài)鏈接

9、靜態(tài)鏈接(static linking)是在生成可執(zhí)行文件時(shí)進(jìn)行的，即在目標(biāo)模塊中記錄被調(diào)用模塊的名字符號地址(symbolic address)，在可執(zhí)行文件中將該名字改寫為指令直接使用的數(shù)字地址，如圖4.4所示。,圖4.4 靜態(tài)鏈接,2) 動態(tài)鏈接 動態(tài)鏈接(dynamic-linking)是在運(yùn)行可執(zhí)行文件時(shí)進(jìn)行的,亦即，執(zhí)行過程中，當(dāng)發(fā)現(xiàn)一個(gè)被調(diào)用模塊未裝入內(nèi)存時(shí)，立即取找到該模塊，并鏈接到調(diào)用者模塊上。 通常被鏈接的共享代碼稱為動態(tài)鏈接庫(Dynamic Link Library，DLL)或共享庫(shared library)。,動態(tài)鏈接的優(yōu)點(diǎn)是： (1) 共享：多個(gè)進(jìn)程可以共用一

10、個(gè)DLL，比較節(jié)省內(nèi)存，從而可以減少文件的交換。 (2) 部分裝入：一個(gè)進(jìn)程可以將多種操作分散在不同的DLL中實(shí)現(xiàn)，而只將當(dāng)前操作的DLL裝入內(nèi)存。 (3) 便于局部代碼修改：即便于代碼升級和代碼重用；只要函數(shù)的接口參數(shù)(輸入和輸出)不變，則修改函數(shù)及其DLL時(shí)，無需對可執(zhí)行文件重新編譯或鏈接。 (4) 便于適應(yīng)運(yùn)行環(huán)境：調(diào)用不同的DLL，就可以適應(yīng)多種使用環(huán)境并提供不同的功能。,動態(tài)鏈接的缺點(diǎn)是： (1) 增加了程序執(zhí)行時(shí)的鏈接開銷。 (2) 程序由多個(gè)文件組成，因此增加了管理復(fù)雜度。,4.1.5 存儲管理的任務(wù) 在現(xiàn)代操作系統(tǒng)中，存儲管理的主要任務(wù)有以下幾個(gè)方面。 (1) 存儲分配和回收：

11、是存儲管理的主要內(nèi)容，用來確定其算法和相應(yīng)的數(shù)據(jù)結(jié)構(gòu)。 (2) 地址變換(地址再定位)：可執(zhí)行文件生成中的鏈接技術(shù)、程序加載時(shí)的重定位技術(shù)及進(jìn)程運(yùn)行時(shí)硬件和軟件的地址變換技術(shù)和機(jī)構(gòu)。,(3) 存儲共享和保護(hù)：將代碼和數(shù)據(jù)共享，設(shè)定對地址空間的訪問權(quán)限(讀、寫、執(zhí)行)。 (4) 存儲器擴(kuò)充：它涉及存儲器的邏輯組織和物理組織，有兩種控制方式： 如果由應(yīng)用程序控制，則采用覆蓋技術(shù)。 如果由操作系統(tǒng)控制，則采用交換技術(shù)(整個(gè)進(jìn)程空間范圍內(nèi))或請求調(diào)入和預(yù)調(diào)入(部分進(jìn)程空間)。,4.1.6 各種存儲管理方案 從操作系統(tǒng)的發(fā)展歷史來看，存儲管理主要有以下幾個(gè)方案： (1) 分區(qū)存儲管理方案：是一種連續(xù)存儲

12、管理方案，但需要一次性全部裝入內(nèi)存。 (2) 段式存儲管理方案：是一種不連續(xù)存儲管理方案，段和段之間可以不連續(xù)，但需要一次性全部裝入內(nèi)存。 (3) 頁式存儲管理方案：是一種不連續(xù)存儲管理方案，也需要一次性全部裝入內(nèi)存。,(4) 段頁式存儲管理方案：是一種不連續(xù)存儲方案，如果采用純分頁和分段思想，需要一次性全部裝入內(nèi)存；如果采用虛擬存儲思想，則不需要一次性全部裝入內(nèi)存。 (5) 交換技術(shù)和覆蓋技術(shù)：是存儲擴(kuò)充的兩種技術(shù)，其中交換技術(shù)的優(yōu)點(diǎn)是編寫程序時(shí)不需要特殊的控制，也不會影響程序的結(jié)構(gòu)。 (6) 虛擬存儲管理方案：又分為兩種，分別是虛擬頁式(請求分頁)存儲管理和虛擬段式(請求分段)存儲管理。,

13、4.2 分區(qū)存儲管理方案,分區(qū)存儲管理方案的數(shù)據(jù)結(jié)構(gòu)是分區(qū)表或分區(qū)鏈表，主要功能是： (1) 可以只記錄空閑分區(qū)，也可以同時(shí)記錄空閑和占用分區(qū)。 (2) 分區(qū)表中，表項(xiàng)數(shù)目隨著內(nèi)存的分配和釋放而動態(tài)改變，可以規(guī)定最大表項(xiàng)數(shù)目。 (3) 分區(qū)表可以劃分為兩個(gè)表格：空閑分區(qū)表和分配分區(qū)表，從而減小每個(gè)表格的長度。,4.2.1 單一連續(xù)分區(qū)存儲管理 單一連續(xù)分區(qū)存儲管理把整個(gè)內(nèi)存空間的最低端和最高端作為操作系統(tǒng)區(qū)，中間作為用戶程序區(qū)。在DOS操作系統(tǒng)中就采用了這種方法，如圖4.7所示。,圖4.7 單一連續(xù)分區(qū)存儲管理的分配方式,這種存儲分配思想將內(nèi)存分為兩個(gè)區(qū)域：系統(tǒng)區(qū)和用戶區(qū)。應(yīng)用程序裝入到用戶區(qū)

14、，可使用用戶區(qū)全部空間。 單一連續(xù)分區(qū)的優(yōu)點(diǎn)是：簡單，適用于單用戶、單任務(wù)的操作系統(tǒng)(比如CP/M和DOS操作系統(tǒng))，不需要復(fù)雜的硬件支持。 單一連續(xù)分區(qū)的缺點(diǎn)是：一個(gè)作業(yè)運(yùn)行時(shí)要占用整個(gè)內(nèi)存的地址空間，即使很小的程序也是如此，對內(nèi)存造成了很大的浪費(fèi)，內(nèi)存的利用率很低。,4.2.2 固定分區(qū)分配 為了便于管理整個(gè)內(nèi)存，需建立一個(gè)表格來登記和管理整個(gè)內(nèi)存。在這個(gè)表中登記了每一個(gè)分區(qū)的大小，起始地址和分配狀態(tài)，如表4.1和圖4.8所示。當(dāng)有作業(yè)裝入時(shí)，系統(tǒng)便可以搜索這個(gè)表，找出一個(gè)大小合適的分區(qū)分配給它。當(dāng)程序運(yùn)行結(jié)束時(shí)，可以把它所占用的空間再釋放回去。地址重定位可以采用靜態(tài)地址定位或是動態(tài)地址定

15、位的方法。,表4.1 分區(qū)狀態(tài)表,圖4.8 固定分區(qū)的內(nèi)存分配情況,為了實(shí)現(xiàn)多道程序設(shè)計(jì)，可以按等待作業(yè)的類型設(shè)置多個(gè)等待隊(duì)列，也可以把所有的等待作業(yè)設(shè)置為一個(gè)等待隊(duì)列。如圖4.9所示為多道程序情況下固定分區(qū)的情況，左邊為多個(gè)等待隊(duì)列情況下的固定分區(qū)，右邊為單個(gè)等待隊(duì)列情況下的固定分區(qū)。,圖4.9 多道程序情況下的固定分區(qū)原理,固定分區(qū)的優(yōu)點(diǎn)是：與單一連續(xù)分配方法相比，固定分區(qū)法的內(nèi)存利用率提高了；可以支持多道程序；實(shí)現(xiàn)簡單，開銷小。 固定分區(qū)的缺點(diǎn)：必須預(yù)先能夠估計(jì)作業(yè)要占用多大的內(nèi)存空間，有時(shí)候這是難以做到的；區(qū)內(nèi)碎片造成浪費(fèi)；分區(qū)總數(shù)固定，限制了并發(fā)執(zhí)行的程序數(shù)目。,4.2.3 可變分區(qū)

16、 (動態(tài)分區(qū)分配) 1空閑存儲區(qū)表 若采用固定分區(qū)法，則作業(yè)運(yùn)行時(shí)所需內(nèi)存一般不會剛好等于某一個(gè)分區(qū)的大小，因此分區(qū)內(nèi)部的“內(nèi)零頭”被白白浪費(fèi)了；另一方面，固定分區(qū)的分區(qū)數(shù)在系統(tǒng)啟動以后不能任意改變，當(dāng)系統(tǒng)中運(yùn)行的作業(yè)數(shù)大于分區(qū)數(shù)時(shí)，就不可避免地會有一些作業(yè)分配不到分區(qū)，即使所有作業(yè)所需存儲空間總和小于內(nèi)存總和也不行。,可變分區(qū)存儲管理法并不預(yù)先將內(nèi)存劃分成分區(qū)，而是等到作業(yè)運(yùn)行需要內(nèi)存時(shí)才向系統(tǒng)申請，從空閑的內(nèi)存區(qū)中挖一塊出來，其大小等于作業(yè)所需內(nèi)存的大小，這樣就不會產(chǎn)生“內(nèi)零頭”。管理空閑內(nèi)存區(qū)的數(shù)據(jù)結(jié)構(gòu)可采用鏈接法和連續(xù)線性表格法。每一個(gè)空閑分區(qū)用一個(gè)map結(jié)構(gòu)管理： struct ma

17、p unsigned m_size; /空閑分區(qū)的長度 char * m_addr; /空閑分區(qū)的起始地址 ； struct map coremapN;,圖4.10所示為空閑分區(qū)表的初始狀態(tài)，圖4.11為某一時(shí)刻空閑分區(qū)表的狀態(tài)。圖中，m_size是空閑分區(qū)的長度，m_addr是空閑分區(qū)的起始地址。各個(gè)空閑分區(qū)按起始地址由低到高的順序登記在空閑存儲區(qū)表中，m_size為0的表項(xiàng)是空白表項(xiàng)，它們集中在表的后部。,圖4.10 空閑分區(qū)表的初始狀態(tài),圖4.11 某一時(shí)刻空閑分區(qū)表的狀態(tài),2分區(qū)分配算法 尋找某個(gè)空閑分區(qū)，其大小必須大于或等于程序的要求。若是大于要求，則將該分區(qū)分割成兩個(gè)分區(qū)，其中一個(gè)

18、分區(qū)為要求的大小并標(biāo)記為“占用”，而另一個(gè)分區(qū)為余下部分并標(biāo)記為“空閑”。分區(qū)的先后次序通常是從內(nèi)存低端到高端。 選擇分區(qū)的算法有四種：最先適應(yīng)算法、最佳適應(yīng)算法、最差適應(yīng)算法和循環(huán)最先適應(yīng)算法。,1) 最先適應(yīng)算法(first-fit) 最先適應(yīng)算法是將所有的空閑分區(qū)按照地址遞增的順序排列，然后按照分區(qū)的先后次序從頭開始查找，符合要求的第一個(gè)分區(qū)就是要找的分區(qū)。該算法的分配和釋放的時(shí)間性能較好，較大的空閑分區(qū)可以被保留在內(nèi)存高端。,(1) 分配算法： 當(dāng)為作業(yè)分配大小為size的空間時(shí)，總是從表的低地址部分開始查找，當(dāng)?shù)谝淮握业酱笥诘扔谏暾埓笮〉目臻g時(shí)，就按所需要的大小分配空間給作業(yè)，若分配

19、后還有剩余空間，就修改原來的m_size和m_addr，以記錄余下的零頭；如果作業(yè)所需要的空間剛好等于該空間的大小，那么該空間的m_size就為0；然后要?jiǎng)h除表中的這些空間，即將各個(gè)非零的表項(xiàng)上移。程序描述如下：,int *ffmalloc( mp , size ) struct map *mp; unsigned int size; register int regint; register struct map *bp; /從mp開始，只要size不等于0，逐個(gè)地址檢查 for(bp=mp; bp-m_size ; bp+ ) if ( bp-m_size = size ) /只要空間足夠

20、大,struct map unsigned m_size; char * m_addr; ；, regint = bp-m_addr ; /把老的起始地址保存到a bp-m_addr += size; /起始地址加size，把此塊一分為二 if ( bp-m_size -= size ) = 0 )/如果塊大小相同為0 do bp+; (bp-1)-m_addr = bp-m_addr ; while ( ( bp-1 )-m_size = bp-m_size );,return(regint ) ; return(0) ; ,(2) 釋放算法： 某一個(gè)作業(yè)釋放以前所分配到的內(nèi)存就是將該內(nèi)存區(qū)

21、歸還給操作系統(tǒng)，使其成為空閑區(qū)而可以被其他作業(yè)使用?；厥諘r(shí)如果釋放區(qū)與臨近的空閑區(qū)相連接，要將它們合并成較大的空閑區(qū)，否則空閑區(qū)將被分割得越來越小，最終導(dǎo)致不能利用。另外，空閑區(qū)個(gè)數(shù)越來越多，也會使得空閑區(qū)登記表溢出。,釋放算法分四種情況： 僅與前面一個(gè)空閑區(qū)相連，如圖4.12(a)所示。合并前空閑區(qū)和釋放區(qū)以構(gòu)成一塊大的新空閑區(qū)，并修改空閑區(qū)表項(xiàng)。 與前面空閑區(qū)和后面空閑區(qū)都相連，如圖4.12(b)所示。將三塊空閑區(qū)合并成一塊空閑區(qū)。, 僅僅與后空閑區(qū)相連，如圖4.12(c)所示。與后空閑區(qū)合并，使后空閑區(qū)表項(xiàng)的m_addr為釋放區(qū)的起始地址，m_size為釋放區(qū)與后空閑區(qū)的長度之和。 與前

22、后空閑區(qū)都不相連，如圖4.12(d)所示。在前、后空閑區(qū)表項(xiàng)中間插入一個(gè)新的表項(xiàng)，其m_addr為釋放區(qū)的起始地址，m_size為釋放區(qū)的長度。,圖4.12 釋放區(qū)與前后空閑區(qū)相鄰的情況,程序描述如下： mfree( unsigned size , char * StartAddr ) struct map *bp; char *addr, *taddr; unsigned TmpSize ; addr = StartAddr;,struct map unsigned m_size; char * m_addr; ；,for( bp = coremap ; bp-m_addr m_size !

23、= 0 ; bp + ) if ( bp coremap while ( bp-m_size ), bp + ; ( bp-1)-m_addr = bp-m_addr ; ( bp-1)-m_size = bp-m_size ; else if ( addr + size = bp-m_addr bp-m_size += size ; else if ( size ) do /單獨(dú)插入空閑分區(qū)表,而不與前后相連 taddr = bp-m_addr ; bp-m_addr = addr; addr = taddr; TmpSize = bp-m_size ;,bp-m_size = size ;

24、 bp + ; while ( size = TmpSize ); ,最先適應(yīng)算法的優(yōu)點(diǎn)：分配簡單而且合并相鄰的空閑區(qū)也比較容易，該算法的實(shí)質(zhì)是盡可能利用存儲區(qū)低地址的空閑區(qū)，而盡量在高地址部分保存較大的空閑區(qū)，以便一旦有分配大的空閑區(qū)的要求時(shí)，容易得到滿足。在釋放內(nèi)存分區(qū)時(shí)，如果有相鄰的空閑區(qū)就進(jìn)行合并，使其成為一個(gè)較大的空閑區(qū)。,最先適應(yīng)算法的缺點(diǎn)：由于查找總是從表首開始，前面的空閑區(qū)被分割得很小時(shí)，能滿足分配要求的可能性就較小，查找次數(shù)就較多。系統(tǒng)中作業(yè)越多，這個(gè)問題就越來越嚴(yán)重。針對這個(gè)問題，對最先適應(yīng)法稍加改進(jìn)，就有了循環(huán)最先適應(yīng)法。會產(chǎn)生碎片，這些碎片散布在存儲器的各處，不能集中使

25、用，因而降低了存儲器的利用率。,如圖4.13所示是某一個(gè)時(shí)刻J1、J2、J3、J4四個(gè)作業(yè)在內(nèi)存中的分配情況、空閑區(qū)表和已分配區(qū)表，它們的長度分別是15 KB、10 KB、12 KB、10 KB。J5和J6兩個(gè)新作業(yè)的長度分別為5 KB和13 KB，分配內(nèi)存后的內(nèi)存分配情況、空閑區(qū)表和已分配區(qū)表如圖4.14所示。,圖4.13 最先適應(yīng)算法分配前的狀態(tài),圖4.14 最先適應(yīng)算法分配后的狀態(tài),2) 循環(huán)最先適應(yīng)算法 (next-fit，下次適應(yīng)算法) 相對于最先適應(yīng)算法，下次適應(yīng)算法按分區(qū)的先后次序，從上次分配的分區(qū)開始查找，到最后分區(qū)時(shí)再回到開頭，符合要求的第一個(gè)分區(qū)就是找到的分區(qū)。,循環(huán)最先適

26、應(yīng)算法分配時(shí)總是從起始查找指針?biāo)赶虻谋眄?xiàng)開始，第一次找到滿足要求的空閑區(qū)時(shí)，就分配所需要的空閑區(qū)，然后修改表項(xiàng)，并調(diào)整起始查找指針，使其指向隊(duì)列中被分配的后面的那塊空閑區(qū)。 循環(huán)最先適應(yīng)法的實(shí)質(zhì)是起始查找指針?biāo)傅目臻e區(qū)和其后的空閑區(qū)群常為較長時(shí)間未被分割過的空閑區(qū)，它們已經(jīng)合并成為大的空閑區(qū)的可能性較大，與最先適應(yīng)算法相比，它在沒有增加多少代價(jià)的情況下卻明顯地提高了分配查找的速度。 循環(huán)最先適應(yīng)算法的釋放算法與最先適應(yīng)算法的基本相同。,3) 最佳適應(yīng)算法(best-fit) 最佳適應(yīng)算法的思想是將所有的空閑分區(qū)按照其容量遞增的順序排列，當(dāng)要求分配一個(gè)空白分區(qū)時(shí)，由小到大進(jìn)行查找。,最佳適應(yīng)

27、算法的空閑存儲區(qū)管理表的組織方法可以采用順序結(jié)構(gòu)，也可以采用鏈接結(jié)構(gòu)。 最佳適應(yīng)算法的優(yōu)點(diǎn)：由于算法是在所有大于或者等于要求分配長度的空閑區(qū)中挑選一個(gè)最小的分區(qū)，所以分配后所剩余的空白塊會最小。平均而言，只要查找一半的表格便能找到最佳適應(yīng)的空白區(qū)。如果有一個(gè)空白區(qū)的容量正好滿足要求，則它必被選中。,最佳適應(yīng)算法的缺點(diǎn)：由于空閑區(qū)是按大小而不是按地址的順序排列的，因此釋放時(shí)，要在整個(gè)鏈表上搜索地址相鄰的空閑區(qū)，合并后又要插入到合適的位置?？瞻讌^(qū)一般不可能恰好滿足要求，在分配之后的剩余部分通常非常小，以致小到無法使用。 其內(nèi)存分配前的狀態(tài)如圖4.13所示，J5和J6是兩個(gè)新作業(yè)，對它們分配內(nèi)存后的

28、內(nèi)存分配情況、空閑區(qū)表和已分配區(qū)表如圖4.15所示。,4) 最壞適應(yīng)算法(worst-fit) 最壞適應(yīng)算法的思想與最佳適應(yīng)算法相反，將所有的空白分區(qū)按容量遞減的順序排列，最前面的最大的空閑分區(qū)就是找到的分區(qū)。該算法是取所有空閑區(qū)中最大的一塊，把剩余的塊再變成一個(gè)新小一點(diǎn)的空閑區(qū)。算法基本不留下小空閑分區(qū)，但較大的空閑分區(qū)不會被保留。,最壞適應(yīng)算法的實(shí)現(xiàn)與前面的最佳適應(yīng)算法類似。 最壞適應(yīng)算法的優(yōu)點(diǎn)：分配的時(shí)候只需查找一次就可以成功，分配的算法很快。 最壞適應(yīng)算法的缺點(diǎn)：最后剩余的分區(qū)會越來越小，無法運(yùn)行大程序。 其內(nèi)存分配前的狀態(tài)如圖4.13所示，J5和J6是兩個(gè)新作業(yè)，對它們分配內(nèi)存后的內(nèi)

29、存分配情況、空閑區(qū)表和已分配區(qū)表如圖4.16所示。,圖4.15 最佳適應(yīng)算法分配后的狀態(tài),圖4.16 最差適應(yīng)算法分配后的狀態(tài),4.2.4 可再定位式分區(qū)(可重定位分區(qū)分配) 可再定位分區(qū)分配即浮動分區(qū)分配，是解決碎片問題的簡單而有效的辦法。其基本思想是移動所有被分配了的分區(qū)，使之成為一個(gè)連續(xù)區(qū)域，而留下一個(gè)較大的空白區(qū)。這好像在一個(gè)隊(duì)列中有些人出列以后，指揮員命令隊(duì)列向前(或向右)靠攏一樣。這種過程我們稱之為“靠攏”或“緊湊”，如圖4.17所示。,圖4.17 可再定位分區(qū)分配的靠攏過程,為解決程序浮動問題，可使用模塊裝入程序，將程序的裝配模塊重新裝入到指定位置，并從頭開始啟動執(zhí)行。但是這種辦

30、法有兩個(gè)缺點(diǎn)：一是要花費(fèi)較多的處理機(jī)時(shí)間；二是如果該程序已經(jīng)執(zhí)行了一段時(shí)間，則不能再從頭開始，否則將引起混亂。 較好的辦法是采用動態(tài)再定位技術(shù)。,4.2.5 伙伴系統(tǒng)（Buddy System） 伙伴系統(tǒng)提供了一個(gè)在固定大小和可變大小之間折衷的方案。內(nèi)存被劃分成大小為2的整次冪的單元，初始只有一個(gè)包含所有內(nèi)存的單元。當(dāng)要將內(nèi)存分配給進(jìn)程時(shí)，分配大于該進(jìn)程大小的最小2的整次冪單元。 例如，一個(gè)需50K內(nèi)存進(jìn)程要放入大小為64K的內(nèi)存單元。如果沒有這樣的內(nèi)存單元，大于該進(jìn)程需求的最小可利用空間被分成原來一半大小的“伙伴”單元，繼續(xù)分割其中一個(gè)伙伴單元，直到創(chuàng)建一個(gè)大小合適的分配單元位置。當(dāng)進(jìn)程釋放

31、內(nèi)存時(shí)，如果互成“伙伴”關(guān)系的兩個(gè)單元均被釋放，這兩個(gè)單元就結(jié)合成一個(gè)兩倍大小的單元。圖4.18說明了分配和釋放內(nèi)存時(shí)，是如何分割和連接分配單元的。 給定大小為2n，伙伴系統(tǒng)維持了一個(gè)最大長度為2n的空閑數(shù)據(jù)塊，每種大小的單元各有一個(gè)（假定內(nèi)存大小為28，則大小為28到21的分配單元都有可能得到）。由于有一個(gè)單獨(dú)的各種大小空閑塊，伙伴系統(tǒng)分配或釋放內(nèi)存效率較高。然而，由于存在內(nèi)部碎片和外部碎片，所以伙伴系統(tǒng)內(nèi)存利用率不高。,圖4.18 伙伴系統(tǒng),4.2.6 多重分區(qū) 可變分區(qū)雖然解決了多道程序運(yùn)行的情況，但是總是有碎片的問題，而且一個(gè)程序總是一定要放在一個(gè)分區(qū)中。為了解決這個(gè)問題，就引入了多重

32、分區(qū)的分配方案。 所謂多重分區(qū)，就是把一個(gè)程序放在多個(gè)分區(qū)中，這樣當(dāng)一個(gè)作業(yè)在一個(gè)分區(qū)中裝不下時(shí)，可以把它裝入到另外一個(gè)分區(qū)，依此類推。采用多重分區(qū)分配方案，可以使存儲空間的利用率得到提高，但是實(shí)現(xiàn)起來比較困難，所以這里不再贅述。,4.3 頁式存儲管理,4.3.1 基本原理 把作業(yè)的虛擬地址空間劃分成若干個(gè)長度相等的頁(pages)，也可以稱為“虛頁”，每一個(gè)程序的虛頁都從0開始編號。主存也劃分成若干個(gè)與虛頁長度相等的頁框(page frame)，也稱為頁面或?qū)嶍摗Ｔ陟o態(tài)頁式存儲管理系統(tǒng)中，作業(yè)加載時(shí)可以將任意一頁放入內(nèi)存中的任意一個(gè)頁框，而且這些頁框不必連續(xù)，從而實(shí)現(xiàn)了不連續(xù)分配。,但是要求

33、一個(gè)作業(yè)在運(yùn)行前將其所有的虛頁全部都裝入主存的塊中，當(dāng)然這就要求主存中有足夠多的空閑塊，否則程序便不能運(yùn)行。如圖4.18所示是分頁存儲管理的基本原理。,圖4.19 分頁存儲管理的基本原理,在分頁系統(tǒng)中，頁的大小往往都是2的整數(shù)次冪，因此在分頁系統(tǒng)中，地址的結(jié)構(gòu)由兩部分構(gòu)成：P(頁號)和D(頁內(nèi)偏移量)，如圖4.19所示。頁內(nèi)偏移量的值為02n-1。 P=INTA/L D=A mod L 注:A為邏輯地址,頁面大小為L,圖4.20 頁的劃分,對于分頁系統(tǒng)來說，程序在虛擬地址空間是連續(xù)的，但卻要映射到物理內(nèi)存中不連續(xù)的空閑frame中，所以需要系統(tǒng)在內(nèi)存中開辟一個(gè)頁表區(qū)來建立每一個(gè)作業(yè)的虛頁號到物

34、理內(nèi)存的frame號之間的映射關(guān)系，這個(gè)表格就叫做頁變換表(page management table)，也叫頁表。頁表中的內(nèi)容分為三部分：頁號、塊號和頁內(nèi)偏移量。 程序執(zhí)行的時(shí)候，對于每一條訪問內(nèi)存的指令，分頁系統(tǒng)的地址變化過程如圖4.20所示。,圖4.21 分頁式存儲管理的地址變換過程,過程說明： (1) 由硬件機(jī)構(gòu)自動將虛擬地址字分成虛頁號和頁內(nèi)偏移量兩個(gè)部分，虛頁號送給累加器，它和頁表起始地址之和就是所要查找的表項(xiàng)。 (2) 由頁表控制寄存器中的頁表起始地址和虛擬地址字中的虛頁號查找頁表，對應(yīng)的虛頁號的頁表地址為：頁表起始地址虛頁號頁表表項(xiàng)長度。 (3) 將頁表中取出的frame號和虛

35、擬地址字中的頁內(nèi)偏移量一起裝入到地址寄存器，根據(jù)地址寄存器中的地址值來訪問內(nèi)存。,4.3.2 頁式存儲管理的地址變換 1頁式管理的數(shù)據(jù)結(jié)構(gòu) 頁式存儲管理系統(tǒng)中，當(dāng)進(jìn)程建立時(shí)，操作系統(tǒng)為進(jìn)程中所有的頁分配頁塊。當(dāng)進(jìn)程撤消時(shí)需收回所有分配給它的物理頁塊。,為了完成上述功能，在一個(gè)頁式存儲管理系統(tǒng)中，一般要采用如下的數(shù)據(jù)結(jié)構(gòu)： (1) 進(jìn)程頁表：是邏輯頁號(本進(jìn)程的地址空間)到物理頁面號(實(shí)際內(nèi)存空間)的映射。 (2) 物理頁面表(空閑內(nèi)存頁表)：描述物理內(nèi)存空間的分配使用狀況。整個(gè)系統(tǒng)有一個(gè)物理頁面表。其數(shù)據(jù)結(jié)構(gòu)是位示圖(如圖4.22所示)和空閑頁面鏈表，用來記錄內(nèi)存中每個(gè)頁的使用情況和當(dāng)前空閑頁

36、的總數(shù)。,圖4.23 位示圖,(3) 請求表：描述系統(tǒng)內(nèi)各個(gè)進(jìn)程頁表的位置和大小，用于地址轉(zhuǎn)換，也可以結(jié)合到各進(jìn)程的PCB里。整個(gè)系統(tǒng)有一個(gè)請求表。,2. 地址變換機(jī)構(gòu) 前面已經(jīng)指出，在頁式存儲系統(tǒng)中，指令所給出的地址分為兩部分：邏輯頁號和頁內(nèi)偏移量。CPU中的內(nèi)存管理單元(MMU)按邏輯頁號通過查進(jìn)程頁表得到物理頁框號，將物理頁框號與頁內(nèi)偏移量相加即可形成物理地址，如圖4.23所示。,程序裝入后執(zhí)行時(shí)，應(yīng)該需要內(nèi)存管理單元(Memory Management Unit，MMU)的支持，根據(jù)進(jìn)程頁表進(jìn)行執(zhí)行時(shí)的動態(tài)地址映射和保護(hù)。映射的過程如上所述。MMU的位置和功能如圖4.24所示。,圖4.

37、24 MMU的位置和功能,MMU是Memory Management Unit的縮寫，中文名是存儲器管理單元，它是中央處理器（CPU）中用來管理虛擬存儲器、物理存儲器的控制線路，同時(shí)也負(fù)責(zé)虛擬地址映射為物理地址，以及提供硬件機(jī)制的內(nèi)存訪問授權(quán)。,圖4.25 頁式地址變換,頁面變換（頁表建立）的過程是：先要得到進(jìn)程所需要的頁數(shù)，參照空閑內(nèi)存頁表，看是否有這么多的空閑頁，如果有，則將N個(gè)頁面分配給這個(gè)進(jìn)程，并修改空閑內(nèi)存頁表，將程序一次性全部裝入用戶區(qū)內(nèi)存，同時(shí)建立起這個(gè)進(jìn)程的進(jìn)程頁表，也就是頁面變換表。如果沒有N個(gè)空閑頁面，則被拒絕或者排隊(duì)等待。,4.3.3 硬件支持 從上面的介紹可以看出，每訪

38、問一次指令或者數(shù)據(jù)，至少需要訪問兩次內(nèi)存，第一次是查找頁表，第二次才是真正訪問指令或者數(shù)據(jù)。為了加快頁式存儲管理的速度，往往也需要硬件支持，主要是頁表基址寄存器、頁表長度寄存器和關(guān)聯(lián)存儲器等一些寄存器。,1系統(tǒng)設(shè)置一對寄存器 (1) 頁表基址寄存器(Page Table Base Register，PTBR) 用戶程序在執(zhí)行過程中每次訪問內(nèi)存時(shí)(即每次地址映射時(shí))，MMU需要根據(jù)當(dāng)前進(jìn)程的進(jìn)程頁表基址寄存器值和此次地址映射的邏輯頁號，訪問當(dāng)前進(jìn)程的進(jìn)程頁表(在內(nèi)存)，得到此次地址映射的物理頁號，再根據(jù)邏輯地址中頁內(nèi)偏移量得到真正的物理地址。在進(jìn)程切換時(shí)頁表基址寄存器的內(nèi)容才被保存和恢復(fù)，其內(nèi)容

39、是當(dāng)前進(jìn)程的進(jìn)程頁表的內(nèi)存起始地址。頁表基址寄存器的工作原理如圖4.26所示。,圖4.26 進(jìn)程頁表基址寄存器的工作原理,由圖4.24可以看出以下4點(diǎn)： 每次進(jìn)程切換時(shí)不用保存和恢復(fù)當(dāng)前新老進(jìn)程的整個(gè)進(jìn)程頁表，只需保存和恢復(fù)PTBR。 進(jìn)程頁表是由硬件訪問的，這意味著進(jìn)程頁表的格式是由硬件規(guī)定的。 對進(jìn)程頁表的訪問是直接存取。 用戶程序執(zhí)行時(shí)的每次內(nèi)存訪問，都至少訪問內(nèi)存兩次，第一次訪問進(jìn)程頁表，第二次才是訪問此次要訪問的頁本身，這意味著用戶程序的執(zhí)行時(shí)間將增加一倍。,(2) 頁表長度寄存器 為了實(shí)現(xiàn)存儲保護(hù)，在頁表基址寄存器的基礎(chǔ)上，還需要一個(gè)頁表長度寄存器，它用來存放當(dāng)前進(jìn)程頁表的長度。在

40、每次訪問內(nèi)存之前，先檢查所取得指令的地址是否超過了進(jìn)程頁表的長度。如果在范圍之內(nèi)，則正常訪問內(nèi)存；如果在長度范圍之外，則拒絕此次訪問。,直接采用上述機(jī)構(gòu)進(jìn)行地址變換實(shí)際上是不可取的。由于頁表是駐留在內(nèi)存中的，為了進(jìn)行地址變換，對于每一條訪問內(nèi)存的指令，系統(tǒng)至少要訪問內(nèi)存兩次，這樣程序執(zhí)行的速度只能是原來的1/2。,2關(guān)聯(lián)存儲器快表 為縮短查找時(shí)間，可以將頁表裝入到關(guān)聯(lián)存儲器，按內(nèi)容查找邏輯頁號到物理頁號的映射。很多頁式系統(tǒng)都有一組關(guān)聯(lián)存儲器(Translation Lookaside Buffer，TLB)，用來存放當(dāng)前運(yùn)行作業(yè)的頁表表項(xiàng)，以加速地址變換過程，這種頁表稱為快表，它是介于內(nèi)存與寄

41、存器之間的存儲機(jī)制。內(nèi)存中的頁表有時(shí)也稱為慢表。利用快表進(jìn)行地址變換的過程如圖4.25所示。,圖4.27 利用快表進(jìn)行地址變換的過程,頁表,兩級和多級頁表,兩級頁表 解決大頁表占用大的連續(xù)存儲空間的問題； 關(guān)于“頁表”的分頁存放“頁表”外層頁表(頁目錄)； 邏輯地址： 外層頁號+外層頁內(nèi)地址+頁內(nèi)地址 多級頁表,頁框?yàn)?K; 頁目錄項(xiàng)(4Byte)用來尋址一個(gè)頁表；頁表項(xiàng)(4Byte)用來指定一個(gè)物理內(nèi)存頁面。圖中二級目錄的尋址空間范圍是?,該頁目錄表尋址的所有頁表共可以尋址1024*1024*4096=4G 內(nèi)存空間。,4.28 地址變換示意圖 (CPU的寄存器CR3用來確定當(dāng)前頁目錄的物理

42、地址),4.29 頁目錄和頁表表項(xiàng)結(jié)構(gòu),每個(gè)表項(xiàng)由頁框地址、訪問標(biāo)志位、臟（已改寫）標(biāo)志位和存在標(biāo)志位等構(gòu)成。,4.3.5 優(yōu)缺點(diǎn) 分頁式存儲管理的優(yōu)點(diǎn)： (1) 沒有外碎片，每個(gè)內(nèi)碎片不超過頁的大小。 (2) 一個(gè)程序不必連續(xù)存放。 (3)便于改變程序占用空間的大小(主要指隨著程序運(yùn)行而動態(tài)生成的數(shù)據(jù)增多，要求地址空間相應(yīng)增長，通常由系統(tǒng)調(diào)用完成而不是操作系統(tǒng)自動完成)。,分頁式存儲管理的缺點(diǎn)： (1) 程序要全部裝入內(nèi)存。 (2) 采用動態(tài)地址變換機(jī)構(gòu)會增加計(jì)算機(jī)的成本和降低處理機(jī)的速度。 (3) 各種表格要占用一定的內(nèi)存空間，而且要花費(fèi)一定的時(shí)間來建立和管理這些表格。 (4) 存儲擴(kuò)充問

43、題沒有得到解決。 (5) 不易實(shí)現(xiàn)共享。 (6) 不便于動態(tài)連接。,4.4 段式存儲管理,通常，一個(gè)作業(yè)是由若干個(gè)自然段組成的。因而，用戶希望能把自己的作業(yè)按照邏輯關(guān)系劃分為若干個(gè)段，每個(gè)段都有自己的名字和長度。要訪問的邏輯地址是由段名(段號)和段內(nèi)偏移量(段內(nèi)地址)決定的，每個(gè)段都從0開始編址。這樣，用戶程序在執(zhí)行中可用段名和段內(nèi)地址進(jìn)行訪問。例如，下述的兩條指令便是使用的段名和段內(nèi)地址。,LOAD L，A|(D) STORE I，B|(C) 其中，前一條指令的含義是將分段A中D單元內(nèi)的值讀入寄存器L；后一條指令的含義是將寄存器I的內(nèi)容存入分段B中的C單元內(nèi)。,段式存儲管理(simple s

44、egmentation)可以實(shí)現(xiàn)共享。通常，在實(shí)現(xiàn)程序和數(shù)據(jù)的共享時(shí)，都是以信息的邏輯單位為基礎(chǔ)的，比如共享某個(gè)例程和函數(shù)。 段式存儲管理可以實(shí)現(xiàn)分段保護(hù)。在多道程序環(huán)境下，為了防止其他程序?qū)δ吵绦蛟趦?nèi)存中的數(shù)據(jù)有意無意的破壞，必須采取保護(hù)措施。 段式存儲管理可以實(shí)現(xiàn)動態(tài)鏈接。 段式存儲管理使得段可以動態(tài)增長。,4.4.1 基本思想 在頁式存儲管理思想中，作業(yè)的地址空間是連續(xù)的一維地址空間，程序的各個(gè)目標(biāo)模塊都由鏈接程序裝配成一個(gè)可執(zhí)行的程序后裝入內(nèi)存執(zhí)行。,我們根據(jù)程序的模塊結(jié)構(gòu)，把作業(yè)地址空間劃分為大小不同的一些塊，我們把這些大小不同的塊叫做段。每個(gè)程序段都有一個(gè)段名，且有一個(gè)段號。段號從

45、0開始，每一段也從0開始編址，段內(nèi)地址是連續(xù)的，通常分為主程序段、子程序段、庫函數(shù)段和數(shù)據(jù)段等等。同時(shí)在物理內(nèi)存中，也分成一些和這些塊一樣大的塊。分段的基本原理如圖4.26所示。,圖4.26 分段的基本原理,作業(yè)在裝入的時(shí)候是一次性全部裝入的，如果不是一次性裝入，就叫做請求分段式的管理。 將程序的地址空間劃分為若干個(gè)段(segment)，程序加載時(shí)，為每個(gè)段分配其所需的一個(gè)連續(xù)內(nèi)存分區(qū)，而進(jìn)程中的各個(gè)段可以不連續(xù)地存放在內(nèi)存的不同分區(qū)中。 物理內(nèi)存的管理采用動態(tài)分區(qū)的思想，即在為某個(gè)段分配物理內(nèi)存時(shí)，可以采用最先適應(yīng)法、下次適應(yīng)法和最佳適應(yīng)等方法。,在收回某個(gè)段所占用的空間時(shí)，要注意將收回的空

46、間與其相鄰的空間合并。分段式存儲管理也需要硬件支持，以實(shí)現(xiàn)邏輯地址到物理地址的映射。分段式存儲管理的基本原理如圖4.27所示。,圖4.27 分段式存儲管理的基本原理,在分段式存儲管理的思想中，程序通過分段(segmentation)劃分為多個(gè)模塊，如代碼段、數(shù)據(jù)段、共享段，其優(yōu)點(diǎn)是可以分別進(jìn)行編寫和編譯；可以針對不同類型的段采取不同的保護(hù)；可以以段為單位來進(jìn)行共享，包括通過動態(tài)鏈接進(jìn)行代碼共享。 在分段存儲管理系統(tǒng)中，作業(yè)地址空間的每一個(gè)單元均采用二維地址(S，W)，其中，S為段號，W為段內(nèi)地址或者偏移量，如圖4.28所示。,圖4.28 進(jìn)程段地址,4.4.2 分段式管理的數(shù)據(jù)結(jié)構(gòu) (1) 進(jìn)

47、程段表：也叫段變換表(SMT)，如圖4.29所示。它描述組成進(jìn)程地址空間的各段。它可以是指向系統(tǒng)段表中表項(xiàng)的索引，每段都有段基址(base address)。 (2) 系統(tǒng)段表：描述系統(tǒng)所有占用的段。 (3) 空閑段表：描述了內(nèi)存中所有空閑段，可以結(jié)合到系統(tǒng)段表中。內(nèi)存的分配算法可以采用最先適應(yīng)法、最佳適應(yīng)法和最壞適應(yīng)法。,圖4.29 段式地址變換,4.4.3 分段式管理的地址變換 為了實(shí)現(xiàn)從邏輯地址到物理地址的變換功能，在系統(tǒng)中設(shè)置了段表基址寄存器和段表長度寄存器。在進(jìn)行地址變換時(shí)，系統(tǒng)將邏輯地址中的段號S與段表長度STL進(jìn)行比較。若SSTL，表示段號太大，則越界訪問，產(chǎn)生越界中斷；若未越界

48、，則根據(jù)段表的起始地址和該段的段號，計(jì)算出該段對應(yīng)段表項(xiàng)的位置，從中讀出該段在內(nèi)存的起始地址，然后再檢查段內(nèi)地址D是否超過該段的段長SL。若DSL，同樣發(fā)出越界中斷；若未越界，則將該段的基址D與段內(nèi)地址相加，即得到要訪問的內(nèi)存物理地址。,和分頁式存儲管理系統(tǒng)一樣，當(dāng)段表放在內(nèi)存中時(shí)，分段式每訪問一個(gè)數(shù)據(jù)或者指令，都需至少訪問內(nèi)存兩次，從而成倍地降低了計(jì)算機(jī)的速率。解決的辦法和分頁存儲管理的思想類似，即再增設(shè)一個(gè)關(guān)聯(lián)寄存器，用于保存最近常用的段表項(xiàng)。由于一般情況下段比頁大，因而段表項(xiàng)的數(shù)目比頁表數(shù)目少，其所需的關(guān)聯(lián)寄存器也相對較小，可以顯著地減少存取數(shù)據(jù)的時(shí)間。,4.4.4 分段式管理的硬件支持

49、 如上面所述，和分頁式存儲管理的思想類似，也可以設(shè)置一對寄存器：段表基址寄存器和段表長度寄存器。段表基址寄存器用于保存正在運(yùn)行進(jìn)程的段表的基址，而段表長度寄存器用于保存正在運(yùn)行進(jìn)程的段表的長度。,同樣，和分頁式存儲管理的思想類似，也可以設(shè)置聯(lián)想存儲器，它是介于內(nèi)存與寄存器之間的存儲機(jī)制，和分頁式存儲管理系統(tǒng)一樣也叫快表。它的用途是保存正在運(yùn)行進(jìn)程的段表的子集(部分表項(xiàng))，其特點(diǎn)是可按內(nèi)容并行查找。引入快表的作用是為了提高地址映射速度，實(shí)現(xiàn)段的共享和段的保護(hù)。快表中的項(xiàng)目包括：段號、段基址、段長度、標(biāo)識(狀態(tài))位、訪問位和淘汰位。,4.4.5 分段式管理的優(yōu)缺點(diǎn) 分段式存儲管理的優(yōu)點(diǎn)：沒有內(nèi)碎片

50、，外碎片可以通過內(nèi)存緊湊來消除；便于改變進(jìn)程占用空間的大??；便于實(shí)現(xiàn)共享和保護(hù)，即允許若干個(gè)進(jìn)程共享一個(gè)或者多個(gè)段，對段進(jìn)行保護(hù)。如圖4.30所示是分段系統(tǒng)中共享一個(gè)compiler編譯器程序的例子。 分段式存儲管理的缺點(diǎn)：作業(yè)需要全部裝入內(nèi)存，不能實(shí)現(xiàn)存儲擴(kuò)充。,圖4.30 分段系統(tǒng)中共享compilor的示意圖,4.4.6 分頁式管理和分段式管理的比較 (1) 分頁是出于系統(tǒng)管理的需要，分段是出于用戶應(yīng)用的需要。 (2) 頁的大小是系統(tǒng)固定的，而段的大小則通常不固定。 (3) 邏輯地址表示：分頁是一維的，各個(gè)模塊在鏈接時(shí)必須組織在同一個(gè)地址空間；而分段是二維的，各個(gè)模塊在鏈接時(shí)可以把每個(gè)段

51、組織成一個(gè)地址空間。 (4) 通常段比頁大，因而段表比頁表短，可以縮短查找時(shí)間，提高訪問速度。 (5) 分段式存儲管理可以實(shí)現(xiàn)內(nèi)存共享，而分頁式存儲管理則不能實(shí)現(xiàn)內(nèi)存共享。但是兩者都不能實(shí)現(xiàn)存儲擴(kuò)充。 分頁式管理和分段式管理的比較如圖4.31所示。,圖4.31 頁式管理與段式管理的比較,4.5 段頁式存儲管理,4.4.1 基本思想 段頁式存儲管理是對虛擬頁式和虛擬段式存儲管理的結(jié)合，這種思想結(jié)合了二者的優(yōu)點(diǎn)，克服了二者的缺點(diǎn)。這種思想將用戶程序分為若干個(gè)段，再把每個(gè)段劃分成若干個(gè)頁，并為每一個(gè)段賦予一個(gè)段名。,也就是說將用戶程序按段式劃分，而將物理內(nèi)存按頁式劃分，即以頁為單位進(jìn)行分配。換句話來

52、說，段頁式管理對用戶來講是按段的邏輯關(guān)系進(jìn)行劃分的，而對系統(tǒng)來講是按頁劃分每一段的。在段頁式存儲管理中，其地址結(jié)構(gòu)由段號、段內(nèi)頁號和頁內(nèi)地址三部分組成，如圖4.32所示。,圖4.32 段頁式存儲管理的地址結(jié)構(gòu),在段頁式存儲管理中，為了實(shí)現(xiàn)從邏輯地址到物理地址的變換，系統(tǒng)中需要同時(shí)配置段表和頁表。由于允許將一個(gè)段中的頁進(jìn)行不連續(xù)分配，因而使段表的內(nèi)容有所變化：它不再是段內(nèi)起始地址和段長，而是頁表起始地址和頁表長度。如圖4.33所示是段頁式存儲管理中利用段表和頁表進(jìn)行邏輯地址到物理地址的映射過程。,圖4.33 段頁式存儲管理的地址映射,4.4.2 段頁式存儲管理的地址變換 如圖4.33所示，為了實(shí)

53、現(xiàn)段頁式存儲管理的機(jī)制，需要在系統(tǒng)中設(shè)置以下幾個(gè)數(shù)據(jù)結(jié)構(gòu)： (1) 段表：記錄每一段的頁表起始地址和頁表長度。 (2) 頁表：記錄每一個(gè)段所對應(yīng)的邏輯頁號與內(nèi)存塊號的對應(yīng)關(guān)系，每一段有一個(gè)頁表，而一個(gè)程序可能有多個(gè)頁表。 (3) 空閑內(nèi)存頁表：其結(jié)構(gòu)同分頁式存儲管理，因?yàn)榭臻e內(nèi)存采用分頁式的存儲管理。 (4) 物理內(nèi)存分配：同分頁式存儲管理。,4.4.3 硬件支持 在段頁式系統(tǒng)中，為了便于實(shí)現(xiàn)地址變換，必須配置一個(gè)段表基址寄存器(在其中存放段表起始地址)和一個(gè)段表長度寄存器(在其中存放段長SL)。進(jìn)行地址變換時(shí)，首先利用段號S，將它與段長SL進(jìn)行比較。若SSL，表示沒有越界，于是利用段表起始地

54、址和段號求出該段對應(yīng)的段表項(xiàng)在段表中的位置，從中得到該段的頁表起始地址，并利用邏輯地址中的段內(nèi)頁號P來獲得對應(yīng)的頁表項(xiàng)位置，從中讀出該頁所在的物理塊號B，再用塊號B和頁內(nèi)地址構(gòu)成物理地址。如圖4.34所示為段頁式存儲管理中的地址變換結(jié)構(gòu)。,圖4.34 段頁式存儲管理的地址變換機(jī)構(gòu),在段頁式存儲管理中，為了獲得一條指令或者數(shù)據(jù)，至少需要三次訪問內(nèi)存：第一次訪問是訪問內(nèi)存中的段表；第二次訪問是訪問內(nèi)存中的頁表，從中取出該頁所在的物理塊號，并將該塊號與頁內(nèi)地址一起形成指令或者數(shù)據(jù)的物理地址；第三次訪問才是真正從第二次訪問所得到的地址中取出指令或者數(shù)據(jù)。,4.6 交換技術(shù)與覆蓋技術(shù),4.6.1 覆蓋技

55、術(shù) 覆蓋(overlay)技術(shù)的目標(biāo)是在較小的可用內(nèi)存中運(yùn)行較大的程序，常用于多道程序系統(tǒng)，與分區(qū)存儲管理配合使用。 覆蓋技術(shù)不需要任何來自操作系統(tǒng)的特殊支持，可以完全由用戶實(shí)現(xiàn)，即overlay，是用戶程序自己附加的控制。,1覆蓋技術(shù)的原理 通常一個(gè)程序的幾個(gè)代碼段或數(shù)據(jù)段是按照時(shí)間先后來占用公共的內(nèi)存空間的，它們裝入時(shí)可以采用如下幾種： (1) 將程序的必要部分(常用功能)的代碼和數(shù)據(jù)常駐內(nèi)存。 (2) 將可選部分(不常用功能)在其他程序模塊中實(shí)現(xiàn)，平時(shí)存放在外存中的覆蓋文件中，在用到時(shí)才裝入到內(nèi)存。,(3) 不存在調(diào)用關(guān)系的模塊不必同時(shí)裝入到內(nèi)存，從而可以相互覆蓋。 覆蓋技術(shù)的原理如圖4

56、.35所示。,圖4.35 覆蓋技術(shù)原理,2覆蓋技術(shù)的優(yōu)缺點(diǎn) 覆蓋技術(shù)使一個(gè)作業(yè)能夠有效地利用內(nèi)存，但是它有如下的缺點(diǎn)：編程時(shí)必須劃分程序模塊和確定程序模塊之間的覆蓋關(guān)系，增加了編程復(fù)雜度；從外存裝入覆蓋文件，是以時(shí)間延長來換取空間節(jié)省的；各個(gè)作業(yè)占用的分區(qū)仍然存在著碎片。,4.6.2 交換技術(shù) 交換技術(shù)(swapping)最早應(yīng)用于麻省理工學(xué)院的兼容分時(shí)系統(tǒng)CTSS中。 交換技術(shù)用于多個(gè)程序并發(fā)執(zhí)行的系統(tǒng)中。當(dāng)某一個(gè)作業(yè)的存儲空間不夠時(shí)，可以將暫時(shí)不能執(zhí)行的程序所占用的地址空間換出到外存中，從而獲得空閑內(nèi)存空間來裝入新程序，或讀入保存在外存中而目前處于就緒狀態(tài)的程序。交換單位為整個(gè)進(jìn)程的地址空

57、間。交換技術(shù)常用于多道程序系統(tǒng)或小型分時(shí)系統(tǒng)中，可與分區(qū)存儲管理配合使用。它又稱作“對換”或“滾進(jìn)/滾出(roll-in/roll-out)”。,程序暫時(shí)不能執(zhí)行的可能原因是：處于阻塞狀態(tài)，低優(yōu)先級(確保高優(yōu)先級程序先執(zhí)行)。其處理方法同上。 如果將簡單的交換技術(shù)加以發(fā)展，就可用于固定分區(qū)或者可變分區(qū)的存儲管理技術(shù)中。在采用可變分區(qū)存儲管理的多道程序設(shè)計(jì)中，當(dāng)要運(yùn)行一個(gè)高優(yōu)先級的作業(yè)而又沒有足夠的空閑內(nèi)存時(shí)，可以按某一個(gè)算法從主存中換出一個(gè)或多個(gè)作業(yè)，騰出空間裝入高優(yōu)先級的作業(yè)，使之能夠運(yùn)行。在Windows操作系統(tǒng)中，就是利用交換技術(shù)運(yùn)行多個(gè)任務(wù)的。,交換技術(shù)的優(yōu)點(diǎn)：增加并發(fā)運(yùn)行的程序數(shù)目，

58、并且給用戶提供適當(dāng)?shù)捻憫?yīng)時(shí)間；編寫程序時(shí)不影響程序結(jié)構(gòu)。 交換技術(shù)的缺點(diǎn)：對換入和換出的控制增加了處理機(jī)開銷；程序整個(gè)地址空間都進(jìn)行傳送，沒有考慮執(zhí)行過程中地址訪問的統(tǒng)計(jì)特性。還存在兩個(gè)問題：程序換入時(shí)的重定位問題；交換過程中傳送的信息量特別大的問題。,4.7 虛 擬 存 儲,4.7.1 虛擬存儲管理的引入 虛擬存儲(virtual memory)管理的基礎(chǔ)是程序的局部性原理(principle of locality)。所謂局部性原理，是指程序在執(zhí)行過程中的一個(gè)較短時(shí)期內(nèi)，所執(zhí)行的指令地址和指令的操作數(shù)地址分別局限于一定的區(qū)域，主要表現(xiàn)為：,(1) 時(shí)間局部性：指一條指令的一次執(zhí)行和下次執(zhí)行，一個(gè)數(shù)據(jù)的一次訪問和下次訪問都集中在一個(gè)較短時(shí)期內(nèi)。 (2) 空間局部性：指當(dāng)前指令和鄰近的幾條指令，當(dāng)前訪問的