第八章动态存储管理 选择题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