第五章存儲管理(1)

1、1第五章第五章 存儲管理存儲管理主存的管理主存的管理2第五章第五章 存儲管理存儲管理v5.1 存儲管理的功能存儲管理的功能v5.2 分區(qū)存儲管理分區(qū)存儲管理v5.3 覆蓋和交換覆蓋和交換v5.4 頁式管理頁式管理v5.5 段式與段頁式管理段式與段頁式管理v5.6 局部性原理與抖動問題局部性原理與抖動問題35.1 存儲管理的功能存儲管理的功能v5.1.1 虛擬存儲器虛擬存儲器v5.1.2 地址變換地址變換v5.1.3 內外存數(shù)據(jù)傳輸?shù)目刂苾韧獯鏀?shù)據(jù)傳輸?shù)目刂苬5.1.4 內存的分配與回收內存的分配與回收v5.1.5 內存信息的共享與保護內存信息的共享與保護45.1.1 虛擬存儲器虛擬存儲器v內存

2、由順序編址的塊組成，內存的每個存內存由順序編址的塊組成，內存的每個存儲單元都有一個編號，這種編號稱為儲單元都有一個編號，這種編號稱為內存內存地址地址（或稱為物理地址，絕對地址）。（或稱為物理地址，絕對地址）。v內存地址的集合稱為內存地址的集合稱為內存空間內存空間（或物理地（或物理地址空間）。址空間）。55.1.1 虛擬存儲器虛擬存儲器v用戶編程所用的地址稱為用戶編程所用的地址稱為邏輯地址邏輯地址（或虛地（或虛地址）。址）。v由邏輯地址組成的空間稱為由邏輯地址組成的空間稱為邏輯地址空間邏輯地址空間（或虛擬地址空間）（或虛擬地址空間）。65.1.1 虛擬存儲器虛擬存儲器源程序源程序目標代碼目標代碼

3、 地址安排？地址安排？v按照物理存儲器中的位置賦予實際物理地址。按照物理存儲器中的位置賦予實際物理地址。優(yōu)點：優(yōu)點：CPU 執(zhí)行目標代碼時的執(zhí)行速度高。執(zhí)行目標代碼時的執(zhí)行速度高。缺點：缺點：能裝入內存并發(fā)執(zhí)行的進程數(shù)大大減少，對于某能裝入內存并發(fā)執(zhí)行的進程數(shù)大大減少，對于某些較大的進程可能會無法執(zhí)行；編譯程序將非常復雜，些較大的進程可能會無法執(zhí)行；編譯程序將非常復雜，編譯程序必須知道內存的當前空閑部分及其地址，并編譯程序必須知道內存的當前空閑部分及其地址，并且把一個進程的不同程序段連續(xù)地存放起來且把一個進程的不同程序段連續(xù)地存放起來7 由編譯鏈接程序編譯后鏈接（靜態(tài)、動態(tài)）到一由編譯鏈接程序

4、編譯后鏈接（靜態(tài)、動態(tài)）到一個以個以0地址為始地址的線性或多維地址為始地址的線性或多維虛擬地址空間虛擬地址空間（邏輯地址空間邏輯地址空間）。每個進程都擁有一個虛擬地址空間。每個指令或數(shù)據(jù)單每個進程都擁有一個虛擬地址空間。每個指令或數(shù)據(jù)單元都在這個虛擬空間中擁有確定的地址，把這個地址元都在這個虛擬空間中擁有確定的地址，把這個地址稱為稱為虛擬地址虛擬地址（virtual address）(邏輯地址邏輯地址)。地址轉換地址轉換Load A 200 3456 。 。1200物理地址空間物理地址空間Load A data1data1 3456源程序源程序Load A 200 34560100200編譯編

5、譯鏈接鏈接虛擬地址空間虛擬地址空間BA=100085.1.1 虛擬存儲器虛擬存儲器v虛擬存儲器：虛擬存儲器：進程中的目標代碼、數(shù)據(jù)等的進程中的目標代碼、數(shù)據(jù)等的虛擬地址組成的虛擬空間稱為虛擬存儲器。虛擬地址組成的虛擬空間稱為虛擬存儲器。9實現(xiàn)虛擬內存的基本原理實現(xiàn)虛擬內存的基本原理v將程序正在使用的部分內容放在內存，而暫時不將程序正在使用的部分內容放在內存，而暫時不用的部分放在外存，在需要時由系統(tǒng)調入內存，用的部分放在外存，在需要時由系統(tǒng)調入內存，并將不需要（或暫不需要）的部分調出內存。并將不需要（或暫不需要）的部分調出內存。v由于程序在執(zhí)行時，在一段時間內一般僅使用它由于程序在執(zhí)行時，在一段

6、時間內一般僅使用它的程序的一部分（或一小部分），所以程序僅有的程序的一部分（或一小部分），所以程序僅有部分裝入內存完全能夠正確執(zhí)行。部分裝入內存完全能夠正確執(zhí)行。v要由操作系統(tǒng)結合相關硬件來完成上述工件，這要由操作系統(tǒng)結合相關硬件來完成上述工件，這樣計算機好象為用戶提供了一個容量遠大于內存樣計算機好象為用戶提供了一個容量遠大于內存的存儲器，這個存儲器稱為的存儲器，這個存儲器稱為虛擬存儲器虛擬存儲器。 105.1.1 虛擬存儲器虛擬存儲器v虛擬存儲器虛擬存儲器呈現(xiàn)在用戶面前的是一個在呈現(xiàn)在用戶面前的是一個在物理上只受物理上只受內存和外存總容量限制內存和外存總容量限制的存儲系統(tǒng)，這要求存儲管的存儲

