虚拟内存 | My Documentations

虚拟内存提供三个重要能力

将主存看作磁盘的高速缓存，在主存中只保留活动区域，并根据需要在主存和磁盘间传送数据，高效地使用了主存
为每个进程提供了一致的地址空间，简化了内存管理
也保护了每个进程的地址空间不被其他进程破坏

# 物理和虚拟寻址

物理地址(Physical Address, PA)：计算机的主存被组织成一个由M个连续的字节大小的单元组成的数组。每字节都有一个唯一的物理地址。
虚拟寻址(Virtual Address, VA)：CPU生成一个虚拟地址来访问主存，这个虚拟地址在被送到内存之前先转换为适当的物理地址。在CPU芯片上由叫内存管理单元(Memory Management Unit, MMU)的硬件负责地址翻译，即将VA转换为PA。MMU通过到主存中查询页表来动态翻译VA。

# 地址空间

地址空间是一个非负整数地址的有序集合，为了简化讨论总是使用线性地址空间，即整数是连续的。
虚拟地址空间的大小用位表示，n位地址空间，表示有 $N=2^n$ 个地址。物理地址空间对应于物理内存的M个字节。M不要求是2的幂，但我们通常这样假设。
虚拟内存的基本思想是：允许每个数据对象(字节)有多个独立的地址，其中每个地址来自不同的地址空间。

# 虚拟内存的结构

概念上，虚拟内存是一个由存放在磁盘上的N个连续字节组成的数组。磁盘上的数据被分割成块，作为在磁盘和主存之间的传送单元。VM系统将虚拟内存分割成的块称为虚拟页(Virtual Page, VP)，物理内存的块称为物理页(Physical Page, PP)或页帧(page frame)(大小为 $P=2^p$ 字节)。

VP-PP

# DRAM缓存

术语DRAM缓存表示VM系统的缓存，即用主存缓存VP。
相应的SRAM缓存表示CPU和主存之间的L1,L2,L3高速缓存。

磁盘比DRAM慢大约100000多倍，不命中的开销巨大。从磁盘读取第一个字节的开销也很大。因此

虚拟页往往很大，通常为4KB~2MB
DRAM缓存是全相联的
替换策略更复杂，精密
使用写回，而非直写

# 页表(Page Table)

建立虚拟页到物理页的映射

页表是一个存放在物理内存中的数据结构，是一个页表条目(Page Table Entry, PTE)的数组，建立虚拟页到物理页的映射。虚拟地址空间中的每个页在页表中一个固定偏移量处都有一个PTE。
MMU中的地址翻译硬件每次将VA转换为PA时，都会去读页表。
OS负责维护页表的内容，以及在磁盘和DRAM之间来回传送页。 PS：有效位为1表示对应的VP已经装入物理内存了，地址为内存地址。有效位为0表示要么VP还未分配，要么地址指向VP在磁盘上的位置。

# 命中与缺页

当CPU想要读取VM系统中的一个字节（如VP2）时，发送一个VA到MMU的地址翻译硬件，地址翻译硬件根据VA的前n-p位VPN(Virtual Page Number)定位页表中相应的PTE，然后查看PTE的有效位

如果为1，说明VP2已缓存在内存中了。PTE中的地址就是PA的PPN(Physics Page Number)。取出来和VPO(Virtual Page Offset)构成实际物理地址。
如果为0，称为缺页(page fault)。引发一个缺页异常。缺页异常调用内核中的缺页异常处理程序，该程序选择一个牺牲页，设为VP4(如果VP4已经被修改了，则内核将VP4复制回磁盘)，内核修改相应PTE，以表示VP4已不再主存中。接下来，内核从磁盘复制VP2到原VP4所在的主存位置，更新相应PTE后返回。异常处理程序返回时，会重新启动导致缺页的指令，此时必定命中。
页面调度(Paging)：在磁盘和内存之间传送页的活动。从磁盘到DRAM称换入，反之称换出。
页面分配：分配一个新的VP，如调用malloc，使PTE中含null的空洞页实际占有物理空间。

# 内存管理

OS为每个进程提供了一个独立的页表，因而也就是一个独立的虚拟地址空间。

好处

简化链接：每个进程的内存格式都类似。对于64位地址空间，代码段总是从VA=0x400000开始。数据段跟在代码段之后，中间有一段符合要求的对齐空白。栈占据用户进程地址空间最高的部分，并向下生长。链接时，一直使用VA，实际运行时再映射为PA。
简化加载：有了虚拟内存后，加载文件时，只需要为文件分配虚拟页，即将其PTE有效位设为0，并指向目标文件的适当位置。也就是说，实际没有任何复制动作，实际要用时再按需调度。
简化共享：OS可将不同进程的页表中适当的VP映射到相同的PP，从而实现多进程共享相应代码。
简化内存分配：用malloc要求额外的堆空间时，在VM中分配的连续的VP，实际PP可以不连续。

