1、第四章存儲器管理 第四章存儲器管理 4.1 存儲器的層次結構存儲器的層次結構 4.2程序的裝入和鏈接程序的裝入和鏈接 4.3連續分配存儲管理方式連續分配存儲管理方式4.4 對換對換4.4分頁存儲管理方式分頁存儲管理方式4.5分段存儲管理方式分段存儲管理方式第四章存儲器管理 4.1 存儲器的層次結構存儲器的層次結構 一、多級存儲器結構一、多級存儲器結構 在現代計算機系統在現代計算機系統中，存儲器是信息中，存儲器是信息的來源與歸宿，占據重的來源與歸宿，占據重要位置。但是，在現有要位置。但是，在現有技術條件下，任何一種技術條件下，任何一種存儲裝置，都無法同時存儲裝置，都無法同時從速度與容量兩方面，從

2、速度與容量兩方面，滿足用戶的需求。實際滿足用戶的需求。實際上它們組成了一個速度上它們組成了一個速度由快到慢，容量由小到由快到慢，容量由小到大的存儲裝置層次。大的存儲裝置層次。 寄存器高速緩存主存磁盤緩存磁盤可移動存儲介質CPU寄存器主存輔存圖圖4-1 計算機系統存儲層次示意計算機系統存儲層次示意 速速度度快快慢慢小小大大容容量量OS管理管理設備管理設備管理第四章存儲器管理 二、各種存儲器二、各種存儲器1 1主存儲器主存儲器簡稱內存、主存、簡稱內存、主存、可執行存儲器；可執行存儲器；主要部件，保存進程運行時的程主要部件，保存進程運行時的程序和數據，序和數據，若干兆字節、中等速度、中等價格。若干兆

3、字節、中等速度、中等價格。 主存儲器的訪問速度遠低于主存儲器的訪問速度遠低于CPU執行指令的速度，為緩和這一矛盾，執行指令的速度，為緩和這一矛盾，在計算機系統中引入了寄存器和高速緩存。在計算機系統中引入了寄存器和高速緩存。 2 2寄存器寄存器速度最快，價格昂貴，容量小。以字速度最快，價格昂貴，容量小。以字(word)為單位。寄存器用于加為單位。寄存器用于加速存儲器的訪問速度，如：用寄存器存放操作數。速存儲器的訪問速度，如：用寄存器存放操作數。3高速緩存高速緩存 少量的、容量小（幾十少量的、容量小（幾十KB幾幾MB ）、非常快速、昂貴。）、非常快速、昂貴。 主存中常訪問的信息存放在高速緩存中，減

4、少訪主次數。主存中常訪問的信息存放在高速緩存中，減少訪主次數。第四章存儲器管理 4 4磁盤緩存磁盤緩存目前磁盤的目前磁盤的I/OI/O速度遠低于對主存的訪問速度，將速度遠低于對主存的訪問速度，將頻繁使用頻繁使用的一部分的一部分磁盤數據和信息，暫時存放在磁盤緩存中，可減少訪問磁盤的次數。磁盤數據和信息，暫時存放在磁盤緩存中，可減少訪問磁盤的次數。 即利用主存中的存儲空間，來暫存從磁盤中讀出即利用主存中的存儲空間，來暫存從磁盤中讀出( (或寫入或寫入) )的信息。的信息。 掉電則丟失。掉電則丟失。文件文件硬盤硬盤存放存放內存內存調入調入磁盤磁盤緩沖緩沖備備份份磁帶磁帶文件出文件出現于不現于不同的存

5、同的存儲層次儲層次中中第四章存儲器管理 三、存儲管理的目的三、存儲管理的目的 1) 1) 主存的分配和管理主存的分配和管理 當用戶需要內存時，系統為之分配相應的存儲空間；不需要時，及時回收，當用戶需要內存時，系統為之分配相應的存儲空間；不需要時，及時回收，以供其它用戶使用。以供其它用戶使用。 2) 2) 提高主存儲器的利用率提高主存儲器的利用率 不僅能使多道程序動態地共享主存，提高主存利用率，最好還能共享主存不僅能使多道程序動態地共享主存，提高主存利用率，最好還能共享主存中某個區域的信息。中某個區域的信息。 3) 3) “擴充擴充”主存容量主存容量 為用戶提供比為用戶提供比主存物理空間主存物理

6、空間大得多的大得多的地址空間地址空間，以至使用戶感覺他的作業，以至使用戶感覺他的作業是在這樣一個大的存儲器中運行。是在這樣一個大的存儲器中運行。 4) 4) 存儲保護存儲保護 確保多道程序都在各自分配到存儲區域內操作，互不干擾，防止一道程序確保多道程序都在各自分配到存儲區域內操作，互不干擾，防止一道程序破壞其它作業或系統文件的信息。破壞其它作業或系統文件的信息。第四章存儲器管理 四、預備知識（補充）四、預備知識（補充）1.1.定位（存儲分配）定位（存儲分配） 為具體的程序和數據等為具體的程序和數據等分配分配存儲單元或存儲區工作。存儲單元或存儲區工作。2.2.映射映射 把邏輯地址轉換為相應的物理

7、地址的過程。把邏輯地址轉換為相應的物理地址的過程。3.3.隔離隔離 按按存取權限存取權限把合法區與非法區分隔，實現存儲保護。把合法區與非法區分隔，實現存儲保護。第四章存儲器管理 4.名空間名空間程序員在程序中定義的標識符程序員在程序中定義的標識符程序符號集合程序符號集合由程序員自定義由程序員自定義沒有地址的概念沒有地址的概念符號指令符號指令數據說明數據說明I/OI/O說明說明第四章存儲器管理 5、邏輯地址、邏輯地址空間、邏輯地址、邏輯地址空間邏輯地址邏輯地址 (相對地址、虛地址相對地址、虛地址) 用戶的程序經過匯編或編譯后形成目標代碼，用戶的程序經過匯編或編譯后形成目標代碼，目標代碼通常采用相

