页面置换与内存分配¶

当可用页框不足时，系统必须选择哪些页面继续驻留、哪些页面回收。页面置换是策略问题：硬件提供访问位、脏位和异常等机制，操作系统据此近似判断未来最有价值的页面。

为什么不能等内存完全耗尽再处理¶

缺页处理、文件写回和设备驱动本身都可能需要内存。若系统到最后一页才回收，容易陷入无法为回收路径分配资源的困境。实际系统通常维护低水位和高水位，在压力达到阈值前后台回收，极端情况下再同步回收。

局部性与工作集¶

程序访问通常具有：

时间局部性：刚访问的数据近期可能再次访问。
空间局部性：附近地址可能接着访问。

在时间窗口 \(\Delta\) 内被访问的页面集合称为一个工作集近似：

\[ W(t,\Delta)=\{p\mid p\text{ 在 }(t-\Delta,t]\text{ 内被访问}\}. \]

若活跃进程的工作集总和长期超过物理内存，系统会频繁换入换出，CPU 大量时间等待缺页，形成抖动。

理想算法与可实现算法¶

OPT¶

淘汰未来最晚才会再次访问的页面。它给出理论最优基线，但需要知道未来访问序列，在线系统无法实现。

FIFO¶

淘汰最早进入内存的页面。实现简单，却不考虑使用频率和近期性，还可能出现分配更多页框反而缺页更多的 Belady 异常。

LRU¶

淘汰最长时间未访问的页面，利用时间局部性近似未来。精确维护每次内存访问顺序成本过高，因此系统通常使用硬件访问位和近似队列。

Clock / Second Chance¶

页面按环排列，指针扫描候选：

若 accessed == 0：选择回收
若 accessed == 1：清零并跳过，给第二次机会

它近似 LRU，维护成本较低。实际系统还会区分匿名页、文件页、活跃/非活跃队列和脏页写回状态。

一个页面序列例子¶

访问序列：

1 2 3 1 4 1 2 5

只有 3 个页框时，可以手工模拟 FIFO 与 LRU。关键不是记最终数字，而是每一步写出：当前页框、命中/缺页、被淘汰页和算法依据。这样能发现 FIFO 只看进入时间，LRU 则会保留最近再次访问的 1。

脏页与干净页¶

干净文件页已与持久化文件一致，可丢弃，之后再从文件读取。
脏文件页必须先写回，或保留到写回完成。
匿名页没有原始文件后备，若要腾出内存通常需交换空间，或在确定可重建时丢弃。

回收算法不仅看“多久没访问”，还要考虑写回成本。若总偏爱干净页，可能保留大量冷脏页；若立即同步写回，又会增加前台延迟。因此系统常把选择和异步写回配合。

局部置换与全局置换¶

局部置换只从发生缺页的进程已分配页中选择，隔离性较强，但空闲页难动态流向活跃进程。
全局置换从全系统候选中选择，提高总体利用率，却可能让一个进程的突发访问驱逐其他进程工作集。

实际系统会结合进程/控制组限制、优先级和全局压力，在效率与隔离之间折中。

抖动怎样形成¶

工作集不驻留
  -> 频繁缺页
  -> 页面读入
  -> 为腾空间又淘汰仍活跃页面
  -> 很快再次访问被淘汰页
  -> 更多缺页和 I/O

增加并发任务不一定提高利用率。当总工作集超过内存，额外任务会放大缺页和 I/O，使 CPU 利用率反而下降。

缓解方式包括：

降低多道程序度或限制并发。
增加内存。
改善数据访问局部性。
为关键工作负载设置内存保护或限制。
修复泄漏和无界缓存。

预取与按需的权衡¶

按需分页只在访问时加载，避免无用 I/O，但首次访问延迟高。预取利用空间/顺序模式提前读取，命中预测时减少等待，预测错误则浪费带宽并污染缓存。

顺序文件读取适合较大预读窗口，随机数据库访问可能不适合。自适应策略应根据命中和访问模式调整，而不是固定越大越好。

物理页分配：伙伴系统¶

页面置换决定腾出哪些页，物理分配器还要高效提供连续页框。伙伴系统把内存按 \(2^k\) 页大小分组：

请求大小向上取整到某个阶。
若无该阶空闲块，拆分更大块为两个伙伴。
释放时，若伙伴也空闲则合并到更高阶。

优点是拆分与合并快，易提供对齐连续块。代价是向上取整造成内部碎片；长期分配还可能使高阶连续块稀缺。

小对象分配：slab 思想¶

内核频繁创建固定类型对象，如进程描述符、目录项和网络缓冲元数据。每个对象都按整页分配会严重浪费。

slab 类分配器为对象类型维护缓存：

从伙伴系统获得页。
把页切成等大小对象槽。
缓存已构造对象，减少重复初始化。
使用每 CPU 缓存降低全局锁竞争。

代价是每类缓存占用页，低使用率时可能造成内部碎片和缓存膨胀。

用户态分配器¶

用户态 malloc 通常维护 arena、大小类和空闲链表。小对象从已获得的虚拟区域切分，大对象可能直接映射。常见碎片：

内部碎片：分配块大于请求。
外部碎片：空闲总量足够，却分散成无法满足大请求的小块。

多线程分配器使用线程缓存减少锁竞争，但会增加每线程保留内存，使“已释放给分配器”不等于“已归还操作系统”。

内存超量承诺与 OOM¶

虚拟分配成功时，系统可能尚未为所有页面预留实际物理内存和交换空间，因为许多映射永远不会被全部触碰。这提高利用率，却可能在未来触碰页面时发现承诺无法兑现。

极端内存压力下，系统可能：

让分配或缺页失败。
强制回收缓存与交换。
触发 OOM 选择并终止进程。

“申请成功”与“未来每页都一定可驻留”不是同一保证。关键服务需要结合内存限制、预留、锁页和失败策略评估。

NUMA 放置¶

NUMA 系统中，访问本地节点内存通常比远端快。首次触碰策略把页分配到首次写入它的线程所在节点，这使并行初始化方式影响后续性能。

页面迁移可改善局部性，但要复制数据、更新页表并失效 TLB。任务频繁迁移时，盲目追随可能产生抖动，调度和内存策略要协同。

诊断线索¶

现象	候选解释
主要缺页持续很高	工作集超内存、随机文件访问、交换抖动
RSS 高但缺页低	工作集稳定，不一定有压力
释放对象后 RSS 不降	分配器缓存、碎片、共享映射
高阶页分配失败	物理碎片，即使总空闲页不少
CPU 低且存储繁忙	页面换入换出或文件 I/O 等待

指标必须结合时间线和工作负载。一次性启动缺页与持续抖动含义完全不同。

自测¶

OPT 为什么不可实现，却仍有价值？
Clock 如何用访问位近似 LRU？
干净文件页和匿名页的回收成本为何不同？
伙伴系统解决什么问题，可能留下什么碎片？
为什么 free 后进程 RSS 不一定立即下降？

参考思路

OPT 需要未来信息，但可作为离线下界。Clock 给近期访问页第二次机会。干净文件页可直接丢弃，匿名页通常需交换或保留。伙伴系统快速提供对齐的 \(2^k\) 连续页，向上取整有内部碎片。用户分配器可能把块留在 arena 或线程缓存中复用。