Cache Hit / Cache Miss#

1. cache hit（命中）

   • 处理器要的数据已经在 cache 中；
   • 这时直接从 cache 返回，处理器几乎感觉不到“下面还有主存”这件事。

2. cache miss（失效）

   • 处理器要的数据不在 cache 中；
   • 这时就必须继续访问下层存储，把数据取回来。

对处理器来说，hit 和 miss 的差别非常大：

• hit 时，控制逻辑很简单；
• miss 时，不仅要访问下层 memory，还可能要 replacement、write-back，甚至让整个处理器 stall。

Block / Line#

cache 和 memory 之间传输数据时，基本单位不是单个 word，而是：

• block（块）
• 也常叫 cache line（缓存行）

它表示的是：

一组固定大小的数据，其中包含了当前请求的那个 word。

NOTE

为什么不只搬一个 word？

• 空间局部性说明：既然访问了这个地址，附近地址的数据很可能也快要用了；
• 所以一次 miss 时顺手把整个 block 一起搬上来，通常更划算。

对应而生的参数：

• byte offset 决定 block 内具体取哪个字节；
• index 决定这个 block 去 cache 的哪一行/哪一组；
• tag 决定当前这行里放的是不是我要的那个 block。

Direct Mapped#

direct mapped cache（直接映射） :

一个 memory block 只能去 cache 里的一个固定位置。

优点：

• 实现最简单；
• 查找快；
• hit time 往往较小。

缺点：

• 灵活性最差；
• 很容易出现 conflict miss。

Fully Associative#

fully associative cache（全相联） : 一个 memory block 可以放到 cache 中任意位置。

优点：

• 放置最灵活；
• conflict miss 最少。

缺点：

• 查找最贵；
• 需要比较所有 tag；
• 硬件开销大。

Set Associative#

set associative cache（组相联） 处于两者之间。

如果是 n-way set associative，表示：

• cache 被分成若干 set（组）；
• 每个 set 里有 n 个 block；
• 一个 memory block 先确定自己属于哪一组；
• 进入该组后，再从这组里的 n 个位置中挑一个。

三者其实可以都看作 Set Associative：

• direct mapped = 1-way set associative
• fully associative = 整个 cache 只有一组

TIP

• associativity 不是越大越好；
• associativity 越高，冲突越少，但查找和 replacement 逻辑也越复杂；
• 实际系统里，很多 cache 的 associativity 常见是 n ≤ 4。

NOTE

why index with the middle bits。

核心原因是：

• 低位已经被 block offset 占掉，不能再用来选 set；
• 如果直接拿高位做 index，那么很多连续地址会扎堆映射到同一个 set；
• 这会破坏空间局部性本来带来的好处。

所以更常见的做法是：

• 保留最低位给 offset
• 用中间若干位做 index
• 把更高位留给 tag

这样连续地址更容易分散到相邻 set，局部性利用会更自然。

Example#

设：

• $M$：Cache 总块数
• $n$：每组中的块数，即相联度（associativity）
• $G$：组数（number of sets）

则有：

• 全相联（full-associative）

  • $n = M$
  • $G = 1$
  • 整个 Cache 只有一组，主存块可放入任意 Cache 块中

• 直接映射（direct mapped）

  • $n = 1$
  • $G = M$
  • 每组只有一个块，主存块只能映射到唯一位置

• 组相联（set-associative）

  • $1 < n < M$
  • $1 < G < M$
  • 主存块先映射到某一组，再放入该组内任意一个块中

相联度 $n$ 越大，优点：

• Cache 空间利用更充分
• 块冲突（block collision） 更少
• 冲突失效（conflict miss） 降低
• 整体 miss rate 往往下降

缺点：

• 命中判断更复杂，需要比较更多 tag
• 硬件成本更高
• 功耗增加
• 命中时间（hit time）可能变长
• 替换策略（如 LRU）实现更复杂

实际设计中，大多数 Cache 的相联度不会太高，常见为：

即通常采用 2-way 或 4-way set-associative cache。

查找方式#

Direct Mapped#

• index 选中唯一一行；
• 看这一行的 valid；
• 再把请求地址的 tag 和该行的 tag 比较；
• 相等则 hit，否则 miss。

特点：

• 查找路径最短；
• 但如果别的 block 映射到同一行，就一定会冲突。

Fully Associative#

Assume cache has 4 blocks

fully associative 最灵活，也最贵：

• 没有传统意义上的 index；
• 访问时必须对所有行的 tag 做比较；
• 任意一行匹配就算 hit。

因此它通常只在规模较小、对灵活性要求很高的结构里更适合。

Set Associative#

• Assume cache has 4 blocks and each block is 1 word
• 2 blocks per set, hence 2 sets per cache