8、對地址的形式，其首地址目標代碼通常采用相對地址的形式，其首地址為為0，其余指令中的地址都相對于首地址而編，其余指令中的地址都相對于首地址而編址。址。用戶的程序地址用戶的程序地址(指令地址或操作數地址指令地址或操作數地址)均為均為邏輯地址。邏輯地址。不能用邏輯地址在內存中讀取信息。不能用邏輯地址在內存中讀取信息。(why)作業地址空間（作業邏輯地址空間、作業虛空間）作業地址空間（作業邏輯地址空間、作業虛空間） 用戶程序所有的邏輯地址集合對應的空間。用戶程序所有的邏輯地址集合對應的空間。由編譯程序生成由編譯程序生成作業地址空間作業地址空間01 n-1 指令、數據指令、數據mov r1,500123

9、0100500599作業地址空間作業地址空間第四章存儲器管理 6、物理地址、物理地址空間、物理地址、物理地址空間物理地址物理地址 (絕對地址、實地址絕對地址、實地址) 物理地址是計算機主存單元的真物理地址是計算機主存單元的真實地址，又稱為絕對地址或實地實地址，又稱為絕對地址或實地址。址。 可直接尋址。可直接尋址。主存空間（物理地址空間、存儲空主存空間（物理地址空間、存儲空間）間） 物理地址的集合所對應的空間組物理地址的集合所對應的空間組成了主存空間。成了主存空間。主存空間主存空間01 n-1 第四章存儲器管理 地址映射地址映射Load A 200 3456 。 。1200物理地址空間物理地址空

10、間Load A data1data1 3456名空間名空間Load A 200 34560100200編譯編譯連接連接邏輯地址空間邏輯地址空間BA=1000圖圖: : 名空間、地址空間、存儲空間名空間、地址空間、存儲空間源程序源程序目標程序目標程序可執行程序可執行程序第四章存儲器管理 7.7.存儲共享存儲共享內存共享：內存共享： 兩個或多個進程共用內存中相同區。兩個或多個進程共用內存中相同區。目的：目的： 節省內存空間，提高內存利用率。節省內存空間，提高內存利用率。實現進程通信：實現進程通信： 數據共享。數據共享。共享內容：共享內容：代碼共享。代碼共享。 數據共享。數據共享。第四章存儲器管理

11、8.8.存儲保護與安全存儲保護與安全1) 1) 保護目的保護目的為多個程序共享內存提供保障為多個程序共享內存提供保障, ,使在內存中的各道程序使在內存中的各道程序, , 只能訪只能訪問它自己的區域，避免各道程序間相互干攏，特別是當一道程序發問它自己的區域，避免各道程序間相互干攏，特別是當一道程序發生錯誤時生錯誤時, , 不致于影響其他程序的運行。不致于影響其他程序的運行。通常由硬件完成保護功能，通常由硬件完成保護功能，由軟件輔助實現。由軟件輔助實現。特權指令不能完成存儲保護。特權指令不能完成存儲保護。2) 2) 存儲保護存儲保護.保護系統程序區不被用戶侵犯。保護系統程序區不被用戶侵犯。（有意或

12、無意的）（有意或無意的）.不允許用戶程序讀寫不屬于自己地址空間的數據。不允許用戶程序讀寫不屬于自己地址空間的數據。 （系統區地址空間，其他用戶程序的地址空間）（系統區地址空間，其他用戶程序的地址空間）3) 3) 保護過程保護過程-防止地址越界防止地址越界每個進程都有自己獨立的進程空間，如果一個進程在運行時所產每個進程都有自己獨立的進程空間，如果一個進程在運行時所產生的地址在其地址空間之外，則發生地址越界。即當程序要訪問某生的地址在其地址空間之外，則發生地址越界。即當程序要訪問某個內存單元時，由個內存單元時，由硬件檢查硬件檢查是否允許，如果允許則執行，否則產生是否允許，如果允許則執行，否則產生地

13、址越界中斷，由操作系統進行相應處理。地址越界中斷，由操作系統進行相應處理。第四章存儲器管理 9.9.內存內存“擴充擴充” 通過虛擬存儲技術實現通過虛擬存儲技術實現 用戶在編制程序時，不應該用戶在編制程序時，不應該受內存容量限制受內存容量限制，所以要采用一定技術來，所以要采用一定技術來“擴充擴充”內存的容量，使用戶得到比實際內存容量大的多的內存空間。內存的容量，使用戶得到比實際內存容量大的多的內存空間。具體實現是在硬件支持下，軟硬件相互協作，將內存和外存結合起來具體實現是在硬件支持下，軟硬件相互協作，將內存和外存結合起來統一使用。通過這種方法把內存擴充，使用戶在編制程序時不受內存統一使用。通過這

14、種方法把內存擴充，使用戶在編制程序時不受內存限制。限制。第四章存儲器管理 4.2 4.2 程序的裝入和鏈接程序的裝入和鏈接 在多道程序環境下，要使在多道程序環境下，要使程序運行，必須創建進程，而程序運行，必須創建進程，而創建進程第一件事就是將程序創建進程第一件事就是將程序和數據裝入內存。一個用戶源和數據裝入內存。一個用戶源程序要程序要變為變為在內存中可執行的在內存中可執行的程序，通常要進行以下處理程序，通常要進行以下處理： （1 1）編譯：編譯：由編譯程序將由編譯程序將用戶源程序編譯成若干個目標用戶源程序編譯成若干個目標模塊模塊 （2 2）鏈接鏈接：由鏈接程序將由鏈接程序將目標模塊和相應的庫函

