计算机系统 Lecture 1：虚拟内存详解

Part I：TLB命中示例

1、存储器层次结构

因此，现代计算机系统通常把各种不同存储容量、存取速度和价格的存储器按照一定的体系组成多层结构，以解决存储器容量、存取速度和价格之间的矛盾。

分层存储（Tiered Storage）的理论基础是：局部性原理，其中包括时间局部性与空间局部性 2 类：

• 时间局部性（Temporal locality）：如果某个信息这次被访问，那它有可能在不久的未来被多次访问（比如：循环）。
• 空间局部性（Spatial locality）：如果某个位置的信息被访问，那和它相邻的信息也很有可能被访问到（比如：数组）。

上图为 MIT 6.004 Computation Structures 课程中非常经典的一张存储器层次结构图：从上到下，容量更大，访问速度更慢、价格更便宜。

在计算机系统中：内存/DRAM 被称为主存（Primary Storage），磁盘/Disk 被称为辅助存储器/次级存储器（Secondary Storage）。

2、物理内存与物理寻址

计算机系统的主存（Primary Storage）被组织成一个由 M 个连续的字节（bytes）大小的单元组成的数组。每字节都有一个唯一的物理地址（Physical Address，PA）。

CPU 访问内存的最自然的方式就是使用物理地址。我们把这种方式称为物理寻址（physical addressing）。

Part I：物理寻址的3个问题

1. 物理内存不足

在一个 32-bit 的操作系统中，CPU 能够提供 2^32（bytes）= 4GB 的程序地址空间，如果该操作系统只有 1GB DRAM 物理内存。如果采用物理寻址，当应用程序的访问地址空间（4GB）超过物理内存的实际地址空间（1GB DRAM）范围时，就会导致程序崩溃。

1. 内存碎片化

在一个 32-bit 的操作系统中，如果该操作系统同时拥有 4 GB 的 DRAM，首先运行程序 1（占用 1GB 连续 DRAM）与程序 2（占用 2GB 连续 DRAM），此时程序 3 无法正常运行（占用 2GB 连续 DRAM）。

此时程序 1 退出，剩余 2 GB RAM，程序 3 依然无法运行。因为剩余的 2 GB RAM内存空间不是连续的。

1. 内存安全问题

每个程序都可以访问 4GB 的物理内存地址空间，如果多个程序访问相同的物理地址，会导致数据污染或崩溃。

3、虚拟内存

怎么才能解决物理寻址的 3 个问题？

计算机领域有一句名言：“All problems in computer science can be solved by another level of indirection."（计算机科学领域的任何问题都可以通过增加一个间接的中间层来解决。）通过引入虚拟内存来解决物理寻址的带来的上述问题。

虚拟内存是物理内存和进程地址空间之间的中间层，它为进程隐藏了物理内存这一概念。虚拟内存提供了 3 个重要的能力：

• 简化内存管理：为每个进程提供了一致的地址空间（在一个 32-bit 的操作系统中，每个进程都拥有 2^32（bytes）= 4GB 的程序地址空间），从而简化了链接、加载、内存共享等过程；
• 高效使用内存：将进程的地址空间存储在磁盘上，将主存看成是存储在磁盘上的地址空间的高速缓存，主存中保存热的数据，根据需要在磁盘和主存之间传送数据；
• 内存保护：保护每个进程的地址空间不被其他进程破坏。

Part I：虚拟寻址

CPU 通过生成一个虚拟地址（Virtual Address， VA）来访问主存，这个虚拟地址在被送到主存之前需要先转换成适当的物理地址。将一个虚拟地址转换为物理地址的任务叫做地址翻译（address translation）。

这一过程需要 CPU 硬件和操作系统的合作，CPU 芯片上叫做内存管理单元（memory Management Unit， MMU），利用操作系统管理的存放在主存中的查询表（Page Table）来动态的将虚拟地址翻译为物理地址。

Part II：虚拟内存使用主存作为缓存

