虚拟内存

系统中的进程与其他进程共享CPU和主存。首先进程多需要的内存也多，其次内存易被破坏，如进程A不小心写入进程B使用的内存。为更有效管理内存且少出错，系统提供对主存的抽象概念叫虚拟内存。虚拟内存是硬件异常、硬件地址翻译、主存、磁盘文件和内核的完美交互，为每个进程提供大的、一致的和私有的地址空间，虚拟内存提供三个重要能力：

1. 使用主存更有效率：用 DRAM 作为部分的虚拟地址空间的缓存
2. 简化内存管理：每个进程都有统一的线性地址空间
3. 隔离地址空间：进程间不会相互影响；用户程序不能访问内核信息和代码

1 地址空间

物理地址通常应用在“简单”的嵌入式微控制器中（汽车、电梯等），内存管理较简单，但现代计算机，包括其他智能设备如笔记本电脑、智能手机等，需要较复杂的内存管理机制，因此虚拟地址必不可少，它是计算机科学中最伟大的ideas之一。

2 虚拟内存作为缓存工具

概念上来说，虚拟内存就是存储在磁盘上的 N 个连续字节的数组。磁盘上数组的内容被缓存在物理内存上（DRAM缓存）），其中的每个缓存块(cache block)就称为页(page)，如下图所示：

任何时刻，虚拟页都可分为三个部分：

• 未分配的：VM系统还未分配或创建的页，不占用任何磁盘空间
• 缓存的：已缓存在主存中的已分配的页
• 未缓存的：未缓存在物理内存中的已分配页

具体看上图：0和3未分配，1、4、6被缓存在物理内存，2、5、7被分配但未缓存在主存

2.1 DRAM缓存组织

和之前的 cache memory类似，将访问速度快的作为访问速度慢的缓存，利用DRAM比磁盘快一万倍，将磁盘数据尽量缓存在DRAM中（同样DRAM比SRAM慢10倍，也可将SRAM作为缓存），所以需尽可能从 DRAM中拿数据。为此需要：

• 更大的页尺寸(page size)：通常是 4KB，Linux"huge pages"是2M到1G
• 全相联(Fully associative)：每一个虚拟页(virual page)可以放在任意的物理页(physical page)中，映射函数很复杂，不同于缓存，无法在硬件中实现，置换算法较昂贵
• 通常使用 Write-back 而非 Write-through 机制
  • Write-through: 命中后更新缓存，同时写入到内存中
  • Write-back: 直到这个缓存需要被置换出去，才写入到内存（需dirty bit表示缓存中数据是否和内存中相同，因为可能某时刻内存中对应地址的数据已更新，重复写入就会导致原有数据丢失）

2.2 页表

页表是一个元素为页表项(PTE, page table entry)的数组，页表项把虚拟页映射到物理页上。PTE由1个有效位和n个地址字段组成。在 DRAM 中，每个进程都有自己的页表，具体如下：

2.2.1 页命中

访问的虚拟地址的页在DRAM缓存中，则叫页命中，命中时由于在 DRAM 中有对应的数据，可直接访问。不命中时，由于DRAM中没有对应数据，所以需从磁盘复制到DRAM中，具体为：

• MMU触发 Page fault异常
• 将模式升级为内核模式
• 调用软件页面错误处理程序
• Page fault handler选择DRAM中要被置换的page，并把数据从磁盘复制到DRAM中，复制的等待时间称为demand paging
• 重新执行访问指令，这时候就会是page hit

2.2.2 处理页错误

在磁盘和内存之间传送页的活动叫交换或页面调度。页从磁盘换入（或页面调入）DRAM和从DRAM换出（或页面调出）磁盘。一直等待直到最后时刻，当不命中发生时才换入页面的策略叫按需页面调度，所有现代操作系统都使用按需页面调度方式。

2.2.3 完成页错误

页错误处理程序执行返回中断指令（iret）返回：

• 像ret指令但恢复特权级别
• 返回造成错误的指令

