第4章存儲管理

1、第第4 4章章 存儲管理存儲管理 第第4章章 存儲管理存儲管理 4.1 概述概述 4.2 分區(qū)存儲管理方案分區(qū)存儲管理方案 4.3 頁式存儲管理頁式存儲管理 4.4 段式存儲管理段式存儲管理 4.5 段頁式存儲管理段頁式存儲管理 4.6 交換技術(shù)與覆蓋技術(shù)交換技術(shù)與覆蓋技術(shù) 4.7 虛擬存儲虛擬存儲 4.8 高速緩沖存儲器高速緩沖存儲器 4.9 內(nèi)存管理實例分析內(nèi)存管理實例分析習(xí)題習(xí)題 第第4 4章章 存儲管理存儲管理 4.1 概概 述述 存儲器是計算機(jī)系統(tǒng)中的重要組成部分，隨著計存儲器是計算機(jī)系統(tǒng)中的重要組成部分，隨著計算機(jī)技術(shù)的飛速發(fā)展和內(nèi)存價格的降低，現(xiàn)代計算機(jī)算機(jī)技術(shù)的飛速發(fā)展和內(nèi)存價

2、格的降低，現(xiàn)代計算機(jī)中的內(nèi)存也在不斷增加，已經(jīng)達(dá)到中的內(nèi)存也在不斷增加，已經(jīng)達(dá)到GB的范圍。的范圍。 第第4 4章章 存儲管理存儲管理 4.1.1 存儲體系存儲體系 存儲器的功能是保存指令和數(shù)據(jù)，它的發(fā)展方向是存儲器的功能是保存指令和數(shù)據(jù)，它的發(fā)展方向是高速、大容量和小體積，諸如內(nèi)存在訪問速度方面的高速、大容量和小體積，諸如內(nèi)存在訪問速度方面的發(fā)展有發(fā)展有DRAM、SDRAM、SRAM等技術(shù)；而磁盤技等技術(shù)；而磁盤技術(shù)的發(fā)展方向主要在大容量方面，比如接口標(biāo)準(zhǔn)、存術(shù)的發(fā)展方向主要在大容量方面，比如接口標(biāo)準(zhǔn)、存儲密度等。儲密度等。第第4 4章章 存儲管理存儲管理 存儲組織的功能是在存儲存儲組織的功

3、能是在存儲技術(shù)和技術(shù)和CPU尋址技術(shù)許可的范圍尋址技術(shù)許可的范圍內(nèi)組織合理的存儲結(jié)構(gòu)，其依據(jù)內(nèi)組織合理的存儲結(jié)構(gòu)，其依據(jù)是訪問速度的匹配關(guān)系、容量要是訪問速度的匹配關(guān)系、容量要求和價格。常見的存儲結(jié)構(gòu)有兩求和價格。常見的存儲結(jié)構(gòu)有兩種：種：“寄存器寄存器內(nèi)存內(nèi)存外存外存”結(jié)構(gòu)和結(jié)構(gòu)和“寄存器寄存器快速緩存快速緩存內(nèi)內(nèi)存存外存外存”結(jié)構(gòu)。結(jié)構(gòu)。 圖圖4.1所示的是所示的是“寄存器寄存器快快速緩存速緩存內(nèi)存內(nèi)存外存外存”結(jié)構(gòu)。結(jié)構(gòu)。外存(secondary storage)快速緩存(cache)寄存器(register)內(nèi)存(primary storage)圖4.1 存儲層次結(jié)構(gòu)第第4 4章章 存

4、儲管理存儲管理 從源程序到程序執(zhí)行從源程序到程序執(zhí)行編譯：編譯程序編譯：編譯程序 由編譯程序由編譯程序（Compiler）將用戶源代碼編譯成若干）將用戶源代碼編譯成若干個目標(biāo)模塊。個目標(biāo)模塊。鏈接：鏈接程序鏈接：鏈接程序 由鏈接程序（由鏈接程序（Linker）將編譯后形成的一組目標(biāo)模）將編譯后形成的一組目標(biāo)模塊，以及它們所需要的庫函數(shù)鏈接在一起，形成裝塊，以及它們所需要的庫函數(shù)鏈接在一起，形成裝入模塊。入模塊。裝入：裝入程序裝入：裝入程序 由裝入程序由裝入程序（Loader）將裝入模塊復(fù)制到內(nèi)存中。）將裝入模塊復(fù)制到內(nèi)存中。庫匯編編譯主子1子2目標(biāo)模塊鏈接程序裝入模塊庫主子1子2裝入程序內(nèi)存庫

5、主子1子2第第4 4章章 存儲管理存儲管理 地址空間的概念地址空間的概念物理（絕對）地址物理（絕對）地址程序執(zhí)行程序執(zhí)行 每個內(nèi)存單元的固定順序地址（編號）。每個內(nèi)存單元的固定順序地址（編號）。邏輯（相對）地址邏輯（相對）地址裝入（匯編編譯）裝入（匯編編譯） 被鏈接裝配（或匯編、編譯）后的目標(biāo)模塊被鏈接裝配（或匯編、編譯）后的目標(biāo)模塊所限定的地址的集合；所限定的地址的集合； 相對于某個基準(zhǔn)量（通常為：相對于某個基準(zhǔn)量（通常為：0）的編址。）的編址。物理地址 內(nèi)存000000000100002.0100001FFF主子1子2主子1子2邏輯地址 裝入模塊000.FFF主子1子2相對地址源程序/單個

6、目標(biāo)模塊0005FF0005FF0003FF第第4 4章章 存儲管理存儲管理 4.1.2 地址重定位地址重定位 可執(zhí)行文件的建立過程是：源程序可執(zhí)行文件的建立過程是：源程序編譯編譯目標(biāo)目標(biāo)模塊模塊(多個目標(biāo)模塊或程序庫多個目標(biāo)模塊或程序庫) 鏈接鏈接可執(zhí)行文件?？蓤?zhí)行文件。當(dāng)程序執(zhí)行時由操作系統(tǒng)裝入內(nèi)存而成為進(jìn)程。當(dāng)程序執(zhí)行時由操作系統(tǒng)裝入內(nèi)存而成為進(jìn)程。 對程序員來說，數(shù)據(jù)的存放地址是由符號決定的，對程序員來說，數(shù)據(jù)的存放地址是由符號決定的，故稱為符號名地址，或者稱為名地址。故稱為符號名地址，或者稱為名地址。 第第4 4章章 存儲管理存儲管理 當(dāng)程序被裝入內(nèi)存時，程序的邏輯地址被轉(zhuǎn)換成內(nèi)存的

7、物理當(dāng)程序被裝入內(nèi)存時，程序的邏輯地址被轉(zhuǎn)換成內(nèi)存的物理地址，稱為地址，稱為地址重定位地址重定位。 在可執(zhí)行文件裝入時需要解決可執(zhí)行文件中地址在可執(zhí)行文件裝入時需要解決可執(zhí)行文件中地址(指令和數(shù)指令和數(shù)據(jù)據(jù))和內(nèi)存地址的對應(yīng)問題。這是由操作系統(tǒng)中的裝入程序和內(nèi)存地址的對應(yīng)問題。這是由操作系統(tǒng)中的裝入程序Loader來完成的，如圖來完成的，如圖4.2所示。所示。圖4.2 地址重定位Load A datal源程序編譯鏈接0100BA1000datal 34562003456Load A datal邏輯地址空間地址映射Load A datal3456物理地址空間12001000第第4 4章章 存儲管

