計算機(jī)操作系統(tǒng)課件第四章

1、第四章存儲器管理4.1 4.1 存儲器的層次結(jié)構(gòu)存儲器的層次結(jié)構(gòu)4.2 4.2 程序的裝入和鏈接程序的裝入和鏈接 4.3 4.3 連續(xù)分配方式連續(xù)分配方式 4.4 4.4 基本分頁存儲管理方式基本分頁存儲管理方式 4.5 4.5 基本分段存儲管理方式基本分段存儲管理方式 4.6 4.6 虛擬存儲器的基本概念虛擬存儲器的基本概念 4.7 4.7 請求分頁存儲管理方式請求分頁存儲管理方式4.84.8 頁面置換算法頁面置換算法4.94.9 請求分段存儲管理方式請求分段存儲管理方式4.1.1 存儲器的層次結(jié)構(gòu)1. 存儲器的層次結(jié)構(gòu) 在現(xiàn)代計算機(jī)系統(tǒng)在現(xiàn)代計算機(jī)系統(tǒng)中，存儲器是信息處理中，存儲器是信息處

2、理的來源與歸宿，占據(jù)重的來源與歸宿，占據(jù)重要位置。但是，在現(xiàn)有要位置。但是，在現(xiàn)有技術(shù)條件下，任何一種技術(shù)條件下，任何一種存儲裝置，都無法同時存儲裝置，都無法同時從從速度與容量速度與容量兩方面，兩方面，滿足用戶的需求。實際滿足用戶的需求。實際上它們組成了一個速度上它們組成了一個速度由快到慢，容量由小到由快到慢，容量由小到大的存儲裝置層次。大的存儲裝置層次。 存儲器的層次結(jié)構(gòu)存儲器的層次結(jié)構(gòu) 2.各種存儲器 高速緩存高速緩存CacheCache： 少量的、非常快速、昂貴、易變的少量的、非?？焖?、昂貴、易變的 內(nèi)存內(nèi)存RAMRAM： 若干兆字節(jié)、中等速度、中等價格、易若干兆字節(jié)、中等速度、中等價格

3、、易變的變的 磁盤：磁盤： 數(shù)百兆或數(shù)千兆字節(jié)、低速、價廉、不數(shù)百兆或數(shù)千兆字節(jié)、低速、價廉、不易變的易變的 由操作系統(tǒng)協(xié)調(diào)這些存儲器的使用由操作系統(tǒng)協(xié)調(diào)這些存儲器的使用4.1.2 存儲管理的目的1)1)主存的分配和管理：當(dāng)用戶需要內(nèi)存時主存的分配和管理：當(dāng)用戶需要內(nèi)存時, ,系統(tǒng)為之分配相應(yīng)的存儲空間；不需要系統(tǒng)為之分配相應(yīng)的存儲空間；不需要時，及時回收，以供其它用戶使用。時，及時回收，以供其它用戶使用。2)2)提高主存儲器的利用率：不僅能使多道提高主存儲器的利用率：不僅能使多道程序動態(tài)地共享主存，提高主存利用率，程序動態(tài)地共享主存，提高主存利用率，最好還能共享主存中某個區(qū)域的信息。最好還能

4、共享主存中某個區(qū)域的信息。存儲管理的目的（續(xù)）3)3)“擴(kuò)充擴(kuò)充”主存容量：為用戶提供比主存物理主存容量：為用戶提供比主存物理空間大得多的地址空間，以至使用戶感覺空間大得多的地址空間，以至使用戶感覺他的作業(yè)是在這樣一個大的存儲器中運(yùn)行。他的作業(yè)是在這樣一個大的存儲器中運(yùn)行。4)4)存儲保護(hù)：確保多道程序都在各自分配到存儲保護(hù)：確保多道程序都在各自分配到存儲區(qū)域內(nèi)操作，互不干擾，防止一道程存儲區(qū)域內(nèi)操作，互不干擾，防止一道程序破壞其它作業(yè)或系統(tǒng)文件的信息。序破壞其它作業(yè)或系統(tǒng)文件的信息。4.1.3. 基本概念1.1.定位（存儲分配）：為具體的程序和數(shù)定位（存儲分配）：為具體的程序和數(shù)據(jù)等分配存儲

