北郵計算機科學(xué)與技術(shù)專業(yè)課設(shè)要求大二數(shù)據(jù)結(jié)構(gòu)作業(yè)dsc8

§8.1存儲管理概述第八章.動態(tài)存儲管理（Chapter8.DynamicStorageManagement)

前面幾章我們介紹了數(shù)據(jù)的幾種邏輯結(jié)構(gòu)及其相應(yīng)的物理結(jié)構(gòu)（在內(nèi)存中的映像），本章則簡單介紹了在單一連續(xù)區(qū)方式下計算機內(nèi)存儲器的動態(tài)管理。

內(nèi)存的初始狀態(tài)U1U2U3U4

系統(tǒng)運行初期U2U4

系統(tǒng)運行若干時后

計算機內(nèi)存在剛開始工作時，空閑部分是一個整塊的連續(xù)區(qū)域；隨著用戶進(jìn)入系統(tǒng)，多次申請和釋放內(nèi)存以后，空閑部分不再是連續(xù)的了，而成了多個空閑區(qū)，通常用鏈表的形式管理起來，即可利用空間表。右圖即為內(nèi)存在不同時間下的示意圖：§8.2可利用空間表和分配回收方法

可利用空間表是將所有內(nèi)存空閑塊用鏈表連接而成?？臻e塊的大小可以是全相同的，也可以是分成若干固定大小的，還可以是隨機大小的。如下面所示即是隨機大小的：tagsizelinkspacetag=0：空閑tag=1：使用av

020003000150...對于隨機大小的可利用空間塊，在分配時可以采用三種分配策略，它們各有利弊：1、首次適應(yīng)法：操作方便，查找快捷；2、最佳適應(yīng)法：盡可能將大的空閑塊留給大程序使用；3、最壞適應(yīng)法：盡可能減少分配后無用碎片；分配和回收：1、分配時根據(jù)用戶申請內(nèi)存大小利用相應(yīng)的分配策略分配給用戶所需的空間，若分配塊大小與申請大小差不多，則將此塊全部分給用戶；否則，就需將分配塊分為兩塊，一部分給用戶使用，另一部分繼續(xù)留在可利用空間表中。2、回收時需測試回收塊前后相鄰內(nèi)存塊是否空閑，若是則需將回收塊與相鄰空閑塊合并成較大的空閑塊，再鏈入可利用空間表中。§8.3邊界標(biāo)識法

邊界標(biāo)識法（boundarytagmethod）的數(shù)據(jù)結(jié)構(gòu)示意如右：spacetagsizerlinkllinktaguplinkheaderfooter

llink和rlink構(gòu)成雙向循環(huán)鏈表，uplink則指向塊頭，tag表示是否空閑。typedefstructblk{struct{blk*llink,*rlink;inttagintsize}header;datatypespace[0..size-3];struct{blk*uplink;inttag;}footer;}blk,*blkptr;邊界標(biāo)識法的數(shù)據(jù)結(jié)構(gòu)定義如下：§8.4伙伴系統(tǒng)

伙伴系統(tǒng)（buddysystem）采用的是一系列固定大?。?k）的空閑塊。系統(tǒng)開始時只有一個空閑塊，大小為2m

，其后隨著用戶的內(nèi)存申請，就將剛好滿足用戶需求的2k大小的空閑塊分配給用戶，若不存在2k這么大的空閑塊，就找大小為2k+1的空閑塊，將其分為兩半（互稱伙伴），一半給用戶，另一半加入大小為2k的循環(huán)鏈表中?；厥諘r，只有伙伴才合并，并將合并后的新空閑塊加入上一級大小的空閑塊鏈表中。B1B2B3B4注意：并非大小相同的相鄰塊都是伙伴，找伙伴時單方向的！如左圖中的B1和B2、B3和B4是伙伴，它們的大小都相同，但B2和B3則不是伙伴，它們再回收時時不能夠合并的。

首地址為Z，大小為2k的內(nèi)存塊，其伙伴為：(a)初始狀態(tài)(b)若干時間后20212k2m∧∧∧

0m

202k-12k2m∧∧k-1

0k

0k

0Buddy(k,Z)=Z+2k

當(dāng)Zmod2k+1=0Z-2k

當(dāng)Zmod2k+1=2k{typedefstructfreenode{struct{freenode*llink,*rlink;inttag;intkval;}header;datatypespace[0..Size-2];}freenode,*freeptr;伙伴系統(tǒng)的數(shù)據(jù)結(jié)構(gòu)定義如下：typedefstruct{intnodesize;freeptrfirst;}headnode;typedefheadnodefreelist[0..m];

其實，在內(nèi)存管理方面還有很多技術(shù)，如無用單元的回收、交換技術(shù)、覆蓋技術(shù)，在方法上還有頁式、段式、段頁式以及虛擬內(nèi)存等等技術(shù)，將來再操作系統(tǒng)課程中會詳細(xì)講解。作業(yè)24.

假設(shè)利用邊界標(biāo)識法首次匹配策略分配，已知在某個時刻的可利用空間表如下：（1）、請畫出當(dāng)系統(tǒng)回收一個起始地址為559、大小為45的空閑塊之后的鏈表狀態(tài)；（2）、請畫出系統(tǒng)在之后接受大小為100的請求后又回收