# 内存保护

OS需要某种手段来控制对内存系统的访问。如

不允许用户进程修改其只读代码段
不允许用户进程修改内核中的代码和数据结构
不允许用户进程读或写其他进程的私有内存
不允许用户进程修改任何与其他进程共享的虚拟页面(除非所有共享者都允许它这么做)

实现很容易，只需在PTE中添加几个许可位。例如

SUP：进程需要在内核(超级用户)模式下才能访问该页
READ：读权限
WRITE：写权限
……

保护违例：如果一条指令违反了这些许可条件，则CPU触发一个保护故障，将控制传递给一个内核中的异常处理程序。Linux shell 一般称这种异常为“段错误(segmentation fault)”

# 地址翻译

TLB， Translation Lookaside Buffer，简称快表

符号

$N=2^n$ ：虚拟地址空间中的地址数量
$M=2^m$ ：物理地址空间中的地址数量
$P=2^p$ ：页大小(字节)

VPN：虚拟页号
VPO：虚拟页面偏移量
TLBT： TLB标记
TLBI：TLB索引

PPO：物理页面偏移量，和VPO一样
PPN：物理页号
CO：缓存块内字节偏移量
CI： cache索引
CT： cache标记

地址翻译

CPU中的一个控制寄存器，页表基址寄存器(PTBR)指向当前页表基址。
虚拟地址=VPN(n-p位)+VPO(p位)
VPN和页表中的PTE一一对应。
物理地址=PPN+VPO

页面命中时CPU执行步骤：

处理器生成一个虚拟地址，并把它传送给 MMU。
MMU 生成 PTE 地址，并从高速缓存/主存请求得到它。
高速缓存/主存向 MMU 返回 PTE。
MMU 构造物理地址，并把它传送给高速缓存/主存。
高速缓存/主存返回所请求的数据字给处理器。

缺页时：

第 1 步到第 3 步：和命中时的第 1 步到第 3 步相同。
第 4 步：PTE 中的有效位是零，所以 MMU 触发了一次异常，传递 CPU 中的控制到操作系统内核中的缺页异常处理程序。
第 5 步：缺页处理程序确定出物理内存中的牺牲页，如果这个页面已经被修改了，则把它换出到磁盘。
第 6 步：缺页处理程序页面调入新的页面，并更新内存中的 PTE。
第 7 步：缺页处理程序返回到原来的进程，再次执行导致缺页的指令。CPU 将引起缺页的虚拟地址重新发送给 MMU。因为虚拟页面现在缓存在物理内存中，所以就会命中，在 MMU 执行了图 9-13b 中的步骤之后，主存就会将所请求字返回给处理器。

# 结合高速缓存和虚拟内存

因为MMU在CPU内，翻译地址时需要到主存中查页表，因此缓存可以发挥作用，缓存PTE就像其他数据字一样。

# 使用TLB加速地址翻译

为了减少到主存或缓存中查询页表的次数，在MMU中包括了一个关于PTE的小的缓存，称为翻译后备缓冲器(TLB)，即快表。
TLB 是一个小的、虚拟寻址的缓存，其中每一行都保存着一个由单个 PTE 组成的块。

TLB

CPU访存时，地址中虚页号被分成tag+index，tag用于和TLB页表项中的tag比较，index用于定位需要比较的表项。

TLB全相联时，没有index，只有Tag，虚页号需与每个Tag比较；
TLB组相联时，则虚页号高位为Tag，低位为index，用作组索引

寻址-tlb

# 多级页表

如果我们有一个 32 位的地址空间、4KB 的页面和 4B 的 PTE，那么即使应用所引用的只是虚拟地址空间中很小的一部分，也总是需要一个 4MB 的页表驻留在内存中。对于地址空间为 64 位的系统来说，问题更大。所以需要压缩页表，常用方法是使用层次结构的页表。
假设 32 位虚拟地址空间被分为 4KB 的页，而每个页表条目都是 4 字节。还假设在这一时刻，虚拟地址空间有如下形式：内存的前 2K 个页面分配给了代码和数据，接下来的 6K 个页面还未分配，再接下来的 1023 个页面也未分配，接下来的 1 个页面分配给了用户栈。多级页表

