对应于书中的9.9。

  • 虚拟页的存在是作为虚拟内存和物理内存传输数据块的单位，是由一系列连续的虚拟内存地址组成的，并且这些虚拟地址的特点由虚拟页定义。而虚拟内存段是将一系列大量的连续的具有相似特点的虚拟地址聚集起来，且虚拟内存段也描述了这些虚拟地址的一些特点，并且这些虚拟地址以虚拟页为单位进行组织，即虚拟内存段包含虚拟页。
    我们使用虚拟内存时是以虚拟地址为单位的，只是根据我们对其使用方式的不同要求和权限，会处于不同虚拟段中的不同虚拟页中。
  • 当调用malloc函数来分配块时，首先会在空闲链表中寻找是否有合适的空闲块，如果尝试了合并空闲块还是没找到，则会调用sbrk函数来向内核申请更大的堆内存。所以在一开始将堆与匿名文件映射时，堆内存为0，则第一次调用malloc函数时，会直接调用sbrk函数来申请得到一块大的空闲块，该空闲块可能会比你尝试分配的块大，然后就一直在这个堆中进行操作。
  • 堆的起始地址到brk之间是已申请的堆内存，可以在里面进行动态内存分配，而brk之外的是未申请的堆内存，只有当找不到合适的空闲块时，才会向内核申请更大的可用空间，此时就会移动brk。

除了上一章介绍的通过mmap函数能让用户自定义内存映射，将磁盘文件映射到虚拟内存中以外，也可以在运行时使用动态内存分配器（Dynamic Memory Allocator）来分配额外的虚拟内存。动态内存分配器维护着虚拟内存中的堆段，将堆视为一组不同大小的块的集合，每个块由若干个连续的虚拟地址构成（一个块不一定处在同一个虚拟页），每个块具有两种状态：

  • 已分配：已分配的块能为应用程序所用，且块会保持已分配状态直到被释放
  • 空闲的：空闲的块无法使用，直到它被分配
img

而在最开始进行内存映射时，堆是与匿名文件关联起来的，所以堆是一个全0的段，即处于空闲状态，它紧跟在未初始的数据段后面，向地址更大的方向延伸，且内核对每个进程都维护了brk变量来指向堆顶。

动态内存分配器具有两种类型，都要求由应用程序显示分配块，但是由不同实体来负责释放已分配的块：

  • 显示分配器（Explicit Allocator）：要求应用程序显示释放已分配的块。比如C中通过malloc来分配块，再通过free来显示释放已分配的块，C++中的new和delete相同。
  • 隐式分配器（Implicit Allocator）：由分配器检测哪些块已不被应用程序使用，就自动释放这些块。这种隐式分配器称为垃圾收集器（Garbage Collector），而这种过程称为垃圾收集（Garbage Collection）。比如Java、ML和Lisp。

程序使用动态内存分配器来动态分配内存的意义在于：有些数据结构只有在程序运行时才知道大小。通过这种方式就无需通过硬编码方式来指定数组大小，而是根据需要动态分配内存。

1
2
3
4
5
6
7
8
9
10
11
12
#include <stdio.h>
#include <stdlib.h>
int main(){
  int *array, i, n;
  scanf("%d", &n);
  array = (int *)malloc(n*sizeof(int));
  for(i=0; i<n; i++){
    scanf("%d", &array[i]);
  }
  free(array);
  exit(0);
}

这一章主要介绍管理堆内存的显示分配器。

malloc和free函数

C中提供了malloc显示分配器，程序可以通过malloc函数来显示地从堆中分配块

1
2
#include <stdlib.h>
void *malloc(size_t size);

该函数会返回一个指向大小至少为size字节的未初始化内存块的指针，且根据程序的编译时选择的字长，来确定内存地址对齐的位数，比如-m32表示32位模式，地址与8对齐，-m64表示64位模式，地址与16对齐。如果函数出现错误，则返回NULL，并设置errno。我们也可以使用calloc函数来将分配的内存块初始化为0，也可以使用realloc函数来改变已分配块的大小。

程序可以通过free函数来释放已分配的堆块

1
2
#include <stdlib.h>
void free(void *ptr);

其中ptr参数要指向通过malloc、calloc或realloc函数获得的堆内存。

动态内存分配器可以使用mmap和munmap函数，也可以使用sbrk函数来向内核申请堆内存空间，只有先申请获得堆内存空间后，才能尝试对块进行分配让应用程序使用。

