数据结构(C语言版)第8章 动态存储管理

第八章 动态存储管理

一、选择题

1. 动态存储管理系统中，通常可有（ ）种不同的分配策略。【长沙铁道学院 1998 三、3 (2分)】

A． 1 B. 2 C. 3 D. 4 E. 5

二、判断题

1． 在伙伴系统中的伙伴是指任意两块大小相同、位置相邻的内存块。（ ）

【北京邮电大学 2000 一、8(1分)】

2． 在动态存储管理系统中做空间分配时，最佳适配法与最先适配法相比，前者容易增加闲

置空间的碎片。（ ）【东南大学 2001 一、1-1 （1分）】【中山大学 1994 一、1（2分）】

三、填空题 1．起始地址为480,大小为8的块,其伙伴块的起始地址是_______;若块大小为32,则其伙伴块的起始地址为_______。【北方交通大学 1999 二、1（4分）】

2．二进制地址为011011110000，大小为（4）10和（16）10块的伙伴地址分别为：________、_________。

【上海大学 2002 二、2（2分）】

3． 无用单元是指________,例________【北方交通大学 1999 二、6（4分）】

四、应用题

1．伙伴空间（名词解释）【西北工业大学 1999 一、4（3分）】

2．设内存中可利用空间已连成一个单链表，对用户的存储空间需求，一般有哪三种分配策略？

【北京科技大学 1999 一、6（2分）】

3．计算起始二进制地址为011011110000，长度为4（十进制）的块的伙伴地址是多少？

【中山大学1999一、2(3分)】

4

4．在一个伙伴系统中，已知某存储块的始址Ｘ＝（011011110000）2，大小为２，则它的伙伴块的始址是多少？【北方交通大学 1996 一、1（5分）】

5．地址为（1664）10大小为（128）10的存储块的伙伴地址是什么？

地址为（2816）10大小为（64）10的存储块的伙伴地址是什么？【清华大学 1996 四、】 6． 试叙述动态存储分配伙伴系统的基本思想，它和边界标识法不同点是什么？

【青岛大学 2000 十、（10分）】【中国人民大学 2000 一、1（4分）】 7．组织成循环链表的可利用空间表附加什么条件时，首次适配策略就转变为最佳适配策略？

【北方交通大学 1998 四、（8分）】

8．已知一个大小为512个字长的存储，假设先后有6个用户申请大小分别为23，45，52，100，11和19的存储空间，然后再顺序释放大小为45，52，11的占用块。假设以伙伴系统实现动态存储管理。

（1） 画出可利用空间表的初始状态。 （2） 画出为6个用户分配所需要的存储空间后可利用空间表的状态以及每个用户所得到的存储块的起始地址。

（3） 画出在回收3个占用块之后可利用空间表的状态。【清华大学1998三(15分)】【同济

大学 1999】

7

9．下图所示的伙伴系统中，回收两块首地址分别为768及128，大小为2的存储块，请画出回收后该伙伴系统的状态图。【北京邮电大学 1996 二、（10分）】 896256...

26?

27

51228

9?2

10．假设利用边界标识法，并以首次拟合策略分配，已知在某个时刻可利用空间表的状态如下图所示：

（注：存储块头部size域的值和申请分配的存储量均包括头部和尾部的存储空间。） 请画出：

（1）当系统回收一个起始地址为559，大小为45的空闲块之后的链表状态；

（2）系统继而在接受存储块大小为100的请求后，又回收一个起始地址为515，大小为44的空闲块之后的链表状态。【上海大学 2002 二、3（8分）】

pav

80221346260405601170530122

0000

第10题图：可利用空间表的状态图

第八章 动态存储管理

一．选择题 1C

二．判断题 1．错误 2．正确 三．填空题

3+1

1．（1）480+8=488（480 %2=0） （2）480-32=448 2．（1）011011110100 （2）011011100000

3．用户不再使用而系统没有回收的结构和变量。例如，p=malloc(size)；?，p=null； 四．应用题

1． 在伙伴系统中，无论占用块或空闲块，其大小均为2的k(k为≥0的正整数)次幂。若内

m012m

存容量为2，则空闲块大小只能是2，2，2，?，2。由同一大块分裂而得的两个小块

109

互称“伙伴空间”，如内存大小为2的块分裂成两个大小为2的块。只有两个“伙伴空间”才能合并成一个大空间。