一级页表中的每个 PTE 负责映射虚拟地址空间中一个 4MB 的片（chunk），这里每一片都是由 1024 个连续的页面组成的。假设地址空间是 4GB，1024 个 PTE 已经足够覆盖整个空间了。如果片 i 中的每个页面都未被分配，那么一级 PTE i 就为空。如果在片 i 中至少有一个页是分配了的，那么一级 PTE i 就指向一个二级页表的基址。二级页表中的每个 PTE 都负责映射一个 4KB 的虚拟内存页面，就像我们查看只有一级的页表一样。
注意，使用 4 字节的 PTE，每个一级和二级页表都是 4KB 字节，这刚好和一个页面的大小是一样的。

这种方法从两个方面减少了内存要求。

如果一级页表中的一个 PTE 是空的，那么相应的二级页表就根本不会存在。这代表着一种巨大的潜在节约，因为对于一个典型的程序，4GB 的虚拟地址空间的大部分都会是未分配的。
只有一级页表才需要总是在主存中；虚拟内存系统可以在需要时创建、页面调入或调出二级页表，这就减少了主存的压力；只有最经常使用的二级页表才需要缓存在主存中。

使用 k 级页表层次结构的地址翻译。虚拟地址被划分成为 k 个 VPN 和 1 个 VPO。每个 VPN i 都是一个到第 i 级页表的索引。第 j 级页表中的每个 PTE都指向第 j+1 级的某个页表的基址。

为了确定PPN，MMU必须访问k个PTE。看上去消耗很大，实际上TLB可以将不同层次上页表的PTE缓存起来，代价并没有大很多。

多级页表

# Linux虚拟内存系统

Linux为每个进程维护一个单独的虚拟地址空间。形式如图。 Linux虚拟内存系统

# Linux虚拟内存区域

Linux将虚拟内存组织成一些区域(area，也叫做段,segment)的集合。一个段就是已分配的虚拟内存的连续片(chunk)，并以某种形式相关联。每个虚拟页都保存在某个段中，如果引用的虚拟页不属于某个段，会引发段错误。
以段的形式组织内存，好处是：允许虚拟地址空间有间隙，因此内存无需记录那些不存在的虚拟页。

# 虚拟内存区域的内核数据结构

内核为每个进程维护一个单独的任务结构(task_struct)。
task_struct中一个条目指向一个描述虚拟内存当前状态的数据结构(mm_struct)。
mm_struct中有两个重要字段：
- pgd：指向第一级页表的基址。当内核运行该程序是，将pdg放到CR3控制寄存器中。
- mmap：指向一个区域结构(vm_area_structs)的链表。
  - 每个vm_area_structs都描述了当前虚拟地址空间中的一个区域，包含：
  - vm_start：指向区域的起始地址。
  - vm_end：指向区域的结束地址。
  - vm_prot：描述该区域包含的所有页的读写许可权限。
  - vm_flags：描述一些其他信息，如该区域内的页面是与其他进程共享的，还是私有的。
  - vm_next：指向下一个区域结构。

Linux虚拟内存段

# Linux缺页处理异常

设MMU在试图翻译某个VA时，触发了一个缺页。导致控制转到内核的缺页处理程序，随后执行：

VA是否合法?也就是说，VA在某个区域结构定义的区域内吗？为了作出判断，需要将VA和链表中所有区域结构的vm_start,vm_end作比较。如果不合法，触发一个段错误，并终止进程。因为一个进程可以创建任意数量的新虚拟内存区域，所以这种顺序搜索效率不够。因而实际中，有优化。
试图进行的内存访问是否合法?即进程的访问权限对不对？如果访问不合法，那么缺页处理程序会触发一个保护异常，从而终止进程。
如果确实是对合法VA的合法操作。则选择牺牲页，如果有修改，则多一步换出操作，否则换入新的页面并更新页表。
当缺页处理程序返回时，CPU重新启动引起缺页的指令，该指令就能正常执行了。

# 内存映射

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

**Linux 文件系统中的普通文件：**一个段可以映射到一个普通磁盘文件的连续部分，例如一个可执行目标文件。文件区（section）被分成页大小的片，每一片包含一个虚拟页面的初始内容。因为按需进行页面调度，所以这些虚拟页面没有实际交换进入物理内存，直到 CPU 第一次引用到页面。如果段比文件区要大，那么就用零来填充这个段的余下部分。
匿名文件：一个段也可以映射到一个匿名文件，匿名文件是由内核创建的，包含的全是二进制零。CPU 第一次引用这样一个段内的虚拟页面时，内核就在物理内存中找到一个合适的牺牲页面，如果该页面被修改过，就将这个页面换出来，用二进制零覆盖牺牲页面并更新页表，将这个页面标记为是驻留在内存中的。注意在磁盘和内存之间并没有实际的数据传送。因为这个原因，映射到匿名文件的段中的页面也叫做demand-zero page。

