操作系統(tǒng)存儲(chǔ)管理課件

1、第四章存儲(chǔ)器管理4.1 存儲(chǔ)器的層次結(jié)構(gòu)4.2 程序的裝入和鏈接 4.3 連續(xù)分配方式 第四章存儲(chǔ)器管理 4.1 存儲(chǔ)器的層次結(jié)構(gòu)4.1.1 存儲(chǔ)器的層次結(jié)構(gòu)1. 存儲(chǔ)器的層次結(jié)構(gòu) 在現(xiàn)代計(jì)算機(jī)系統(tǒng)中，存儲(chǔ)器是信息外理的來(lái)源與歸宿，占據(jù)重要位置。但是，在現(xiàn)有技術(shù)條件下，任何一種存儲(chǔ)裝置，都無(wú)法同時(shí)從速度與容量?jī)煞矫妫瑵M足用戶的需求。實(shí)際上它們組成了一個(gè)速度由快到慢，容量由小到大的存儲(chǔ)裝置層次。 存儲(chǔ)器的層次結(jié)構(gòu) 2.各種存儲(chǔ)器高速緩存Cache： 少量的、非常快速、昂貴、易變的內(nèi)存RAM： 若干兆字節(jié)、中等速度、中等價(jià)格、易變的 磁盤： 數(shù)百兆或數(shù)千兆字節(jié)、低速、價(jià)廉、不易變的 由操作系統(tǒng)協(xié)調(diào)

2、這些存儲(chǔ)器的使用 4.1.2 存儲(chǔ)管理的目的1)主存的分配和管理：當(dāng)用戶需要內(nèi)存時(shí),系統(tǒng)為之分配相應(yīng)的存儲(chǔ)空間；不需要時(shí)，及時(shí)回收，以供其它用戶使用。2)提高主存儲(chǔ)器的利用率：不僅能使多道程序動(dòng)態(tài)地共享主存，提高主存利用率，最好還能共享主存中某個(gè)區(qū)域的信息。存儲(chǔ)管理的目的（續(xù)）3)“擴(kuò)充”主存容量：為用戶提供比主存物理空間大得多的地址空間，以至使用戶感覺他的作業(yè)是在這樣一個(gè)大的存儲(chǔ)器中運(yùn)行。4)存儲(chǔ)保護(hù)：確保多道程序都在各自分配到存儲(chǔ)區(qū)域內(nèi)操作，互不干擾，防止一道程序破壞其它作業(yè)或系統(tǒng)文件的信息。 4.1.3. 基本概念1.定位（存儲(chǔ)分配）：為具體的程序和數(shù)據(jù)等分配存儲(chǔ)單元或存儲(chǔ)區(qū)工作。2.映

3、射：把邏輯地址轉(zhuǎn)換為相應(yīng)的物理地址的過程。3.隔離：按存取權(quán)限把合法區(qū)與非法區(qū)分隔，實(shí)現(xiàn)存儲(chǔ)保護(hù)。 4.名空間程序員在程序中定義的標(biāo)識(shí)符程序符號(hào)集合由程序員自定義沒有地址的概念符號(hào)指令數(shù)據(jù)說(shuō)明I/O說(shuō)明 地址空間及存儲(chǔ)空間5.地址空間程序用來(lái)訪問信息所用地址單元的集合邏輯（相對(duì)）地址的集合由編譯程序生成6.存儲(chǔ)空間主存中物理單元的集合物理（絕對(duì)）地址的集合由裝配程序等生成地址映射Load A 200 3456 。 。1200物理地址空間Load A data1data1 3456源程序Load A 200 34560100200編譯連接邏輯地址空間BA=1000圖41名空間、地址空間、存儲(chǔ)空間

