Dynamic Memory Management

Published: by Creative Commons Licence

此文介绍动态存储管理(Dynamic memory management)

动态存储管理的基本问题：系统如何应用户提出的“请求”分配内存？如何回收那些用户不再使用而“释放”的内存，以备新的“请求”产生时重新进行分配？

提出请求的用户可能是进入系统的一个作业，也可能是程序执行过程中的一个动态变量。

在不同的动态存储管理系统中，请求分配的内存量大小不同。通常在编译程序中是一个或几个字，而在系统中则是几千、几万，甚至是几十万。

系统每次分配给用户(不论大小)都是一个地址连续的内存区。

  • 占用块：已分配给用户使用的地址连续的内存区。
  • 空闲块(可利用空间块)：未曾分配的地址连续的内存区。

不论什么样的动态存储管理系统，在刚开工时，整个内存区是一个“空闲块”(在编译程序中称之为“堆”)。

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

  • 在系统运行初期，整个内存区基本上分隔成两大部分：低地址区占若干占用块；高地址区(分配后的剩余部分)是一个“空闲块”
  • 经过一段时间后，有的用户结束运行，它所占用的内存区变为空闲块，这就使得整个内存区呈现出占用块和空闲块犬牙相错的状态。
  • 如下图所示

动态存储分配过程中的内存状态

此时如果有新的用户进入系统请求分配内存，系统的处理策略有二：

  • 一种策略是系统继续从高地址的空闲块中进行分配，而不理会已分配给用户的内存区中是否已空闲，直到分配无法进行(剩余空闲块不能满足分配的请求)时，系统才会去回收所有用户不再使用的空闲块，并且重新组织内存，将所有空闲的内存区连接在一起成为一个大的空闲块；
  • 另一种策略是用户一旦运行结束，便将它所占内存区释放成空闲块，同时，每当新用户请求分配内存时，系统需要巡视整个内存区中所有空闲块，并从中找到一个“合适”的空闲块分配之。(由此，系统需要建立一张记录所有空闲块的可利用空间表，此表的结构可以是“目录表”，也可是“链表”。如下图所示)

动态存储管理中的内存状态和可利用空间表

(可利用空间表的“链表”形式中，表中每一个结点表示一个空闲块，系统每次进行分配或回收即为在可利用空间表中删除或插入一个结点)

可利用空间表及分配方式

利用可利用空间表进行动态存储分配的方法。目录表比较简单，下面仅考虑链表的情况。

可利用空间表中包含所有可分配的空闲块，每一块是链表中的一个结点。当用户请求分配时，系统从可利用空间表中删除一个结点分配之；当用户释放其所占内存时，系统立即回收并将它插入到可利用空间表中。

可利用空间表亦称做“存储池”。

根据系统运行的不同情况，可利用空间表可以由下面3种不同的结构形式：

  1. 系统运行期间所有用户请求分配的存储量大小相同。
  2. 系统运行期间用户请求分配的存储量有若干种大小的规格。
  3. 系统在运行期间分配给用户的内存块大小不固定，随请求而变。

上述3种结构形式的各自详细描述：

  1. 在系统将归它使用的内存区按所需大小分隔成若干个大小相同的块，然后用指针链接成一个可利用空间表。因为表中结点大小相同，则分配时无需查找，只要将第一个结点分配给用户；当用户释放内存时，系统只要将用户释放的空闲块直接插入在表头(为什么插入在表头？个人理解：表头指针总是已知的，此种做法不仅可以减少一个指针变量，也可以减少时间复杂度——遍历是需要时间的)。由上述可见，此时的可利用空间表实质上是一个链栈。这是一种最简单的动态存储管理方式。
  2. 一般情况下，是建立若干个可利用空间表，同一链表中的结点大小相同【每个结点中的第一个字设有链域、标志域和结点类型域】。此时的分配和回收的方法在很大程度上和第一种情况类似，只是当结点大小和请求分配的量相同的链表为空时，需查询结点较大的点，并从中取出一个结点，将其中一部分内存分配给用户，而将剩余部分插入到相应大小的链表中(比如说要找一个大小为4的，但是4的没了，只有16的，那么如此操作：将16分为4，4，8，将一个4分配给用户，剩下的一个4和一个8插入到相应大小的链表中)。这种情况的系统还有一个特殊的问题要处理：当结点与请求相符的链表和结点更大的链表均为空时，分配不能进行，而实际上内存空间不一定不存在所需大小的空间，只是由于在系统运行过程中，频繁出现小块的分配和回收，使得大结点链表中的空闲块被分割成小块后插入在小结点的链表中，此时若要使系统继续运行，就必须重新组织内存，即执行存储紧缩的操作。
  3. 分配给用户的内存块大小不固定，那么，可利用空间表中的结点即空闲块的大小也是随意的。通常，操作系统中的可利用空间表属于这种类型。这种类型的结构形式将在后面更加详细的叙述。

