OS041-43存儲(chǔ)管理-2014-2015-2

1、操作系統(tǒng)操作系統(tǒng)Operating Systems笫四章笫四章 存儲(chǔ)器管理存儲(chǔ)器管理笫四章笫四章 存儲(chǔ)器管理存儲(chǔ)器管理4.1 存儲(chǔ)器的層次結(jié)構(gòu)存儲(chǔ)器的層次結(jié)構(gòu) 4.2 程序的裝入和鏈接程序的裝入和鏈接4.3連續(xù)分配存儲(chǔ)管理方式連續(xù)分配存儲(chǔ)管理方式4.4對(duì)換對(duì)換4.5分頁存儲(chǔ)管理方式分頁存儲(chǔ)管理方式4.6分段存儲(chǔ)管理方式分段存儲(chǔ)管理方式圖圖4-1 計(jì)算機(jī)系統(tǒng)存儲(chǔ)層次示意計(jì)算機(jī)系統(tǒng)存儲(chǔ)層次示意 寄存器高速緩存主存磁盤緩存磁盤可移動(dòng)存儲(chǔ)介質(zhì)CPU寄存器主存輔存制造成本趨高制造成本趨高訪問速度趨慢訪問速度趨慢4.1 存儲(chǔ)器的層次結(jié)構(gòu)存儲(chǔ)器的層次結(jié)構(gòu) CPUWord TransferFastFastes

2、tFastLessfastSlowSlowBlock TransferCacheMain MemoryFigure 1.16 Cache and Main Memory(a) Single cache(b) Three-level cache organizationCPULevel 1(L1) cacheLevel 2(L2) cacheLevel 3(L3) cacheMainMemory高速緩存（高速緩存（Cache） 介于寄存器和存儲(chǔ)器之間介于寄存器和存儲(chǔ)器之間的存儲(chǔ)器的存儲(chǔ)器 容量遠(yuǎn)大于寄存器容量遠(yuǎn)大于寄存器 訪問速度快于主存儲(chǔ)器訪問速度快于主存儲(chǔ)器 主要用于備份主存中較常主要用于備

3、份主存中較常用的數(shù)據(jù)用的數(shù)據(jù) 以減少處理機(jī)對(duì)主存儲(chǔ)以減少處理機(jī)對(duì)主存儲(chǔ)器的訪問次數(shù)。器的訪問次數(shù)。磁盤緩存磁盤緩存 緩和兩者之間在速度上的不匹配緩和兩者之間在速度上的不匹配 磁盤的磁盤的I/O速度遠(yuǎn)低于對(duì)主存的訪問速度速度遠(yuǎn)低于對(duì)主存的訪問速度 用于暫時(shí)存放頻繁使用的一部分磁盤數(shù)據(jù)和信息用于暫時(shí)存放頻繁使用的一部分磁盤數(shù)據(jù)和信息 以減少訪問磁盤的次數(shù)。以減少訪問磁盤的次數(shù)。 磁盤緩存與高速緩存磁盤緩存與高速緩存 磁盤緩存并不是一種實(shí)際存在的存儲(chǔ)器磁盤緩存并不是一種實(shí)際存在的存儲(chǔ)器 利用主存中的部分存儲(chǔ)空間暫時(shí)存放從磁盤中讀出利用主存中的部分存儲(chǔ)空間暫時(shí)存放從磁盤中讀出(或或?qū)懭雽懭?的信息的信

4、息主存儲(chǔ)器管理功能主存儲(chǔ)器管理功能 存儲(chǔ)分配和回收存儲(chǔ)分配和回收 分配和回收算法及相應(yīng)的數(shù)據(jù)結(jié)構(gòu)分配和回收算法及相應(yīng)的數(shù)據(jù)結(jié)構(gòu) 地址變換和重定位地址變換和重定位 存儲(chǔ)共享和保護(hù)存儲(chǔ)共享和保護(hù) 存儲(chǔ)器擴(kuò)充存儲(chǔ)器擴(kuò)充 交換交換 虛擬存儲(chǔ)的請(qǐng)求調(diào)入和預(yù)調(diào)入虛擬存儲(chǔ)的請(qǐng)求調(diào)入和預(yù)調(diào)入物理地址空間物理地址空間 把內(nèi)存分成若干個(gè)大小相等的存儲(chǔ)單元把內(nèi)存分成若干個(gè)大小相等的存儲(chǔ)單元 存儲(chǔ)單元占存儲(chǔ)單元占8位，稱作字節(jié)（位，稱作字節(jié)（byte） 每個(gè)單元給一個(gè)編號(hào)每個(gè)單元給一個(gè)編號(hào) 這個(gè)編號(hào)稱為內(nèi)存地址這個(gè)編號(hào)稱為內(nèi)存地址物理地址、絕對(duì)地址、實(shí)地址物理地址、絕對(duì)地址、實(shí)地址 物理地址空間：物理地址空間： 物理

5、地址的集合稱為物理地址空間（主存地址空間）物理地址的集合稱為物理地址空間（主存地址空間）1000邏輯地址空間邏輯地址空間 邏輯地址空間邏輯地址空間 生成的目標(biāo)程序占據(jù)一定的地址空生成的目標(biāo)程序占據(jù)一定的地址空間，稱為程序的邏輯地址空間（簡(jiǎn)間，稱為程序的邏輯地址空間（簡(jiǎn)稱邏輯空間）。稱邏輯空間）。 每個(gè)目標(biāo)程序都是以每個(gè)目標(biāo)程序都是以0為基址順序?yàn)榛讽樞蜻M(jìn)行編址的進(jìn)行編址的 在邏輯空間中每條指令的地址和指令在邏輯空間中每條指令的地址和指令中要訪問的操作數(shù)地址統(tǒng)稱為邏輯地中要訪問的操作數(shù)地址統(tǒng)稱為邏輯地址。址。Load A 500 34560100500邏輯地址空間邏輯地址空間gcc -o te

