《算法与数据结构考研试题精析》笔记(8) - 动态存储管理

Published: by Creative Commons Licence

动态存储管理系统介绍的博客

动态存储管理系统中，通常可有3种不同的分配策略。

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

Buddy System

关于伙伴系统的详细相关介绍，点击《Buddy System》跳转。

关于计算伙伴的起始地址是一个非常重要的考点，考察方法有下面两种方式。

起始地址为480，大小为8的块，其伙伴块的起始地址为（488）；若块大小为32，则其伙伴块的起始地址为（448）。

  • 8 = 2 ^ 3, 480 % (2 ^ (3 + 1)) = 0，所以其伙伴块的起始地址为480 + 8 = 488；
  • 32 = 2 ^ 5, 480 % (2 ^ (5 + 1)) != 0，所以其伙伴块的起始地址为480 - 32 = 448。

下面这种是上面的变形。

二进制地址为011011110000，大小(十进制)为4和16块的伙伴地址分别为（），（）。

  • 先将大小转换为二进制。如4转换为100，观察二进制地址末尾4位是0000(前面有非零项)，和1000(100+0)相比(相当与上面的*2)，所以说明可以整除，故而直接加上原来的100，得到最后4位为0100，前面数位的数值都不变，故而第一个空的答案为011011110100；
  • 第二空同理，16 -> 10000，二进制末尾6位为110000和100000(10000+0)相比不等，故而末尾6位110000减去10000(16转化为的二进制数)得到100000，前面的不变，故而第二个空的答案为011011100000。

无用单元

无用单元是指用户不再使用而系统没有回收的结构和变量。例如p = malloc(size); ...; p = NULL;

关于无用单元更详细的见此博客底部