OSTEP - 虚拟化部分笔记

本文最后更新于 2026年7月24日 下午

前言

课内的教学：采用《操作系统概念》这本教材

  • 我感觉写得一般般...

课内教学顺序：

  • OS概述
  • 计算机体系结构
  • 进程、线程
  • CPU调度
  • 死锁
  • 内存管理
  • 虚拟内存
  • 文件系统
  • 设备管理
  • 磁盘结构

与OSTEP差别很大，OSTEP把虚拟化的部分放在了最前面。不过 I/O 持久化 / 文件系统部分，两本书都是靠后的。

第4章 进程

所谓进程：有自己的地址空间、寄存器、程序计数器等。

管理进程：用PCB (Process Control Block)。

第5章 进程API

fork()

代码C · 19 行
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

int main(int argc, char* argv[]) {
    printf("Hello, world (pid: %d)\n", (int) getpid());
    int rc = fork();
    if (rc < 0) {
        fprintf(stderr, "fork failed\n");
        exit(1);
    }
    else if (rc == 0) {
        printf("Hello, I'm child (pid: %d)\n", (int) getpid());
    }
    else {
        printf("Hello, I'm parent of %d (pid: %d)\n", rc, (int) getpid());
    }
    return 0;
}
> ./fork_p1
Hello, world (pid: 3972)
Hello, I'm parent of 3973 (pid: 3972)
Hello, I'm child (pid: 3973)

我对这个运行过程的理解：

int rc = fork()之后，立刻创建了一个子进程，子进程是父进程的几乎完全副本，子进程不从main开始运行，而是从调用fork处开始运行。

  • 对于父进程，获得的返回值是子进程的PID
  • 对于子进程，如果返回值是0说明成功创建了子进程

运行的具体顺序会依CPU调度而不同，每次运行可能获得的结果也不一样。

wait()

父进程调用后会堵塞，直到任意一个子进程结束才返回子进程的ID。

上面的代码的部分改成这样：

else {
    int wc = wait(NULL);
    printf("Hello, I'm parent of %d (wc: %d) (pid: %d)\n", rc, wc, (int) getpid());
}

则输出变成确定：先运行子进程

Hello, world (pid: 7835)
Hello, I'm child (pid: 7836)
Hello, I'm parent of 7836 (wc: 7836) (pid: 7835)

exec()

先fork创建一个子进程，然后在rc == 0的分支内，调用execvp()，从其他可执行程序中加载代码和静态数据，覆写自己的代码段，并执行。对exec()的成功调用永远不会返回。

为什么不合并 fork 和 exec

举个例子，运行：

cat < input.txt > output.txt

shell 的做法：

  • fork 一个子进程
  • 在子进程内：
    • 把标准输入重定向到 input.txt
    • 把标准输出重定向到 output.txt
    • （所谓重定向：修改 STDOUT 的 file 句柄（fd））
  • exec("cat")

核心在于需要在 fork 和 exec 之间进行重定向，如果合并了，就没有这样的空间了。

第6章 受限直接执行

核心：操作系统想把一颗真实的 CPU “虚拟化”成很多进程都像在同时运行，但它又不能把控制权真的交出去。所以它必须同时做到两件事：

  • 一是让程序跑得快，尽量直接在 CPU 上执行——直接执行
  • 二是始终保留“随时管住程序、随时把 CPU 拿回来”的能力——受限

首先从直接执行引入：

  • 程序装入内存，
  • 设置好栈和寄存器，
  • 然后直接让它在 CPU 上跑。

但是这样有两个问题：

  1. 程序一直占着CPU不放；
  2. 程序想做一些比如 I/O 之类的敏感操作

所以我们提出两类限制：

受限操作不能乱做

我们通过硬件给出两种模式：user mode and kernel mode.

  • 普通程序在user mode进行，权限小
  • 操作系统在kernel mode执行，可以做 I/O、改页表、控制设备这些敏感动作

但是普通程序也需要执行敏感操作，这个时候在OS内部实际上执行的是：

  • 对于高级语言：表面上和调用一般的过程调用没区别，比如read()
  • 实际上，库函数的代码最后从汇编层面，执行trap指令，将CPU从用户态切到内核态；
  • OS将这个程序的寄存器的值推入内核栈
  • 内核在启动时设置过trap table，trap 让硬件根据陷入号跳到一个固定入口，入口代码再根据 syscall number 选择具体的系统调用实现
  • 完成之后，OS调用一个return-from-trap指令，内核栈的值弹出，回到用户态。

关于trap table的存在意义