• index 先选中一组；
• 组内每一行都要看 valid，并比较 tag；
• 只要组内某一行匹配，就 hit。

因此它比 direct mapped 多出来的，是：

• 组内并行比较多个 tag；
• 以及 miss 时还得在组内决定替换谁。

FSM Control Simple Cache#

Cache 的行为是一个时序过程。
一次访存请求到来后，控制器可能需要依次完成：

• 接收 CPU 请求
• 比较 Tag
• 判断命中 / 失效
• 判断被替换块是否为脏块（dirty）
• 若脏，则先写回主存（write-back）
• 再从主存读入新块（allocate）
• 最后通知 CPU Cache 已准备好

Cache Controller 适合建模成一个 有限状态机。

FSM#

一个有限状态机通常包括三部分：

• 当前状态（current state）
• 输入（inputs）
• 输出（outputs）

并由两类逻辑决定行为：

1. 下一状态函数 根据：当前状态、当前输入，决定：下一拍进入哪个状态
2. 输出函数 根据：当前状态、有时还包括输入，产生：对数据通路（datapath）的控制信号
   例如：是否读主存、是否写主存、是否更新 valid/tag/dirty、是否通知 CPU ready 等。

State Machine#

Cache 容量计算#

• 地址长度：$A$ bits
  （例如 64 位地址时，$A=64$）
• Cache 数据区共有 $L$ 个 cache line（或 block）
• 每个 block 大小为 $2^m$ words
• 每个 word = 4 bytes = 32 bits
• 相联度（associativity）为 $k$
  • direct-mapped：$k=1$
  • $k$-way set-associative：$1<k<L$
  • full-associative：$k=L$
• 组数为 $S$

则有：

Example#

替换策略#

常见的替换策略有：Random / FIFO / LRU / OPT

LRU#

LRU（Least Recently Used，最近最少使用） 是最经典也最符合 locality 直觉的策略之一：

• 认为最近刚访问过的 block，更可能很快又被访问；
• 因此优先淘汰最久没被访问过的 block。

既然无法预测未来，那就让已经发生的访问历史来帮助猜测未来。

优点：

• 和 temporal locality 很契合；
• 通常表现优于纯随机和 FIFO。

缺点：

• 需要额外记录访问顺序；
• associativity 一大，硬件代价就会上升得很快。

Example#

2, 3, 2, 1, 5, 2, 4, 5, 3, 4

• cache block 数量：3
• 访问序列：

1
2, 3, 2, 1, 5, 2, 4, 5, 3, 4

hit 次数：

• replacement policy 确实会直接影响 hit rate；
• 而 hit rate 的变化，最终又会传导到 miss rate 和 AMAT。

Thrashing and Belady Anomaly#

Thrashing#

如果工作集比 cache 能承受的更大，并且访问序列不断在几组数据之间来回切换，就会出现 thrashing（抖动）。

典型序列：

1
1, 2, 3, 4, 1, 2, 3, 4

当 cache 太小、映射又不友好时：

• 刚装进来的数据很快又被挤掉；
• hit 非常少；
• 系统大部分时间都花在 miss 和 replacement 上。

thrashing 的本质就是：

• 工作集大于有效 cache 容量
• 映射冲突太严重

Comparison Pair#

如果想精确实现 LRU，可以使用 comparison pair method（成对比较法）。

基本思想是：

• 对组内每两个 block 记录谁比谁更新近；
• 然后用这些 pairwise 状态推导出谁是最久未使用者。

例如 3 个 block A, B, C 时，可以维护：

• T_AB
• T_AC
• T_BC

但这个方法的代价增长非常快。 $C_p^2$

• 3 个 block：需要 3 个 flip-flop
• 4 个 block：需要 6 个 flip-flop
• 8 个 block：需要 28 个 flip-flop
• 64 个 block：需要 2016 个 flip-flop

所以：

• 精确 LRU 在 associativity 较高时硬件代价非常大
• 这也是为什么实际处理器里经常用 pseudo-LRU（近似 LRU），而不是严格 LRU

Write Hit#

Write-Through vs Write-Back

Write Miss#

Write Allocate vs No-Write-Allocate

write miss 时，策略分歧主要在：

要不要先把目标 block 装进 cache？

常见组合#

理论上 write hit 和 write miss 策略可以自由组合，但有两种最常见组合：

1. write-back + write-allocate

   • 写 miss 时先把 block 调上来；
   • 后续读写都更可能 hit；
   • 真正回 memory 等 replacement 再说。

2. write-through + no-write-allocate

   • 写 miss 时直接写 main memory；
   • 不把数据引入 cache；
   • 简单、直观，也避免无意义占用 cache。

