编程之禅
0%

Linux 虚拟内存系统, 内存映射, fork, execve, malloc, free 动态内存分配与释放

发表于 更新于 分类于 阅读次数： Disqus：

Linux 为每个进程维护一个单独的虚拟地址空间，如下图所示。

  • 内核虚拟内存包含内核中的代码和数据结构。
  • 内核虚拟内存的某些区域被映射到所有进程共享的物理页面，例如每个进程都共享内核的代码和全局数据结构。
  • Linux 也将一组连续的虚拟页面(大小等于系统中 DRAM 的总量)映射到相应的一组连续的物理页面。例如：访问页表，或对设备执行IO操作，这些设备被映射到特定物理内存位置时。
  • 内核虚拟内存的其它区域包含每个进程的独有数据，例如页表，内核在进程的上下文中执行代码时使用的栈，以及记录虚拟地址空间当前组织的各种数据结构。 一个Linux进程的虚拟内存

内存区域

Linux 将虚拟内存组织成一些段(或区域)的集合，一个段就是已经分配的虚拟内存的连续片，这些页是以某种方式相关联的。例如，代码段，数据段，堆，共享库段，以及用户栈都是不同的段。每个存在的虚拟页都保存在某个段中，而不属于某个段的虚拟页是不存在的，并且不能被进程引用。Linux 段的概念很重要，因为它允许虚拟地址空间有间隙。

下图所示记录了一个进程中虚拟内存区域的内核数据结构。内核为每个进程维护一个单独的任务结构(task_struct) 。任务结构包含内核运行该进程所需要的所有信息(PID，用户栈指针，可执行目标文件的名字，以及程序计数器)。

Linux 是如何组织虚拟内存的

任务结构的一个属性 mm 指向 mm_struct，它描述虚拟内存的当前状态。其中的两个字段，pgd 指向第一级页表的基址，mmap 指向 vm_area_structs(区域结构/段结构)的链表，其中每个 vm_area_structs 都描述了当前虚拟地址空间的一个段。当内核运行这个进程时，将 pgd 存放在 CR3 控制寄存器中。

每个 vm_area_structs 都包含以下属性：

  • vm_start 段的开始地址
  • vm_end 段的结束地址
  • vm_prot 这个段内所包含的所有页的读写权限
  • vm_flags 描述这个段内的页是否与其它进程共享，和其它一些信息。
  • vm_next 指向链表中的下一个段结构

缺页异常处理

假设 MMU 在试图翻译某个虚拟地址 A 时，触发一个缺页，这个异常导致控制转移到内核的缺页处理程序，该缺页处理程序执行下面的步骤：

  1. 虚拟地址 A 是合法的吗？

    地址 A 和每个段结构中的 vm_start 和 vm_end，如果地址 A 不在任何一个段中，就触发了段错误，随后终止这个进程。

    一个进程可以创建任意数量的新虚拟内存区域，顺序搜索区域结构的链表花销可能很大，Linux 通常在链表中构建一棵树，在树中进行查找。

  2. 试图进行的内存访问是否合法？

    换句话说，进程是否有读，写或执行这个区域内页面的权限。当一个进程对一个只读页面进行写操作，或一个运行在用户模式中的进程试图从内核虚拟内存中读取字。这时就会触发一个保护异常，从而终止这个进程。

  3. 到这一步，内核知道这个缺页是合法的虚拟地址进行合法的操作造成的。随后，它选择一个牺牲页，如果这个牺牲页面被修改过，那么就将它交换出去，换入新的页面并更新页表。当缺页程序返回时，CPU 重新启动引起缺页的指令。

具体过程如下图所示：

Linux 缺页处理

内存映射