2.2.4 分配页

只有当出现 page fault 的时候才将数据拷贝到内存，即按需页面调度

2.2.5 局部性原理

• 虚拟内存看起来不高效，但因局部性原理，虚拟内存非常高效
• 任何时刻程序都倾向于访问一组称为工作集的活动的虚拟页，局部性越好程序工作集越小
  • 工作集大小<内存大小，进程有良好性能
  • 工作集大小>内存大小，多个进程同时运行，页面不断被交换（复制）进或出，也叫抖动

3 作为内存管理工具

每个进程都有自己的虚拟地址空间，这些地址空间可以看作是简单的线性空间（但实际上在物理内存中可能是间隔、分散的），映射函数通过物理内存分散地址，好的映射函数可提升局部性，具体的映射过程如图：

作为内存管理工具：

• 简化内存分配：每个虚拟页都可被映射到任何物理页上。虚拟页可在不同时间存在不同物理页上
• 简化共享：每个进程都有自己私有的代码、数据、堆及栈不与其他进程共享，为操作系统提供进程和系统间共享代码和数据的机制，映射不同进程的虚拟页到同样的物理页（也就是上图 PP 6 的状况，只读）
• 简化链接和加载：每个程序有相同的抽象，有相似的虚拟地址空间，Code、data、heap段开始于相同的地址；execve为.text和.data节分配虚拟页并创建标记为invalid的页表项（PTEs）；根据虚拟内存系统的需要将.text和.data段逐页复制

4 作为内存保护工具

任何现代计算机系统必须为操作系统提供手段控制对内存系统的访问，不应允许进程修改只读代码段，也不许读或修改任何内核中的代码和数据结构。不许读或改其他进程私有地址，不许改任何与其他进程共享的虚拟页面，除非所有共享者都显式允许这么做（通过调用明确的进程间通信系统调用）

使用权限位扩展PTEs，高位是表示权限的位，MMU 检查这些位进行权限控制（读、写、执行），如下图所示：

5 地址翻译

5.1 地址翻译符号

地址空间可分为：

• 线性地址空间：连续非负整数地址的有序集合，{0, 1, 2, 3 … }
• 虚拟地址空间：N=2^n的虚拟地址集合，{0, 1, 2, 3, …, N-1}
• 物理地址空间：M=2^m的物理地址集合，{0, 1, 2, 3, …, M-1}

地址翻译：MAP: V → P U {}

• MAP(a) = a’：若虚拟地址a中的数据在P中的物理地址a '上
• MAP(a) = {}：若虚拟地址a中的数据不在物理内存中（无效或存储在磁盘）

开始之前先来了解以下参数：

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

虚拟地址(VA, Virtual Address)中的元素：

• TLBI：TLB索引
• TLBT：TLB标记(tag)
• VPO：虚拟页偏移量
• VPN：虚拟页号

物理地址(PA, physical address)中的元素：

• PPO：物理页偏移（与 VPO 的值相同）
• PPN：物理页号
• CO：缓存偏移字节
• CI：缓存索引
• CT：缓存标签

5.2 用页表进行地址翻译

具体的访问过程为：

1. 通过虚拟地址找到页表(page table)中对应的条目
2. 检查有效位(valid bit)，是否需要触发页错误(page fault)
3. 根据页表中的物理页编号(physical page number)找到内存中对应地址
4. 把实际地址和虚拟页偏移(virtual page offset)拼接即为最终的物理地址

这里又分两种情况：Page Hit 和 Page Fault

5.2.1 page hit

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

5.2.2 page fault

1. 处理器生成一个虚拟地址，并把它传给MMU
2. MMU生成PTE地址，并从高速缓存/主存请求得到它
3. 高速缓存/主存向MMU返回PTE
4. 有效位为零，所以MMU触发页故障异常，传递CPU控制到系统内核中缺页异常处理程序
5. 处理程序寻找被置换页(如果页脏，则将其换出到磁盘)
6. 处理程序从磁盘找到对应页并载入内存/缓存并更新内存中的PTE
7. 处理程序返回到原始进程，重启出错指令，CPU将引起缺页的虚拟地址重新发给MMU，由于已缓存在主存故会命中

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