4、7.邏輯地址與物理地址邏輯地址（相對(duì)地址，虛地址） ： 用戶的程序經(jīng)過匯編或編譯后形成目標(biāo)代碼，目標(biāo)代碼通常采用相對(duì)地址的形式，其首地址為0，其余指令中的地址都相對(duì)于首地址而編址。 不能用邏輯地址在內(nèi)存中讀取信息物理地址（絕對(duì)地址，實(shí)地址） 內(nèi)存中存儲(chǔ)單元的地址，可直接尋址 8.存儲(chǔ)共享內(nèi)存共享：兩個(gè)或多個(gè)進(jìn)程共用內(nèi)存中相同區(qū)域目的：節(jié)省內(nèi)存空間，提高內(nèi)存利用率實(shí)現(xiàn)進(jìn)程通信（數(shù)據(jù)共享）共享內(nèi)容： 代碼共享，要求代碼為純代碼 數(shù)據(jù)共享 9.存儲(chǔ)保護(hù)與安全保護(hù)目的： 為多個(gè)程序共享內(nèi)存提供保障,使在內(nèi)存中的各道程序, 只能訪問它自己的區(qū)域，避免各道程序間相互干攏，特別是當(dāng)一道程序發(fā)生錯(cuò)誤時(shí), 不致

5、于影響其他程序的運(yùn)行。通常由硬件完成保護(hù)功能，由軟件輔助實(shí)現(xiàn)。（特權(quán)指令不能完成存儲(chǔ)保護(hù)。）1) 存儲(chǔ)保護(hù) 保護(hù)系統(tǒng)程序區(qū)不被用戶侵犯 （有意或無(wú)意的）不允許用戶程序讀寫不屬于自己地址空間的數(shù)據(jù) （系統(tǒng)區(qū)地址空間，其他用戶程序的地址空間）2) 保護(hù)過程-防止地址越界 每個(gè)進(jìn)程都有自己獨(dú)立的進(jìn)程空間，如果一個(gè)進(jìn)程在運(yùn)行時(shí)所產(chǎn)生的地址在其地址空間之外，則發(fā)生地址越界。即當(dāng)程序要訪問某個(gè)內(nèi)存單元時(shí)，由硬件檢查是否允許，如果允許則執(zhí)行，否則產(chǎn)生地址越界中斷，由操作系統(tǒng)進(jìn)行相應(yīng)處理。10.內(nèi)存“擴(kuò)充” 通過虛擬存儲(chǔ)技術(shù)實(shí)現(xiàn) 用戶在編制程序時(shí)，不應(yīng)該受內(nèi)存容量限制，所以要采用一定技術(shù)來(lái)“擴(kuò)充”內(nèi)存的容量，

6、使用戶得到比實(shí)際內(nèi)存容量大的多的內(nèi)存空間具體實(shí)現(xiàn)是在硬件支持下，軟硬件相互協(xié)作，將內(nèi)存和外存結(jié)合起來(lái)統(tǒng)一使用。通過這種方法把內(nèi)存擴(kuò)充，使用戶在編制程序時(shí)不受內(nèi)存限制第四章存儲(chǔ)器管理 4.2 程序的裝入和鏈接4.2 程序的裝入和鏈接圖 4-2-1 對(duì)用戶程序的處理步驟4.2.1 程序的裝入1. 絕對(duì)裝入方式 程序中所使用的絕對(duì)地址，可在編譯或匯編時(shí)給出， 也可由程序員直接賦予。 但在由程序員直接給出絕對(duì)地址時(shí)， 不僅要求程序員熟悉內(nèi)存的使用情況，而且一旦程序或數(shù)據(jù)被修改后，可能要改變程序中的所有地址。因此，通常是寧可在程序中采用符號(hào)地址，然后在編譯或匯編時(shí)，再將這些符號(hào)地址轉(zhuǎn)換為絕對(duì)地址。 2.

7、 可重定位裝入方式圖 4-2-2 作業(yè)裝入內(nèi)存時(shí)的情況3. 動(dòng)態(tài)運(yùn)行時(shí)裝入方式 動(dòng)態(tài)運(yùn)行時(shí)的裝入程序，在把裝入模塊裝入內(nèi)存后，并不立即把裝入模塊中的相對(duì)地址轉(zhuǎn)換為絕對(duì)地址，而是把這種地址轉(zhuǎn)換推遲到程序真正要執(zhí)行時(shí)才進(jìn)行。因此， 裝入內(nèi)存后的所有地址都仍是相對(duì)地址。 4.2.2 程序的鏈接圖 4-2-3 程序鏈接示意圖1.靜態(tài)鏈接方式2. 裝入時(shí)動(dòng)態(tài)鏈接 用戶源程序經(jīng)編譯后所得的目標(biāo)模塊，是在裝入內(nèi)存時(shí)邊裝入邊鏈接的，即在裝入一個(gè)目標(biāo)模塊時(shí)，若發(fā)生一個(gè)外部模塊調(diào)用事件，將引起裝入程序去找出相應(yīng)的外部目標(biāo)模塊，并將它裝入內(nèi)存，還要修改目標(biāo)模塊中的相對(duì)地址。裝入時(shí)動(dòng)態(tài)鏈接方式有以下優(yōu)點(diǎn)： 便于修改和

