🌰Senjl's Digital Garden🐉

Recent writing

33-Virtual-Memory

9分钟阅读

为什么需要虚拟内存？

  • 虚拟地址（逻辑地址）：程序员编程使用的地址
  • 物理地址（实地址）：物理存储器的地址

虚拟内存解决的问题及思路

  1. 如果程序的工作集大小大于物理内存大小，程序还能执行吗？

    • 缓存的思想（虚拟化）

  2. 如果多个程序共享使用，那么

    • 程序员在编程时，怎么知道在哪儿分配内存？
    • 多个程序需要共享时，怎么办？
    • 多个程序同时执行时，某进程（程序）不想让另一个进程看到或者修改本进程的内容，怎么办？
    • 思想：程序员编程使用的空间与程序运行空间相互独立

  1. 独立的逻辑地址空间: 通过页表将虚地址转换为实地址

  2. 每个进程有独立的逻辑地址空间，建立逻辑地址和物理地址的转换机制

  3. 页表中存放有访问权限：通过硬件来保证权限（操作系统的“陷阱”操作）

虚拟存储器的目的

  • 容量
    • 获得运行比物理存储器更大空间程序的能力
  • 存储管理
    • 内存的分配以及虚实地址转换
  • 保护
    • 操作系统可以对虚拟存储空间进行特定的保护
  • 灵活
    • 程序的某部分可以装入主存的任意位置
  • 提高存储效率
    • 只在主存储器中保留最重要的部分
  • 提高并行度
    • 在进行段页替换的同时可以执行其它进程
  • 可扩展
    • 为对象提供了扩展空间的能力.

虚拟内存与高速缓存的比较

页式内存管理

  • 将主存和虚存划分为固定大小的页
  • 以页为单位进行管理和数据交换
  • 虚地址=虚页号+页内地址偏移
  • 实地址=实页框号+页内地址偏移
  • 通过页表进行管理
    • 页表基地址寄存器 PTBR
    • 实页号
    • 控制位

  • 控制位：包括修改位、替换位
  • 有效位：表示该页是否已装入主存

页式虚拟存储器的访问过程

  1. 得到程序给出的虚地址；
  2. 由虚地址得到虚页号；
  3. 访问页表，得到对应的实页号；
  4. 若该页已在内存中，则根据实页号得到实地址，访问内存；
  5. 否则，启动输入输出系统，读出对应页装入主存，再进行访问。

为了加快找页表、找页的多次访存时间，引入 TLB。

页表大小

  • 与虚页数直接相关，但是
    • 虽然理论上每个进程的逻辑空间很大，但其实大部分应该是不活跃的
    • 实际调入到内存的内容不可能超过物理存储空间
  • 如何减少页表本身所占的空间？而且还要实现简单（页表访问频繁）
    • 两种途径
      • 层次页表（hierarchical page table）
      • 反转页表（inverted page table

TLB

TLB 缺失将造成：

  • 流水线停止
  • 通知操作系统
  • 读页表
  • 将页表项写入 TLB
  • 返回到用户程序
  • 重新访问

因此，应尽量减少缺失:

  • 多路组相连
  • 再尽量提高 TLB 的容量

页面大小

减少内部碎片

  • 缩小页面大小可以减少内部碎片
  • 但是：需要更大的页表

趋势：增大页面大小

  • RAM 价格下降，内存储器容量增大
  • 内存和外存性能差距增大
  • 程序员需要更大的地址空间

目前：页面大小为4K 左右

  • 但也并非不可以（1MB, 2MB, 4MB, 1GB)
  • Linux 内核的 Huge Page 机制

页面替换算法

  • 最近最少使用（LRU）
    • 将页帧按照最近最多使用到最近最少使用进行排序，再次访问一个页帧时，将该页帧移到表头，替换时将表尾的页帧换出。
    • 改进：替换出其中一个“干净”的页帧。

例子：RISC-V 页表管理

基于页面的虚拟内存

  • 分页命名模式：SvX，其中 X 是以位为单位的虚拟地址长度
  • 内存划分为固定大小的页面进行地址转换和对内存内容的保护（页面大小通常为 4KB，也有大页面粒度）
  • 启用分页的时候，大多数地址（包括 load 和 store 的有效地址和 PC 中的地址）都是虚拟地址
  • 要访问物理内存，虚拟地址必须被转换为真正的物理地址
  • 通过页表的结构来进行转换
  • 权限位指示那些权限模式和通过哪种类型的访问可以操作这个页
  • 访问未被映射的页或者访问权限不足会导致页面错误异常 （page fault exception）