在既有虚拟内存又有SRAM高速缓存的系统中，是使用虚拟地址还是物理地址访问SRAM高速缓存的讨论有很多，但大多数系统用物理寻址，这样多个进程共享虚拟页和存储的值，无需处理保护问题，因为访问权限的检查是地址翻译过程的一部分。虽然缓存已经很快了，但还能更快，主要思路是地址翻译发生在高速缓存查找之前，直接在 MMU和内存之间加上L1缓存，于是就有了另外一种设计，如图：

页表条目(PTE)像任何其他内存中的数据一样缓存在L1中，PTE可能被其他数据驱逐；PTE命中仍然需要一个小的L1延迟，解决办法是使用Translation Lookaside Buffer(TLB)。TLB可以认为是页表在处理芯片上的缓存，是MMU中的小型集关联硬件缓存，将虚拟页号映射到物理页号，大多数页表条目位于L1高速缓存，但被称为TLB的页表条目的片上高速缓存，包含少量页的完整页表条目，通常回消除访问L1上的页表条目的开销。MMU使用虚拟地址的VPN部分位访问TLB：

如图是TLB命中和不命中的两种情况：

若TLB不命中时，MMU必须从L1缓存中取出相应的PTE，新取出的PTE存放在TLB中可能覆盖已存在的条目（这里未画出L1缓存，下面Interl Core i7部分画出cpu中的L1缓存和MMU的TLB）

这里顺便复习下前面的缓存结构：

这里 VPN + VPO 就是虚拟地址，同样分成三部分，分别用于匹配标签、确定集合，若TLB命中，直接返回对应页表项(PTE)，否则，就要从缓存/内存中获取，并更新 TLB 的对应集合。幸好不命中很少发生

5.4 多级页表

因为虚拟地址的位数比物理内存的位数要大得多，所以保存页表项(PTE) 所需要的空间也是一个问题。例如：

假设每个页的大小是 4KB（2的12次方），每个地址有 48 位，一条 PTE 记录有 8 个字节，那么要全部保存下来，需要的大小是：

2^48×2−12×2³⁼²39bytes = 512G

所以采用多层页表，第一层的页表中的条目指向第二层的页表，一个一个索引下去，最终寻找具体的物理地址，如图是二级页表：

K级页表翻译过程如下：

5.5 地址翻译实例

来看一个简单的例子，我们的内存系统设定如下：

• 虚拟地址14 位
• 物理地址12 位
• 页大小 64 字节

简单内存系统的TLB的配置为：

• 存储 16 条记录
• 4个集合

简单内存系统页表：

简单内存系统缓存：

• 16 行，每个块 4 个字节
• 物理地址
• 直接映射（即 16 个集合）

虚拟地址：0x03D4，在TLB中找到index为3的set，且其tag为3的PPN为0D，加上前面的虚拟地址的VPO即为最终的物理地址

得到物理地址，在缓存中找到idx为，tag为0D，且CO为0，则值为36

虚拟地址为0x0020，虽然TLB中去找到编号为0的set且tag为0的缓存，但为0，所以TLB Miss了，从页表中找到缓存PPN为2，则物理地址为0x0A20

接下来找到idx为8的缓存，但tag不匹配，故未命中缓存，只能重新读取

5.6 Intel Core i7内存系统

5.6.1 Intel Core i7 内存翻译

5.6.2 Core i7 1-3层页表项

5.6.3 Core i7 4级页表项

5.6.4 加速技巧

将1）MMU将地址翻译成物理地址2）将物理地址传送到L1高速缓存。这两步骤部分重叠，故也加速对L1高速缓存的访问。

