【学习笔记】数据结构（八）

动态存储管理

8.1 概述

在刚开工时，整个内存区是一个“空闲块“（在 编译程序中称之为＂堆")。

随着用户进入系统，先后提出存储请求，系统则依次进行分配。

在系统运行的初期，整个内存区基本上分隔成两大部分：低地址区包含若干占用块； 高地址区（即分配后的剩余部分）是一个空闲块。

8.2 可利用空间表及分配方法

可利用空间表可以有下列 3种不同的结构形式：

• 第一种情况，系统运行期间所有用户请求分配的存储量大小相同。

  • 在系统开始运行时将归它使用的内存区按所需大小分割成若干大小相同的块，然后用指针链接成一个可利用空间表。

  • 由于表中结点大小相同，则分配时无需查找， 只要将第一个结点分配给用户即可；

  • 同样，当用户释放内存时，系统只要将用户释放的空 闲块插入在表头即可。

  • 可见，这种情况下的可利用空间表实质上是一个链栈。

• 第二种情况，系统运行期间用户请求分配的存储量有若干种大小的规格。

  • 是建立若干个可利用空间表，同一链表中的结点大小相同。

  • eg：用户将请求分配2个字、4个字或8个字的内存块

    • 系统建立 3个结 点大小分别为3个字、5 个字和 9 个字的链表，它们的表头指针分别为 av2、av4 和 av8。

    • 每个结点中的第一个字设有链域(link)【存储指向同一链表中下一结点的指针】, 标志域(tag)【tag - 区别结点为空闲块或占用块】和结点类型域 (type)【type-区别 3 种大小不同的结点】。

    • 而结点中的值域是其大小分别为 2 、4 和 8 个字的连续空间。

  • 分配和回收的方法在很大程度上和第一种情况类似

    • 当结点大小和请求分配的量相同的链表为空时，需查询结点较大的链表，并从中取出 一个结点，将其中一部分内存分配给用户，而将剩余部分插入到相应大小的链表中。

    • 回收时，也只要将释放的空闲块插人到相应大小的链表的表头中去即可。

    • 当结点与请求相符的链表和结点更大的链表均为空时， 分配不能进行，而实际上内存空间并不一定不存在所需大小的连续空间，只是由于在系统 运行过程中，频繁出现小块的分配和回收，使得大结点链表中的空闲块被分隔成小块后插 入在小结点的链表中，此时若要使系统能继续运行，就必须重新组织内存，即执行“存储紧缩”的操作

• 第三种情况，系统在运行期间分配给用户的内存块的大小不固定，可以随请求而变。

  • 系统刚开始工作时，整个内存空间是一个空闲块，即可利用空间表中只有一个大小为整个内存区的结点

  • 标志域、链域之外，还有一个结点大小域(size),以指示空闲块的存储量

  • 分配：

    • 某用户所需大小为n的内存，而可利用空间表中仅有一块大小为m≥n 的空闲块，则只需将其中大小为 n 的一部分分配给申请分配的用户，同时将剩余大小为m-n 的部分作为一个结点留在链表中即可。

    • 若可利用空间表中有若干个不小于n的空闲块时

      • 首次拟合法。从表头指针开始查找可利用空间表，将找到的第一个大小不小于n的空闲块的一部分分配给用户。在回收时，只要将释放的空闲块插人在链表的表头即可。常适用于系统事先不掌握运行期间可能出现的请 求分配和释放的信息的情况。
      • 最佳拟合法。将可利用空间表中一个不小于 n且最接近n 的空闲块的一部分分配给用户。但在回收时，必须将释放的空闲块插入到合适的位置上去。适用于请求分配的内存大小范 围较广的系统
      • 最差拟合法。将可利用空间表中不小于 n且是链表中最大的空闲块的一部分分配给用户。为了节省时间，此时的可利用空间 表的结构应按空闲块的大小自大至小有序。这样，每次分配无需查找，只需从链表中删除 第一个结点，并将其中一部分分配给用户，而剩余部分作为一个新的结点插入到可利用空 间表的适当位置上去。但在回收时，需将释放的空闲块插入到链表的适当位置上去。它适用千请求分配的内存大小范围较窄的系统。

      

8.3 边界标识法

8.3.1 可利用空间表的结构

可以解决系统中内存碎片过多而无法使用的问题。

本身是 双向循环链表，每个内存块结点都有指向前驱和后继结点的指针域。