5、單元或存儲區(qū)工作。據(jù)等分配存儲單元或存儲區(qū)工作。2.2.映射：把邏輯地址轉(zhuǎn)換為相應(yīng)的物理地映射：把邏輯地址轉(zhuǎn)換為相應(yīng)的物理地址的過程。址的過程。3.3.隔離：按存取權(quán)限把合法區(qū)與非法區(qū)分隔離：按存取權(quán)限把合法區(qū)與非法區(qū)分隔，實現(xiàn)存儲保護(hù)。隔，實現(xiàn)存儲保護(hù)。4.名空間 程序員在程序中定義的標(biāo)識符程序員在程序中定義的標(biāo)識符 程序符號集合程序符號集合 由程序員自定義由程序員自定義 沒有地址的概念沒有地址的概念地址空間及存儲空間5.地址空間 程序用來訪問信息所用地址單元的集合程序用來訪問信息所用地址單元的集合 邏輯（相對）地址的集合邏輯（相對）地址的集合 由編譯程序生成由編譯程序生成6.6.存儲空間存

6、儲空間 主存中物理單元的集合主存中物理單元的集合 物理（絕對）地址的集合物理（絕對）地址的集合 由裝配程序等生成由裝配程序等生成地址映射地址映射Load A 200 3456 。 。1200物理地址空間物理地址空間Load A data1data1 3456源程序源程序Load A 200 34560100200編譯編譯連接連接邏輯地址空間邏輯地址空間BA=1000圖41名空間、地址空間、存儲空間7.邏輯地址與物理地址 邏輯地址邏輯地址（相對地址，虛地址）（相對地址，虛地址） ： 用戶的程序經(jīng)過匯編或編譯后形成目標(biāo)代碼，用戶的程序經(jīng)過匯編或編譯后形成目標(biāo)代碼，目標(biāo)代碼通常采用相對地址的形式，其

7、首地目標(biāo)代碼通常采用相對地址的形式，其首地址為址為0 0，其余指令中的地址都相對于首地址而，其余指令中的地址都相對于首地址而編址。編址。 不能用邏輯地址在內(nèi)存中讀取信息不能用邏輯地址在內(nèi)存中讀取信息 物理地址（絕對地址，實地址）物理地址（絕對地址，實地址） 內(nèi)存中存儲單元的地址，可直接尋址內(nèi)存中存儲單元的地址，可直接尋址8.存儲共享 內(nèi)存共享：兩個或多個進(jìn)程共用內(nèi)存中內(nèi)存共享：兩個或多個進(jìn)程共用內(nèi)存中相同區(qū)域相同區(qū)域 目的：節(jié)省內(nèi)存空間，提高內(nèi)存利用率目的：節(jié)省內(nèi)存空間，提高內(nèi)存利用率 實現(xiàn)進(jìn)程通信（數(shù)據(jù)共享）實現(xiàn)進(jìn)程通信（數(shù)據(jù)共享） 共享內(nèi)容：共享內(nèi)容： 代碼共享，要求代碼為純代碼代碼共享，

8、要求代碼為純代碼 數(shù)據(jù)共享數(shù)據(jù)共享9.存儲保護(hù)與安全保護(hù)目的：保護(hù)目的： 為多個程序共享內(nèi)存提供保障為多個程序共享內(nèi)存提供保障, ,使在使在內(nèi)存中的各道程序內(nèi)存中的各道程序, , 只能訪問它自己只能訪問它自己的區(qū)域，避免各道程序間相互干攏，的區(qū)域，避免各道程序間相互干攏，特別是當(dāng)一道程序發(fā)生錯誤時特別是當(dāng)一道程序發(fā)生錯誤時, , 不致不致于影響其他程序的運(yùn)行。通常由硬件于影響其他程序的運(yùn)行。通常由硬件完成保護(hù)功能，由軟件輔助實現(xiàn)。完成保護(hù)功能，由軟件輔助實現(xiàn)。（特權(quán)指令不能完成存儲保護(hù)。）（特權(quán)指令不能完成存儲保護(hù)。）1) 存儲保護(hù) 保護(hù)系統(tǒng)程序區(qū)不被用戶侵犯保護(hù)系統(tǒng)程序區(qū)不被用戶侵犯 （有意

9、或無意的）（有意或無意的） 不允許用戶程序讀寫不屬于自己地址不允許用戶程序讀寫不屬于自己地址空間的數(shù)據(jù)空間的數(shù)據(jù) （系統(tǒng)區(qū)地址空間，其他用（系統(tǒng)區(qū)地址空間，其他用戶程序的地址空間）戶程序的地址空間）2) 保護(hù)過程-防止地址越界 每個進(jìn)程都有自己獨(dú)立的進(jìn)程空間，每個進(jìn)程都有自己獨(dú)立的進(jìn)程空間，如果一個進(jìn)程在運(yùn)行時所產(chǎn)生的地址在如果一個進(jìn)程在運(yùn)行時所產(chǎn)生的地址在其地址空間之外，則發(fā)生地址越界。即其地址空間之外，則發(fā)生地址越界。即當(dāng)程序要訪問某個內(nèi)存單元時，由硬件當(dāng)程序要訪問某個內(nèi)存單元時，由硬件檢查是否允許，如果允許則執(zhí)行，否則檢查是否允許，如果允許則執(zhí)行，否則產(chǎn)生地址越界中斷，由操作系統(tǒng)進(jìn)行相產(chǎn)