性能优先 -> 更偏 write-back + write-allocate 一致性 / 可预测性优先 -> 更偏 write-through + no-write-allocate

Write Stall and Write Buffer#

write-through 的一个直接问题是：

• 每次写都可能要等 main memory；
• CPU 很容易被迫停下来。

这就是 write stall（写停顿）。

一种非常常见的优化是：

• write buffer（写缓冲）

它的思路是：

• CPU 先把要直写的数据放入一个小 buffer；
• 然后继续执行后续指令；
• 由 buffer 在后台慢慢把数据推到 memory。

这样可以明显减轻 write-through 的性能损失。
但它也不是万能的，因为：

• 如果短时间内写太密集；
• buffer 还是可能被写满；
• 写满后 CPU 仍然要 stall。

Example#

No-Write-Allocate vs Write-Allocate

条件：

• fully associative
• write-back
• cache 很大，不考虑 replacement
• 初始为空
• 访问序列如下：

1
1. write Mem[100]
2
2. write Mem[100]
3
3. read  Mem[200]
4
4. write Mem[200]
5
5. write Mem[100]

比较：

• no-write-allocate
• write-allocate

Case 1：No-Write-Allocate

1. write Mem[100]

   • write miss
   • 直接写 memory，不装入 cache
   • miss

2. write Mem[100]

   • cache 中仍没有这个 block
   • 还是 miss

3. read Mem[200]

   • 读 miss
   • 把 block 200 调入 cache
   • miss

4. write Mem[200]

   • 此时 block 200 已在 cache 中
   • hit

5. write Mem[100]

   • 100 对应 block 仍不在 cache 中
   • miss

因此结果是：

总计：

• 1 hit
• 4 misses

Case 2：Write-Allocate

1. write Mem[100]

   • write miss
   • 但因为采用 write allocate，要先把 100 所在 block 调到 cache
   • 再写入 cache
   • miss

2. write Mem[100]

   • 100 所在 block 已经在 cache 中
   • hit

3. read Mem[200]

   • 第一次访问 200
   • miss
   • 并把 200 所在 block 调入 cache

4. write Mem[200]

   • 200 所在 block 刚才已经调入
   • hit

5. write Mem[100]

   • 100 所在 block 也还在 cache 中
   • hit

所以结果是：

总计：

• 3 hits
• 2 misses

如果后续确实还要继续访问这个 block；那么 write allocate 往往更合适。也就是说，write allocate 的效果本质上还是靠 locality 在支撑。

Small and Simple First-Level Caches#

L1 cache 几乎每次访存都会经过，所以 L1 的 hit time 往往比它的 miss rate 更敏感。

核心思路：

• L1 不做得太大；
• associativity 不做得太高；
• 让 tag compare、data access、way select 这条关键路径尽量短。

优点：

• hit 更快；
• 往往也更省电。

代价：

• 容量小、相联度低时，可能增加 miss rate；
• 需要依赖更大的 L2 / L3 来兜底。

所以经典设计通常是：

• 小而快的 L1
• 大而慢的 L2 / L3

Way Prediction#

组相联 cache 的问题在于：
为了知道哪一 way 命中，通常要比较多个 tag，再做数据选择，这会拉长 hit time。

way prediction 的做法是：

• 先预测“这次大概率命中哪一 way”；
• 先按这个预测去访问；
• 如果预测正确，就接近 direct-mapped 的 hit path；
• 如果预测错误，再补查其他 way，付出额外延迟。

本质上它是在做这样的折中：

• 用少量预测状态
• 换取 平均 hit time 的下降

适合场景：

• 组相联 cache；
• 对 hit time 很敏感的前端 / L1。

代价：

• 预测错时会有额外 penalty；
• 数据 cache 上做 way prediction 一般比 I-cache 更麻烦，因为误判更容易影响后续流水线。

Pipelined Caches#

把一次 cache access 拆成多个 pipeline stage，例如：

• 地址/index 处理
• tag compare
• data array access
• 返回结果

这样做的好处是：

• 可以提高时钟频率；
• cache 本身吞吐更高。

但要注意：

• 带宽上升，不代表单次访问 latency 下降
• 有时 latency 反而更高了

影响：

• I-cache pipeline 更深，会放大 branch misprediction 的代价；
• D-cache pipeline 更深，会增加 load-use latency。

所以 pipelined cache 更像是在用 更长的访问流水，换 更高的频率和吞吐。

Multibanked Caches#

把一个 cache 分成多个独立 bank，让不同访问可以并行落到不同 bank：

• 若两个请求去不同 bank，可以同周期并行；
• 若两个请求撞到同一个 bank，就会出现 bank conflict。

优点：

• 提高并发访问能力；
• 对 superscalar、多发射、多 load/store 系统尤其重要。

