Boundary Tag Method
边界标识法(boundary tag method)是操作系统中用以进行动态分区分配的一种存储管理方法。
系统将所有的空闲块链接在一个双重循环链表结构的可利用空间表中；分配可按首次拟合进行，也可按最佳拟合进行。
系统的特点：在每个内存区的头部和底部两个边界上分别设有标识，以标志该区域为占用块或空闲块(目的：以便将所有地址连续的空闲存储区组合成一个尽可能大的空闲块)。
可利用空间表的结构
表中结点结构(它表示一个空闲块)如下图：
整个结点由3部分组成。
space为一组地址连续的存储单元，是可以分配各用户使用的内存区域，它的大小由head中的size域指示，并以头部head和底部foot作为它的两个边界。- 在
head和foot中分别设有标志域tag，且设定空闲块中tag的值为"0"，占用块中tag的值为"1"。 foot位于结点底部，因此它的地址是随结点中space空间大小而变。
可利用空间表设为双重循环链表。
head中的llink和rlink分别指向前驱结点和后继结点。- 表中不设表头结点，表头指针
pav可以指向表中任一结点(任何一个结点都可以看作是链表中的第一个结点)； - 表头指针为空，说明可利用空间表为空。
foot中的uplink域也为指针，指向本结点(它的值为该空闲块的首地址)。
分配算法
下面说一说分配。
(假设下面都采用首次拟合法进行分配)。
在边界标识法中作了如下两条约定(【目的】为了整个系统更有效的运行)：
约定一：
- 【问题】出现一些容量及小总也分配不出去的空闲块
- 【处理】选定一个适当的常量e，当m-n<=e时，就将容量为m的空闲块整块分配给用户；反之，值分配其中的n个字的内存块。(同时，为了避免修改指针，约定将该结点中高地址部分分配给用户)
约定二：
- 【问题】如果每次分配都从一个结点开始查找的话，势必造成存储量小的结点密集在头指针pav所指结点的附近，这样会增加查询较大空间块的时间。
- 【处理】在每次分配之后，令指针pav指向刚进行过分配的结点的后继结点。(这样子可以使得分配后剩余的小块均匀地分布在链表中，避免上述弊端)
【图：某系统的可利用空间表】
【分配策略的算法描述】
Space AllocBoundTag(Space &pav, int n) {
// 若有不小于n的空闲块，则分配相应的存储块，并返回首地址，否则返回NULL；
// 若分配后可利用空间表不空，则pav指向表中刚分配过的结点的后继结点。
for (p = pac; p && p->size < n && p->rlink != pav; p = p->next); // 查询不小于n的空闲块
if (!p || p->size < n) return NULL; // 如果找不到，则返回NULL
else { // p指向找到的空闲块
f = FootLoc(p); // 指向底部
pav = p->next; // pav指向*p结点的后继结点
if (p->size - n <= e) { // 整块分配，不保留<=e的剩余量
if (pav == p) pav = NULL; // 可利用空间表为空表
else { // 在表中删除分配的结点
pav->llink = p->llink;
p->llink->rlink = pav;
}
p->tag = 1; // 修改分配结点的头部和底部标志
f->tag = 1;
}
else { // 分配该块后面的n个字
f->tag = 1; // 修改分配块的底部标志
p->size -= n; // 置剩余块大小
f = FootLoc(p); // 指向剩余块底部
f->tag = 0; // 设置剩余块底部
f->uplink = p;
p = f + 1; // 指向分配块头部
p->tag = 1; // 设置分配块头部
p->size = n;
}
return p; // 返回分配块收地址
}
}
回收算法
一旦用户释放占用块，系统需立即回收以备新的请求产生时进行再分配。为了使物理地址相邻的空闲块结合成一个尽可能大的点，首先要检查刚释放的占用块的左右紧邻是否为空闲块，由本文上述内容可见(系统在每个内存区，无论是占用块还是空闲块的边界上都设有标志值)，所以非常容易辨别。
一些值以及说明
假设用户释放的头部地址为p，则与其低地址紧邻的内存区的底部地址为p-1，与其嘎坪地址紧邻的内存区的头部地址为p+p->size，它们中的标志域就表明了这两个邻区的使用状况：
- 若(p-1)->tag = 0，说明其左邻为空闲块；
- 若(p+p->size)->tag = 0，说明其右邻为空闲块。
分情况讨论
主要分为四种情况：
- 左右均为占用块 -> 直接插入表中
- 只有左为空 -> 和左边的合并插入表中
- 只有右为空 -> 和右边的合并插入表中
- 左右均为空闲块 -> 和左右的合并插入表中
下面是四种情况的具体操作：
- 左右均为占用块。简单插入即可(因为边界标识法在首次拟合进行分配时对可利用空间表的结构没有任何要求，则新的空闲块可以插入表中任何位置，当然最简单的就是插入在pav所指结点之前或之后)。
- 只有左为空闲块。改变左邻空闲块的结点：增加结点的size域的值，并且重新设置结点的底部。
- 只有右为空闲块。结点的底部位置不变，但是头部要变，链表中的指针也要变。
- 左右均为空闲块。增加左邻空闲块的space容量，同时在链表中删去右邻空闲块的结点。
下面是四种情况的算法描述：
/*左右均为占用块的情况*/
p->tag = 0; FootLoc(p)->uplink = p; FootLoc(p)->tag = 0;
if(!pav) pav = p->llink = p->rlink = p;
else {
q = pav->llink;
p->rlink = pav; p->llink = q;
q->rlink = pav->llink = p;
pav = p; // 令刚释放的结点作为下此分配时最先查询的结点
}
/*只有左邻块为空闲块的情况*/
n = p->size; // 释放块的大小
s = (p - 1)->uplink; // 左邻空闲块的头部地址
s->size += n; // 设置新的空闲块的大小
f = p + n - 1; f->uplink = s; f->tag = 0; // 设置新的空闲块的底部
/*只有右邻块为空闲块的情况*/
t = p + p->size; // 右邻空闲块的头部地址
p->tag = 0; // p为合并后的结点头部地址
q = t->llink; // q为*t结点在可利用空间表中的前驱结点的头部地址
p->llink = q; q->rlink = p; // q指向*p的前驱
q1 = t->rlink; // q1为*t结点在可利用空间表中的后继结点的头部地址
q->rlink = q1; q1->llink = p; // q1指向*p的后继
p->size += t->size; // 新的空闲块的大小
FootLoc->uplink = p; // 底部指针指向新结点的头部
/*左右均为空闲块的情况*/
n = p->size; // 释放块的大小
s = (p - 1)->uplink; // 指向左邻块
t = p + p->size; // 指向右邻块
s->size += n + t->size; // 设置新结点的大小
q = t->llink; q1 = t->rlink; // q != q1
q->rlink = q1; q1->llink = q; // 删去右邻空闲块结点
FootLoc(t)->uplink = s; // 新结点底部指针指向其头部
【图：后三种情况地图解】
小结
边界标识法由于在每个结点的头部和底部设立了标识域，使得用户在回收用户释放的内存块时，很容易判别与它毗邻的内存区是否是空闲块，且不需要查询整个可利用空间表便能找到毗邻的空闲块与其合并(细细品位：优美地利用其物理位置)；再者，由于可利用空间表上结点即不需依结点大小有序(对于首次拟合法而言)，也不需依结点地址有序，则释放块插入时也不需查找链表。由此，不论是哪一种情况，回收空闲块的时间都是个常量，和可利用空间表地大小无关。唯一的缺点是增加了结点底部所占地存储量。