8、更新。 (2) 便于實(shí)現(xiàn)對(duì)目標(biāo)模塊的共享。 (1) 便于修改和更新。對(duì)于經(jīng)靜態(tài)鏈接裝配在一起的裝入模塊，如果要修改或更新其中的某個(gè)目標(biāo)模塊，則要求重新打開裝入模塊。這不僅是低效的，而且有時(shí)是不可能的。若采用動(dòng)態(tài)鏈接方式，由于各目標(biāo)模塊是分開存放的，所以要修改或更新各目標(biāo)模塊是件非常容易的事。(2) 便于實(shí)現(xiàn)對(duì)目標(biāo)模塊的共享。在采用靜態(tài)鏈接方式時(shí)，每個(gè)應(yīng)用模塊都必須含有其目標(biāo)模塊的拷貝，無(wú)法實(shí)現(xiàn)對(duì)目標(biāo)模塊的共享。但采用裝入時(shí)動(dòng)態(tài)鏈接方式，OS則很容易將一個(gè)目標(biāo)模塊鏈接到幾個(gè)應(yīng)用模塊上，實(shí)現(xiàn)多個(gè)應(yīng)用程序?qū)υ撃K的共享。 3. 運(yùn)行時(shí)動(dòng)態(tài)鏈接 這種鏈接方式是將對(duì)某些模塊的鏈接推遲到執(zhí)行時(shí)才執(zhí)行，即，

9、在執(zhí)行過程中，當(dāng)發(fā)現(xiàn)一個(gè)被調(diào)用模塊尚未裝入內(nèi)存時(shí)，立即由OS去找到該模塊并將之裝入內(nèi)存， 把它鏈接到調(diào)用者模塊上。凡在執(zhí)行過程中未被用到的目標(biāo)模塊，都不會(huì)被調(diào)入內(nèi)存和被鏈接到裝入模塊上，這樣不僅可加快程序的裝入過程，而且可節(jié)省大量的內(nèi)存空間。 4.2.3 重定位 把作業(yè)地址空間中使用的邏輯地址變換成內(nèi)存空間中的物理地址的過程。又稱地址映射。如下圖，作業(yè)i經(jīng)過重定位，把地址集合映射到以1000為始址的內(nèi)存中，作為作業(yè)i的存儲(chǔ)空間。1. 重定位的類型 1)靜態(tài)重定位:當(dāng)用戶程序被裝入內(nèi)存時(shí)，一次性實(shí)現(xiàn)邏輯地址到物理地址的轉(zhuǎn)換，以后不再轉(zhuǎn)換（一般在裝入內(nèi)存時(shí)由軟件完成）作業(yè)i在執(zhí)行前一次變址，直到該

10、作業(yè)完成退出內(nèi)存為止。2)動(dòng)態(tài)重定位2) 動(dòng)態(tài)重定位 在程序運(yùn)行過程中要訪問數(shù)據(jù)時(shí)再進(jìn)行地址變換。由地址變換機(jī)構(gòu)進(jìn)行的地址變換，硬件上需要重定位寄存器的支持。2.動(dòng)態(tài)重定位的實(shí)現(xiàn)方式重定位寄存器：在執(zhí)行一條指令取操作數(shù)時(shí)，要將指令給出的有效地址(500)與重定位寄存器中的內(nèi)容（1000）相加，得訪問地址（1500），從而實(shí)現(xiàn)了地址動(dòng)態(tài)修改。映象方式：采用頁(yè)表來(lái)描述虛、實(shí)頁(yè)面的對(duì)應(yīng)關(guān)系 。第四章存儲(chǔ)器管理 4.3 連續(xù)分配存儲(chǔ)管理 4.3.1 單用戶存儲(chǔ)管理在單道環(huán)境下，不管是單用戶系統(tǒng)還是單道批處理系統(tǒng)，進(jìn)程（作業(yè)）執(zhí)行時(shí)除了系統(tǒng)占用一部分主存外，剩下的主存區(qū)域全部歸它占用。主存可以劃分為三部