代价：

• bank 映射和仲裁逻辑更复杂；
• 存在 bank conflict；
• 程序访问模式会直接影响收益。

所以它本质上是在做：

• 把一个大缓存拆成多个可并行的小通道

Nonblocking Caches#

传统 blocking cache 在 miss 时会卡住后续访问。
nonblocking cache 则允许：

• hit under miss：一个 miss 正在处理时，后续 hit 还能继续；
• miss under miss：甚至允许多个 miss 并行在途。

直观理解：

• miss 不再把整个 cache 前端“封死”；
• 处理器能把部分等待隐藏掉。

关键实现点：

• 要记录多个 outstanding misses；
• 常见做法是用 MSHR（Miss Status Handling Register） 跟踪每个 miss 的去向、返回数据该填到哪里、唤醒哪条 load/store。

优点：

• 显著降低 effective miss penalty；
• 对 memory-level parallelism 较高的程序很有效。

代价：

• 控制逻辑明显更复杂；
• 需要处理返回乱序、命中/失效碰撞、coherence 等问题。

Multilevel Caches#

这是最基本也最常见的方法：

• L1 miss 后先查 L2；
• L2 miss 后再查 L3；
• 最后才去 main memory。

作用：

• 把“直接掉到主存”的昂贵 miss，改成“更低一级 cache hit”的相对便宜 miss；
• 从而降低 effective miss penalty。

代价：

• hierarchy 更复杂；
• inclusive / exclusive / non-inclusive 等策略会影响设计；
• 多级之间的一致性和替换关系更复杂。

Critical Word First / Early Restart#

一次 miss 往往是按 block 为单位搬运的。
但处理器真正急需的，常常只是其中一个 word。

因此可以：

• Critical Word First：先取当前最需要的那个 word；
• Early Restart：只要关键 word 到了，就先让处理器继续执行，剩余部分稍后补齐。

作用：

• 不一定减少总传输量；
• 但可以减少处理器真正“卡住”的时间。

适合场景：

• block 较大；
• miss penalty 中“首字返回延迟”占比较高。

Read Miss Priority Over Write Miss#

读 miss 往往直接阻塞程序继续执行；
写请求很多时候可以先暂存在 write buffer 里。

所以常见策略是：

• 读优先于写
• 尤其是 read miss priority over write miss

这样做可以：

• 让关键路径上的 stall 更少；
• 避免写流量把读请求拖住。

Merging Write Buffers#

如果 write buffer 中有多次写，目标恰好落在同一 cache line 或相邻区域，就可以合并：

• 减少总线事务数；
• 减少下层存储压力；
• 降低写流量对读 miss 的干扰。

优点：

• 对 write-through cache 特别常见；
• 硬件代价通常不算太夸张。

代价：

• 需要检测可合并性；
• buffer 管理更复杂。

Victim Cache#

victim cache 是一个很小的、通常是 fully-associative 的缓冲区，
专门保存 刚从主 cache 被替换出去的 block。

工作方式：

• L1 hit：直接返回；
• L1 miss 且 victim cache hit：通常执行 swap，把 victim cache 中的目标块和 L1 中冲突块交换；
• L1 miss 且 victim cache miss：再访问下层存储。

它针对的核心问题是：

• conflict miss
• 且通常是 被替换后很快又重用 的那类 conflict miss

优点：

• 不把额外复杂度放到 L1 正常 hit path 上；
• 对 direct-mapped cache 很有吸引力；
• 常能以很小硬件代价显著缓解“ABAB 式冲突抖动”。

局限：

• 对 capacity miss 帮助有限；
• 对长 reuse distance、流式访问帮助也有限；
• 它不是一个“正常的额外 cache level”，而是一个 专门接住 victim line 的小旁路结构。

Larger Block Size#

block 变大以后，一次 miss 会顺带把附近更多数据带上来，因此：

• spatial locality 利用更充分；
• compulsory miss 往往下降。

但副作用也很明显：

• miss penalty 变大；
• 同样 cache 容量下，block 数变少；
• 可能加重 conflict miss / capacity miss。

所以 block size 永远是 locality 和 penalty 的折中。

Larger Cache Size#

cache 更大时，能留下更多 block，因此：

• capacity miss 一般下降。

但代价是：

• 成本和面积增加；
• 功耗上升；
• hit time 可能变长。

因此：

• L1 通常不会做得很大；
• 更大的容量往往放到 L2 / L3 / LLC。

Higher Associativity#

提高 associativity 的核心作用是：

• 把“只能放一个位置”变成“能在同组多个位置中选一个”
• 从而减少 conflict miss

优点：

• 对冲突敏感的工作负载常常有效。

代价：