SV32

基于分页的虚拟内存

S 模式提供了一种传统的虚拟内存系统，它将内存划分为固定大小的页来进行地址转换和对内存内容的保护。启用分页的时候，大多数地址（包括 load 和 store 的有效地址和 PC 中的地址）都是虚拟地址。要访问物理内存，它们必须被转换为真正的物理地址，这通过遍历一种称为页表的 radix-tree 实现。页表中的叶节点指示虚地址是否已经被映射到了真正的物理页面，如果是，则指示了哪些权限模式和通过哪种类型的访问可以操作这个页。访问未被映射的页或访问权限不足会导致页错误异常（page fault exception）。

SV32

RISC-V 的分页方案以 SvX 的模式命名,其中 X 是以位为单位的虚拟地址的长度。RV32 的分页方案 Sv32 支持 4GiB 的虚址空间，这些空间被划分为 2^10 个 4 MiB 大小的巨页。每个巨页被进一步划分为 2^10个 4 KiB 大小的基页（分页的基本单位）。因此，Sv32 的页表是基数为 2^10的两级树结构。页表中每个项的大小是四个字节，因此页表本身的大小是 4 KiB。页表的大小和每个页的大小完全相同，这样的设计简化了操作系统的内存分配。

图 10.10 显示了 Sv32 页表项（page-table entry，PTE）的布局，从右到左分别包含如下所述的域：

  • V 位决定了该页表项的其余部分是否有效（V = 1 时有效）。若 V = 0，则任何遍历到此页表项的虚址转换操作都会导致页错误。
  • R、W 和 X 位分别表示此页是否可以读取、写入和执行。如果这三个位都是 0，那么这个页表项是指向下一级页表的指针，否则它是页表树的一个叶节点。
  • U 位表示该页是否是用户页面。若 U = 0，则 U 模式不能访问此页面，但 S 模式可以。若 U = 1，则 U 模式下能访问这个页面，而 S 模式不能。

这里说的很不准确。请参考原版文档： If the SUM bit in the sstatus register is set, supervisor mode software may also access pages with U=1. However, supervisor code normally operates with the SUM bit clear, in which case, supervisor code will fault on accesses to user-mode pages.

  • G 位表示这个映射是否对所有虚址空间有效，硬件可以用这个信息来提高地址转换的性能。这一位通常只用于属于操作系统的页面。
  • A 位表示自从上次 A 位被清除以来，该页面是否被访问过。
  • D 位表示自从上次清除 D 位以来页面是否被弄脏（例如被写入）。
  • RSW 域留给操作系统使用，它会被硬件忽略。
  • PPN 域包含物理页号，这是物理地址的一部分。若这个页表项是一个叶节点，那么 PPN 是转换后物理地址的一部分。否则 PPN 给出下一节页表的地址。（图 10.10 将 PPN 划分为两个子域，以简化地址转换算法的描述。）

[! note] OS 的页面置换 操作系统依赖于A位和 D 位来决定将哪些页面交换到辅存。定期清除 A 位有助于 OS 判断哪些页面是最近最少使用的。置上 D 位表示换出该页面的成本更高，因为它必须写回辅存。

SV39

RV64 支持多种分页方案，但我们只介绍最受欢迎的一种，Sv39。Sv39 使用和 Sv32 相同的 4 KiB 大的基页。页表项的大小变成 8 个字节，所以它们可以容纳更大的物理地址。为了保证页表大小和页面大小一致，树的基数相应地降到 2^9，树也变为三层。Sv39 的 512 GiB 地址空间划分为 2^9个 1 GiB 大小的吉页。每个吉页被进一步划分为 2^9 个巨页。在 Sv39 中这些巨页大小为 2 MiB，比 Sv32 中略小。每个巨页再进一步分为 2^9个 4 KiB 大小 的基页。

图 10.11 显示了 Sv39 页表项的布局。它和 Sv32 完全相同，只是 PPN 字段被扩展到了 44 位，以支持 56 位的物理地址，或者说 2^26 GiB 大小的物理地址空间。

[! note] 未被使用的地址位 由于 Sv39 的虚拟地址比 RV64 整数寄存器要短，可能你想知道剩下的 35 位是什么。Sv39 要求地址位 63-39 是第 38 位的副本。因此有效的虚拟地址是 0000_0000_0000_0000hex0000_003f_ffff_ffffhex 和 ffff_ffc0_0000_0000hex-ffff_ffff_ffff_ffffhex。