无论在哪种情况中，一旦一个虚拟页面被初始化了，它就在一个由内核维护的专门的交换文件（swap file）之间换来换去。交换文件也叫做交换空间（swap space）或者交换区域（swap area）。需要意识到的很重要的一点是，在任何时刻，交换空间都限制着当前运行着的进程能够分配的虚拟页面的总数。

# 再看共享对象

一个对象可以被映射到虚拟内存的一个区域，要么作为共享对象，要么作为私有对象。

如果一个进程将一个共享对象映射到它的虚拟地址空间的一个区域内，那么这个进程对这个区域的任何写操作，对于其它也把这个共享对象映射到虚拟内存中的进程而言也是可见的。而且，这些变化也会反映在磁盘上的原始对象中。
对一个映射到私有对象的区域做的改变，对于其他进程来说是不可见的，并且进程对这个区域所做的任何写操作都不会反映在磁盘上的对象中。一个映射到共享对象的虚拟内存区域叫做共享区域。类似地，也有私有区域。

因为每个对象都有一个唯一的文件名，内核可以迅速地判定进程 1 已经映射了这个对象，而且可以使进程 2 中的页表条目指向相应的物理页面。关键点在于即使对象被映射到了多个共享区域，物理内存中也只需要存放共享对象的一个副本。为了方便，我们将物理页面显示为连续的，但是在一般情况下当然不是这样的。

私有对象使用一种叫做写时复制（copy-on-write）的技术映射到虚拟内存中。一个私有对象开始时共享对象的一样，在物理内存中只有私有对象的一份副本，但相应私有区域的页表条目都被标记为只读，并且区域结构的标记(vm_flags)为私有的、写时复制。当没有进程试图写它自己的私有区域时，它们就共享物理内存中对象的一个单独副本。然而，只要有一个进程试图写私有区域内的某个页面，那么这个写操作就会触发一个保护故障。当故障处理程序注意到保护异常是由于进程试图写一个标记为私有的、写时复制的区域中的一个页面而引起的时候，它就会在物理内存中创建这个页面的一个新副本，更新页表条目指向这个新的副本，然后恢复这个页面的可写权限。当故障处理程序返回时，CPU 重新执行这个写操作，现在在新创建的页面上这个写操作就可以正常执行了。

通过尽可能延迟私有对象的拷贝操作，copy-on-write充分地使用了稀有的物理内存。

# 再看fork函数

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

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

# 再看 execve 函数

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

删除已存在的用户区域。删除当前进程虚拟地址的用户部分中的已存在的区域结构。
映射私有区域。为新程序的text、data、bss 和栈区域创建新的区域结构。所有这些新的区域标记为私有的、写时复制的。代码和data区域被映射为 a.out 文件中的.text 和.data 区。bss 区域映射到匿名文件，其大小包含在 a.out 中。栈和堆区域也映射到匿名文件，初始长度为零。(C/C++的未初始化static变量，全局变量都是在.bss节，因此都会初始化为0。堆栈虽然会初始化为零，但堆栈都是动态的，其地址可能被复用，导致下一次分配到的地址可能存在之前留下的脏数据，因此，未初始化的堆栈变量的值无法确定)
映射共享区域。如果 a.out 程序与共享对象链接，比如标准 C 库 libc.so，那么这些对象都是动态链接到这个程序的，然后再映射到用户虚拟地址空间中的共享区域内。
设置程序计数器（PC）。execve 做的最后一件事情就是设置当前进程上下文中的程序计数器，使之指向代码区域的入口点。

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

execve加载

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

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

#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)。

1
2
3
4
5
6
7

mmap 函数要求内核创建一个新的虚拟内存区域，最好是从地址 start 开始的一个区域，并将文件描述符 fd （用于打开文件的open函数的返回值）指定的对象的一个连续的片（chunk）映射到这个新的区域。连续的对象片大小为 length 字节，从距文件开始处偏移量为 offset 字节的地方开始。start 地址仅仅是一个暗示而不是命令，通常设为 NULL。 mmap函数

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

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

参数 flags 由描述被映射对象类型的位组成。