6、st test.c 邏輯地址和物理地址邏輯地址和物理地址When running a user program, the CPU deals with logical addresses.The memory controller sees a stream of physical addresses.The memory management unit (MMU) does the conversion.CPUMMUVirtualAddressesPhysicalAddresses4.2 程序的裝入和鏈接程序的裝入和鏈接 鏈接鏈接動(dòng)態(tài)動(dòng)態(tài)重定重定位位靜態(tài)靜態(tài)重定重定位位源程序源程序模塊模塊1

7、 1源程序源程序模塊模塊2 2源程序源程序模塊模塊n n目標(biāo)目標(biāo)模塊模塊1 1目標(biāo)目標(biāo)模塊模塊2 2目標(biāo)目標(biāo)模塊模塊n n目標(biāo)代碼目標(biāo)代碼( (裝入模裝入模塊塊)()(輔存輔存) )編譯編譯裝入裝入執(zhí)行執(zhí)行程序名字空間程序名字空間邏輯地址空間邏輯地址空間物理地址空間物理地址空間可執(zhí)行可執(zhí)行二進(jìn)代二進(jìn)代碼碼( (主存主存) )庫(kù)代碼庫(kù)代碼可執(zhí)行可執(zhí)行二進(jìn)代二進(jìn)代碼碼( (主存主存) ) 0 0m-1m-10 00 0Typical programming stepstest1.c, test2.cgcc c test1.c;gcc c test2.c; test1.o, test2.ogcc o

8、 test test1.o test2.o lmylib -lmtest./testC sourceC sourcecompilercompilerobjectmoduleobjectmodulelinkerOther objectmodulesSystemlibraryLoad moduleloadermemoryimagemylib,Compile timeLoad timeRun timeDynamicallyLoadedSystem library4.2.1 程序的裝入程序的裝入 絕對(duì)裝入方式（絕對(duì)裝入方式（ Absolute Loading Mode） 可重定位裝入方式（可重定位裝入

9、方式（ Relocation Loading Mode） 動(dòng)態(tài)運(yùn)行時(shí)裝入方式（動(dòng)態(tài)運(yùn)行時(shí)裝入方式（ Dynamic Run-time Loading）1. 1. 絕對(duì)裝入方式絕對(duì)裝入方式 程序中的邏輯地址與實(shí)際內(nèi)存地址完全相同程序中的邏輯地址與實(shí)際內(nèi)存地址完全相同。 只能將目標(biāo)模塊裝入內(nèi)存中事先指定的位置。只能將目標(biāo)模塊裝入內(nèi)存中事先指定的位置。絕對(duì)裝入方式只適用于單道程序環(huán)境。絕對(duì)裝入方式只適用于單道程序環(huán)境。Load A 500Load A 500 3456 34560 01001005 50000邏輯地址空間邏輯地址空間Load A 500Load A 500 3456 34560 01

10、001005 50000物理地址空間物理地址空間2. 2. 可重定位裝入方式可重定位裝入方式 根據(jù)內(nèi)存的當(dāng)前情況，將裝入模塊裝入到內(nèi)存的適當(dāng)位置根據(jù)內(nèi)存的當(dāng)前情況，將裝入模塊裝入到內(nèi)存的適當(dāng)位置 又稱又稱靜態(tài)重定位靜態(tài)重定位：地址變換在裝入時(shí)一次完成：地址變換在裝入時(shí)一次完成LOAD 1,2500365LOAD 1,2500365100001100012500150005000250010000作 業(yè) 地 址 空 間內(nèi) 存 空 間LOAD 1,12500可重定位裝入方式特點(diǎn)可重定位裝入方式特點(diǎn) 可用于多道程序環(huán)境可用于多道程序環(huán)境 可將裝入模塊裝入到內(nèi)存中任何允許的位置可將裝入模塊裝入到內(nèi)存中

11、任何允許的位置 不允許程序運(yùn)行時(shí)在內(nèi)存中移動(dòng)位置。不允許程序運(yùn)行時(shí)在內(nèi)存中移動(dòng)位置。 在運(yùn)行過程中它在內(nèi)存中的位置可能經(jīng)常要改變?cè)谶\(yùn)行過程中它在內(nèi)存中的位置可能經(jīng)常要改變 此時(shí)就應(yīng)采用動(dòng)態(tài)運(yùn)行時(shí)裝入的方式此時(shí)就應(yīng)采用動(dòng)態(tài)運(yùn)行時(shí)裝入的方式 Load A, 2500 36502500邏輯地址空間邏輯地址空間Load A, 3651000012500物理地址空間物理地址空間1250020000Load A,22500365225003. 3. 動(dòng)態(tài)運(yùn)行時(shí)裝入方式動(dòng)態(tài)運(yùn)行時(shí)裝入方式 在把裝入模塊裝入內(nèi)存后，并不立即把裝入模塊中的相對(duì)在把裝入模塊裝入內(nèi)存后，并不立即把裝入模塊中的相對(duì)地址轉(zhuǎn)換為絕對(duì)地址地