内核在启动时用特权指令把“陷入向量/入口地址”注册给硬件（用户态不能改），这样用户程序即使触发 trap 也只能进入内核允许的入口，而不是跳到任意内核地址

关于内核栈

每个进程通常都有自己的 内核栈（kernel stack），陷入内核后用的是这个栈，不是用户栈。

程序不能永远霸占CPU

OS如何夺回控制权？

核心：时钟中断

OS在启动时设置一个硬件计时器，每隔一小段时间强制触发一次中断，硬件会帮忙保存当前程序的一部分现场（寄存器的值），切回内核态，并跳到内核的中断处理代码。于是 OS 就重新拿回 CPU，可以决定“继续让当前进程跑”还是“换另一个进程上来”。——这个决定是调度程序控制的。

如果需要切换进程：核心：上下文切换。

  • OS帮忙保存当前运行的进程的一些寄存器的值，比如PC、通用寄存器、内核栈指针，保存到内核栈；
  • 然后，切换内核栈
    • 具体而言，是把当前进程的寄存器状态保存到它的进程结构里（PCB）；
    • 切换到另一个进程时恢复它的寄存器状态

第7章 进程调度：介绍

这一章主要是做一个最简单的调度策略的介绍。

先提出五个不切实际的假设：作业等长、同时到达、开始后跑到结束、不做 I/O、并且已知运行时间。

明晰两个核心指标：

  • 周转时间：任务完成时间 - 任务到达系统的时间
  • 响应时间：工作第一次到达系统的时间 to 工作第一次被调度运行的时间

这两个指标之间存在trade-offs。

下面给出几个调度的方法范例：

FIFO

作业等长时表现尚可，但是一旦作业长短不一，就会有后面的短任务被前面的长任务卡死。

SJF STCF

  • SJF：Shortest Job First，在「已知作业长度、且同时到达」的条件下是最优的
  • STCF：Shortest Time-to-Completion First，任何时刻都选择剩余时间最短的作业；短作业到来时可以打断长作业，从而继续优化周转时间

响应时间和RR

STCF/SJF 可能让某个作业「很久才第一次拿到 CPU」，响应时间很差。

引入时间片，RR即时间片轮转，每个作业只跑一个时间片就切换到下一个。

时间片长度通常要和定时器中断周期匹配（例如取其整数倍）

这里存在 trade-offs：

  • 时间片越短，响应时间越好，但是上下文切换过于频繁，会导致性能损耗；
  • 切换开销不仅是保存/恢复寄存器，还包括缓存、TLB、分支预测等硬件状态被冲掉带来的性能损失

总结：像 RR 这样强调公平（小时间尺度上均分 CPU）的策略，往往会把周转时间拉得很差；反过来，偏向短作业优先的策略周转好，但响应差。这是典型系统权衡。

第8章 调度：多级反馈队列

MLFQ（Multi-Level Feedback Queue）的核心：用历史行为当作反馈来猜测未来，边跑边学习，判断一个进程是偏交互还是偏CPU密集。

MLFQ的基本结构：维护多条就绪序列，每条队列有自己的优先级，

具体而言，五个规则：

  • Rule 1/2：优先级高的先跑；同优先级用 RR，每层的时间片都不一样，自定义，通常高优先级队列用更短时间片（更像交互），低优先级用更长时间片（减少切换开销）
  • Rule 3（新来的先当成短任务）：新任务进入系统时放在最高优先级
  • Rule 4（用满“配额”就降级）：一个任务在某个优先级上累计用完 allotment（时间配额），就被降到下一层；关键点是“不管它中间让没让出 CPU”，累计到了就降级
  • Rule 5（周期性提权，防饿死/应对相变）：每隔一段时间 S，把所有任务都提到最高优先级

一些概念解释：

  • 饥饿：交互任务太多时，低优先级的长任务可能一直拿不到 CPU，解决方案是Rule 5

第9章 调度：比例份额

这是另一种调度的思想：不以周转时间/响应时间的优化为核心指标，而是尽量保证每个任务拿到某个比例的 CPU。

彩票调度

基本概念很直观：tickets 表示某个进程应得的 CPU 份额。比如 A 有 75 张票、B 有 25 张票，期望 A 拿 75% 时间、B 拿 25%。

调度方式：每个时间片抽一次奖

  • 维护总票数 totaltickets
  • 随机生成 winner ∈ [0, totaltickets-1]
  • 扫描进程列表，累加票数，第一次使累加值超过 winner 的进程获胜并运行

为什么采用随机？大数定律。保证概率意义上的公平。

本章也强调了“随机化”的工程价值：实现轻、状态少、避免一些奇怪的边界行为，且通常足够快。