k

起始地址为p，大小为2的内存块，其伙伴的起始地址为：

k k+1k k+1k

buddy(p,k)=p+2 (若p % 2=0),或buddy(p,k)=p-2 (若p % 2=2) 2．首次拟合法；从链表头指针开始查找，找到第一个≥所需空间的结点即分配。

最佳拟合法：链表结点大小增序排列，找到第一个≥所需空间的结点即分配。

最差拟合法：链表结点大小逆序排列，总从第一个结点开始分配，将分配后结点所剩空

间插入到链表适当位置。

首次拟合法适合事先不知道请求分配和释放信息的情况,分配时需查询,释放时插在表头。 最佳拟合法适用于请求分配内存大小范围较宽的系统,释放时容易产生存储量很小难以利用的内存碎片,同时保留那些很大的内存块以备将来可能发生的大内存量的需求，分配与回收均需查询。 最差拟合法适合请求分配内存大小范围较窄的系统,分配时不查询,回收时查询,以便插入适当位置。

3． 011011110100 4．011011100000 5．（1）buddy(1664,7)=1664-128=1536 （2）buddy(2816,6)=2816+64=2880

6．动态存储分配伙伴系统的基本思想请参见上面题1。边界标识法在每块的首尾均有“占用”/“空闲”标志，空闲块合并方便。伙伴系统算法简单，速度快，但只有互为伙伴的两个空闲块才可合并，因而易产生虽空闲但不能归并的碎片。

7．组织成循环链表的可利用空间表的结点大小按递增序排列时, 首次适配策略就转变为最佳适配策略。

9

8．因为512=2,可利用空间表的初始状态图如8-1所示。

4559

当用户申请大小为23的内存块时,因2<23<=2,但没有大小为2的块,只有大小为2的

988

块,故将2的块分裂成两个大小为2的块,其中大小为2的一块挂到可利用空间表上,另一块

77

再分裂成两个大小为2的块。又将其中大小为2的一块挂到可利用空间表上,另一块再分裂

665

成两个大小为2的块,一块2的块挂到可利用空间表上,另一块分裂成两个大小为2的块,其中一块挂到可利用空间表上,另一块分给用户(地址0—31)。如此下去,最后每个用户得到的存储空间的起始地址如图8-2, 6个用户分配所需要的存储空间后可利用空间表的状态如图8-3。

6

在回收时,因为给申请45的用户分配了2,其伙伴地址是0,在占用中,不能合并,只能挂到可利用空间表上。在回收大小为52的占用块时,其伙伴地址是192,也在占用。回收大小

5

为11的占用块时,其伙伴地址是48,可以合并为大小2的块, 挂到可利用空间表上。回收3个占用块之后可利用空间表的状态如图8-4。

20?

21?存储大小 起始地址

22? 23 0 23? 45 64 24?

25? 52 128

26? 100 256 27? 11 32 28? 0929 19 192

图8-2 图8-1

（注：在图8.3和8.4画上了占用块，从原理上，只有空闲块才出现在“可利用空间表”中。）

20?

21?20?

22?21?

23?22?1404

23?24 24?251515052526271515050526161606170607

图8-3 图8-4

7+17

9． 因为768 % 2=0，所以768和768+2=896互为伙伴, 伙伴合并后,首址为768,块大小

88+1888

为2。因为768 % 2=2,所以,所以首址768大小为2的块和首址512大小为2的块合并,

97+177

成为首址512大小为2的空闲块。因为128 % 2=2，其伙伴地址为128-2=0, 将其插入可利用空间表中。回收后该伙伴系统的状态图如下。

128256 ...

26?

27 51228

29? 10．（1）系统回收一个起始地址为559，大小为45的空闲块后，因右侧起始地址604为空闲块，应与之合并。合并后，起始地址为559，大小为167的空闲块。链表状态如图10．（1）所示。

10．（1）

pav802056021301170462053055901670

（2）系统在接受存储块大小为100的请求后，将大小为117的空闲块分出100给予用户。在回收一个起始地址为515，大小为44的空闲块之后，因左侧起始地址462大小53和右侧起始地址559大小167均为空闲块，应与之合并。合并后，起始地址为462，大小为264的空闲块。链表状态如图10．（2）所示。

10．（2）

pav8020560213017046202640