12、址轉(zhuǎn)換為絕對(duì)地址 把這種地址轉(zhuǎn)換推遲到程序真正要執(zhí)行時(shí)才進(jìn)行。把這種地址轉(zhuǎn)換推遲到程序真正要執(zhí)行時(shí)才進(jìn)行。 裝入內(nèi)存后的所有地址都仍是相對(duì)地址。裝入內(nèi)存后的所有地址都仍是相對(duì)地址。 地址變換發(fā)生在程序執(zhí)行過程中！地址變換發(fā)生在程序執(zhí)行過程中！ 動(dòng)態(tài)重定位動(dòng)態(tài)重定位程序的鏈接程序的鏈接 靜態(tài)鏈接方式（靜態(tài)鏈接方式（ Static Linking） 裝入時(shí)動(dòng)態(tài)鏈接裝入時(shí)動(dòng)態(tài)鏈接（ Load-time Dynamic Linking） 運(yùn)行時(shí)動(dòng)態(tài)鏈接（運(yùn)行時(shí)動(dòng)態(tài)鏈接（ Run-time Dynamic Linking）程序的鏈接程序的鏈接 靜態(tài)鏈接靜態(tài)鏈接 在程序運(yùn)行之前，先將各目標(biāo)模塊及它們所需的

13、庫(kù)函數(shù)在程序運(yùn)行之前，先將各目標(biāo)模塊及它們所需的庫(kù)函數(shù)，鏈接成一個(gè)完整的，鏈接成一個(gè)完整的裝配裝配模塊，以后不再拆開。模塊，以后不再拆開。 修改相對(duì)地址；修改相對(duì)地址； 變換外部調(diào)用符號(hào)；變換外部調(diào)用符號(hào)； Module ACALL BReturnLength LModule BCALL CReturnLength MModule CReturnLength N0L-1Module AJSR “L”ReturnModule BJSR “L+M”ReturnModule CReturnLL+M-1L+ML+M+N-1Object ModulesLoad Module0L-10M-10N-1裝入前

14、裝入前鏈接修鏈接修改地址改地址靜態(tài)鏈接靜態(tài)鏈接裝入時(shí)動(dòng)態(tài)鏈接裝入時(shí)動(dòng)態(tài)鏈接 在裝入內(nèi)存時(shí)，邊裝入邊鏈接。在裝入內(nèi)存時(shí)，邊裝入邊鏈接。Module ACALL BReturnLength LModule BCALL CReturnLength MModule CReturnLength N0L-1Module AJSR “L”ReturnModule BJSR “L+M”ReturnModule CReturnLL+M-1L+ML+M+N-1Object Modules0L-10M-10N-1裝入時(shí)裝入時(shí)鏈接修鏈接修改地址改地址外存外存內(nèi)存內(nèi)存裝入時(shí)動(dòng)態(tài)鏈接優(yōu)點(diǎn)裝入時(shí)動(dòng)態(tài)鏈接優(yōu)點(diǎn) 便于修改和更新

15、便于修改和更新 靜態(tài)鏈接靜態(tài)鏈接若更新某個(gè)模塊，則需重新鏈接全部應(yīng)用程序模塊若更新某個(gè)模塊，則需重新鏈接全部應(yīng)用程序模塊 gcc -o test test1.o test2.o 便于實(shí)現(xiàn)對(duì)目標(biāo)模塊的共享便于實(shí)現(xiàn)對(duì)目標(biāo)模塊的共享 靜態(tài)鏈接靜態(tài)鏈接每個(gè)模塊都包含有其目標(biāo)模塊的拷貝每個(gè)模塊都包含有其目標(biāo)模塊的拷貝 裝入時(shí)動(dòng)態(tài)鏈接裝入時(shí)動(dòng)態(tài)鏈接易將一個(gè)目標(biāo)模塊鏈接到幾個(gè)應(yīng)用模塊中易將一個(gè)目標(biāo)模塊鏈接到幾個(gè)應(yīng)用模塊中g(shù)cc -o test3 test4.o test2.o運(yùn)行時(shí)動(dòng)態(tài)鏈接運(yùn)行時(shí)動(dòng)態(tài)鏈接 運(yùn)行時(shí)動(dòng)態(tài)鏈接運(yùn)行時(shí)動(dòng)態(tài)鏈接 將對(duì)某些模塊的將對(duì)某些模塊的鏈接推遲鏈接推遲到程序執(zhí)行時(shí)才進(jìn)行鏈接到程序執(zhí)

16、行時(shí)才進(jìn)行鏈接 在在執(zhí)行過程中執(zhí)行過程中，當(dāng)發(fā)現(xiàn)一個(gè)被調(diào)用模塊尚未裝入內(nèi)存，當(dāng)發(fā)現(xiàn)一個(gè)被調(diào)用模塊尚未裝入內(nèi)存時(shí)，立即由時(shí)，立即由OSOS去找到該模塊并將之去找到該模塊并將之裝入內(nèi)存裝入內(nèi)存， 把它把它鏈鏈接到調(diào)用者模塊上接到調(diào)用者模塊上運(yùn)行時(shí)動(dòng)態(tài)鏈接特點(diǎn)運(yùn)行時(shí)動(dòng)態(tài)鏈接特點(diǎn) 可加快程序的裝入過程，可節(jié)省大量的內(nèi)存空間可加快程序的裝入過程，可節(jié)省大量的內(nèi)存空間應(yīng)用程序在每次運(yùn)行的模塊可能不相同應(yīng)用程序在每次運(yùn)行的模塊可能不相同凡在執(zhí)行過程中未被用到的目標(biāo)模塊，都不會(huì)被調(diào)入凡在執(zhí)行過程中未被用到的目標(biāo)模塊，都不會(huì)被調(diào)入內(nèi)存和被鏈接到裝入模塊上內(nèi)存和被鏈接到裝入模塊上4.3連續(xù)分配方式連續(xù)分配方式 單