15、數鏈接目標模塊和相應的庫函數鏈接成裝入模塊成裝入模塊 （3 3）裝入裝入：由裝入程序將由裝入程序將裝入模塊裝入內存裝入模塊裝入內存庫目標程序塊1目標程序塊2第一步鏈接程序裝入模塊(.exe)第二步裝入程序第三步用戶源程序(.c;.c+)編譯程序.obj第四章存儲器管理 一、程序的裝入一、程序的裝入( (由裝入程序將裝入模塊由裝入程序將裝入模塊(exe(exe文件文件) )裝入內存裝入內存) )1 1絕對裝入方式絕對裝入方式(Absolute Loading Mode)(Absolute Loading Mode)（早期）（早期）如果在編譯時，如果在編譯時，事先知事先知用戶程序在內存的駐留位置，

16、則編譯程序用戶程序在內存的駐留位置，則編譯程序在編譯時就產生絕對地址的目標代碼。裝入程序就直接把裝入模塊中在編譯時就產生絕對地址的目標代碼。裝入程序就直接把裝入模塊中的程序和數據裝入到指定的位置，（不需進行地址轉換）的程序和數據裝入到指定的位置，（不需進行地址轉換） 該裝入方式只適用于該裝入方式只適用于單道程序環境單道程序環境。第四章存儲器管理 2可重定位裝入方式可重定位裝入方式(Relocation Loading Mode) 在多道程序環境下，目標模塊中的其它地址都是相對于在多道程序環境下，目標模塊中的其它地址都是相對于0 0編址。應根據編址。應根據內存的當前情況，將裝入模塊裝入到內存的適

17、當位置。內存的當前情況，將裝入模塊裝入到內存的適當位置。 通常是把通常是把在裝入時在裝入時對目標程序中指令和數據的修改過程稱為對目標程序中指令和數據的修改過程稱為重定位重定位。 圖圖4-3作業裝入內存時的情況作業裝入內存時的情況LOAD 1,2500365LOAD 1,2500365100001100012500150005000250010000作業地址空間內存空間修改指令地址修改指令地址修改數據地址修改數據地址指令中的相對指令中的相對地址是否要修改？地址是否要修改？ 裝入模裝入模塊中所有塊中所有的邏輯地的邏輯地址與實際址與實際裝入內存裝入內存的物理地的物理地址不同。址不同。從此裝入從此裝入

18、第四章存儲器管理 物理地址物理地址基地址基地址相對地址相對地址地址變換在裝入地址變換在裝入時一次完成，以時一次完成，以后不改變，靜態后不改變，靜態再定位。再定位。是否允許程序是否允許程序運行時在內存運行時在內存中移動位置？中移動位置？第四章存儲器管理 3 3動態運行時裝入方式動態運行時裝入方式(Dynamic Run-time Loading)(Dynamic Run-time Loading)可重定位裝入方式可重定位裝入方式: : 裝入模塊裝入到內存中任何允許的位置。裝入模塊裝入到內存中任何允許的位置。不允許程序運行時在內存中不允許程序運行時在內存中移動位置移動位置。 實際情況：實際情況：程

19、序程序在運行過程中它在內存中的位置在運行過程中它在內存中的位置可能經常要改變可能經常要改變。 動態運行時的裝入程序，在把裝入模塊裝入內存后，并動態運行時的裝入程序，在把裝入模塊裝入內存后，并不不立即把立即把裝入模塊中的裝入模塊中的相對地址轉換為絕對地址相對地址轉換為絕對地址，而是把這種地址轉換推遲到程序，而是把這種地址轉換推遲到程序真正要真正要執行時執行時才進行。因此，才進行。因此， 裝入內存后的所有地址都仍是相對地址。裝入內存后的所有地址都仍是相對地址。 第四章存儲器管理 二、程序的鏈接二、程序的鏈接根據鏈接時間的不同，程序鏈接分成三種：根據鏈接時間的不同，程序鏈接分成三種：(1) (1)

20、靜態鏈接。靜態鏈接。(2) (2) 裝入時動態鏈接。裝入時動態鏈接。 (3) 運行時動態鏈接。運行時動態鏈接。第四章存儲器管理 1 1靜態鏈接方式靜態鏈接方式(Static Linking)(Static Linking)圖圖 4-4程序鏈接示意圖程序鏈接示意圖 模塊 ACALL B；Return；0L-1模塊 BCALL C；Return；0M-1模塊 CReturn；0N-10模塊 AJSR“L”Return；L-1模塊 BJSR“LM”Return；LL+M-1L+ML+M+N-1模塊 CReturn；(a ) 目標模塊(b ) 裝入模塊 是一種是一種事先鏈接方式事先鏈接方式，即在程序運

21、行之前，先將各目標模塊及它們，即在程序運行之前，先將各目標模塊及它們所需的庫函數，鏈接成一個完整的裝入模塊所需的庫函數，鏈接成一個完整的裝入模塊( (執行文件執行文件) )，以后不再拆開。，以后不再拆開。 實現靜態鏈接應解決的問題：實現靜態鏈接應解決的問題： （1 1）相對地址的修改）相對地址的修改 （2 2）變換外部調用符號）變換外部調用符號 存在問題：存在問題：（1 1）不便于對目標模塊的修改和更新。）不便于對目標模塊的修改和更新。 如要更新其中一個模塊，如要更新其中一個模塊， 需要打開裝入模塊。需要打開裝入模塊。（2 2）無法實現對目標模塊的共享。）無法實現對目標模塊的共享。PPAB靜態

22、靜態鏈接鏈接第四章存儲器管理 2 2裝入時動態鏈接裝入時動態鏈接(Load-time Dynamic Linking)(Load-time Dynamic Linking) 將用戶源程序編譯后所得到的將用戶源程序編譯后所得到的一組目標模塊一組目標模塊，在裝入內存時，采，在裝入內存時，采用邊裝入邊鏈接的鏈接方式。用邊裝入邊鏈接的鏈接方式。 優點：優點： (1) (1) 便于修改和更新。便于修改和更新。各目標模塊是分開存放的各目標模塊是分開存放的;修改容易；修改容易； (2) (2) 便于實現對目標模塊的共享。便于實現對目標模塊的共享。PPAB靜態靜態鏈接鏈接PAB裝入裝入時動時動態鏈態鏈接接存在

