占用块和空闲块
对于计算机中的内存来说，称已经分配给用户的的内存区统称为“占用块”；还未分配出去的内存区统称为“空闲块”或者“可利用空间块”。
系统的内存管理
对于初始状态下的内存来说，整个空间都是一个空闲块（在编译程序中称为“堆”）。但是随着不同的用户不断地提出存储请求，系统依次分配。
整个内存区就会分割成两个大部分：低地址区域会产生很多占用块；高地址区域还是空闲块。
当某些用户运行结束，所占用的内存区域就变成了空闲块，如图2：
时，就形成了占用块和空闲块犬牙交错的状态。当后续用户请求分配内存时，系统有两种分配方式：
- 系统继续利用高地址区域的连续空闲块分配给用户，不去理会之前分配给用户的内存区域的状态。直到分配无法进行，也就是高地址的空闲块不能满足用户的需求时，系统才会去回收之前的空闲块，重新组织继续分配；
- 当用户运行一结束，系统马上将其所占空间进行回收。当有新的用户请求分配内存时，系统遍历所有的空闲块，从中找出一个合适的空闲块分配给用户。
可利用空间表
系统需要建立一张记录所有空闲块信息的表。表的形式有两种：目录表和链表。各自的结构如图3所示：
图3 目录表和链表
目录表：表中每一行代表一个空闲块，由三部分组成：
- 初始地址：记录每个空闲块的起始地址。
- 空闲块大小：记录每个空闲块的内存大小。
- 使用情况：记录每个空闲块是否存储被占用的状态。
链表：表中每个结点代表一个空闲块，每个结点中需要记录空闲块的使用情况、大小和连接下一个空闲块的指针域。
由于链表中有指针的存在，所以结点中不需要记录各内存块的起始地址。
存储空闲块的可利用空间表有以下不同的结构：
- 如果每次用户请求的存储空间大小相同，对于此类系统中的内存来说，在用户运行初期就将整个内存存储块按照所需大小进行分割，然后通过链表链接。当用户申请空间时，从链表中摘除一个结点归其使用；用完后再链接到可利用空间表上。
- 每次如果用户申请的都是若干种大小规格的存储空间，针对这种情况可以建立若干个可利用空间表，每一个链表中的结点大小相同。当用户申请某一规格大小的存储空间时，就从对应的链表中摘除一个结点供其使用；用完后链接到相同规格大小的链表中。
- 用户申请的内存的大小不固定，所以造成系统分配的内存块的大小也不确定，回收时，链接到可利用空间表中每个结点的大小也各不一样。
第 2 种情况下容易面临的问题是：如果同用户申请空间大小相同的链表中没有结点时，就需要找结点更大的链表，从中取出一个结点，一部分给用户使用，剩余部分插入到相应大小的链表中；回收时，将释放的空闲块插入到大小相同的链表中去。如果没有比用户申请的内存空间相等甚至更大的结点时，就需要系统重新组织一些小的连续空间，然后给用户使用。
分配存储空间的方式
通常情况下系统中的可利用空间表是第 3 种情况。如图 3(C) 所示。由于链表中各结点的大小不一，在用户申请内存空间时，就需要从可利用空间表中找出一个合适的结点，有三种查找的方法：
- 首次拟合法：在可利用空间表中从头开始依次遍历，将找到的第一个内存不小于用户申请空间的结点分配给用户，剩余空间仍留在链表中；回收时只要将释放的空闲块插入在链表的表头即可。
- 最佳拟合法：和首次拟合法不同，最佳拟合法是选择一块内存空间不小于用户申请空间，但是却最接近的一个结点分配给用户。为了实现这个方法，首先要将链表中的各个结点按照存储空间的大小进行从小到大排序，由此，在遍历的过程中只需要找到第一块大于用户申请空间的结点即可进行分配；用户运行完成后，需要将空闲块根据其自身的大小插入到链表的相应位置。
- 最差拟合法：和最佳拟合法正好相反，该方法是在不小于用户申请空间的所有结点中，筛选出存储空间最大的结点，从该结点的内存空间中提取出相应的空间给用户使用。为了实现这一方法，可以在开始前先将可利用空间表中的结点按照存储空间大小从大到小进行排序，第一个结点自然就是最大的结点。回收空间时，同样将释放的空闲块插入到相应的位置上。
以上三种方法各有所长：
- 最佳拟合法由于每次分配相差不大的结点给用户使用，所以会生成很多存储空间特别小的结点，以至于根本无法使用，使用过程中，链表中的结点存储大小发生两极分化，大的很大，小的很小。该方法适用于申请内存大小范围较广的系统
- 最差拟合法，由于每次都是从存储空间最大的结点中分配给用户空间，所以链表中的结点大小不会起伏太大。依次适用于申请分配内存空间较窄的系统。
- 首次拟合法每次都是随机分配。在不清楚用户申请空间大小的情况下，使用该方法分配空间。
边界标识法管理动态内存
使用边界标识法的系统管理内存时，可利用空间表中的结点的构成如图 4：
图4 结构构成
每个结点中包含3个区域，head域、foot域和space域：
- space域表示为该内存块的大小，它的大小通过head域中的size值表示。
- head域中包含有4部分：llink 和rlink分别表示指向当前内存块结点的直接前驱和直接后继。tag值用于标记当前内存块的状态，是占用块（用 1 表示）还是空闲块（用 0 表示）。size用于记录该内存块的存储大小。
- foot域中包含有2部分：uplink 是指针域，用于指向内存块本身，通过uplink就可以获取该内存块所在内存的首地址。tag同head域中的tag相同，都是记录内存块状态的。
注意：head域和foot域在本节中都假设只占用当前存储块的1个存储单位的空间，对于该结点整个存储空间来说，可以忽略不计。也就是说，在可利用空间表中，知道下一个结点的首地址，该值减1就可以找到当前结点的foot域。
边界标识法管理的内存块结点代码：
typedef struct WORD{
union{
struct WORD *llink;//指向直接前驱
struct WORD *uplink;//指向结点本身
};
int tag;//标记域,0表示为空闲块；1表示为占用块
int size;//记录内存块的存储大小
struct WORD *rlink;//指向直接后继
OtherType other;//内存块可能包含的其它的部分
}WORD,head,foot,*Space;
分配算法
3 种分配方法分别为：首部拟合法、最佳拟合法和最差拟合法。
- 选定一个常量e，每次分配空间时，判断当前内存块向用户分配空间后，如果剩余部分的容量比e小，则将整个内存块全部分配给用户。
- 采用头部拟合法进行分配时，如果每次都从pav指向的结点开始遍历，在若干次后，会出现存储量小的结点密集地分布在pav结点附近的情况，严重影响遍历的时间。解决办法就是：在每次分配空间后，让pav指针指向该分配空间结点的后继结点，然后从新的pav指向的结点开始下一次的分配。
首部拟合法具体实现：
Space AllocBoundTag(Space *pav, int n)
{
Space p, f;
int e = 10; //设定常亮 e 的值
//如果在遍历过程，当前空闲块的在存储容量比用户申请空间 n 值小，在该空闲块有右孩子的情况下直接跳过
for (p = (*pav); p && p->size < n && p->rlink != (*pav); p = p->rlink)
;
//跳出循环，首先排除p为空和p指向的空闲块容量小于 n 的情况
if (!p || p->size < n)
{
return NULL;
}
else
{
//指针f指向p空闲块的foot域
f = FootLoc(p);
//调整pav指针的位置，为下次分配做准备
(*pav) = p->rlink;
//如果该空闲块的存储大小比 n 大，比 n+e 小，负责第一种情况，将 p 指向的空闲块全部分配给用户
if (p->size - n <= e)
{
if ((*pav) == p)
{
pav = NULL;
}
else
{
//全部分配用户，即从可利用空间表中删除 p 空闲块
(*pav)->llink = p->llink;
p->llink->rlink = (*pav);
}
//同时调整head域和foot域中的tag值
p->tag = f->tag = 1;
}
//否则，从p空闲块中拿出 大小为 n 的连续空间分配给用户，同时更新p剩余存储块中的信息。
else
{
//更改分配块foot域的信息
f->tag = 1;
p->size -= n;
//f指针指向剩余空闲块 p 的底部
f = FootLoc(p);
f->tag = 0;
f->uplink = p;
p = f + 1; //p指向的是分配给用户的块的head域，也就是该块的首地址
p->tag = 1;
p->size = n;
}
return p;
}
}
回收算法
系统需要立即回收被用户占用的存储空间，以备新的用户使用。回收算法中需要解决的问题是：在若干次分配操作后，可利用空间块中会产生很多存储空间很小以致无法使用的空闲块。但是经过回收用户释放的空间后，可利用空间表中可能含有地址相邻的空闲块，回收算法需要将这些地址相邻的空闲块合并为大的空闲块供新的用户使用。合并空闲块有3种情况：
- 该空闲块的左边有相邻的空闲块可以进行合并；
- 该空闲块的右边用相邻的空闲块可以进行合并；
- 该空闲块的左右两侧都有相邻的空闲块可以进行合并；
判断当前空闲块左右两侧是否为空闲块的方法是：对于当前空闲块p ，p-1 就是相邻的低地址处的空闲块的foot域，如果foot域中的tag值为0 ，表明其为空闲块； p+p->size 表示的是高地址处的块的head域，如果head域中的tag值为 0，表明其为空闲块。
如果当前空闲块的左右两侧都不是空闲块，而是占用块，此种情况下只需要将新的空闲块按照相应的规则（头部拟合法随意插入，其它两种方法在对应位置插入）插入到可利用空间表中即可。实现代码为：
//设定p指针指向的为用户释放的空闲块
p->tag=0;
//f指针指向p空闲块的foot域
Space f=FootLoc(p);
f->uplink=p;
f->tag=0;
//如果pav指针不存在，证明可利用空间表为空，此时设置p为头指针，并重新建立双向循环链表
if (!pav) {
pav=p->llink=p->rlink=p;
}else{
//否则，在p空闲块插入到pav指向的空闲块的左侧
Space q=pav->llink;
p->rlink=pav;
p->llink=q;
q->rlink=pav->llink=p;
pav=p;
}
该空闲块的左侧相邻的块为空闲块，右侧为占用块，处理的方法是：只需要更改左侧空闲块中的size的大小，并重新设置左侧空闲块的foot 域即可（如图2）。
例如，当大小为$2^{8}$ ，起始地址为512的伙伴块的起始地址的计算方式为：由于512 MOD $2^{9}$=0，所以，$512+2^{8}=768$，及如果该存储块回收时，只需要查看起始地址为 768 的存储块的状态，如果是空闲块则两者合并，反之直接将回收的释放块链接到大小为$2^{8}$的链表中。
总结
使用伙伴系统进行存储空间的管理过程中，在用户申请空间时，由于大小不同的空闲块处于不同的链表中，所以分配完成的速度会更快，算法相对简单。
回收存储空间时，对于空闲块的合并，不是取决于该空闲块的相邻位置的块的状态；而是完全取决于其伙伴块。所以即使其相邻位置的存储块时空闲块，但是由于两者不是伙伴的关系，所以也不会合并。这也就是该系统的缺点之一：由于在合并时只考虑伙伴，所以容易产生存储的碎片。
垃圾回收机制
当用户发出申请空间的请求后，系统向用户分配内存；用户运行结束释放存储空间后，系统回收内存。这两部操作都是在用户给出明确的指令后，系统对存储空间进行有效地分配和回收。
但是在实际使用过程中，有时会因为用户申请了空间，但是在使用完成后没有向系统发出释放的指令，导致存储空间既没有被使用也没有被回收，变为了无用单元或者会产生悬挂访问的问题。
什么是无用单元？简单来讲，无用单元是一块用户不再使用，但是系统无法回收的存储空间。例如在C语言中，用户可以通过 malloc 和 free 两个功能函数来动态申请和释放存储空间。当用户使用 malloc 申请的空间使用完成后，没有使用 free 函数进行释放，那么该空间就会成为无用单元。
悬挂访问也很好理解：假设使用malloc申请了一块存储空间，有多个指针同时指向这块空间，当其中一个指针完成使命后，私自将该存储空间使用free释放掉，导致其他指针处于悬空状态，如果释放掉的空间被再分配后，再通过之前的指针访问，就会造成错误。数据结构中称这种访问为悬挂访问。
解决存储空间可能成为无用单元或者产生悬挂访问的方法有两个：
- 每个申请的存储空间设置一个计数域，这个计数域记录的是指向该存储空间的指针数目，只有当计数域的值为 0 时，该存储空间才会被释放。
- 在程序运行时，所有的存储空间无论是处于使用还是空闲的状态，一律不回收，当系统中的可利用空间表为空时，将程序中断，对当前不在使用状态的存储空间一律回收，全部链接成一个新的可利用空间表后，程序继续执行。
使用第二种方式，可以分为两步进行：
- 对所有当前正在使用的存储空间加上被占用的标记（对于广义表来说，可以在每个结点结构的基础上，添加一个 mark 的标志域。在初始状态下，所有的存储空间全部标志为 0，被占用时标记为 1）；
- 依次遍历所有的存储空间，将所有标记为 0 的存储空间链接成一个新的可利用空间表。
对正在被占用的存储空间进行标记的方法有三种：
- 从当前正在工作的指针变量开始，采用递归算法依次将所有表中的存储结点中的标志域全部设置为 1；
*第一种方法中使用递归算法实现的遍历。而递归底层使用的栈的存储结构，所以也可以直接使用栈的方式进行遍历； - 以上两种方法都是使用栈结构来记录遍历时指针所走的路径，便于在后期可以沿原路返回。所以第三种方式就是使用其他的方法代替栈的作用。
内存碎片化处理
这些地址连续的未被占用的存储区在编译程序中称为堆。
分配内存空间
在分配内存空间时，每次都从可利用空间中选择最低（或者最高）的地址进行分配。具体的实现办法为：设置一个指针（称为堆指针），每次用户申请存储空间时，都是堆的最低（或者最高）地址进行分配。假设当用户申请 N 个单位的存储空间时，堆指针向高地址（或者低地址）移动 N 个存储单位，这 N 个存储单位即为分配给用户使用的空闲块，空闲块的起始地址为堆指针移动之前所在的地址。
例如，某一时间段有四个用户（A、B、C、D）分别申请 12 个单位、6 个单位、10 个单位和 8 个单位的存储空间，假设此时堆指针的初值为 0。则分配后存储空间的效果为：
回收算法
由于系统中的可利用空间始终都是一个连续的存储空间，所以回收时必须将用户释放的存储块合并到这个堆上才能够重新使用。存储紧缩有两种做法：其一是一旦用户释放所占空间就立即进行回收紧缩；另外一种是在程序执行过程中不立即回收用户释放的存储块，而是等到可利用空间不够分配或者堆指针指向了可利用存储区的最高地址时才进行存储紧缩。
具体的实现过程是：
- 计算占用块的新地址。设立两个指针随巡查向前移动，分别用于指示占用块在紧缩之前和之后的原地址和新地址。因此，在每个占用块的第一个存储单位中，除了存储该占用块的大小和标志域之外，还需要新增一个新地址域，用于存储占用块在紧缩后应有的新地址，即建立一张新、旧地址的对照表。
- 修改用户的出事变量表，保证在进行存储紧缩后，用户还能找到自己的占用块。
- 检查每个占用块中存储的数据。如果有指向其它存储块的指针，则需作相应修改。
- 将所有占用块迁移到新地址去，即进行数据的传递。
最后，还要将堆指针赋以新的值。