7、系統(tǒng)，這要求存儲管理系統(tǒng)只把進程執(zhí)行時頻繁使用和立即需要的指令理系統(tǒng)只把進程執(zhí)行時頻繁使用和立即需要的指令與數(shù)據(jù)等存放在內存中，而把那些暫時不需要的部與數(shù)據(jù)等存放在內存中，而把那些暫時不需要的部分存放在外存中，待需要時自動調入，以提高內存分存放在外存中，待需要時自動調入，以提高內存的利用率和并行執(zhí)行的作業(yè)道數(shù)。的利用率和并行執(zhí)行的作業(yè)道數(shù)。v虛擬存儲器虛擬存儲器不考慮不考慮物理存儲器的大小和信息存放的物理存儲器的大小和信息存放的實際位置實際位置，只規(guī)定只規(guī)定每個進程中互相關聯(lián)的信息的每個進程中互相關聯(lián)的信息的相相對位置對位置。v每個進程都擁有自己的虛擬存儲器，且虛擬存儲器每個進程都擁有自己的虛

8、擬存儲器，且虛擬存儲器的容量是由計算機的地址結構和尋址方式確定的。的容量是由計算機的地址結構和尋址方式確定的。115.1.2 地址變換地址變換v地址重定位：地址重定位：從虛擬地址到內存地址的轉換從虛擬地址到內存地址的轉換稱為稱為地址重定位地址重定位，或稱為，或稱為地址映射地址映射。v地址映射的方式：地址映射的方式： 1 1、靜態(tài)地址重定位、靜態(tài)地址重定位2 2、動態(tài)地址重定位、動態(tài)地址重定位121、靜態(tài)地址重定位、靜態(tài)地址重定位v在虛擬空間程序執(zhí)行之前由裝配程序完成地在虛擬空間程序執(zhí)行之前由裝配程序完成地址映射的工作。址映射的工作。不能實現(xiàn)虛擬存儲器不能實現(xiàn)虛擬存儲器v假定程序裝入內存的首地址

9、為假定程序裝入內存的首地址為BA，程序地，程序地址為址為VA，內存地址為，內存地址為MA，則地址映射按下，則地址映射按下式進行：式進行：MA=(BA)+(VA) 。13例例v程序裝入內存的首地址為程序裝入內存的首地址為1000，則，則裝配程序就按裝配程序就按MA=1000+VA對程序對程序中所有地址部分進行修改，修改后中所有地址部分進行修改，修改后指令指令Load A，200就變?yōu)榫妥優(yōu)長oad A，120014靜態(tài)地址重定位的靜態(tài)地址重定位的優(yōu)缺點優(yōu)缺點v優(yōu)點：優(yōu)點：不需要硬件的支持。不需要硬件的支持。v缺點：缺點：程序必須占用連續(xù)的內存空間，程序程序必須占用連續(xù)的內存空間，程序和數(shù)據(jù)不能共

10、享；和數(shù)據(jù)不能共享；程序一旦裝入內存之后就程序一旦裝入內存之后就不能再移動，并且必須在程序執(zhí)行之前將有不能再移動，并且必須在程序執(zhí)行之前將有關部分全部裝入。關部分全部裝入。152、動態(tài)地址重定位、動態(tài)地址重定位v動態(tài)地址重定位是在程序執(zhí)行的過程中，在動態(tài)地址重定位是在程序執(zhí)行的過程中，在CPUCPU訪訪問內存之前，將要訪問的程序地址轉換為內存地址。問內存之前，將要訪問的程序地址轉換為內存地址。一般來說這種轉換是由專門的一般來說這種轉換是由專門的硬件機構硬件機構來完成的。來完成的。v在地址重定位機構中，有一個在地址重定位機構中，有一個基地址寄存器基地址寄存器BR和一和一個個程序地址寄存器程序地址

11、寄存器VR，一個，一個內存地址寄存器內存地址寄存器MR。 MA=(BR)+(VR)162、動態(tài)地址重定位、動態(tài)地址重定位v動態(tài)地址重定位的具體過程：動態(tài)地址重定位的具體過程：程序裝入內存后，它所占用的內存區(qū)的程序裝入內存后，它所占用的內存區(qū)的首地址首地址由系統(tǒng)由系統(tǒng)送入送入基地址寄存器基地址寄存器BRBR中。中。在程序在程序執(zhí)行的過程中執(zhí)行的過程中，若要訪問內存，將訪問，若要訪問內存，將訪問的的邏輯地址送入邏輯地址送入程序地址寄存器程序地址寄存器VRVR中。中。地址轉換機構地址轉換機構把把VRVR和和BRBR中的內容相加中的內容相加，并將結，并將結果果送入送入MRMR中，作為實際訪問的物理地址

12、。中，作為實際訪問的物理地址。17圖圖5.3 動態(tài)地址重定位動態(tài)地址重定位182、動態(tài)地址重定位、動態(tài)地址重定位v動態(tài)地址重定位的動態(tài)地址重定位的優(yōu)點優(yōu)點可以對內存進行非連續(xù)分配?？梢詫却孢M行非連續(xù)分配。程序占用的內存空程序占用的內存空間是動態(tài)可變的，當程序從某個存儲區(qū)移到另一間是動態(tài)可變的，當程序從某個存儲區(qū)移到另一個區(qū)域時，只需要修改相應的寄存器個區(qū)域時，只需要修改相應的寄存器BRBR的內容即的內容即可。可。提供了實現(xiàn)虛擬存儲器的基礎。提供了實現(xiàn)虛擬存儲器的基礎。一個程序不一定一個程序不一定要求占用一個連續(xù)的內存空間。可以部分地裝入要求占用一個連續(xù)的內存空間。可以部分地裝入程序運行。程序