23、問題：存在問題： 由于程序運行所有由于程序運行所有可能用的目標模塊可能用的目標模塊在裝入時均全部鏈接在裝入時均全部鏈接在一起，所以將會把一些不會運行的目標模塊也鏈接進去。如在一起，所以將會把一些不會運行的目標模塊也鏈接進去。如程序中的錯誤處理模塊。程序中的錯誤處理模塊。第四章存儲器管理 3 3運行時動態鏈接運行時動態鏈接(Run-time Dynamic Linking)(Run-time Dynamic Linking) 定義：定義： 對某些模塊的鏈接對某些模塊的鏈接推遲到程序執行推遲到程序執行時才進行鏈接。時才進行鏈接。 在執行過程中，當發現一個被調用模塊尚未裝入內存時，立即在執行過程中，

24、當發現一個被調用模塊尚未裝入內存時，立即由由OS去找到該模塊并將之裝入內存，把它鏈接到調用者模塊上。去找到該模塊并將之裝入內存，把它鏈接到調用者模塊上。凡在凡在執行過程中未被用到的目標模塊，執行過程中未被用到的目標模塊，都不會被調入內存和被鏈接到裝入模都不會被調入內存和被鏈接到裝入模塊上，這樣不僅可加快程序的裝入過程，而且可節省大量的內存空間。塊上，這樣不僅可加快程序的裝入過程，而且可節省大量的內存空間。 第四章存儲器管理 三、重定位三、重定位 地址映射：地址映射： 把作業地址空間中使用的把作業地址空間中使用的邏輯地址邏輯地址變換成內存空間中的變換成內存空間中的物理地址物理地址的的過程。如下圖

25、，作業過程。如下圖，作業i i經過重定位，把地址集合映射到以經過重定位，把地址集合映射到以10001000為始址的為始址的內存中，作為作業內存中，作為作業i i的存儲空間。的存儲空間。作業作業i第四章存儲器管理 1. 重定位的類型重定位的類型 1) ) 靜態重定位靜態重定位 當用戶程序被裝入內存時，當用戶程序被裝入內存時，一次性一次性實現邏輯地址到物理實現邏輯地址到物理地址的轉換，以后不再轉換（一般在裝入內存時由軟件完地址的轉換，以后不再轉換（一般在裝入內存時由軟件完成），成），作業作業i在執行前在執行前一次變址，直到該作業完成退出內存為一次變址，直到該作業完成退出內存為止。止。 第四章存儲器

26、管理 2)動態重定位動態重定位 在程序運行過程中要在程序運行過程中要訪問數據時訪問數據時再進行地址變換。由地址變換再進行地址變換。由地址變換機構進行的地址變換，硬件上需要重定位寄存器的支持。機構進行的地址變換，硬件上需要重定位寄存器的支持。 重定位寄存器：重定位寄存器：在執行一條指令取操作數時，要將指令給出的有效在執行一條指令取操作數時，要將指令給出的有效地址地址(500)(500)與重定位寄存器中的內容（與重定位寄存器中的內容（10001000）相加，得訪問地址）相加，得訪問地址（15001500），從而實現了地址動態修改。），從而實現了地址動態修改。裝入裝入時未時未修改修改第四章存儲器管理

27、 4.3連續分配存儲管理方式連續分配存儲管理方式 一、單一連續分配方式一、單一連續分配方式 最簡單的一種存儲管理方式，但只最簡單的一種存儲管理方式，但只能用于能用于單用戶、單任務的單用戶、單任務的OSOS中。中。存儲管理方法存儲管理方法：將內存分為：將內存分為系統區系統區（內存（內存低端，分配給低端，分配給OSOS用）和用）和用戶區用戶區（內存高端，（內存高端，分配給用戶用）。采用靜態分配方式，即分配給用戶用）。采用靜態分配方式，即作業一旦進入內存，就要等待它運行結束作業一旦進入內存，就要等待它運行結束后才能釋放內存。后才能釋放內存。主要特點主要特點：管理簡單，只需小量的軟件和管理簡單，只需小

28、量的軟件和硬件支持，便于用戶了解和使用。但因內硬件支持，便于用戶了解和使用。但因內存中只裝入一道作業運行，內存空間浪費存中只裝入一道作業運行，內存空間浪費大，各類資源的利用率也不高。大，各類資源的利用率也不高。系統區-os用戶區用戶程序第四章存儲器管理 工作流程工作流程 單一連續區分配采用單一連續區分配采用靜態重定位方式靜態重定位方式，即作業或進程一旦進入主，即作業或進程一旦進入主存，就一直等到它運行結束后才能釋放主存。下圖所示的主存分配與存，就一直等到它運行結束后才能釋放主存。下圖所示的主存分配與回收法。并且由回收法。并且由裝入程序檢查裝入程序檢查其絕對地址是否越界，即可達到保護系其絕對地址

29、是否越界，即可達到保護系統的目的。統的目的。缺點：缺點： 不支持多道。不支持多道。 主存利用率不高。主存利用率不高。 程序的運行受主存容量限制。程序的運行受主存容量限制。第四章存儲器管理 分區分配方式存儲管理分區分配方式存儲管理 分區分配方式分區分配方式是滿足是滿足多道多道程序設計需要的一種最簡單的存儲程序設計需要的一種最簡單的存儲管理方法。管理方法。存儲管理方法存儲管理方法 將內存分成若干個分區（大小相等將內存分成若干個分區（大小相等/ /不相等），除不相等），除OSOS占一區外，占一區外，其余的每一個分區容納一個用戶程序。按分區的變化情況，可將其余的每一個分區容納一個用戶程序。按分區的變化

