嚴(yán)蔚敏教材講義動(dòng)態(tài)存儲(chǔ)管理PPT課件

1、 對(duì)操作系統(tǒng)和編譯程序來(lái)說(shuō)，存儲(chǔ)管理都是一個(gè)復(fù)雜而又重要的問(wèn)題。不同語(yǔ)言的編譯程序和不同的操作系統(tǒng)可以采用不同的存儲(chǔ)管理方法。它們采用的具體做法，將在后續(xù)課程編譯原理和操作系統(tǒng)中學(xué)習(xí)。 動(dòng)態(tài)存儲(chǔ)管理的基本問(wèn)題是系統(tǒng)如何應(yīng)用戶提出的“請(qǐng)求”分配內(nèi)存?又如何回收那些用戶不再使用而“釋放”的內(nèi)存，以備新的“請(qǐng)求”產(chǎn)生時(shí)重新進(jìn)行分配? 下面將簡(jiǎn)單討論利用不同策略進(jìn)行動(dòng)態(tài)存儲(chǔ)管理的方法。 第1頁(yè)/共18頁(yè)8.2 可利用空間表及分配方法 利用可利用空間表進(jìn)行動(dòng)態(tài)存儲(chǔ)分配的方法一般會(huì)利用目錄表或鏈表記錄所有空閑塊。目錄表的情況比較簡(jiǎn)單，這類(lèi)系統(tǒng)將在操作系統(tǒng)課程中作詳細(xì)介紹，在此僅就鏈表的情況進(jìn)行討論。 可利

2、用空間表中包含所有可分配的空閑塊，每一塊是鏈表中的一個(gè)結(jié)點(diǎn)。當(dāng)用戶請(qǐng)求分配時(shí)，系統(tǒng)從可利用空間表中刪除一個(gè)結(jié)點(diǎn)分配之；當(dāng)用戶釋放其所占內(nèi)存時(shí)，系統(tǒng)即回收并將它插入到可利用空間表中。因此，可利用空間表亦稱作“存儲(chǔ)池”。根據(jù)系統(tǒng)運(yùn)行的不同情況，可利用空間表可以有下列三種不同的結(jié)構(gòu)形式：第2頁(yè)/共18頁(yè) 第一種情況，系統(tǒng)運(yùn)行期間所有用戶請(qǐng)求分配的存儲(chǔ)量大小相同。對(duì)此類(lèi)系統(tǒng)，通常的做法是，在系統(tǒng)開(kāi)始運(yùn)行時(shí)將歸它使用的內(nèi)存區(qū)按所需大小分割成若干大小相同的塊，然后用指針鏈接成一個(gè)可利用空間表。 第二種情況，系統(tǒng)運(yùn)行期間用戶請(qǐng)求分配的存儲(chǔ)量有若干種大小的規(guī)格。對(duì)此類(lèi)系統(tǒng)，一般情況下是建立若干個(gè)可利用空間表，

3、同一鏈表中的結(jié)點(diǎn)大小相同。 第三種情況，系統(tǒng)在運(yùn)行期間分配給用戶的內(nèi)存塊的大小不固定，可以隨請(qǐng)求而變。因此，可利用空間表中的結(jié)點(diǎn)即空閑塊的大小也是隨意的。通常，操作系統(tǒng)中的可利用空間表屬這種類(lèi)型。第3頁(yè)/共18頁(yè) 可利用空間表的第三種結(jié)構(gòu)中的結(jié)點(diǎn)大小不同，則在分配時(shí)就有一個(gè)如何分配的問(wèn)題。假設(shè)某用戶需大小為n的內(nèi)存，而可利用空間表中僅有一塊大小為mn的空閑塊，則只需將其中大小為n的一部分分配給申請(qǐng)分配的用戶，同時(shí)將剩余大小為m-n的部分作為一個(gè)結(jié)點(diǎn)留在鏈表中即可。然而，若可利用空間表中有若干個(gè)不小于n的空閑塊時(shí)，該分配哪一塊呢?通常，可有三種不同的分配策略： (1)首次擬合法。從表頭指針開(kāi)始查

