第八章 動態(tài)存儲管理.ppt

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

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

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

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

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

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

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