11、分：系統(tǒng)區(qū)、用戶區(qū)、空閑區(qū)。用戶占用區(qū)是一個(gè)連續(xù)的存儲(chǔ)區(qū)所以又稱單一連續(xù)區(qū)存儲(chǔ)管理。單用戶系統(tǒng)在一段時(shí)間內(nèi)，只有一個(gè)進(jìn)程在內(nèi)存，故內(nèi)存分配管理十分簡(jiǎn)單，內(nèi)存利用率低。內(nèi)存分為兩個(gè)區(qū)域，一個(gè)供操作系統(tǒng)使用，一個(gè)供用戶使用工作流程 單一連續(xù)區(qū)分配采用靜態(tài)分配和靜態(tài)重定位方式，亦即作業(yè)或進(jìn)程一旦進(jìn)入主存，就一直等到它運(yùn)行結(jié)束后才能釋放主存。如下圖所示的主存分配與回收法。并且由裝入程序檢查其絕對(duì)地址是否超越，即可達(dá)到保護(hù)系統(tǒng)的目的。工作流程(續(xù))單用戶系統(tǒng)缺點(diǎn) 不支持多道。主存利用率不高。程序的運(yùn)行受主存容量限制。 4.3.2 固定分區(qū)分配 分區(qū)式管理是滿足多道程序的最簡(jiǎn)單的存儲(chǔ)管理方案。它的基本思想

12、是將內(nèi)存劃分成若干個(gè)連續(xù)區(qū)域，稱為分區(qū)。每個(gè)分區(qū)只能存儲(chǔ)一個(gè)程序，而且程序也只能在它所駐留的分區(qū)中運(yùn)行。 預(yù)先把可分配的主存儲(chǔ)器空間分割成若干個(gè)連續(xù)區(qū)域，稱為一個(gè)分區(qū)。每個(gè)分區(qū)的大小可以相同也可以不同，如圖所示。但分區(qū)大小固定不變，每個(gè)分區(qū)裝一個(gè)且只能裝一個(gè)作業(yè)存儲(chǔ)分配：如果有一個(gè)空閑區(qū), 則分配給進(jìn)程 1. 固定分區(qū)分區(qū)4分區(qū)3分區(qū)2分區(qū)1操作系統(tǒng)多個(gè)等待隊(duì)列單個(gè)等待隊(duì)列分區(qū)4分區(qū)3分區(qū)2分區(qū)1操作系統(tǒng)圖 4-3-2 固定分區(qū)示意圖 2.內(nèi)存分配管理圖 4-3-3 固定分區(qū)使用表通過設(shè)置內(nèi)存分配表，內(nèi)存分配簡(jiǎn)單缺點(diǎn)：內(nèi)存利用率不高 4.3.2 可變分區(qū)分配 基本思想：內(nèi)存不是預(yù)先劃分好的，而

13、是當(dāng)作業(yè)裝入時(shí)，根據(jù)作業(yè)的需求和內(nèi)存空間的使用情況來(lái)決定是否分配。若有足夠的空間，則按需要分割一部分分區(qū)給該進(jìn)程；否則令其等待主存空間內(nèi)存管理：設(shè)置內(nèi)存空閑塊表記錄了空閑區(qū)起始地址和長(zhǎng)度內(nèi)存分配：動(dòng)態(tài)分配內(nèi)存回收：當(dāng)某一塊歸還后，前后空間合并，修改內(nèi)存空閑塊表1. 分區(qū)分配中的數(shù)據(jù)結(jié)構(gòu)分區(qū)分配表（見圖 4-3-5）(2) 空閑分區(qū)鏈圖 4-3-4 空閑鏈結(jié)構(gòu)0K15K38K48K68K80K110K120K空閑區(qū)表已分配區(qū)表始址長(zhǎng)度標(biāo)志15K23K未分配48K20K未分配80K30K未分配空空始址長(zhǎng)度標(biāo)志0K15KJ138K10KJ268K12KJ3110K10KJ4空空分區(qū)分配表：圖 4-3

