数据结构之动态内存管理机制（上）：https://developer.aliyun.com/article/1471376
如果用户释放的内存块的相邻左侧为占用块，右侧为空闲块，处理的方法为：将用户释放掉的存储块替换掉右侧的空闲块，同时更改存储块的 size 和右侧空闲块的 uplink 指针的指向（如图 3 所示）。
图 3 空闲块合并（当前块、右侧内存块）
实现代码为：
Space t=p+p->size;//t指针指向右侧空闲块的首地址 p->tag=0;//初始化head域的tag值为0 //找到t右侧空闲块的前驱结点和后继结点，用当前释放的空闲块替换右侧空闲块 Space q=t->llink; p->llink=q; q->rlink=p; Space q1=t->rlink; p->rlink=q1; q1->llink=p; //更新释放块的size的值 p->size+=t->size; //更改合并后的foot域的uplink指针的指向 Space f=FootLoc(t); f->uplink=p;
如果当前用户释放掉的空闲块，物理位置上相邻的左右两侧的内存块全部为空闲块，需要将 3 个空闲块合并为一个更大的块，操作的过程为：更新左侧空闲块的 size 的值，同时在可利用空间表中摘除右侧空闲块，最后更新合并后的大的空闲块的 foot 域。
此情况和只有左侧有空闲块的情况雷同，唯一的不同点是多了一步摘除右侧相邻空闲块结点的操作。
实现代码为：
int n=p->size; Space s=(p-1)->uplink;//找到释放内存块物理位置相邻的低地址的空闲块 Space t=p+p->size;//找到物理位置相邻的高地址处的空闲块 s->size+=n+t->size;//更新左侧空闲块的size的值 //从可利用空间表中摘除右侧空闲块 Space q=t->llink; Space q1=t->rlink; q->rlink=q1; q1->llink=q; //更新合并后的空闲块的uplink指针的指向 Space f=FootLoc(t); f->uplink=s;
伙伴系统管理动态内存
伙伴系统本身是一种动态管理内存的方法，和边界标识法的区别是：使用伙伴系统管理的存储空间，无论是空闲块还是占用块，大小都是 2 的 n 次幂（n 为正整数）。
例如，系统中整个存储空间为 2m 个字。那么在进行若干次分配与回收后，可利用空间表中只可能包含空间大小为：20、21、22、…、2m 的空闲块。
字是一种计量单位，由若干个字节构成，不同位数的机器，字所包含的字节数不同。例如，8 位机中一个字由 1 个字节组成；16 位机器一个字由 2 个字节组成。
可利用空间表中结点构成
伙伴系统中可利用空间表中的结点构成如图 1 所示：
图 1 结点构成
header 域表示为头部结点，由 4 部分构成：
- llink 和 rlink 为结点类型的指针域，分别用于指向直接前驱和直接后继结点。
- tag 值：用于标记内存块的状态，是占用块（用 1 表示）还是空闲块（用 0 表示）
- kval ：记录该存储块的容量。由于系统中各存储块都是 2 的 m 幂次方，所以 kval 记录 m 的值。
代码表示为：
typedef struct WORD_b{ struct WORD_b *llink;//指向直接前驱 int tag;//记录该块是占用块还是空闲块 int kval;//记录该存储块容量大小为2的多少次幂 struct WORD_b *rlink;//指向直接后继 OtherType other;//记录结点的其它信息 }WORD_b,head;
在伙伴系统中，由于系统会不断地接受用户的内存申请的请求，所以会产生很多大小不同但是都是容量为 2m 的内存块，所以为了在分配的时候查找方便，系统采用将大小相同的各自建立一个链表。对于初始容量为 2m 的一整块存储空间来说，形成的链表就有可能有 m+1 个，为了更好的对这些链表进行管理，系统将这 m+1 个链表的表头存储在数组中，就类似于邻接表的结构，如图 2。
图 2 伙伴系统的初始状态
可利用空间表的代码表示为：
#define m 16//设定m的初始值 typedef struct HeadNode { int nodesize;//记录该链表中存储的空闲块的大小 WORD_b * first;//相当于链表中的next指针的作用 }FreeList[m+1];//一维数组
分配算法
伙伴系统的分配算法很简单。假设用户向系统申请大小为 n 的存储空间，若 2k-1 < n <= 2k，此时就需要查看可利用空间表中大小为 2k 的链表中有没有可利用的空间结点：
- 如果该链表不为 NULL，可以直接采用头插法从头部取出一个结点，提供给用户使用；
- 如果大小为 2k 的链表为 NULL，就需要依次查看比 2k 大的链表，找到后从链表中删除，截取相应大小的空间给用户使用，剩余的空间，根据大小插入到相应的链表中。
例如，用户向系统申请一块大小为 7 个字的空间，而系统总的内存为 24 个字，则此时按照伙伴系统的分配算法得出：22 < 7 < 23，所以此时应查看可利用空间表中大小为 23 的链表中是否有空闲结点：
- 如果有，则从该链表中摘除一个结点，直接分配给用户使用；
- 如果没有，则需依次查看比 23 大的各个链表中是否有空闲结点。假设，在大小 24 的链表中有空闲块，则摘除该空闲块，分配给用户 23 个字的空间，剩余 23 个字，该剩余的空闲块添加到大小为 23 的链表中。
（A）分配前 （B）分配后
图 3 伙伴系统分配过程
回收算法
无论使用什么内存管理机制，在内存回收的问题上都会面临一个共同的问题：如何把回收的内存进行有效地整合，伙伴系统也不例外。
当用户申请的内存块不再使用时，系统需要将这部分存储块回收，回收时需要判断是否可以和其它的空闲块进行合并。
在寻找合并对象时，伙伴系统和边界标识法不同，在伙伴系统中每一个存储块都有各自的“伙伴”，当用户释放存储块时只需要判断该内存块的伙伴是否为空闲块，如果是则将其合并，然后合并的新的空闲块还需要同其伙伴进行判断整合。反之直接将存储块根据大小插入到可利用空间表中即可。
判断一个存储块的伙伴的位置时，采用的方法为：如果该存储块的起始地址为 p，大小为 2k，则其伙伴所在的起始地址为：
例如，当大小为 28 ，起始地址为 512 的伙伴块的起始地址的计算方式为：
由于 512 MOD 29=0，所以，512+28=768，及如果该存储块回收时，只需要查看起始地址为 768 的存储块的状态，如果是空闲块则两者合并，反之直接将回收的释放块链接到大小为 28 的链表中。
总结
使用伙伴系统进行存储空间的管理过程中，在用户申请空间时，由于大小不同的空闲块处于不同的链表中，所以分配完成的速度会更快，算法相对简单。
回收存储空间时，对于空闲块的合并，不是取决于该空闲块的相邻位置的块的状态；而是完全取决于其伙伴块。
所以即使其相邻位置的存储块时空闲块，但是由于两者不是伙伴的关系，所以也不会合并。这也就是该系统的缺点之一：由于在合并时只考虑伙伴，所以容易产生存储的碎片。
无用单元收集（垃圾回收机制）
通过前几节对可利用空间表进行动态存储管理的介绍，运行机制可以概括为：
- 当用户发出申请空间的请求后，系统向用户分配内存；
- 用户运行结束释放存储空间后，系统回收内存。
这两部操作都是在用户给出明确的指令后，系统对存储空间进行有效地分配和回收。
但是在实际使用过程中，有时会因为用户申请了空间，但是在使用完成后没有向系统发出释放的指令，导致存储空间既没有被使用也没有被回收，变为了无用单元或者会产生悬挂访问的问题。
什么是无用单元？简单来讲，无用单元是一块用户不再使用，但是系统无法回收的存储空间。例如在C语言中，用户可以通过 malloc 和 free 两个功能函数来动态申请和释放存储空间。当用户使用 malloc 申请的空间使用完成后，没有使用 free 函数进行释放，那么该空间就会成为无用单元。
悬挂访问也很好理解：假设使用 malloc 申请了一块存储空间，有多个指针同时指向这块空间，当其中一个指针完成使命后，私自将该存储空间使用 free 释放掉，导致其他指针处于悬空状态，如果释放掉的空间被再分配后，再通过之前的指针访问，就会造成错误。数据结构中称这种访问为悬挂访问。
图 1 含有共享子表的广义表
数据结构之动态内存管理机制（下）：
