邊界辨別法——配置設定和回收

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