第八章动态存储管理
一.选择题 1C
二.判断题 1.错误 2.正确
三.填空题
1.(1)480+8=488(480 %2
3+1
=0) (2)480-32=448
2.(1)011011110100 (2)011011100000
3.用户不再使用而系统没有回收的结构和变量。例如,p=malloc(size);…,
p=null;
四.应用题
1. 在伙伴系统中,无论占用块或空闲块,其大小均为 2 的 k(k 为≥0 的正整数)次幂。若内
存容量为 2
m
,则空闲块大小只能是 2
0
,2
1
,2
2
,…,2
m
。由同一大块分裂而得的两个小
块互称“伙伴空间”,如内存大小为 2
10
的块分裂成两个大小为 2
9
的块。只有两个“伙伴
空间”才能合并成一个大空间。
起始地址为 p,大小为 2
k
的内存块,其伙伴的起始地址为:
buddy(p,k)=p+2
k
(若 p % 2
k+1
=0),或 buddy(p,k)=p-2
k
(若 p % 2
k+1
=2
k
)
2.首次拟合法;从链表头指针开始查找,找到第一个≥所需空间的结点即分配。
最佳拟合法:链表结点大小增序排列,找到第一个≥所需空间的结点即分配。
最差拟合法:链表结点大小逆序排列,总从第一个结点开始分配,将分配后结点所剩空
间插入到链表适当位置。
首次拟合法适合事先不知道请求分配和释放信息的情况,分配时需查询,释放时插在表
头。 最佳拟合法适用于请求分配内存大小范围较宽的系统,释放时容易产生存储量很小难以
利用的内存碎片,同时保留那些很大的内存块以备将来可能发生的大内存量的需求,分配与
回收均需查询。 最差拟合法适合请求分配内存大小范围较窄的系统,分配时不查询,回收时
查询,以便插入适当位置。
3. 011011110100 4.011011100000
5.(1)buddy(1664,7)=1664-128=1536 (2)buddy(2816,6)=2816+64=2880
6.动态存储分配伙伴系统的基本思想请参见上面题 1。边界标识法在每块的首尾均有“占
用”/“空闲”标志,空闲块合并方便。伙伴系统算法简单,速度快,但只有互为伙伴的两
个空闲块才可合并,因而易产生虽空闲但不能归并的碎片。
7.组织成循环链表的可利用空间表的结点大小按递增序排列时, 首次适配策略就转变为最
佳适配策略。
8.因为 512=2
9
,可利用空间表的初始状态图如 8-1 所示。
当用户申请大小为 23 的内存块时,因 2
4
<23<=2
5
,但没有大小为 2
5
的块,只有大小为 2
9
的
块,故将 2
9
的块分裂成两个大小为 2
8
的块,其中大小为 2
8
的一块挂到可利用空间表上,另一
块再分裂成两个大小为 2
7
的块。又将其中大小为 2
7
的一块挂到可利用空间表上,另一块再分
裂成两个大小为 2
6
的块,一块 2
6
的块挂到可利用空间表上,另一块分裂成两个大小为 2
5
的块,
其中一块挂到可利用空间表上,另一块分给用户(地址 0—31)。如此下去,最后每个用户得到
的存储空间的起始地址如图 8-2, 6 个用户分配所需要的存储空间后可利用空间表的状态如
图 8-3。
在回收时,因为给申请 45 的用户分配了 2
6
,其伙伴地址是 0,在占用中,不能合并,只能挂
到可利用空间表上。在回收大小为 52 的占用块时,其伙伴地址是 192,也在占用。回收大小
为 11 的占用块时,其伙伴地址是 48,可以合并为大小 2
5
的块, 挂到可利用空间表上。回收 3
个占用块之后可利用空间表的状态如图 8-4。
评论0