虚拟存储器

虚拟存储器

虚拟存储器是一种计算机内存管理技术，它在物理内存和磁盘存储之间创建了一个抽象的、扩展的内存空间，以提供更大的可用内存容量。

物理内存

物理内存（Physical Memory）指的是计算机系统中的实际硬件内存，即随机存取存储器（RAM）。 物理内存是计算机直接用于存储和操作数据的地方，所有进程的数据和代码实际上都是存储在物理内存上。

虚拟内存

虚拟内存（Virtual Memory）是一种计算机系统内存管理技术，它使得进程可以认为自己拥有一个连续且独立的内存空间， 即使实际上物理内存可能不够用或者是分散的。

进程使用虚拟地址来访问内存中的数据和指令，而不需要了解物理内存的详细情况。 进程使用虚拟地址去访问虚拟内存， 当进程访问虚拟内存时，操作系统会将虚拟地址转化为物理地址， 进而根据物理地址去访问物理内存。

页式虚拟存储器

将虚拟地址空间和物理地址空间都划分为固定大小的块，称为“页”（Page）。 程序运行时，操作系统只将部分页面加载到物理内存中，其余页面保存在硬盘上。 当程序访问不在物理内存中的页面时，会发生缺页中断，操作系统负责将所需的页面从硬盘加载到物理内存，并替换掉暂时不用的页面。

页面划分和地址结构

在页式虚拟存储器中，虚拟内存空间被划分为一个个虚拟页面（VP，Virtual Page），物理内存空间被划分为一个个物理页面（PP，Physical Page）。

虚拟地址（VA, Virutal Address）被划分为 虚拟页面号（VPN，Virutal Page Number）和 页内偏移（Offset）这两个字段。

在使用虚拟地址去访问虚拟内存时，我们可以根据虚拟页面号找到该地址所在的虚拟页面，在找到虚拟页面后，我们可以根据页内偏移找到该地址在虚拟页面内的偏移大小。

同理， 物理地址（PA, Physical Address）被划分为 物理页面号（PPN，Physical Page Number）和 页内偏移（Offset）这两个字段。

在使用物理地址去访问虚拟内存时，我们可以根据物理页面号找到该地址所在的物理页面，在找到物理页面后，我们可以根据页内偏移找到该地址在物理页面内的偏移大小。

地址翻译机构

CPU 中的内存管理单元（Memory Management Unit，MMU）是计算机体系结构的重要组成部分，它负责虚拟内存到物理内存的地址映射和内存访问的控制。MMU 的主要功能包括：

• 地址转换：MMU 负责将程序使用的虚拟地址转换为对应的物理地址。
• 地址保护：MMU 实施内存保护策略，以确保不同的程序或进程无法越界访问彼此的内存空间。
• 内存访问权限：MMU 根据地址映射和保护位（在页表或段表中定义）来控制内存访问权限，包括读、写、执行等。

页表

页表（page table）是操作系统维护的一张表，用于将虚拟地址转化为物理地址，每个运行的进程都有自己页表。 进程的页表存储在其内存空间中的内核空间中， 详见进程内存空间。 在进程执行时，MMU 使用当前活动进程的页表来执行地址转换。

单级页表

页表的功能是将 虚拟页号 转换为 物理页号，进而实现地址翻译。 对于单级页表而言，只需访问一次页表即可实现 页面号 的翻译过程。

单级页表结构

一个典型的单级页表结构如下图所示：

页表中的每一行叫做页表项（PTE, page table entry），页表项可包含如下内容：

• 虚拟页框号（VPN，Virtual Page Number）：对于单级页表而言，VPN 并不需要实际存储在页表的字段中，其隐性地作为页表项的下标进行存储。
• 物理页框号（PPN，Physical Page Number）：当前 VPN 所对应的物理页号。
• 有效位（Valid Bit）：有效位用于指示虚拟页是否有效。如果有效位为 1，表示虚拟页是有效的，可以用于地址转换。如果有效位为 0，表示虚拟页无效，访问它会导致错误。
• 修改位（Dirty Bit）：修改位用于指示虚拟页的内容是否已被修改。如果修改位为 1，表示虚拟页的内容已被更改，可能需要写回到磁盘或其他非易失性存储介质。
• 访问位（Accessed Bit）：访问位用于指示虚拟页是否已被访问。如果访问位为 1，表示虚拟页已被访问。这对于操作系统的页面置换算法很有用。
• 保护位（Protection Bits）：保护位用于指定虚拟页的访问权限，例如读取、写入或执行权限。这有助于操作系统实施内存保护策略。
• 缓存位（Caching Bits）：缓存位用于指示是否允许将虚拟页的内容缓存在高速缓存中。这有助于控制内存访问的性能。