17、一連續(xù)分配單一連續(xù)分配 固定分區(qū)分配固定分區(qū)分配 動(dòng)態(tài)分區(qū)分配動(dòng)態(tài)分區(qū)分配 伙伴系統(tǒng)伙伴系統(tǒng) 動(dòng)態(tài)重定位分區(qū)分配動(dòng)態(tài)重定位分區(qū)分配4.3.14.3.1單一連續(xù)分配單一連續(xù)分配 只能用于單用戶、單任務(wù)的操作系統(tǒng)中。只能用于單用戶、單任務(wù)的操作系統(tǒng)中。 如：如：MS-DOSMS-DOS 把內(nèi)存分為系統(tǒng)區(qū)和用戶區(qū)兩部分把內(nèi)存分為系統(tǒng)區(qū)和用戶區(qū)兩部分 系統(tǒng)區(qū)系統(tǒng)區(qū)僅提供給僅提供給OSOS使用使用通常是放在內(nèi)存的低址部分通常是放在內(nèi)存的低址部分 用戶區(qū)用戶區(qū)是指除系統(tǒng)區(qū)以外的全部?jī)?nèi)存空間，提供給用戶使是指除系統(tǒng)區(qū)以外的全部?jī)?nèi)存空間，提供給用戶使用。用。4.3.24.3.2固定分區(qū)分配固定分區(qū)分配 多道程

18、序的存儲(chǔ)管理多道程序的存儲(chǔ)管理 主存空間被劃分成主存空間被劃分成固定大小固定大小的分區(qū)，每個(gè)分區(qū)只裝入一個(gè)作業(yè)，的分區(qū)，每個(gè)分區(qū)只裝入一個(gè)作業(yè)， 若多個(gè)分區(qū)中都裝有作業(yè)，則它們可以并發(fā)執(zhí)行。若多個(gè)分區(qū)中都裝有作業(yè)，則它們可以并發(fā)執(zhí)行。1 1劃分分區(qū)的方法劃分分區(qū)的方法 分區(qū)大小相等。分區(qū)大小相等。缺點(diǎn)是缺乏靈活性。缺點(diǎn)是缺乏靈活性。 太大：浪費(fèi)太大：浪費(fèi) 太?。翰粔蛴锰。翰粔蛴?內(nèi)部碎片內(nèi)部碎片 由于被裝入的數(shù)據(jù)塊小于分區(qū)由于被裝入的數(shù)據(jù)塊小于分區(qū)大小，從而導(dǎo)致分區(qū)內(nèi)部有空大小，從而導(dǎo)致分區(qū)內(nèi)部有空間浪費(fèi)。間浪費(fèi)。2M1 1劃分分區(qū)的方法劃分分區(qū)的方法(2)(2)分區(qū)大小不等。分區(qū)大小不等。

19、劃分為多個(gè)大、中、小搭配劃分為多個(gè)大、中、小搭配的分區(qū)的分區(qū) 根據(jù)程序大小決定所使用根據(jù)程序大小決定所使用的分區(qū)的分區(qū) 2M2 2內(nèi)存分配內(nèi)存分配 通常將分區(qū)按大小進(jìn)行排隊(duì)，并為之建立一張分區(qū)使用表通常將分區(qū)按大小進(jìn)行排隊(duì)，并為之建立一張分區(qū)使用表操作系統(tǒng)作業(yè)A作業(yè)B作業(yè)C24 KB32 KB64 KB128 KB256 KB分區(qū)號(hào)大小/KB起址/KB狀態(tài)11220已分配23232已分配36464已分配4128128未分配(b) 存儲(chǔ)空間分配情況(a) 分區(qū)說明表問題：并發(fā)進(jìn)程數(shù)受分區(qū)個(gè)數(shù)的制約！問題：并發(fā)進(jìn)程數(shù)受分區(qū)個(gè)數(shù)的制約！出現(xiàn)：有內(nèi)存卻不能運(yùn)行程序或大進(jìn)程無法運(yùn)行！出現(xiàn)：有內(nèi)存卻不能運(yùn)

20、行程序或大進(jìn)程無法運(yùn)行！4.3.34.3.3動(dòng)態(tài)分區(qū)分配動(dòng)態(tài)分區(qū)分配 動(dòng)態(tài)分區(qū)分配是根據(jù)進(jìn)程的實(shí)際需要，動(dòng)態(tài)地為之分配內(nèi)動(dòng)態(tài)分區(qū)分配是根據(jù)進(jìn)程的實(shí)際需要，動(dòng)態(tài)地為之分配內(nèi)存空間。存空間。動(dòng)態(tài)分區(qū)動(dòng)態(tài)分區(qū)外部碎片：在所有分區(qū)外的存儲(chǔ)空間變成越來越多的碎片。外部碎片：在所有分區(qū)外的存儲(chǔ)空間變成越來越多的碎片。動(dòng)態(tài)分區(qū)分配動(dòng)態(tài)分區(qū)分配 優(yōu)點(diǎn)：優(yōu)點(diǎn)： 便于動(dòng)態(tài)申請(qǐng)內(nèi)存便于動(dòng)態(tài)申請(qǐng)內(nèi)存 碎片問題碎片問題( (外部碎片外部碎片) ) 要求連續(xù)的內(nèi)存空間要求連續(xù)的內(nèi)存空間 經(jīng)過一段時(shí)間的分配回收后，內(nèi)存中存在很多很小的經(jīng)過一段時(shí)間的分配回收后，內(nèi)存中存在很多很小的空閑塊。它們每一個(gè)都空閑塊。它們每一個(gè)都很小