• space 域 表示为该内存块的大小，它的大小通过 head 域中的 size 值表示。
• head 域中包含有 4 部分：
  • llink 和 rlink 分别表示指向当前内存块结点的直接前驱和直接后继；
  • tag 值用于标记当前内存块的状态，是占用块（用 1 表示）还是空闲块（用 0 表示）；
  • size 用于记录该内存块的存储大小(包括头部 head 和底部 foot 所占空间)。
• foot 域中包含有 2 部分：
  • uplink 是指针域，用于指向内存块本身，通过 uplink 就可以获取该内存块所在内存的首地址；
  • tag 同 head 域中的 tag 相同，都是记录内存块状态的。

typedef struct WORD{  // WORD: 内存字类型
    union{ // head 和 foot 分别是结点的第一个字和最后的字
        struct WORD *llink;    //头部域，指向直接前驱
        struct WORD *uplink;   //底部域，指向结点本身
    };
    int tag;//标记域,0表示为空闲块；1表示为占用块，头部和尾部均有。
    int size;//／头部域，记录内存块的存储大小
    struct WORD *rlink;//／头部域，指向直接后继
    OtherType other;//内存块可能包含的其它的部分
}WORD,head,foot,*Space; //* Space, 可利用空间指针类型

# define FootLoc(p) p+p->size-1 //指向 p 所指结点的底部

/*表中不设表头结点，表头指针 pav 可以指向表中任一结点，即任何一个结点都
可看成是链表中的第一个结点；表头指针为空，则表明可利用空间表为空。 */

8.3.2 分配算法

分配算法：假设我们采用首次拟合法进行分配，则只要从表头指针pav所 指结点起，在可利用空间表中进行查找，找到第一个容量不小于请求分配的存储量(n)的 空闲块时，即可进行分配。

注意：

• 待分配的空闲块的容量为 m个字（包括头部和底部），若每次分配只是从中分配n个字给用户，则需要选定一个适当的常量e, 当m-n≤e时，就将容量为m 的空闲 块整块分配给用户；反之，只分配其中 n个字的内存块。
• 在每次分配之后，令指针 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);
    if (!p || p->size < n) {
        return NULL; // 找不到，返回空指针
    }
    // p 指向找到的空闲块
    else {
        //指针f指向p空闲块的foot域
        f = FootLoc(p);
        // *pav 指向 P 结点的后继结点
        (*pav) = p->rlink;

        //整块分配，不保留 <= e的剩余量
        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;
        }
        // 分配该块的后 n个字
        else {
            //更改分配块foot域的信息
            f->tag = 1; // 修改分配块的底部标志

            p->size -= n; // 置剩余块大小
            f = FootLoc(p);// f指针指向剩余空闲块 p 的底部
            f->tag = 0;   f->uplink = p; // 设置剩余块底部

            p = f + 1; // 指向分配块头部
            p->tag = 1;   p->size = n; // 设置分配块头部
        }
        return p;
    }
}

8.3.3 回收算法

回收算法：当用户释放占用块时，系统需立即回收以备新的请求产生时进行再分配。

• 若释放块的左、右邻区均为占用块，则处理最为简单，只要将此新的空闲块作为一个 结点插入到可利用空闲表中即可；
• 若只有左邻区是空闲块，则应与左邻区合并成一个结点；
• 若只有右邻区是空闲块，则应与右邻区合并成一个结点；
• 若左、右邻区都是空闲块，则 应将 3 块合起来成为一个结点留在可利用空间表中

判断当前空闲块左右两侧是否为空闲块的方法：

• 假设用户释放的内存区的头部地址为P，则与其低地址紧邻的内存区的底部地址为 p-1;

  与其高地址紧邻的内存区的头部地址为 p+p->size；

• 若(p-1)->tag=0;则表明其左邻为空闲块，若(p+p->size)-> tag=0; 则表明其右邻为空闲块。

1️⃣空闲块两侧是占用块

直接插入

//设定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;
}

2️⃣空闲块左侧是空闲块

更改左侧空闲块中的 size 的大小，并重新设置左侧空闲块的 foot 域即可

//常量 n 表示当前空闲块的存储大小
int n=p->size;
Space s=(p-1)->uplink;//p-1 为当前块的左侧块的foot域，foot域中的uplink指向的就是左侧块的首地址，s指针代表的是当前块的左侧存储块
s->size+=n;//设置左侧存储块的存储容量
Space f=p+n-1;//f指针指向的是空闲块 p 的foot域
f->uplink=s;//这是foot域的uplink指针重新指向合并后的存储空间的首地址
f->tag=0;//设置foot域的tag标记为空闲块

3️⃣空闲块右侧是空闲块