彩票机制

  • Ticket currency：每个用户在自己的“币种”里分配票，系统再换算到全局票数（比例换算）
  • Ticket transfer：客户端把票临时给服务端，让服务端处理请求时更容易被调度，做完再还回去
  • Ticket inflation：在一个进程之间相互信任的环境下，任务可以临时提高 / 降低自己的票数

步长调度

为了解决合理分配彩票的问题。

  • 每个进程有 stride = 常数 / tickets（票越多 stride 越小）
  • 每次选择 pass 最小的进程运行，每一个时间片pass += stride

问题：当一个新进程加入时，这个进程的常数难以分配。

因此还是通常使用MLFQ。

第10章 多处理器调度（高级）

先略，学完并发来补。

第13章 抽象：地址空间

主要是提出了一个「地址空间」的抽象概念：OS需要给每个进程分配一个「地址空间」，但现实里所有进程共享同一份虚拟内存。

多道程序与分时：为了效率希望「进程留在内存里轮流跑」，而不是每切换一次就把整个内存都保存到磁盘再恢复，因为那会非常慢。

地址空间：分成三段

虚拟化的关键：即使进程尝试访问地址0，但是OS+硬件必须把这些虚拟地址转换成正确的物理地址。

即，三大关键：

  • 透明性：好像透明了，让进程察觉不到；
  • 效率；
  • 保护：OS和进程之间必须存在隔离，避免相互读写内存。

第14章 插叙：内存操作API

这一章主要是讲C语言中的内存分配API。

  • 栈内存由编译器在函数调用与返回时自动管理
  • 堆内存需要显式 malloc() 申请、在不再使用时 free() 释放

这里有一些常见的内存错误：

  • 忘记分配就写内存
  • 分配不够导致的越界写
  • 读取未初始化的区域
  • 忘记释放导致内存泄漏
  • 释放之后的内存继续使用（悬垂指针）
  • 重复释放

第15章 机制：地址转换

硬件地址翻译：

核心 trade-offs：

  • 既要效率（大部分时刻不允许OS介入）
  • 保护（进程只能访问自己的内存）
  • 灵活

和之前将调度算法一样，我们先基于一个简单乃至于不切实际的假设出发，并逐渐扩展。

假设：

  • 每个进程的地址空间可以连续放进物理内存
  • 大小均小于物理内存的大小
  • 每个地址空间的大小完全一样

依赖的硬件支持：

  • 基址寄存器（base）：把「虚拟地址」当作是「相对于base的偏移量」，即physical = virtual + base；
  • 界限寄存器（bound）：virtual >= bound即非法，触发trap指令

二者组合，被称为内存管理单元 (Memory Management Unit) MMU。

依赖的 OS 的介入：

  • 空闲列表 free list：OS中的一个数据结构，标记内存空间的空闲 / 已用；
  • 上下文切换：每个 CPU 只有一对 base/bounds，切进程时 OS 要把旧进程的 base/bounds 保存到 PCB 之类的结构里，再把新进程的 base/bounds 恢复到 CPU；
  • 异常处理：OS 在启动时安装各种处理器异常处理函数；一旦进程越界访问内存，硬件切到内核态并跳到对应 handler，OS 决定怎么处置（常见就是 kill 并回收内存）。

基于三个浅显的假设，我们实现了内存的虚拟化，但是有这些问题：

  • 每个进程占的内存大小都相同，会造成巨大浪费，具体而言，堆和栈之间的巨大空间会被浪费。

第16章 分段

分段主要是为了解决上面所说的，空间大量浪费的问题。

所谓分段：把一个进程的地址空间按逻辑（即代码、栈、堆）切成数段，每一段各自用一个MMU进行重定位和保护，段与段之间放在物理内存的不同位置。

分段的精髓在于把不同进程的段映射到完全不同的物理位置（具体在哪，是靠下一章的寻找来找到的）。

注意这里还有给OS预留的空间

如何判断引用哪个段

显式方式：我们有一个虚拟地址，用虚拟地址的高位（前几位）来标识不同的段，比如有三个段的话，我们就用前两位来标识，然后用后面的部分作为段内的偏移量，再将这个偏移量与基址寄存器相加，硬件便得到了最终的物理地址。同时，我们检查的时候也只需要检查偏移量是否小于界限（段的界限寄存器）。

隐式方式：

  • 如果地址来自 PC（取指），认为在 code 段。
  • 如果地址基于栈指针/帧指针，认为在 stack 段。
  • 其他一般认为在 heap 段

对于栈的特殊处理

