背景
虚拟内存将用户逻辑内存与物理内存分离。在物理内存有限的情况下，为程序提供了巨大的虚拟内存。
随着动态内存分配，栈向下生长，堆向上生长。但实际上中间空余的虚拟空间并不真实占用物理内存。另外，一个进程可以有多个线程，每个线程有自己的栈，但它们共享一个堆。
虚存的实现方式：
- 按需分页
- 按需分段
按需换页（Demand Paging）
延迟交换器（Lazy swapper）：仅当需要页时把页换入内存。
页表项的有效位：指出页是否在内存。
若无效页被引用，则触发页故障（page fault）。
**EAT（有效访问时间）**计算：
页故障率 $p$
EAT = (1 – p) x memory access
+ p (page fault overhead
+ swap page out
+ swap page in
+ restart overhead
)
写时复制
Copy-on-Write (COW) 使得父子进程开始可以共享页，直到其中一方修改内存。
页面置换算法
页置换算法的思想在各种缓存系统中普遍应用。
我们可以将高速容器（如内存相对于磁盘）看作有限个槽。此数量即可用帧数。
基本页置换
假设需要换入一个新帧
- 有空闲帧，则使用它
- 否则，选择一个牺牲帧（victim frame）
- 将牺牲帧写入到低速容器，用新帧取代其原来位置
FIFO 页置换
用一个 FIFO 队列管理页。需要置换时，队头页被换出，新帧加入队尾。
缺点：Belady 异常
Belady 异常：使用 FIFO 算法时，会出现增加可用帧数，缺页率反而提高的现象。
个人认为，这种现象出现的本质原因是，死板 FIFO 导致将高频页面换出，从而命中率下降。使用栈可避免 Belady 异常。
最优页置换（OPT or MIN）
最优页置换置换距离最远的页。距离：下次执行所间隔的指令数。
缺点：无法预测未来。
最近最少使用页置换（LRU）
最近最少使用（Least Recently Used）。有多种实现方式。
基于计数器的实现：
- 建立一个时钟机制 clock
- 每个页表项关联一个时间域 refTime
- 每次引用
clock++,refTime [i] = clock
于是我们相当于记录了各页的上次访问时间。从而可以换出最老的页。
基于栈的实现：
严格来说是一个双端队列。容量固定，每次引用，若已存在，则对应页上浮。栈底是 LRU 页。
近似 LRU
附加引用位算法
内存的每个页有一个 8 位字节，记录了 8 个周期内的使用情况。
1100 0100 表示之前 1,2,6 个周期使用过，之前 3,4,5,7,8 个周期没有使用过。
第 2~7 位叫做历史位。
二次机会算法
当历史位降低到 0 时，即 1 个引用位，相当于二次机会（second chance）算法。
当要选择一个页时，检查其引用位。如果其值为 0, 那么就直接置换该页。如果引用位为 1, 那么就给该页第二次机会，并选择下一个 FIFO 页。当一个页获得第二次机会时，其引用位清零，且其到达时间设为当前时间。
简言之，增加一次访问位清零的机会。即检查表头（最老）页面的 R 位，是 0 则置换，不是 0 则清零然后放到表尾。
SC 优化了 FIFO 的错误淘汰常用页的频率。
增强型二次机会算法（NRU 页置换）
最近未使用算法使用了 引用位 和 修改位，根据这两个值分为 4 类，随机地从类编号最小队列中挑选一个页面淘汰之。
编号规则：访问 > 未访问，修改 > 未修改
第 0 类： 没有被访问， 没有被修改。
第 1 类： 没有被访问， 已被修改。
第 2 类： 已被访问， 没有被修改。
第 3 类： 已被访问， 已被修改。
CLOCK 页置换
优化了二次机会法经常操作链表的缺点。
所有的页面都保存在一个类似钟面的环形链表中， 一个表针指向最老的页面。
当发生缺页中断时， 算法首先检查表针指向的页面， 如果它的 R 位是 0 就淘汰该页面， 并把新的页面插入这个位置， 然后把表针前移一个位置； 如果 R 位是 1 就清除 R 位并把表针前移一个位置， 重复这个过程直到找到了一个 R 位为 0 的页面为止。
基于计数的页置换
最小使用频率页置换（LFU）
每次引用计数自增。
定期右移指数衰减。
最大使用频率页置换（MFU）
最差内存分配方案的泛化，认为如果页面的频率计数器很大，那么该页面已经拥有公平的内存份额，是时候轮到其他人了。
不幸的是，它不起作用。
内核内存分配
内核的内存来自于空闲内存池而非用户态进程的内存链表。原因：
- 内核需要为不同大小的数据结构分配内存。链表分配很容易产生碎片。
- 有的内核程序必须使用连续物理页。
伙伴分配器（Buddy 系统）
Buddy 系统分配物理上连续的段。使用 2^n 分配器。并且可以快速合并小段为大段（32 + 32 = 64）。
当请求 11KB，则分配 16KB。也正因此，容易产生内存碎片。
SLAB 分配器
课本讲得不好。建议看 SLAB 分配器和 kmalloc - 魅族内核团队 (meizu.com)
slab 分配器 | FreeFlyingSheep 的小站