1、8.1 概述 8.2 可利用空間表及分配辦法 8.3 邊界標(biāo)識法 8.4 伙伴系統(tǒng),第八章 動(dòng)態(tài)存儲管理,動(dòng)態(tài)存儲管理,知識點(diǎn) 概念，動(dòng)態(tài)存儲管理 的基本問題 可利用空間表的結(jié)構(gòu)及三種分配方法 邊界標(biāo)識法的分配和回收算法 伙伴系統(tǒng)的分配和回收算法 重點(diǎn)和難點(diǎn) 伙伴系統(tǒng)的分配和回收 伙伴地址的計(jì)算,8.1 基本概念,動(dòng)態(tài)存儲管理研究的基本問題： 系統(tǒng)如何按用戶的 “請求” 分配內(nèi)存； 當(dāng)用戶使用完畢“釋放”后，系統(tǒng)如何回收內(nèi)存。 “占用塊”：分配給用戶使用的地址連續(xù)的內(nèi)存區(qū)。 “空閑塊”：未曾分配的地址連續(xù)的內(nèi)存區(qū)，也稱“可利用空間塊”,剛“開工”時(shí)，整個(gè)內(nèi)存是一個(gè)“堆”（即一個(gè)空閑塊）；,動(dòng)態(tài)

2、存儲分配過程中的內(nèi)存狀態(tài),a. 系統(tǒng)運(yùn)行初期,b. 系統(tǒng)運(yùn)行若干時(shí)間后,犬牙交錯(cuò)狀,運(yùn)行中如何分配內(nèi)存,又有新的內(nèi)存使用請求，如何分配？ 方法1：繼續(xù)從高地址空閑塊進(jìn)行分配，直至無法分配，再去回收用戶釋放的內(nèi)存，重組內(nèi)存，并分配； 方法2：用戶一旦運(yùn)行結(jié)束，便將其占用的內(nèi)存釋放成空閑塊。有新請求時(shí)從內(nèi)存所有空閑塊中找出合適的一塊分配之； 概念：可利用空間表（目錄表，鏈表）,分配內(nèi)存中使用的可利用空間表,動(dòng)態(tài)存儲管理過程中的內(nèi)存狀態(tài)和可利用空間表,a.內(nèi)存狀態(tài),b. 目錄表,c. 鏈表,每個(gè)空閑塊是鏈表中的一個(gè)結(jié)點(diǎn),8.2 可利用空間表及分配方法,可利用空間表：把可利用空間表看做是一個(gè)“存儲池”

3、，它有以下三種不同的結(jié)構(gòu)形式： 第一種情況是系統(tǒng)運(yùn)行期間所有用戶請求分配的存儲量大小相同 ； 第二種情況是系統(tǒng)運(yùn)行期間用戶請求分配的存儲量有幾種大小的規(guī)格 ； 第三種情況，系統(tǒng)在運(yùn)行期間分配給用戶的內(nèi)存塊大小不固定 。,基本概念,可利用空間表的結(jié)點(diǎn)結(jié)構(gòu)： 結(jié)點(diǎn)大小相同 （實(shí)質(zhì)上是一個(gè)鏈棧） 結(jié)點(diǎn)大小不同，但只有幾種規(guī)格 各種大小的結(jié)點(diǎn)鏈接在一個(gè)鏈表中,此為第三種情況,空閑塊的大小隨意的結(jié)點(diǎn)結(jié)構(gòu),結(jié)點(diǎn)大小不同，但只有幾種（三種）規(guī)格的可利用空間表,結(jié)點(diǎn)結(jié)構(gòu),可利用空間表,空閑塊的分配方式,可利用空間表的分配方式： 最先適配法FF(First Fit) 最佳適配法BF(Best Fit) 最差適配

4、法WF(Worst Fit),可利用空間表的分配方式,分配給用戶的占用塊,首次擬合法,最佳擬合法,最差擬合法,分配高地址，可以避免修改指針,8.3 邊界標(biāo)識法,邊界標(biāo)識法(Boundary Tag Methed)： 系統(tǒng)將所有的空閑塊鏈接在一個(gè)雙重循環(huán)鏈表結(jié)構(gòu)的可利用空間表中，無須從頭到尾掃描鏈表也能確定一個(gè)釋放塊的相鄰塊是否為空閑。 系統(tǒng)在運(yùn)行期間分配給用戶的內(nèi)存塊大小不固定(第三種結(jié)構(gòu)形式) 。 可以用首次擬合或者最佳擬合方法分配。,邊界標(biāo)識法的結(jié)點(diǎn)結(jié)構(gòu),該指針指向本結(jié)點(diǎn)，目的是便于任一結(jié)點(diǎn)都可以作為第一個(gè)結(jié)點(diǎn),邊界標(biāo)識法的特點(diǎn),結(jié)點(diǎn)中的頭部和底部的標(biāo)識使得便于在回收時(shí)判別相鄰的物理位置上