21、很小，不足以滿足分配要求；，不足以滿足分配要求；但其總和滿足分配要求。這些空閑塊被稱為碎片。但其總和滿足分配要求。這些空閑塊被稱為碎片。 造成存儲(chǔ)資源的浪費(fèi)造成存儲(chǔ)資源的浪費(fèi)1 1分區(qū)分配中的數(shù)據(jù)結(jié)構(gòu)分區(qū)分配中的數(shù)據(jù)結(jié)構(gòu) 空閑分區(qū)表?？臻e分區(qū)表。設(shè)置一張空閑分區(qū)表，用于記錄每個(gè)空閑分區(qū)的情況。設(shè)置一張空閑分區(qū)表，用于記錄每個(gè)空閑分區(qū)的情況。每個(gè)空閑分區(qū)占一個(gè)表目：包括分區(qū)序號(hào)、分區(qū)始址及每個(gè)空閑分區(qū)占一個(gè)表目：包括分區(qū)序號(hào)、分區(qū)始址及分區(qū)的大小等數(shù)據(jù)項(xiàng)。分區(qū)的大小等數(shù)據(jù)項(xiàng)。 空閑分區(qū)鏈。空閑分區(qū)鏈。前向指針0N 個(gè)字節(jié)可用后向指針0N +2N +23 3分區(qū)分配操作分區(qū)分配操作1) 1) 分配

22、內(nèi)存分配內(nèi)存從頭開始查表檢索完否？m.size u.size?m.size u.sizesize?從該分區(qū)中劃出u.size 大小的分區(qū)將該分區(qū)分配給請(qǐng)求者修改有關(guān)數(shù)據(jù)結(jié)構(gòu)返回返回繼續(xù)檢索下一個(gè)表項(xiàng)將該分區(qū)從鏈中移出YNNYYN動(dòng)態(tài)分區(qū)回收算法（動(dòng)態(tài)分區(qū)回收算法（1） 只需修改其前一分區(qū)只需修改其前一分區(qū)F1F1的大小的大小 X F2 X F2 變?yōu)樽優(yōu)?F1 F1 F1 F1X X回收前回收前X X回收后回收后B B大小大小首址首址20K20K 20K 20K20K20K40K40K60K60K大小大小首址首址40K40K 2 20K0K空閑區(qū)表空閑區(qū)表空閑區(qū)表空閑區(qū)表動(dòng)態(tài)分區(qū)回收算法（動(dòng)態(tài)

23、分區(qū)回收算法（2） 用回收區(qū)的首址作為新空閑區(qū)的首址，大小為兩者之和用回收區(qū)的首址作為新空閑區(qū)的首址，大小為兩者之和 F1 X F F1 X F F1 F1變?yōu)樽優(yōu)?F2 F2X X回收前回收前X X回收后回收后X X大小大小首址首址20K20K 60K 60K40K40K60K60K大小大小首址首址40K40K 40K 40K空閑區(qū)表空閑區(qū)表空閑區(qū)表空閑區(qū)表動(dòng)態(tài)分區(qū)回收算法（動(dòng)態(tài)分區(qū)回收算法（3） 使用使用F1F1的表項(xiàng)和的表項(xiàng)和F1F1的首址，取消的首址，取消F2F2的表項(xiàng)的表項(xiàng) 變?yōu)樽優(yōu)镕1F1 F1 F1 F2 F2X X回收前回收前X X回收后回收后X X60K60K20K20K40

24、K40K大小大小首址首址20K20K 20K 20K20K20K 6 60K0K大小大小首址首址60K60K 2 20K0K空閑區(qū)表空閑區(qū)表空閑區(qū)表空閑區(qū)表動(dòng)態(tài)分區(qū)回收算法動(dòng)態(tài)分區(qū)回收算法（4 4） 回收區(qū)既不與回收區(qū)既不與F1鄰接，又不與鄰接，又不與F2鄰接。鄰接。 這時(shí)應(yīng)為回收區(qū)單獨(dú)建立一新表項(xiàng)，填寫回收區(qū)的首址和這時(shí)應(yīng)為回收區(qū)單獨(dú)建立一新表項(xiàng)，填寫回收區(qū)的首址和大小，并根據(jù)其首址插入到空閑鏈（表）中的適當(dāng)位置。大小，并根據(jù)其首址插入到空閑鏈（表）中的適當(dāng)位置。 F1 X F2 F1 X F2 F1 F2 F1 F2 變?yōu)樽優(yōu)閄 XX X回收前回收前X X回收后回收后大小大小首址首址空閑區(qū)