• 在虚拟地址和物理地址中确定CI的位
• 当地址翻译时，可以将索引存入缓存
• 通常用TLB，PPN位（CT位）可很快得到
• 虚拟索引，物理标记
• 仔细调整缓存大小

6 Linux进程中的虚拟地址

Linux为每个进程维护单独的虚拟地址空间，包括内核虚拟内存和进程虚拟内存。前者某些区域被映射到所有进程共享的物理页面，如每个进程共享内核的代码和全局数据结构。有趣的是，Linux也将一组连续的虚拟页面（大小等于系统中DRAM的总量）映射到相应的一组连续的物理页面，为内核提供便利的方法访问物理内存中特定位置。

6.1 Linux将虚拟内存组织为“区域”集合

Linux将虚拟内存组织称一些区域（也叫段）的集合，区域就是已经存在着的（已分配的）虚拟内存的连续片，这些页以某种方式相关联。如代码段、数据段、堆、共享库段以及用户栈都市不同区域，每个存在的虚拟页都抱存在某个区域中，而不属于某个区域的虚拟页是不存在的，且不能被进程引用。区域的概念很重要，因为它允许虚拟地址空间有间隙，内核不用记录那些不存在的虚拟页，而这样的页也不占用内存、磁盘或内核本身中的任何资源。

6.2 Linux页异常处理

缺页异常步骤：

1. 虚拟地址A是否和法：缺页处理程序搜索区域结构的链表，把A和每个区域结构中的vm_start和vm_end做比较，若该指令不合法，则缺页处理程序就出发一个段错误，从而终止该进程，对应下图中的1
2. 内存访问是否合法：进程是否有读、写或执行这个区域内页面的权限，如是不是因为运行在用户模式的进程试图从内核虚拟内存中读取字造成，若访问不合法则触发缺页异常，从而终止该进程，对应图中的2
3. 合法虚拟地址进行合法操作：按调度算法选择一个页，若该页被修改过，将其交换出去换入新页并更新页表。缺页处理程序返回时，CPU重新启动引起缺页的指令，该指令再次发A到MMU，这次就能正常翻译A

6.3 内存映射

将虚拟内存的areas与磁盘对象关联并初始化的机制叫内存映射。area可通过磁盘的普通文件（如可执行文件），初始化来自文件的一部分为页，或者匿名文件，首次错误将分配一个写满0的物理页，一旦页被写（脏）就跟其他页一样。无论哪种情况，一旦虚拟页面被初始化了，它就在由内核维护的专门的交换文件间换来换取，任何时刻，交换空间都限制着当前运行着的进程能分配的虚拟页面的总数。

6.3.1 共享对象

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

很多进程都有同样的只读代码区域，且许多程序需访问只读运行时库代码的相同副本，如每个C程序都需标准C库的printf函数，若每个进程都在主存中保持这些代码的副本，就极端浪费。

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

多个进程可共享相同的对象，虚拟地址可以有差异，但差异必须是页大小的倍数

6.3.2 私有的写时复制对象

对于每个映射私有对象的进程，相应私有区域的页表条目都被标记为只读，且该区域被标记为私有的写时复制。一旦写入则触发保护错误，处理程序在主存中创建试图写私有的写时复制区域中的一个页面该页面的信服本，更新页表条目指向该新副本，再恢复该页面可写权限。指令在处理程序返回时重新执行，拷贝尽可能被推迟。

再看fork函数，当被当前进程调用时，创建当前进程的mm_struct、区域结构和页表的原样副本。将两个进程中的每个页面都标记为只读，并将两进程中每个区域结构都标记为私有的写时复制。fork返回时，新进程虚拟内存和调用fork时存在的虚拟内存相同，当两进程中任一个后来进行写操作，写时复制机制就创建新页面，因此也就为每个进程保持私有地址空间的抽象概念。

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

• 删除已存在的用户区域：删除当前进程虚拟地址的用户部分中的已存在的区域结构

• 映射私有区域：为新程序代码、数据、bss和栈区域常见新的区域结构，所有这些新区域都是私有的、写时复制的