我们需要注意，栈是向下增长的，即栈是往更小地址方向扩展的。

因此，其实虚拟地址里面还有一位是作为标识，标识段的增长方向。

假设是反向增长的，那么对于虚拟地址的处理是这样的：

  • 得到偏移量
  • 用偏移量减去最大的段地址（其实就是界限寄存器的大小）
  • 用这个负数（这里可以assert一下）加上基址寄存器，得到实际的物理地址

共享

在地址空间之间共享内存，只需要在硬件中做一些小小的支持。

给每个段再增加几个位，标记程序对于这个段的权限：读写、只读、执行代码等等。

这样，同样的代码可以被多个进程共享，但是不需要担心破坏隔离。

这样，前面的硬件算法也需要做出改变：检查虚拟地址是否越界、检查特定访问是否符合权限。

问题

  • 外部碎片：段是变长的，物理内存里空闲块会被切成零碎小洞，导致“明明总空闲很多，但找不到足够大的连续块”；这个问题有很多缓解方案，但是终究无法解决。

第17章 空闲空间管理

其实主要就是尝试去解决外部碎片的问题。

我们假设，内存一旦被分配给用户，就不可以被重定位到其他位置。

底层机制

假设我们靠一个free list 空闲列表来管理内存，那么存在以下机制：

  • splitting：假设有100字节空闲块，有人申请20字节，应当将内存块分隔成20+80，然后只给用户20，而不是把整个100给用户
  • coalescing：假设20字节被释放了，那么需要与80合并，这样又有了一块100字节的完整内存块
  • header：回忆free(ptr)的调用过程，参数只有一个指针，没有内存块的大小，所以每个分配内存块前面是有一个 header 来存 metadata，记录内存块的大小的；里面还会有 magic number，用来做健全性检查。

接下来我们分析：「当有很多空闲块能满足要求时，选哪一块？」几种策略：

  • First fit：从头开始找，遇到第一块够大的就分配。它的优点是简单、快，不用把整张 free list 都看完。缺点是前面的空闲块容易被切得越来越碎。
  • Best fit：把所有能装下请求的空闲块都看一遍，挑“最小但够用”的那块。它的直觉是“尽量别浪费大块”，但代价是搜索更慢，而且实际效果也不总是最好，因为它可能制造很多特别小、以后谁也用不上的碎片。
  • Worst fit：挑最大的那块来切。它的想法是“切大块，剩下的也还是比较大”，但实践里通常并不出色，而且同样需要较多搜索。
  • Next fit：和 first fit 很像，只不过不是每次都从链表开头找，而是从上次停下来的地方继续找，想把碎片分布得更均匀一些。

这里永远存在trade-offs。

但是只依靠free-list有点效率低，这里还有几种思想：

  • segregated free lists：给常用的大小预分配一个单独的空闲列表，比如16字节、32字节，这样分配时就不用在一条大链表里慢慢找，速度会快很多。
  • buddy allocator：规定：内存块大小都按照$2^k$来管理。一块 64KB 的空闲空间，需要8KB，就不断二分，优点是合并容易，缺点是申请7KB也会给8KB，从而产生碎片。

总结：

  • 变长内存管理最核心的问题是外部碎片。
  • 分配器能工作的基础是 splitting、coalescing 和 header。
  • fit 策略解决的是“挑哪块”，本质是在速度和碎片之间做权衡。
  • 工程上常用 segregated lists/slab 或 buddy 来进一步提升效率和可管理性。

第18章 分页：介绍

分段解决了「整个地址空间当成一块过于浪费」的问题，但是解决了，但是带来了外部碎片的问题。

所谓「分页」，是将虚拟内存和物理内存都切成固定大小的小块，相比分段关心逻辑，分页不关心逻辑。

具体而言：

  • 将进程的虚拟地址空间切成一个个固定大小的page；
  • 再将物理内存切成同样大小的page frame
  • 寻址类似于分段：
    • 前面几位表示虚拟页面号（virtual page number，VPN）
    • 后面几位表示偏移量 offset
    • 根据页表去查询虚拟页面号对应的物理地址
    • 注意这里是直接把VPN换成页表里面查到的PFN (Physical Frame Number) 的二进制，然后和OFFSET直接拼起来，而不是相加
  • 页表是每进程的数据结构，注意地址空间也是每进程的。

好处：

  • 分配空闲空间简单化，只需找若干个空闲的 page frame，把进程的page塞进去即可
  • 虚拟空间可以是连续的，但是映射到物理空间里面就可以不连续了