这两个区间之间间隔的大小是两个区间长度大小的 2^25 倍，看上去似乎浪费了 64 位寄存器可以表达范围的 99.999997%。为什么不充分地利用这额外的 25 位空间呢？答案是，随着程序的增长，它们可能会需要大于 512 GiB 的虚址空间。而架构师希望在不破坏向后兼容性的前提下增加地址空间。如果我们允许程序在高 25 位中存储额外的数据，那么以后就不可能把这些位回收从而存储更大的地址。像这样允许在未使用的地址位中存储数据的严重错误，在计算机的历史中已经重复出现了多次。

SATP: 控制分页

一个叫 satp（Supervisor Address Translation and Protection，监管者地址转换和保护）的 S 模式控制状态寄存器控制了分页系统。

如图 10.12 所示，satp 有三个域。

  • MODE 域可以开启分页并选择页表级数，图 10.13 展示了它的编码。
  • ASID（Address Space Identifier， 地址空间标识符）域是可选的，它可以用来降低上下文切换的开销。
  • 最后，PPN 字段保存了根页表的物理地址，它以 4 KiB 的页面大小为单位。

通常 M 模式的程序在第一次进入 S 模式之前会把零写入 satp 以禁用分页，然后 S 模式的程序在初始化页表以后会再次进行 satp 寄存器的写操作。

虚拟地址到物理地址的转换

当在 satp 寄存器中启用了分页时，S 模式和 U 模式中的虚拟地址会以从根部遍历页表的方式转换为物理地址。

图 10.14 描述了这个过程：

  1. satp.PPN 给出了一级页表的基址，VA[31:22] 给出了一级页号，因此处理器会读取位于地址(satp.PPN × 4096 + VA[31: 22] × 4)的页表项。
  2. 该 PTE 包含二级页表的基址，VA[21:12] 给出了二级页号，因此处理器读取位于地址(PTE.PPN × 4096 + VA[21: 12] × 4)的叶节点页表项。
  3. 叶节点页表项的 PPN 字段和页内偏移（原始虚址的最低 12 个有效位）组成了最终结果：物理地址就是 (LeafPTE.PPN × 4096 + VA[11: 0])

随后处理器会进行物理内存的访问。Sv39 的转换过程几乎和 Sv32 相同，区别在于其具有较大的 PTE 和更多级页表。本章末尾的图 10.19 给出了页表遍历算法的完整描述，详细说明了异常条件和超页面转换的特殊情况。

除了一点以外，我们几乎讲完了 RISC-V 分页系统的所有内容。如果所有取指，load 和 store 操作都导致多次页表访问，那么分页会大大地降低性能！所有现代的处理器都用地址转换缓存（通常称为 TLB，全称为 Translation Lookaside Buffer）来减少这种开销。为了降低这个缓存本身的开销，大多数处理器不会让它时刻与页表保持一致。这意味着如果操作系统修改了页表，那么这个缓存会变得陈旧而不可用。S 模式添加了另一条指令来解决这个问题。这条 sfence.vma 会通知处理器，软件可能已经修改了页表，于是处理器可以相应地刷新转换缓存。它需要两个可选的参数，这样可以缩小缓存刷新的范围。

  • 一个位于 rs1，它指示了页表哪个虚址对应的转换被修改了；
  • 另一个位于 rs2，它给出了被修改页表的进程的地址空间标识符（ASID）。

如果两者都是 x0，便会刷新整个转换缓存。

[! note] sfence.vma 的作用就是刷新TLB The SFENCE.VMA is used to flush any local hardware caches related to address translation.

It is specified as a fence rather than a TLB flush to provide cleaner semantics with respect to which instructions are affected by the flush operation and to support a wider variety of dynamic caching structures and memory-management schemes.

SFENCE.VMA is also used by higher privilege levels to synchronize page table writes and the address translation hardware.

多处理器中的地址转换缓存一致性

sfence.vma 仅影响执行当前指令的 hart 的地址转换硬件。当 hart 更改了另一个 hart 正在使用的页表时，前一个 hart 必须用处理器间中断来通知后一个 hart，他应该执行 sfence.vma 指令。这个过程通常被称为 TLB shootdown。

虚拟地址到物理地址的转换算法