• tag compare 更多；
• replacement 逻辑更复杂；
• hit time 往往更长；
• 功耗也会增加。

所以常见的理解就是：

• direct-mapped：快，但脆弱
• higher associativity：稳，但贵

Compiler Optimizations#

有些 miss 不是硬件“命不好”，而是程序访问顺序本身写得不友好。

编译器常见优化包括：

Hardware Prefetching#

核心思想：

• 在处理器真正发出 demand access 之前，
• 预测它很快会用到哪些数据，
• 然后提前取回来。

常见形式：

• next-line prefetch
• stream buffer
• stride prefetch
• 更复杂的相关性预取

优点：

• 若预取及时，可把后续 miss 变成 hit；
• 若不够及时，也能降低 miss penalty。

代价：

• 预取错会浪费带宽；
• 还可能污染 cache；
• 对功耗也可能有负面影响。

所以 prefetch 的本质是：

• 用多做一点“可能没必要的工作”
• 去换 关键时刻少等一点

Compiler-Controlled Prefetching#

这类方法由编译器显式插入 prefetch 指令：

• 在真正用到数据之前若干迭代，先发预取；
• 目标通常是让访问和计算重叠。

优点：

• 编译器更了解循环结构和访问模式；
• 对规则数组访问特别有效。

前提：

• 必须给预取留出足够“提前量”；
• cache 通常需要是 nonblocking 的，否则预取本身又会把执行卡住。

代价：

• 会增加指令数；
• 预取距离不好选；
• 程序行为稍变，效果可能就明显波动。

Using HBM to Extend the Memory Hierarchy#

HBM（High Bandwidth Memory） 是把 DRAM 堆叠起来，放得更靠近处理器/加速器的一种近存储方案。

特点：

• 总线非常宽；
• 带宽很高；
• 容量通常不如外部大容量 DRAM；
• 成本和封装要求更高。

在 hierarchy 中，HBM 常见角色是：

• 作为高带宽近内存；
• 作为比 DDR 更快但更贵的一层；
• 有时也可视作 L4 / near-memory cache。

它解决的主要矛盾是：

• 传统 DDR 容量够，但带宽不够
• HBM 带宽很强，但容量和成本受限

Using CXL to Extend the Memory Hierarchy#

CXL（Compute Express Link） 可以把外部内存设备、加速器和主机以 cache-coherent 的方式连起来。

从 memory hierarchy 视角看，它的重要价值是：

• 支持 memory expansion（内存扩展）
• 支持 memory pooling（内存池化）
• 支持 memory sharing（内存共享）
• 让部分“原本不在本机板上的内存”也能进入层次结构

可以把它理解成：

• 在本地 DDR / HBM 之下，
• 引入一层 更远、通常更慢、但更灵活、更大 的扩展内存层。

优点：

• 提升容量弹性；
• 资源利用率更高；
• 对数据中心和大规模异构系统很重要。

代价：

• 延迟通常高于本地 DRAM；
• QoS、coherence、资源管理都更复杂；
• 更适合作为“较远的一层内存”，不适合作为最靠近核心的高速层。

Using UnifiedBus to Extend the Memory Hierarchy#

这里把 UnifiedBus 理解为近年来“统一互连 / memory-semantic fabric / 资源池化总线”这一类方案。

它的目标通常是：

• 把 CPU、GPU、NPU、内存和 I/O 设备放到更统一的互连语义下；
• 让远端内存、池化内存、异构设备内存更容易被系统按层次结构使用；
• 支持更大范围的资源共享与扩展。

直观理解：

• 传统 memory hierarchy 多是在单机板内分层；
• UnifiedBus 这类方案是在 更大系统范围 上继续分层。

优点：

• 容量扩展强；
• 资源池化能力强；
• 对大规模 AI / 数据中心系统有吸引力。

代价：

• 延迟一定高于本地 cache / DRAM；
• 流控、QoS、容错、隔离、安全都更难；
• 软件栈和资源调度复杂度明显上升。

扩容：Main Memory + Secondary Storage#

1
Virtual Memory = Main Memory + Secondary Storage

也就是：

• main memory 保存当前活跃的数据和指令；
• secondary storage 保存暂时不在内存中的页；
• OS 通过 page fault / page replacement 在两者之间调入调出。

这和 cache hierarchy 的思想是一致的：

• CPU 希望大多数访问都在快层级命中；
• 访问不到时，再去慢层级取。

区别是：virtual memory 的下一级可能是 disk / SSD，miss penalty 极大，因此设计上会尽量降低 virtual memory miss 的概率。

灵活管理：物理地址可以不连续#

没有 virtual memory 时，程序如果直接使用 physical address，就必须面对真实物理内存的布局。多个进程运行、换入换出之后，物理内存容易出现碎片。