13、運行。便于多個進程共享同一個程序的代碼。便于多個進程共享同一個程序的代碼。192、動態(tài)地址重定位、動態(tài)地址重定位v動態(tài)地址重定位的代價：動態(tài)地址重定位的代價：需要硬件的支持。需要硬件的支持。實現(xiàn)存儲管理的軟件算法較為復雜。實現(xiàn)存儲管理的軟件算法較為復雜。205.1.3 內外存數(shù)據(jù)傳輸?shù)目刂苾韧獯鏀?shù)據(jù)傳輸?shù)目刂苬內外存數(shù)據(jù)傳輸?shù)目刂疲簝韧獯鏀?shù)據(jù)傳輸?shù)目刂疲河脩舫绦蜃约嚎刂疲河脩舫绦蜃约嚎刂疲焊采w技術覆蓋技術用戶負擔很用戶負擔很大，程序段的最大長度受內存容量限制，不能大，程序段的最大長度受內存容量限制，不能實現(xiàn)虛擬存儲器。實現(xiàn)虛擬存儲器。操作系統(tǒng)控制：操作系統(tǒng)控制：v交換交換(swapping)方

14、式方式：不同的進程或作業(yè)之間：不同的進程或作業(yè)之間v請求調入請求調入(on demand)方式和方式和預調入預調入(on prefetch)方式方式215.1.4 內存的分配與回收內存的分配與回收v要完成內存的分配和回收工作，要求設計者要完成內存的分配和回收工作，要求設計者選擇和確定以下幾種策略和結構：選擇和確定以下幾種策略和結構：分配結構分配結構調入策略調入策略放置策略放置策略交換策略交換策略回收策略回收策略225.1.4 內存的分配與回收內存的分配與回收v分配結構分配結構分配結構是用來登記內存使用情分配結構是用來登記內存使用情況的數(shù)據(jù)結構。如況的數(shù)據(jù)結構。如空閑區(qū)表、空閑區(qū)隊列等?？臻e區(qū)表

15、、空閑區(qū)隊列等。v調入策略調入策略用戶程序在何時、怎樣調入內存用戶程序在何時、怎樣調入內存的策略。的策略。v放置策略放置策略用戶程序調入內存時，確定將其用戶程序調入內存時，確定將其放置在何處的策略。放置在何處的策略。235.1.4 內存的分配與回收內存的分配與回收v交換策略交換策略當需要將某個用戶程序調入內存當需要將某個用戶程序調入內存而內存空間又不夠時，就要確定哪個或哪些而內存空間又不夠時，就要確定哪個或哪些程序可以從內存中移走。程序可以從內存中移走。v回收策略回收策略確定回收的時機和對所回收的內確定回收的時機和對所回收的內存空閑區(qū)和已存在的內存空閑區(qū)進行調整。存空閑區(qū)和已存在的內存空閑區(qū)進

16、行調整。245.1.5 內存信息的共享與保護內存信息的共享與保護v保證在內存中的多道程序只能在給定的保證在內存中的多道程序只能在給定的存儲區(qū)域內活動并互不產生干擾。存儲區(qū)域內活動并互不產生干擾。 v包括：包括：防止地址越界防止地址越界防止越權防止越權( (對共享區(qū)有訪問權對共享區(qū)有訪問權) )255.1.5 內存信息的共享與保護內存信息的共享與保護v內存保護的方法：內存保護的方法：硬件法、軟件法硬件法、軟件法和和軟硬件法軟硬件法。v上下界保護法上下界保護法：硬件法：硬件法 1 1、在、在CPUCPU中設置一對下限寄存器和上限寄存器存放中設置一對下限寄存器和上限寄存器存放用戶作業(yè)在主存中的下限和

17、上限地址用戶作業(yè)在主存中的下限和上限地址 2 2、每當、每當CPUCPU要訪問主存，硬件自動將被訪問的主存要訪問主存，硬件自動將被訪問的主存地址與界限寄存器的內容進行比較，以判斷是否越界地址與界限寄存器的內容進行比較，以判斷是否越界 3 3、如果未越界，則按此地址訪問主存，否則將產生、如果未越界，則按此地址訪問主存，否則將產生程序中斷程序中斷越界中斷越界中斷（存儲保護中斷）（存儲保護中斷）26圖圖5.4 上、下界寄存器保護法上、下界寄存器保護法275.1.5 內存信息的共享與保護內存信息的共享與保護v保護鍵法：保護鍵法：軟件法軟件法 為每一個被保護的存儲塊分配一個單為每一個被保護的存儲塊分配一

18、個單獨的保護鍵。在程序狀態(tài)字中設置相應的獨的保護鍵。在程序狀態(tài)字中設置相應的保護鍵開關字段，訪問過程中比較保護開保護鍵開關字段，訪問過程中比較保護開關字段的內容和保護鍵是否匹配，匹配則關字段的內容和保護鍵是否匹配，匹配則允許訪問，否則產生訪問出錯中斷。允許訪問，否則產生訪問出錯中斷。28圖圖5.5 保護鍵保護法保護鍵保護法295.1.5 內存信息的共享與保護內存信息的共享與保護v界限寄存器與界限寄存器與CPU的用戶態(tài)或核心態(tài)工作方的用戶態(tài)或核心態(tài)工作方式相結合的保護方式。式相結合的保護方式。軟硬件法軟硬件法 用戶態(tài)進程只能訪問那些在界限寄存器用戶態(tài)進程只能訪問那些在界限寄存器所規(guī)定范圍內的內存