坏处：

  • 页表大，占很多内存
    • 因为页表很大，塞不进少量硬件寄存器（MMU）中，所以只能把页表放入内存中
    • 假设一个32位系统，地址空间4GB，页面大小4KB，则offset占12位，因为4KB = $2^{12}$ ，故VPN是剩下的20个bit，则有 $2^{20}$ 个虚拟页，假设一个页表项只有4B，那也是4MB，而且还得注意是每个进程都有一个页表。
  • 地址翻译变慢，因为每次访存都需要查询页表

页表项 PTE：

OS通过VPN检索页表，在这个索引处找到PTE，以便找到PFN，PTE里面也有很多内容：

  • valid bit：这条映射是否有效，也就是还没被分配的页框不允许使用（不有效）
  • protection bit：这个页能不能读写执行
  • present bit：页面当前是否在物理内存里，还是已经被换到磁盘、dirty bit：这页是否被修改过、reference/accessed bit：这页最近有没有被访问过 （目前不重要）

分页的时间开销：

CPU想访问一个虚拟地址所需要做的工作：

  1. 从虚拟地址提取VPN
  2. 从页表基址寄存器中找到当前进程的页表的起始位置
  3. 计算目标页表项地址
  4. 从内存中把那个PTE取出来
  5. 检查各种位
  6. 拿到PFN，得到物理地址
  7. 取数据

查页表也是一次load，真正的取数据也是一次load，十分慢。

第19章 分页：快速地址转换（TLB）

TLB是一个很小、很快、放在MMU里面的页表缓存，缓存的是最近常用的地址翻译结果，也就是「某个虚拟页号 VPN 对应哪个物理页框号 PFN」。

具体而言，一次程序访问虚拟地址的流程：

  • CPU把地址拆成VPN和OFFSET
  • 拿着VPN去查TLB：
    • 如果TLB Hit，则CPU立刻拿到PFN，得到真实物理地址
    • 如果TLB Miss，这时才需要去查页表，一方面得到PFN，另一方面把这个映射塞入TLB

T核心判断标准：有效内存访问时间 EMAT，取决于TLB命中率。

为什么TLB作用很大？

因为程序访问有局部性：

  • 时间局部性：刚刚访问过的页，很快会被又一次访问
  • 空间局部性：相邻的（虚拟意义上相邻）地址可能被一块访问，典型如循环访问数组

TLB的内容

TLB里面只有PTE的一部分内容，包括：

  • valid bit：是否有效
  • protection bit：权限
  • dirty bit：是否被写入过
  • address-space identifier ASID：这条映射属于哪个进程

这里最重要的是ASID，因为要处理上下文切换：

上下文切换

比如进程A切换到进程B时，本来TLB中的存的全是A相关的页表，现在要换到B了，这些TLB都没用了，解决：

  • 简单粗暴的做法是把TLB全部清空，但是这样处理完之后命中率会很差
  • TL所以我们需要支持ASID，这样不同进程的映射可以共存于TLB中：
  • TLB是全局的硬件缓存，但是系统里面有许多进程，但是VPN当然会重合，所以首先从这里就可以看出来ASID很重要（可以理解为这个数据库的主键是(ASID, VPN)，在切换时无需对TLB进行特别的处理。

TLB Miss的处理

  • 对于CISC，全权由硬件处理；
  • 对于RISC，交给OS处理，硬件触发异常，陷入内核态，由OS的异常处理程序去处理。

前者访问路径直接，后者灵活性高但陷入内核，性能损耗大。

TLB 的替换

在讨论页换出到磁盘的问题时，我们将详细研究这样的策略。

这里简单提一下LRU，即替换least-recently-used的项。

TLB 越小，替换策略越重要；但更关键的通常还是程序访问是否具有局部性。 如果程序不断访问大量分散的页，TLB 再聪明也会频繁 miss。

总结

  • TLB = 页表的高速缓存，用来缓存最近使用的 VPN -> PFN 翻译结果。
  • 地址翻译先查 TLB，hit 就快，miss 才去查页表。
  • TLB 的价值来自局部性：程序常反复访问少量页面。
  • TLB 命中率高时，可以大幅降低分页带来的额外访存开销。
  • 多进程下要考虑上下文切换，常见办法是 flush TLB 或使用 ASID。
  • TLB miss 的处理可以偏硬件，也可以通过陷入 OS 由软件参与。

第20章 分页：较小的表

回忆一下，分页带来了两个问题：

  • 页表太大
  • 翻译太慢

其中上一章，我们通过TLB解决了翻译太慢的问题，这一章我们解决页表过大的问题。

为什么不能单纯把页放大