有 virtual memory 后：

• 进程看到的是连续 virtual address；
• OS 可以把它映射到不连续 physical frames；
• 页表记录这种映射关系。

这让物理内存分配更灵活，也方便 OS 在多进程场景下管理空间。

隔离与保护：每个进程有自己的地址空间#

Virtual memory 的另一个关键作用是 process isolation。

每个进程都有自己的 page table：

1
Process A virtual address  ── Page Table A ──> Physical pages for A
2
Process B virtual address  ── Page Table B ──> Physical pages for B

即使两个进程使用了相同的 virtual address，例如都访问 0x4000，它们也可以通过不同的 page table 映射到不同的 physical page。

这样可以做到：

• A 访问不到 B 的私有物理页；
• B 访问不到 A 的私有物理页；
• OS 可以显式决定哪些页允许共享；
• 用户程序不能随便修改 page table。

WARNING

Virtual memory 提供的是机制上的隔离基础，不代表系统绝对安全。攻击和防护都可能围绕 page table、权限位、地址空间隔离、进程上下文展开。

Paged Virtual Memory#

分页把虚拟地址空间切成固定大小的 page。

地址形式：

1
page address = page number || page offset

例如 4KB page：

• page size = $2^{12}$ bytes；
• page offset = 12 bits；
• 剩下的高位作为 page number。

优点：

• 每个 page 大小相同；
• 替换和分配简单；
• 适合用 page table 建立索引。

缺点：

• 会产生 internal fragmentation（内部碎片）；
• 如果程序只用了一个 page 的一部分，剩余空间仍然被这个 page 占用。

Segmented Virtual Memory#

分段按逻辑模块或程序结构划分，每个 segment 可以有不同大小。

地址形式：

1
segment address = segment number + offset

优点：

• 更贴近程序逻辑结构；
• 不同 segment 可以按实际需要分配不同大小。

缺点：

• segment 大小不固定；
• 替换、分配、压缩更复杂；
• 容易产生 external fragmentation（外部碎片）。

Paging vs Segmentation#

现代系统通常会组合使用分段与分页的思想

Q1：Where can a block be placed in main memory?#

fully associative strategy。

在 virtual memory 层级中，一个 virtual page 可以放到 main memory 中几乎任意一个可用 physical frame。

原因：

• virtual memory miss penalty 极大；
• 如果因为“固定映射位置”导致冲突 miss，代价无法接受；
• 因此 OS 通常允许 page 放在任意可用 frame 中。

这和 cache 的 direct mapped 形成对比：

• cache 追求 hit path 简单、速度快；
• virtual memory 更重视降低 miss rate。

Q2：How is a block found if it is in main memory?#

通过 page table。

Virtual address 可以拆成：

1
Virtual Address = VPN || page offset

Physical address 可以拆成：

1
Physical Address = PPN || page offset

其中：

• VPN：Virtual Page Number；
• PPN：Physical Page Number / Physical Page Frame Number；
• page offset：页内偏移，翻译前后保持不变。

地址翻译的核心就是：

1
VPN ──查 Page Table──> PPN
2
PPN || page offset ──> Physical Address

NOTE

Page table 记录的是 page-level 的映射，所以它只需要翻译页号部分；页内偏移不需要改变。

Q3：Which block should be replaced on a virtual memory miss?#

通常希望替换 least recently used page，实际 OS 会用近似算法。

LRU 在 virtual memory 中通常通过 use bit / reference bit 近似实现：

• page 被访问时，硬件或 OS 逻辑设置 use bit；
• OS 周期性清除 use bit；
• 之后再观察哪些 page 被重新访问；
• 长时间未被访问的 page 更可能被替换。

完全精确的 LRU 维护成本很高，因此 OS 通常采用 Clock / Second Chance 等近似策略。

Q4：What happens on a write?#

采用 write-back strategy。

原因：

• virtual memory 的下一级可能是 disk / SSD；
• 每次写都同步写回 secondary storage 成本太高；
• 只有 page 被替换且内容被修改过时，才需要写回。

这需要 dirty bit：

• dirty = 0：page 内容没有被修改，替换时可以直接丢弃；
• dirty = 1：page 内容已经修改，替换前必须写回 secondary storage。

Page Table 的基本作用#

Page table 的作用是保存 virtual page 到 physical page 的映射关系。

1
virtual address = VPN || page offset
2
                     |
3
                     v
4
                Page Table
5
                     |
6
                     v
7
physical address = PPN || page offset

一次地址翻译可以写成：

1
VPN    = virtual_address[high bits]
2
offset = virtual_address[page-offset bits]
3
PPN    = page_table[VPN]
4
physical_address = PPN || offset

Page Table Size Example#

假设：

