虚拟内存¶

本章问题：程序访问的数据暂时不在内存时怎么办？内存放不下所有页面，又应该留下哪些？

学习顺序：

1. 从上一章的页表状态进入合法缺页处理。
2. 追踪旧页保存、新页取得与原指令重试。
3. 分别按装入次序、最近访问和引用位做页面置换。
4. 用工作集与局部性解释抖动和访问顺序。
5. 区分写时复制、文件映射与内核分配。

页面可以暂时不在内存¶

上一章解决了“页已经在内存，怎样找到它”。虚拟内存进一步允许一部分页暂时没有物理帧。页表需要同时记录映射、权限和驻留状态；驻留集是当前实际在内存中的页面集合。

进程可用虚拟空间很大，当前驻留集却只占其中一部分。

虚拟内存让进程使用独立地址空间，只把当前需要的部分装入主存。访问页时，页表状态可能表示尚未驻留，产生缺页异常。内核先检查地址与权限是否合法；非法访问不能靠随意分配一页放行。

合法缺页的路径是：确认来源→找空闲帧或选牺牲页→必要时写回脏页→取得所需内容→更新页表与转换缓存→重试指令。进程等待设备期间阻塞，完成后先就绪，再等调度。

首次匿名页可以清零得到，写时复制可在内存中复制，所以缺页不一定读磁盘。

flowchart TB
    A["访问触发页异常"] --> B{"地址与访问权限是否合法？"}
    B -->|"非法"| E["报告访问错误，不能任意放行"]
    B -->|"合法，需要建立页面"| C{"有空闲帧？"}
    C -->|"有"| F["取得空闲帧"]
    C -->|"无"| V["选牺牲页，撤销旧映射"]
    V --> D{"旧页已修改且内容需保存？"}
    D -->|"是"| W["先写回旧内容"]
    D -->|"否"| L["取得新页内容"]
    W --> L
    F --> L
    L --> U["更新页表与相关TLB"]
    U --> R["恢复执行后重试原指令"]

脏页是自上次保存后已修改的页；若唯一的新内容还在这个帧中，覆盖前必须保存。干净页若能从原文件或其他后备存储重新取得，通常可以直接丢弃该内存副本。

页面来源可能是文件、交换区、清零的新匿名页或共享页副本，因此异常处理的每一条路径都应按来源判断。

• **写时复制（COW）**让父子先只读共享同一页；
• 某一方写入时触发保护异常，内核建立私有副本、修改映射并重试。
• 共享值10时子写11，父仍读10、子读11；
• 若有空闲帧且源页驻留，不必读取磁盘。

flowchart LR
    P["父进程：映射旧页"] --> O["共享旧帧：值10"]
    C["子进程：写入前也映射旧页"] --> O
    C -->|"写触发COW处理"| N["新私有帧：先复制10，再重试写成11"]

这里应用本来具有写入这块数据的逻辑权限；只读映射用来捕获第一次写入。普通无权限写入与COW有意设置的写保护需要由内核区分，不能把所有保护错误都当成COW。

练习 1¶

没有空帧时换谁¶

• 手算时先选一种记录顺序，并始终保持一致。
• FIFO队列记录“谁最早装入”，命中不改变装入时间；
• LRU队列记录“谁最久没用”，每次命中都要移动；
• OPT需要向引用串后面看下一次使用距离，未来不再使用者可以优先淘汰。
• 它们判断的时间依据不同，不能共用同一套更新规则。

FIFO换最早装入者，命中不改入队次序；LRU换最长时间未使用者，每次命中也更新最近性；OPT换未来最晚再用者，作为理想比较基准，需要预知未来。

3帧初始全空，访问1、2、1、3、4、2、1。下表FIFO从最早装入排到最晚，LRU从最久未用排到最近，星号表示缺页：

第3次访问1命中，LRU把1移到最近端；所以访问4时淘汰2，随后访问2要再淘汰1，最后访问1又缺页。LRU共6次，FIFO共5次。算法优劣不能由单个串保证，LRU并非每串都胜过FIFO。

Clock用一位近似最近性¶

精确维护LRU成本较高。Clock把帧排成环，每帧有引用位R，访问置1；缺页时从指针开始，见R=1就清0并向后，见R=0就替换，新页置1，再移动到下一帧。命中一般不移动指针，以题设为准。

FIFO可能发生Belady异常：增加帧数反而增加缺页。LRU、OPT具有栈包含性质，在其标准模型下增加帧不会出现这种异常。首次装入也算缺页，不能漏计。

工作集与抖动¶

固定分配可按进程大小或比例给帧，可变分配随需求调整；局部置换只换自己的帧，全局置换可影响其他进程。工作集是最近一个窗口中访问过的不同页面集合，重复访问只算一个。

引用1、2、1、3、4，窗口为最近3次，第4次后集合为{1,2,3}，第5次后为{1,3,4}。它描述近期需求，可能大于当前驻留帧数。

活跃进程总需求超过内存时，频繁换入换出导致抖动；再增加并发进程可能更差，应减少并发量或为工作集提供足够帧。

练习 2¶

练习 3¶

映射与内核分配¶

mmap把文件内容映入地址空间。共享映射的修改可按接口对其他映射者可见；私有映射修改通常进入私有副本，不因此改原文件。可见性与掉电持久化是不同保证，仍需相应刷回协议。

伙伴分配把内存拆成按自身大小对齐的二次幂块。1024 KiB中连续申请两个100 KiB，各向上取128 KiB，得到[0,128)、[128,256)。

释放后只有同大小且正好互为伙伴的空闲块才能合并，逐层回到大块；相邻并不足够。Slab则缓存特定类型的内核对象，复用已经组织好的小对象，减少反复初始化和碎片。

局部性决定帧是否够用：4×4数组每行一页，只有2帧，按行访问一行的4项后才换行，缺页4次；按列形成0、1、2、3反复循环，LRU下每次再用前都已被淘汰，缺页16次。

优化访问次序有时比机械增加并发更有效。

练习 4¶

记忆要点¶