30、情況，可將分區存儲管理進一步分為：分區存儲管理進一步分為： 固定分區存儲管理固定分區存儲管理 動態分區存儲管理動態分區存儲管理第四章存儲器管理 二、固定分區分配二、固定分區分配（固定分區存儲管理）固定分區存儲管理） 是最早使用的一種可運行多道程序的存儲管理方法是最早使用的一種可運行多道程序的存儲管理方法。 存儲管理方法存儲管理方法 內存空間的劃分內存空間的劃分：將內存空間劃分為若干個固定大小的分區，將內存空間劃分為若干個固定大小的分區，除除OSOS占一區外，其余的一個分區裝入一道程序。分區的大小占一區外，其余的一個分區裝入一道程序。分區的大小可以相等，也可以不等，但事先必須確定，在運行時不能改

31、可以相等，也可以不等，但事先必須確定，在運行時不能改變。即變。即分區大小及邊界在運行時不能改變分區大小及邊界在運行時不能改變。 系統需系統需建立一張分區說明表或使用表建立一張分區說明表或使用表，以記錄分區號、分區以記錄分區號、分區大小、分區的起始地址及狀態（已分配或未分配）大小、分區的起始地址及狀態（已分配或未分配）。第四章存儲器管理 固定分區分配方式示意圖固定分區分配方式示意圖os用戶程序p4p1p20k20k56k65k125k135k區號區號大小大小起址起址狀態狀態136k20k已分配已分配29k56k未分配未分配360k65k已分配已分配410k125k已分配已分配分區說明表分區說明表

32、第四章存儲器管理 分區分區4分區分區3分區分區2分區分區1操作系統操作系統多個等待隊列多個等待隊列單個等待隊列單個等待隊列分區分區4分區分區3分區分區2分區分區1操作系統操作系統圖：固定分區示意圖圖：固定分區示意圖第四章存儲器管理 內存分配內存分配 當某個用戶程序要裝入內存時，由內存分配程序當某個用戶程序要裝入內存時，由內存分配程序檢索分區說檢索分區說明表明表，從表中找出一個滿足要求的尚未分配的分區分配該程，從表中找出一個滿足要求的尚未分配的分區分配該程序，同時序，同時修改說明表修改說明表中相應分區的狀態；若找不到大小足夠中相應分區的狀態；若找不到大小足夠的分區，則拒絕為該程序分配內存。的分區

33、，則拒絕為該程序分配內存。 當程序執行完畢，釋放占用的分區，管理程序將修改說明表當程序執行完畢，釋放占用的分區，管理程序將修改說明表中相應分區的狀態為未分配，實現內存資源的回收。中相應分區的狀態為未分配，實現內存資源的回收。主要特點主要特點：管理簡單，但因作業的大小并管理簡單，但因作業的大小并不一定與某個分區大不一定與某個分區大小相等小相等，從而使一部分存儲空間被浪費。所以主存的利用率不高。，從而使一部分存儲空間被浪費。所以主存的利用率不高。例例 題題操作系統作業A作業B作業C24 KB32 KB64 KB128 KB256 KB分區號大小/KB起址/KB狀態11220已分配23232已分配3

34、6464已分配4128128未分配(b) 存儲空間分配情況(a) 分區說明表分配分配回收回收第四章存儲器管理 例：例：在某系統中，采用固定分區分配管理方式，內存分區（單位字在某系統中，采用固定分區分配管理方式，內存分區（單位字節）情況如圖所示，現有大小為節）情況如圖所示，現有大小為1K1K、9K9K、33K33K、121K121K的多個作業要求進的多個作業要求進入內存，試畫出它們進入內存后的空間分配情況，并說明主存浪費多大？入內存，試畫出它們進入內存后的空間分配情況，并說明主存浪費多大？10k20k28k60k180k511k234（1）內存分區圖內存分區圖os區號區號大小大小起址起址狀態狀態

35、1 18k8k20k20k未分配未分配2 232k32k28k28k未分配未分配3 3120k120k60k60k未分配未分配4 4331k331k180k180k未分配未分配（2）分區說明表）分區說明表第四章存儲器管理 區號區號 大小大小起址起址狀態狀態18k20k已分配已分配232k28k已分配已分配3120k60k已分配已分配4331k180k已分配已分配（2）分區說明表）分區說明表0k20k28k60k180k511k23(1)內存分配圖內存分配圖(3)主存浪費空間主存浪費空間=(8-1)+(32-9)+(120-33)+(331-121) =7+23+87+210=327(k)解：解

36、：根據分區說明表，將根據分區說明表，將4個分區依次分配給個分區依次分配給4個作業，同時個作業，同時修改分區說明表，其內存分配和分區說明表如下所示：修改分區說明表，其內存分配和分區說明表如下所示：1K9K33K121K結論：浪費嚴重；產生內部碎片結論：浪費嚴重；產生內部碎片第四章存儲器管理 三、動態分區分配方式三、動態分區分配方式 動態分區分配又稱為動態分區分配又稱為可變式分區分配可變式分區分配，是一種動態劃分存儲器，是一種動態劃分存儲器的分區方法。的分區方法。存儲管理方法存儲管理方法 不事先將內存劃分成一塊塊的分區，而是在作業進入內存時，不事先將內存劃分成一塊塊的分區，而是在作業進入內存時，根

37、據根據作業的大小作業的大小動態地建立分區，并使分區的大小動態地建立分區，并使分區的大小正好適應正好適應作業的需作業的需要。因此系統中分區的大小是要。因此系統中分區的大小是可變的可變的，分區的數目分區的數目也是可變的。也是可變的。 主要特點主要特點 管理簡單，只需小量的軟件和硬件支持，便于用戶了解和使用。管理簡單，只需小量的軟件和硬件支持，便于用戶了解和使用。進程的大小與某個分區大小相等，從而主存的利用率有所提高。進程的大小與某個分區大小相等，從而主存的利用率有所提高。第四章存儲器管理 1 1、分區分配中的數據結構、分區分配中的數據結構空閑分區表空閑分區表 用來登記系統中的空閑分區用來登記系統中