单级页表地址翻译

虚拟地址和物理地址的格式

• 虚拟地址（Virutal Address）分为两个部分：
  • 虚拟页框号（VPN, Virtual Page Number）：当前地址所在的页框在虚拟内存对应的所有页框中的下标
  • 页内偏移（VPO, Virutal Page Offset）：地址在页面内的偏移
• 物理地址（Physical Address）同样分为两个部分：
  • 物理页框号（PPN, Physical Page Number）：当前地址所在的页框在物理内存对应的所有页框中的下标
  • 页内偏移（PPO, Physical Page Offset）：地址在页面内的偏移

其中 VPO = PPO = offset，页面大小 = $2^{\text{offset}}$

虚拟页面个数 = $2^{\text{VPN}}$，物理页面个数 = $2^{\text{PPN}}$

地址翻译过程

PPO 和 VPO 的内容一致，所以地址翻译主要在于通过将 VPN 转化为 PPN，VPN 的值为对应的页表项（PTE）在页表中下标，在找到对应的页表项后，判断 Valid 字段是否为 1：

• 如果为 0 的话，会发生 缺页中断
• 如果为 1 的话，读取其中的 PPN，完成地址翻译

举一个实际 例子 说明一下：

假设虚拟内存为 16MB，物理内存为 1MB，页面大小为 4KB，则翻译虚拟地址0x321654

• VPO 和 PPO 的位数为 12（$4\text{ KB} = 2^{12}\text{B}$），地址对应的 page offset 为0x654
• 虚拟地址的总位数为 24（$16\text{ MB} = 2^{24}\text{B}$）
• 物理地址的总位数为 20（$1\text{ MB} = 2^{20}\text{B}$）
• VPN 的位数为 24 - 12 = 12，虚拟地址对应的 VPN 为0x321
• PPN 的位数为 20 - 12 = 8，
• 虚拟地址格式为 | VPN (12bits) | VPO (12bits) |
• 物理地址格式为 | PPN ( 8bits) | PPO (12bits) |
• VPN 为0x321，找到页表的第0x321个页表项，判断其中的 valid 字段是否为 1，如果为 0，则调用缺页中断，如果为 1，则找到其中的 PPN，并使用 PPN 和 PPO 组成物理地址。

多级页表

单级页表会有什么问题？

在单级页表中，为了管理大型虚拟地址空间，需要创建庞大的页表，其中包含了大量的页表项，这会导致页表本身需要占用大量的内存空间。

假如我们有一个 32 位 4GB 的虚拟地址空间、4KB 的页面和一个 4 字节的 PTE，那么我们将需要一个 4MB 的页面表始终驻留在内存中，即使应用程序只引用虚拟地址空间的一小块。

多级页表结构

在多级页表中，虚拟页号 VPN 被分割为多个字段，假设被分割为 k 个字段的话，第 k 个字段对应的页表中的查询内容为 PPN，前 k-1 个字段对应的页表中的查询内容为下一级页表的位置。

如果当前多级页表对应的一级页表有 $m^k$ 个 PTE，将 VPN 分割为 k 个长度相同的子字段后，每个子字段对应的页表的 PTE 个数为$log_k{m^k} = m$。

其中，第一层有 $m$ 个页表，第二层最多有 $m^2$ 个页表在内存中存在， $\cdots$ ，第 k 层最多有 $m^k$ 个页表在内存中存在。

多级页表是如何节省内存的？

只有一级页表需要始终在主存中，对于其他层次的页表，可以按需分配，如果使用到的，就在内存中创建对应的页表结构，如果没使用到，就不需要为其分配内存。 这代表了巨大的潜在节省，因为典型程序的 4GB 虚拟地址空间中的大部分都是未分配的。