页越大，页数越少，页表项越少，但是这会导致页内浪费过多，形成内部碎片。因此，OS还是主要用比较小的页，比如4KB 8KB

把分页和分段结合起来 Hybrid 方法

  • 先分段，段负责把地址空间划分成几个逻辑区域；
  • 分页，负责在每个段内部继续按页来映射。

但是这个结构其实不是很合理，因为「分页」本身的优点，就是不依赖程序的逻辑结构。

多级页表

核心：线性页表里面很多页表项其实都是invalid的，那么干脆把这些无效的页表页分配出来。

引入更上一层的结构：页目录

  • 页目录中的每个项，指向某一页页表
  • 页表项，负责指向真正的 page frame

即：

  • 原来的线性情况，是每个进程都分配一个大页表
  • 现在的情况，是每个进程分配一个页目录，页目录里面的页目录项 PDE指向一个页表
    • 被指向的页表和原来的线性页表一样，都是PTE的数组
    • 重点是这个小页表是按需创建的，只为真正用到的虚拟地址区域分配页表空间。

多级页表的Trade-off：TLB Miss时，需要从内存中加载两次（首先从页目录中加载，再从PTE本身加载）

一个虚拟地址怎么在二级页表里面查询？

在一个二级页表中，虚拟地址会被拆成三部分：

  • 页目录索引 Page Directory Index -> 用于确定是哪个进程的页目录的
  • 页表索引 Page Table Index
  • 页内偏移 offset

查询流程：

  1. 先用PDIndex去查页目录，计算得到得到对应的页目录项 PDE的地址
  2. 若PDE无效，触发异常
  3. PDE有效，继续查询，可以根据PTIndex，计算得到相应的页表项PTE的起始地址
  4. 如果无效，跳出
  5. 如果有效，则根据PTE查询PFN
  6. 最后与OFFSET结合得到答案。

这里给一个GPT的例子，看完就懂了：

引用为了容易算，我们假设一个很小的系统。 已知条件 虚拟地址长度：8 bit 页大小：16B = 2^4 所以： 页内偏移 offset 占 4 b...

为了容易算，我们假设一个很小的系统。

已知条件

  • 虚拟地址长度：8 bit
  • 页大小：16B = 2^4
  • 所以：
    • 页内偏移 offset 占 4 bit
    • 剩下高 4 bit 用来表示“虚拟页号 VPN”

但现在我们是两级页表，所以这 4 bit 的 VPN 再拆成两部分：

  • 高 2 bit：页目录索引 PDI
  • 低 2 bit：页表索引 PTI

所以一个虚拟地址会被拆成：

| 2 bit 页目录索引 | 2 bit 页表索引 | 4 bit 页内偏移 |

比如我们现在有一个虚拟地址：

01100101

把它拆开：

01 | 10 | 0101
PDI  PTI  offset

所以它表示：

  • 页目录索引 PDI = 01 = 1
  • 页表索引 PTI = 10 = 2
  • 页内偏移 offset = 0101 = 5

第一步 查页目录

假设当前进程的页目录如下：

页目录索引 是否有效 指向哪张页表
0 1 页表 A
1 1 页表 B
2 0 不存在
3 0 不存在

刚刚得到 PDI=1，查询得到存在，是页表B

第二步 再查页表

假设页表B内容如下：

页表索引 是否有效 物理页框号 PFN
0 1 4
1 0 -
2 1 9
3 1 3

刚刚得到 PTI=2，所以得到 PFN=9

第三步 拼地址

物理地址 = PFN * 页大小 + offset
         = 9 * 16 + 5
         = 144 + 5
         = 149

最终结果：虚拟地址 01100101 被翻译成物理地址 149。

多级页表的优缺点：

  • 优点：显著减小页表大小
  • 缺点：TLB Miss时，翻译路径更长了，多花了一次load的时间

更高级

如果地址空间远大于页的大小，那么二级页表也不够，需要多级页表。

目标是「让每一级页表结构的大小尽量不超过OS的一页的大小，并只在需要时分配」.

反向列表

前面我们一直强调每个进程一张页表。

反向页表的思路：

  • 整个系统只有一张表
  • 每个物理页框有一个表项
  • 表项记录这个物理页框属于哪个进程，对应此进程的哪个虚拟页

但是纯线性会很慢（因为主键是(PID, VPN)），故通常再加一个哈希表。

很重要的观点： 页表本质上只是数据结构。 既然是数据结构，就可以有很多不同设计，大家都是在“空间”和“时间”之间做不同取舍。

第21章 超越物理内存：Swap机制

我们之前都默认内存装得下页面，但是实际上：

  • 进程的地址空间可能很大，同时运行的进程也可能很多，
  • 导致物理内存其实装不下需要使用的所有页面。