25、表空閑區(qū)表 40K40K60K60K大小大小首址首址空閑區(qū)表空閑區(qū)表20K20K 40K 40K 動(dòng)態(tài)分區(qū)分配算法動(dòng)態(tài)分區(qū)分配算法 基于順序式搜索的動(dòng)態(tài)分區(qū)分配算法基于順序式搜索的動(dòng)態(tài)分區(qū)分配算法 基于索引搜索的動(dòng)態(tài)分區(qū)分配算法基于索引搜索的動(dòng)態(tài)分區(qū)分配算法4.3.4基于順序式搜索的動(dòng)態(tài)分區(qū)分配算法基于順序式搜索的動(dòng)態(tài)分區(qū)分配算法 首次適應(yīng)算法首次適應(yīng)算法(First(First Fit)Fit) 循環(huán)首次適應(yīng)算法循環(huán)首次適應(yīng)算法(next fit)(next fit) 最佳適應(yīng)算法最佳適應(yīng)算法(best fit)(best fit) 最壞適應(yīng)算法最壞適應(yīng)算法(worst fit)(worst

26、 fit)首次適應(yīng)算法首次適應(yīng)算法(FF)(FF) 要求要求空閑分區(qū)鏈空閑分區(qū)鏈以地址遞增的次序鏈接。以地址遞增的次序鏈接。首次適應(yīng)算法首次適應(yīng)算法(first fit)(first fit) 該算法傾向于優(yōu)先利用內(nèi)存中該算法傾向于優(yōu)先利用內(nèi)存中低址部分低址部分的空閑分區(qū)，從而的空閑分區(qū)，從而保留了高址部分的大空閑區(qū)。保留了高址部分的大空閑區(qū)。 為以后到達(dá)的大作業(yè)分配大的內(nèi)存空間創(chuàng)造了條件。為以后到達(dá)的大作業(yè)分配大的內(nèi)存空間創(chuàng)造了條件。 缺點(diǎn)缺點(diǎn) 低址部分不斷被劃分，會(huì)留下許多難以利用的、低址部分不斷被劃分，會(huì)留下許多難以利用的、很小很小的空閑分區(qū)的空閑分區(qū) 每次查找又都是從低址部分開始，這無

27、疑會(huì)增加每次查找又都是從低址部分開始，這無疑會(huì)增加查找查找可用空閑分區(qū)時(shí)的可用空閑分區(qū)時(shí)的開銷開銷。 循環(huán)首次適應(yīng)算法循環(huán)首次適應(yīng)算法(next fit)(next fit) 該算法是由首次適應(yīng)算法演變而成的。該算法是由首次適應(yīng)算法演變而成的。 在分配內(nèi)存空間時(shí)在分配內(nèi)存空間時(shí) 不再是每次都從鏈?zhǔn)组_始查找，不再是每次都從鏈?zhǔn)组_始查找， 是從上次找到的空閑分區(qū)的是從上次找到的空閑分區(qū)的下一個(gè)空閑分區(qū)下一個(gè)空閑分區(qū)開始查找開始查找 直至找到一個(gè)能滿足要求的空閑分區(qū)直至找到一個(gè)能滿足要求的空閑分區(qū) 從中劃出一塊與請(qǐng)求大小相等的內(nèi)存空間分配給作業(yè)從中劃出一塊與請(qǐng)求大小相等的內(nèi)存空間分配給作業(yè) 應(yīng)設(shè)置一

28、應(yīng)設(shè)置一起始查尋指針起始查尋指針，用于指示下一次起始查尋的空閑，用于指示下一次起始查尋的空閑分區(qū)，并采用循環(huán)查找方式分區(qū)，并采用循環(huán)查找方式循環(huán)首次適應(yīng)算法循環(huán)首次適應(yīng)算法(next fit)(next fit) 使內(nèi)存中的空閑分區(qū)分布得更均勻使內(nèi)存中的空閑分區(qū)分布得更均勻 減少了查找空閑分區(qū)時(shí)的開銷減少了查找空閑分區(qū)時(shí)的開銷 會(huì)缺乏大的空閑分區(qū)。會(huì)缺乏大的空閑分區(qū)。 最佳適應(yīng)算法最佳適應(yīng)算法(best fit)(best fit) 把能滿足要求、又是最小的空閑分區(qū)分配給作業(yè)把能滿足要求、又是最小的空閑分區(qū)分配給作業(yè) 將所有的空閑分區(qū)按其容量以從小到大的順序形成一空將所有的空閑分區(qū)按其容量以從

29、小到大的順序形成一空閑分區(qū)鏈。閑分區(qū)鏈。 在存儲(chǔ)器中會(huì)留下許多難以利用的小空閑區(qū)。在存儲(chǔ)器中會(huì)留下許多難以利用的小空閑區(qū)。 最壞適應(yīng)算法最壞適應(yīng)算法(worst fit)(worst fit) 優(yōu)點(diǎn)優(yōu)點(diǎn) 可使剩下的空閑區(qū)不至于太小，產(chǎn)生碎片的幾率最小可使剩下的空閑區(qū)不至于太小，產(chǎn)生碎片的幾率最小 對(duì)中、小作業(yè)有利，查找效率很高。對(duì)中、小作業(yè)有利，查找效率很高。 缺點(diǎn)：它會(huì)使存儲(chǔ)器中缺乏大的空閑分區(qū)。缺點(diǎn)：它會(huì)使存儲(chǔ)器中缺乏大的空閑分區(qū)。練習(xí)練習(xí) 在動(dòng)態(tài)分區(qū)分配存儲(chǔ)管理下，按地址排列的內(nèi)存空閑區(qū)為：在動(dòng)態(tài)分區(qū)分配存儲(chǔ)管理下，按地址排列的內(nèi)存空閑區(qū)為：10K 、4K 、20K 、18K 、7K 、