19、部分，而核心態(tài)進程則所規(guī)定范圍內的內存部分，而核心態(tài)進程則可以訪問整個內存地址空間。可以訪問整個內存地址空間。305.2 分區(qū)存儲管理分區(qū)存儲管理v把整個內存劃分為若干大小不等的區(qū)域，操把整個內存劃分為若干大小不等的區(qū)域，操作系統(tǒng)占用一個區(qū)域，其它區(qū)域供系統(tǒng)中的多作系統(tǒng)占用一個區(qū)域，其它區(qū)域供系統(tǒng)中的多個進程共享，這種方法稱為個進程共享，這種方法稱為分區(qū)存儲管理分區(qū)存儲管理。5.2.1 5.2.1 分區(qū)存儲管理的基本原理分區(qū)存儲管理的基本原理5.2.2 5.2.2 分區(qū)的分配與回收分區(qū)的分配與回收5.2.3 5.2.3 有關分區(qū)管理其他問題討論有關分區(qū)管理其他問題討論 315.2.1 5.2.

20、1 分區(qū)存儲管理的基本原理分區(qū)存儲管理的基本原理v基本原理：基本原理：給每一個內存中的進程劃分一塊給每一個內存中的進程劃分一塊適當大小的存儲區(qū)適當大小的存儲區(qū),以連續(xù)存儲各進程的程序以連續(xù)存儲各進程的程序和數(shù)據(jù)，使各進程得以并發(fā)執(zhí)行。和數(shù)據(jù)，使各進程得以并發(fā)執(zhí)行。 這是最簡單的一種存儲管理這是最簡單的一種存儲管理，按分區(qū)劃分按分區(qū)劃分的時機可分為：的時機可分為： 1 1、固定分區(qū)、固定分區(qū) 2 2、動態(tài)分區(qū)、動態(tài)分區(qū)321 1、固定分區(qū)、固定分區(qū)v固定分區(qū)：固定分區(qū)：把內存固定地劃分為若干個大小把內存固定地劃分為若干個大小不等的區(qū)域。分區(qū)的劃分由計算機的操作員不等的區(qū)域。分區(qū)的劃分由計算機的操

21、作員或者由操作系統(tǒng)給出，并給出或者由操作系統(tǒng)給出，并給出分區(qū)說明表分區(qū)說明表。在調度作業(yè)時，由存儲管理根據(jù)所需量在分在調度作業(yè)時，由存儲管理根據(jù)所需量在分區(qū)說明表中找出一個單元分配給它。區(qū)說明表中找出一個單元分配給它。331 1、固定分區(qū)、固定分區(qū)v分區(qū)說明表分區(qū)說明表分區(qū)號分區(qū)號大小大小(KB)始址始址狀態(tài)狀態(tài)1820已分配已分配23228已分配已分配36460已分配已分配4132124未分配未分配34圖圖5.6 固定分區(qū)法固定分區(qū)法351 1、固定分區(qū)、固定分區(qū)v在作業(yè)大小和出現(xiàn)頻率均已知的情況下，固在作業(yè)大小和出現(xiàn)頻率均已知的情況下，固定分區(qū)是合適的。定分區(qū)是合適的。在這種情況下分區(qū)的大

22、小在這種情況下分區(qū)的大小選擇與作業(yè)大小相當，這樣內存的使用效率選擇與作業(yè)大小相當，這樣內存的使用效率較高。較高。v但是若作業(yè)的大小和出現(xiàn)的頻率不知道時，但是若作業(yè)的大小和出現(xiàn)的頻率不知道時，勢必造成分區(qū)的大小和作業(yè)的大小相差甚遠，勢必造成分區(qū)的大小和作業(yè)的大小相差甚遠，這樣就會造成這樣就會造成存儲空間的浪費存儲空間的浪費，從而影響整，從而影響整個系統(tǒng)的效率。個系統(tǒng)的效率。 362 2、動態(tài)分區(qū)、動態(tài)分區(qū)v動態(tài)分區(qū)：動態(tài)分區(qū)：在系統(tǒng)運行的過程中建立分區(qū)，在系統(tǒng)運行的過程中建立分區(qū)，并使分區(qū)的大小剛好與作業(yè)的大小相等。并使分區(qū)的大小剛好與作業(yè)的大小相等。v這種存儲管理的方法解決了固定分區(qū)嚴重浪這種

23、存儲管理的方法解決了固定分區(qū)嚴重浪費內存的問題。是一種較為實用的存儲管理費內存的問題。是一種較為實用的存儲管理方法。方法。37圖圖5.7 動態(tài)分區(qū)內存初始分配情況動態(tài)分區(qū)內存初始分配情況382 2、動態(tài)分區(qū)、動態(tài)分區(qū)v 在實現(xiàn)動態(tài)分區(qū)分配的時候需要涉及到以下在實現(xiàn)動態(tài)分區(qū)分配的時候需要涉及到以下三個方面的問題：三個方面的問題： 動態(tài)分配中所用到的數(shù)據(jù)結構動態(tài)分配中所用到的數(shù)據(jù)結構；分區(qū)的分配算法；分區(qū)的分配算法；分區(qū)的分配和回收操作。分區(qū)的分配和回收操作。392 2、動態(tài)分區(qū)、動態(tài)分區(qū)v實現(xiàn)動態(tài)分區(qū)的數(shù)據(jù)結構：實現(xiàn)動態(tài)分區(qū)的數(shù)據(jù)結構：在動態(tài)分區(qū)存儲管理中，要有相應的數(shù)據(jù)結構來在動態(tài)分區(qū)存儲管理