1
2
3
4
#include <unistd.h>
void *sbrk(intptr_t incr); 
int brk(void *addr);
`brk`函数会将`brk`设置为`addr`指定的值。`sbrk`函数通过`incr`来增加`brk`
  • 当incr小于0时，会减小brk来解除已分配的堆内存
  • 当incr等于0时，会返回当前的brk值
  • 当incr大于0时，会增加brk来分配更多的堆内存

当sbrk函数运行正常时，会返回之前的brk值，否则会返回-1并设置errno为ENOMEM。

当我们使用malloc函数申请较小的堆内存时，会通过brk或sbrk函数设置brk来实现。brk和sbrk函数分配的堆内存类似于缓冲池，每次malloc从缓冲池获得内存时，如果缓冲池大小不够，就会调用brk或sbrk函数来扩充缓冲池，然后从该缓冲池中获得对应的内存，而free函数就会将应用程序使用的内存空间归还缓冲池。

通过sbrk和brk函数来针对小块内存的申请，会产生内存碎片问题。对于大块内存的申请，会直接使用mmap函数，直接将大段的虚拟地址空间与匿名文件关联起来，就不会有内存碎片问题。

在本章节中，以字为单位进行操作，每个字为4字节，并进行双字对齐（下图中，一格代表一字）。

img

注意：

  • 分配堆内存时，会进行地址对齐
  • 释放内存后，其指针不会被删除，所以要谨慎被删除的指针的使用

显示分配器的要求和目标

显示分配器的要求有：

  • 只要满足每个释放请求都对应于一个由以前分配请求获得的已分配的块，则应用程序可以以任意顺序发送分配请求和释放请求。
  • 分配器必须立即响应请求，不允许对请求进行重排列或缓存。
  • 为了使分配器是可扩展的，分配器使用的任何非标量数据结构都必须保存在堆内。
  • 为了能保存任意类型的数据对象，分配必须对齐块。（比如讲解struct时，它根据对齐要求对起始虚拟地址是有要求的）
  • 当块被分配了，分配器不允许对其进行修改或移动，因为已分配块属于应用程序了。

显示分配器的目标为：吞吐率最大化和内存使用率最大化

  • 吞吐率是指每个单位时间内完成的请求数。一个分配请求的最差运行时间与空闲块的数量成线性关系（要一次搜索每个空闲块来确定是否适合），而一个释放请求的运行时间是常数，则我们可以通过最小化分配请求和释放请求的平均运行时间来最大化吞吐率，主要约束项在分配请求。

  • 一个系统中所有进程分配的虚拟内存的全部数量是受磁盘上的交换空间限制的，所以要尽可能最大化内存使用率。首先，我们给定n个分配请求和释放请求的序列 $R_0,R_1,…,R_k,…,R_{n-1}$ ，然后定义以下概念：

    • 有效载荷（Payload）：应用程序请求一个p字节的块，则该已分配的块的有效载荷为p字节。（分配器为了对齐要求和块的格式，可能会申请比p更大的块）
    • 聚集有效载荷（Aggregate Payload）P：当前已分配的块的有效载荷之和
    • 然后我们可以通过brk变量来确定堆当前的大小 $H_k$ （假设是单调不递减的）
      由此我们可以确定前k+1个请求的峰值利用率（Peak Utilization）$U_k = \frac{max_{i \leq k}P_i}{H_k}$ 。通过峰值利用率就能确定分配器使用堆的效率，并且对于任意的分配和释放序列，最大的 $P_i$ 是相同的。在理想状态下，每个块的内容都是有效载荷，所以利用率为1。

造成堆内存使用效率低下的主要原因是碎片（Fragmentation）现象，当空闲的内存不能满足分配请求时就会产生碎片，主要分为两种：

  • 内部碎片（Internal Fragmentation）：当已分配的块比有效载荷大时，就会产生内部碎片。比如分配器为了满足对齐要求或保存块的数据结构，就会对分配块增加额外的内存空间。我们可以通过已分配块的大小与其有效载荷的差来量化内部碎片，则内部碎片的数量主要取决于之前请求的模式和分配器的实现方法。
img
  • 外部碎片（External Fragmentation）：当空闲的内存合起来够满足一个分配请求，但单独一个空闲内存不够时，就会产生外部碎片。外部碎片比较难进行量化，因为它主要取决于未来请求的模式，所以分配器通常试图维持少量的大的空闲块。
img

为了让分配器能平衡吞吐率和利用率，需要考虑以下几个问题：

  • 如何记录堆中空闲的块？
  • 如何选择一个合适的空闲块来放置一个新分配的块？
  • 再将一个新分配的块放置在某个空闲块后，如何处理空闲块中剩余部分？
  • 如何处理一个刚刚被释放的块？
  • 当我们对一个指针调用free时，怎么知道要释放多少内存？