Linux 通过将一个虚拟内存区域与一个磁盘上的对象(object)关联起来，以初始化这个虚拟内存区域的内容，这个过程称之为内存映射(memory mapping)。虚拟内存区域可以映射到两种类型的对象之一：

  1. Linux 文件系统中的普通文件

    一个区域可以映射到一个普通磁盘文件的连续部分，例如一个可执行目标文件。文件区(section)被分成页大小的片，每一片包含一个虚拟页面的初始内容。虚拟页面采用按需调度，如果区域比文件区要大，则用零填充。

  2. 匿名文件

    一个区域也可以映射到一个匿名文件，匿名文件是由内核创建，包含全是二进制零。CPU 第一次引用这样一个区域内的虚拟页面时，内核就在物理内存中找到一个合适的牺牲页，如果该页面被修改过，就将这个页面换出来，用二进制零覆盖牺牲页面并更新页表，将这个页面标记为驻留在内存中的。映射到匿名文件的区域中的页面有时也叫做请求二进制零的页。

一旦一个虚拟页面被初始化了，它就在一个由内核维护的专门的交换文件(swap file)之间换来换去。交换文件也叫做交换空间(swap space)或者交换区域(swap area)。在任何时刻，交换空间都限制着当前运行着的进程能够分配的虚拟页面总数。

再看共享对象

如果虚拟内存可以集成到传统的文件系统中，那么就能提供一种简单而高效的把程序和数据加载到内存中方法。

每个进程都有独立的虚拟地址空间，不过许多代码有同样的只读代码区域，例如每个 C 程序都需要来自标准 C 库的诸如 printf 这样的函数，每个进程都包含这些函数会造成大量的内存浪费，内存映射提供了一种清晰的机制，用来控制多个进程如何共享对象。

一个对象可以被映射到虚拟内存的一个区域，要么作为共享对象，用么作为私有对象。如果一个进程将一个共享对象映射到它的虚拟地址空间的一个区域内，那么这个进程对这个区域的任何写操作，对于那些也把这个共享对象映射到它们虚拟内存的其它进程也是可见的。而且，这些变化也会反映在原始对象中。

对于一个映射到私有对象的区域做的改变，对于其它进程来说是不可见的，并且进程对这个区域所做的任何写操作都不会反映在磁盘的原始对象中。一个映射到共享对象的虚拟内存区域叫做共享区域。类似地，也有私有区域。

如下图所示，进程1 将一个共享对象映射到它的虚拟内存的一个区域中。

IMG_CF52C57D94FE-1

每个对象都有一个唯一的文件名，内核可以迅速地判定进程1已经映射了这个对象。即使对象被映射到多个共享区域，物理内存中也只需要存放对象的一个副本。

私有对象使用一种写时复制(copy-on-write)的巧妙技术被映射到虚拟内存中。一个私有对象开始生命周期的方式基本上与共享对象的一样，在物理内存中保存私有对象的一个副本。对于每个映射私有对象的进程，相应私有区域的页表条目都被标记为只读，并且区域结构被标记为私有的写时复制技术。只要有一个进程试图写私有区域内的某个页面，那么这个写操作就会触发一个保护故障。

当故障处理程序注意到保护异常是由于进程试图写私有的写时复制区域中的一个页面而引起的，它就会在物理内存中创建这个页面的一个新副本，更新页表条目指向这个新的副本，然后恢复这个页面的可写权限。当故障程序返回时，CPU 重新执行这个写操作，之后就可以正常进行写了。如下图所示：

IMG_250648794461-1

通过延迟私有对象中的副本直到最后可能的时刻，写时复制最充分地使用了稀有的物理内存。

再看 fork 函数

当 fork 函数被当前进程调用，内核为新进程创建各种数据结构，并分配给它一个唯一的 PID。为了给这个新进程创建虚拟内存，它创建了当前进程的 mm_struct，区域结构和页表的原样副本。它将两个进程中的每个页面都标记为只读，并将两个进程中的每个区域结构都标记为私有的写时复制。

当 fork 函数结束时，新进程现在的虚拟内存刚好和调用 fork 时存在的虚拟内存相同。当两个进程中的任一个后来进行写操作时，写时复制机制就会创建新页面，因此，每个进程都保持了私有地址空间的抽象概念。

再看 execve 函数

假设在当前进程中进行如下调用：execve(“a.out”,NULL,NULL);