8、理存儲管理 1絕對裝入絕對裝入(absolute loading) 在可執(zhí)行文件中記錄內(nèi)存地址，裝入時直接定位在可執(zhí)行文件中記錄內(nèi)存地址，裝入時直接定位于上述內(nèi)存地址的方式稱為絕對裝入于上述內(nèi)存地址的方式稱為絕對裝入(或者稱為固定地或者稱為固定地址再定位址再定位)。 在這種方式下，程序的地址再定位是在執(zhí)行之前在這種方式下，程序的地址再定位是在執(zhí)行之前被確定的，也就是在編譯、鏈接時直接制定程序在執(zhí)被確定的，也就是在編譯、鏈接時直接制定程序在執(zhí)行時訪問的實際存儲器地址。這樣，程序的地址空間行時訪問的實際存儲器地址。這樣，程序的地址空間和內(nèi)存地址空間是一一對應(yīng)的。單片機(jī)或者單用戶系和內(nèi)存地址空間是一

9、一對應(yīng)的。單片機(jī)或者單用戶系統(tǒng)常采用這種方式。統(tǒng)常采用這種方式。 固定地址再定位的優(yōu)點是裝入過程簡單；缺點是固定地址再定位的優(yōu)點是裝入過程簡單；缺點是過于依賴于硬件結(jié)構(gòu)，不適合多道程序系統(tǒng)。過于依賴于硬件結(jié)構(gòu)，不適合多道程序系統(tǒng)。第第4 4章章 存儲管理存儲管理 2可重定位裝入可重定位裝入(relocatable loading) 可重定位裝入方式是指在可執(zhí)行文件中，列出各個需可重定位裝入方式是指在可執(zhí)行文件中，列出各個需要重定位的地址單元和相對地址值，裝入時再根據(jù)所定要重定位的地址單元和相對地址值，裝入時再根據(jù)所定位的內(nèi)存地址去修改每個重定位地址項，添加相應(yīng)的偏位的內(nèi)存地址去修改每個重定位地

10、址項，添加相應(yīng)的偏移量。移量。 一個有相對地址空間的程序裝入到物理地址空間時，一個有相對地址空間的程序裝入到物理地址空間時，由于兩個空間不一致，就需要進(jìn)行地址變換，或稱由于兩個空間不一致，就需要進(jìn)行地址變換，或稱地址地址映射，即地址的再定位。映射，即地址的再定位。 地址再定位有兩種方式：靜態(tài)再定位和動態(tài)再定位。地址再定位有兩種方式：靜態(tài)再定位和動態(tài)再定位。 第第4 4章章 存儲管理存儲管理 1) 靜態(tài)再定位靜態(tài)再定位 靜態(tài)再定位是指當(dāng)程序執(zhí)靜態(tài)再定位是指當(dāng)程序執(zhí)行時，行時，由裝入程序運行重定位程由裝入程序運行重定位程序序，根據(jù)作業(yè)在內(nèi)存重分配的起，根據(jù)作業(yè)在內(nèi)存重分配的起始地址，將可執(zhí)行的目標(biāo)

11、代碼裝始地址，將可執(zhí)行的目標(biāo)代碼裝入到指定內(nèi)存中。所謂靜態(tài)，是入到指定內(nèi)存中。所謂靜態(tài)，是指地址定位完成后，在程序的執(zhí)指地址定位完成后，在程序的執(zhí)行期間將不會再發(fā)生變化。靜態(tài)行期間將不會再發(fā)生變化。靜態(tài)再定位是在程序執(zhí)行之前進(jìn)行地再定位是在程序執(zhí)行之前進(jìn)行地址再定位的，這一工作通常是由址再定位的，這一工作通常是由裝配程序完成的。裝配程序完成的。 LOAD 1,50012 3450100500700LOAD 1,5 50012 34505 700程序A的地址空間程序A的存儲空間5 5005 1005 000靜態(tài)重定位示意圖 第第4 4章章 存儲管理存儲管理 靜態(tài)地址再定位的靜態(tài)地址再定位的優(yōu)點是

12、優(yōu)點是：無需硬件地址變化機(jī)：無需硬件地址變化機(jī)構(gòu)支持，容易實現(xiàn)；無需硬件支持，它只要求程序本構(gòu)支持，容易實現(xiàn)；無需硬件支持，它只要求程序本身是可再定位的；它只對那些要修改的地址部分做出身是可再定位的；它只對那些要修改的地址部分做出某種標(biāo)識，再由專門設(shè)計的程序來完成。在早期的操某種標(biāo)識，再由專門設(shè)計的程序來完成。在早期的操作系統(tǒng)中大多數(shù)都采用這種方法。作系統(tǒng)中大多數(shù)都采用這種方法。 靜態(tài)地址再定位的靜態(tài)地址再定位的缺點是缺點是：必須給作業(yè)分配一個：必須給作業(yè)分配一個連續(xù)的存儲區(qū)域，該存儲區(qū)不能分布在內(nèi)存的不同區(qū)連續(xù)的存儲區(qū)域，該存儲區(qū)不能分布在內(nèi)存的不同區(qū)域；在作業(yè)的執(zhí)行期間不能擴(kuò)充存儲空間，也

13、不能在域；在作業(yè)的執(zhí)行期間不能擴(kuò)充存儲空間，也不能在內(nèi)存中移動，因而不能重新分配內(nèi)存，不利于內(nèi)存的內(nèi)存中移動，因而不能重新分配內(nèi)存，不利于內(nèi)存的有效利用；多個用戶很難共享內(nèi)存中的同一程序，如有效利用；多個用戶很難共享內(nèi)存中的同一程序，如若共享同一程序，則各用戶必須使用自己的副本。若共享同一程序，則各用戶必須使用自己的副本。 第第4 4章章 存儲管理存儲管理 2) 動態(tài)再定位動態(tài)再定位 動態(tài)地址再定位是在程序執(zhí)行期間，動態(tài)地址再定位是在程序執(zhí)行期間，在每次存儲在每次存儲訪問之前進(jìn)行的訪問之前進(jìn)行的。程序在裝入內(nèi)存時，并不修改程序。程序在裝入內(nèi)存時，并不修改程序的邏輯地址值，而是在訪問物理內(nèi)存之前

14、，再實時地的邏輯地址值，而是在訪問物理內(nèi)存之前，再實時地將邏輯地址轉(zhuǎn)換成物理地址。在這種情況下，其實現(xiàn)將邏輯地址轉(zhuǎn)換成物理地址。在這種情況下，其實現(xiàn)機(jī)制要依賴硬件地址變換機(jī)構(gòu)，即通過基地址寄存器機(jī)制要依賴硬件地址變換機(jī)構(gòu)，即通過基地址寄存器BR、變址寄存器、變址寄存器VR計算出指令的有效地址，再利用計算出指令的有效地址，再利用硬件機(jī)構(gòu)實現(xiàn)地址變換，如圖硬件機(jī)構(gòu)實現(xiàn)地址變換，如圖4.3所示。所示。第第4 4章章 存儲管理存儲管理 LOAD-A 200200VRBR1000邏輯地址空間34563002001000物理地址空間LOAD-A 20034561300120011000圖圖4.3 動態(tài)地址