24、中，要有相應的數(shù)據(jù)結構來登記空閑區(qū)的說明信息，它包括空閑區(qū)的大小登記空閑區(qū)的說明信息，它包括空閑區(qū)的大小和位置。和位置。其數(shù)據(jù)結構有：分區(qū)說明表、可用分其數(shù)據(jù)結構有：分區(qū)說明表、可用分區(qū)表（或自由鏈）、請求表。區(qū)表（或自由鏈）、請求表。分區(qū)說明表分區(qū)說明表可用分區(qū)表：可用分區(qū)表：用于為內存中每個還沒有分區(qū)設用于為內存中每個還沒有分區(qū)設置一個表項，每個分區(qū)表項包含分區(qū)序號、分置一個表項，每個分區(qū)表項包含分區(qū)序號、分區(qū)起始地址以及分區(qū)大小。（占用內存）區(qū)起始地址以及分區(qū)大小。（占用內存）402 2、動態(tài)分區(qū)、動態(tài)分區(qū)v實現(xiàn)動態(tài)分區(qū)的數(shù)據(jù)結構：實現(xiàn)動態(tài)分區(qū)的數(shù)據(jù)結構：自由鏈：自由鏈：利用每個內存空閑

25、區(qū)的頭幾個單元存放利用每個內存空閑區(qū)的頭幾個單元存放本空閑區(qū)的大小和下個空閑區(qū)的起始地址，將所本空閑區(qū)的大小和下個空閑區(qū)的起始地址，將所有空閑區(qū)組成一條鏈。（不占用內存）有空閑區(qū)組成一條鏈。（不占用內存） 請求表：請求表：表的每個表目描述請求內存資源的作表的每個表目描述請求內存資源的作業(yè)或進程號以及所請求的內存大小。業(yè)或進程號以及所請求的內存大小。41圖圖5.9 可用表、自由鏈及請求表可用表、自由鏈及請求表42圖圖5.8 內存分配變化過程內存分配變化過程435.2.2 分區(qū)的分配與回收分區(qū)的分配與回收v1、固定分區(qū)的分配與回收、固定分區(qū)的分配與回收v2、動態(tài)分區(qū)時的分配與回收、動態(tài)分區(qū)時的分配

26、與回收v3、動態(tài)分區(qū)時的回收與拼接、動態(tài)分區(qū)時的回收與拼接v4、幾種分配算法的比較、幾種分配算法的比較441、固定分區(qū)的分配與回收、固定分區(qū)的分配與回收v分配：分配：當用戶程序要裝入執(zhí)行時，通過請求當用戶程序要裝入執(zhí)行時，通過請求表提出內存分配要求和所要求的內存空間大表提出內存分配要求和所要求的內存空間大小。存儲管理程序小。存儲管理程序根據(jù)請求表要求查詢分區(qū)根據(jù)請求表要求查詢分區(qū)說明表說明表，從中找出一個滿足要求的空閑分區(qū)，從中找出一個滿足要求的空閑分區(qū)，將其分配給申請者。將其分配給申請者。P117圖圖v回收：回收：回收時管理程序只需將對應的分區(qū)狀回收時管理程序只需將對應的分區(qū)狀態(tài)置為未使用即

27、可。態(tài)置為未使用即可。 452、動態(tài)分區(qū)時的分配與回收、動態(tài)分區(qū)時的分配與回收v主要解決的三個問題主要解決的三個問題: (1) 對于請求表中的要求內存長度，從可用表或對于請求表中的要求內存長度，從可用表或自由鏈中尋找出合適的空閑區(qū)分配程序。自由鏈中尋找出合適的空閑區(qū)分配程序。(2) 分配空閑區(qū)之后，更新可用表或自由鏈。分配空閑區(qū)之后，更新可用表或自由鏈。(3) 進程或作業(yè)釋放內存資源時，和相鄰的空閑進程或作業(yè)釋放內存資源時，和相鄰的空閑區(qū)進行鏈接合并，更新可用表或自由鏈。區(qū)進行鏈接合并，更新可用表或自由鏈。462、動態(tài)分區(qū)時的分配與回收、動態(tài)分區(qū)時的分配與回收v從可用表或自由鏈中尋找空閑區(qū)的常

28、用的三從可用表或自由鏈中尋找空閑區(qū)的常用的三種方法：種方法：最先適應法最先適應法(first fit algorithm)最佳適應法最佳適應法(best fit algorithm) 最壞適應法最壞適應法(worst fit algoriathm)這三種方法要求可用表或自由鏈按不同的方式排列。這三種方法要求可用表或自由鏈按不同的方式排列。47最先適應法最先適應法v要求可用表或自由鏈要求可用表或自由鏈按起始地址遞增的次序按起始地址遞增的次序排列排列。v分配：分配：當進程申請大小為當進程申請大小為SIZESIZE的內存時，的內存時，存存儲管理程序儲管理程序從空閑區(qū)表的第一個表目開始查從空閑區(qū)表的第

29、一個表目開始查詢，直到首次找到等于或大于詢，直到首次找到等于或大于SIZESIZE的空閑區(qū)。的空閑區(qū)。從該區(qū)中劃出大小為從該區(qū)中劃出大小為SIZESIZE的分區(qū)分配給進程，的分區(qū)分配給進程，余下的部分仍作為一個空閑區(qū)留在空閑區(qū)表余下的部分仍作為一個空閑區(qū)留在空閑區(qū)表中，但要修改其首址和大小。中，但要修改其首址和大小。48最先適應法最先適應法v回收：回收：按釋放區(qū)的首址，查詢空閑區(qū)表，若按釋放區(qū)的首址，查詢空閑區(qū)表，若有與釋放區(qū)相鄰的空閑區(qū)，則合并到相鄰的有與釋放區(qū)相鄰的空閑區(qū)，則合并到相鄰的空閑區(qū)中，并修改該區(qū)的大小和首址，否則，空閑區(qū)中，并修改該區(qū)的大小和首址，否則，把釋放區(qū)作為一個空閑區(qū)，