execve 函数在当前进程中加载并运行包含在可执行目标文件 a.out 中的程序，用 a.out 程序有效地替代了当前程序。加载并运行 a.out 需要以下几个步骤：

  • 删除已存在的用户区域：删除当前进程虚拟地址的用户部分中的已存在的区域结构。
  • 映射私有区域。为程序的代码，数据，bss 和 栈区域创建新的区域结构。所有这些新的区域都是私有的，写时复制的。代码和数据区域被映射为 a.out 文件中的 .text 和 .data区。bss 区域是请求二进制零的，映射到匿名文件。
  • 映射共享区域：如果 a.out 程序与共享对象(或目标)链接，比如标准 C 库 libc.so，那么这些对象都是动态链接到这个程序的，然后再映射到用户虚拟地址空间中的共享区域。
  • 设置程序计数器(PC)。execve 做的最后一件事情就是设置当前进程上下文中的程序计数器，使之指向代码区域的入口点。

下一次调度这个程序时，它将从这个入口点开始执行。Linux 将根据需要换入代码和数据页面。

IMG_010A1CCB5875-1

使用 mmap 函数的用户级内存映射

Linux 可以使用 mmap 函数来创建新的虚拟内存区域，并将对象映射到这些区域中。

1
2
3
4
5
#include <unistd.h>
#include <sys/mman.h>

void *mmap(void *start, size_t length, int prot,int flags, int fd ,off_t offset);
// 返回值：执行成功则返回指向映射区域的指针，若出错则为 MAP_FAILED(-1)

mmap 函数要求内核创建一个新的虚拟内存区域，最好是从 start 开始的一个区域，并将文件描述符 fd 指定的对象的一个连续的片(chunk)映射到这个新的区域，连续的对象片大小为 length 字节，从距文件开始处偏移量为 offset 字节的地方开始。start 地址仅仅是一个暗示，通常被定义为 NULL。以下，我们假定起始地址总是 NULL。

IMG_B909BA8CBBF5-1

参数 prot 包含描述新映射的虚拟内存区域的访问权限(即在相应区域结构中 vm_prot 位)。

  • PROT_EXEC：这个区域内的页面由可以被 CPU 执行的指令组成。
  • PROT_READ：这个区域内的页面可读。
  • PROT_WRITE：这个区域内的页面可写。
  • PROT_WRITE：这个区域内的页面不可访问。

参数 flag 描述被映射对象类型的位组成。如果设置了 MAP_ANON 标记位，那么被映射的对象就是一个匿名函数，而相应的虚拟页面是请求二进制零的。MAP_PRIVATE 表示被映射的对象是一个私有的，写时复制的对象，而 MAP_SHARED 表示一个共享对象。例如：

1
bufp = mmap(NULL,size,PROT_READ,MAP_PRIVATE|MAP_ANON,0,0);

以上代码让内核创建一个新的包含 size 字节的只读，私有，请求二进制零的虚拟内存区域。如果调用成功，那么 bufp 包含新区域的地址。

munmap 函数删除虚拟内存的区域：

1
2
3
4
#include <unistd.h>
#include <sys/mman.h>

int munmap(void *start,size_t length);

munmap 函数删除从虚拟地址 start 开始，接下来 length 字节组成的区域。如果之后对已经删除区域的引用会导致段错误。

习题：编写一个 C 程序 mmapcopy.c，使用 mmap 将一个任意大小的磁盘文件复制到 stdout。输入文件名字必须作为一个命令行参数来传递。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <stdio.h>
#include <unistd.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <sys/mman.h>
#include <stdlib.h>

int main(int argc,char* argv[]){
    if(argc!=2){
        char s[30];
        sprintf(s,"使用方法: %s 文件名\n",argv[0]);
        fputs(s,stderr);
        exit(1);
    }

    struct stat statbuf;

    int fd = open(argv[1],O_RDONLY);
    stat(argv[1],&statbuf);
    int length = statbuf.st_size;

    void* bufp = mmap(NULL,length,PROT_READ,MAP_SHARED,fd,0);
    int len = write(1,bufp,length);

    close(fd);
    munmap(bufp,length);
    return 0;
}