MAP_ANON 标记位，表示被映射的对象是一个匿名对象，而相应的虚拟页面是请求二进制零的
MAP_PRIVATE 表示是一个私有的、写时复制的对象
MAP_SHARED 表示是一个共享对象。

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

#include <unistd.h>
#include <sys/mman.h>

int munmap(void *start, size_t length);

// 返回：若成功则为 0，若出错则为 -1。

1
2
3
4
5
6

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

更多信息

#include "csapp.h"

/*
* mmapcopy - uses mmap to copy file fd to stdout
*/
void mmapcopy(int fd, int size)
{
    char *bufp; /* ptr to memory-mapped VM area */

    bufp = mmap(NULL, size, PROT_READ, MAP_PRIVATE, fd, 0);
    Write(1, bufp, size);
    return;
}

/* mmapcopy driver */
int main(int argc, char **argv)
{
    struct stat stat;
    int fd;

    /* Check for required command-line argument */
    if (argc != 2) {
        printf("usage: %s <filename>\n", argv[0]);
        exit(0);
    }

    /* Copy the input argument to stdout */
    fd = Open(argv[1], O_RDONLY, 0);
    fstat(fd, &stat);
    mmapcopy(fd, stat.st_size);
    exit(0);
}

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
29
30
31
32

# 动态内存分配

动态内存分配器维护着一个进程的虚拟内存区域--堆

堆紧接在未初始化的数据区域(bss)后开始，并向高地址增长。
内核为每个进程维护一个变量 brk(读做 “break”)，指向堆的顶部。
分配器将堆视为一组不同大小的块（block）的集合来维护。每个块就是一个连续的虚拟内存片（chunk），要么是已分配的，要么是空闲的。

分配器风格

显式分配器（explicit allocator），要求应用显式地释放任何已分配的块。malloc/free, new/delete。
隐式分配器（implicit allocator），要求分配器检测一个已分配块何时不再被程序所使用，并负责释放这个块。隐式分配器也叫做垃圾收集器（garbage collector），而自动释放未使用的已分配的块的过程叫做垃圾收集（garbage collection）

# malloc和free函数

#include <stdlib.h>
void *malloc(size_t size);
void *calloc(size_t size);
void free(void *ptr);

#include <unistd.h>
void *sbrk(intptr_t  incr);

1
2
3
4
5
6
7

malloc函数返回一个指针，指向大小至少为size字节的内存块。在32位模式中，malloc返回的块地址总是8的倍数。64位模式下，总是16的倍数。
如果malloc遇到问题则返回NULL并设置errno。
malloc不初始化它返回的内存。要初始化，使用calloc。
sbrk函数通过将内核的brk指针增加incr来扩展和收缩堆(incr为负值)。成功返回brk的旧值，否则返回-1,并设errno为ENOMEM。
sbrk(0)返回当前brk的值。
free的参数必须是已分配块的起始位置。否则free的行为未定义。

峰值利用率

为程序的聚集有效载荷(每个块的有效载荷的和)占当前堆大小的比例，在分配器分配释放内存的序列中达到的峰值。

# 碎片

内部碎片：已分配块比有效载荷大的部分。
外部碎片：是当空闲内存合计起来足够满足一个分配请求，但是没有一个单独的空闲块足够大可以来处理这个请求时发生的。
- 外部碎片不仅取决于以前请求的模式和分配器的实现方式，还取决于将来请求的模式。例如，现在内存中只有6个字的空闲，但这六个字是分散的，有两个3字的空闲块组成的。那么，对于一个6字的请求，就存在两个碎片，对于一个3字的请求，就不存在碎片。
- 因为外部碎片难以量化且不可能预测，所以分配器通常釆用启发式策略来试图维持少量的大空闲块，而不是维持大量的小空闲块。

# 分配器的实现问题

最简单的分配器会把堆组织成一个大的字节数组，还有一个指针 p，初始指向这个数组的第一个字节。为了分配 size 个字节，malloc 将 p 的当前值保存在栈里，将 p 增加 size，并将 p 的旧值返回到调用函数。free 只是简单地返回到调用函数，而不做其他任何事情。

这个简单的分配器是设计中的一种极端情况。因为每个 malloc 和 free 只执行很少量的指令，吞吐率会极好。然而，因为分配器从不重复使用任何块，内存利用率将极差。一个实际的分配器要在吞吐率和利用率之间把握好平衡，就必须考虑以下几个问题：

空闲块组织：我们如何记录空闲块？(核心)
放置：我们如何选择一个合适的空闲块来放置一个新分配的块？
分割：在将一个新分配的块放置到某个空闲块之后，我们如何处理这个空闲块中的剩余部分？
合并：我们如何处理一个刚刚被释放的块？