10、生地址越界中斷，由操作系統(tǒng)進(jìn)行相應(yīng)處理。應(yīng)處理。10.內(nèi)存“擴(kuò)充” 通過虛擬存儲技術(shù)實現(xiàn)通過虛擬存儲技術(shù)實現(xiàn) 用戶在編制程序時，不應(yīng)該受內(nèi)存容量限用戶在編制程序時，不應(yīng)該受內(nèi)存容量限制，所以要采用一定技術(shù)來制，所以要采用一定技術(shù)來“擴(kuò)充擴(kuò)充”內(nèi)存內(nèi)存的容量，使用戶得到比實際內(nèi)存容量大的的容量，使用戶得到比實際內(nèi)存容量大的多的內(nèi)存空間多的內(nèi)存空間 具體實現(xiàn)是在硬件支持下，軟硬件相互協(xié)具體實現(xiàn)是在硬件支持下，軟硬件相互協(xié)作，將內(nèi)存和外存結(jié)合起來統(tǒng)一使用。通作，將內(nèi)存和外存結(jié)合起來統(tǒng)一使用。通過這種方法把內(nèi)存擴(kuò)充，使用戶在編制程過這種方法把內(nèi)存擴(kuò)充，使用戶在編制程序時不受內(nèi)存限制序時不受內(nèi)存限制4.

11、2 程序的裝入和鏈接圖 4-2-1 對用戶程序的處理步驟4.2.1 程序的裝入 1. 1. 絕對裝入方式絕對裝入方式 程序中所使用的絕對地址，可在編譯程序中所使用的絕對地址，可在編譯或匯編時給出，或匯編時給出， 也可由程序員直接賦予。也可由程序員直接賦予。 但在由程序員直接給出絕對地址時，但在由程序員直接給出絕對地址時， 不僅不僅要求程序員熟悉內(nèi)存的使用情況，而且一要求程序員熟悉內(nèi)存的使用情況，而且一旦程序或數(shù)據(jù)被修改后，可能要改變程序旦程序或數(shù)據(jù)被修改后，可能要改變程序中的所有地址。因此，通常是寧可在程序中的所有地址。因此，通常是寧可在程序中采用符號地址，然后在編譯或匯編時，中采用符號地址，

12、然后在編譯或匯編時，再將這些符號地址轉(zhuǎn)換為絕對地址。再將這些符號地址轉(zhuǎn)換為絕對地址。 2. 可重定位裝入方式圖 4-2-2 作業(yè)裝入內(nèi)存時的情況3. 動態(tài)運(yùn)行時裝入方式 動態(tài)運(yùn)行時的裝入程序，在把裝入模塊動態(tài)運(yùn)行時的裝入程序，在把裝入模塊裝入內(nèi)存后，并不立即把裝入模塊中的相裝入內(nèi)存后，并不立即把裝入模塊中的相對地址轉(zhuǎn)換為絕對地址，而是把這種地址對地址轉(zhuǎn)換為絕對地址，而是把這種地址轉(zhuǎn)換推遲到程序真正要執(zhí)行時才進(jìn)行。因轉(zhuǎn)換推遲到程序真正要執(zhí)行時才進(jìn)行。因此，此， 裝入內(nèi)存后的所有地址都仍是相對地裝入內(nèi)存后的所有地址都仍是相對地址。址。 4.2.2 程序的鏈接圖 4-2-3 程序鏈接示意圖1.靜態(tài)鏈