动态分配内存

虽然可以使用低级的 mmap 和 munmap 函数创建和删除虚拟内存区域，但是 C程序员还是会觉得使用动态内存分配器(dynamic memory allocator)更方便，也有更好的可移植性。

动态内存分配器维护着一个进程的虚拟内存区域，称为堆(head)。假设堆是一个请求二进制零的区域，它紧挨着未初始化的数据区域后开始，并向更高地址生长。对于每个进程，内核维护者一个变量 brk(break)，它指向堆的顶部。如下图所示：

IMG_239E7761CD51-1

分配器将堆视为一组不同大小的块(block)的集合来维护，每个块就是一个连续的虚拟内存片(chunk)，要么是已经分配的，要么是空闲的。一个已分配的块保持已分配状态，直到它被释放，这种释放要么是应用程序显示执行的，要么是内存分配器自身隐式执行的。

分配器有两种风格，它们的区别在于哪个实体来负责释放已经分配的块：

  • 显式分配器(explicit allocator)，要求应用显式地释放任何已分配的块。例如，C 标准库提供一种叫做 malloc 程序包的显式分配器。C 程序通过调用 malloc 函数来分配一个块，并通过调用 free 函数来释放一个块。C++ 中的 new 和 delete 操作符与 C 中的 malloc 和 free 相当。
  • 隐式分配器(implicit allocator)，另一方面，要求分配器检测到一个已分配块何时不被程序使用，就释放这个块。隐式分配器也叫垃圾收集(garbage collection)。例如 Lisp，ML 以及 Java 之类的高级语言就依赖垃圾收集来释放已分配的块。

malloc 和 free 函数

C 标准库提供了称为 malloc 程序包的显式分配器。程序通过调用 malloc 函数来从堆中分配块。

1
2
3
4
#include <stdlib.h>

void *malloc(size_t size);
// 返回值 执行成功返回已分配块的指针，失败则返回 NULL

malloc 返回大小至少为 size 字节的内存块，这个块会为可能包含在这个块内的任何数据对象类型做对齐。在 32 位模式下，malloc 返回的块的地址总是 8 的倍数，在 64 位模式中，该地址总是 16 的倍数。

在本节中，我们假设字是 4 字节对象，双字是 8 字节对象。

当申请的动态内存超过虚拟内存可提供的最大大小，就返回 NULL，并设置 errno。malloc 不初始化它返回的内存。malloc 并不初始化它返回的内存，可以使用 calloc 获得已经初始化的内存，它是一个基于 malloc 的瘦包装函数，它将初始化内存初始化为 0。想要改表一个已分配块的大小，可以使用 realloc 函数。

动态内存分配器，例如 malloc，可以通过使用 mmap 和 munmap 函数，显式地分配和释放堆内存，或者还可以使用 sbrk 函数

1
2
3
4
#include <unistd.h>

void *sbrk(intptr_t incr);
// 返回值 若执行成功返回 旧的 brk 指针，出错返回 -1

sbrk 函数通过将内核的 brk 指针增加 incr 来扩展和收缩堆。成功则返回 brk 的旧值，否则返回 -1，并将 errno 设置为 ENOMEM。如果 incr 为 0，那么 sbrk 就返回当前值。incr 为负也是合法的，因为返回值(brk 的旧值)指向距新堆顶向上 abs(incr)字节处。

程序通过调用 free 函数来释放已经分配的堆块

1
2
3
4
#include <stdlib.h>

void free(void *ptr);
// 无返回值

ptr 参数必须指向一个从 malloc, calloc, 或者 realloc 获得的已分配块的起始地址。如果不是，则 free 的行为是未定义的。更糟的是，它什么都不返回，free 就不会告诉应用程序出现了错误。

下图展示了 malloc 和 free 的实现如何管理一个 C 程序的 16字的(非常)小的堆。每个方框代表了一个 4 字节的字，有阴影表示已分配的块，无阴影表示空闲块。初始时，堆是由一个大小为 16个字的，双字对齐的，空闲块组成的。具体分配过程如下图所示：