将用户释放掉的存储块替换掉右侧的空闲块，同时更改存储块的 size 和右侧空闲块的 uplink 指针的指向

Space t=p+p->size;//t指针指向右侧空闲块的首地址
p->tag=0;//初始化head域的tag值为0
//找到t的前驱结点，用当前释放的空闲块替换右侧空闲块
Space q=t->llink;
p->llink=q; q->rlink=p;
//找到t的后继结点，用当前释放的空闲块替换右侧空闲块
Space q1=t->rlink;
p->rlink=q1; q1->llink=p;
//更新释放块的size的值
p->size+=t->size;
//更改合并后的foot域的uplink指针的指向
Space f=FootLoc(t);
f->uplink=p;

4️⃣空闲块两侧是空闲块

将 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;

8.4 伙伴系统

在伙伴系统中，无论是占用块或空闲块，其大小均为 2的k 次幂(k 为某个正整数）例如；当用户申请n个字的内存区时，分配的占用块大小为 2^k 个字(2^k-1 ＜ n ≤ 2^k)

伙伴系统的优点是算法简单、速度快；缺点是由于只归并伙伴而容易产生碎片。

8.4.1 可利用空间表的结构

将所有大小相同的空闲块建于一张子表中。 每个子表是一个双重链表，双重链表中的结点结构：

​ head 为结点头部，是一个由 4 个域组成的记录，

• ​ llink域和 rlink域分别指向同一链表中的前驱和后继结点；

• ​ tag域为值 取"0""1"的标志域；

• ​ kval 域的值为 2 的幂次 k;

• ​ space 是一个大小为 2k-1 个字的连续内存空间（仍假设 head 占一个字的空间）。

# define m 16
typedef struct WORD_b {
	struct WORD_b* llink; // 指向前驱结点
	int tag;// 块标志，0:空闲，l: 占用。
	int kval;// 块大小，值为 2 的幂次 K
	struct WORD_b* rlink;// 头部域，指向后继结点
	OtherType other; // 字的其他部分
}WORD_b, head; // WORD : 内存字类型，结点的第一个字也称为 head

typedef struct HeadNode {
	int nodesize; // 该链表的空闲块的大小
	WORD_b* first; // 该链表的表头指针
}FreeList[m+1]; // 表头向量类型

8.4.2 分配算法

在分配时经常需要将一个大的空闲块分裂成两个大小相等 的存储区，这两个由同一大块分裂出来的小块就称之“互为伙伴＂

例题：

思路：

初始状态为2¹⁰大小的空闲块

• 为A进程分配150B (2⁷ < 150 ≤ 2⁸ ==> 2^k-1 < 150 ≤ 2^k, k = 8)分区时，首先计算应该分配在哪个k区 k=8
• 接着，在2^k的空闲分区链中查找
  • 找到，将空闲分区分配给进程A
  • 未找到，表示大小为2^k的空闲分区已耗尽，需要在大小为2^k+1的空闲分区链中继续查找。
    • 若存在大小为2^k+1的空闲分区，则将其等分为两个分区，这两个分区称为一对伙伴，其中一个用于分配，另一个加入大小为2^k的空闲分区链。
    • 若不存在大小为2^k+1的空闲分区，则继续查找2^k+2的空闲分区链，
      • 若找到则需要进行两次分割，分割称两个2^k+1的分区，一个2^k+1大小的分区加入到对应的空闲分区链中; 另一个分区继续分割，分割成两个2^k的分区，一个加入对应分区链中，一个分给进程。
      • 若仍然不存在，则继续查找，以此类推

WORD_b* AllocBuddy(FreeList* avail, int n)
{
	//avail[O .. m]为可利用空间表，n 为申请分配量，若有不小于 n 的空闲块，
	int k;
	for (k = 0; k <= m && ((*avail)[k].nodesize < n + 1 || !(*avail)[k].first); k++)
	{
		// 查找满足分配要求的子表
		continue;
	}
	if (k > m) return NULL; // 分配失败，返回 NULL
	else {
		// 进行分配
		WORD_b* pa = (*avail)[k].first; //指向可分配子表的第一个结点
		WORD_b* pre = pa->llink; //指向前驱
		WORD_b* suc = pa->rlink; //指向后继
		if (pa == suc) (*avail)[k].first = NULL; //分配后该子表变成空表
		else { // 从子表删去*pa结点
			/*pre->rlink = suc;
			suc->llink = pre;*/
			(*avail)[k].first = suc;
		}
		int i;
		for (i = 1; (*avail)[k-i].nodesize >= n + 1; ++i)
		{
			WORD_b* pi = pa + (int)pow(2,k-i);
			pi->rlink = pi;
			pi->llink = pi;
			pi->tag = 0;
			pi->kval = k - i;
			(*avail)[k - i].first = pi;
		}// 将剩余块插入相应子表
		pa->tag = 1;
		pa->kval = k - (--i);

		return pa;
	}
}

8.4.3 回收算法

首先判别其伙伴是否为空闲块，

• 若否，则只要将释放的空闲块简单插入在相应子表中即可；
• 若是，则需在相应子表中找到其伙伴并删除之，然后再判 别合并后的空闲块的伙伴是否是空闲块。依此重复，直到归并所得空闲块的伙伴不是空闲块时，再插入到相应的子表中去。

例如，当大小为2⁸，起始地址为 512 的伙伴块的起始地址的计算方式为：
由于 512 取余 2⁹=0，所以，512+ 2⁸=768，即如果该存储块回收时，只需要查看起始地址为 768 的存储块的状态，如果是空闲块则两者合并，反之直接将回收的释放块链接到大小为 2⁸ 的链表中。

8.5 无用单元收集 - 垃圾回收机制

问题描述：

​ 内存在使用完成后没有向系统发出释放的指令，导致存储空间既没有被使用也没有被回收，变为了无用单元或者会产生悬挂访问。

• 无用单元 :是指那些用户不再使用而系统没有回收的结构和变量。

  例如，在C语言中，用户可以通过 malloc 和 free 两个功能函数来动态申请和释放存储空间，当用户使用 malloc 申请的空间使用完成后，没有使用 free 函数进行释放，那么该空间就会成为无用单元。

• 悬挂访问 : 假设使用 malloc 申请了一块存储空间，有 多个指针同时指向这块空间，当其中一个指针完成使命后，私自将该存储空间使用 free 释放掉，导致 其他指针处于悬空状态，如果 释放掉的空间被再分配后，再通过之前的指针访问，就会造成错误，数据结构中称这种访问为悬挂访问。

解决方法：

1. **使用访问计数器：**每个申请的存储空间设置一个计数域，这个计数域 记录的是 指向该存储空间的指针数目，只有当计数域的值为 0 时，该存储空间才会被释放。
2. **收集无用单元（中断回收机制）：**在程序运行时， 所有的存储空间无论是处于使用还是空闲的状态，一律不回收，当系统中的可利用空间表为空时，将程序中断，对当前 不再使用状态的存储空间一律回收，全部链接成一个新的可利用空间表后，程序继续执行。

注意：

​ 实际上，无用单元收集本身都是很 费时间 的，所以无用单元的收集 不适用于实时处理的情况中使用。

➡️ 解决方法2 - 中断回收机制 详细内容

• 中断回收机制步骤：

  • 对所有当前正在使用的 存储空间加上被占用的标记（对于广义表来说，可以在每个结点结构的基础上，添加一个 mark 的标志域。）在初始状态下，所有的存储空间全部标志为 0表示未被占用，被占用时程序标记为 1；
  • 依次遍历所有的存储空间，将所有标记为 0 的存储空间链接成一个新的可利用空间表。

• 步骤一的三种标志算法：

  • 递归算法：加标志的操作实质上是遍历广义表，将广义表中所有结点的标志域赋值"1"。

    • 遍历（加标志）算法的递归定义：
      • 若列表为空，则无需遍历；
      • 若是一个数据元素，则标志元素结点；
      • 反之，则列表非空，首先标志表结点；然后分别遍历表头和表尾。
    • 缺点：需要一个较大的实现 递归用的栈的辅助内存，这部分内存不能用于动态分配。

  • 非递归算法：程序中附设栈（或队列）实现广义表的遍历。

    • 从广义表的存储结构 来看，表中有两种结点：

      • 一种是元素结点，结点中没有指针域；
      • 另一种是表结点，结点中包含两个指针域：表头指针和表尾指针

    • 方法：

      • 深度优先搜索遍历 - 为实现这个遍历需附设一个栈

        ① 当表非空时，在对表结点加标志后，

        ② 先顺表头指针逐层向下对表头加标志，同时将同层非空且未加标志的表尾指针依次入栈，

        ③ 直到表头为空表或为元素结点时停止，然后退栈取出上一层的表尾指针。

        ④ 反复上述进行 过程，直到栈空为止

      • 广度优先搜索遍历（列表按层次遍历）- 为实现这个遍历需附设一个队列

  • 利用表结点本身的指针域标记遍历路径的算法：

    添加三个指针，p 指针指向当前遍历的结点，t 指针永远指向 p 的父结点，q 指向 p 结点的表头或者表尾结点。在遍历过程遵循以下原则：

    1. 当 q 指针指向 p 的表头结点时，可能出现 3 种情况：
       1. p 结点的表头结点只是一个元素结点，没有表头或者表尾: 只需要对该结点打上标记后令 q 指向 p 的表尾
       2. p 结点的表头结点是空表或者是已经做过标记的子表: 只需要直接令 q 指针指向 p 结点的表尾即可
       3. p 结点的表头是未添加标记的子表: 需先遍历表头子表，即p应赋q的值，t相应往下移动改赋p 的值。为了记 下 t指针移动的路径，以便在 p退回原结点时同时能找到 p的母表结点（即使t退回到原来的值），则在修改这个指针的值之前，应先记下 t移动的路径，即令 p所指结点的 hp域 的值为 t,且 tag 域的值为"0"。
    2. 当 q 指针指向 p 的表尾结点时，可能出现 2 种情况：
       1. p 的表尾为未加标志的子表，则需遍历表尾的子表，同样 p、t指针要作相应的移动。为了记下当前表结点的母表 结点，同样要在改动p、t指针的值之前先记下路径；即令 p所指结点的 tp域的值改为 t, 然后令t赋值p,p 赋值 q;
       2. p 的表尾为“空”或是已加上标志的子表，此时表明 p所指的表已加上标志，则 p应退回到其母表结点即 t所指结点，相应地t也应后退一步，即退到 t 结点的母表结点。

    

• 中断回收机制优缺点

  优点：不需要附加存储，使动态分配的 可利用空间得到充分利用，

  缺点：但是由于在算法中，几乎是每个表结点的指针域的值都要作两次改变，因此时间上的开销相当大，而且一旦发生中断，整个系统瘫痪，无法重新启动运行。

8.6 存储紧缩 - 内存碎片化处理

• 堆

  无论是边界标识法还是伙伴系统，都是将空闲的存储空间链接成一个链表，即可利用空间表，对存储空间进行分配和回收。

  另外一种动态内存管理的方法，使用这种方式在整个内存管理过程中，**不管哪个时刻，可利用空间都是一个地址连续的存储区，在编译程序中称之为＂堆 " **，每次分配都是从这个可利用空间中划出一块。

• 分配算法

  在 分配内存空间时，每次都从可利用空间中选择最低（或者最高）的地址进行分配。具体的实现办法为：设置一个指针（称为堆指针），每次用户申请存储空间时，都是堆的最低（或者最高）地址进行分配。假设当用户申请 N 个单位的存储空间时，堆指针向高地址（或者低地址）移动 N 个存储单位，这 N 个存储单位即为分配给用户使用的空闲块，空闲块的起始地址为堆指针移动之前所在的地址。

  

• 回收算法

  由于系统的可利用空间 始终是一个地址连续的存储块，因此回收时必须将所释放的空闲块合并到整个堆上去才 能重新使用，这就是“存储紧缩＂的任务

  做法：

  • 一种是一旦用户释放所占空间就立即进行回收紧缩
  • 另外一种是在程序执行过程中不立即回收用户释放的存储块，而是等到可利用空间不够分配或者堆指针指向了可利用存储区的最高地址时才进行存储紧缩。具体的实现过程是：
    • 计算占用块的新地址。从最低地址始巡查整个存储空间，对每一个占用块找到 它在紧缩后的新地址。为此，需设立两个指针随巡查向前移动，这两个指针分别指示占用 块在紧缩之前和之后的原地址和新地址。因此，在每个占用块的第一个存储单位中，除了 设立长度域（存储该占用块的大小）和标志域（存储区别该存储块是占用块或空闲块的标 志）之外，还需设立一个新地址域，以存储占用块在紧缩后应有的新地址，即建立一张新、 旧地址的对照表。
    • 修改用户的初始变量表，以便在存储紧缩后用户程序能继续正常运行。
    • 检查每个占用块中存储的数据。若有指向其他存储块的指针，则需作相应修改。
    • 将所有占用块迁移到新地址去——传送数据。
    • 将堆指针赋以新值（即紧缩后的空闲存储区的 最低地址）。

• 注意：存储紧缩较之无用单元收集更为复杂，是一个系统的操作，如果不是非不得已不建议使用。

参考：

教材：严蔚敏《数据结构》（C语言版）.pdf

博客：

边界标识法管理动态内存

无用单元收集(垃圾回收机制)

内存紧缩(内存碎片化处理)

视频

10分钟速通伙伴系统算法！