隐式空闲链表

对于堆内存中的块，我们可以将其定义为以下数据结构形式

img

则每个块由三部分构成：

  • 头部：大小为一个字（一个字为4字节），可以用来保存块大小，如果我们添加一个双字的对齐要求，则块大小就总是8的倍数，则头部中表示块大小的低3位就总是0，我们可以拿这3位来表示该块是否被分配。（则一个块最大只能是 $2^{29}-1$字节)
  • 有效载荷：应用通过malloc请求的有效载荷
  • 填充：可选的，分配器可用来处理外部碎片，或满足对齐要求。

我们通过块的这种数据结构来组织堆内存，则通过块头部的块大小来将堆中的所有块链接起来。分配器可以通过遍历所有块，然后通过块头部的字段来判断该块是否空闲的，来间接遍历整个空闲块集合。我们可以通过一个大小为0的已分配块来作为终止头部（Terminating Header），来表示结束块。

img

头部标记为（大小（字节）/已分配位）

注意：计算块大小时，要先将有效载荷加上块头部大小，然后再计算满足对齐要求时的块大小。

由于地址对齐要求和分配器对块格式的选择，会对最小块的大小有限制，没有已分配的块和空闲块比最小块还小，如果比最小块还小，就会变成外部碎片（所以最小块越大，内部碎片程度越高）。比如这里如果对齐要求是双字8字节的，则最小块大小为双字：第一个字用来保存头部，另一个字用来满足对齐要求。

选择空闲块

当应用请求一个k字节的空闲块时，分配器会搜索空闲链表，并根据不同的放置策略（Placement Policy）来确定使用的空闲块：

  • 首次适配（First Fit）：分配器从头开始搜索空闲链表，选择第一个块大小大于k的空闲块。

    • 优点：趋向于将大的空闲块保留在空闲链表后面。
    • 缺点：空闲链表开始部分会包含很多碎片
img

  • 下一次适配（Next Fit）：分配器从上一次查询结束的地方开始进行搜索，选择第一个块大小大于k的空闲块。

    • 优点：运行比首次适配块一些，可以跳过开头的碎片
    • 缺点：内存利用率比首次适配低很多

  • 最佳适配（Best Fit）：分配器会查找所有空闲块，选择块大小大于k的最小空闲块。

    • 优点：内存利用率比前两者都高一些
    • 缺点：需要遍历完整的空闲链表

如果分配器可以找到满足要求的空闲块，则需要确定如何使用这个空闲块：

  • 如果空闲块与k大小相近，则可以直接使用这一整个空闲块
  • 如果空闲块比k大很多，如果直接使用整个空闲块，则会造成很大的内部碎片，所以会尝试对该空闲块进行分割，一部分用来保存k字节数据，另一部分构成新的空闲块。
img

如果分配器找不到满足要求的空闲块，则会首先尝试将物理上相邻的两个空闲块合并起来创建一个更大的空闲块，如果还是不满足要求，则分配器会调用sbrk函数来向内核申请额外的堆内存，然后将申请到的新空间当做是一个空闲块。

合并空闲块

当我们尝试释放分配块时，如果当前块与其他空闲块相邻，则会产生假碎片（Fault Fragmentation）现象，即许多可用的空闲块被分割为小的无法使用的空闲块，此时分配器就可以合并相邻空闲块来解决假碎片问题，具有以下策略：

  • 立即合并（Immediate Coalescing）：当我们释放一个分配块时，就合并与其相邻的空闲块。

    • 优点：可在常数时间内完成
    • 缺点：可能一个空闲块会被来回分割和合并，产生抖动

  • 推迟合并（Deferred Coalescing）：当找不到合适的空闲块时，再扫描整个堆来合并所有空闲块。

img

为了高效合并前一个空闲块，需要使用边界标记（Boundary Tag）技术，使得当前块能迅速判断前一个块是否为空闲的

img

在块的数据结构中，会添加一个块头部的副本到脚部。这样当前块从起始位置向前偏移一个字长度，就能得到前一个块的脚部，通过脚部就能判断前一个快是否为空闲的，并且也能得到前一个块的大小。且当前块通过自己头部的块大小就能得到下一个块的头部，由此来判断下一个块是否空闲，以及下一个块的大小。

img

可以将所有情况分成以下几种：

img
  • 前一块和后一块都是分配的：此时不会发生合并操作。
  • 前一块是已分配的，后一块是空闲的：当前块会将头部中的块大小设置为当前快的大小和下一块大小之和，并且修改下一块的脚部。
  • 前一块是空闲的，下一块是已分配的：前一块会将头部中的块大小设置为自己的块大小和当前块大小之和，并且修改当前块的脚部。
  • 前一块和当前快都是空闲的：前一块会将头部中的块大小设置为这三个块的大小之和，并修改下一块的脚部。

