当 cpu 访问到一个已分配但未缓存的页面时，触发 page fault，操作系统需要分配一个物理页帧。如果此时物理内存不足，就需要将部分页面交换到磁盘，然后将新的页面加载到内存。
为什么说是要分配一个物理页帧？
如果是 malloc 等动态分配内存的操作，只需要在内存中分配一个页帧，而如果还需要从磁盘加载数据的话，还需要将页面从磁盘加载到这个页帧中。
什么情况下会需要将页面换出？
当内存中的页帧不足，但是又需要分配新页帧时。
如果没有开启 swap，是否不会产生页交换？
理论上不会将页面交换到 swap 分区，也就不存在“页交换”。但是 linux 系统仍然有一些回收内存的机制，直接将一些页面丢弃掉，为新页面腾出空间，如：文件页回收，OOM Killer。
既然有页交换机制，为什么还会触发 OOM ？
- swap 空间不足
- 部分内存也不允许被换出，如：内核内存、mlock 锁定内存、共享内存等
当一个进程需要页交换时，应当换出哪个进程的页面？
都可以，由页面替换算法决定。
页交换涉及到磁盘 IO，性能损耗大，应当尽力避免不必要的页交换，这就需要合理选择被换出的页面。
如果频繁访问的页面被换出，CPU 很快又会访问它们，又需要将他们从 swap 加载回内存，导致不必要的性能损耗。
3.4.1 The Optimal Page Replacement Algorithm
“计算”每个页面到下一次被引用时需要经过的指令数，需要经过指令数最多的页面就是最晚被引用的，移除这个页面。
缺点：难以实现。无法确定每个页面的下一次访问时间。
3.4.2 The Not Recently Used Page Replacement Algorithm
么个虚拟页都有两个标志位：
- R：页面是否被访问（读或者写）
- W：页面是否被写入
每次内存引用时都必须更新这两个标志位，这就有必要通过硬件来实现。如果硬件不支持，可以通过软件模拟（page fault & clock interrupt）。操作系统定期复位 R 标记位，用来标识近期哪些页面被访问。
进程启动时，所有的页面都不在内存中。发生 page fault 后，将页面加载到内存中，将 R 标志位置位，此时页面处于 Read Only 模式。如果之后页面被修改，将 M 标志位置位，页面可以被读写。
根据 R/M 标记位，将页面分为四类，需要替换页面时，从换出优先级最高的一类页面中随机选择一个页面换出。
| R | M | 换出优先级 | |
|---|---|---|---|
| Class 0 | 0 | 0 | 最高 |
| Class 1 | 0 | 1 | 高 |
| Class 2 | 1 | 0 | 低 |
| Class 3 | 1 | 1 | 最低 |
3.4.3 The First-In, First-Out (FIFO) Page Replcaement Algorithm
操作系统维护一个队列来保存页面，新页面从队列尾部入队，当需要替换页面时，移除队列首部的页面。
FIFO 算法没有考虑到页面访问的频率。当内存引用访问到一个已经在队列中的页面时，页面在队列中的顺序不变，所以队首的页面可能是一个被频繁访问的页面，不应当被替换出去。
3.4.4 The Second-Chance Page Replacement Algorithm
对 FIFO 算法改进：使用 R 标志位记录当前页面是否被使用。
- 当页面被引用时，R 标志位置位
- 当一个页面将要被替换出去时，如果 R 标志位置位，就清除 R 标志位，并将页面放在队列尾部，修改页面的加载时间为当前时间，否则换出页面。
通过上述算法，始终可以找到内存中最老且最近没有被访问的页面，然后将这个页面替换出去。
当队列中的所有页面的 R 标志位都置位时，该算法会退化为 FIFO 算法。
3.3.5 The Clock Page Replacement Algorithm
Second-Chance 算法的性能有一些小瑕疵，完全没有必要移动链表的节点。
Clock 算法将 Second-Chance 算法的链表替换为循环链表，使用一个指针指向最老的一个页面。当发生 page fault 时：
- 如果指针指向的页面 R 标志位为 0，就替换该页面
- 如果指针指向的页面 R 标志位为 1，标志位复位，指针指向下一个页面，直到找到 R 为 0 的页面
3.4.6 The Least Recently Used (LRU) Page Replacement Algorithm
原理：时间局部性原理，最近经常使用的指令在接下来的一段时间内大概率也会被使用，反之亦然。
基于这一原理的 LRU 算法，在需要替换页面时，换出最久未使用的页面。
LRU 的页面替换效率接近 Optimal 算法，但是实现复杂并且代价昂贵。
- 需要在内存中维护一个记录了所有页面使用频率的有序链表
- 每次发生内存引用时，都需要更新链表
- 在链表中删除节点、移动节点等操作都是昂贵的
可以凭借特殊的硬件实现 LRU。用一个 64 bit 的计数器，在每次执行指令后自增一。每个页表项保留一个字段，在每次内存引用后保存计数器的值，作为这个页面最后一次被访问的时间戳。
当发生 page fault 时，找到时间戳最小的页面，替换出去。
3.4.7 Simulating LRU in Software
使用 NFU (Not Frequently Used) 算法软件化模拟 LRU。
每个页面都有一个独立的计数器（counter），发生时钟终端时，扫描内存中的所有页面，如果 R 标志位为 1 则 counter++。当发生 page fault 时，淘汰 counter 最小的页面。
NFU 算法存在一个致命缺陷，如果或一个页面早期使用频繁，但是近期不怎么使用，它的 counter 依然会很高，在 page fault 时，可能会将近期频繁使用的页面替换出去。
在此基础上，aging 算法做了改进，在统计页面使用频率时，先将 counter 右移一位，然后将 R 标志位放到 counter 的最高位。这样 counter 从最高位到最低位，依次表示最近的某个时钟周期内，该页面是否被使用过，由此反映出这个页面最近的使用情况。
\(counter = (counter >> 1) | (R << (n-1))\)（n 为 counter 的位数）
当发生 page fault 时，依然选择 counter 最小的页面淘汰掉。距离现在越近的页面，它在 counter 中的位置越高，所占的权重越大。