• 映射共享区域：若a.out程序与共享对象链接，先动态链接，再映射到用户虚拟地址空间中的共享区域内

• 设置程序计数器：设置当前进程上下文中的程序计数器，使之指向代码区域入口点

6.3.3 找到可共享的页

内核相同页归并：

• 系统扫描所有物理内存，寻找重复页，找到则归并为单个页，标记为写时拷贝
• 在2009年的Linux内核实现，仅限于标记为可能的页，特别是处理器运行许多虚拟机时特别有用

6.3.4 用户模式的内存映射

函数void *mmap(void *start, int len,int prot, int flags, int fd, int offset)，从文件描述副fd指定的文件偏移量offset，从start地址（可能为0）开始映射len字节，prot表示权限（PROT_READ、PROT_WRITE、 PROT_EXEC），flags表示映射权限（MAP_ANON、 MAP_PRIVATE、MAP_SHARED等），返回映射区域开始的指针（可能不是start）

6.3.5 mmap的使用

使用分页机制将大文件读入内存，共享数据结构，当调用带MAP_SHARED的标签时，多进程可访问相同内存区域，很危险。基于文件的数据结构例如数据库，将prot设置为PROT_READ和PROT_WRITE，当解除映射时，文件通过写入被更新，通过文件加载/更新/写回文件实现。

6.3.6 用mmap实现attack lab

当机器堆栈不能执行时，如何通过代码注入进行攻击，解决方法是使用mmap分配内存并标记为可执行，转移堆栈到该区域，执行攻击代码，恢复原来堆栈，移除映射区域。

7 动态内存分配

程序员通过动态内存分配器（如 malloc）让程序在运行时得到虚拟内存，因为程序经常直到实际运行时才知道某些数据结构大小。动态内存分配器管理一个虚拟内存区域，称为堆(heap)。

分配器以块为单位来维护堆，可分配或释放。有两种类型的分配器：

• 显式分配器：应用分配并且回收空间（C 语言中的 malloc 和 free）
• 隐式分配器：应用只负责分配，但是不负责回收（Java 中的new和垃圾收集）

7.1 相关函数

• malloc：失败返回空指针并设置errno=ENOMEM，成功返回指向至少请求字节大小的内存块的指针
• free：将参数p指向的块返回到可用内存池，p必须来自先前调用的malloc、calloc、realloc
• calloc：将已分配的块初始化为0的malloc版本
• realloc：改变先前分配的快的大小
• sbrk：分配器内部使用，用于增加或缩小堆

先来看看一个简单的使用 malloc 和 free 的例子

#include <stdio.h>
#include <stdlib.h>

void foo(int n) {
    int i, *p;
    
    /* Allocate a block of n ints */
    p = (int *) malloc(n * sizeof(int));
    if (p == NULL) {
        perror("malloc");
        exit(0);
    }
    
    /* Initialize allocated block */
    for (i=0; i<n; i++)
        p[i] = i;

    /* Return allocated block to the heap */
    free(p);
}

为了讲述方便，我们做如下假设：

• 内存地址按照字来编码
• 每个字的大小和整型一致

例如：

可以用任意的顺序发送 malloc 和 free 请求，但free 请求必须作用与已被分配的 block。

显式分配器的限制：

• 不能控制已分配块的数量和大小
• 必须立即响应 malloc 请求（不能缓存或者给请求重新排序）
• 必须在未分配的内存中分配
• 不同的块需要对齐（32 位中 8 byte，64 位中 16 byte）
• 只能操作和修改未分配的内存
• 不能移动已分配的块，不允许压缩，为什么？

7.2 性能指标

假设给定 malloc 和 free 的请求的序列：

R0,R1,…,Rk,…,Rn−1R0,R1,…,Rk,…,Rn−1

目标是尽可能提高吞吐量以及内存利用率（注意，这两个目标常常是冲突的）