30、將其大小和首址把釋放區(qū)作為一個空閑區(qū)，將其大小和首址按照首地址大小遞增按照首地址大小遞增的順序插入到空閑區(qū)表的順序插入到空閑區(qū)表的適當位置。的適當位置。49最先適應法的最先適應法的優(yōu)點優(yōu)點v釋放某一存儲區(qū)時，若與空閑區(qū)相鄰則合并釋放某一存儲區(qū)時，若與空閑區(qū)相鄰則合并到相鄰空閑分區(qū)中去，這種情況并不改變該到相鄰空閑分區(qū)中去，這種情況并不改變該區(qū)在表中的位置，只要修改其大小或首址。區(qū)在表中的位置，只要修改其大小或首址。v這種算法是盡可能地利用低地址空間，從而這種算法是盡可能地利用低地址空間，從而保證高地址空間有較大的空閑區(qū)。保證高地址空間有較大的空閑區(qū)。50最佳適應法最佳適應法v要求按要求按空閑區(qū)

31、大小從小到大空閑區(qū)大小從小到大的次序組成空閑的次序組成空閑區(qū)表（隊列）。區(qū)表（隊列）。v分配：分配：當當用戶作業(yè)或用戶作業(yè)或進程申請一個存儲區(qū)時，進程申請一個存儲區(qū)時，存儲存儲管理程序管理程序從表頭開始查找，當找到第一個滿足要求從表頭開始查找，當找到第一個滿足要求的空閑區(qū)時，停止查找，并且這個空閑區(qū)是的空閑區(qū)時，停止查找，并且這個空閑區(qū)是最佳的最佳的空閑區(qū)空閑區(qū)（選中的空閑區(qū)是滿足要求的最小空閑區(qū)）選中的空閑區(qū)是滿足要求的最小空閑區(qū)）。如果該空閑區(qū)大于請求表中的請求長度，則與最先如果該空閑區(qū)大于請求表中的請求長度，則與最先適應法時相同，將減去請求長度后的剩余空閑區(qū)部適應法時相同，將減去請求長度

32、后的剩余空閑區(qū)部分留在可用表中。分留在可用表中。51最佳適應法最佳適應法v回收：回收：按釋放區(qū)的首址，查詢空閑區(qū)表（隊按釋放區(qū)的首址，查詢空閑區(qū)表（隊列）列） ，若有與釋放區(qū)相鄰的空閑區(qū)，則合，若有與釋放區(qū)相鄰的空閑區(qū)，則合并到相鄰的空閑區(qū)中，并修改該區(qū)的大小和并到相鄰的空閑區(qū)中，并修改該區(qū)的大小和首址，否則，把釋放區(qū)作為一個空閑區(qū)插入首址，否則，把釋放區(qū)作為一個空閑區(qū)插入空閑區(qū)表（隊列）空閑區(qū)表（隊列） 。v分配和回收后要對空閑區(qū)表（隊列）重新排分配和回收后要對空閑區(qū)表（隊列）重新排序。序。52最佳適應算法的最佳適應算法的優(yōu)點優(yōu)點v在系統(tǒng)中若存在一個與申請分區(qū)大小相等的在系統(tǒng)中若存在一個與申

33、請分區(qū)大小相等的空閑區(qū)，必定會被選中，而最先適應法則不空閑區(qū)，必定會被選中，而最先適應法則不一定。一定。v若系統(tǒng)中不存在與申請分區(qū)大小相等的空閑若系統(tǒng)中不存在與申請分區(qū)大小相等的空閑區(qū)，則選中的空閑區(qū)是滿足要求的最小空閑區(qū)，則選中的空閑區(qū)是滿足要求的最小空閑區(qū)，而不致于毀掉較大的空閑區(qū)。區(qū)，而不致于毀掉較大的空閑區(qū)。53最佳適應算法的最佳適應算法的缺點缺點v 空閑區(qū)的大小一般與申請分區(qū)大小不相等，空閑區(qū)的大小一般與申請分區(qū)大小不相等，因此將其一分為二，留下來的空閑區(qū)一般情況因此將其一分為二，留下來的空閑區(qū)一般情況下是很小的，以致無法使用。隨著時間的推移，下是很小的，以致無法使用。隨著時間的推移

34、，系統(tǒng)中的小空閑區(qū)會越來越多，從而造成存儲系統(tǒng)中的小空閑區(qū)會越來越多，從而造成存儲區(qū)的大量浪費。區(qū)的大量浪費。 54最壞適應算法最壞適應算法v 要求空閑區(qū)按要求空閑區(qū)按由大至小遞減由大至小遞減的順序組織空閑的順序組織空閑區(qū)表（或隊列）。區(qū)表（或隊列）。v分配：分配：進程申請一個大小為進程申請一個大小為SIZE的存儲區(qū)時，的存儲區(qū)時，總是檢查空閑區(qū)表的第一個空閑區(qū)的大小是否總是檢查空閑區(qū)表的第一個空閑區(qū)的大小是否大于或等于大于或等于SIZE。若空閑區(qū)小于。若空閑區(qū)小于SIZE，則分，則分配失?。环駝t從空閑區(qū)中分配配失?。环駝t從空閑區(qū)中分配SIZE的存儲區(qū)給的存儲區(qū)給用戶，然后修改和調整空閑區(qū)表。