这里先给一个第二种类型(存储量有若干种大小规格)的可利用空间表的例子：

有3种大小结点的可利用空间表

下面开始详细的介绍可利用空间表的第三种类型：

系统刚开始工作的时候，整个内存空间是一个空闲块(可利用空间表只有一个大小为整个内存区的结点)，随着分配和回收的进行，可利用空间表中的结点大小和个数也随之改变。(在图【动态存储管理中的内存状态和可利用空间表】中的链表即为这种情况的可利用空间表)

由于链表中结点大小不同，结点的结构也与前面两种情况的结构不一样，结点中除了标志域和链域之外，还需要一个结点大小域(size)，作用是指示空间块的存储量，如下图所示。

空闲块的大小随意的结点结构

【说明】结点中的space域是一个地址连续的内存空间。

由于可利用空间表中的结点大小不同，在分配时就有一个如何分配的问题。(如果用户需要n的内存，而可利用空间表种只有一块m>=n的空闲块，我们只需要将其中大小为n的部分分配给申请分配的用户，剩下的m-n作为一个结点留在链表中，但是如果有若干个不小于n的空闲块呢？这就需要接下来的三种不同分配策略了。) -> 关于如何分配，也有3种不同的分配策略：

  1. 首次拟合法
  2. 最佳拟合法
  3. 最差拟合法

下面是三种方法的详细介绍(图在下面)：

  1. 首次拟合法。从表头指针开始查找可利用空间表，将找到的第一个大小不小于n的空闲块的一部分分配给用户。可利用空间表本身不按结点的初始地址有序，也不按结点的大小有序，回收时，同样只需将释放的空闲块插入在链表表头即可。
  2. 最佳拟合法。将可利用空间中一个不小于n且最接近n的空闲块的一部分分配给用户。(这样子就需要系统再分配前对可利用空间表从头到尾扫视一遍，然后从中找出一块不小于n且最接近n的空闲块进行分配)。通常，预先设定可利用空间表的结构按空间块的大小自小到大有序(由此，只要找到第一块大于n的空闲块即可进行分配，但是相应的在回收时，需要将释放的空闲块插入到合适的位置上去)。
  3. 最差拟合法。将可利用空间表中不小于n且是链表中最大空闲块的一部分分配给用户。为了节省时间，可利用空间表的结构应按空闲块的大小自大至小有序。这样子，每次分配无需查找，只需要从链表中删除第一个结点，并将其一部分分配给用户，而剩余部分作为一个新的结点插入到可利用空间表的适当位置上。自然，回收的时候也需要将释放的空闲块插入到链表的适当位置上去。

结点大小随意的可利用空间表

三种不同分配策略的比较：

比较一：

  • 最佳拟合法适用于请求分配的内存大小范围较广的系统(按最佳拟合的原则进行分配时，总是找大小最接近请求的空闲块，所以系统中会产生一些存储量甚小而无法利用的小片内存，同时也会保留那些很大的内存块以备响应后面将发生的内存量特大的请求，从而使整个链表趋向于结点大小差别甚远的状态)。
  • 最差拟合法适用于请求分配的内存大小范围较窄的系统(每次从内存量最大的结点中进行分配，从而使链表中的结点大小趋于均匀)。
  • 首次拟合法适用于系统事先不掌握运行期间可能出现的请求分配和释放的信息的情况。