30、9K 、12K 和和15K 。 對(duì)于下列的連續(xù)存儲(chǔ)區(qū)的請(qǐng)求：對(duì)于下列的連續(xù)存儲(chǔ)區(qū)的請(qǐng)求： 12K 、10K 、9K， 試問：使用首次適應(yīng)算法、最佳適應(yīng)算法、最壞適應(yīng)算法和試問：使用首次適應(yīng)算法、最佳適應(yīng)算法、最壞適應(yīng)算法和循環(huán)首次適應(yīng)算法循環(huán)首次適應(yīng)算法，哪個(gè)空閑區(qū)被使用？，哪個(gè)空閑區(qū)被使用？首次適應(yīng)分配算法首次適應(yīng)分配算法要求空閑區(qū)按要求空閑區(qū)按首址遞增首址遞增的次序組織空閑區(qū)表（隊(duì)列）的次序組織空閑區(qū)表（隊(duì)列） 。順序查找未分配區(qū)表或鏈表，直到找第一能滿足長(zhǎng)度要順序查找未分配區(qū)表或鏈表，直到找第一能滿足長(zhǎng)度要求的空閑區(qū)為止，分割此分區(qū)。求的空閑區(qū)為止，分割此分區(qū)。 按地址排列的內(nèi)存空閑區(qū)為

31、：按地址排列的內(nèi)存空閑區(qū)為： 10KB、4KB、20KB、18KB、7KB、9KB、12KB、15KB 請(qǐng)求序列：請(qǐng)求序列：12KB; 10KB ; 9KB : 8KB 9KB最佳適應(yīng)分配算法最佳適應(yīng)分配算法 要求按要求按空閑區(qū)大小空閑區(qū)大小從小到大的次序組成空閑區(qū)表從小到大的次序組成空閑區(qū)表挑選一個(gè)能滿足用戶要求的最小分區(qū)。挑選一個(gè)能滿足用戶要求的最小分區(qū)。 按地址排列的內(nèi)存空閑區(qū)為：按地址排列的內(nèi)存空閑區(qū)為： 10KB、4KB、20KB、18KB、7KB、9KB、12KB、15KB按按空閑區(qū)大小空閑區(qū)大小: : 4KB 7KB 9KB 10KB 12KB 15KB 18KB 20KB請(qǐng)求序

32、列：請(qǐng)求序列：12KB; 10KB ; 9KB : 最壞適應(yīng)分配算法最壞適應(yīng)分配算法要求空閑區(qū)要求空閑區(qū)按大小遞減按大小遞減的順序組織空閑區(qū)表的順序組織空閑區(qū)表掃描整個(gè)未分配區(qū)鏈表，挑選一個(gè)最大的空閑區(qū)分割掃描整個(gè)未分配區(qū)鏈表，挑選一個(gè)最大的空閑區(qū)分割 按地址排列的內(nèi)存空閑區(qū)為：按地址排列的內(nèi)存空閑區(qū)為： 10KB、4KB、20KB、18KB、7KB、9KB、12KB、15KB按按空閑區(qū)大小空閑區(qū)大小: :20KB 18KB 15KB12KB 10KB 9KB 7KB 4KB請(qǐng)求序列：請(qǐng)求序列：12KB; 10KB ; 9KB : 8KB8KB6KB循環(huán)首次適應(yīng)算法循環(huán)首次適應(yīng)算法要求空閑區(qū)按

33、要求空閑區(qū)按首址遞增首址遞增的次序組織空閑區(qū)表（隊(duì)列）的次序組織空閑區(qū)表（隊(duì)列） 。從未分配區(qū)的上次掃描結(jié)束處順序查找。從未分配區(qū)的上次掃描結(jié)束處順序查找。按地址排列的內(nèi)存空閑區(qū)為：按地址排列的內(nèi)存空閑區(qū)為： 10KB、4KB、20KB、18KB、7KB、9KB、12KB、15KB請(qǐng)求序列：請(qǐng)求序列：12KB; 10KB ; 9KB : 8KB8KB 對(duì)如圖所示的內(nèi)存分配情況對(duì)如圖所示的內(nèi)存分配情況(其中，其中，陰影部分表示已占用塊，空白部分陰影部分表示已占用塊，空白部分表示空閑塊表示空閑塊)，若要申請(qǐng)一塊，若要申請(qǐng)一塊40KB的內(nèi)存，對(duì)于最佳適應(yīng)算法，給出的內(nèi)存，對(duì)于最佳適應(yīng)算法，給出分配區(qū)

34、域的首地址分配區(qū)域的首地址_。A.100KB B.190KBC.330KB D.410KB102K60K90K80K0KB100KB180KB190KB280KB330KB390KB410KB512KBC問題問題思考思考 假設(shè)使用固定分區(qū)的內(nèi)存管理方案，分區(qū)大小為假設(shè)使用固定分區(qū)的內(nèi)存管理方案，分區(qū)大小為216字節(jié)，字節(jié)，內(nèi)存總大小為內(nèi)存總大小為224字節(jié)。系統(tǒng)維護(hù)著一張進(jìn)程表，為每個(gè)常字節(jié)。系統(tǒng)維護(hù)著一張進(jìn)程表，為每個(gè)常駐進(jìn)程保存指向一個(gè)分區(qū)的指針，這個(gè)指針需要多少位？駐進(jìn)程保存指向一個(gè)分區(qū)的指針，這個(gè)指針需要多少位？ 分區(qū)數(shù)：分區(qū)數(shù)： 224/216 = 284.3.54.3.5基于索引搜

