边界标识法——分配和回收

8.3 边界标识法

• 预备知识
• 边界标识法
• • 边界标识法结点结构
  • 首次拟合法分配
  • 回收算法

预备知识

(1) 首次拟合 从表头指针查找，找到的第一个大小不小于m的结点的一部分分配给用户。

分配时需要查找可利用空间表，回收时直接插到表头即可。

(2) 最佳拟合 将可利用空间表中一个不小于m且最接近m的空闲块的一部分分配给用户，推荐按结点从小到大排序，回收时把释放的空闲块插入到合适的位置上。

最佳拟合法适用于请求分配的内存大小范围较广的系统。

最佳拟合无论分配回收都需要查找可利用空间表，因此最费时间。

(3) 最差拟合 将可利用空间表中不小于n且是链表中最大的空闲块的一部分分配给用户，此时结点应当从大到小排序，分配时只需从链表中删除第一个结点，并分配一部分给用户，剩余部分插入到合适位置。

最差拟合每次从最大结点分配，最终结点大小趋于一致，适用于内存大小范围较窄的系统。

最差拟合分配时直接表头分配，回收时需要把空闲块插入在合适位置上，因此需要查找链表。

边界标识法

边界标识法是操作系统中用以动态分区分配的一种存储管理方法，系统将所有空闲块连接在一个双重循环链表结构的可利用空间表中。

边界标识法结点结构

每个内存区头部和底部设标识，标识该区域是占用块（1）还是空闲块（0），使得在回收用户释放的空闲块时易于判别在物理位置上与其相邻的内存内存区域是否为空闲块，以便合并空闲存储区。

//space指示存储单元，单元大小由head中的size域表示，以head和foot作为边界，head和foot中都有标志域tag
typedef struct WORD
{
    union
    {                 //head和foot分别是节点的的第一个字和最后一个字
        WORD *llink;  //头部域，指向前驱结点
        WORD *uplink; //底部域，指向本节点头部，大小随size改变
    };
    int tag; //0空闲1占用，后部和尾部均有
    int size;
    WORD *rlink;            //头部域，指向后继结点
    OtherType other;        //字的其他部分
} WORD, head, foot, *Space; //*Space可利用空间指针类型
           

#define FootLoc(p) p + p->size - 1

指向p所指结点的底部

首次拟合法分配

找到表头指针所指结点起在可利用空间表中查找，找到第一个容量不小于请求分配的存储量的空闲块就进行分配

(1)如果待分配块容量为m个字，每次分配分配n个字给用户，剩余m-n大小的结点仍然留在链表中（剩余容量极小的块）

解决方法：设定一个e，m-n<e时，就将m整块分配给用户，反之分配高地址的n个字给用户(避免修改指针)

(2)如果每次分配都从表头指针开始找的话，会使得存储量小的结点密集在头指针附近，所以每次查找应当从不同结点开始查找，实现方法是使头指针指向刚分配过结点的后继结点

#define e 40
Space AllocBoundTag(Space &pav, int n)
{
    //若有不小于n的空闲块则分配相应的存储块，返回首地址；
    //若分配后表不空，则pav指向表中刚分配过的结点的后继结点
    WORD *p = NULL,*f=NULL;
    for (p = pav; p->size < n && p->rlink != pav; p = p->rlink)
        ; // p->rlink!=pav，循环链表的头
    if (!p || p->size < n)
        return NULL;
    else
    {
        f = FootLoc(p);
        pav = p->rlink;
        if (p->size - n < e)//整块分配，不保留剩余量
        {
            if (pav == p) //可利用表为空表
                pav = NULL; 
            else//删除p结点
            {
                pav->llink = p->llink;
                p->llink->rlink = pav;
            }
            p->tag = f->tag = 1;
            pav=p->llink;//pav指向表中刚分配过的结点的后继结点（严版书上没有我加的，觉得应该有）
        }
        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;
            pav=p->llink;//pav指向表中刚分配过的结点的后继结点（严版书上没有我加的，觉得应该有）
        }
        return p;
    }
}
           

回收算法

若释放块头部地址为p 则p-1为左侧紧邻块地址，p+p->size为右侧紧邻块地址，检查这两个地址中tag就知道是否为空闲块，故有四种情况：

(1) 左右均为占用块，即做简单插入，假设新增结点加在pav指向结点之前；

(2) 左边为空闲块，右边为占用块，只需改变左邻结点的底部，重新设置size；

(3) 左边为占用块，右边空闲块,与右边合并之后，结点头指针改变了位置；

(4) 左右邻均是空闲块，增加左邻的space容量，删去右邻结点。

【注意】 左邻块：(p-1)->uplink；右邻块：p+p->size；

Space MergeBoundTag(Space &pav, WORD *p)
{
    WORD *q = NULL,*f=NULL,*r=NULL;
    int n;
    if ((p - 1)->tag == 1 && (p + p->size)->tag == 1)
    {
        // (1) 左右均为占用块，即做简单插入，假设新增结点加在pav指向结点之前
        p->tag = 0;
        FootLoc(p)->uplink = p;
        FootLoc(p)->tag = 0;
        if (!pav)
            pav = p->llink = p->rlink = p;
        else
        {
            //先维护pav指向的前一个结点，如果每次头插，则pav->llink是最后一个结点q
            q = pav->llink;
            q->rlink = p;
            p->llink = q;
            //再维护pav指向结点的指针
            pav->llink = p;
            p->rlink = pav;
        }
    }
    else if ((p - 1)->tag == 0 && (p + p->size)->tag == 1)
    {
        //(2) 左边为空闲块，右边为占用块，只需改变左邻结点的底部，重新设置size
        // （已经有空闲块，pav非空，不用过多考虑维护pav）
        q = (p - 1)->uplink;
        q->size += p->size;
        f = FootLoc(q) - 1;
        f->uplink = q;
        f->tag = 0;
    }else if((p-1)->tag==1 && (p+p->size)->tag==0){
        // (3) 左边为占用块，右边空闲块,与右边合并之后，结点头指针改变了位置
        // 交代p的右结点的前后结点及其指针
        q=p+p->size;
        q->llink->rlink=p;
        p->llink=q->llink;
        p->rlink=q->rlink;
        q->rlink->llink=p;
        // 修改p右结点的foot
        FootLoc(q)->uplink=p;
        FootLoc(q)->tag=0;
        // 修改p
        p->size+=q->size;
        p->tag=0;
    }else{
        // (4) 左右邻均是空闲块，增加左邻的space容量，删去右邻结点
        // q1, q p r, r1
        q=(p-1)->uplink;//左邻块
        r=p+p->size;//右邻块
        q->rlink=r->rlink;
        r->rlink->llink=q;
        f=FootLoc(r);
        f->uplink=q;
        f->tag=0;
        q->size+=(p->size+r->size);
    }
    //最后令刚释放的结点为下次分配时最先查询的结点
    pav = p;
}
           

参考：

1.严氏数据结构C语言教材

2.https://blog.csdn.net/sinat_34753172/article/details/86584542