4、找可利用空間表，將找到的第一個(gè)大小不小于 n的空閑塊的一部分分配給用戶。 (2)最佳擬合法。將可利用空間表中一個(gè)不小于”且最接近n的空閑塊的一部分分配給用戶。 (3)最差擬合法。將可利用空間表中不小于”且是鏈表中最大的空閑塊的一部分分配給用戶。 第4頁(yè)/共18頁(yè) 因此，不同的情景需采用不同的方法，通常在選擇時(shí)需考慮下列因素：用戶的邏輯要求；請(qǐng)求分配量的大小分布；分配和釋放的頻率以及效率對(duì)系統(tǒng)的重要性等等。 在實(shí)際使用的系統(tǒng)中回收空閑塊時(shí)還需考慮一個(gè)“結(jié)點(diǎn)合并”的問(wèn)題。這是因?yàn)橄到y(tǒng)在不斷進(jìn)行分配和回收的過(guò)程中，大的空閑塊逐漸被分割成小的占用塊，在它們重又成為空閑塊回收之后，即使是地址相鄰的兩個(gè)空

5、閑塊也只是作為兩個(gè)結(jié)點(diǎn)插入到可利用空間表中，以致使得后來(lái)出現(xiàn)的大容量的請(qǐng)求分配無(wú)法進(jìn)行，為了更有效地利用內(nèi)存，就要求系統(tǒng)在回收時(shí)應(yīng)考慮將地址相鄰的空閑塊合并成盡可能大的結(jié)點(diǎn)。換句話說(shuō)，在回收空閑塊時(shí)，首先應(yīng)檢查地址與它相鄰的內(nèi)存是否是空閑塊。第5頁(yè)/共18頁(yè)8.3 邊界標(biāo)識(shí)法 邊界標(biāo)識(shí)法(boundary tag method)是操作系統(tǒng)中用以進(jìn)行動(dòng)態(tài)分區(qū)分配的一種存儲(chǔ)管理方法，它屬于上一節(jié)討論中的第三種情況。系統(tǒng)將所有的空閑塊鏈接在一個(gè)雙重循環(huán)鏈表結(jié)構(gòu)的可利用空間表中；分配可按首次擬合進(jìn)行，也可按最佳擬合進(jìn)行。系統(tǒng)的特點(diǎn)在于：在每個(gè)內(nèi)存區(qū)的頭部和底部?jī)蓚€(gè)邊界上分別設(shè)有標(biāo)識(shí)，以標(biāo)識(shí)該區(qū)域?yàn)檎加?/p>

6、塊或空閑塊，使得在回收用戶釋放的空閑塊時(shí)易于判別在物理位置上與其相鄰的內(nèi)存區(qū)域是否為空閑塊，以便將所有地址連續(xù)的空閑存儲(chǔ)區(qū)組合成一個(gè)盡可能大的空閑塊。下面分別就系統(tǒng)的可利用空間表的結(jié)構(gòu)及其分配和回收的算法進(jìn)行簡(jiǎn)單討論。第6頁(yè)/共18頁(yè) 8.3.1 可利用空間表的結(jié)構(gòu) 可利用空間表中的結(jié)點(diǎn)結(jié)構(gòu)如下所示： head foot 它表示一個(gè)空閑塊。整個(gè)結(jié)點(diǎn)由三部分組成。其中space為一組地址連續(xù)的存儲(chǔ)單元，是可以分配給用戶使用的內(nèi)存區(qū)域，它的大小由head中的size域指示，并以頭部head和底部foot作為它的兩個(gè)邊界；在head和foot中分別設(shè)有標(biāo)志域tag，且設(shè)定空閑塊中tag的值為“0”，