35、索的動(dòng)態(tài)分區(qū)分配算法基于索引搜索的動(dòng)態(tài)分區(qū)分配算法 快速適應(yīng)算法快速適應(yīng)算法(quick fit)(quick fit) 伙伴系統(tǒng)伙伴系統(tǒng) 哈希算法哈希算法伙伴系統(tǒng)伙伴系統(tǒng) 固定分區(qū)和動(dòng)態(tài)分區(qū)方式的折衷固定分區(qū)和動(dòng)態(tài)分區(qū)方式的折衷 分區(qū)大小均為分區(qū)大小均為2 2的的K K次冪次冪，L LK KM M。 2L = 分配的最小分區(qū)大小分配的最小分區(qū)大小 2M = 分配的最大分區(qū)大小，通常是整個(gè)可分配的內(nèi)存大小分配的最大分區(qū)大小，通常是整個(gè)可分配的內(nèi)存大小 伙伴通過對(duì)大塊的物理主存劃分而獲得伙伴通過對(duì)大塊的物理主存劃分而獲得 每次都對(duì)半劃分每次都對(duì)半劃分2M 2M-1 n 2M 2M-1 2M-1

36、伙伴原理伙伴原理 兩個(gè)伙伴的大小必須相同兩個(gè)伙伴的大小必須相同 無論已分配分區(qū)或空閑分區(qū)其大小均為無論已分配分區(qū)或空閑分區(qū)其大小均為2的的k次冪。次冪。2M 2M-2 n 2M-12M-2 2M-2 伙伴原理伙伴原理 直到產(chǎn)生大于或等于直到產(chǎn)生大于或等于n的最小塊的最小塊2M 2M-2 2M-2 空閑分區(qū)雙向鏈表空閑分區(qū)雙向鏈表 在系統(tǒng)運(yùn)行過程中，因不斷劃分，可形成若干個(gè)不連續(xù)空在系統(tǒng)運(yùn)行過程中，因不斷劃分，可形成若干個(gè)不連續(xù)空閑分區(qū)。閑分區(qū)。 對(duì)每一類具有相同大小的空閑分區(qū)，單獨(dú)設(shè)立一個(gè)空對(duì)每一類具有相同大小的空閑分區(qū)，單獨(dú)設(shè)立一個(gè)空閑分區(qū)雙向鏈表。閑分區(qū)雙向鏈表。0 k-12L2k-12k

37、2M0 k0 k 當(dāng)需要為進(jìn)程分配一個(gè)長(zhǎng)度為當(dāng)需要為進(jìn)程分配一個(gè)長(zhǎng)度為n的存儲(chǔ)空間時(shí)，的存儲(chǔ)空間時(shí)， 計(jì)算一個(gè)計(jì)算一個(gè) i 值，使值，使 2i1 n 2i， 在空閑分區(qū)大小為在空閑分區(qū)大小為2i的空閑分區(qū)鏈表中查找。的空閑分區(qū)鏈表中查找。 若找到，把該空閑分區(qū)分配給進(jìn)程。若找到，把該空閑分區(qū)分配給進(jìn)程。 否則，表明長(zhǎng)度為否則，表明長(zhǎng)度為2i的空閑分區(qū)已經(jīng)耗盡，的空閑分區(qū)已經(jīng)耗盡，在分區(qū)大小為在分區(qū)大小為2i1的空閑分區(qū)鏈表中尋找。的空閑分區(qū)鏈表中尋找。 若存在若存在2i1的一個(gè)空閑分區(qū)，的一個(gè)空閑分區(qū)，把該空閑分區(qū)分為相等的兩個(gè)分區(qū)，把該空閑分區(qū)分為相等的兩個(gè)分區(qū)，1.這兩個(gè)分區(qū)稱為一對(duì)伙伴，

38、其中的一個(gè)分區(qū)用于分配，而這兩個(gè)分區(qū)稱為一對(duì)伙伴，其中的一個(gè)分區(qū)用于分配，而把另一個(gè)加入分區(qū)大小為把另一個(gè)加入分區(qū)大小為2i的空閑分區(qū)鏈表中的空閑分區(qū)鏈表中2i2i+12i+2 若大小為若大小為2i1的空閑分區(qū)也不存在，則需要查找大小為的空閑分區(qū)也不存在，則需要查找大小為2i2的空閑分區(qū)，的空閑分區(qū)， 若找到則對(duì)其進(jìn)行兩次分割：若找到則對(duì)其進(jìn)行兩次分割：第一次，將其分割為大小為第一次，將其分割為大小為2i1的兩個(gè)分區(qū)的兩個(gè)分區(qū)一個(gè)用于分配一個(gè)用于分配一個(gè)加入到大小為一個(gè)加入到大小為2i1的空閑分區(qū)鏈表中；的空閑分區(qū)鏈表中；第二次，將第一次用于分配的空閑區(qū)分割為：第二次，將第一次用于分配的空閑區(qū)分割為：一個(gè)用于分配，一個(gè)用于分配，一個(gè)加入到大小為一個(gè)加入到大小為2i的空閑分區(qū)鏈表中。的空閑分區(qū)鏈表中。 若仍然找不到，則繼續(xù)查找大小為若仍然找不到，則繼續(xù)查找大小