• virtual address = 32 bits；
• page size = 4KB = $2^{12}$ bytes；
• PTE（page table entry）大小 = 4 bytes = $2^2$ bytes。

则虚拟页数量为：

page table 总大小为：

所以即使只是 32-bit virtual address，单级页表也可能很大。

TIP

page table size 和两个因素直接相关：

• virtual address space 越大，VPN 数量越多，page table 越大；
• page size 越大，VPN 数量越少，page table 越小。

为什么需要 TLB？#

Page table 通常存放在 main memory 中。

如果没有 TLB，一次 data access 逻辑上需要两次 memory access：

1. 访问 page table，得到 PPN；
2. 用 physical address 访问真正的数据。

这会让访存时间近似翻倍。

解决方法是增加一个专门缓存地址翻译结果的小 cache：

1
TLB = Translation Lookaside Buffer

TLB 保存最近用过的 virtual page 到 physical page 的翻译关系。

TLB Hit#

TLB hit 时：

1
VA = VPN || offset
2
TLB[VPN] -> PPN
3
PA = PPN || offset

此时不需要访问 page table，地址翻译非常快。

TLB Miss#

TLB miss 时：

1. 需要通过 page table walker 查询 page table；
2. 找到 PTE 后得到 PPN 和权限信息；
3. 把新的翻译结果填入 TLB；
4. 再次访问时即可 TLB hit。

如果 page table 中没有有效映射，或者权限不满足，就会触发 page fault。

TLB Access Steps#

1. 发送虚拟地址到所有 tag

   • TLB 中的多个 entry 同时比较；
   • 只有 valid entry 才参与匹配。

2. 检查访问类型和权限

   • load / store / instruction fetch 对权限要求不同；
   • protection field 决定当前访问是否合法。

3. 匹配 tag 并选择 PPN

   • 命中的 entry 通过 mux 输出对应的 physical page frame number。

4. 拼接 page offset

   • PPN || page offset 形成最终 physical address。

NOTE

TLB 和 cache 的思想相同：把近期常用信息保存在小而快的结构中。区别在于 cache 缓存数据，TLB 缓存地址翻译结果。

Larger Page Size 的优点#

更大的 page size 会带来：

• page table 更小；
• 同样数量的 TLB entry 可以覆盖更大的地址范围；
• TLB miss 次数可能减少；
• 从 secondary storage 调入调出时，较大块传输更高效。

这类似 cache 中较大 block size 对 spatial locality 的利用。

Larger Page Size 的代价#

更大的 page 也有明显代价：

• 内部碎片更严重；
• page fault 时一次调入更多数据，单次 miss penalty 更高；
• 如果程序局部性不好，会搬入很多用不到的数据。

Smaller Page Size 的优点#

更小的 page size 可以：

• 减少内部碎片；
• 更精细地管理内存；
• 对小对象和稀疏访问更友好。

Multiple Page Sizes#

现代处理器常支持 multiple page sizes，例如常规页和 huge page。

原因：

• 小页适合细粒度管理；
• 大页适合大连续内存区域；
• 大页能减少 TLB miss；
• 某些程序中，TLB miss 对 CPI 的影响可以接近 cache miss。

基本位宽#

page size = 8KB：

所以：

1
page offset = 13 bits
2
VPN = 64 - 13 = 51 bits
3
PPN = 41 - 13 = 28 bits

physical address：

1
Physical Address = PPN || page offset
2
                 = 28 bits || 13 bits
3
                 = 41 bits

TLB 位宽#

TLB 有 256 entries：

在这个例子中，可以理解为：

1
TLB index = 8 bits
2
TLB tag   = VPN - TLB index = 51 - 8 = 43 bits

TLB 命中后输出 PPN = 28 bits，再与 13-bit page offset 拼接成 41-bit physical address。

L1 Cache 位宽#

L1 cache = 8KB = $2^{13}$ bytes，block size = 64B = $2^6$ bytes。

因此 L1 line 数为：

所以：

1
L1 block offset = 6 bits
2
L1 index        = 7 bits
3
L1 tag          = 41 - 7 - 6 = 28 bits

注意这里：

1
L1 index + block offset = 7 + 6 = 13 bits = page offset

page offset 在地址翻译前后不变，因此 L1 的 index 可以直接从 virtual address 的低 13 位中取出；同时，真正的 tag 比较仍然依赖翻译得到的 physical address 高位。

TIP

这就是很多处理器中常见的思路：

• 用 page offset 中的位先索引 L1；
• TLB 并行翻译得到 physical tag；
• 再用 physical tag 做最终比较。

这样可以把 TLB lookup 和 L1 access 尽量并行化。

L2 Cache 位宽#

L2 cache = 4MB = $2^{22}$ bytes，block size = 64B = $2^6$ bytes。