吞吐量是在单位时间内完成的请求数量。假设在 10 秒中之内进行了 5000 次 malloc 和 5000 次 free 调用，那么吞吐量是 1000 operations/second

另外一个目标是 Peak Memory Utilization，就是最大的内存利用率。其次最小化开销，定义总负载Pk表示请求Rk完成时的当前已分配的载荷之和，当前堆大小Hk（假定Hk是单调非递减），则K+1次请求的开销Ok = Hk / (maxi≤k P i ) – 1.0

7.3 内存碎片

影响内存利用率的主要因素就是『内存碎片』，分为内部碎片和外部碎片两种。

内部碎片

内部碎片指的是存储的数据(payload)小于块大小，就会因对齐和维护堆所需的数据结构或明确的决策（如返回大块满足小的请求）的缘故而出现无法利用的空间，例如：

内部碎片只依赖于之前的请求的具体模式

外部碎片

内存中有足够的空间，但是空间不连续，所以成为了碎片，取决于未来请求的模式

实现细节

如何实现高效的内存分配算法？在具体实现之前，需要考虑以下问题：

• 给定一个指针，如何知道需要释放多少内存？
• 如何记录未分配的块？
• 当分配的结构小于所在的空闲块时，如何处理多余的空间?
• 有多个区域满足条件，如何选择？
• 如何重用已经释放的块？

如何实现回收

标准方法：在块开头记录块的长度（包括块头），每个分配的块需额外的字节

具体这部分书中提到了四种方法：

1. 隐式列表 Implicit List：在首部记录长度，链接所有块
2. 显式列表 Explicit List：用指针的空闲块的显式列表
3. 分离的空闲列表 Segregated Free List：不同大小的不同链表
4. 按大小对块排序 Blocks Sorted by Size：使用平衡树（如红黑树），每个空闲块都有指针，长度作为键

8 跟踪自由块

8.1 隐式空闲列表

每个块都记录大小和分配状态，只需一个字节，当块对齐时，一些低阶地址位总是0，与其存储始终为0的位，不如将其作为已分配/空闲标志。当读取Size字节时，必须屏蔽该位

8.1.1 数据结构

8.1.2 头访问

8.1.3 遍历链表

8.1.4 找到一个空闲块

如何确定哪部分空间合适，有三种方法：

1. First Fit: 每次都从头进行搜索，找到第一个合适的块，线性查找
2. Next Fit: 每次从上次搜索结束的位置继续搜索，避免重复搜索没有帮助的块，速度较快，但可能会有更多碎片，一些研究表明碎片化教糟糕
3. Best Fit: 每次遍历列表，找到剩余字节最少最合适的块，碎片较少，通常可提高内存利用率，但是速度最慢，仍是贪婪算法，没最优保证

8.1.5 分配空闲块

由于已分配空间可能小于空闲空间，可以分割块

8.1.6 释放块

最简单的实现方式是清除“已分配”的标记，但可能导致错误的碎片化

8.1.7 合并

若下一个/前一个块是空闲的，则连接合并

8.1.8 双向合并

在前面的基础上，在空闲块的“底部”记录块的大小，允许反向遍历列表，但需额外空间，边界标签（Knuth73）

8.1.9 通过footers实现

8.1.10 常数时间合并

总共四种情况，这里以第一种为例：

注意：对于头和尾需要加上"dummy footer"，标记为已分配，防止在释放第一块和最后一块时意外合并

8.1.11 高层malloc/free代码

malloc/free不常用，因为线性时间分配，多用于特殊目的应用

const size_t dsize = 2*sizeof(word_t);
void *mm_malloc(size_t size)
{
    size_t asize = round_up(size + dsize, dsize);
    block_t *block = find_fit(asize);
    
    if (block == NULL)
    	return NULL;
    
    size_t block_size = get_size(block);
    write_header(block, block_size, true);
    write_footer(block, block_size, true);
    
    split_block(block, asize);
    
    return header_to_payload(block);
}
void mm_free(void *bp)
{
    block_t *block = payload_to_header(bp);
    size_t size = get_size(block);
    
    write_header(block, size, false);
    write_footer(block, size, false);
    
    coalesce_block(block);
}