比较二(从时间上来比较)：

  • 首次拟合法。在分配时需查询可利用空间表，而回收时仅需插入在表头。
  • 最差拟合法。分配时无需查询链表，而回收时将新的“空闲块”插入到链表中的适当位置上，需要进行查找。
  • 最佳拟合法。无论是分配还是回收，都需要查找链表(为了找到最适合的位置)，因此在三种方法中最费时间。

不同的情形需要采用不同的方法，选择时需要考虑的因素：

  1. 用户的逻辑要求；
  2. 请求分配量的大小分布；
  3. 分配和释放的频率；
  4. 效率对系统的重要性；
  5. …

【结点合并】(这是一个在实际使用的系统中回收空闲块时需要考虑的一个问题)：在回收空闲块时，需要检查地址与它相邻的内存是否是空闲块。(具体实现方法，看后文的【边界标志法】以及【伙伴系统】)

利用可利用空间表进行动态存储管理的特点

在用户请求存储时进行分配，在用户释放存储时进行回收，即系统是应用户的需求来进行存储分配和回收的。

因此，在这类存储管理系统中，用户必须明确给出“请求”和“释放”的信息(在使用C语言时，用户通过malloc和free来请求分配和释放存储的；在多用户分时并发的操作系统中，用户程序进入系统中时即请求分配存储区，用户程序执行完毕退出系统时即释放所占存储)。但有时会因为用户的疏漏或者结构本身的问题致使系统在不恰当的时候或没有进行回收而产生“无用单元”或“悬挂访问”的问题。这就是我们下一节要了解的内容。

无用单元收集

无用单元和悬挂访问

无用单元：用户不再使用而系统没有回收的结构和变量

p = malloc(size);
 .
 .
 .
p = NULL;

该C程序段执行的结果，会使执行p=malloc(size)为用户分配的结点成为无用单元，无法得到利用。

悬挂访问：

p = malloc(size);
 .
 .
 .
q = p;
free(p);

该程序段的执行结果使指针变量q悬空，如果所释放那个的结点再被分配而继续访问指针q所指的结点，则称这种访问为悬挂访问。

结构本身的问题同样会导致上述问题的情况

含有共享子表的广义表

在上图中我们可以得到的信息：某用户程序中有三个广义表结构，L1、L2和L3分别为他们的表头指针，L4是L1和L2共享的子表，L3本身又为L2共享，则L5为3个广义表所共享。

在这种情况下，表结点的释放就成为一个问题。假设表L1不再使用，而L2和L3尚在使用。若释放表L1(自L1指针起，顺链将所有结点回收到可利用空间表中，包括子表L4和L5上的所有结点)，这就破坏了表L2和L3，从而产生悬挂访问；反之，若不将L1中结点释放，则当L2和L3两个表也不被使用时，这些结点由于未曾释放无法再被分配而称为无用单元。

我们后面主要考虑由结构本身问题导致的无用单元和悬挂访问(因为前者的解决较简单)，而且你可以含有共享子表的广义表或者链表来理解后述内容。

解决方法

  • 方法一：使用访问计数器。在所有的子表或广义表上增加一个表头结点，并设立一个“计数域”，它的值为指向该子表或广义表的指针数目(只有当该计数域的值为零的时候，此子表或广义表中结点才会被释放)。
  • 方法二：收集无用单元。在程序运行过程中，对所有的链表结点，不管它有没有用，都不回收，直到整个可利用空间表为空。此时才暂停执行程序，将所有当前不被使用的结点链接在一起，成为一个新的可利用空间表，而后程序再继续执行。(一般情况下，辨别哪些结点当前未被使用是困难的，但是哪些结点正在使用是容易查明的，这只要从所有当前正在工作的指针变量出发，顺链遍历，那么，所有链接在这些链上的结点都是占用的，而可利用存储空间中的其他结点就是无用的了)

收集无用单元

用上文所述，收集无用单元应该分为两步：

  1. 对所有占用结点加上标志。在每个结点上加设一个标志(remark)域，假设在无用单元收集之前所有结点的标志域均为0，则加上标志就是将结点的标志域置为1.
  2. 对整个可利用存储空间顺序扫描以一遍，将所有标志域为0的结点链接成一个新的可利用空间表。