# 隐式空闲链表

任何实际的分配器都需要一些数据结构，允许它来区别块边界，以及区别已分配块和空闲块。大多数分配器将这些信息嵌入块本身。堆块的格式

头部编码了这个块的大小（包括头部和所有的填充），以及这个块是已分配的还是空闲的。
有效载荷的大小为malloc的参数。malloc返回的指针，指向的就是有效载荷的首地址。
填充可能是分配器策略的一部分，用来对付外部碎片。或者也需要用它来满足对齐要求。

注意

因为对齐约束条件，块大小就总是 8 的倍数，也就是说块大小的最低 3 位总是零。因此，内存大小只要用到其 29 个高位，剩余的 3 位来编码其他信息。我们用其中的最低位（称已分配位）来指明这个块是已分配的还是空闲的。

将堆组织为一个连续的已分配块和空闲块的序列，称为隐式空闲链表，因为空闲块是通过头部中的大小字段隐含地连接着的。隐式空闲列表注意：结束块需要某种特殊标记，在这个示例中，就是一个设置了已分配位而大小为零的终止头部（terminating header）。

系统对齐要求和分配器对块格式的选择会对分配器上的最小块大小有强制的要求。

# 放置

当一个应用请求一个k字节的块时，分配器搜索空闲链表，查找一个足够大可以放置所请求块的空闲块。搜索的方式由放置策略确定。

首次适配：从头开始搜索空闲链表，选择第一个合适的空闲块。
下一次适配：从上一次查询结束的地方开始搜索空闲链表，选择第一个合适的空闲块。
最佳适配：检查每个空闲块，选择适合所需请求大小的最小空闲块。

# 分割

一旦分配器找到一个匹配的空闲块，它就必须做另一个策略决定，那就是分配这个空闲块中多少空间。一个选择是用整个空闲块。虽然这种方式简单而快捷，但是主要的缺点就是它会造成内部碎片。分配器通常会选择将这个空闲块分割为两部分。第一部分变成分配块，而剩下的变成一个新的空闲块。

注意

如果分配器不能为请求块找到合适的空闲块将发生什么呢？

合并那些在内存中物理上相邻的空闲块来创建一些更大的空闲块
调用 sbrk 函数，向内核请求额外的堆内存。分配器将额外的内存转化成一个大的空闲块，将这个块插入到空闲链表中，然后将被请求的块放置在这个新的空闲块中。

# 合并

当分配器释放一个已分配块时，可能有其他空闲块与这个新释放的空闲块相邻。这些邻接的空闲块可能引起一种现象，叫做假碎片（fault fragmentation），就是有许多可用的空闲块被切割成为小的、无法使用的空闲块。为了解决假碎片问题，任何实际的分配器都必须合并相邻的空闲块，这个过程称为合并（coalescing）。

合并策略

立即合并（immediate coalescing）：在每次一个块被释放时，就合并所有的相邻块。
推迟合并（deferred coalescing）：等到某个稍晚的时候再合并空闲块。例如，某个分配请求失败时，扫描整个堆，合并所有的空闲块。
立即合并简单明了，可以在常数时间内执行完成，但是对于某些请求模式，这种方式会产生一种形式的抖动，块会反复地合并，然后马上分割。快速的分配器通常会选择某种形式的推迟合并。

# 带边界标记的合并

设想要释放的块为当前块。那么，合并下一个空闲块很简单而且高效。当前块的头部指针+头部大小=下一块的头部指针，可以检查这个指针以判断下一个块是否是空闲的。如果是，就将它的大小简单地加到当前块头部的大小上，这两个块在常数时间内被合并。但是，对于前一块，因为不知道块大小，所以无法找到其头部指针，因而无法判断其是否空闲，也无从合并。

Knuth提出了一种解决方法，叫边界标记(boundary tag)。
在每个块的结尾处添加一个脚部（footer，边界标记），实际上就是头部的一个副本。这样，因为头部指针大小是固定的，从当前块的头部指针上移一个指针就能找到上一块的脚步，从而确定其是否空闲，块大小为多少。

使用边界标记合并共有4种情况：

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

边界标记的概念是简单优雅的，它对许多不同类型的分配器和空闲链表组织都是通用的。然而，它也存在一个潜在的缺陷。它要求每个块都保持一个头部和一个脚部，在应用程序操作许多个小块时，会产生显著的内存开销。

边界标记的优化方法