35、用戶，然后修改和調整空閑區(qū)表。55最壞適應算法最壞適應算法v回收：回收：按釋放區(qū)的首址，查詢空閑區(qū)表（隊按釋放區(qū)的首址，查詢空閑區(qū)表（隊列），若有與釋放區(qū)相鄰的空閑區(qū)，則合并列），若有與釋放區(qū)相鄰的空閑區(qū)，則合并到相鄰的空閑區(qū)中，并修改該區(qū)的大小和首到相鄰的空閑區(qū)中，并修改該區(qū)的大小和首址，否則，把釋放區(qū)作為一個空閑區(qū)插入空址，否則，把釋放區(qū)作為一個空閑區(qū)插入空閑區(qū)表（隊列）。閑區(qū)表（隊列）。v分配和回收后要對空閑區(qū)表（隊列）重新排分配和回收后要對空閑區(qū)表（隊列）重新排序。序。56最壞適應算法的優(yōu)點最壞適應算法的優(yōu)點v當程序裝入內存中最大的空閑區(qū)后，剩下的當程序裝入內存中最大的空閑區(qū)后，剩下的

36、空閑區(qū)還可能相當大，還能裝下較大的程序?？臻e區(qū)還可能相當大，還能裝下較大的程序。v每次僅作一次查詢工作。每次僅作一次查詢工作。573、動態(tài)分區(qū)時分區(qū)的回收、動態(tài)分區(qū)時分區(qū)的回收v當某個進程釋放某存儲區(qū)時，系統(tǒng)首先檢查當某個進程釋放某存儲區(qū)時，系統(tǒng)首先檢查釋放區(qū)是否與系統(tǒng)中的空閑區(qū)相鄰，若相鄰則釋放區(qū)是否與系統(tǒng)中的空閑區(qū)相鄰，若相鄰則把釋放區(qū)合并到相鄰的空閑區(qū)中去，否則把釋把釋放區(qū)合并到相鄰的空閑區(qū)中去，否則把釋放區(qū)作為一個空閑區(qū)插入到空閑區(qū)表的適當位放區(qū)作為一個空閑區(qū)插入到空閑區(qū)表的適當位置。置。 58圖圖5.12 空閑區(qū)的合并空閑區(qū)的合并59空閑區(qū)的合并空閑區(qū)的合并v釋放區(qū)與上下兩空閑區(qū)相鄰

37、：釋放區(qū)與上下兩空閑區(qū)相鄰：將三個空閑區(qū)合并為將三個空閑區(qū)合并為一個空閑區(qū)。新空閑區(qū)的起始地址為上空閑區(qū)的起一個空閑區(qū)。新空閑區(qū)的起始地址為上空閑區(qū)的起始地址，大小為三個空閑區(qū)之和。空閑區(qū)合并后，始地址，大小為三個空閑區(qū)之和。空閑區(qū)合并后，取消可用表或自由鏈中下空閑區(qū)的表目項或鏈指針，取消可用表或自由鏈中下空閑區(qū)的表目項或鏈指針，修改上空閑區(qū)的對應項。修改上空閑區(qū)的對應項。v釋放區(qū)只與上空閑區(qū)相鄰：釋放區(qū)只與上空閑區(qū)相鄰：將釋放區(qū)與上空閑區(qū)合將釋放區(qū)與上空閑區(qū)合并為一個空閑區(qū)，其起始地址為上空閑區(qū)的起始地并為一個空閑區(qū)，其起始地址為上空閑區(qū)的起始地址，大小為上空閑區(qū)與釋放區(qū)之和。合并后，修改址

38、，大小為上空閑區(qū)與釋放區(qū)之和。合并后，修改上空閑區(qū)對應的可用表的表目項或自由鏈指針。上空閑區(qū)對應的可用表的表目項或自由鏈指針。60空閑區(qū)的合并空閑區(qū)的合并v釋放區(qū)與下空閑區(qū)相鄰：釋放區(qū)與下空閑區(qū)相鄰：將釋放區(qū)與下空閑將釋放區(qū)與下空閑區(qū)合并，并將釋放區(qū)的起始地址作為合并區(qū)區(qū)合并，并將釋放區(qū)的起始地址作為合并區(qū)的起始地址。合并區(qū)的長度為釋放區(qū)與下空的起始地址。合并區(qū)的長度為釋放區(qū)與下空閑區(qū)之和。合并后修改可用表或自由鏈中相閑區(qū)之和。合并后修改可用表或自由鏈中相應的表目項或鏈指針。應的表目項或鏈指針。v釋放區(qū)不與任何空閑區(qū)相鄰：釋放區(qū)不與任何空閑區(qū)相鄰：釋放區(qū)作為一釋放區(qū)作為一個新可用區(qū)插入可用表或

39、自由鏈。個新可用區(qū)插入可用表或自由鏈。614、三種分配算法的比較、三種分配算法的比較v三種算法的優(yōu)缺點比較三種算法的優(yōu)缺點比較搜索速度：搜索速度：最先適應算法最先適應算法具有具有最佳性能最佳性能，最佳適應算法，最佳適應算法和最壞適應算法都要求把不同大小的空閑區(qū)按大小進行和最壞適應算法都要求把不同大小的空閑區(qū)按大小進行排隊；排隊；回收過程回收過程：最先適應算法最先適應算法具有具有最佳性能，最佳性能，因為最佳適應因為最佳適應算法和最壞適應算法都必須重新調整空閑區(qū)的位置；算法和最壞適應算法都必須重新調整空閑區(qū)的位置；空閑區(qū)利用：空閑區(qū)利用：最佳適應法找到的空閑區(qū)是最佳的，最佳適應法找到的空閑區(qū)是最佳