5、的塊是否是空閑塊，便于空閑塊的合并。,邊界標(biāo)識法,邊界標(biāo)識法的分配算法,1. 設(shè)空閑塊的容量為m，用戶申請的大小為n,若m-n=e（常量）,則將m整塊分配給用戶。反之分配給用戶大小為 n 的內(nèi)存； 2. 每次分配后，鏈表指針pav后移，指向剛分配結(jié)點(diǎn)的后繼結(jié)點(diǎn)。,避免容量小的空閑塊結(jié)點(diǎn)密集的集中在頭指針pav所指結(jié)點(diǎn)的附近，便于查詢較大的空閑塊,假設(shè)采用FF法分配,為了減少內(nèi)存碎片,0,0,某邊界標(biāo)識法系統(tǒng)的可利用空間表,a. 初始狀態(tài),b. 運(yùn)行若干時(shí)間后,c. 進(jìn)行再分配后,邊界標(biāo)識法的回收算法,若用戶釋放占用塊，則系統(tǒng)回收，并盡可能和比鄰的空閑塊結(jié)合成大的空閑塊。 1. 空閑塊和左鄰空閑

6、塊合并； 2. 空閑塊和右鄰空閑塊合并； 3. 空閑塊和左、右鄰空閑塊合并；,邊界標(biāo)識法的優(yōu)缺點(diǎn),優(yōu)點(diǎn)： 由于有標(biāo)識，無需查詢整個(gè)可利用空間表，便于空閑塊的合并； 插入釋放的空閑塊時(shí)也無需查找鏈表； 回收空閑塊的時(shí)間是常量，與表的大小無關(guān)； 缺點(diǎn)： 增加了結(jié)點(diǎn)底部的存儲量；,8.4 伙伴系統(tǒng),伙伴系統(tǒng)(Buddy System)：在用戶提出空間申請時(shí)，分配一塊大小合適的內(nèi)存塊給用戶；當(dāng)用戶釋放占用塊時(shí)，操作系統(tǒng)回收被釋放的空閑塊； 無論是占用塊還是空閑塊，分配的大小均為2的k次冪（k為某個(gè)正整數(shù)）； 如果用戶申請n個(gè)字的內(nèi)存時(shí)，分配的占用塊大小為,伙伴系統(tǒng)中的可利用空間表的結(jié)構(gòu),a. 空閑塊的

7、結(jié)點(diǎn)結(jié)構(gòu),b. 表的初始狀態(tài),c. 分配前的表,d. 分配后的表,伙伴系統(tǒng)的分配算法,若2k-1n=2k-1,且第k+1個(gè)子表不空，則刪除此鏈表中第一個(gè)結(jié)點(diǎn)，分配給用戶。 若2k-2n=2k-1-1,由于大小為2k-1的子表為空，則需要從結(jié)點(diǎn)大小為2k的子表中取出一塊，將一半分給用戶，另一半插到大小為2k-1的子表中。,伙伴系統(tǒng)的分配,伙伴系統(tǒng)的回收算法,回收時(shí)僅為“伙伴”的兩個(gè)空閑塊才被歸并； 伙伴：如一個(gè)大塊分裂成的兩個(gè)小塊互為伙伴,伙伴系統(tǒng)的回收算法,起始地址為p大小為2k的內(nèi)存塊，其伙伴塊的起始地址： 例：空閑區(qū)的大小為210=1024,地址從0到1023。 如果一個(gè)塊的大小為28,起始地址為512，則它的伙伴塊的起始地址為768。 如果大小為27，起始地址為384，則伙伴塊的起始地址為256。,練習(xí)題,下圖所示的伙伴系統(tǒng)中，回收兩塊首地址分別為768及128，大小為27的存儲塊，請畫出回收后該伙伴系統(tǒng)的狀態(tài)圖。,伙伴系統(tǒng)的回收算法,因?yàn)?68 % 27+1=0，所以768和768+27=896互為伙伴, 伙伴合并后,首址為768,塊大小為28。因?yàn)?68 % 28+1=28,所以,所以首址768大小為28的塊和首址512大小為2