我们通过把当前不常用的页面放到磁盘的swap space来解决这个问题。

核心流程图：

flowchart TD
    CPU["CPU 访问某个虚拟地址"] --> TLB["先查 TLB"]
    TLB -->|命中| MEM["直接访问物理内存中的页"]
    TLB -->|未命中| PT["查页表"]
    PT -->|页在内存中| MEM
    PT -->|页不在内存中| PF["触发 page fault"]
    PF --> OS["OS 的 page-fault handler 介入"]
    OS --> DISK["从 swap / 磁盘把页读回内存"]
    DISK --> MEM
    MEM --> RETRY["重试原来的指令"]

合法页和在内存里的页

两个位：valid 和 present。

  • valid bit：这个页是不是这个进程合法地址空间的一部分。
  • present bit：这个合法页现在是不是正在物理内存里。

当valid=1而present=0时，说明这个页在磁盘里，访问触发page fault 缺页异常。

page fault 是虚拟内存系统的一个正常工作环节。

如何处理page fault

  1. 先看 TLB 里有没有这条地址翻译
  2. 如果 TLB 没命中，再去查页表
  3. 查页表后发现这个页 valid = 1，但 present = 0
  4. 硬件触发 page fault，把控制权交给 OS
  5. OS 的 page-fault handler 开始工作。
  6. OS 找一个物理页框，准备把缺的页读进来。
  7. OS 去磁盘的 swap 区把这页读回内存。
  8. OS 更新页表，把这个页表项改成：
    • present = 1
    • PFN = 某个新的物理页框号
  9. 必要时还会更新 TLB。
  10. 然后重新执行刚才那条出错的指令。
  11. 这次因为页已经在内存里了，就能正常完成访问

访问一个不在内存里的合法页时，OS 负责把它“补回来”，然后让程序像什么都没发生一样继续运行。

重试之后，很可能还会先经历一次 TLB miss，因为 TLB 里还没有这条新翻译；再经过一次重试后，才会真正 TLB hit，最终访问到数据。

page fault很贵

触发磁盘I/O的访问速度是非常非常慢的，所以只要page fault 变多，程序速度就会急剧下降。

在page fault想要补回来的时候，内存满了怎么办

那么就必须先把在内存里面的一个物理页框赶出来，即所谓 page replacement（页面置换） 或 eviction（驱逐）。

这个机制下一章再说。

页错误期间进程在干嘛

因为磁盘I/O是一个很贵的操作，回忆我们之前的调度算法，这个进程是blocked的状态，所以这段时间，OS可以去运行别的进程。

为什么页错误交给OS而不是硬件

  1. 硬件处理太复杂
  2. 真正耗时的是磁盘 I/O，所以就算 OS 多执行一些软件逻辑，相比磁盘的慢，这点额外开销也不算什么。

交换何时真正发生

刚刚说内存满了才会发生OS去换出页面，但实际并非如此，OS其实更加主动：

系统设置两个水位：

  • low watermark（LW）
  • high watermark（HW）

工作机制：

OS发现空闲页数低于LW，则后台线程开始运行，主动把一些页swap出去，直到空闲页数回升到HW。

这个后台线程常常叫 swap daemon 或 page daemon。

第22章 超越物理内存：策略

本章的核心问题：page replacement policy（页面置换策略）

总目标：物理内存可以看成磁盘上虚拟页的一个 cache，页面置换策略要做的事，就是尽量让这个 cache 的命中率高一些、缺页率低一些。

因为磁盘IO的速度远慢于访问内存的速度，一旦miss，性能也会迅速恶化，所以目标也可以是尽量少miss。

Optimal

理想上能换掉的最优：总是换掉「未来最晚才会再被访问」的那一页。

Optimal的意义：这是理论最好的方式，但是难以实现，之后我们的实现需要向这个方向靠齐。

一些策略

FIFO

字面意思，谁最早进入内存，谁先被换掉。

问题：「最早进入」$\neq$ 「最不重要」

随机

字面意思。

  • Random 不一定特别好；
  • 但它有一个优点：没有特别奇怪的固定坏模式。

它虽然不聪明，但也不容易像 FIFO 那样在某些特殊访问序列里表现得特别离谱。

LRU

  • 如果一个页最近刚被访问过，那它很可能很快还会再被访问
  • 如果一个页已经很久没被碰过，那它更像是可以被牺牲的对象

依赖的是局部性：时间局部性 & 空间局部性

引申出 LRU Least Recently Used：

  • 淘汰最近，最久没有被访问的页