7、占用塊中tag的值為“1”；foot位于結(jié)點(diǎn)底部，因此它的地址是隨結(jié)點(diǎn)中space空間的大小而變的。 llinktagsizerlink space uplinktag第7頁(yè)/共18頁(yè) 8.3.2 分配算法 分配的算法比較簡(jiǎn)單，假設(shè)我們采用首次擬合法進(jìn)行分配，則只要從表頭指針pav所指結(jié)點(diǎn)起，在可利用空間表中進(jìn)行查找，找到第一個(gè)容量不小于請(qǐng)求分配的存儲(chǔ)量(n)的空閑塊時(shí)，即可進(jìn)行分配。為了使整個(gè)系統(tǒng)更有效地運(yùn)行，在邊界標(biāo)識(shí)法中還作了如下兩條約定： (1)假設(shè)找到的此塊待分配的空閑塊的容量為m個(gè)字(包括頭部和底部)，若每次分配只是從中分配n個(gè)字給用戶，剩余mn個(gè)字大小的結(jié)點(diǎn)仍留在鏈表中，則在若干

8、次分配之后，鏈表中會(huì)出現(xiàn)一些容量極小總也分配不出去的空閑塊，這就大大減慢了分配 (查找)的速度。彌補(bǔ)的辦法是：選定一個(gè)適當(dāng)?shù)某Ａ縠，當(dāng)m-ne時(shí)，就將容量為m的空閑塊整塊分配給用戶；反之，只分配其中n個(gè)字的內(nèi)存塊。同時(shí)，為了避免修改指針，約定將該結(jié)點(diǎn)中的高地址部分分配給用戶。第8頁(yè)/共18頁(yè) (2)如果每次分配都從同一個(gè)結(jié)點(diǎn)開(kāi)始查找的話，勢(shì)必造成存儲(chǔ)量小的結(jié)點(diǎn)密集在頭指針pay所指結(jié)點(diǎn)附近，這同樣會(huì)增加查詢較大空閑塊的時(shí)間。反之，如果每次分配從不同的結(jié)點(diǎn)開(kāi)始進(jìn)行查找，使分配后剩余的小塊均勻地分布在鏈表中，則可避免上述弊病。 8.3.3 回收算法 一旦用戶釋放占用塊，系統(tǒng)需立即回收以備新的請(qǐng)求產(chǎn)

9、生時(shí)進(jìn)行再分配。為了使物理地址毗鄰的空閑塊結(jié)合成一個(gè)盡可能大的結(jié)點(diǎn)，則首先需要檢查剛釋放的占用塊的左、右緊鄰是否為空閑塊。由于本系統(tǒng)在每個(gè)內(nèi)存區(qū)(無(wú)論是占用塊或空閑塊)的邊界上都設(shè)有標(biāo)志值，則很容易辨明這一點(diǎn)。第9頁(yè)/共18頁(yè) 假設(shè)用戶釋放的內(nèi)存區(qū)的頭部地址為p，則與其低地址緊鄰的內(nèi)存區(qū)的底部地址為 p-l；與其高地址緊鄰的內(nèi)存區(qū)的頭部地址為p+p-size，它們中的標(biāo)志域就表明了這兩個(gè)鄰區(qū)的使用狀況： 若(p-1)-tag=0；則表明其左鄰為空閑塊， 若(p+p-size)- tag=0；則表明其右鄰為空閑塊。 若釋放塊的左、右鄰區(qū)均為占用塊，則處理最為簡(jiǎn)單，只要將此新的空閑塊作為一個(gè)結(jié)點(diǎn)插

10、入到可利用空閑表中即可；若只有左鄰區(qū)是空閑塊，則應(yīng)與左鄰區(qū)合并成一個(gè)結(jié)點(diǎn)；若只有右鄰區(qū)是空閑塊，則應(yīng)與右鄰區(qū)合并成一個(gè)結(jié)點(diǎn)；若左、右鄰區(qū)都是空閑塊，則應(yīng)將三塊合起來(lái)成為一個(gè)結(jié)點(diǎn)留在可利用空間表中。第10頁(yè)/共18頁(yè) 84 伙伴系統(tǒng) 伙伴系統(tǒng)(buddy system)是操作系統(tǒng)中用到的另一種動(dòng)態(tài)存儲(chǔ)管理方法。它和邊界標(biāo)識(shí)法類(lèi)似，在用戶提出申請(qǐng)時(shí)，分配一塊大小“恰當(dāng)”的內(nèi)存區(qū)給用戶；反之，在用戶釋放內(nèi)存區(qū)時(shí)即回收。所不同的是：在伙伴系統(tǒng)中，無(wú)論是占用塊或空閑塊，其大小均為2的是次冪(是為某個(gè)正整數(shù))。例如；當(dāng)用戶申請(qǐng)n個(gè)字的內(nèi)存區(qū)時(shí)，分配的占用塊大小為 2k個(gè)字(2k-1n 2k)。由此，在可利