考虑合并的四种情况，只有在前面的块是空闲时(情况3,4)，才会需要用到它的脚部。因此，可以将表明前面块是已分配还是空闲的标志位，放在当前块头部的3个低位中(最低位是当前块的标志，次低位是前一块的标志)，这样已分配的块就不要footer了。但注意，空闲块仍然需要footer。
例如，如果当前块的次低位为1，即前一块是已分配的，那么合并时用不到前一块，自然不需要前一块的footer。如果次低位是0，即前一块是未分配的，可以通过空闲块的footer找到其头部，将前一块和当前块合并。至于后面的块，本来就用不到footer，用头部即可。

# 显式空闲链表

隐式空闲链表，块分配与堆块的总数呈线性关系(每次分配块，都要从头开始扫描整个堆)，所以对于通用的分配器，隐式空闲链表是不适合的。一种更好的方法是将空闲块组织为某种形式的显式数据结构。另外，根据定义，程序不需要一个空闲块的主体，所以实现这个数据结构的指针可以存放在这些空闲块的主体里面。

显示空闲链表

使用双向链表而不是隐式空闲链表，使首次适配的分配时间从块总数的线性时间减少到了空闲块数量的线性时间。
释放时间取决于链表中块的排序策略。
- 用后进先出的顺序维护链表，将新释放的块放置在链表的开始处。释放与合并可以在常数时间内完成。
- 按照地址顺序来维护链表，其中链表中每个块的地址都小于它后继的地址。在这种情况下，释放一个块需要线性时间的搜索来定位合适的前驱。但首次适配的内存利用率更高。

一般而言，显式链表的缺点是空闲块必须足够大，以包含所有需要的指针，以及头部和可能的脚部。这就导致了更大的最小块大小，也潜在地提高了内部碎片的程度。

# 分离的空闲链表

分离存储（segregated storage），就是维护多个空闲链表，其中每个链表中的块有大致相等的大小。一般的思路是将所有可能的块大小分成一些等价类，也叫做大小类（size class，例如{17~32}表示大小为17到32字之内的内存都属于这一类）。
分配器维护着一个空闲链表数组，每个大小类一个空闲链表，按照大小的升序排列。当分配器需要一个大小为 n 的块时，它就搜索相应的空闲链表。如果不能找到合适的块与之匹配，它就搜索下一个链表，以此类推。

# 简单分离存储

每个大小类的空闲链表包含大小相等的块，每个块的大小就是这个大小类中最大元素的大小。例如{17~32}中就只有大小为32字的块。
空闲块是不会分割以满足分配请求的。
如果链表为空，分配器就向操作系统请求一个固定大小的额外内存片（通常是页大小的整数倍），将这个片分成大小相等的块，并将这些块链接起来形成新的空闲链表。
要释放一个块，分配器只要简单地将这个块插入到相应的空闲链表的前部。因为不分割，所以也不会有合并。

优点：
- 分配和释放块都很快，常数时间。
- 每个片中都是大小相等的块，不分割，不合并，内存开销少(不需要头部，脚部，单向链表只要一个指针)。
- 最小块大小为一个字，即succ指针
缺点：
- 非常容易造成内部和外部碎片。

# 分离适配

每个链表包含潜在的大小不同的块，这些块的大小是大小类的成员。

为了分配一个块，必须确定请求的大小类，并且对适当的空闲链表做首次适配，査找一个合适的块。
如果找到了一个，那么就（可选地）分割它，并将剩余的部分插入到适当的空闲链表中。如果找不到，就搜索下一个更大的大小类的空闲链表。如此重复，直到找到一个合适的块。
如果空闲链表中没有合适的块，那么就向操作系统请求额外的堆内存，从这个新的堆内存中分配出一个块，将剩余部分放置在适当的大小类中。
要释放一个块，执行合并，并将结果放置到相应的空闲链表中。

分离适配方法是一种常见的选择，C 标准库中提供的 GNU malloc 包就是釆用的这种方法，因为这种方法既快速，对内存的使用也很有效率。

# 伙伴系统

伙伴系统（buddy system）是分离适配的一种特例，其中每个大小类都是 2 的幂。基本的思路是假设一个堆的大小为 $2^m$ 个字，我们为每个块大小 $2^k$ 维护一个分离空闲链表，其中 $0 \leq k \leq m$ 。请求块大小向上舍入到最接近的 2 的幂。最开始时，只有一个大小为 $2^m$ 个字的空闲块。