13、接方式2. 裝入時動態(tài)鏈接裝入時動態(tài)鏈接方式有以下優(yōu)點：裝入時動態(tài)鏈接方式有以下優(yōu)點： 便于修改和更新。便于修改和更新。 (2) (2) 便于實現(xiàn)對目標(biāo)模塊的共享。便于實現(xiàn)對目標(biāo)模塊的共享。3. 運(yùn)行時動態(tài)鏈接這種鏈接方式是將對某些模塊的鏈接推遲到執(zhí)行這種鏈接方式是將對某些模塊的鏈接推遲到執(zhí)行時才執(zhí)行，即，在執(zhí)行過程中，當(dāng)發(fā)現(xiàn)一個被調(diào)時才執(zhí)行，即，在執(zhí)行過程中，當(dāng)發(fā)現(xiàn)一個被調(diào)用模塊尚未裝入內(nèi)存時，立即由用模塊尚未裝入內(nèi)存時，立即由OSOS去找到該模塊去找到該模塊并將之裝入內(nèi)存，并將之裝入內(nèi)存， 把它鏈接到調(diào)用者模塊上。把它鏈接到調(diào)用者模塊上。凡在執(zhí)行過程中未被用到的目標(biāo)模塊，都不會被凡在執(zhí)行過

14、程中未被用到的目標(biāo)模塊，都不會被調(diào)入內(nèi)存和被鏈接到裝入模塊上，這樣不僅可加調(diào)入內(nèi)存和被鏈接到裝入模塊上，這樣不僅可加快程序的裝入過程，而且可節(jié)省大量的內(nèi)存空間?？斐绦虻难b入過程，而且可節(jié)省大量的內(nèi)存空間。4.2.3 重定位 把作業(yè)地址空間中使用的邏輯地址變換成內(nèi)把作業(yè)地址空間中使用的邏輯地址變換成內(nèi)存空間中的物理地址的過程。又稱地址映射。如存空間中的物理地址的過程。又稱地址映射。如下圖，作業(yè)下圖，作業(yè)i i經(jīng)過重定位，把地址集合映射到以經(jīng)過重定位，把地址集合映射到以10001000為始址的內(nèi)存中，作為作業(yè)為始址的內(nèi)存中，作為作業(yè)i i的存儲空間。的存儲空間。1. 重定位的類型1)1)靜態(tài)重定位

15、靜態(tài)重定位: :當(dāng)用戶程序被裝入內(nèi)存時，當(dāng)用戶程序被裝入內(nèi)存時，一次性實現(xiàn)邏輯地址到物理地址的轉(zhuǎn)換，一次性實現(xiàn)邏輯地址到物理地址的轉(zhuǎn)換，以后不再轉(zhuǎn)換（一般在裝入內(nèi)存時由軟以后不再轉(zhuǎn)換（一般在裝入內(nèi)存時由軟件完成）件完成）作業(yè)作業(yè)i i在執(zhí)行前一次變址，直在執(zhí)行前一次變址，直到該作業(yè)完成退出內(nèi)存為止。到該作業(yè)完成退出內(nèi)存為止。2)動態(tài)重定位 在程序運(yùn)行過程中要訪問數(shù)據(jù)時再進(jìn)行地在程序運(yùn)行過程中要訪問數(shù)據(jù)時再進(jìn)行地址變換。由地址變換機(jī)構(gòu)進(jìn)行的地址變換，硬址變換。由地址變換機(jī)構(gòu)進(jìn)行的地址變換，硬件上需要重定位寄存器的支持。件上需要重定位寄存器的支持。2.動態(tài)重定位的實現(xiàn)方式 重定位寄存器：重定位寄存

16、器：在執(zhí)行一條指令取操在執(zhí)行一條指令取操作數(shù)時，要將指令給出的有效地址作數(shù)時，要將指令給出的有效地址(500)(500)與重定位寄存器中的內(nèi)容（與重定位寄存器中的內(nèi)容（10001000）相加，得訪問地址（相加，得訪問地址（15001500），從而實），從而實現(xiàn)了地址動態(tài)修改。現(xiàn)了地址動態(tài)修改。 映象方式映象方式：采用頁表來描述虛、實頁：采用頁表來描述虛、實頁面的對應(yīng)關(guān)系面的對應(yīng)關(guān)系 。4.3 連續(xù)分配存儲管理 4.3.1 4.3.1 單用戶存儲管理單用戶存儲管理 在單道環(huán)境下，不管是單用戶系統(tǒng)還是單道批在單道環(huán)境下，不管是單用戶系統(tǒng)還是單道批處理系統(tǒng)，進(jìn)程（作業(yè)）執(zhí)行時除了系統(tǒng)占用處理系統(tǒng)，進(jìn)