38、的空閑分區( (分區號分區號, ,分區起始地址分區起始地址, ,分區大小及狀態分區大小及狀態). ). 分區號分區號大小大小KBKB起始地址起始地址KBKB狀態狀態1閑空閑2 2空表目空表目3 3520520504504空閑空閑4 4空表目空表目5 5空閑分區鏈空閑分區鏈 用用鏈頭指針鏈頭指針將系統中的空閑分區鏈接起來，構成空閑分區鏈。每個將系統中的空閑分區鏈接起來，構成空閑分區鏈。每個空閑分區的起始部分存放相應的控制信息空閑分區的起始部分存放相應的控制信息( (如大小如大小, ,指向下一空閑分區的指向下一空閑分區的指針等指針等).).352KB504KB504KB3

39、2KB32KB 520KB520KB空閑分區鏈頭指針空閑分區鏈頭指針第四章存儲器管理 2 2、分區分配算法、分區分配算法 為了將一個作業裝入內存，應按照一定的分配算法從空閑分區為了將一個作業裝入內存，應按照一定的分配算法從空閑分區表（鏈）中選出一個滿足作業需求的分區分配給作業，如果這個空表（鏈）中選出一個滿足作業需求的分區分配給作業，如果這個空閑分區的容量比作業申請的閑分區的容量比作業申請的空間要大空間要大，則將該分區，則將該分區一分為二一分為二，一部，一部分分配給作業，剩下的部分仍然留在空閑分區表（鏈）中，同時修分分配給作業，剩下的部分仍然留在空閑分區表（鏈）中，同時修改空閑分區表（鏈）中相

40、應的信息。目前常用分配算法有：改空閑分區表（鏈）中相應的信息。目前常用分配算法有：q首次適應算法首次適應算法q循環首次適應算法循環首次適應算法q最佳適應算法最佳適應算法q最壞適應算法最壞適應算法第四章存儲器管理 首次適應算法（最先適應算法）首次適應算法（最先適應算法）算法算法 空閑分區（鏈）按地址遞增空閑分區（鏈）按地址遞增的次序排列。在進行內存分的次序排列。在進行內存分配時配時, ,從空閑分區表從空閑分區表/ /鏈首鏈首開始順序查找開始順序查找, ,直到找到第一個滿足直到找到第一個滿足其大小要求的空閑分區為止。然后再按照作業大小，從該分其大小要求的空閑分區為止。然后再按照作業大小，從該分區中

41、劃出一塊內存空間分配給請求者，區中劃出一塊內存空間分配給請求者，余下余下的空閑分區仍留的空閑分區仍留在空閑分區表（鏈）中。在空閑分區表（鏈）中。第四章存儲器管理 區號區號大小大小起址起址132k20k28k52k3120k60k4331k180k空閑分區表空閑分區表解：解：按按首次適應算法首次適應算法， 申請作業申請作業100k，分配分配3號分區，剩下分區為號分區，剩下分區為20k，起始地址，起始地址160K ； 申請作業申請作業30k， 分配分配1號分區，剩下分區為號分區，剩下分區為2k，起始地址，起始地址50K ； 申請作業申請作業7k， 分配分配2號分區，剩下分區為號分區，剩下分區為1k

42、，起始地址，起始地址59K ；其內存分配圖及分配后空閑分區表如下其內存分配圖及分配后空閑分區表如下:例例 ：系統中的空閑分區表如下，現有三個作業分配申請內存空間系統中的空閑分區表如下，現有三個作業分配申請內存空間100K、30K及及7K。給出按首次適應算法的內存分配情況及分配后空閑。給出按首次適應算法的內存分配情況及分配后空閑分區表。分區表。第四章存儲器管理 區號區號大小大小起址起址12k50k21k59k320k160k4331k380k(3)該算法分配后的空閑分區表該算法分配后的空閑分區表0k20k52k60k180k511k(1)內存分配圖內存分配圖50K59K160K380Kv首次適應

43、算法的特點首次適應算法的特點 優先利用優先利用內存低地址部分的空閑分區內存低地址部分的空閑分區, ,從而保留了高地址部分的大空閑區。從而保留了高地址部分的大空閑區。但由于但由于低地址部分不斷被劃分低地址部分不斷被劃分, ,致使低地址端留下許多難以利用的很小的空閑分致使低地址端留下許多難以利用的很小的空閑分區區( (碎片或零頭碎片或零頭),),而每次查找又都是從低地址部分開始而每次查找又都是從低地址部分開始, ,這無疑這無疑增加了查找可用增加了查找可用空閑分區的開銷。空閑分區的開銷。區號區號大小大小起址起址132k20k28k52k3120k60k4331k180k(2)分配前空閑分區表分配前空

44、閑分區表三個作業分配申請內存空間三個作業分配申請內存空間100K、30K及及7K。第四章存儲器管理 循環首次適應算法循環首次適應算法算法算法 又稱為又稱為下次適應算法下次適應算法，由首次適應算法演變而來。在為作，由首次適應算法演變而來。在為作業分配內存空間時業分配內存空間時, ,不再每次從空閑分區表不再每次從空閑分區表/ /鏈首開始查找鏈首開始查找, ,而是而是從從上次找到的空閑分區的下一個空閑分區上次找到的空閑分區的下一個空閑分區開始查找開始查找, ,直到找到第直到找到第一個能滿足其大小要求的空閑分區為止。然后，再按照作業大一個能滿足其大小要求的空閑分區為止。然后，再按照作業大小，從該分區中

45、劃出一塊內存空間分配給請求者，余下的空閑小，從該分區中劃出一塊內存空間分配給請求者，余下的空閑分區仍留在空閑分區表分區仍留在空閑分區表/ /鏈中。鏈中。第四章存儲器管理 區號區號大小大小起址起址132k20k28k52k3120k60k4331k180k空閑分區表空閑分區表解：解：按循環首次適應算法，按循環首次適應算法， 申請作業申請作業100k，分配分配3號分區，剩下分區為號分區，剩下分區為20k,起始地址起始地址160K； 申請作業申請作業30k， 分配分配4號分區，剩下分區為號分區，剩下分區為301k，起始地址，起始地址210K ； 申請作業申請作業7k， 分配分配1號分區，剩下分區為號