虚拟内存被组织为一个由存放在磁盘上的 N 个连续的字节（Bytes）大小的单元组成的数组，每字节都有一个唯一的虚拟地址。磁盘上的数组的内容被缓存在主存中，根据需要在磁盘和主存之间传送数据。

通过查看 DRAM 时序，我们发现检索连续字节块的时间比访问单独一个字节的时间要短很多。对于磁盘来说，从一个扇区读取第一个字节的时间开销，要比读这个扇区内的连续字节要慢 100,000 倍。因此虚拟内存想要获取比较高的性能，磁盘（较低层级）上的数据被分割成块，这些块作为磁盘和主存（较高层级）之间的传输单元。

虚拟内存系统通过将将虚拟内存分割为称为虚拟页（Virtual Page， VP）的大小固定的块来处理这个问题。每个虚拟页的大小为 P=2^p 字节（虚拟页一般大小为 4kb ~ 2MB）。类似的，物理内存被分割成物理页（Physical Page， PP），大小为 P 字节（物理页也被称为页帧，page frame）。

任意时刻， 虚拟页面的集合分成 3 个不相交的子集：

• 未分配的：虚拟内存还未分配（或者创建）的页；
• 缓存的：已缓存在 DRAM 内存中的已分配页；
• 未缓存的：未缓存在 DRAM 内存中的已分配页；

上图中包含 8 个虚拟页的虚拟内存系统，VP0、VP3 未分配，VP1、VP4、VP6 分配并缓存在 DRAM 内存中，VP2、VP5、VP7 被分配了，但是没有缓存在 DRAM 内存中。

Part III：页表

每一个进程都有一份页表（Page Table），作为其上下文的一部分。页表由一系列页表条目（PTE，Page Table Entry）组成，每个页表条目都包含着虚拟页和物理页的映射关系。PTE 由一个有效位（valid bit，表明该虚拟页是否被缓存在 DRAM 中）和一个 n 位地址字段组成。

页表（page table）的数据结构存放在物理内存（DRAM）中，操作系统负责维护页表结构，每次 MMU（内存管理单元）中的地址翻译硬件将一个虚拟地址转换成物理地址时，都会读取页表。

MMU 通过页表来确定一个虚拟页是否缓存在 DRAM 中：

• 如果是（有效位为 1），则该条目指向该虚拟页所存放在物理页的位置；
• 如果不是（有效位为 0），则该条目指向该虚拟页所存放在磁盘的位置，在物理内存（DRAM）中选择一个牺牲页，并将虚拟页从磁盘复制到 DRAM 中，替换这个牺牲页。

上图为包含 8个虚拟页，4 个物理页的系统的页表结构。

Part IV：页命中

页命中指的是当 MMU 需要根据虚拟地址输出物理地址时，这个地址所在的页已经被装载到物理内存中了（即对应的 PTE 的有效为 1）。

上图中，当 MMU 访问的虚拟地址对应到页表中 VP 2 时，地址翻译硬件发现该地址在页表当中有效位为 1，即被缓存在 DRAM 当中（称为页命中），则使用页表当中 PTE 所对应的物理内存地址，来访问数据。

Part V：缺页

上图中，当 MMU 访问的虚拟地址对应到页表中 VP 3 时，地址翻译硬件发现该地址在页表当中有效位为 0，即未被缓存在 DRAM 当中，称为缺页（Page Fault），触发一个缺页异常。

缺页异常的处理程序被启动，该程序会选择一个牺牲页，若是该牺牲页被标记为已经更改过，则内核会将其复制回磁盘，若是未更改过，调整牺牲页在页表中所对应的 PTE。接着，内核从磁盘(虚拟内存)当中将内容复制到牺牲页(物理内存)上，再次更新其PTE，随后返回。

当缺页异常处理程序返回时，原进程会重新启动导致缺页异常的指令，该指令会将导致缺页的虚拟地址重发送到地址翻译硬件，这时就会进行页命中的相关流程了。