对于 k 级页表而言，前 k-1 级页表中 PTE 存储的关键字段都是下一级页表的位置，如果其中某个 PTE 的有效位为 0 的话， 那么操作系统无需为该页表项对应的下一级页表分配内存空间。

TLB

TLB（Translation Lookaside Buffer）是 CPU 内存管理单元（MMU）中的一种高速缓存，用于加速 虚拟地址（VA）到 物理地址（PA）的地址转换过程。 TLB 存储了最近用过的虚拟地址到物理地址的映射，以减少每次内存访问时的地址翻译延迟。

由于页表存储在内存中，所以每一次通过页表的地址翻译过程都至少需要一次访存，开销还是比较大的。 所以为了降低这个开销，TLB 就应运而生，与 Cache 类似，你可以从概念上将 TLB 理解成一个硬件结构，与 Cache 类似，因为离 CPU 更近，所以其访问速度感更快。

存储结构

TLB 是一个硬件结构，但从逻辑上可以将其理解为一张表。

与 cache 存储结构 类似， TLB 由许多表项（TLB Entry）构成，每一个表项包含多个字段，其中 tag 和 PPN 是必须的，其他字段是可选的。

TLB 和 cache 对比

TLB 和页表的关系类似于 cache 与主存的关系，TLB 和 cache 都是一个硬件结构，不过两者发挥作用的场合不同。TLB 和 Cache 的区别如下表所示：

TLB 中也包含三种映射方式：直接映射、全相联映射、组相联映射。

在访问 TLB 时，虚拟地址中虚拟页号（VPN）被按照映射方式进行不同的切分。在访问 cache 时，物理地址中的主存块号被按照映射方式进行不同的切分。

两者的对比如下所示：

在直接映射中，通过 TLB 行号去对应行的表项进行查询。

在组相联映射中，通过 TLB 组号去对应组进行查询（遍历组中的所有 TLB 表项）。

在全相联映射中，遍历 TLB 中的所有表项。

地址结构

当我们在通过 TLB 进行 虚拟页号（VPN）→ 物理页号（PPN）的翻译时，访问 TLB 需要使用到 VPN。 从逻辑上而言，VPN 可以被分为 标记 和 匹配字段这两个部分：

• 标记（TLBT, 即 TLB Tag）：与 TLB 中的 tag 进行对比，判断是否命中 TLB 表项。
• 匹配字段（Match Field），通过该字段判断 VPN 可能被哪些 TLB 表项所缓存，这里 TLB 与 Cache 类似，同样具有三种映射方式，每一种映射方式匹配字段会具有不同的位数。
  • 直接映射：匹配字段为 TLB 表项编号，即行编号（TLB entry index），其位数为 $log_2{(\text{\small TLB 行数})}$
  • 全相联映射：没有匹配字段，即匹配字段位数为 0，因为每一个 VPN 都可能被任何一个 TLB 行所缓存
  • 组相联映射：匹配字段为组号（TLB group index），位数为 $log_2{(\text{\small TLB 组数})}$

使用 TLB 进行地址翻译的过程如下：

• 给定一个 虚拟地址（VA），从中提取出 虚拟页号（VPN）
• 根据映射方式从 VPN 中提取出 标记（TLBT）和 匹配字段
• 根据匹配字段从 TLB 的相应表项中依次查找，命中时应满足如下条件：
  • 有效位（valid）为 1
  • 该表项中的 TLBT 与 VPN 中的 tag 字段相同
• 如果命中某个表项，则通过 TLB 完成 VPN → PPN 的翻译
• 如果没有命中，则通过页表完成翻译

请求页式管理

请求页式管理（Demand Paging）是一种计算机操作系统中的内存管理技术，它允许进程在需要时才将页面（或者说虚拟内存中的数据块）加载到物理内存中，而不是一次性将整个进程加载到内存中。这个概念的核心思想是，将物理内存划分成固定大小的页框（page frame），并将虚拟内存划分成相应大小的页面（page）。

页面错误

当进程尝试访问一个虚拟页面，但该页面当前未加载到物理内存中时，会触发页面错误（page fault）。此时，操作系统会将相应的页面从磁盘加载到物理内存，进行页面替换。

页面替换

页面替换时包含两种情况：

1. 内存中存在空闲页面（未被任何进程使用的页面）。
2. 进程中不存在任何空间页面，即所有页面都被进程使用了。