46、分區，剩下分區為25k，起始地址，起始地址27K ；其內存分配圖及分配后空閑分區表如下：其內存分配圖及分配后空閑分區表如下：例例 ：系統中的空閑分區表如下，現有三個作業分配申請內存空間系統中的空閑分區表如下，現有三個作業分配申請內存空間100K、30K及及7K。給出按循環首次適應算法的內存分配情況及分配后空閑分區。給出按循環首次適應算法的內存分配情況及分配后空閑分區表。表。第四章存儲器管理 區號區號大小大小起址起址125k27k28k52k320k160k4301k210k(3)該算法分配后的空閑分區表該算法分配后的空閑分區表v算法特點算法特點 使存儲空間的利用使存儲空間的利用更加均衡更加均衡

47、，不致使小的空閑區集中在存儲，不致使小的空閑區集中在存儲區的一端，但這會導致區的一端，但這會導致缺乏大的空閑分區缺乏大的空閑分區。 0k 20k 52k 60k180k511k(1)內存分配圖內存分配圖27K52K160K210K區號區號大小大小起址起址132k20k28k52k3120k60k4331k180k(2)分配前空閑分區表分配前空閑分區表三個作業分配申請內存空間三個作業分配申請內存空間100K、30K及及7K。第四章存儲器管理 最佳適應算法最佳適應算法算法算法 空閑分區表空閑分區表/ /鏈按容量大小遞增鏈按容量大小遞增的次序排列。在進行內存的次序排列。在進行內存分配時，從空閑分區表

48、分配時，從空閑分區表/ /鏈的首開始順序查找，直到找到第一鏈的首開始順序查找，直到找到第一個滿足其大小要求的空閑分區為止。個滿足其大小要求的空閑分區為止。 按這種方式為作業分配內存，就能把既滿足作業要求又按這種方式為作業分配內存，就能把既滿足作業要求又與作業大小與作業大小最接近最接近的空閑分區分配給作業。如果該空閑分區大的空閑分區分配給作業。如果該空閑分區大于作業的大小，則與首次適應算法相同，將剩余空閑分區仍留于作業的大小，則與首次適應算法相同，將剩余空閑分區仍留在空閑分區表在空閑分區表/ /鏈中。鏈中。第四章存儲器管理 0k 20k 52k 60k180k511k2134例例 ：系統中的空閑

49、分區表如下，現有三個作業分配申請內存空間系統中的空閑分區表如下，現有三個作業分配申請內存空間100K、30K及及7K。給出按最佳適應算法的內存分配情況及分配后。給出按最佳適應算法的內存分配情況及分配后空閑分區表。空閑分區表。區號區號大小大小起址起址18k52k232k20k3120k60k4331k180k分配前的空閑分區表分配前的空閑分區表內存分區內存分區按從小到大排隊按從小到大排隊第四章存儲器管理 解：解：按按最佳適應算法最佳適應算法，分配前的空閑分區表如上表。，分配前的空閑分區表如上表。 申請作業申請作業100k，分配分配3號分區，剩下分區為號分區，剩下分區為20k,起始地址起始地址16

50、0K； 申請作業申請作業30k， 分配分配2號分區，剩下分區為號分區，剩下分區為2k，起始地址，起始地址50K ； 申請作業申請作業7k， 分配分配1號分區，剩下分區為號分區，剩下分區為1k，起始地址，起始地址59K ；其內存分配圖及分配后空閑分區表如下其內存分配圖及分配后空閑分區表如下區號大小起址18k52k320k160k232k20k4331k180k作業作業100K分配后的空閑分區表分配后的空閑分區表區號大小起址22k50k18k52k320k160k4331k180k作業作業30K分配后的空閑分區表分配后的空閑分區表區號大小起址11k59k22k50k320k160k4331k180

51、k作業作業7K分配后的空閑分區表分配后的空閑分區表區號區號大小大小起址起址18k52k232k20k3120k60k4331k180k分配前的空閑分區表分配前的空閑分區表第四章存儲器管理 (2)該算法分配后的空閑分區表該算法分配后的空閑分區表 0k 20k 52k 60k180k511k(1)內存分配圖內存分配圖50K59K160K180K區號區號大小大小起址起址11k59k22k50k320k160k4331k180kv算法特點算法特點 若存在與作業大小一致的空閑分區若存在與作業大小一致的空閑分區, ,則它必然被選中，若則它必然被選中，若不存在不存在與與作業大小一致的空閑分區，則只劃分比作業

52、稍大的空閑分區，作業大小一致的空閑分區，則只劃分比作業稍大的空閑分區，, ,從而保從而保留了大的空閑分區留了大的空閑分區, ,但空閑區一般不可能正好和它申請的內存空間大小但空閑區一般不可能正好和它申請的內存空間大小一樣一樣, ,因而將其分割成兩部分時因而將其分割成兩部分時, ,往往使往往使剩下的空閑區非常小剩下的空閑區非常小, ,從而在存從而在存儲器中留下許多難以利用的小空閑區（碎片或零頭）儲器中留下許多難以利用的小空閑區（碎片或零頭）。第四章存儲器管理 最壞適應算法最壞適應算法算法算法 空閑分區表空閑分區表/ /鏈按容量大小遞減鏈按容量大小遞減的次序排列。在進行的次序排列。在進行內存分配時，