L2 line 数为：

因此：

1
L2 block offset = 6 bits
2
L2 index        = 16 bits
3
L2 tag          = 41 - 16 - 6 = 19 bits

访问过程可以概括为：

1
1. CPU 产生 virtual address
2
2. TLB 查询 VPN -> PPN
3
3. 同时用 page offset 中的一部分索引 L1
4
4. TLB 输出 physical tag 后，与 L1 tag 比较
5
5. L1 hit：返回数据
6
6. L1 miss：用 physical address 继续查 L2
7
7. L2 miss：访问 main memory

地址翻译伪代码#

1
function access(virtual_address):
2
    vpn    = virtual_address[63:13]
3
    offset = virtual_address[12:0]
4

5
    if TLB.hit(vpn):
6
        ppn = TLB[vpn].ppn
7
    else:
8
        pte = page_table_walk(vpn)
9
        if !pte.valid or !pte.permission_ok:
10
            raise page_fault
11
        ppn = pte.ppn
12
        TLB.insert(vpn, ppn, pte.permission)
13

14
    physical_address = ppn || offset
15

16
    if L1.hit(physical_address):
17
        return L1.data
18
    else if L2.hit(physical_address):
19
        fill_L1_from_L2()
20
        return L2.data
21
    else:
22
        fetch_from_memory()
23
        fill_L2_and_L1()
24
        return data

Multiprogramming#

Multiprogramming 允许多个程序并发运行，共享同一台机器。

因此系统需要同时解决：

• protection：一个程序不能随便破坏另一个程序；
• sharing：某些资源又需要被多个程序共享。

Process#

一个 process 可以理解为：

一个正在运行的程序，加上它继续运行所需的全部状态。

Process state 包括：

• PC；
• registers；
• stack；
• heap；
• page table；
• OS 维护的进程控制信息。

Time-sharing 让多个用户或多个程序共享 CPU 和 memory，并给每个程序一种“自己独占机器”的假象。

当 OS 从一个 process 切换到另一个 process 时，需要进行 context switch：

• 保存旧进程的处理器状态；
• 加载新进程的处理器状态；
• 切换地址空间相关信息，例如 page table base。

Process Protection#

进程保护依赖体系结构和操作系统共同完成。

硬件设计者需要保证：

• 处理器状态可以被保存和恢复；
• 用户态不能随便执行高权限操作；
• 地址翻译与权限检查不能被用户程序绕过。

OS 设计者需要保证：

• 不同进程的 page table 指向正确的 physical pages；
• 用户程序不能修改自己的 page table；
• 共享页必须由 OS 显式建立。

Proprietary Page Tables#

最基本的隔离方式是每个进程拥有自己的 page table。

1
Process A page table -> A 的 physical pages
2
Process B page table -> B 的 physical pages

如果需要共享内存，OS 可以让两个 page table 的某些 entry 指向同一个 physical page：

1
Process A page table entry ─┐
2
                            ├── shared physical page
3
Process B page table entry ─┘

这样既能隔离私有空间，又能支持共享库、共享内存、copy-on-write 等机制。

Rings#

Rings 是一种多级权限保护结构。

大致思想：

• 最内层权限最高，可以访问所有资源；
• 外层权限逐渐降低；
• 普通用户程序在最低权限层，只能访问受限资源。

在 RISC-V 中，类似思想体现为 privilege levels：

• M-mode：Machine mode，最高权限；
• S-mode：Supervisor mode，通常运行 OS kernel；
• U-mode：User mode，运行用户程序。

Keys and Locks#

Keys and locks 是另一类保护思想：

• 数据像被 lock 保护；
• 程序必须持有对应 key / capability 才能访问。

关键点是：

• key 不能由普通程序伪造；
• 硬件和 OS 必须能安全地传递 key；
• 权限本身必须受到保护。

Virtual Memory#

Virtual memory 主要虚拟的是 memory：

1
virtual address space -> physical memory / secondary storage

它解决的是：

• 地址空间抽象；
• 地址翻译；
• 内存扩容；
• 进程隔离；
• 页级保护与共享。

Virtual Machine#

Virtual machine 虚拟的是整台机器。

在 CPU 和 OS 之间有一层：

1
Hardware / CPU
2
      |
3
VMM / Hypervisor
4
      |
5
Guest OS
6
      |
7
Applications

VMM / hypervisor 向 guest OS 提供一个“像真实硬件一样”的抽象，让多个 OS 可以共享同一台物理机器。

因此：

• virtual memory 是 OS + MMU 提供的地址空间机制；
• virtual machine 是 hypervisor 提供的机器级虚拟化机制；
• 两者都会涉及地址翻译、权限保护和资源隔离。