该技术的缺点是会显著增加内存开销，由于引入了脚部，使得有效载荷大小变小，而使得内部碎片变多了，并且最小块的大小变大导致外部碎片也变多了。

我们可以对其进行优化，有些情况是不需要边界标记的，只有在合并时才需要脚部，而我们只会在空闲块上进行合并，所以在已分配的块上可以不需要脚部，那空闲块如何判断前一个块是否为已分配的呢？可以在自己的头部的3个位中用一个位来标记前一个块是否为空闲的，如果前一个块为已分配的，则无需关心前一个块的大小，因为不会进行合并；如果前一个块为空闲的，则前一个块自己就有脚部，说明了前一个块的大小，则可以顺利进行合并操作。

通过合并操作，空闲块的两侧一定都是已分配的块。

隐式空闲链表的特点总结：

img

显示空闲链表

由于隐式空闲列表的块分配耗费时间与堆块的总数呈线性关系，其对于通用的分配器是不适合的。

一种更好的方法是将空闲块组织成某种形式的显示数据结构。因为空闲块中除了头部和脚部以外都是没有被使用的，所以可以在空闲块中的其余部分引入其他信息，这里引入了一个指向前一个空闲块的pred指针，还有一个指向下一个空闲块的succ指针，由此就将空闲块组织成双向链表形式。 但是这种方法需要更大的空闲最小块，否则不够存放两个指针，这就提高了外部碎片的程度。

img

对于已分配块，可以通过头部和脚部来得到地址相邻两个块的信息，而对于空闲块，可以通过头部和脚部来得到地址相邻两个块，也可以通过两个指针直接获得相邻的两个空闲块。注意：逻辑上看这两个空闲块是相邻的，但物理地址上不一定是相邻的，如下图所示。

img

分配器使用这种形式的块结构，可以将首次适配时间从块总数的线性时间降低为空闲块总数的线性时间（因为要依次遍历检索到满足要求的空闲块）。比如我们这里存在以下3个空闲块的双向链表，此时想要分配中间的空闲块，且对其进行分割

img

此时就会获得以下形式，因为已分配块可以根据指针来定位，所以不需要额外进行链接。而空闲块会从中分割出合适的部分用于分配，其余部分作为新的空闲块，此时只要更新对应的指针就行。

img

而当我们想要释放已分配块时，它并不在空闲链表中，要将其放在空闲链表什么位置？我们对空闲链表的维护会影响释放已分配块的时间：

  • 后进先出（LIFO）策略：将释放的已分配块放到空闲链表开始的地方，则只需要常数时间就能释放一个块。如果使用后进先出和首次适配策略，则分配器会先检索最近使用过的块。但是碎片化会比地址顺序策略严重。
  • 地址顺序策略：释放一个块需要遍历空闲链表，保证链表中每个空闲块的地址都小于它后继的地址。这种策略的首次适配会比后进先出的首次适配有更高的内存利用率。

接下来以LIFO策略为例，说明在四种情况下如何进行空闲块合并：

img
情况一：要释放的块前后都为已分配的块

我们可以通过后面块的头部以及前面块的脚部来得知相邻两个块的已分配状况（这就是保留头部和脚部的意义）。由于相邻的都是已分配的块，所以不会进行空闲块合并，直接更新Root的succ指针使其指向要释放的块，而让要释放的块的pred指向Root，succ指向原来第一个空闲块，然后更新原来的第一个空闲块的pred指针。

img
情况一解决方案
img
情况二：要释放的块后面为空闲块，前面为已分配的块

要释放的块后面为空闲块，则需要将当前块和后一块进行合并。我们可以简单地修改头部和脚部直接将两个空闲块合并，但是后一块为空闲块，会处于空闲链表的某个位置，所以要修改后一块的前后两个空闲块的指针，使其跳过后一块。然后修改对应指针就行。

img
情况二的解决方案
img
情况三：要释放的块前面为空闲块，后面为已分配的块

和情况二类似。如果不是LIFO策略，其实可以直接保留前一个块的指针。

img
情况三的解决方案
img
情况四：当前块的前后两个块都为空闲块

情况四其实就是情况二和三的合并。对于前后两个空闲块，直接让其指针前后的两个空闲块修改指针跳过，然后修改头部和脚部进行合并

img
情况四的解决方案

显示链表特点总结：

img

分离的空闲链表