如果存在空闲页面的话，当一个进程出现缺页中断时，直接使用空闲页面即可。

如果物理内存已满，操作系统需要选择一个页面来替换。通常，操作系统会选择一个不再需要的页面进行替换，这个决策基于 使用的页面替换算法。

如果操作系统中有配置交换分区（swap area）的话，被置换的页面会被写入交换分区中，当被置换的页面需要被再次使用时，页面会从交换分区中被加载到内存的页面中。

交换分区是硬盘上专门划出的一个区域，用来作为系统内存的“扩展”。当物理内存使用接近或达到上限时，操作系统会把暂时不用的内存页（比如不活跃的后台程序）移到交换分区，从而释放出物理内存。

访存过程

对于进程而言，它自己可见的就是 虚拟地址（VA），当进程访问虚拟地址时，实际上是对于某个物理地址进行访问。

访存主要包含两大过程：

1. 地址翻译：VPN → PPN，即由虚拟地址（VA）得到物理地址（PA）的过程。
2. 根据物理地址（PA）去 cahce 或 主存 中读取数据。

需要熟练掌握将这两大过程中的各种细节，在考试中常将这个过程中的几个知识点复合在一起考察。

虚拟地址翻译过程

操作系统经过如下步骤将 虚拟地址 转为 物理地址：

1. 从虚拟地址（VA）中提取 VPN（虚拟页号）。
2. 根据 VPN 去访问 TLB。
   • 命中 TLB：从 TLB 中读取到相应的 物理页号（PPN）。
   • 未命中 TLB：读取页表后更新 TLB。
     • 命中页表：从页表中读取到相应的 PPN，并且更新 TLB 表项。
     • 未命中页表：触发缺页中断，从内存中找一个页面以加载物理页面
       • 存在空闲页面，直接使用空闲页面，使用空闲页面的 PPN 更新页表。
       • 不存在空闲页面，选择一个进程的页面进行置换。
3. 组装 物理页号（PPN）和 页内偏移（PPO）得到物理地址。

上述过程可以由如下的流程图表示：

上文中提到的缺页中断过程忽略了一些细节，缺页中断处理的详细过程如下：

1. 触发缺页中断：
   • 当 CPU 尝试访问一个虚拟内存页面，但该页面未加载到物理内存（或页面无效）时，MMU（内存管理单元）检测到页面缺失，触发缺页中断。
2. 判断缺页原因：
   • 缺页有三种情况：
     • 页面未分配
     • 页面在磁盘（换出）
     • 非法访问：访问越界或权限不足
   • 如果是非法访问，如果是非法访问，操作系统会终止程序（如段错误，Segmentation Fault）。
3. 判断是否有空闲页面：
   • 如果有空闲页面，操作系统会分配一个新的物理页面。
   • 如果物理内存不足，可能会通过页面置换算法（如 LRU）选择一个现有页面换出到磁盘，腾出空间。
4. 加载页面内容：
   • 如果页面未分配，操作系统会分配一个新的物理页面。
   • 如果物理内存不足，可能会通过页面置换算法（如 LRU）选择一个现有页面换出到磁盘，腾出空间。
5. 更新页表：
   • 添加一条新的页面映射表项。
6. 恢复执行：
   • 缺页中断处理完成后，操作系统恢复被中断的程序上下文。
   • CPU 重新执行引发缺页的指令，此时页面已可用，程序继续正常运行。

物理地址访存过程

访存过程常常和地址翻译过程放在一起考察，在进程访问一个虚拟地址时，首先完成地址翻译得到物理地址，然后就是使用这个物理地址去访问内存。

使用物理地址去访问内存时首先需要去判断物理地址是否命中 cache，如果没有命中的话，就去访问内存，然后再更新 cache， 在使用主存块去更新 cache 块的过程中，还要根据 cache 和主存的映射方式去决定应该替换哪一个 cache 块， 详细过程如下图所示。

虚拟地址翻译和访存过程总结

如果将 地址翻译过程 和 访存过程放在一起的话，使用一个虚拟地址访问内存，大致包含如下流程（这里 ? 表示不一定会发生）：

虚拟地址 → TLB → （页表）? → （缺页中断）? → 物理地址 → Cache → （内存）? → （更新 Cache）?