17、程（作業(yè)）執(zhí)行時除了系統(tǒng)占用一部分主存外，剩下的主存區(qū)域全部歸它占用。一部分主存外，剩下的主存區(qū)域全部歸它占用。主存可以劃分為三部分：主存可以劃分為三部分： 系統(tǒng)區(qū)、用戶區(qū)、空系統(tǒng)區(qū)、用戶區(qū)、空閑區(qū)閑區(qū)。用戶占用區(qū)是一個連續(xù)的存儲區(qū)所以又用戶占用區(qū)是一個連續(xù)的存儲區(qū)所以又稱單一連續(xù)區(qū)存儲管理稱單一連續(xù)區(qū)存儲管理。 單用戶系統(tǒng)在一段時間內(nèi)，只有一個進(jìn)程在內(nèi)單用戶系統(tǒng)在一段時間內(nèi)，只有一個進(jìn)程在內(nèi)存，故內(nèi)存分配管理十分簡單，內(nèi)存利用率低。存，故內(nèi)存分配管理十分簡單，內(nèi)存利用率低。內(nèi)存分為兩個區(qū)域，一個供操作系統(tǒng)使用，一內(nèi)存分為兩個區(qū)域，一個供操作系統(tǒng)使用，一個供用戶使用個供用戶使用用戶程序用戶程序

18、位于位于RAM中的中的操作系統(tǒng)操作系統(tǒng)0 xFFF.0位于位于RAM中的中的操作系統(tǒng)操作系統(tǒng)用戶程序用戶程序0ROM中的中的設(shè)備驅(qū)動程序設(shè)備驅(qū)動程序用戶程序用戶程序位于位于RAM中的中的操作系統(tǒng)操作系統(tǒng)0圖圖 4-3-1 4-3-1 單一連續(xù)區(qū)存儲分配示意圖單一連續(xù)區(qū)存儲分配示意圖工作流程 單一連續(xù)區(qū)分配采用靜態(tài)分配和靜態(tài)單一連續(xù)區(qū)分配采用靜態(tài)分配和靜態(tài)重定位方式，亦即作業(yè)或進(jìn)程一旦進(jìn)入重定位方式，亦即作業(yè)或進(jìn)程一旦進(jìn)入主存，就一直等到它運(yùn)行結(jié)束后才能釋主存，就一直等到它運(yùn)行結(jié)束后才能釋放主存。如下圖所示的主存分配與回收放主存。如下圖所示的主存分配與回收法。并且由裝入程序檢查其絕對地址是法。并

19、且由裝入程序檢查其絕對地址是否超越，即可達(dá)到保護(hù)系統(tǒng)的目的。否超越，即可達(dá)到保護(hù)系統(tǒng)的目的。工作流程(續(xù))單用戶系統(tǒng)缺點 不支持多道。不支持多道。 主存利用率不高。主存利用率不高。 程序的運(yùn)行受主存容量限制。程序的運(yùn)行受主存容量限制。存儲保護(hù) 自動地址修改例如，存儲器的地址空間為，自動地址修改例如，存儲器的地址空間為，而操作系統(tǒng)位于低址端的內(nèi)。對于這樣的系統(tǒng)，而操作系統(tǒng)位于低址端的內(nèi)。對于這樣的系統(tǒng)，我們給用戶一個位的地址空間，并對其每個存儲我們給用戶一個位的地址空間，并對其每個存儲器訪問自動加上。如果操作系統(tǒng)占用高址端的器訪問自動加上。如果操作系統(tǒng)占用高址端的，則我們?nèi)∶恳粋€存儲訪問，而實際

20、上，其地址，則我們?nèi)∶恳粋€存儲訪問，而實際上，其地址為為 （）（） 從而實現(xiàn)了對操作系統(tǒng)的保護(hù)。從而實現(xiàn)了對操作系統(tǒng)的保護(hù)。存儲保護(hù)（續(xù)） 頁、頁尋址通過對每個用戶生成頁、頁尋址通過對每個用戶生成的地址左端拼接上一位來實現(xiàn)區(qū)的地址左端拼接上一位來實現(xiàn)區(qū)與用戶區(qū)。把操作系統(tǒng)確定在頁，而與用戶區(qū)。把操作系統(tǒng)確定在頁，而把用戶作業(yè)放在頁。把用戶作業(yè)放在頁。 界限寄存器通過增加界限寄存器，劃界限寄存器通過增加界限寄存器，劃分區(qū)與用戶區(qū)。分區(qū)與用戶區(qū)。4.3.2 固定分區(qū)分配 分分區(qū)式管理是滿足多道程序的最簡單的區(qū)式管理是滿足多道程序的最簡單的存儲管理方案。它的基本思想是將內(nèi)存存儲管理方案。它的基本思想