15、再定位的原理動態(tài)地址再定位的原理第第4 4章章 存儲管理存儲管理 從圖從圖4.3中可以看出：當(dāng)程序開始執(zhí)行時，系統(tǒng)將程中可以看出：當(dāng)程序開始執(zhí)行時，系統(tǒng)將程序在內(nèi)存的起始地址送入序在內(nèi)存的起始地址送入BR中。執(zhí)行指令時，系統(tǒng)將邏中。執(zhí)行指令時，系統(tǒng)將邏輯地址與輯地址與BR中的起始地址相加，從而得到物理地址。中的起始地址相加，從而得到物理地址。 動態(tài)地址再定位的動態(tài)地址再定位的優(yōu)點是：優(yōu)點是：程序在執(zhí)行期間可以換程序在執(zhí)行期間可以換入和換出內(nèi)存，這樣可以緩解內(nèi)存緊張的矛盾；可以把入和換出內(nèi)存，這樣可以緩解內(nèi)存緊張的矛盾；可以把內(nèi)存中的碎片集中起來，以充分利用空間；不必給程序內(nèi)存中的碎片集中起來，

16、以充分利用空間；不必給程序分配連續(xù)的內(nèi)存空間，可以較好地利用較小的內(nèi)存塊；分配連續(xù)的內(nèi)存空間，可以較好地利用較小的內(nèi)存塊；若干用戶可以共享同一程序。若干用戶可以共享同一程序。 動態(tài)地址再定位的動態(tài)地址再定位的缺點：缺點：需要附加的硬件支持，需要附加的硬件支持，而且實現(xiàn)存儲管理的軟件算法比較復(fù)雜。而且實現(xiàn)存儲管理的軟件算法比較復(fù)雜。第第4 4章章 存儲管理存儲管理 3動態(tài)運行期裝入動態(tài)運行期裝入 動態(tài)運行期裝入動態(tài)運行期裝入(dynamic run-time loading)是指在是指在可執(zhí)行文件中記錄虛擬內(nèi)存地址，在裝入和執(zhí)行時通可執(zhí)行文件中記錄虛擬內(nèi)存地址，在裝入和執(zhí)行時通過硬件地址變換機(jī)構(gòu)

17、完成虛擬地址到實際內(nèi)存地址的過硬件地址變換機(jī)構(gòu)完成虛擬地址到實際內(nèi)存地址的變換。變換。 動態(tài)運行期裝入的優(yōu)點是：操作系統(tǒng)可以將一個動態(tài)運行期裝入的優(yōu)點是：操作系統(tǒng)可以將一個程序分散存放于不連續(xù)的內(nèi)存空間，可以通過程序分散存放于不連續(xù)的內(nèi)存空間，可以通過移動程移動程序來實現(xiàn)共享序來實現(xiàn)共享；能夠支持程序執(zhí)行中產(chǎn)生的地址引用，；能夠支持程序執(zhí)行中產(chǎn)生的地址引用，如指針變量如指針變量(而不僅是生成可執(zhí)行文件時的地址引用而不僅是生成可執(zhí)行文件時的地址引用)。 動態(tài)運行期裝入的缺點是：需要硬件支持動態(tài)運行期裝入的缺點是：需要硬件支持(通常是通常是CPU)，操作系統(tǒng)的實現(xiàn)比較復(fù)雜。，操作系統(tǒng)的實現(xiàn)比較復(fù)雜

18、。第第4 4章章 存儲管理存儲管理 4.1.3 鏈接鏈接 1鏈接方法鏈接方法 常見的鏈接方法有靜態(tài)鏈接和動態(tài)鏈接兩種。常見的鏈接方法有靜態(tài)鏈接和動態(tài)鏈接兩種。 1) 靜態(tài)鏈接靜態(tài)鏈接 靜態(tài)鏈接靜態(tài)鏈接(static linking)是在生成可執(zhí)行文件時進(jìn)是在生成可執(zhí)行文件時進(jìn)行的，即在目標(biāo)模塊中記錄被調(diào)用模塊的名字符號地行的，即在目標(biāo)模塊中記錄被調(diào)用模塊的名字符號地址址(symbolic address)，在可執(zhí)行文件中將該名字改寫，在可執(zhí)行文件中將該名字改寫為指令直接使用的數(shù)字地址，如圖為指令直接使用的數(shù)字地址，如圖4.4所示。所示。第第4 4章章 存儲管理存儲管理 0L1callfunct

19、ion1Module AModule B function10 function1( ) call LFModule AModule B0L1L function1 function1( ) LFLM1M1F圖圖4.4 靜態(tài)鏈接靜態(tài)鏈接 第第4 4章章 存儲管理存儲管理 2) 動態(tài)鏈接動態(tài)鏈接 動態(tài)鏈接動態(tài)鏈接(dynamic-linking)是在運行可執(zhí)行文件時是在運行可執(zhí)行文件時進(jìn)行的進(jìn)行的,亦即，執(zhí)行過程中，當(dāng)發(fā)現(xiàn)一個被調(diào)用模塊未亦即，執(zhí)行過程中，當(dāng)發(fā)現(xiàn)一個被調(diào)用模塊未裝入內(nèi)存時，立即取找到該模塊，并鏈接到調(diào)用者模裝入內(nèi)存時，立即取找到該模塊，并鏈接到調(diào)用者模塊上。塊上。 通常被鏈接的共

20、享代碼稱為動態(tài)鏈接庫通常被鏈接的共享代碼稱為動態(tài)鏈接庫(Dynamic Link Library，DLL)或共享庫或共享庫(shared library)。第第4 4章章 存儲管理存儲管理 動態(tài)鏈接的優(yōu)點是：動態(tài)鏈接的優(yōu)點是： (1) 共享：多個進(jìn)程可以共用一個共享：多個進(jìn)程可以共用一個DLL，比較節(jié)省，比較節(jié)省內(nèi)存，從而可以減少文件的交換。內(nèi)存，從而可以減少文件的交換。 (2) 部分裝入：一個進(jìn)程可以將多種操作分散在不部分裝入：一個進(jìn)程可以將多種操作分散在不同的同的DLL中實現(xiàn)，而只將當(dāng)前操作的中實現(xiàn)，而只將當(dāng)前操作的DLL裝入內(nèi)存。裝入內(nèi)存。 (3) 便于局部代碼修改：即便于代碼升級和代碼

21、重便于局部代碼修改：即便于代碼升級和代碼重用；只要函數(shù)的接口參數(shù)用；只要函數(shù)的接口參數(shù)(輸入和輸出輸入和輸出)不變，則修改函不變，則修改函數(shù)及其數(shù)及其DLL時，無需對可執(zhí)行文件重新編譯或鏈接。時，無需對可執(zhí)行文件重新編譯或鏈接。 (4) 便于適應(yīng)運行環(huán)境：調(diào)用不同的便于適應(yīng)運行環(huán)境：調(diào)用不同的DLL，就可以，就可以適應(yīng)多種使用環(huán)境并提供不同的功能。適應(yīng)多種使用環(huán)境并提供不同的功能。 第第4 4章章 存儲管理存儲管理 動態(tài)鏈接的缺點是：動態(tài)鏈接的缺點是：(1) 增加了程序執(zhí)行時的鏈接開銷。增加了程序執(zhí)行時的鏈接開銷。(2) 程序由多個文件組成，因此增加了管理復(fù)雜度。程序由多個文件組成，因此增加了