53、從空閑分區表內存分配時，從空閑分區表/ /鏈的首開始順序查找，直到鏈的首開始順序查找，直到找到第一個比之大的空閑分區為止。剩下的空閑仍留在找到第一個比之大的空閑分區為止。剩下的空閑仍留在空閑分區表空閑分區表/ /鏈中。鏈中。第四章存儲器管理 區號區號大小大小起址起址1331k180k2120k60k332k20k48k52k空閑分區表空閑分區表例例 ：系統中的空閑分區表如下，現有三個作業分配申請內存空系統中的空閑分區表如下，現有三個作業分配申請內存空間間100K、30K及及7K。給出按最壞適應算法的內存分配情況及分。給出按最壞適應算法的內存分配情況及分配后空閑分區表。配后空閑分區表。按從大到小

54、排隊按從大到小排隊第四章存儲器管理 區號大小起址1231k280k2120k60k332k20k48k52k作業作業100K分配后的空閑分區表分配后的空閑分區表區號大小起址1201k310k2120k60k332k20k48k52k作業作業30K分配后的空閑分區表分配后的空閑分區表區號大小起址1194k317k2120k60k332k20k48k52k作業作業7K分配后的空閑分區表分配后的空閑分區表解：解：按按最壞適應算法最壞適應算法，分配前的空閑分區表如上表。，分配前的空閑分區表如上表。 申請作業申請作業100k，分配分配1號分區，剩下分區為號分區，剩下分區為231k,起始地址起始地址280

55、K； 申請作業申請作業30k， 分配分配1號分區，剩下分區為號分區，剩下分區為201k，起始地址，起始地址310K ； 申請作業申請作業7k， 分配分配1號分區，剩下分區為號分區，剩下分區為194k，起始地址，起始地址317K ；其內存分配圖及分配后空閑分區表如下：其內存分配圖及分配后空閑分區表如下：區號區號大小大小起址起址1331k180k2120k60k332k20k48k52k空閑分區表空閑分區表第四章存儲器管理 區號區號大小大小起址起址1194k317k2120k60k332k20k48k52k(2)該算法分配后的空閑分區表該算法分配后的空閑分區表3 0k 20k 52k 60k180

56、k511k(1)內存分配圖內存分配圖20K52K60K280K310K317Kv算法特點算法特點 總是挑選滿足總是挑選滿足作業要求的最大作業要求的最大的分區分配給作業。這樣使分給作業后剩下的分區分配給作業。這樣使分給作業后剩下的空閑分區也較大，可裝下其它作業。但由于最大的空閑分區總是因首先分配的空閑分區也較大，可裝下其它作業。但由于最大的空閑分區總是因首先分配而劃分，當有而劃分，當有大作業到來大作業到來時，其存儲空間的申請往往會得不到滿足。時，其存儲空間的申請往往會得不到滿足。第四章存儲器管理 3 3分區分配操作分區分配操作1) 1) 分配內存分配內存根據內存分配算法根據內存分配算法圖圖 4-

57、7內存分配流程內存分配流程 從頭開始查表檢索完否？m.sizeu.size?m.size-u.sizesize?從該分區中劃出u.size大小的分區將該分區分配給請求者修改有關數據結構返回返回繼續檢索下一個表項將該分區從鏈中移出YNNYYN設設: : u.size: 請求的分區大小為；請求的分區大小為； m.size: 空閑分區的大小；空閑分區的大小； size： 規定不再切割的剩余分規定不再切割的剩余分區的大小；區的大小； 該分區該分區整體分整體分配配分成分成兩部兩部分分找一個空找一個空閑區能滿閑區能滿足作業大足作業大小小第四章存儲器管理 （2 2）回收內存）回收內存 當作業執行結束時，應回

58、收已使用完畢的分區。系統根據當作業執行結束時，應回收已使用完畢的分區。系統根據回收分區的大小及首回收分區的大小及首地址地址，在空閑分區表中檢查，在空閑分區表中檢查是否有鄰接的空閑分區是否有鄰接的空閑分區，如有，則合成為一個大的空閑，如有，則合成為一個大的空閑分區，然后修改有關的分區狀態信息。分區，然后修改有關的分區狀態信息。v 回收分區與回收分區與已有空閑分區已有空閑分區的相鄰情況有以下四種的相鄰情況有以下四種： 1）回收分區上鄰接一個空閑分區）回收分區上鄰接一個空閑分區,合并后首地址為空閑分區的首地址合并后首地址為空閑分區的首地址,大小為二者之和。大小為二者之和。 2）回收分區下鄰接一個空閑

59、分區）回收分區下鄰接一個空閑分區,合并后首地址為回收分區的首地址合并后首地址為回收分區的首地址,大小為二者之和。大小為二者之和。 3）回收分區上下鄰接空閑分區）回收分區上下鄰接空閑分區,合并后首地址為上空閑分區的首地址合并后首地址為上空閑分區的首地址,大小為三者之和。大小為三者之和。 4）回收分區不鄰接空閑分區，這時在空閑分區表中新建一表項，并填寫分區大小等）回收分區不鄰接空閑分區，這時在空閑分區表中新建一表項，并填寫分區大小等信息。信息。回收分區空閑分區(a)空閑分區回收分區(b)空閑分區回收分區空閑分區(c)內存回收情況內存回收情況思考：思考： 哪種回收哪種回收情況，回收情況，回收后，空閑

60、分后，空閑分區數目要減區數目要減少一個？少一個？第四章存儲器管理 四、可重定位分區分配方式四、可重定位分區分配方式1、碎片問題、碎片問題 在分區存儲管理方式中，必須把作業裝入到在分區存儲管理方式中，必須把作業裝入到一片連續的一片連續的內存空間。如果系統中有若干個小的分區，其總容量內存空間。如果系統中有若干個小的分區，其總容量大于要大于要裝入的作業裝入的作業，但由于它們不相鄰接，也將致使作業不能裝入，但由于它們不相鄰接，也將致使作業不能裝入內存。內存。例例 ：如圖所示系統中有四個小空閑分區，不相鄰，但總容量為如圖所示系統中有四個小空閑分區，不相鄰，但總容量為90KB，如果現有一作業要求分配，如果