IMG_8CD3D184A04B-1

为什么要使用动态内存

某些数据需要实际运行的时候才能确定大小，所以需要动态地分配内存。

分配器的要求和目标

分配器必须在以下严格约束条件下工作：

  • 处理任意请求序列：分配器不可以假设分配和释放请求的顺序。
  • 立即响应请求：不能为了提供性能而重新排列或者缓冲请求。
  • 只使用堆：为了使分配器是可扩展的，分配器使用的任何非标准数据结构都必须保存在堆里。
  • 对齐块：分配器必须对齐块，使得它们可以保存任何数据类型。
  • 不修改已经分配的块：只能操作或改变空闲块。

在满足以上条件下：分配器应该尽可能实现吞吐率最大化，内存使用率最大化。往往这两方面是相互矛盾的。

目标1：最大吞吐率

吞吐率定义为每个单位时间里完成的请求数。合理性能为：一个分配请求的最糟运行时间与空闲块的数量成线性关系，而一个释放请求的运行时间是个常数。

目标2：最大内存利用率

最有用的标准是峰值利用率。

碎片

造成堆利用率低的主要原因就是内存碎片。分为内部碎片和外部碎片。

内部碎片：已分配块比有效载荷大的时候发生，比如有时为了使内存对齐，实际分配数量比请求分配数量大。

外部碎片：空闲内存块合计起来足够满足一个分配请求，但是没有一个单独的空闲块足够大可以处理这个请求时发生。外部碎片难以量化且不可预测，所以分配器通常采用启发式策略来试图维持少量的大空闲块，而不是维持大量的小空闲块。

实现问题

很容易想到将堆作为一个很大的字节数组，还有一个指针 p，初始时指向这个数组第一个字节。这中分配方式每个 malloc 和 free 只执行很少量的指令，因而吞吐率极好。但这种方式从不重复使用任何块，内存利用率将极差。为了平衡吞吐率和内存利用率，必须考虑以下问题：

  • 空闲块组织。
  • 放置：选择一个合适的空闲块。
  • 分割：从一个大块分配完内存之后 ，如何处理它的剩余部分。
  • 合并：如何处理一个刚刚被释放的块。

在下面的部分，介绍一种称为 隐式空闲链表的简单空闲块组织结构。

隐式空闲链表

任何实际的分配器都需要一些数据结构，允许它来区分块边界，以及已分配块和未分配块。大多数分配器将这些信息嵌入块本身，如下图所示：

截屏2021-11-06 上午11.30.41

当考虑到字节对齐时，块的大小总是 8 的倍数，所以块大小的最低 3 位总是 0。我们可以利用最高的 29位保存块大小，剩余的 3 位保存其它信息，例如是否已分配等。

假设我们有一个已分配的块，大小为24 (0x18)字节，那么它的头部将是：0x00000018 | 0x1 = 0x00000019

头部后面是应用调用 malloc 时请求的有效载荷(实际用于存放数据的大小)，有效载荷后是一片不使用的填充块，其大小是任意的，填充的原因：对付外部碎片，满足内存对齐要求。

如下图所示，将堆组织为一个连续的已分配块和空闲块的序列：

IMG_39CE7ADFE601-1

我们称这种方式为隐式空闲链表，因为空闲块是通过头部中的大小字段隐含地连接着的，分配器可以便利链表中的所有块，从而间接地遍历整个空闲块的集合。

隐式空闲链表优点：简单。显著缺点：每次都需要遍历，时间复杂度高。

很重要的一点是系统对齐要求和分配器对块格式的选择会对分配器上的最小块大小有强制的要求。没有已分配块和空闲块可以比这个最小值还要小。

放置已分配的块

