算法与数据结构 C语言版 第二版 (陈守孔 孟佳娜 武秀川 著) 机械工业出版社 课后答案 第8章 动态存储管理

课后答案网 8 章 动态存储结构 在伙伴系统中的伙伴是指任意两块大小相同、位置相邻的内存块。这种说法对吗？ 【解答】不对。只有同一内存块分裂的两块才互称伙伴。 佳适配法与最先适配法相比，前者容易增加闲置空间的碎片。这种说法对吗？ 【解答】对。 内存中可利用空间已连成一个单链表，对用户的存储空间需求，一般有哪三种分配策略？ 【解答】 首次拟合法；从链表头指针开始查找，找到第一个大于等于所需空间的结点即分配。 最佳拟合法：链表结点大小增序排列，找到第一个大于等于所需空间的结点即分配 。 最差拟合法：链表结点大小逆序排列，总从第一个结点开始分配，将分配后结点所剩空间插入到链表适当位置。 首次拟合法适合事先不知道请求分配和释放信息的情况 ,分配时需查询 ,释放时插在表头。 最佳拟合法适用于请求分配内存大小范围较宽的系统 ,释放时容易产生存储量很小难以利用的内存碎片 ,同时保留那些很大的内存块以备将来可能发生的大内存量的需求，分配与回收均需查询。 最差拟合法适合请求分配内存大小范围较窄的系统 ,分配时不查询 ,回收时查询 ,以便插入适当位置。 算起始二进制地址为 011011110000，长度为 4（十进制）的块的伙伴地址是多少？ 【解答】 011011110100 址为（ 1664） 10大小为（ 128） 10的存储块的伙伴地址是什么？ 地址为（ 2816） 10大小为（ 64） 10的存储块的伙伴地址是什么？ 【解答】 （ 1） 664,7)=1664536 （ 2） 816,6)=2816+64=2880 叙述动态存储分配伙伴系统的基本思想，它和边界标识法不同点是什么？ 【解答】 动态存储分配伙伴系统的基本思想是：在伙伴系统中，无论占用块或空闲块 ，其大小均为 2的 k(k 为 0 的正整数 )次幂。若内存容量为 2m，则空闲块大小只能是 20， 21， 22， 2m。由同一大块分裂而得的两个小块互称“伙课后答案网 空间”，如内存大小为 210的块分裂成两个大小为 29的块。只有两个“伙伴空间”才能合并成一个大空间。 起始地址为 p，大小为 2伙伴的起始地址为： 边界标识法在每块的首尾均有“占用” /“空闲”标志，空闲块合并方便。伙伴系统算法简单，速度快，但只有互为伙伴的两个空闲块才可合并，因而易产生虽空闲但不能归并的碎片。 12个字长的存储，假 设先后有 6个用户申请大小分别为 23，45， 52， 100， 11和 19 的存储空间，然后再顺序释放大小为 45， 52， 11 的占用块。假设以伙伴系统实现动态存储管理。 （ 1） 画出可利用空间表的初始状态。 （ 2） 画出为 6 个用户分配所需要的存储空间后可利用空间表的状态以及每个用户所得到的存储块的起始地址。 （ 3） 画出在回收 3 个占用块之后可利用空间表的状态。 【解答】 因为 512=29,可利用空间表的初始状态图如 8 当用户申请大小为 23 的内存块时 ,因 2423=25,但没有大小为 25的块 ,只有大小为 29的块 ,故将 29的块分裂成两个大小为 28的块 ,其中大小为 28的一块挂到可利用空间表上 ,另一块再分裂成两个大小为 27的块。又将其中大小为 27的一块挂到可利用空间表上 ,另一块再分裂成两个大小为 26的块 ,一块 26的块挂到可利用空间表上 ,另一块分裂成两个大小为 25的块 ,其中一块挂到可利用空间表上 ,另一块分给用户 (地址 0 31)。如此下去 ,最后每个用户得到的存储空间的起始地址如图 86 个用户分配所需要的存储空间后可利用空间表的状态如图 8 在回收时 ,因为给申请 45的用户分配了 26,其伙伴地址是 0,在占用中 ,不能合 并 ,只能挂到可利用空间表上。在回收大小为 52的占用块时 ,其伙伴地址是 192,也在占用。回收大小为 11的占用块时 ,其伙伴地址是 48,可以合并为大小 25的块 , 挂到可利用空间表上。回收 3个占用块之后可利用空间表的状态如图 8 图 8 图 8储大小 起始地址 23 0 45 64 52 128 100 256 11 32 19 192 课后答案网 注：在图 图 上了占用块，从原理上，只有空闲块才出现在“可利用空间表”中。） 图 8 图 8图所示的伙伴系统中，回收两块首地址分别为 768 及 128，大小为 27的存储块，请画出回收后该伙伴系统的状态图。 【解答】 因为 768 % 27+1=0，所以 768 和 768+27=896 互为伙伴 , 伙伴合并后 ,首址为 768,块大小为 28。因为 768 % 28+1=28,所以 ,所以首址 768 大小为 28