虚拟存储器
虚拟存储器
虚拟存储器是一种计算机内存管理技术，它在物理内存和磁盘存储之间创建了一个抽象的、扩展的内存空间，以提供更大的可用内存容量。
虚拟内存和物理内存
- 虚拟内存（Virtual Memory）：
- 虚拟内存是一种计算机内存管理技术，它将计算机的物理内存扩展到磁盘上，从而提供了更大的可用内存空间。
- 每个进程拥有自己的虚拟地址空间，这个地址空间通常比物理内存大得多。
- 进程使用虚拟地址来访问内存中的数据和指令，而不需要了解物理内存的详细情况。
- 物理内存（Physical Memory）：
- 物理内存是计算机上实际存在的内存硬件，包括 RAM（随机存储器）芯片和其他存储设备。
- 物理内存是计算机硬件用来存储正在运行的进程和操作系统内核的数据和指令的地方。
- 物理地址是实际的内存地址，对应于计算机硬件上的存储器芯片中的位置。
页式虚拟存储器
地址翻译机构
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）：缓存位用于指示是否允许将虚拟页的内容缓存在高速缓存中。这有助于控制内存访问的性能。
Note:
需要注意的是，页表项的具体结构可以因不同的计算机体系结构和操作系统而异，在做题目时根据题目的具体指示进行判断。
这里主要关注虚拟页框号、物理页框号以及有效位即可，这是大多数单级页表中都会包含的内容。
对于页表项中的其他位，主要管制修改位和访问位，保护位和缓存位不太会考察。
通过单级页表的地址翻译过程
虚拟地址和物理地址的格式
- 虚拟地址（Virutal Address）分为两个部分：
- 虚拟页框号（VPN, Virtual Page Number）：当前地址所在的页框在虚拟内存对应的所有页框中的下标
- 页内偏移（VPO, Virutal Page Offset）：地址在页面内的偏移
- 物理地址（Physical Address）同样分为两个部分：
- 物理页框号（PPN, Physical Page Number）：当前地址所在的页框在物理内存对应的所有页框中的下标
- 页内偏移（PPO, Physical Page Offset）：地址在页面内的偏移
地址翻译过程
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）得到物理地址。
上述过程可以由如下的流程图表示：
物理地址访存过程
访存过程常常和地址翻译过程放在一起考察，在进程访问一个虚拟地址时，首先完成地址翻译得到物理地址，然后就是使用这个物理地址去访问内存。
访问内存时首先需要去判断 cache 是否命中，如果没有命中的话，就去访问内存，然后再更新 cache，详细过程如下图所示。
如果将 地址翻译过程 和 访存过程放在一起的话，使用一个虚拟地址访问内存，大致包含如下流程（这里 ? 表示不一定会发生）：
虚拟地址 → TLB → (页表)? → (缺页中断)? → 物理地址 → Cache → (内存)? → (更新Cache)?