【注意】步骤二是容易进行的，而步骤一是在极其困难的条件(即可利用存储几乎耗用殆尽)下进行的，因此，人们的精力主要集中在研究标志算法上。下面介绍3种标志算法。

标志算法

标志算法有三：

  1. 递归算法
  2. 非递归算法
  3. 利用表结点本身的指针域标记遍历路径的方法

递归算法：

加标志的操作实际上是遍历广义表(将广义表中所有结点的标志域赋值为"1")。

下面是遍历(加标志)算法的递归定义：

  1. 若列表为空，则无需遍历；
  2. 若是一个数据元素，则标志元素结点；
  3. 反之，则列表非空，首先标志表结点，然后分别遍历表头和表尾。

【优缺点】此算法需要一个较大的实现递归栈的辅助内存，这部分内存不能用于动态分配。并且，由于列表层次的不定，使得栈的容量不易确定，除非是在内存区中开辟一个相当大的区域留作栈，否则就有可能由于在标志过程中因为栈溢出而导致系统瘫痪。

非递归算法：

程序中附设栈(或队列)实现广义表的遍历。因为广义表的存储结构很类似于二叉树的二叉链表(广义表的存储结构中，有两种结点：一种是元素结点，结点中没有指针域；另一种是表结点，结点中包含两个指针域，表头指针和表尾指针)，于是可以写出类似遍历二叉树写出遍历表的非递归算法。

可以类似于二叉树的前序遍历(dfs)，也可以类似于二叉树的层序遍历(bfs).\

【优缺点】尽管附设的栈或队列的容量比递归算法中的栈的容量要小很多，但是和递归算法一样需要一个不确定量的附加存储，因此也不是理想的方法。

利用表结点本身的指针域标记遍历路径(详细)

和之前算法的比较：利用已经标志过的表结点中的tag、hp和tp域来代替栈记录遍历过程中的路径。

算法中设3个互相关联的指针：当p指向某个表结点时；t指向p的母表结点；q指向p的表头或表尾。

当q指向p的表头结点时，可能有3种情况出现：

  1. 设p的表头只是一个元素结点，则遍历表头仅需对该表头结点打上标志后，令q指向p的表尾；
  2. 设p的表头为空表或是已加上标志的子表，则无需遍历表头，只要令q指向p的表尾；
  3. 设p的表头为未加标志的子表，则需先遍历表头子表(p=q)，t相应的往下移动修改为p的值(t=p)。

为了记下t指针移动的路径，以便在p退回原结点时同时能找到p的母表结点(t退回到原来的值)，则在修改这个指针的值之前，应先记下t移动的路径(令p所指结点的hp域的值为t，且tag域的值为"0")。

当q指向p的表尾时，可能有2种情况：

  1. p的表尾为未加标志的子表，则需遍历表尾的子表，同样p、t指针要作相应的移动。为了记录下当前表结点的母表结点，同样要在改动p、t指针之前先记下路径(即令p所指结点的tp域的值改为t)，然后令t赋值p(t=p)，p赋值q(p=q)；
  2. p的表尾为空或是已加上标志的子表，此时表明p所指的表已加上标志，则p应退回到其目标结点即t所指结点，相应地t也后退一步，即退到t结点的母表结点.

综上，可见，t的移动路径已记录在t结点的hp域或者tp域中，然而究竟是哪一个勒？ 我们需要辨别tag的值来定。它不仅只是t应按哪个指针所指路径退回，而且指示了下一步应做什么。

  1. 若t结点是其母表表头，则应继续遍历其母表的表尾；
  2. 若t结点是其母表表尾，则应继续找更高一层的母表结点。

三种标志算法优劣

  • 第三种算法不需要附加存储，使动态分配的可利用空间得到充分利用，但是由于在算法中，几乎每个表结点的指针域的值都要作两次改变，因此时间开销相当大，而且一旦中断，整个系统瘫痪，无法重新启动运行。
  • 非递归算法操作简单，但时间上要比第三种算法省的多，然而它需要占有一定空间，是动态分配所使用的存储量减少。

总之，无用单元收集是很费时间的，不能在实时处理的情况下应用。

定量估计