上图中，触发缺页异常后，缺页异常处理程序选择 VP 4 作为牺牲页，并从磁盘上用 VP 3 的副本取代它。

在缺页异常处理程序重新启动导致缺页的指令之后，该指令将从内存中正常地读取字，而不会再产生缺页异常。

Part VI：分配新页

如上图，内核在磁盘上分配 VP 5，并将 PTE 5 指向这个新的位置。

Part VII：虚拟内存作为内存管理的工具

操作系统为每个进程提供了一个独立的页表，也就是每个进程独占一个独立的虚拟地址空间。

这样做的好处：

• 简化共享内存：操作系统通过将不同进程中适当的虚拟页面映射到相同的物理页面，从而安排多个进程共享下共同代码的副本。
• 简化链接：独立的地址空间允许每个进程的内存布局使用相同的基本格式，而不管代码和数据实际存放在物理内存的何处。链接器可以假设每个程序都加载到相同的位置，然后它可以重定位这些引用。
• 简化加载：execve 查看 ELF 文件，它知道文件中的代码和数据段有多大，它从固定的地址为代码和数据分配虚拟内存。
• 简化内存分配：虚拟内存为向用户进程提供一个简单的分配额外内存的机制。当一个运行在用户进程中的程序要求额外的堆空间时（如调用malloc），操作系统分配一个适当数字（eg：k）个连续的虚拟内存页面，并且将他们映射到物理内存中任意位置的 k 个任意的物理页面。

Part VIII：虚拟内存作为内存保护的工具

虚拟内存通过在 PTE 上添加一些额外的许可位来控制对一个虚拟页面的访问权限，通过虚拟内存可以提供页面级的内存保护。

4、地址翻译

Part I：地址翻译术语

1. 基本参数 符号描述N = 2n 虚拟地址空间中的地址数量 M = 2m 物理地址空间中的地址数量 P = 2p 页的大小（字节）
2. 虚拟地址（VA）的组成部分

3. 物理地址（PA）的组成部分

Part II：使用页表的地址翻译

在 CPU 中地址翻译由一个叫做 MMU（Memory Management Unit，内存管理单元）的硬件完成。MMU 接收一个虚拟地址，并且输出一个物理地址。如果这个虚拟地址在物理内存中存在，那么就叫做页命中。如果这个虚拟地址在物理内存中不存在，那么 MMU 将产生一个缺页错误。

n 位的虚拟地址包括两个部分：一个 p 位的虚拟页面偏移（Virtual Page Offset，VPO），和一个 n-p 位的虚拟页号（Virtual Page Number， VPN），MMU 利用 VPN 来选择适当的 PTE。

因为物理和虚拟页面都是 P 字节的，所以物理页面偏移（Physical Page Offset，PPO）和 虚拟页面偏移（Virtual Page Offset，VPO）是相同的，因此将 PTE 中的物理页号（Physical Page Number， PPN）与 VPO 串联起来，就得到了相应的物理地址。

1. 页命中时地址翻译

1. 处理器生成一个虚拟地址，并把它传送给 MMU。
2. MMU 生成根据虚拟地址生成 VPN，然后请求高速缓存/主存，获取 PTE 的数据。
3. 高速缓存/主存向 MMU 返回 PTE 的数据。
4. 从 PTE 获取对应的物理页号 PPN。用物理页的基址加上页偏移 PPO（假设页大小为 4KB，那么页偏移就是虚拟地址的低 12 位，物理页的页偏移和虚拟页的页偏移相同），获取对应的物理地址。
5. 主存/高速缓存将数据返回给 CPU。

2.缺页时的地址翻译

