第八章动态存储管理 选择题1C 判断题1.错误2.正确 填空题 1.(1)480+8=488(480%23=0 (2)480-32=448 2.(1)011011110100 (2)011011100000 3.用户不再使用而系统没有回收的结构和变量。例如,p= malloc(size);…,p=null 四.应用题 1.在伙伴系统中,无论占用块或空闲块,其大小均为2的k(k为≥0的正整数)次幂。若内 存容量为2,则空闲块大小只能是2,2,2,…,2。由同一大块分裂而得的两个小块 互称“伙伴空间”,如内存大小为20的块分裂成两个大小为2的块。只有两个“伙伴空 间”才能合并成一个大空间 起始地址为p,大小为2的内存块,其伙伴的起始地址为: buddy(p,k)=p+2(若p%2=0),或budy(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.组织成循环链表的可利用空间表的结点大小按递增序排列时,首次适配策略就转变为最 佳适配策略 8.因为512=2,可利用空间表的初始状态图如8-1所示 当用户申请大小为23的内存块时,因2<23<=2,但没有大小为25的块,只有大小为2的 块,故将2的块分裂成两个大小为2的块,其中大小为2的一块挂到可利用空间表上,另一块 再分裂成两个大小为2的块。又将其中大小为2的一块挂到可利用空间表上,另一块再分裂 成两个大小为26的块,一块2的块挂到可利用空间表上,另一块分裂成两个大小为25的块 其中一块挂到可利用空间表上,另一块分给用户(地址0-31)。如此下去,最后每个用户得到 的存储空间的起始地址如图8-2,6个用户分配所需要的存储空间后可利用空间表的状态如 图8-3 在回收时,因为给申请45的用户分配了2,其伙伴地址是0,在占用中,不能合并,只能挂 到可利用空间表上。在回收大小为52的占用块时,其伙伴地址是192,也在占用。回收大小 为11的占用块时,其伙伴地址是48,可以合并为大小2的块,挂到可利用空间表上。回收3 个占用块之后可利用空间表的状态如图8-4
第八章动态存储管理 一．选择题 1C 二．判断题 1．错误 2．正确 三．填空题 1．（1）480+8=488（480 %23+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+2k (若 p % 2k+1=0),或 buddy(p,k)=p-2 k (若 p % 2k+1=2k ) 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=29 ,可利用空间表的初始状态图如 8-1 所示。 当用户申请大小为 23 的内存块时,因 2 4 <23<=25 ,但没有大小为 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 9 2 0 2 1 2 2 2 3 2 4 2 5 2 6 2 7 2 8 2 9
储大小「起始地址 128 19 19 图8-2 图8-1 (注:在图8.3和8.4画上了占用块,从原理上,只有空闲块才出现在“可利用空间表”中。) 21 ola 21A 14 a图地量种P回 21 17}-日 图8-3 图8-4 9.因为768%2=0,所以768和768+2=896互为伙伴,伙伴合并后,首址为768,块大小 为2。因为768%2=2,所以,所以首址768大小为2的块和首址512大小为2的块合并, 成为首址512大小为2的空闲块。因为128%21=2,其伙伴地址为128-2=0,将其插入可 利用空间表中。回收后该伙伴系统的状态图如下 10.(1)系统回收一个起始地址为559,大小为45的空闲块后,因右侧起始地址604为空 闲块,应与之合并。合并后,起始地址为559,大小为167的空闲块。链表状态如图10.(1) o56 0117t053 0 0
图 8-2 图 8-1 （注：在图 8.3 和 8.4 画上了占用块，从原理上，只有空闲块才出现在“可利用空间表”中。） 图 8-3 图 8-4 9． 因为 768 % 27+1=0，所以 768 和 768+27 =896 互为伙伴, 伙伴合并后,首址为 768,块大小 为 2 8。因为 768 % 28+1=28 ,所以,所以首址 768 大小为 2 8 的块和首址 512 大小为 2 8 的块合并, 成为首址 512 大小为 2 9 的空闲块。因为 128 % 27+1=27，其伙伴地址为 128-2 7 =0, 将其插入可 利用空间表中。回收后该伙伴系统的状态图如下。 10．（1）系统回收一个起始地址为 559，大小为 45 的空闲块后，因右侧起始地址 604 为空 闲块，应与之合并。合并后，起始地址为 559，大小为 167 的空闲块。链表状态如图 10．（1） 所示。 存储大小 起始地址 23 0 45 64 52 128 100 256 11 32 19 192 2 0 2 1 2 2 2 3 2 4 2 5 2 6 2 7 2 8 1 4 0 4 1 5 1 5 0 5 1 6 1 6 1 7 0 7 0 0 0 0 0 0 0 0 802 213 462 56 117 53 pav 559 167 1 5 1 5 0 5 6 6 1 7 0 7 0 5 2 0 2 1 2 2 2 3 2 4 2 5 2 6 2 7 2 8 0 0 ... 2 6 2 7 2 8 2 9 512 128 256
10.(1) (2)系统在接受存储块大小为100的请求后,将大小为117的空闲块分出100给予用户 在回收一个起始地址为515,大小为44的空闲块之后,因左侧起始地址462大小53和右侧 起始地址559大小167均为空闲块,应与之合并。合并后,起始地址为462,大小为264的 空闲块。链表状态如图10.(2)所示。 pav 10.(2) m叶
10．（1） （2）系统在接受存储块大小为 100 的请求后，将大小为 117 的空闲块分出 100 给予用户。 在回收一个起始地址为 515，大小为 44 的空闲块之后，因左侧起始地址 462 大小 53 和右侧 起始地址 559 大小 167 均为空闲块，应与之合并。合并后，起始地址为 462，大小为 264 的 空闲块。链表状态如图 10．（2）所示。 10．（2） 0 0 0 0 0 0 802 213 462 56 pav 17 264