通常，无用单元的收集工作是由编译程序中的专用系统来完成，也可以作为一个标准函数由用户自行调用(类似free()的使用)。不管是上述两者中的哪一种情况，系统都要求用户建立一个初始变量表登陆用户程序中所有链表的表头指针，以便从这些指针出发进行标志。

定量估计是对无用单元收集算法的定量估计。

整个算法分为两步(从上文可以看出)：

  1. 步骤一：对占用结点加标志。假设总的占用数为N，则标志过程中需要的时间为c1N，其中c1为某个常数。
  2. 步骤二：从可用空间的第一个结点起，顺序扫描，将所有未标志的结点链接在一起。假设可用空间总共含有M个结点，则所需时间为c2M，其中c2为某个常数。

收集算法的总时间为c1N+c2M，收集到的无用单元的个数为M-N.

无用单元收集的收集效率：收集效率 <- 此为收集一个无用单元所需的平均时间

如果用内存使用密度内存使用密度带入效率公式之中，则式子化为：带入rho之后的效率公式

举个例子：如果内存中3/4的结点为无用结点，即内存使用密度为1/4，那么收集一个结点所需平均时间为例子的公式

从上面的式子中我们可以发现，可利用内存区中只有少量的结点为无用结点时，收集无用单元操作的效率很低。-> 【无用结点所占比例越少，收集无用单元操作效率越低】

不仅如此，当系统再次恢复运行时，这些结点又会很快被消耗，导致另一次无用单元的收集，如此辖区造成恶性循环，致使最后整个系统瘫痪。

【解决方法】由系统实现确定一个常数k，当收集到的无用单元数为k或者更少时系统就不再运行。

存储紧缩

上面介绍的动态存储管理方法都有一个共同的特点(建立一个空闲块或者无用结点组成的可利用空间表，可利用空间表采用链表结构，其结点大小随意(可同可不同))，下面介绍另一种结构的动态存储管理方法——堆存储管理。

在整个动态存储管理过程中，不论何时，可利用空间都是一个地址连续的存储区，在编译程序中称之为“堆”，每次分配都是从这个可利用空间中划出一块。

【实现方法】设立一个指针(称之为堆指针)，始终指向堆的最低(最高)地址。当用户申请N个单位的存储块时，堆指针向高地址(或低地址)移动N个存储单位，而移动之前的堆指针的值就是分配给用户的占用块的初始地址。

分配和回收(存储紧缩)

分配算法非常简单，而回收空闲块就比较麻烦一些。下面介绍如何回收。

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

紧缩存储的通常做法有二：

  1. 一旦有用户释放存储块就立即进行回收；
  2. 在程序执行过程中不回收用户随时释放的存储块，直到可利用空间不够分配或堆指针指向最高地址时，才进行存储紧缩。

下面是两种情况的图示：

堆存储管理示意图 紧缩前后的堆

在存储紧缩之前，我们要对占用块进行标志，标志的算法和前文中的标志算法类似(只是存储块的结构可能不同)；其次需要进行下面四个步骤的操作：

  1. 计算占用块的新地址。从最低地址开始巡查整个存储空间，对每一个占用块找到它在紧缩后的新地址(操作方法：设立两个指针随巡查向前移动，这两个指针分别指示占用块在紧缩之前和紧缩之后的原地址和新地址)。在每个占用块的第一个存储单位中，除了设立长度域(存储该占用块的长度)和标志域(存储区别该存储块时占用块或空闲块的标志)之外，还需要设立一个新地址域(存储占用块在紧缩后应有的新地址)，即建立一张新、旧地址的对照表。
  2. 修改用户的初始变量表(见“无用单元收集->定量估计”)。目的：在存储紧缩后用户能继续正常工作。
  3. 检查每个占用块中存储的数据。若有指向其他存储块的指针，则需相应修改。
  4. 将所有占用块迁移到新地址上。传送数据。

如此，我们就完成了存储紧缩的操作。不过，在最后我们还需要将堆指针赋以新的值(即紧缩后的空闲存储区的最低地址)。

(可见，存储紧缩法比无用块收集法更加复杂，前者不仅要传送数据(占用块迁移)，而且要修改所有占用块中的指针。因此，存储紧缩也是一个系统操作，但是能不用就不用。)