21、是將內(nèi)存劃分成若干個連續(xù)區(qū)域，稱為分區(qū)。每劃分成若干個連續(xù)區(qū)域，稱為分區(qū)。每個分區(qū)只能存儲一個程序，而且程序也個分區(qū)只能存儲一個程序，而且程序也只能在它所駐留的分區(qū)中運(yùn)行。只能在它所駐留的分區(qū)中運(yùn)行。1. 固定分區(qū) 預(yù)先把可分配的主存儲器空間分割成若預(yù)先把可分配的主存儲器空間分割成若干個連續(xù)區(qū)域，稱為一個分區(qū)。每個分干個連續(xù)區(qū)域，稱為一個分區(qū)。每個分區(qū)的大小可以相同也可以不同，如圖所區(qū)的大小可以相同也可以不同，如圖所示。但分區(qū)大小固定不變，每個分區(qū)裝示。但分區(qū)大小固定不變，每個分區(qū)裝一個且只能裝一個作業(yè)一個且只能裝一個作業(yè) 存儲分配：如果有一個空閑區(qū)存儲分配：如果有一個空閑區(qū), , 則分配則分

22、配給進(jìn)程給進(jìn)程 分區(qū)分區(qū)4分區(qū)分區(qū)3分區(qū)分區(qū)2分區(qū)分區(qū)1操作系統(tǒng)操作系統(tǒng)多個等待隊列多個等待隊列單個等待隊列單個等待隊列分區(qū)分區(qū)4分區(qū)分區(qū)3分區(qū)分區(qū)2分區(qū)分區(qū)1操作系統(tǒng)操作系統(tǒng)圖 4-3-2 固定分區(qū)示意圖 圖圖 4-3-3 4-3-3 固定分區(qū)使用表固定分區(qū)使用表2.內(nèi)存分配管理通過設(shè)置內(nèi)存分配表，內(nèi)存分配簡單通過設(shè)置內(nèi)存分配表，內(nèi)存分配簡單缺點：內(nèi)存利用率不高缺點：內(nèi)存利用率不高 4.3.3 可變（動態(tài)）分區(qū)分配 基本思想：內(nèi)存不是預(yù)先劃分好的，而是基本思想：內(nèi)存不是預(yù)先劃分好的，而是當(dāng)作業(yè)裝入時，根據(jù)作業(yè)的需求和內(nèi)存空當(dāng)作業(yè)裝入時，根據(jù)作業(yè)的需求和內(nèi)存空間的使用情況來決定是否分配。若有足

23、夠間的使用情況來決定是否分配。若有足夠的空間，則按需要分割一部分分區(qū)給該進(jìn)的空間，則按需要分割一部分分區(qū)給該進(jìn)程；否則令其等待主存空間程；否則令其等待主存空間 內(nèi)存管理：設(shè)置內(nèi)存空閑塊表內(nèi)存管理：設(shè)置內(nèi)存空閑塊表記錄了空記錄了空閑區(qū)起始地址和長度閑區(qū)起始地址和長度 內(nèi)存分配：動態(tài)分配內(nèi)存分配：動態(tài)分配 內(nèi)存回收：當(dāng)某一塊歸還后，前后空間合內(nèi)存回收：當(dāng)某一塊歸還后，前后空間合并，修改內(nèi)存空閑塊表并，修改內(nèi)存空閑塊表1.分區(qū)分配中的數(shù)據(jù)結(jié)構(gòu) 分區(qū)分配表（見圖分區(qū)分配表（見圖 4-3-54-3-5）(2) (2) 空閑分區(qū)鏈空閑分區(qū)鏈圖4-3-4空閑鏈結(jié)構(gòu)0K15K38K48K68K80K110K1

24、20K空閑區(qū)表空閑區(qū)表已分配區(qū)表已分配區(qū)表始址始址長度長度標(biāo)志標(biāo)志15K23K未分配未分配48K20K未分配未分配80K30K未分配未分配空空空空始址始址長度長度標(biāo)志標(biāo)志0K15KJ138K10KJ268K12KJ3110K10KJ4空空空空分區(qū)分配表分區(qū)分配表：圖4-3-5分區(qū)分配表分區(qū)分配表0K15K38K48K68K80K110K120K空閑區(qū)表空閑區(qū)表已分配區(qū)表已分配區(qū)表始址始址長度長度標(biāo)志標(biāo)志15K23K未分配未分配48K20K未分配未分配98K12K未分配未分配空空空空始址始址長度長度標(biāo)志標(biāo)志0K15KJ138K10KJ268K12KJ3110K10KJ480K5KJ585K13K