14、-5分區(qū)分配表0K15K38K48K68K80K110K120K空閑區(qū)表已分配區(qū)表始址長(zhǎng)度標(biāo)志15K23K未分配48K20K未分配98K12K未分配空空始址長(zhǎng)度標(biāo)志0K15KJ138K10KJ268K12KJ3110K10KJ480K5KJ585K13KJ685K98K 2. 分區(qū)分配操作 1) 分配內(nèi)存 圖 4-3-6 內(nèi)存分配流程 2) 回收內(nèi)存 圖 4-3-7 內(nèi)存回收時(shí)的情況 3.空閑分區(qū)鏈表為了實(shí)現(xiàn)動(dòng)態(tài)分配，系統(tǒng)設(shè)立空閑分區(qū)鏈表：每個(gè)空閑塊的前后兩個(gè)單元，放置必要的說(shuō)明信息和指針。系統(tǒng)只要設(shè)立一個(gè)鏈?zhǔn)字羔槪赶虻谝粋€(gè)空閑塊即可。分配程序可以依照自由塊鏈表，來(lái)查找適合的空閑塊進(jìn)行分配。

15、（如下圖） 4.分配算法 按空閑塊鏈接的方式不同，可以有以下四種算法：首次適應(yīng)算法循環(huán)首次適應(yīng)算法最佳適應(yīng)算法最壞適應(yīng)算法快速適應(yīng)算法1) 首次適應(yīng)算法(first fit)FF算法要求空閑分區(qū)鏈以地址遞增的次序鏈接。在分配內(nèi)存時(shí)，從鏈?zhǔn)组_始順序查找，直至找到一個(gè)大小能滿足要求的空閑分區(qū)為止；從該分區(qū)中劃出一塊內(nèi)存空間分配給請(qǐng)求者，余下的空閑分區(qū)仍留在空閑鏈中。否則此次內(nèi)存分配失敗，返回。該算法優(yōu)先利用內(nèi)存中低址部分的空閑分區(qū)，從而保留了高址部分的大空閑區(qū)。這給為以后到達(dá)的大作業(yè)分配大的內(nèi)存空間創(chuàng)造了條件。缺點(diǎn)是低址部分不斷被劃分，會(huì)留下許多難以利用的、很小的空閑分區(qū)，而每次查找又都是從低址部

16、分開始，這無(wú)疑會(huì)增加查找可用空閑分區(qū)時(shí)的開銷。 2) 循環(huán)首次適應(yīng)算法(next fit)該算法是由首次適應(yīng)算法演變而成的。在為進(jìn)程分配內(nèi)存空間時(shí)，不再是每次都從鏈?zhǔn)组_始查找，而是從上次找到的空閑分區(qū)的下一個(gè)空閑分區(qū)開始查找，直至找到一個(gè)能滿足要求的空閑分區(qū)，從中劃出一塊與請(qǐng)求大小相等的內(nèi)存空間分配給作業(yè)。該算法能使內(nèi)存中的空閑分區(qū)分布得更均勻，從而減少了查找空閑分區(qū)時(shí)的開銷，但這樣會(huì)缺乏大的空閑分區(qū)。 3) 最佳適應(yīng)算法(best fit)所謂“最佳”是指每次為作業(yè)分配內(nèi)存時(shí)，總是把能滿足要求、又是最小的空閑分區(qū)分配給作業(yè)，避免“大材小用”。為了加速尋找，該算法要求將所有的空閑分區(qū)按其容量以

17、從小到大的順序形成一空閑分區(qū)鏈。這樣，第一次找到的能滿足要求的空閑區(qū)，必然是最佳的。孤立地看，最佳適應(yīng)算法似乎是最佳的，然而在宏觀上卻不一定。因?yàn)槊看畏峙浜笏懈钕聛?lái)的剩余部分總是最小的，這樣，在存儲(chǔ)器中會(huì)留下許多難以利用的小空閑區(qū)。 4) 最壞適應(yīng)算法(worst fit)最壞適應(yīng)分配算法要掃描整個(gè)空閑分區(qū)表或鏈表，總是挑選一個(gè)最大的空閑區(qū)分割給作業(yè)使用。其優(yōu)點(diǎn)是可使剩下的空閑區(qū)不至于太小，產(chǎn)生碎片的幾率最小，對(duì)中、小作業(yè)有利，同時(shí)最壞適應(yīng)分配算法查找效率很高。該算法要求將所有的空閑分區(qū)按其容量以從大到小的順序形成一空閑分區(qū)鏈，查找時(shí)只要看第一個(gè)分區(qū)能否滿足作業(yè)要求。該算法的缺點(diǎn)，它會(huì)使存儲(chǔ)