22、管理復(fù)雜度。第第4 4章章 存儲管理存儲管理 4.1.5 存儲管理的任務(wù)存儲管理的任務(wù) 在現(xiàn)代操作系統(tǒng)中，存儲管理的主要任務(wù)有以下幾在現(xiàn)代操作系統(tǒng)中，存儲管理的主要任務(wù)有以下幾個方面。個方面。 (1) 存儲分配和回收：是存儲管理的主要內(nèi)容，用存儲分配和回收：是存儲管理的主要內(nèi)容，用來確定其算法和相應(yīng)的數(shù)據(jù)結(jié)構(gòu)。來確定其算法和相應(yīng)的數(shù)據(jù)結(jié)構(gòu)。 (2) 地址變換地址變換(地址再定位地址再定位)：可執(zhí)行文件生成中的：可執(zhí)行文件生成中的鏈接技術(shù)、程序加載時的重定位技術(shù)及進(jìn)程運行時硬鏈接技術(shù)、程序加載時的重定位技術(shù)及進(jìn)程運行時硬件和軟件的地址變換技術(shù)和機(jī)構(gòu)。件和軟件的地址變換技術(shù)和機(jī)構(gòu)。第第4 4章章

23、存儲管理存儲管理 (3) 存儲共享和保護(hù)：將代碼和數(shù)據(jù)共享，設(shè)定對存儲共享和保護(hù)：將代碼和數(shù)據(jù)共享，設(shè)定對地址空間的訪問權(quán)限地址空間的訪問權(quán)限(讀、寫、執(zhí)行讀、寫、執(zhí)行)。 (4) 存儲器擴(kuò)充：它涉及存儲器的邏輯組織和物理存儲器擴(kuò)充：它涉及存儲器的邏輯組織和物理組織，有兩種控制方式：組織，有兩種控制方式： 如果由應(yīng)用程序控制，則采用覆蓋技術(shù)。如果由應(yīng)用程序控制，則采用覆蓋技術(shù)。 如果由操作系統(tǒng)控制，則采用交換技術(shù)如果由操作系統(tǒng)控制，則采用交換技術(shù)(整個進(jìn)程整個進(jìn)程空間范圍內(nèi)空間范圍內(nèi))或請求調(diào)入和預(yù)調(diào)入或請求調(diào)入和預(yù)調(diào)入(部分進(jìn)程空間部分進(jìn)程空間)。第第4 4章章 存儲管理存儲管理 4.1.6

24、 各種存儲管理方案各種存儲管理方案 從操作系統(tǒng)的發(fā)展歷史來看，存儲管理主要有以從操作系統(tǒng)的發(fā)展歷史來看，存儲管理主要有以下幾個方案：下幾個方案： (1) 分區(qū)存儲管理方案：是一種分區(qū)存儲管理方案：是一種連續(xù)連續(xù)存儲管理方案，存儲管理方案，但需要一次性全部裝入內(nèi)存。但需要一次性全部裝入內(nèi)存。 (2) 段式存儲管理方案：是一種段式存儲管理方案：是一種不連續(xù)不連續(xù)存儲管理方存儲管理方案，段和段之間可以不連續(xù)，但需要一次性全部裝入案，段和段之間可以不連續(xù)，但需要一次性全部裝入內(nèi)存。內(nèi)存。 (3) 頁式存儲管理方案：是一種頁式存儲管理方案：是一種不連續(xù)不連續(xù)存儲管理方存儲管理方案，也需要一次性全部裝入內(nèi)

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

26、6) 虛擬存儲管理方案：又分為兩種，分別是虛擬頁虛擬存儲管理方案：又分為兩種，分別是虛擬頁式式(請求分頁請求分頁)存儲管理和虛擬段式存儲管理和虛擬段式(請求分段請求分段)存儲管理。存儲管理。第第4 4章章 存儲管理存儲管理 4.2 分區(qū)存儲管理方案分區(qū)存儲管理方案 分區(qū)存儲管理方案的數(shù)據(jù)結(jié)構(gòu)是分區(qū)表或分區(qū)鏈分區(qū)存儲管理方案的數(shù)據(jù)結(jié)構(gòu)是分區(qū)表或分區(qū)鏈表，主要功能是：表，主要功能是： (1) 可以只記錄空閑分區(qū)，也可以同時記錄空閑和可以只記錄空閑分區(qū)，也可以同時記錄空閑和占用分區(qū)。占用分區(qū)。 (2) 分區(qū)表中，表項數(shù)目隨著內(nèi)存的分配和釋放而分區(qū)表中，表項數(shù)目隨著內(nèi)存的分配和釋放而動態(tài)改變，可以規(guī)定

27、最大表項數(shù)目。動態(tài)改變，可以規(guī)定最大表項數(shù)目。 (3) 分區(qū)表可以劃分為兩個表格：空閑分區(qū)表和分分區(qū)表可以劃分為兩個表格：空閑分區(qū)表和分配分區(qū)表，從而減小每個表格的長度。配分區(qū)表，從而減小每個表格的長度。 第第4 4章章 存儲管理存儲管理 4.2.1 單一連續(xù)分區(qū)存儲管理單一連續(xù)分區(qū)存儲管理 單一連續(xù)分區(qū)存儲管理把整個內(nèi)存空間的最低端單一連續(xù)分區(qū)存儲管理把整個內(nèi)存空間的最低端和最高端作為操作系統(tǒng)區(qū)，中間作為用戶程序區(qū)。在和最高端作為操作系統(tǒng)區(qū)，中間作為用戶程序區(qū)。在DOS操作系統(tǒng)中就采用了這種方法，如圖操作系統(tǒng)中就采用了這種方法，如圖4.7所示。所示。第第4 4章章 存儲管理存儲管理 分配給用

28、戶作業(yè)的空間操作系統(tǒng)用戶程序未用0 xFFF0ROM中的設(shè)備驅(qū)動程序用戶程序位于RAM中的操作系統(tǒng)0 xFFF0圖圖4.7 單一連續(xù)分區(qū)存儲管理的分配方式單一連續(xù)分區(qū)存儲管理的分配方式 第第4 4章章 存儲管理存儲管理 這種存儲分配思想將內(nèi)存分為兩個區(qū)域：系統(tǒng)區(qū)這種存儲分配思想將內(nèi)存分為兩個區(qū)域：系統(tǒng)區(qū)和用戶區(qū)。應(yīng)用程序裝入到用戶區(qū)，可使用用戶區(qū)全和用戶區(qū)。應(yīng)用程序裝入到用戶區(qū)，可使用用戶區(qū)全部空間。部空間。 單一連續(xù)分區(qū)的優(yōu)點是：簡單，適用于單用戶、單一連續(xù)分區(qū)的優(yōu)點是：簡單，適用于單用戶、單任務(wù)的操作系統(tǒng)單任務(wù)的操作系統(tǒng)(比如比如CP/M和和DOS操作系統(tǒng)操作系統(tǒng))，不需，不需要復(fù)雜的硬件

29、支持。要復(fù)雜的硬件支持。 單一連續(xù)分區(qū)的缺點是：一個作業(yè)運行時要占用單一連續(xù)分區(qū)的缺點是：一個作業(yè)運行時要占用整個內(nèi)存的地址空間，即使很小的程序也是如此，對整個內(nèi)存的地址空間，即使很小的程序也是如此，對內(nèi)存造成了很大的浪費，內(nèi)存的利用率很低。內(nèi)存造成了很大的浪費，內(nèi)存的利用率很低。第第4 4章章 存儲管理存儲管理 4.2.2 固定分區(qū)分配固定分區(qū)分配 為了便于管理整個內(nèi)存，需建立一個表格來登記為了便于管理整個內(nèi)存，需建立一個表格來登記和管理整個內(nèi)存。在這個表中登記了每一個分區(qū)的大和管理整個內(nèi)存。在這個表中登記了每一個分區(qū)的大小，起始地址和分配狀態(tài)，如表小，起始地址和分配狀態(tài)，如表4.1和圖和圖