为了减少分配时间，可以使用分离存储（Segregrated Storage）方法，首先将所有空闲块根据块大小分成不同类别，称为大小类（Size Class），比如可以根据2幂次分成

img

这样不同空闲块就落在不同的大小类中，然后对于每个大小类都生成自己独立的空闲链表，然后分配器根据大小类的大小，将对应的空闲链表按照升序保存在数组中。由此能极大加快分配速度。

img

当我们想要分配一个大小为n的块时，会首先根据空闲链表数组确定对应的大小类，找到合适的空闲链表，搜索是否有合适的空闲块，如果有，可以对其进行分割，则剩下的部分要放到合适合适的空闲链表中，如果没有合适的空闲块，则会找下一个更大的大小类，重复上述步骤。

如果遍历了所有大小类的空闲链表还是找不到合适的空闲块时，分配器就会向内核申请更大的堆内存空间，然后将作为一个空闲块放在最大的大小类的空闲链表中。

当我们想要释放一个块时，需要对其地址周围的空闲块进行合并，然后将其放在合适的大小类中。

分离的空闲链表是当前最好的分配器类型，对于吞吐量方面，由于将原来巨大的空闲链表根据大小类将其划分为很多小的空闲链表，使得在单一空闲链表中搜索速度快很多，对于内存利用率方面，由于大小类的存在，使得你正在搜索的空闲链表是最适合你想要分配的大小，在这里使用首次适配策略就能得到接近在整个空闲链表中使用最佳适配策略的性能。最极端的情况是为每个块都设置一个大小类，这样就等于最佳适配策略的性能了。

简单分离存储

简单分离存储具有以下特点：

  • 每个大小类中都只包含大小相同的块，且块大小就是这个大小类中最大元素的大小。比如{5~8}就只包含大小为8的空闲块。
  • 不执行分割
  • 不执行合并

当进行分配时，会根据块大小先找到对应的空闲链表，如果存在空闲块则直接分配第一个空闲块，如果不存在，则分配器向内核请求得到一个固定大小的虚拟内存片，然后将其划分为大小相同的空闲块，将其链接起来得到新的空闲链表。

当进行释放时，直接将其插入对应的空闲链表头部。

  • 优点：分配和释放块都是常数时间，不分割，不合并，已分配块不需要头部和脚部，空闲链表只需是单向的，因此最小块为单字大小。
  • 缺点：由于使用分割和合并，所以会有大量的内部和外部碎片。

分离适配

分离适配的分配器维护一个空闲链表的数组，每个链表和一个大小类相关联，包含大小不同的块。分配块时，确定请求的大小类，对适当的空闲链表做首次适配，如果找到合适的块，可以分割它，将剩余的部分插入适当的空闲链表中；如果没找到合适的块，查找更大的大小类的空闲链表。如果没有合适的块，就向内核请求额外的堆内存，从这堆内存中分割出合适的块，然后将剩余部分放到合适的大小类中。每释放一个块时，就进行合并，并将其放到合适的大小类中。

分离适配方法比较常见，如GNU malloc包。这种方法既快、利用率也高。

伙伴系统

伙伴系统（Buddy System）是分离适配的一种特例，要求每个大小类都是2的幂。假设一个堆大小为$2^m$​，为每个大小为 $2^k$ 的空闲块都维护了对应的空闲链表。最开始只有一个 $2^m$ 大小的空闲块：

  • 请求分配时：找到第一个可用的大小为 $2^j$ 的空闲块，将其递归平均分割直到刚好能装下我们的数据。每次分割下来的另一部分为伙伴，被放在相应的空闲链表中。
  • 请求释放时：会不断合并空闲的伙伴，直到遇到一个已分配的伙伴就停止。

我们可以通过地址和块大小很快计算出伙伴地址。主要优点在于快速搜索和快速合并，但是会造成大量的内部碎片。

隐式分配器

显示分配器要求应用程序显示地调用free函数来释放已分配块，比如以下代码中在garbage函数中调用了malloc函数来分配块，但是函数返回时并没进行释放，使得p指向的分配块始终保持已分配的状态，则分配器就无权对该分配块进行操作，由于p保存在函数garbage的栈帧中，当garbage返回时也丢失了p，所以这个已分配块就变成了垃圾，无法被使用，直到程序终止。

1
2
3
4
void garbage(){
  int *p = (int *)malloc(128);
  return;
}

而在隐式分配器中，分配器会释放程序不再使用的已分配块，自动对其调用free函数进行释放。则应用程序只需要显示分配自己需要的块，而回收过程由分配器自动完成。

隐式分配器也被称为垃圾收集器，关于垃圾收集器的相关知识可参考jvm的这篇博文