25、J685K98K 2. 分區(qū)分配操作 1) 分配內(nèi)存分配內(nèi)存圖4-3-6內(nèi)存分配流程 2) 回收內(nèi)存圖 4-3-7 內(nèi)存回收時的情況3.空閑分區(qū)鏈表為了實現(xiàn)動態(tài)分配，系統(tǒng)設(shè)立空閑分區(qū)鏈表：每個空為了實現(xiàn)動態(tài)分配，系統(tǒng)設(shè)立空閑分區(qū)鏈表：每個空閑塊的前后兩個單元，放置必要的說明信息和指針。閑塊的前后兩個單元，放置必要的說明信息和指針。系統(tǒng)只要設(shè)立一個鏈?zhǔn)字羔?，指向第一個空閑塊即可。系統(tǒng)只要設(shè)立一個鏈?zhǔn)字羔?，指向第一個空閑塊即可。分配程序可以依照自由塊鏈表，來查找適合的空閑塊分配程序可以依照自由塊鏈表，來查找適合的空閑塊進(jìn)行分配。（如下圖）進(jìn)行分配。（如下圖）4.分配算法 按空閑塊鏈接的方式不同，可

26、以有以下五種按空閑塊鏈接的方式不同，可以有以下五種算法：算法： 最佳適應(yīng)法最佳適應(yīng)法 最壞適應(yīng)法最壞適應(yīng)法 首次適應(yīng)法首次適應(yīng)法 下次適應(yīng)法（循環(huán)首次適應(yīng)法）下次適應(yīng)法（循環(huán)首次適應(yīng)法） 快速適應(yīng)算法快速適應(yīng)算法1)最佳適應(yīng)算法 接到內(nèi)存申請時，在空閑塊表中找到一接到內(nèi)存申請時，在空閑塊表中找到一個不小于請求的最小空塊進(jìn)行分配個不小于請求的最小空塊進(jìn)行分配 為作業(yè)選擇分區(qū)時總是尋找其大小最接為作業(yè)選擇分區(qū)時總是尋找其大小最接近于作業(yè)所要求的存儲區(qū)域。近于作業(yè)所要求的存儲區(qū)域。 特點：用最小空間滿足要求特點：用最小空間滿足要求 要求：空閑分區(qū)按其要求：空閑分區(qū)按其容量從小到大容量從小到大的順的順

27、序排列序排列2)最壞適應(yīng)算法 接到內(nèi)存申請時，在空閑塊表中找到一個接到內(nèi)存申請時，在空閑塊表中找到一個不小于請求的最大空塊進(jìn)行分配，不小于請求的最大空塊進(jìn)行分配，與最佳與最佳適應(yīng)法相反，它在作業(yè)選擇存儲塊時，總適應(yīng)法相反，它在作業(yè)選擇存儲塊時，總是尋找最大的空白區(qū)。是尋找最大的空白區(qū)。 特點：當(dāng)分割后空閑塊仍為較大空塊特點：當(dāng)分割后空閑塊仍為較大空塊 要求：空閑分區(qū)按其要求：空閑分區(qū)按其容量從小到大容量從小到大的順序的順序排列排列分配算法（續(xù)）3)3)首次適應(yīng)法：首次適應(yīng)法： 為作業(yè)選擇分區(qū)時總是從鏈?zhǔn)组_始搜索，為作業(yè)選擇分區(qū)時總是從鏈?zhǔn)组_始搜索，只要找到可以容納該作業(yè)的空白塊，就只要找到可以

28、容納該作業(yè)的空白塊，就把該空白塊分配給該作業(yè)。把該空白塊分配給該作業(yè)。要求：空閑分區(qū)要求：空閑分區(qū)按地址遞增的次序排列按地址遞增的次序排列4)4)下次適應(yīng)法下次適應(yīng)法 類似首次適應(yīng)法每次分區(qū)時，總是從上類似首次適應(yīng)法每次分區(qū)時，總是從上次查找結(jié)束的地方開始，找到一個足夠次查找結(jié)束的地方開始，找到一個足夠大的空白區(qū)分配。大的空白區(qū)分配。要求：空閑分區(qū)要求：空閑分區(qū)按地址遞增的次序排列按地址遞增的次序排列分配算法（續(xù)）5)5)快速適應(yīng)算法快速適應(yīng)算法 該算法又稱分類搜索法。該算法又稱分類搜索法。 是將空閑分區(qū)根據(jù)其容量大小進(jìn)行分是將空閑分區(qū)根據(jù)其容量大小進(jìn)行分類，對于每一類具有相同容量的所有空類，

