九、动态存储管理

九、动态存储管理

1. 边界标识法

边界标识法是在动态存储块的上下边界各设一个双向链表结点，分别称其为头部域和底部域。

通过头部域和底部域的 tag = true ,告诉相邻块自己处于被占用状态。通过块的首地址，可以找到左邻块（低址）的底部域，从而获悉左邻块是否被占用；通过块的首地址和 size = n ，可以找到右邻块（高址）的首地址，从而获悉右邻块是否被占用。当占用块被释放时，其左右邻块如果没被占用的，就要和它们合并成一个大的空闲块。

动态存储区的所有空闲块链接在一个双向链表中，被称为 “可利用空间表” ，等待被分配和使用。

可利用空间表的分配算法有首次拟合法、最佳拟合法和最差拟合法 3 种。

• 首次拟合法是从可利用空间表的第一个结点找起，将遇到的第一个够大的空闲块分配；
• 最佳拟合法是将最接近申请空间的空闲块分配；
• 最差拟合法是将最大的空闲块分配。

最佳拟合法和最差拟合法要将可利用空间表按 size 有序存储。

2. 伙伴系统

伙伴系统不是申请多大空间就分配多大空间，而是以 2 的幂次分配动态存储空间的。

当伙伴系统分配空间时，找到最小满足需要的空闲块，将其从可利用空间表中删除。如果这个空闲块的一半就足够使用，则将此空闲块分割成相等的两部分，这两部分互称为 “伙伴” 。将前半部分进行分配，后半部分插回到相应尺寸的可利用空间表中。如果前半部分还太大，则继续分隔、插回处理。

当伙伴系统回收空间时，要看其 “伙伴” 块是否为空闲块，如果是则要合并两伙伴块。伙伴系统的动态分配只设头部域，因为它的大小不是任意的。通过它的头部域信息，就可以找到其左右邻块 “伙伴” ，并可知道其左右邻块 “伙伴” 是否空闲，所以不需要设底部域。

伙伴系统在回收释放块时，也要合并它的左右邻块。和边界标识法不同的是，在回收释放块时，其左右邻块即使是空闲块，也不一定合并，还要看它们是否为伙伴。如果两相邻块是伙伴，就必须同时满足两个条件：（1）它们的块大小相等；（2）由整个可利用存储区的起点 t 到合并块之前的空间大小是这个合并块的整数倍。