30、4.8所示。當(dāng)有所示。當(dāng)有作業(yè)裝入時，系統(tǒng)便可以搜索這個表，找出一個大小作業(yè)裝入時，系統(tǒng)便可以搜索這個表，找出一個大小合適的分區(qū)分配給它。當(dāng)程序運行結(jié)束時，可以把它合適的分區(qū)分配給它。當(dāng)程序運行結(jié)束時，可以把它所占用的空間再釋放回去。地址重定位可以采用靜態(tài)所占用的空間再釋放回去。地址重定位可以采用靜態(tài)地址定位或是動態(tài)地址定位的方法。地址定位或是動態(tài)地址定位的方法。第第4 4章章 存儲管理存儲管理 表表4.1 分區(qū)狀態(tài)表分區(qū)狀態(tài)表 分區(qū)號分區(qū)號大小大小起始地址起始地址分配狀態(tài)分配狀態(tài)120 KB100 K已分配已分配240 KB120 K已分配已分配3100 KB160 K未分配未分配4200

31、KB260 K已分配已分配第第4 4章章 存儲管理存儲管理 操作系統(tǒng)0下界寄存器作業(yè)A作業(yè)B作業(yè)C460K160K120K100K下界寄存器260K圖圖4.8 固定分區(qū)的內(nèi)存分配情況固定分區(qū)的內(nèi)存分配情況第第4 4章章 存儲管理存儲管理 為了實現(xiàn)多道程序設(shè)計，可以按等待作業(yè)的類型為了實現(xiàn)多道程序設(shè)計，可以按等待作業(yè)的類型設(shè)置多個等待隊列，也可以把所有的等待作業(yè)設(shè)置為設(shè)置多個等待隊列，也可以把所有的等待作業(yè)設(shè)置為一個等待隊列。如圖一個等待隊列。如圖4.9所示為多道程序情況下固定分所示為多道程序情況下固定分區(qū)的情況，左邊為多個等待隊列情況下的固定分區(qū)，區(qū)的情況，左邊為多個等待隊列情況下的固定分區(qū)，

32、右邊為單個等待隊列情況下的固定分區(qū)。右邊為單個等待隊列情況下的固定分區(qū)。第第4 4章章 存儲管理存儲管理 多個等待隊列分區(qū)4分區(qū)3分區(qū)2分區(qū)1操作系統(tǒng)分區(qū)4分區(qū)3分區(qū)2分區(qū)1操作系統(tǒng)單個等待隊列圖圖4.9 多道程序情況下的固定分區(qū)原理多道程序情況下的固定分區(qū)原理第第4 4章章 存儲管理存儲管理 固定分區(qū)的優(yōu)點是：與單一連續(xù)分配方法相比，固定分區(qū)的優(yōu)點是：與單一連續(xù)分配方法相比，固定分區(qū)法的內(nèi)存利用率提高了；可以支持多道程序；固定分區(qū)法的內(nèi)存利用率提高了；可以支持多道程序；實現(xiàn)簡單，開銷小。實現(xiàn)簡單，開銷小。 固定分區(qū)的缺點：必須預(yù)先能夠估計作業(yè)要占用固定分區(qū)的缺點：必須預(yù)先能夠估計作業(yè)要占用多

33、大的內(nèi)存空間，有時候這是難以做到的；區(qū)內(nèi)碎片多大的內(nèi)存空間，有時候這是難以做到的；區(qū)內(nèi)碎片造成浪費；分區(qū)總數(shù)固定，限制了并發(fā)執(zhí)行的程序數(shù)造成浪費；分區(qū)總數(shù)固定，限制了并發(fā)執(zhí)行的程序數(shù)目。目。第第4 4章章 存儲管理存儲管理 4.2.3 可變分區(qū)可變分區(qū) (動態(tài)分區(qū)分配動態(tài)分區(qū)分配) 1空閑存儲區(qū)表空閑存儲區(qū)表 若采用固定分區(qū)法，則作業(yè)運行時所需內(nèi)存一般若采用固定分區(qū)法，則作業(yè)運行時所需內(nèi)存一般不會剛好等于某一個分區(qū)的大小，因此分區(qū)內(nèi)部的不會剛好等于某一個分區(qū)的大小，因此分區(qū)內(nèi)部的“內(nèi)零頭內(nèi)零頭”被白白浪費了；另一方面，固定分區(qū)的分被白白浪費了；另一方面，固定分區(qū)的分區(qū)數(shù)在系統(tǒng)啟動以后不能任意改

34、變，當(dāng)系統(tǒng)中運行的區(qū)數(shù)在系統(tǒng)啟動以后不能任意改變，當(dāng)系統(tǒng)中運行的作業(yè)數(shù)大于分區(qū)數(shù)時，就不可避免地會有一些作業(yè)分作業(yè)數(shù)大于分區(qū)數(shù)時，就不可避免地會有一些作業(yè)分配不到分區(qū)，即使所有作業(yè)所需存儲空間總和小于內(nèi)配不到分區(qū)，即使所有作業(yè)所需存儲空間總和小于內(nèi)存總和也不行。存總和也不行。 第第4 4章章 存儲管理存儲管理 可變分區(qū)存儲管理法并不預(yù)先將內(nèi)存劃分成分區(qū)，可變分區(qū)存儲管理法并不預(yù)先將內(nèi)存劃分成分區(qū)，而是等到作業(yè)運行需要內(nèi)存時才向系統(tǒng)申請，從空閑而是等到作業(yè)運行需要內(nèi)存時才向系統(tǒng)申請，從空閑的內(nèi)存區(qū)中挖一塊出來，其大小等于作業(yè)所需內(nèi)存的的內(nèi)存區(qū)中挖一塊出來，其大小等于作業(yè)所需內(nèi)存的大小，這樣就不會

35、產(chǎn)生大小，這樣就不會產(chǎn)生“內(nèi)零頭內(nèi)零頭”。管理空閑內(nèi)存區(qū)。管理空閑內(nèi)存區(qū)的數(shù)據(jù)結(jié)構(gòu)可采用鏈接法和連續(xù)線性表格法。每一個的數(shù)據(jù)結(jié)構(gòu)可采用鏈接法和連續(xù)線性表格法。每一個空閑分區(qū)用一個空閑分區(qū)用一個map結(jié)構(gòu)管理：結(jié)構(gòu)管理： struct map unsigned m_size; /空閑分區(qū)的長度空閑分區(qū)的長度 char * m_addr; /空閑分區(qū)的起始地址空閑分區(qū)的起始地址 ； struct map coremapN;第第4 4章章 存儲管理存儲管理 圖圖4.10所示為空閑分區(qū)表的初始狀態(tài)，圖所示為空閑分區(qū)表的初始狀態(tài)，圖4.11為某為某一時刻空閑分區(qū)表的狀態(tài)。圖中，一時刻空閑分區(qū)表的狀態(tài)。圖