A virtual address va is translated into a physical address pa as follows:

  1. Let a be satp.ppn × PAGESIZE, and let i = LEVELS − 1. (For Sv32, PAGESIZE= and LEVELS=2.) The satp register must be active, i.e., the effective privilege mode must be S-mode or U-mode.
  2. Let pte be the value of the PTE at address a+va.vpn[i]×PTESIZE. (For Sv32, PTESIZE=4.) If accessing pte violates a PMA or PMP check, raise an access-fault exception corresponding to the original access type.
  3. If pte.v = 0, or if pte.r = 0 and pte.w = 1, or if any bits or encodings that are reserved for future standard use are set within pte, stop and raise a page-fault exception corresponding to the original access type.
  4. Otherwise, the PTE is valid. If pte.r = 1 or pte.x = 1, go to step 5. Otherwise, this PTE is a pointer to the next level of the page table. Let i = i − 1. If i < 0, stop and raise a page-fault exception corresponding to the original access type. Otherwise, let a = pte.ppn × PAGESIZE and go to step 2.
  5. A leaf PTE has been found. Determine if the requested memory access is allowed by the pte.r, pte.w, pte.x, and pte.u bits, given the current privilege mode and the value of the SUM and MXR fields of the mstatus register. If not, stop and raise a page-fault exception corresponding to the original access type.
  6. If i > 0 and pte.ppn[i − 1 : 0] != 0, this is a misaligned superpage; stop and raise a page-fault exception corresponding to the original access type.
  7. If pte.a = 0, or if the original memory access is a store and pte.d = 0, either raise a page-fault exception corresponding to the original access type, or:
    • If a store to pte would violate a PMA or PMP check, raise an access-fault exception corresponding to the original access type
    • Perform the following steps atomically:
      • Compare pte to the value of the PTE at address a + va.vpn[i] × PTESIZE.
      • If the values match, set pte.a to 1 and, if the original memory access is a store, also set pte.d to 1.
      • If the comparison fails, return to step 2
  8. The translation is successful. The translated physical address is given as follows:
    • pa.pgoff = va.pgoff.
    • If i > 0, then this is a superpage translation and pa.ppn[i − 1 : 0] = va.vpn[i − 1 : 0].
    • pa.ppn[LEVELS − 1 : i] = pte.ppn[LEVELS − 1 : i].

All implicit accesses to the address-translation data structures in this algorithm are performed using width PTESIZE.

指向原始笔记的链接

段式内存管理与段页式内存管理

段式存储管理

设置段表进行管理

  • 段表基地址
  • 段起始地址 (段表中表项的位置)
  • 段长
  • 装入位
  • 保护、共享等标志

特点

  • 段的分界与程序和数据的自然分界相对应
  • 易于编译、管理、修改和保护，便于多道程序共享
  • 段长动态可变
  • 段起点、终点不定：由段上界寄存器解决
  • 空间分配困难，容易产生碎片（外碎片）

段页式虚拟存储管理

段页式虚拟存储管理是段式虚拟存储器和页式虚拟存储器的综合。

  • 它先把程序按逻辑单位分为段，再把每段分成固定大小的页。
  • 操作系统对主存的调入调出是按页面进行的，但它又可以按段实现共享和保护，可以兼取页式和段式系统的优点。
  • 其缺点是需要在地址映射过程中多次查表。
  • 其地址映射通过一个段表和一组页表来进行。

例子：x86 虚存管理

模式分类

  • 不分段也不分页模式：

    • 在这种模式下，虚拟存储的地址空间 和物理存储空间大小相同，可以用在复杂度较低但对性能有较 高要求的场合。

  • 页式管理模式：

    • 这种模式将主存分成固定长度的页，通过页 进行存储保护和管理。

  • 段式管理模式：

    • 段式管理模式按程序本身的逻辑段来划分主 存空间，与页式管理相比，段的长度可变

  • 段页式管理模式：

    • 为了兼容旧的模式，在 x86 中段式内存管理 和页式内存管理都是支持的。
    • 程序地址首先经过段式内存转换， 再通过页式内存转换，最终转换为物理地址

32 位 x86 虚实地址转换

  • 虚地址（逻辑地址）：
    • 程序员给出的虚拟地址，格式为段号+段内偏移（16 位 +32 位），每段大小不超过 4GB，一共不超过 2^14 段。（段号中有两位用来表示段优先级）
  • 实地址：32 位的实际内存地址

关系图谱

反向链接