29、對于每一類具有相同容量的所有空閑分區(qū)，單獨(dú)設(shè)立一個空閑分區(qū)鏈表。閑分區(qū)，單獨(dú)設(shè)立一個空閑分區(qū)鏈表。 同時在內(nèi)存中設(shè)立一張管理索引表，同時在內(nèi)存中設(shè)立一張管理索引表，該表的每一個表項對應(yīng)了一個空閑分區(qū)該表的每一個表項對應(yīng)了一個空閑分區(qū)鏈表表頭。鏈表表頭。5.碎片問題 經(jīng)過一段時間的分配回收后，內(nèi)存中存在經(jīng)過一段時間的分配回收后，內(nèi)存中存在很多很小的空閑塊。它們每一個都很小，很多很小的空閑塊。它們每一個都很小，不足以滿足分配要求；但其總和滿足分配不足以滿足分配要求；但其總和滿足分配要求。這些空閑塊被稱為碎片要求。這些空閑塊被稱為碎片 造成存儲資源的浪費(fèi)造成存儲資源的浪費(fèi)碎片問題的解決 緊湊技術(shù)：通

30、過在內(nèi)存移動程序，將所有緊湊技術(shù)：通過在內(nèi)存移動程序，將所有小的空閑區(qū)域合并為大的空閑區(qū)域小的空閑區(qū)域合并為大的空閑區(qū)域 （緊縮技術(shù)，緊致技術(shù)，浮動技術(shù)，搬（緊縮技術(shù)，緊致技術(shù)，浮動技術(shù)，搬家技術(shù)）家技術(shù)） 問題：開銷大；移動時機(jī)問題：開銷大；移動時機(jī)6.動態(tài)分區(qū)式存儲管理的優(yōu)缺點優(yōu)點：優(yōu)點： 便于動態(tài)申請內(nèi)存便于動態(tài)申請內(nèi)存 便于共享內(nèi)存便于共享內(nèi)存 便于動態(tài)鏈接便于動態(tài)鏈接缺點：缺點：碎片問題碎片問題( (外碎片外碎片) )，內(nèi)存利用率不高，受，內(nèi)存利用率不高，受實際內(nèi)存容量限制實際內(nèi)存容量限制4.3.4 伙伴系統(tǒng)無論已分配或空閑分區(qū)，其大小均為無論已分配或空閑分區(qū)，其大小均為2 2的的K

31、 K次冪。次冪。將空閑分區(qū)根據(jù)分區(qū)的大小進(jìn)行分類，對于每將空閑分區(qū)根據(jù)分區(qū)的大小進(jìn)行分類，對于每一類具有相同大小的所有空閑分區(qū)設(shè)立一個空閑一類具有相同大小的所有空閑分區(qū)設(shè)立一個空閑分區(qū)雙向鏈表。分區(qū)雙向鏈表。設(shè)立一張管理索引表，每個表項指向每個鏈表設(shè)立一張管理索引表，每個表項指向每個鏈表的表頭。的表頭。4.3.5 哈希算法 無論已分配或空閑分區(qū)，其大小均為無論已分配或空閑分區(qū)，其大小均為2 2的的K K次冪。次冪。 將空閑分區(qū)根據(jù)分區(qū)的大小進(jìn)行分類，對于每將空閑分區(qū)根據(jù)分區(qū)的大小進(jìn)行分類，對于每一類具有相同大小的所有空閑分區(qū)設(shè)立一個空一類具有相同大小的所有空閑分區(qū)設(shè)立一個空閑分區(qū)雙向鏈表。閑分區(qū)雙向鏈表。 構(gòu)造一張以空閑分區(qū)大小為關(guān)鍵字的哈希表，構(gòu)造一張以空閑分區(qū)大小為關(guān)鍵字的哈希表，該表的每一個表項記錄一個對應(yīng)的空閑分區(qū)鏈該表的每一個表項記錄一個對應(yīng)的空閑分區(qū)鏈表表頭。表表頭。 當(dāng)進(jìn)行空閑分區(qū)分配時，根據(jù)空閑分區(qū)大小，當(dāng)進(jìn)行空閑分區(qū)分配時，根據(jù)空閑分區(qū)大小，通過哈希函數(shù)計算即可。通過哈希函數(shù)計算即可。 4.3.6 可重定位分區(qū)分配1. 動態(tài)重定位的引入動態(tài)重定位的引入圖 4-3-1 緊湊的示意圖 4-3-2 動態(tài)重定位示意圖2. 動態(tài)重定位的實現(xiàn)3. 動態(tài)重定位分區(qū)分配算法圖 4-3-3 動態(tài)分區(qū)分配算法流程圖4.可重定位分區(qū)的優(yōu)缺點 優(yōu)點優(yōu)點: :解決了可變分區(qū)分配