当请求分配 k 字节的内存块时，分配器会遍历空闲链表，查找一个足够大的可以放置所请求块的空闲块。分配器执行这种搜索的方式是由放置策略确定的：

  • 首次适配(first fit)

    选择第一个合适的空闲块。

    优点：趋向于将大的空闲块保留在链表的后面。

    缺点：趋向于在靠近链表起始处留下空闲块的“碎片”，这就增大了对较大块的搜索时间。

  • 下一次适配(next fit)

    和首次适配类似，只不过是从上一次查询结束的地方开始。

    优点：比首次适配运行的更快一些，尤其当链表的前面布满了许多小的碎片时。

    缺点：内存利用率比首次适配要低很多。

  • 最佳适配(best fit)

    检查每个空闲块，选择适合所需请求大小的最小空闲块。

    优点：内存利用率比首次适配和下一次适配都要高一些。

    缺点：需要遍历整个隐式链表。

分割空闲块

一旦分配器找到一个匹配的空闲块，它就需要做出以下决定：

  • 使用整个空闲块

    缺点：易造成内部碎片。

    如果放置策略趋向于产生好的匹配，那么额外的内部碎片也是可以接受的。

  • 分割空闲块，其中一部分变成已分配块，剩下的部分作为空闲块。

下图展示了分割器如何分割图 9-36 中 8 个字的空闲块，来满足一个应用对堆内存 3 个字的请求。

IMG_AD6CC096A171-1

获取额外的堆内存

如果分配器不能为请求块找到合适的空闲块怎么办？

  • 合并多个连续的空闲块，组成一个更大的空闲块。
  • 如果上一个方法也不能满足要求，空闲块已经最大限度地合并了，那么分配器就会通过 sbrk 函数，向内核请求额外的堆内存。分配器将额外的内存转化成一个大的空闲块，将这个空闲块插入到空闲链表中。

合并空闲块

当分配器释放一个已分配块时，可能有其它空闲块与这个新释放的空间块相临，这些邻接的空闲块可能引起一种现象，叫做假碎片(fault fragmentation)。如下图所示：

IMG_71D1416EFF98-1

为了解决假碎片问题，任何实际的分配器都必须合并相临的空闲块，这个过程称为合并。合并分为两种：

  • 立即合并：在每次一个块被释放时，就合并所有相邻块。

    优点：简单明了，可以在常数时间内执行完成。

    缺点：对于某些请求，这种方式会产生一种形式的抖动，块会马上合并，然后马上分割。

  • 推迟合并：直到某个分配请求失败，然后扫描整个堆，合并所有空闲块。

快速的分配器通常会选择某种形式的推迟合并。

带边界标记的合并

当我们想释放当前块，想要合并下一块很简单和高效。当前块的头部指向下一块的头部，可以检查这个指针以判断下一块是否空闲，如果是，就将它的大小简单地加到当前块头部大小上，这样在常数时间下就将这两个块合并了。

那怎么和前面的块合并，这时候唯一的选择是搜索整个链表。Kunth 提出了一种聪明的技术，叫做边界标记(boundary tag)，允许在常数时间内进行对前面块的合并。这种思想是在每个块的结尾添加一个脚部(footer，边界标记)，其中脚步就是头部的一个副本，这样分配器就可以通过前一块的脚部判断前一块的起始位置和状态。这个脚步总是在距当前块开始位置一个字的距离。

分配器释放当前块时所有可能存在的情况：

  • 前面的块和后面的块都已分配的。
  • 前面的块是已分配的，后面的块是空闲的。
  • 前面的块是空闲的，后面的块是已分配的。
  • 前面和后面的块都是空闲的。

具体合并过程如下图所示：

IMG_CEA6A9AC4BA6-1

边界标记和概念是简单优雅的，但它确存在一个潜在的缺陷，它要求每个块都保持一个头部和一个脚部，在应用程序操作许多个小块时，会产生显著的内存开销。

幸运的是，有一种非常聪明的边界标记的优化方法，能够使得在已分配块中不再需要脚部。回想下，当我们试图在内存中将当前块与前面的块，后面的块合并时，只有在前面是空闲块时，才会需要用到它的脚部。如果我们把前面块的已分配/空闲位存放在当前块中多出来低位中，那么已分配的块就不需要脚部了。不过空闲块仍然需要脚部。