36、中，m_size是空閑分區(qū)是空閑分區(qū)的長度，的長度，m_addr是空閑分區(qū)的起始地址。各個空閑分是空閑分區(qū)的起始地址。各個空閑分區(qū)按起始地址由低到高的順序登記在區(qū)按起始地址由低到高的順序登記在空閑存儲區(qū)表空閑存儲區(qū)表中，中，m_size為為0的表項是空白表項，它們集中在表的后部。的表項是空白表項，它們集中在表的后部。第第4 4章章 存儲管理存儲管理 m_sizem_addr00空閑區(qū)內(nèi)存圖圖4.10 空閑分區(qū)表的初始狀態(tài)空閑分區(qū)表的初始狀態(tài) 第第4 4章章 存儲管理存儲管理 m_sizem_addrm_sizem_addrm_sizem_addr0空閑區(qū)已分配區(qū)空閑區(qū)已分配區(qū)已分配區(qū)空閑區(qū)內(nèi)存

37、 圖圖4.11 某一時刻空閑分區(qū)表的狀態(tài)某一時刻空閑分區(qū)表的狀態(tài) 第第4 4章章 存儲管理存儲管理 2分區(qū)分配算法分區(qū)分配算法 尋找某個空閑分區(qū)，其大小必須大于或等于程序?qū)ふ夷硞€空閑分區(qū)，其大小必須大于或等于程序的要求。若是大于要求，則將該分區(qū)分割成兩個分區(qū)，的要求。若是大于要求，則將該分區(qū)分割成兩個分區(qū)，其中一個分區(qū)為要求的大小并標(biāo)記為其中一個分區(qū)為要求的大小并標(biāo)記為“占用占用”，而另，而另一個分區(qū)為余下部分并標(biāo)記為一個分區(qū)為余下部分并標(biāo)記為“空閑空閑”。分區(qū)的先后。分區(qū)的先后次序通常是從內(nèi)存低端到高端。次序通常是從內(nèi)存低端到高端。 選擇分區(qū)的算法有四種：最先適應(yīng)算法、最佳適選擇分區(qū)的算法有

38、四種：最先適應(yīng)算法、最佳適應(yīng)算法、最差適應(yīng)算法和循環(huán)最先適應(yīng)算法。應(yīng)算法、最差適應(yīng)算法和循環(huán)最先適應(yīng)算法。第第4 4章章 存儲管理存儲管理 1) 最先適應(yīng)算法最先適應(yīng)算法(first-fit) 最先適應(yīng)算法是將所有的空閑分區(qū)按照地址遞增最先適應(yīng)算法是將所有的空閑分區(qū)按照地址遞增的順序排列，然后按照分區(qū)的先后次序從頭開始查找，的順序排列，然后按照分區(qū)的先后次序從頭開始查找，符合要求的第一個分區(qū)就是要找的分區(qū)。該算法的分符合要求的第一個分區(qū)就是要找的分區(qū)。該算法的分配和釋放的時間性能較好，較大的空閑分區(qū)可以被保配和釋放的時間性能較好，較大的空閑分區(qū)可以被保留在內(nèi)存高端。留在內(nèi)存高端。 第第4 4章

39、章 存儲管理存儲管理 (1) 分配算法：分配算法： 當(dāng)為作業(yè)分配大小為當(dāng)為作業(yè)分配大小為size的空間時，總是從表的低的空間時，總是從表的低地址部分開始查找，當(dāng)?shù)谝淮握业酱笥诘扔谏暾埓笮〉刂凡糠珠_始查找，當(dāng)?shù)谝淮握业酱笥诘扔谏暾埓笮〉目臻g時，就按所需要的大小分配空間給作業(yè)，若分的空間時，就按所需要的大小分配空間給作業(yè)，若分配后還有剩余空間，就修改原來的配后還有剩余空間，就修改原來的m_size和和m_addr，以記錄余下的零頭；如果作業(yè)所需要的空間剛好等于以記錄余下的零頭；如果作業(yè)所需要的空間剛好等于該空間的大小，那么該空間的該空間的大小，那么該空間的m_size就為就為0；然后要刪；然后要刪

40、除表中的這些空間，即將各個非零的表項上移。程序除表中的這些空間，即將各個非零的表項上移。程序描述如下：描述如下：第第4 4章章 存儲管理存儲管理 int *ffmalloc( mp , size )struct map *mp;unsigned int size;register int regint;register struct map *bp; /從從mp開始，只要開始，只要size不等于不等于0，逐個地址檢查，逐個地址檢查 for(bp=mp; bp-m_size ; bp+ ) if ( bp-m_size = size ) /只要空間足夠大只要空間足夠大struct map uns

41、igned m_size; char * m_addr;；第第4 4章章 存儲管理存儲管理 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) ;第第4 4章

42、章 存儲管理存儲管理 (2) 釋放算法：釋放算法： 某一個作業(yè)釋放以前所分配到的內(nèi)存就是將該內(nèi)存某一個作業(yè)釋放以前所分配到的內(nèi)存就是將該內(nèi)存區(qū)歸還給操作系統(tǒng)，使其成為空閑區(qū)而可以被其他作區(qū)歸還給操作系統(tǒng)，使其成為空閑區(qū)而可以被其他作業(yè)使用?；厥諘r如果釋放區(qū)與臨近的空閑區(qū)相連接，業(yè)使用?；厥諘r如果釋放區(qū)與臨近的空閑區(qū)相連接，要將它們合并成較大的空閑區(qū)，否則空閑區(qū)將被分割要將它們合并成較大的空閑區(qū)，否則空閑區(qū)將被分割得越來越小，最終導(dǎo)致不能利用。另外，空閑區(qū)個數(shù)得越來越小，最終導(dǎo)致不能利用。另外，空閑區(qū)個數(shù)越來越多，也會使得空閑區(qū)登記表溢出。越來越多，也會使得空閑區(qū)登記表溢出。第第4 4章章 存儲

43、管理存儲管理 釋放算法分四種情況：釋放算法分四種情況： 僅與前面一個空閑區(qū)相連，如圖僅與前面一個空閑區(qū)相連，如圖4.12(a)所示。所示。合并前空閑區(qū)和釋放區(qū)以構(gòu)成一塊大的新空閑區(qū)，并合并前空閑區(qū)和釋放區(qū)以構(gòu)成一塊大的新空閑區(qū)，并修改空閑區(qū)表項。修改空閑區(qū)表項。 與前面空閑區(qū)和后面空閑區(qū)都相連，如圖與前面空閑區(qū)和后面空閑區(qū)都相連，如圖4.12(b)所示。將三塊空閑區(qū)合并成一塊空閑區(qū)。所示。將三塊空閑區(qū)合并成一塊空閑區(qū)。 第第4 4章章 存儲管理存儲管理 僅僅與后空閑區(qū)相連，如圖僅僅與后空閑區(qū)相連，如圖4.12(c)所示。與后所示。與后空閑區(qū)合并，使后空閑區(qū)表項的空閑區(qū)合并，使后空閑區(qū)表項的m_

44、addr為釋放區(qū)的起為釋放區(qū)的起始地址，始地址，m_size為釋放區(qū)與后空閑區(qū)的長度之和。為釋放區(qū)與后空閑區(qū)的長度之和。 與前后空閑區(qū)都不相連，如圖與前后空閑區(qū)都不相連，如圖4.12(d)所示。在所示。在前、后空閑區(qū)表項中間插入一個新的表項，其前、后空閑區(qū)表項中間插入一個新的表項，其m_addr為釋放區(qū)的起始地址，為釋放區(qū)的起始地址，m_size為釋放區(qū)的長度。為釋放區(qū)的長度。 第第4 4章章 存儲管理存儲管理 后空閑區(qū)釋放區(qū)前空閑區(qū)后空閑區(qū)釋放區(qū)前空閑區(qū)后空閑區(qū)釋放區(qū)前空閑區(qū)后空閑區(qū)釋放區(qū)前空閑區(qū)(a)(b)(c)(d)圖圖4.12 釋放區(qū)與前后空閑區(qū)相鄰的情況釋放區(qū)與前后空閑區(qū)相鄰的情況第