LRU的失败场景：循环顺序扫描

比如总共有 50 个页，假设内存只能放 49 页，程序不断按顺序访问：

0,1,2,3,...,49,0,1,2,3,...,49 ...

但是这个对于LRU和FIFO都极其糟糕，接近0% hit rate。

LRU很依赖于局部性。

完美的LRU很难高效实现，因为难以统计最近被访问，内存的访问极其频繁。

Clock：对LRU的近似

  • 把物理页排成一个环；
  • 维护一个「钟表指针」在上面转；
  • 每个页有一个 reference bit / use bit。

当需要淘汰某页时，Clock 这样工作：

  1. 看指针当前指向的页。
  2. 如果它的 use bit = 1，说明它最近被访问过，不想立刻淘汰。
  3. 那就把它的 use bit 清成 0，然后指针继续往前走。
  4. 如果看到某页的 use bit = 0，就说明它最近一段时间内没有再次被访问过，于是把它选作牺牲者。
flowchart TD
    A["需要淘汰页面"] --> B["看时钟指针当前页"]
    B --> C{"use bit = 1 ?"}
    C -->|是| D["清零 use bit"]
    D --> E["指针前进到下一页"]
    E --> B
    C -->|否| F["选择该页作为 victim"]

dirty pages

  • 如果一个页没被修改过，它是 clean page
  • 如果一个页被修改过，它是 dirty page

淘汰 clean page 很便宜，因为它不需要额外写回磁盘。而淘汰 dirty page 往往更贵，因为得先把它写回磁盘。

如果两个候选页差不多，那通常更希望先淘汰 clean page，而不是 dirty page。

看似与LRU的理念相反，但是现实中的算法确实会考虑这一点。

抖动

当OS完全负载：

  • 内存明显不够；
  • 系统不停地换页；
  • 页刚换进来又换出去；
  • CPU 大量时间都耗在 paging 上，而不是做真正有用的工作。

此时交换策略大致失效，OS会决定将某些吃内存的进程暂停运行甚至直接kill掉。

Summary by GPT

  • 这章的根问题是：page fault 时如果内存满了，谁该被赶出去。
  • 最优策略是“淘汰未来最晚使用的页”，但现实系统只能用历史信息近似它，所以出现了 LRU 和 Clock。
  • 真正的页面置换不是只看一个算法名，还要面对局部性、脏页成本、顺序扫描坏例子和 thrashing 这些现实问题。

第23章 VAX/VMS虚拟内存系统

本章研究一个真实完整的虚拟内存系统。完整系统是很多设计折中的结果，而不仅是单个机制的堆叠。

VAX/VMS

虚拟地址空间32位，页大小仅512B。页越小则页数越多，线性页表会变得非常大。

[!TIP] $$ 页数=\frac{虚拟地址空间大小}{页大小} $$

VAX/VMS 先把地址空间分成 P0、P1、S 三个大区域；

  • P0 管 code/heap，P1 管 stack，S 管内核。
  • P0 和 P1 各自分页、各自有页表，这样不用为 heap 和 stack 中间的大空洞浪费页表项。
  • 进一步地，用户页表本身放在内核虚拟内存里，所以页表也能被 VM 系统管理，这样省内存，因为用户页表也可以被swap出去。但地址翻译路径会更复杂。

还有几个设计要点：

  • 内核映射进每个进程的地址空间里，也就是，每个进程的虚拟空间里面都有内核（注意是虚拟空间），但是实际上都指向的是同一片存内核的物理内存；用户程序虽然「共享同一个地址空间里的内核映射」，但没有权限去读写它
  • VMS没有reference bit，但是可以用OS和protection bit限制读写权限，通过trap的方式去模拟
  • 规定page 0 无效，方便设置空指针的访问无效
  • 采用resident set size（RSS），是每个进程在物理内存内最多有几个页框项的上限，超过则采用FIFO的手段去进行交换
  • 在FIFO的交换策略中位于队尾的会被交换出去，但是还有第二次机会：clean-page list和dirty-page list，可以理解为暂时先换出去，但是还在物理内存里面，如果之后又申请，不需要再跑一次磁盘I/O
  • demanding-zero：操作系统的lazy优化的典范。用户申请一块内存之后，堆区域内存需要执行一遍清空的操作（访问到之前进程的残余是有风险的），但是实际上做的是OS先把这个页记录下来，等到真的被call的时候再去执行清空操作
  • copy-on-right：如果需要复制，实际上不会立刻复制，而是先建立一个映射并且都标记为只读，只有当某一方需要写的时候才触发trap并真的建立一份副本