1. 处理器生成一个虚拟地址，并把它传送给 MMU。
2. MMU 根据虚拟地址生成 VPN，然后请求高速缓存/主存，获取 PTE 的数据。
3. 高速缓存/主存向 MMU 返回 PTE 的数据。
4. 由于判断出 PTE 的有效位是 0，所以 CPU 将触发一次异常，将控制权转移给内核中的缺页异常处理程序。
5. 缺页异常处理程序确定出物理内存中的牺牲页，如果这个页面被修改过了（D 标志位为 1），那么将牺牲页换出到磁盘。
6. 缺页处理程序从磁盘中调入新的页面到主存中，并且更新 PTE。
7. 缺页处理程序将控制权返回给原来的进程，再次执行导致缺页的指令。再次执行后，就会产生页命中时的情况了。

Part III：地址翻译加速

1.将 Cache 与虚拟内存整合在一起

• VA：虚拟地址
• PA：物理地址
• PTE：页表条目
• PTEA：页表条目地址

从页命中的流程图中可以看出，CPU 每次需要请求一个虚拟地址，MMU 就需要从内存/Cache 中获取 PTE ，然后再根据 PTE 的内容去从物理内存中加载数据。如果在 PTE 在 Cache 中未命中，就需要从内存中获取 PTE。这部分由于 Cache Miss 造成的开销是巨大的。

如果我们将 PTE 存储到一个专门的 L1 Cache 中那么将会减少这部分开销，这个专门存放 PTE 的 L1 Cache 就是 TLB（Translation Lookaside Buffer，翻译后备缓冲器）。

2.利用 TLB 加速地址翻译

许多 MMU 包含一个名叫 TLB（Translation Lookaside Buffer，翻译后备缓冲器） 的 Cache。

TLB 将虚拟内存的 VPN 视为由组索引和行匹配组成，索引部分（TLBI）用来定位 TLB 中的缓存数据项，标记部分（TLBT）用来校验存储的数据项是否为指定的 VPN 对应的数据。

如果 TLB 命中了，那么所有的地址翻译步骤都是在 MMU 中执行的，所以非常快。

1. TLB命中

1. CPU 生成 1 个虚拟地址； 2. MMU 向 TLB 请求 PTE； 3. TLB 返回 PTE 到 MMU； 4. MMU 将这个虚拟地址翻译成一个物理地址，并且把它发送到高速缓存/主存； 5. 高速缓存将所请求的数据字返回给 CPU；

b.TLB未命中

1. CPU 生成 1 个虚拟地址；
2. MMU 向 TLB 请求 PTE，TLB 未命中；
3. MMU 从高速缓存/内存中获取相应的 PTE；
4. MMU 将新取出来的 PTE 放在 TLB 中；
5. MMU 将通过 PTE 这个虚拟地址翻译成一个物理地址，并且把它发送到高速缓存/主存；
6. 高速缓存将所请求的数据字返回给 CPU；

理解 TLB 需要注意的是，因为不同进程的页表内容是不同的，因此在进程上下文切换时，会重置 TLB。

Part IV：多级页表

PTE 的数量由虚拟地址空间的大小和页大小决定。也就是：X=N/P。那如果我们有一个 32 位的物理地址空间、4KB 的页面和 一个 4 字节的 PTE。

即使程序只使用了一小部分虚拟地址空间，也总是需要一个 4MB（ 4 X 232 / 212 ）的页表常驻主存。对于 64 位的系统来说，情况将变得更加复杂。因此使用层次结构的页表来压缩页表。

1. 二级页表

上图展示了一个两级页表的层次结构。二级页表中的每个 PTE 项都负责一个 4KB 页面，而一级页表中的每个 PTE 负责 1024 个二级页表项。

• 只有一级页表才需要存放在主存/TLB，虚拟内存系统可以在需要时创建、调入或调出二级页表；且常用的二级页表才需要缓存在主存/TLB。
• 如果一个一级页表是空的，那么二级页表也不会存在。这是一个很大的节约，因为一个典型程序 4G 的虚拟地址空间的大部分都是未分配的。

如果页表层级太多，则增加缓存未命中的概率，一般层级是4。