45、第4 4章章 存儲管理存儲管理 程序描述如下：程序描述如下：mfree( unsigned size , char * StartAddr ) struct map *bp; char *addr, *taddr; unsigned TmpSize ; addr = StartAddr; struct map unsigned m_size; char * m_addr;；第第4 4章章 存儲管理存儲管理 for( bp = coremap ; bp-m_addr m_size != 0 ; bp + ) if ( bp coremap & ( bp-1)-m_size = addr

46、) ( bp-1) -m_size += size ; /連接前部空閑區(qū)連接前部空閑區(qū) if ( addr + size = bp-m_addr ) /再連接后部空閑區(qū)再連接后部空閑區(qū) ( bp-1)- m_size += bp-m_size ; while ( bp-m_size ) 第第4 4章章 存儲管理存儲管理 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 ) /與后空閑區(qū)相連與后空閑區(qū)相連第第4 4章章

47、 存儲管理存儲管理 bp-m_addr -= size ; bp-m_size += size ; else if ( size ) do /單獨插入空閑分區(qū)表單獨插入空閑分區(qū)表,而不與前后相連而不與前后相連 taddr = bp-m_addr ; bp-m_addr = addr; addr = taddr; TmpSize = bp-m_size ;第第4 4章章 存儲管理存儲管理 bp-m_size = size ; bp + ; while ( size = TmpSize ); 第第4 4章章 存儲管理存儲管理 最先適應(yīng)算法的優(yōu)點：最先適應(yīng)算法的優(yōu)點：分配簡單而且合并相鄰分配簡單而且

48、合并相鄰的空閑區(qū)也比較容易，該算法的實質(zhì)是盡可能利用存的空閑區(qū)也比較容易，該算法的實質(zhì)是盡可能利用存儲區(qū)低地址的空閑區(qū)，而盡量在高地址部分保存較大儲區(qū)低地址的空閑區(qū)，而盡量在高地址部分保存較大的空閑區(qū)，以便一旦有分配大的空閑區(qū)的要求時，容的空閑區(qū)，以便一旦有分配大的空閑區(qū)的要求時，容易得到滿足。易得到滿足。在釋放內(nèi)存分區(qū)時，如果有相鄰的空在釋放內(nèi)存分區(qū)時，如果有相鄰的空閑區(qū)就進(jìn)行合并，使其成為一個較大的空閑區(qū)。閑區(qū)就進(jìn)行合并，使其成為一個較大的空閑區(qū)。第第4 4章章 存儲管理存儲管理 最先適應(yīng)算法的缺點：最先適應(yīng)算法的缺點：由于查找總是從表首開由于查找總是從表首開始，前面的空閑區(qū)被分割得很小時

49、，能滿足分配要求始，前面的空閑區(qū)被分割得很小時，能滿足分配要求的可能性就較小，查找次數(shù)就較多。系統(tǒng)中作業(yè)越多，的可能性就較小，查找次數(shù)就較多。系統(tǒng)中作業(yè)越多，這個問題就越來越嚴(yán)重。針對這個問題，對最先適應(yīng)這個問題就越來越嚴(yán)重。針對這個問題，對最先適應(yīng)法稍加改進(jìn)，就有了循環(huán)最先適應(yīng)法。法稍加改進(jìn)，就有了循環(huán)最先適應(yīng)法。會產(chǎn)生碎片，會產(chǎn)生碎片，這些碎片散布在存儲器的各處，不能集中使用，因而這些碎片散布在存儲器的各處，不能集中使用，因而降低了存儲器的利用率。降低了存儲器的利用率。第第4 4章章 存儲管理存儲管理 如圖如圖4.13所示是某一個時刻所示是某一個時刻J1、J2、J3、J4四個作四個作業(yè)在內(nèi)

50、存中的分配情況、空閑區(qū)表和已分配區(qū)表，它業(yè)在內(nèi)存中的分配情況、空閑區(qū)表和已分配區(qū)表，它們的長度分別是們的長度分別是15 KB、10 KB、12 KB、10 KB。J5和和J6兩個新作業(yè)的長度分別為兩個新作業(yè)的長度分別為5 KB和和13 KB，分配內(nèi)，分配內(nèi)存后的內(nèi)存分配情況、空閑區(qū)表和已分配區(qū)表如圖存后的內(nèi)存分配情況、空閑區(qū)表和已分配區(qū)表如圖4.14所示。所示。第第4 4章章 存儲管理存儲管理 空閑區(qū)表起始地址15 K48 K80 K長度23 KB20 KB30 KB狀態(tài)未分配未分配未分配空空空已分配區(qū)表0 K起始地址0 K38 K68 K110 K長度15 KB10 KB12 KB10 KB

51、狀態(tài)J1J2J3J4空空15 K38 K48 K68 K80 K110 K120 KJ1J2J3J4圖圖4.13 最先適應(yīng)算法分配前的狀態(tài)最先適應(yīng)算法分配前的狀態(tài)第第4 4章章 存儲管理存儲管理 空閑區(qū)表起始地址33 K48 K80 K長度5 KB20 KB30 KB狀態(tài)未分配未分配未分配空空空已分配區(qū)表起始地址0 K38 K68 K110 K15 K20 K長度15 KB10 KB12 KB10 KB5 KB13 KB狀態(tài)J1J2J3J4J5J6120 KJ1J2J5J6J3J4110 K80 K68 K48 K38 K33 K20 K15 K0 K圖圖4.14 最先適應(yīng)算法分配后的狀態(tài)最先

52、適應(yīng)算法分配后的狀態(tài)第第4 4章章 存儲管理存儲管理 2) 循環(huán)最先適應(yīng)算法循環(huán)最先適應(yīng)算法 (next-fit，下次適應(yīng)算法，下次適應(yīng)算法) 相對于最先適應(yīng)算法，下次適應(yīng)算法按分區(qū)的先相對于最先適應(yīng)算法，下次適應(yīng)算法按分區(qū)的先后次序，從上次分配的分區(qū)開始查找，到最后分區(qū)時后次序，從上次分配的分區(qū)開始查找，到最后分區(qū)時再回到開頭，符合要求的第一個分區(qū)就是找到的分區(qū)。再回到開頭，符合要求的第一個分區(qū)就是找到的分區(qū)。 第第4 4章章 存儲管理存儲管理 循環(huán)最先適應(yīng)算法分配時總是循環(huán)最先適應(yīng)算法分配時總是從起始查找指針?biāo)笍钠鹗疾檎抑羔標(biāo)赶虻谋眄楅_始向的表項開始，第一次找到滿足要求的空閑區(qū)時，就，

53、第一次找到滿足要求的空閑區(qū)時，就分配所需要的空閑區(qū)，然后修改表項，并調(diào)整起始查分配所需要的空閑區(qū)，然后修改表項，并調(diào)整起始查找指針，使其指向隊列中被分配的后面的那塊空閑區(qū)。找指針，使其指向隊列中被分配的后面的那塊空閑區(qū)。 循環(huán)最先適應(yīng)法的實質(zhì)是起始查找指針?biāo)傅目臻e循環(huán)最先適應(yīng)法的實質(zhì)是起始查找指針?biāo)傅目臻e區(qū)和其后的空閑區(qū)群常為較長時間未被分割過的空閑區(qū)和其后的空閑區(qū)群常為較長時間未被分割過的空閑區(qū)，它們已經(jīng)合并成為大的空閑區(qū)的可能性較大，與區(qū)，它們已經(jīng)合并成為大的空閑區(qū)的可能性較大，與最先適應(yīng)算法相比，它在沒有增加多少代價的情況下最先適應(yīng)算法相比，它在沒有增加多少代價的情況下卻明顯地提高了