18、器中缺乏大的空閑分區(qū)。最壞適應(yīng)算法與前面所述的首次適應(yīng)算法、循環(huán)首次適應(yīng)算法、最佳適應(yīng)算法一起，也稱為順序搜索法。 5) 快速適應(yīng)算法(quick fit)該算法又稱為分類搜索法，是將空閑分區(qū)根據(jù)其容量大小進(jìn)行分類，對(duì)于每一類具有相同容量的所有空閑分區(qū)，單獨(dú)設(shè)立一個(gè)空閑分區(qū)鏈表。系統(tǒng)中存在多個(gè)空閑分區(qū)鏈表，同時(shí)在內(nèi)存中設(shè)立一張管理索引表，該表的每一個(gè)表項(xiàng)對(duì)應(yīng)了一種空閑分區(qū)類型，并記錄了該類型空閑分區(qū)鏈表表頭的指針?？臻e分區(qū)的分類是根據(jù)進(jìn)程常用的空間大小進(jìn)行劃分，如2 KB、4 KB、8 KB等。 該算法的優(yōu)點(diǎn)是查找效率高，僅需要根據(jù)進(jìn)程的長(zhǎng)度，尋找到能容納它的最小空閑區(qū)鏈表，并取下第一塊進(jìn)行分

19、配即可。該算法的缺點(diǎn)是在分區(qū)歸還主存時(shí)算法復(fù)雜，系統(tǒng)開銷較大。4.3.4伙伴系統(tǒng)固定分區(qū)和動(dòng)態(tài)分區(qū)方式都有不足之處。固定分區(qū)方式限制了活動(dòng)進(jìn)程的數(shù)目，當(dāng)進(jìn)程大小與空閑分區(qū)大小不匹配時(shí)，內(nèi)存空間利用率很低。動(dòng)態(tài)分區(qū)方式算法復(fù)雜，回收空閑分區(qū)時(shí)需要進(jìn)行分區(qū)合并等，系統(tǒng)開銷較大。伙伴系統(tǒng)方式是對(duì)以上兩種內(nèi)存方式的一種折衷方案?；锇橄到y(tǒng)規(guī)定，無(wú)論已分配分區(qū)或空閑分區(qū)，其大小均為2的k次冪，k為整數(shù)，lkm，其中：21表示分配的最小分區(qū)的大小，2m表示分配的最大分區(qū)的大小，通常2m是整個(gè)可分配內(nèi)存的大小。 假設(shè)系統(tǒng)的可利用空間容量為2m個(gè)字，則系統(tǒng)開始運(yùn)行時(shí)，整個(gè)內(nèi)存區(qū)是一個(gè)大小為2m的空閑分區(qū)。在系統(tǒng)

20、運(yùn)行過程中，由于不斷的劃分，可能會(huì)形成若干個(gè)不連續(xù)的空閑分區(qū)，將這些空閑分區(qū)根據(jù)分區(qū)的大小進(jìn)行分類。對(duì)于每一類具有相同大小的所有空閑分區(qū)，單獨(dú)設(shè)立一個(gè)空閑分區(qū)雙向鏈表。這樣，不同大小的空閑分區(qū)形成了k(0km)個(gè)空閑分區(qū)鏈表。 當(dāng)需要為進(jìn)程分配一個(gè)長(zhǎng)度為n的存儲(chǔ)空間時(shí)，首先計(jì)算一個(gè)i值，使2i1n2i，然后在空閑分區(qū)大小為2i的空閑分區(qū)鏈表中查找。 若找到，即把該空閑分區(qū)分配給進(jìn)程。否則，表明長(zhǎng)度為2i的空閑分區(qū)已經(jīng)耗盡，則在分區(qū)大小為2i1的空閑分區(qū)鏈表中尋找。 若存在2i1的一個(gè)空閑分區(qū)，則把該空閑分區(qū)分為相等的兩個(gè)分區(qū)，這兩個(gè)分區(qū)稱為一對(duì)伙伴，其中的一個(gè)分區(qū)用于分配，而把另一個(gè)加入分區(qū)大