8.1.12 边界标签缺点

导致内部碎片，footer标签能被优化，未使用一位代表已分配/未分配，除次之外使用多一位表示前一块是否分配

也有四种情况，这里以第一种情况为例：

8.2 显式空闲列表

维护空闲列表块，而不是所有块，下一个/上一个空闲块可能在任何地方，所以需存储前向/后向指针，而不仅是块大小，合并仍需边界标签，根据记忆顺序找到相邻的块

8.2.1 释放块

在空闲列表的什么地方放新释放的块？

• 无序：LIFO（Last in First out）、FIFO（First in First out），简单但花费时间，研究表明碎片化比按地址序更糟
• 地址序：插入空闲块，以便空闲块总按地址顺序排列，需搜索

同样对于释放内存块也有4种情况，这里以第四种情况做简要说明：

8.2.2 一些实现的技巧建议

使用循环双向链表，但数据结构支持多种方法，要么保持自由指针固定要么作为搜索列表移动

8.2.3 显式空闲列表总结

分配是空闲块数量的线性时间，而不是所有块。由于需在列表中插入和取出块，因此分配和自由更复杂。但需要额外的链接空间

8.3 分割列表分配器

每个大小块类都有自己的空闲列表

8.3.1 分割分配器

给定一个自由列表数组，每个都是一定大小的类，分配一个大小为n的块，搜索大小为m>n的块，若找到合适的块，分割块并放碎片在适当的列表，若没有块被发现，尝试下个更大的种类。重复直到块被找到。用sbrk从系统请求额外的堆内存，从该新内存分配n个字节的块，将剩余的块作为一个单独的空闲块放在适当大小的类中。

8.3.2 分割分配器优点

• 更高的吞吐量：种类大小的2次幂的对数时间vs线性时间
• 更好的内存利用率：对隔离的自由列表的First-fit搜索近似对整个堆的最佳搜索；极端情况是给每个块一个自己的大小的类相当于best-fit

8.4 内存陷阱

关于内存的使用需要注意避免以下问题：

• 解引用错误指针
• 读取未初始化的内存
• 覆盖内存
• 引用不存在的变量
• 多次释放同一块
• 引用已释放的块
• 释放块失败

8.4.1 解引用错误指针

没有引用对应的地址，少了 &

int val;
...
scanf("%d", val);

8.4.2 读取未初始化的内存

不能假设堆中的数据会自动初始化为 0，如：

/* return y = Ax */
int *matvec(int **A, int *x) {
    int *y = malloc(N * sizeof(int));
    int i, j;
    
    for (i = 0; i < N; i++)
        for (j = 0; j < N; j++)
            y[i] += A[i][j] * x[j];
    return y;
}

8.4.3 覆盖内存

第一种是分配错误的大小，下面的例子中，一开始不能用 sizeof(int)，因为指针的长度不一定和 int 一样。

int **p;
p = malloc(N * sizeof(int));

for (i = 0; i < N; i++) 
    p[i] = malloc(M * sizeof(int));

第二个问题是超出分配的空间，下面代码的 for 循环中，因为使用了 <=，会写入到其他位置

int **p;

p = malloc(N * sizeof (int *));

for (i = 0; i <= N; i++)
    p[i] = malloc(M * sizeof(int));

第三种是因为没有检查字符串的长度，超出部分就写到其他地方去了（经典的缓冲区溢出攻击也是利用相同的机制）

char s[8];
int i;

gets(s); /* reads "123456789" from stdin */

第四种是没有正确理解指针的大小以及对应的操作，应该使用 sizeof(int *)

int *search(int *p, int val) {
    while (*p && *p != null)
        p += sizeof(int);
    
    return p;
}