2. K级页表

上图展示的是一个 K 级层次页表的结构图，起始就是将 VPN 部分划分为多个段，每个段都代表某一级页表。而每一级中的 PTE 的 Base addr 为下一级提供入口地址，最后一级的 Base addr 则表示最终物理地址的 PPN。

5、虚拟内存系统示例

本节里，我们通过一个具体的端到端的地址翻译示例来学习虚拟内存系统。

我们假设：

• 内存是按字节寻址的。
• 内存访问是针对 1 字节的字的（不是 4 字节的字）。
• 虚拟地址是 14 位长的（n = 14）。
• 物理地址是 12 位长的（m = 12）。
• 页面大小是 64 字节（P = 64）。
• TLB 是四路组相联的，总共有 16 个条目。
• L1 d-cache 是物理寻址、直接映射的，行大小为 4 字节，而总共有 16 个组。

上图展示了虚拟地址和物理地址的格式。因为每个页面是 26= 64 字节，所以虚拟地址和物理地址的低 6 位分别作为 VPO 和 PPO。虚拟地址的高 8 位作为 VPN，物理地址的高 6 位作为 PPN。

TLB 是利用 VPN 的位进行虚拟寻址的。因为 TLB 有 4 个组，所以 VPN 的低 2 位就作为组索引（TLBI）。VPN 中剩下的高 6 位作为标记（TLBT），用来区别可能映射到同一个 TLB 组的不同的 VPN。

这个页表是一个单级设计，一共有28= 256 个页表条目（PTE）。然而，我们只对这些条目中的开头 16 个感兴趣。为了方便，我们用索引它的 VPN 来标识每个 PTE；但是要记住这些 VPN 并不是页表的一部分，也不储存在内存中。

另外，注意每个无效 PTE 的 PPN 都用一个“-”来表示，以加强一个概念：无论刚好这里存储的是什么位值，都是没有任何意义的。

直接映射的 L1 Cache 是通过物理地址中的字段来寻址的。因为每个块都是 4 字节，所以物理地址的低 2 位作为块偏移（CO）。因为有 16 组，所以接下来的 4 位就用来表示组索引（CI），剩下的 6 位作为标记（CT）。

• Part I：TLB命中示例

过程如上图所示，给定了这种初始化设定，让我们来看看当 CPU 执行一条读地址 0x0369 处字节的加载指令时会发生什么（假定 CPU 读取 1 字节的字，而不是 4 字节的字）。

开始时，MMU 从虚拟地址中抽取出 VPN（0x0D），并且检查 TLB，看它是否因为前面的某个内存引用缓存了 PTE 0x0D 的一个副本。TLB 从 VPN 中抽取出 TLBI（TLB 索引 0x01）和 TLBT（TLB 标记 0x3），Set 0x1 的 Tag 03 条目中有效匹配，所以命中，然后将缓存的 PPN（0x2D）返回给 MMU。

现在，MMU 有了形成物理地址所需要的所有东西。它通过将来自 PTE 的 PPN（0x2D）和来自虚拟地址的 VPO（0x29）连接起来，这就形成了物理地址（0xB69）。

接下来，MMU 发送物理地址给 L1 d-cache 缓存，L1 d-cache 从物理地址中抽取出缓存偏移 CO（0x1）、缓存组索引 CI（0xA）以及缓存标记 CT（0x2D）。

因为 L1 d-cache 的组 0xA 与缓存组索引 CI（0xA）匹配，Set 0xA 的 Tag 2D 与 缓存标记 CT（0x2D）相匹配，所以缓存检测到一个命中，读出在偏移量 CO（0x1）处的数据字节（0x15），并将它返回给 MMU，随后 MMU 将它传递回 CPU。

（正文完）

end

Reference：

• MIT 6.004 Computation Structures
• Computer Systems: A Programmer’s Perspective, 3/E (CS:APP3e)
• CMU 15-213 Introduction to Computer Systems