21、小為2i的空閑分區(qū)鏈表中。若大小為2i1的空閑分區(qū)也不存在，則需要查找大小為2i2的空閑分區(qū)，若找到則對(duì)其進(jìn)行兩次分割：第一次，將其分割為大小為2i1的兩個(gè)分區(qū)，一個(gè)用于分配，一個(gè)加入到大小為2i1的空閑分區(qū)鏈表中；第二次，將第一次用于分配的空閑區(qū)分割為2i的兩個(gè)分區(qū)，一個(gè)用于分配，一個(gè)加入到大小為2i的空閑分區(qū)鏈表中。若仍然找不到，則繼續(xù)查找大小為2i3的空閑分區(qū)，以此類推。由此可見，在最壞的情況下，可能需要對(duì)2k的空閑分區(qū)進(jìn)行k次分割才能得到所需分區(qū)。與一次分配可能要進(jìn)行多次分割一樣，一次回收也可能要進(jìn)行多次合并，如回收大小為2i的空閑分區(qū)時(shí)，若事先已存在2i的空閑分區(qū)時(shí)，則應(yīng)將其與伙伴分

22、區(qū)合并為大小為2i1的空閑分區(qū)，若事先已存在2i1的空閑分區(qū)時(shí)，又應(yīng)繼續(xù)與其伙伴分區(qū)合并為大小為2i2的空閑分區(qū)，依此類推。在伙伴系統(tǒng)中，其分配和回收的時(shí)間性能取決于查找空閑分區(qū)的位置和分割、合并空閑分區(qū)所花費(fèi)的時(shí)間。5. 碎片問題經(jīng)過一段時(shí)間的分配回收后，內(nèi)存中存在很多很小的空閑塊。它們每一個(gè)都很小，不足以滿足分配要求；但其總和滿足分配要求。這些空閑塊被稱為碎片造成存儲(chǔ)資源的浪費(fèi)碎片問題的解決緊湊技術(shù)：通過在內(nèi)存移動(dòng)程序，將所有小的空閑區(qū)域合并為大的空閑區(qū)域 （緊縮技術(shù)，緊致技術(shù)，浮動(dòng)技術(shù)，搬家技術(shù)）問題：開銷大；移動(dòng)時(shí)機(jī) 優(yōu)點(diǎn)： 便于動(dòng)態(tài)申請(qǐng)內(nèi)存 便于共享內(nèi)存 便于動(dòng)態(tài)鏈接缺點(diǎn)：碎片問題(

23、外碎片)，內(nèi)存利用率不高，受實(shí)際內(nèi)存容量限制6.分區(qū)式存儲(chǔ)管理的優(yōu)缺點(diǎn) 4.3.3 可重定位分區(qū)分配1. 動(dòng)態(tài)重定位的引入圖 4-3-1 緊湊的示意2. 動(dòng)態(tài)重定位的實(shí)現(xiàn)圖 4-3-2 動(dòng)態(tài)重定位示意圖3. 動(dòng)態(tài)重定位分區(qū)分配算法圖 4-3-3 動(dòng)態(tài)分區(qū)分配算法流程圖 4.可重定位分區(qū)的優(yōu)缺點(diǎn)優(yōu)點(diǎn):解決了可變分區(qū)分配所引入的“外零頭”問題。消除內(nèi)存碎片，提高內(nèi)存利用率。缺點(diǎn):提高硬件成本，緊湊時(shí)花費(fèi)時(shí)間。4.3.7對(duì)換1對(duì)換(Swapping)的引入所謂“對(duì)換”，是指把內(nèi)存中暫時(shí)不能運(yùn)行的進(jìn)程或者暫時(shí)不用的程序和數(shù)據(jù)調(diào)出到外存上，以便騰出足夠的內(nèi)存空間，再把已具備運(yùn)行條件的進(jìn)程或進(jìn)程所需要的程序和數(shù)據(jù)調(diào)入內(nèi)存。