虚拟存储器

重点内容，每年都会在大题中考察，与操作系统内存管理放在一起复习。

虚拟存储器

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

物理内存

物理内存（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）这两个字段。

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

注意

需要注意和区分一下以下几个名词，它们具有相同的含义：

虚拟页面 = Virutal Page = 逻辑页面 = Logical Page

页框 = Frame = 物理页面 = Physical Page

地址翻译机构

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	Cache
存储的是什么？	物理页面号（PPN）	主存块
使用什么去查找？	虚拟页面号（VPN）	主存块号
在何种场景下使用？	将虚拟地址翻译为物理地址时	访问物理地址时

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）。此时，操作系统会将相应的页面从磁盘加载到物理内存，进行页面替换。

注意

如何判断访问的页面是否在物理内存中呢？

通过查询 TLB 和页表以判断某个虚拟地址对应的页面是否在内存中。

从虚拟地址（VA）中提取出虚拟页号（VPN），再查询 TLB 和页表中是否存在包含 VPN 的记录。如果都不存在的话，则说明内存中不存在与 VPN 对应的物理页面。

页面替换

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

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

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

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

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

访存过程

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

访存主要包含两大过程：

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

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

虚拟地址翻译过程

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

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

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

缺页中断

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

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

物理地址访存过程

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

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

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

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

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