第五章存儲管理(1)

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

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

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

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

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

6、時(shí)間內(nèi)一般僅使用它的程序的一部分（或一小部分），所以程序僅有的程序的一部分（或一小部分），所以程序僅有部分裝入內(nèi)存完全能夠正確執(zhí)行。部分裝入內(nèi)存完全能夠正確執(zhí)行。v要由操作系統(tǒng)結(jié)合相關(guān)硬件來完成上述工件，這要由操作系統(tǒng)結(jié)合相關(guān)硬件來完成上述工件，這樣計(jì)算機(jī)好象為用戶提供了一個(gè)容量遠(yuǎn)大于內(nèi)存樣計(jì)算機(jī)好象為用戶提供了一個(gè)容量遠(yuǎn)大于內(nèi)存的存儲器，這個(gè)存儲器稱為的存儲器，這個(gè)存儲器稱為虛擬存儲器虛擬存儲器。 105.1.1 虛擬存儲器虛擬存儲器v虛擬存儲器虛擬存儲器呈現(xiàn)在用戶面前的是一個(gè)在呈現(xiàn)在用戶面前的是一個(gè)在物理上只受物理上只受內(nèi)存和外存總?cè)萘肯拗苾?nèi)存和外存總?cè)萘肯拗频拇鎯ο到y(tǒng)，這要求存儲管的存儲

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

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

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

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

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

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

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

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

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

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

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

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

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

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

21、作員或者由操作系統(tǒng)給出，并給出或者由操作系統(tǒng)給出，并給出分區(qū)說明表分區(qū)說明表。在調(diào)度作業(yè)時(shí)，由存儲管理根據(jù)所需量在分在調(diào)度作業(yè)時(shí)，由存儲管理根據(jù)所需量在分區(qū)說明表中找出一個(gè)單元分配給它。區(qū)說明表中找出一個(gè)單元分配給它。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è)大小相當(dāng)，這樣內(nèi)存的使用效率選擇與作業(yè)大小相當(dāng)，這樣內(nèi)存的使用效率較高。較高。v但是若作業(yè)的大小和出現(xiàn)的頻率不知道時(shí)，但是若作業(yè)的大小和出現(xiàn)的頻率不知道時(shí)，勢必造成分區(qū)的大小和作業(yè)的大小相差甚遠(yuǎn)，勢必造成分區(qū)的大小和作業(yè)的大小相差甚遠(yuǎn)，這樣就會造成這樣就會造成存儲空間的浪費(fèi)存儲空間的浪費(fèi)，從而影響整，從而影響整個(gè)系統(tǒng)的效率。個(gè)系統(tǒng)的效率。 362 2、動(dòng)態(tài)分區(qū)、動(dòng)態(tài)分區(qū)v動(dòng)態(tài)分區(qū)：動(dòng)態(tài)分區(qū)：在系統(tǒng)運(yùn)行的過程中建立分區(qū)，在系統(tǒng)運(yùn)行的過程中建立分區(qū)，并使分區(qū)的大小剛好與作業(yè)的大小相等。并使分區(qū)的大小剛好與作業(yè)的大小相等。v這種存儲管理的方法解決了固定分區(qū)嚴(yán)重浪這種

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

40、的，但是但是會造成內(nèi)存碎片較多，影響內(nèi)存利用率，而最壞適用法會造成內(nèi)存碎片較多，影響內(nèi)存利用率，而最壞適用法的內(nèi)存碎片最少，但是對內(nèi)存的請求較多的進(jìn)程有可能的內(nèi)存碎片最少，但是對內(nèi)存的請求較多的進(jìn)程有可能分配失敗。分配失敗?？傊?，三種算法各有所長，針對不同的請求隊(duì)列，它們的總之，三種算法各有所長，針對不同的請求隊(duì)列，它們的效率和功能是不一樣的。效率和功能是不一樣的。624、三種分配算法的比較、三種分配算法的比較v上述三種放置策略各有利弊，到底哪種最上述三種放置策略各有利弊，到底哪種最好不能一概而論，而應(yīng)針對具體作業(yè)序列好不能一概而論，而應(yīng)針對具體作業(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ū)隊(duì)列，現(xiàn)在請你分析哪種算法組成的空閑區(qū)隊(duì)列，現(xiàn)在請你分析哪種算法適合該作業(yè)序列？算法適合該作業(yè)序列？ OS30作業(yè)作業(yè)作業(yè)作業(yè)2046作業(yè)作業(yè)5205010012016016016521025664 例題例題最先最先分配前內(nèi)存分配前內(nèi)存 分配前內(nèi)存自由鏈分配前內(nèi)存自由鏈作業(yè)作業(yè) 請求長度請求長度A18B25C30請求表請求表65例題例題v經(jīng)分析可知：最佳適應(yīng)法對這個(gè)作業(yè)序列是經(jīng)分析可知：最佳適應(yīng)法對這個(gè)作業(yè)序列是合適的，而其它兩種對該作業(yè)序列是不合適合適的，而其它兩種對該作業(yè)序列是不合適的。的。v因?yàn)樽钕冗m應(yīng)算法和最壞適應(yīng)算法對于作業(yè)因?yàn)樽钕冗m應(yīng)算法和最壞適應(yīng)算法對于作業(yè)C來

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

44、實(shí)現(xiàn)v無法實(shí)現(xiàn)那種用戶進(jìn)程所需內(nèi)存容量只受內(nèi)無法實(shí)現(xiàn)那種用戶進(jìn)程所需內(nèi)存容量只受內(nèi)存和外存容量之和限制的虛擬存儲器。存和外存容量之和限制的虛擬存儲器。v如果不采用內(nèi)存擴(kuò)充技術(shù)，每個(gè)用戶進(jìn)程所如果不采用內(nèi)存擴(kuò)充技術(shù)，每個(gè)用戶進(jìn)程所需內(nèi)存容量是受到分區(qū)大小限制的。需內(nèi)存容量是受到分區(qū)大小限制的。692、關(guān)于內(nèi)存擴(kuò)充、關(guān)于內(nèi)存擴(kuò)充v可以使用覆蓋或交換技術(shù)來擴(kuò)充內(nèi)存可以使用覆蓋或交換技術(shù)來擴(kuò)充內(nèi)存703、關(guān)于地址變換和內(nèi)存保護(hù)、關(guān)于地址變換和內(nèi)存保護(hù)v靜態(tài)地址重定位和動(dòng)態(tài)地址重定位技術(shù)，都靜態(tài)地址重定位和動(dòng)態(tài)地址重定位技術(shù)，都可用來完成分區(qū)式內(nèi)存管理的地址變換。可用來完成分區(qū)式內(nèi)存管理的地址變換。v不

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