第五种是引用了指针，而不是其指向的对象，下面的例子中，*size-- 一句因为 -- 的优先级比较高，所以实际上是对指针进行了操作，正确的应该是 (*size)--

int *BinheapDelete(int **binheap, int *size) {
    int *packet;
    packet = binheap[0];
    binheap[0] = binheap[*size - 1];
    *size--;
    Heapify(binheap, *size, 0);
    return (packet);
}

8.4.4 引用不存在的变量

下面的情况中，没有注意到局部变量会在函数返回的时候失效（所以对应的指针也会无效），这是传引用和返回引用需要注意的，传值的话则不用担心

int *foo() {
    int val;
    
    return &val;
}

8.4.5 多次释放同一块内存

这个不用多说，不能重复搞两次

x = malloc(N * sizeof(int));
//  <manipulate x>
free(x);

y = malloc(M * sizeof(int));
//  <manipulate y>
free(x);

8.4.6 引用已释放的块

同样是很明显的错误，不要犯

x = malloc(N * sizeof(int));
//  <manipulate x>
free(x);
//  ....

y = malloc(M * sizeof(int));
for (i = 0; i < M; i++)
    y[i] = x[i]++;

8.4.7 内存泄漏

用完没有释放，就是内存泄露啦

foo() {
    int *x = malloc(N * sizeof(int));
    // ...
    return ;
}

或者只释放了数据结构的一部分：

struct list {
    int val;
};

foo() {
    struct list *head = malloc(sizeof(struct list));
    head->val = 0;
    head->next = NULL;
    //...
    free(head);
    return;
}

9 垃圾回收

垃圾回收自动回收堆分配的存储，程序不必显式地释放内存，这种机制在许多动态语言中都有实现：Python, Ruby, Java, Perl, ML, Lisp, Mathematica。C 和 C++ 中也有变种，但是注意，不可能回收所有垃圾。

如何知道什么东西才是垃圾？只要没有任何指针指向的地方，不管有没有用，因为都不可能被使用，当然可以直接清理掉。不过这其实是需要一些前提条件的：

• 可以知道哪里是指针，哪里不是指针
• 每个指针都指向 block 的开头
• 指针不能被隐藏(by coercing them to an int, and then back again)

相关算法如下：

• Mark-and-sweep collection (McCarthy, 1960)
• Reference counting (Collins, 1960)
• Copying collection (Minsky, 1963)
• Generational Collectors(Lieberman and Hewitt, 1983)

9.1 Mark&Sweep垃圾收集器

可在malloc/free包之上构建，用malloc分配直到空间耗尽。当空间不足时，在每个块的头用额外的标记位标记，标记阶段标记出根节点所有可达的和已分配的后继，在每个可达的块上设置标记位，后面的清除释放每个未被标记的已分配块

9.2 简单实现

• 应用：

  • new(n)：返回指向清除所有位置的新块的指针
  • read(b,i)：读块b在i处的值到寄存器
  • wreite(b,i,v)：写v到块b的i处

• 每个块都有一个头：块b的头的地址是b[-1]，在不同的收集器中用于不同目的

• 垃圾收集器使用的指令：is_ptr(p)检测p是否是指针，length(b)返回块b的长，不包括头，get_roots()返回所有的roots

10 总结

首先介绍虚拟内存等方面的知识，具体来说：

• 从程序员角度看虚拟内存：
  • 每个进程有自己的私有线性地址空间
  • 不能被其他进程破坏
• 从系统角度看虚拟内存：
  • 通过缓存虚拟内存页更有效地使用内存（局部性原理）
  • 简化内存管理和编程，提供方便的位检查权限，简化内存保护
• 组合硬件和软件实现：
  • MMU、TLB、各种控制寄存器、异常处理机制是硬件部分
  • 管理页表、页置换算法、管理文件系统、页异常处理、TLB管理是OS软件部分

其次简要介绍了动态内存分配的基本概念和管理动态内存分配的三种算法。最后提及了垃圾回收的基本原理和内存使用中常见的错误。