11、用空間表中的空閑塊大小也只能是2的是次冪。 第11頁(yè)/共18頁(yè) 8.4.1 可利用空間表的結(jié)構(gòu) 假設(shè)系統(tǒng)的可利用內(nèi)存空間容量為2m個(gè)字(地址從0到2m-1)，則在開(kāi)始運(yùn)行時(shí)，整個(gè)內(nèi)存區(qū)是一個(gè)大小為2m的空閑塊，在運(yùn)行了一段時(shí)間之后，被分隔成若干占用塊和空閑塊。為了再分配時(shí)查找方便起見(jiàn)，我們將所有大小相同的空閑塊建于一張子表中。每個(gè)子表是一個(gè)雙重鏈表，這樣的鏈表可能有m+1個(gè)，將這m+1個(gè)表頭指針用向量結(jié)構(gòu)組織成一個(gè)表，這就是伙伴系統(tǒng)中的可利用空間表。header linktag=0kvalrlink space202k2m0 k第12頁(yè)/共18頁(yè) 8.4.2 分配算法 當(dāng)用戶提出大小為n的內(nèi)存

12、請(qǐng)求時(shí)，首先在可利用表上尋找結(jié)點(diǎn)大小與n相匹配的子表，若此子表非空，則將子表中任意一個(gè)結(jié)點(diǎn)分配之即可；若此子表為空，則需從結(jié)點(diǎn)更大的非空子表中去查找，直至找到一個(gè)空閑塊，則將其中一部分分配給用戶，而將剩余部分插入相應(yīng)的子表中。 第13頁(yè)/共18頁(yè) 若2k-1n 2k-1，又第k+1個(gè)子表不空，則只要?jiǎng)h除此鏈表中第一個(gè)結(jié)點(diǎn)并分配給用戶即可；若 2k-2n 2k-1-1，此時(shí)由于結(jié)點(diǎn)大小為2k-1的子表為空，則需從結(jié)點(diǎn)大小為2k的子表中取出一塊，將其中一半分配給用戶，剩余的一半作為一個(gè)新結(jié)點(diǎn)插入在結(jié)點(diǎn)大小為2k-1的子表中，若2k-i-1n 2k-i-1(i為小于是的整數(shù))，并且所有結(jié)點(diǎn)小于2k的

13、子表均為空，則同樣需從結(jié)點(diǎn)大小為2k的子表中取出一塊，將其中2k-i的一小部分分配給用戶，剩余部分分割成若干個(gè)結(jié)點(diǎn)分別插入在結(jié)點(diǎn)大小為2k-1 、 2k-2 、 2k-i的子表中。 第14頁(yè)/共18頁(yè) 8.4.3 回收算法算法 在用戶釋放不再使用的占用塊時(shí)，系統(tǒng)需將這新的空閑塊插入到可利用空間表中去。這里，同樣有一個(gè)地址相鄰的空閑塊歸并成大塊的問(wèn)題。但是在伙伴系統(tǒng)中僅考慮互為“伙伴”的兩個(gè)空閑塊的歸并。 何謂“伙伴”?如前所述，在分配時(shí)經(jīng)常需要將一個(gè)大的空閑塊分裂成兩個(gè)大小相等的存儲(chǔ)區(qū)，這兩個(gè)由同一大塊分裂出來(lái)的小塊就稱之“互為伙伴”。例如：假設(shè)p為大小為2k的空閑塊的初始地址，且p MOD 2k+1=0，則初始地址為p和p+2k的兩個(gè)空閑塊互為伙伴。在伙伴系統(tǒng)中回收空閑塊時(shí)，只當(dāng)其伙伴為空閑塊時(shí)才歸并成大塊。也就是說(shuō)，若有兩個(gè)空閑塊，即使大小相同且地址相鄰，但不是由同一大塊分裂