40、的，但是但是會造成內存碎片較多，影響內存利用率，而最壞適用法會造成內存碎片較多，影響內存利用率，而最壞適用法的內存碎片最少，但是對內存的請求較多的進程有可能的內存碎片最少，但是對內存的請求較多的進程有可能分配失敗。分配失敗?？傊?，三種算法各有所長，針對不同的請求隊列，它們的總之，三種算法各有所長，針對不同的請求隊列，它們的效率和功能是不一樣的。效率和功能是不一樣的。624、三種分配算法的比較、三種分配算法的比較v上述三種放置策略各有利弊，到底哪種最上述三種放置策略各有利弊，到底哪種最好不能一概而論，而應針對具體作業(yè)序列好不能一概而論，而應針對具體作業(yè)序列來分析。來分析。v對于某一作業(yè)序列來說，

41、某種算法能將該對于某一作業(yè)序列來說，某種算法能將該作業(yè)序列中所有作業(yè)安置完畢，那么我們作業(yè)序列中所有作業(yè)安置完畢，那么我們說說該算法對這一作業(yè)序列是合適的。該算法對這一作業(yè)序列是合適的。v對于某一算法而言，如它不能立即滿足某對于某一算法而言，如它不能立即滿足某一要求，而其它算法卻可以滿足此要求，一要求，而其它算法卻可以滿足此要求，則則這一算法對該作業(yè)序列是不合適的。這一算法對該作業(yè)序列是不合適的。63例題例題v例例1 1：有作業(yè)序列：作業(yè)：有作業(yè)序列：作業(yè)A A要求要求18K18K；作業(yè)；作業(yè)B B要要求求25K25K，作業(yè)，作業(yè)C C要求要求30K30K。系統(tǒng)中空閑區(qū)按三種。系統(tǒng)中空閑區(qū)按三

42、種算法組成的空閑區(qū)隊列，現(xiàn)在請你分析哪種算法組成的空閑區(qū)隊列，現(xiàn)在請你分析哪種算法適合該作業(yè)序列？算法適合該作業(yè)序列？ OS30作業(yè)作業(yè)作業(yè)作業(yè)2046作業(yè)作業(yè)5205010012016016016521025664 例題例題最先最先分配前內存分配前內存 分配前內存自由鏈分配前內存自由鏈作業(yè)作業(yè) 請求長度請求長度A18B25C30請求表請求表65例題例題v經(jīng)分析可知：最佳適應法對這個作業(yè)序列是經(jīng)分析可知：最佳適應法對這個作業(yè)序列是合適的，而其它兩種對該作業(yè)序列是不合適合適的，而其它兩種對該作業(yè)序列是不合適的。的。v因為最先適應算法和最壞適應算法對于作業(yè)因為最先適應算法和最壞適應算法對于作業(yè)C來

43、說都不能為它分配所需要的內存空間。來說都不能為它分配所需要的內存空間。66練練 習習v如果現(xiàn)在作業(yè)序列變?yōu)橐韵虑闆r，分析如果現(xiàn)在作業(yè)序列變?yōu)橐韵虑闆r，分析哪種算法適合于這個作業(yè)序列？哪種算法適合于這個作業(yè)序列？作業(yè)作業(yè)A A要求要求21K21K，作業(yè)，作業(yè)B B要求要求30K30K，作業(yè)，作業(yè)C C要求要求25K25K。675.2.3 有關分區(qū)管理其他問題的討論有關分區(qū)管理其他問題的討論v1、關于虛存的實現(xiàn)、關于虛存的實現(xiàn)v2、關于內存擴充、關于內存擴充v3、關于地址變換和內存保護、關于地址變換和內存保護v4、分區(qū)存儲管理的主要優(yōu)缺點、分區(qū)存儲管理的主要優(yōu)缺點681、關于虛存的實現(xiàn)、關于虛存的

44、實現(xiàn)v無法實現(xiàn)那種用戶進程所需內存容量只受內無法實現(xiàn)那種用戶進程所需內存容量只受內存和外存容量之和限制的虛擬存儲器。存和外存容量之和限制的虛擬存儲器。v如果不采用內存擴充技術，每個用戶進程所如果不采用內存擴充技術，每個用戶進程所需內存容量是受到分區(qū)大小限制的。需內存容量是受到分區(qū)大小限制的。692、關于內存擴充、關于內存擴充v可以使用覆蓋或交換技術來擴充內存可以使用覆蓋或交換技術來擴充內存703、關于地址變換和內存保護、關于地址變換和內存保護v靜態(tài)地址重定位和動態(tài)地址重定位技術，都靜態(tài)地址重定位和動態(tài)地址重定位技術，都可用來完成分區(qū)式內存管理的地址變換?？捎脕硗瓿煞謪^(qū)式內存管理的地址變換。v不

45、能使用靜態(tài)地址重定位的方法來完成動態(tài)不能使用靜態(tài)地址重定位的方法來完成動態(tài)分區(qū)時的地址變換。分區(qū)時的地址變換。v動態(tài)地址重定位中的一對硬件寄存器除了完動態(tài)地址重定位中的一對硬件寄存器除了完成動態(tài)地址重定位的功能之外，還具有保護成動態(tài)地址重定位的功能之外，還具有保護內存中數(shù)據(jù)和程序的功能。內存中數(shù)據(jù)和程序的功能。v保護鍵法也可用來對內存各分區(qū)提供保護。保護鍵法也可用來對內存各分區(qū)提供保護。714、分區(qū)存儲管理的主要優(yōu)缺點、分區(qū)存儲管理的主要優(yōu)缺點v優(yōu)點：優(yōu)點：實現(xiàn)了多個作業(yè)或進程對內存的共享，提高了系實現(xiàn)了多個作業(yè)或進程對內存的共享，提高了系統(tǒng)的資源利用率。統(tǒng)的資源利用率。該方法要求的硬件支持少，管理算法簡單，實現(xiàn)該方法要求的硬件支