54、分配查找的速度。卻明顯地提高了分配查找的速度。 循環(huán)最先適應(yīng)算法的釋放算法與最先適應(yīng)算法的基循環(huán)最先適應(yīng)算法的釋放算法與最先適應(yīng)算法的基本相同。本相同。第第4 4章章 存儲管理存儲管理 3) 最佳適應(yīng)算法最佳適應(yīng)算法(best-fit) 最佳適應(yīng)算法的思想是將所有的空閑分區(qū)最佳適應(yīng)算法的思想是將所有的空閑分區(qū)按照其按照其容量遞增的順序排列容量遞增的順序排列，當(dāng)要求分配一個空白分區(qū)時，當(dāng)要求分配一個空白分區(qū)時，由小到大進(jìn)行查找。由小到大進(jìn)行查找。 第第4 4章章 存儲管理存儲管理 最佳適應(yīng)算法的空閑存儲區(qū)管理表的組織方法可以最佳適應(yīng)算法的空閑存儲區(qū)管理表的組織方法可以采用順序結(jié)構(gòu)，也可以采用鏈接

55、結(jié)構(gòu)。采用順序結(jié)構(gòu)，也可以采用鏈接結(jié)構(gòu)。 最佳適應(yīng)算法的優(yōu)點：最佳適應(yīng)算法的優(yōu)點：由于算法是在所有大于或由于算法是在所有大于或者等于要求分配長度的空閑區(qū)中挑選一個最小的分區(qū)，者等于要求分配長度的空閑區(qū)中挑選一個最小的分區(qū)，所以分配后所剩余的空白塊會最小。所以分配后所剩余的空白塊會最小。平均而言，只平均而言，只要查找一半的表格便能找到最佳適應(yīng)的空白區(qū)。要查找一半的表格便能找到最佳適應(yīng)的空白區(qū)。如如果有一個空白區(qū)的容量正好滿足要求，則它必被選中。果有一個空白區(qū)的容量正好滿足要求，則它必被選中。第第4 4章章 存儲管理存儲管理 最佳適應(yīng)算法的缺點：最佳適應(yīng)算法的缺點：由于空閑區(qū)是按大小而由于空閑區(qū)是

56、按大小而不是按地址的順序排列的，因此釋放時，要在整個鏈不是按地址的順序排列的，因此釋放時，要在整個鏈表上搜索地址相鄰的空閑區(qū)，合并后又要插入到合適表上搜索地址相鄰的空閑區(qū)，合并后又要插入到合適的位置。的位置?？瞻讌^(qū)一般不可能恰好滿足要求，在分配空白區(qū)一般不可能恰好滿足要求，在分配之后的剩余部分通常非常小，以致小到無法使用。之后的剩余部分通常非常小，以致小到無法使用。 其內(nèi)存分配前的狀態(tài)如圖其內(nèi)存分配前的狀態(tài)如圖4.13所示，所示，J5和和J6是兩個是兩個新作業(yè)，對它們分配內(nèi)存后的內(nèi)存分配情況、空閑區(qū)新作業(yè)，對它們分配內(nèi)存后的內(nèi)存分配情況、空閑區(qū)表和已分配區(qū)表如圖表和已分配區(qū)表如圖4.15所示。

57、所示。第第4 4章章 存儲管理存儲管理 4) 最壞適應(yīng)算法最壞適應(yīng)算法(worst-fit) 最壞適應(yīng)算法的思想與最佳適應(yīng)算法相反，將所最壞適應(yīng)算法的思想與最佳適應(yīng)算法相反，將所有的空白分區(qū)按容量遞減的順序排列，最前面的最大有的空白分區(qū)按容量遞減的順序排列，最前面的最大的空閑分區(qū)就是找到的分區(qū)。該算法是取所有空閑區(qū)的空閑分區(qū)就是找到的分區(qū)。該算法是取所有空閑區(qū)中最大的一塊，把剩余的塊再變成一個新小一點的空中最大的一塊，把剩余的塊再變成一個新小一點的空閑區(qū)。算法基本不留下小空閑分區(qū)，但較大的空閑分閑區(qū)。算法基本不留下小空閑分區(qū)，但較大的空閑分區(qū)不會被保留。區(qū)不會被保留。第第4 4章章 存儲管理存

58、儲管理 最壞適應(yīng)算法的實現(xiàn)與前面的最佳適應(yīng)算法類似。最壞適應(yīng)算法的實現(xiàn)與前面的最佳適應(yīng)算法類似。 最壞適應(yīng)算法的優(yōu)點：分配的時候只需查找一次最壞適應(yīng)算法的優(yōu)點：分配的時候只需查找一次就可以成功，分配的算法很快。就可以成功，分配的算法很快。 最壞適應(yīng)算法的缺點：最后剩余的分區(qū)會越來越最壞適應(yīng)算法的缺點：最后剩余的分區(qū)會越來越小，無法運行大程序。小，無法運行大程序。 其內(nèi)存分配前的狀態(tài)如圖其內(nèi)存分配前的狀態(tài)如圖4.13所示，所示，J5和和J6是兩個是兩個新作業(yè)，對它們分配內(nèi)存后的內(nèi)存分配情況、空閑區(qū)新作業(yè)，對它們分配內(nèi)存后的內(nèi)存分配情況、空閑區(qū)表和已分配區(qū)表如圖表和已分配區(qū)表如圖4.16所示。所示

59、。第第4 4章章 存儲管理存儲管理 空閑區(qū)表起始地址15 K66 K80 K長度23 KB2 KB30 KB狀態(tài)未分配未分配未分配空空空已分配區(qū)表起始地址0 K38 K68 K110 K48 K53 K長度15 KB10 KB12 KB10 KB5 KB13 KB狀態(tài)J1J2J3J4J5J6120 K110 K80 K68 K66 K48 K38 K15 K0 KJ1J2J5J6J3J453 K圖圖4.15 最佳適應(yīng)算法分配后的狀態(tài)最佳適應(yīng)算法分配后的狀態(tài)第第4 4章章 存儲管理存儲管理 空閑區(qū)表起始地址15 K66 K98 K長度23 KB2 KB12 KB狀態(tài)未分配未分配未分配空空空已分配

60、區(qū)表起始地址0 K38 K68 K110 K80 K85 K長度15 KB10 KB12 KB10 KB5 KB13 KB狀態(tài)J1J2J3J4J5J6120 K110 K80 K68 K48 K38 K15 K0 KJ1J2J5J6J3J498 K85 K圖圖4.16 最差適應(yīng)算法分配后的狀態(tài)最差適應(yīng)算法分配后的狀態(tài)第第4 4章章 存儲管理存儲管理 4.2.4 可再定位式分區(qū)可再定位式分區(qū)(可重定位分區(qū)分配可重定位分區(qū)分配) 可再定位分區(qū)分配即浮動分區(qū)分配，是解決可再定位分區(qū)分配即浮動分區(qū)分配，是解決碎片碎片問題問題的簡單而有效的辦法。其基本思想是移動所有被的簡單而有效的辦法。其基本思想是移動所有被分配了的分