显式空闲链表

对于隐式空闲链表来说，块的分配与堆块的总数呈线性关系，不适合作为通用的分配器。

一种更好的方式是将空闲块组织为某种形式的显式数据结构。例如，堆可以组织成一个双向空闲链表，在每个空闲块中，都包含一个 pred(前驱)和succ(后继)，如下图所示：

IMG_C7AEF56C08B8-1

使用双向链表而不是隐式链表，使首次适配的分配时间从块总数的线性时间减少到了空闲块数量的线性时间。释放一个块可以线性时间，也可以是常数时间：

  • 后进先出(FIFO)的顺序维护链表：将新释放的块放置在链表的开始处，采用首次适配策略，分配器会最先检查最近使用过的块。如果使用了边界标记，合并也可以在常数时间内完成。
  • 按照地址顺序来维护链表：链表中每个块的地址都小于它后继的地址，释放一块需要线性时间的搜索来定位合适的前驱。平衡点在于，按照地址排序的首次适配LIFO排序的首次适配有更高的内存利用率，接近最佳适配的利用率。

分离的空闲链表

一种流行的减少分配时间的方法，称为分离存储，就是维护多个空闲链表，其中每个块有大致相等的大小。一般的思路是将所有可能的大小分成一些等价类，叫做大小类(size class)。有多种方式定义大小类，例如，可以根据 2 的幂来划分：

{1},{2},{3,4},{5~8},…,{1025~2048},{2049~4096},{4097 ~ 无限大}

分配器维护一个空闲链表数组，每个大小类一个空闲链表，按照大小升序排练，从小的开始搜索，如果不满足就搜索下一个链表。

简单分离存储

如果某个大小类定义为{17 ~ 32}，那么这个类的空闲链表完全由大小为 32 的块组成。

为了分配一个给定大小的块，检查相应的空闲链表，如果非空，简单地分配其中第一块的全部，否则检查下一个链表。如果都不满足，分配器就向操作系统请求一个固定大小的内存页，将这个页分成大小相等的块，并将这些块链接起来形成新的空闲链表。

这种方式优点：分配和释放都是很快的常数时间。

缺点：容易产生内部和外部碎片。

分离适配

分配维护一个空闲链表的数组，每个空闲链表是和一个大小相关联的，并且被组成某种类型的显式或隐式链表。链表包含潜在的大小不同的块，这些块是大小类的成员。为了分配一个块，首先确定请求的大小类，做首次适配，查找一个合适的块，找到了，就(可选)分割它，将剩余部分插入到适当的空闲链表中。找不到就搜索下一个更大的空闲链表。搜索完所有的大小类，都找不到就向操作系统申请额外的堆内容，从这个对内存中分配出一块，将剩余部分放置在合适的大小类中。要释放一个块，首先执行合并，并将结果放置到相应的空闲链表中。

C 标准库中提供的 GNU malloc 包就是采用的这种方法，优点：快速，内存利用率高。

伙伴系统

每个大小类都是 2 的幂，假设一个堆的大小是 2m 个字，我们为每个块大小 2k 维护一个分离空闲链表，其中 0<=k<=m，请求块大小向上舍入到 2 的幂，最开始只有大小为 2m 个字的空闲块。

为了分配一个大小为 2k 的块，首先找到第一个可用的，大小为 2j 的块，其中 k<=j<=m，如果 j==k，那么搜索完成，否则递归地二分割这个块，知道 j==k。当我们进行这样的分割时，每个剩下的半块(也叫做伙伴)被放置在相应的空闲链表中。要释放一个大小为 2k 的块，就合并空闲的伙伴。当遇到一个已分配的伙伴时，就停止。

对于伙伴系统：给定地址和块的大小，很容易计算出它的伙伴的地址，一个块的地址和他的伙伴的地址只有一位不相同。

优点：快速搜索，快速合并。

缺点：2 的幂可能导致显著的内部碎片。