为了分配一个大小为 $2^k$ 的块，先找到第一个可用的大小足够的块。如果大小正好，结束。如果找到的块大了，则递归地二分割这个块，直到大小正好，剩下的半块（也叫做伙伴）被放置在相应的空闲链表中。为了释放一个大小为 $2^k$ 的块，只需要合并空闲的伙伴。当遇到一个已分配的伙伴时，就停止合并。

关键事实：给定地址和块的大小，很容易计算出它的伙伴的地址。
主要优点：快速搜索和快速合并。
主要缺点：要求块大小为 2 的幂可能导致显著的内部碎片。

# 垃圾收集

垃圾收集器（garbage collector）是一种动态内存分配器，它自动释放程序不再需要的已分配块。这些块被称为垃圾（garbage）。自动回收堆存储的过程叫做垃圾收集（garbage collection）。

# 基本知识

垃圾收集器将内存视为一张有向可达图（reachability graph），其形式如图所示。
该图的节点被分成一组根节点（root node）和一组堆节点（heap node）。

每个堆节点对应于堆中的一个已分配块。
有向边 p→q 意味着块 p 中的某个位置指向块 q 中的某个位置。
根节点对应于本身不再堆中，但包含指向堆的指针的变量。
p是可达的：存在一条从任意根节点出发并到达 p 的有向路径

Java 的垃圾收集器，对应用如何创建和使用指针有很严格的控制，能够维护可达图的一种精确的表示，因此也就能够回收所有垃圾。然而，诸如 C 和 C++ 这样的语言的收集器通常不能维持可达图的精确表示。这样的收集器也叫做保守的垃圾收集器（conservative garbage collector）。即每个可达块都被正确地标记为可达了，而一些不可达节点却可能被错误地标记为可达。

向malloc包中加入保守的GC后，malloc的流程为

向malloc请求空间，找到了，返回。
找不到合适的空闲块，则调用GC，希望回收一些垃圾到空闲链表。
GC返回，malloc重试。成功找到，返回。
还是失败，向OS要求额外的内存。成功，返回指针，否则返回NULL。

# Mark&Sweep垃圾收集器

Mark&Sweep 垃圾收集器由标记（mark）阶段和清除（sweep）阶段组成，标记阶段标记出根节点的所有可达的和已分配的后继，而后面的清除阶段释放每个未被标记的已分配块。块头部中空闲的低位中的一位通常用来表示这个块是否被标记了。

描述所需函数

ptr 定义为 typedef void* ptr：
ptr isPtr (ptr p)。如果 p 指向一个已分配块中的某个字，那么就返回一个指向这个块的起始位置的指针 b。否则返回 NULL。
int blockMarked(ptr b)。如果块 b 是已标记的，那么就返回 true。
int blockAllocated (ptr b)。如果块 b 是已分配的，那么就返回 true。
void markBlock (ptr b)。标记块 b。
int length (b)。返回块 b 的以字为单位的长度(不包括头部)。
void unmarkBlock (ptr b)。将块 b 的状态由已标记的改为未标记的。
ptr nextBlock (ptr b)。返回堆中块 b 的后继。

void mark(ptr p) {
    if ((b = isPtr(p)) == NULL)
        return;
    if (blockMarked(b))
        return;
    markBlock(b);
    len = length(b);
    for (i = 0; i < len; i++)
        mark(b[i]);
    return;
}

void sweep(ptr b, ptr end) {
    while (b < end) {
        if (blockMarked(b))
            unmarkBlock(b);
        else if (blockAllocated(b))
            free(b);
        b = nextBlock(b);
    }
    return;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

标记阶段为每个根节点调用一次 mark 函数。
清理阶段循环遍历堆上的每个块，为每个调用 sweep 函数。直到某次循环没有清理任何块。

c语言的isPtr函数存在的问题

C 不会用任何类型信息来标记内存位置。因此，对 isPtr 没有一种明显的方式来判断它的输入参数 p 是不是一个指针。这导致了C程序的Mark&Sweep收集器必须是保守的。
即使 p 是一个指针，isPtr 也没有明显的方式来判断 p 是否指向一个已分配块的有效载荷中的某个位置。解决方法是将已分配块集合维护成一棵平衡二叉树，这棵树保持着这样一个属性：左子树中的所有块都放在较小的地址处，而右子树中的所有块都放在较大的地址处。每个已分配块的头部里有两个附加字段（left 和 right）。每个字段指向某个已分配块的头部。isPtr(ptr p) 函数用树来执行对已分配块的二分查找。在每一步中，它依赖于块头部中的大小字段来判断 p 是否落在这个块的范围之内。

← 异常控制流