这次回顾深入理解计算机系统第9章虚拟内存部分。

电子书地址：

http://eol.bnuz.edu.cn/meol/common/script/preview/download_preview.jsp?fileid=2169600&resid=242120&lid=28605

备注：图片和总结内容均来自于电子书。

第9章：虚拟内存

重要概念

物理地址（Physical Address, PA）
虚拟地址（Virtual Address, VA）
内存管理单元（Memory Management Unit, MMU）
地址空间
虚拟页(Virtual Page, VP)
物理页(Physical Page, PP)，也被称为页帧(page frame)
虚拟页面集合的三个部分：
- 末分配的；
- 缓存的；
- 末缓存的；
页表(Page table)
- 虚拟页映射到物理页；
- 页表条目(Page Table Entry, PTE)的数组；
- 缺页（page fault）：DRAM缓存不命中；
工作集(working set)，常驻集合(resident set)，抖动(thrashing)；
段错误(segmentation fault)；
页表基址寄存器(Page Table Base Register, PTBR)；
虚拟页面偏移(Virtual Page Offset, VPO) ；
$(n-p)$位的虚拟页号( Virtual Page Number, VPN)；
页表条目中物理页号(Physical Page Number, PPN)；
物理页面偏移(Physical Page Offset, PPO)；
翻译后备缓冲器(Translation Lookaside Buffer, TLB)；
TLB索引(TLBI)是由VPN的$t$个最低位组成的，而$\mathrm{TLB}$标记( $\mathrm{TLBT})$是由$\mathrm{VPN}$中剩余的位组成的。

简介

虚拟内存提供一种对主存抽象的概念，提供了三个重要功能：

它将主存看成是一个存储在磁盘上的地址空间的高速缓存，在主存中只保存活动区域，并根据需要在磁盘和主存之间来回传送数据，通过这种方式，它高效地使用了主存。
它为每个进程提供了一致的地址空间，从而简化了内存管理。
它保护了每个进程的地址空间不被其他进程破坏。

物理和虚拟寻址

主存结构

计算机系统的主存被组织成一个由$M$个连续的字节大小的单元组成的数组。每字节都有一个唯一的物理地址（Physical Address, PA）。第一个字节的地址为$0$，第二个为$1$，以此类推。

物理寻址

CPU直接读取物理地址的寻址方式称为物理寻址，示例为：

使用场景：

早期的PC；
数字信号处理器、嵌入式微控制器；
Cray超级计算机；

虚拟寻址

CPU通过生成一个虚拟地址（Virtual Address, VA）来访问主存的寻址方式称为虚拟寻址。

虚拟地址在被送到内存之前先转换成适当的物理地址，该过程称为地址翻译，由操作系统使用称为内存管理单元（Memory Management Unit, MMU）的硬件来进行该过程。

虚拟寻址示例：

地址空间

地址空间是一个非负整数地址的有序集合：

$\{0,1,2, \cdots\}$

如果地址空间中的整数是连续的，那么我们说它是一个线性地址空间，后续均假设地址空间为线性地址空间。

在一个带虚拟内存的系统中，CPU从一个有$N=2^{n}$个地址的地址空间中生成虚拟地址，这个地址空间称为虚拟地址空间(virtual address space)：

$\{0,1,2, \cdots, N-1\}$

地址空间的大小由表示最大地址所需要的位数来描述，一个包含$N=2^n$个地址的虚拟地址空间叫做一个$n$位地址空间，现代系统通常支持32位或64位地址空间。

一个系统还有一个物理地址空间(physical address space)，对应于系统中物理内存的$M$个字节：

$\{0,1,2, \cdots,M-1\}$

通常假设

$M=2^m$

说明：

每个数据对象可以有多个独立的地址，每个地址选自于不同的地址空间，这也是虚拟内存的基本思想。

虚拟内存作为缓存的工具

虚拟页和物理页

虚拟页和物理页的概念：

概念上而言，虚拟内存被组织为一个由存放在磁盘上的$N$个连续的字节大小的单元组成的数组。每字节都有一个唯一的虚拟地址，作为到数组的索引。
磁盘上数组的内容被缓存在主存中，和存储器层次结构中其他缓存一样，磁盘（较低层）上的数据被分割成块，这些块作为磁盘和主存（较高层）之间的传输单元。
VM系统通过将虚拟内存分割为称为虚拟页(Virtual Page, VP)的大小固定的块来处理这个问题。每个虚拟页的大小为$P=2^{p}$字节。
类似地，物理内存被分割为物理页(Physical Page, PP)，大小也为$P$字节（物理页也被称为页帧(page frame)）。

在任意时刻，虚拟页面的集合都分为三个不相交的子集：

末分配的：VM系统还末分配（或者创建）的页。末分配的块没有任何数据和它们相关联，因此也就不占用任何磁盘空间。
缓存的：当前已缓存在物理内存中的已分配页。
末缓存的：末缓存在物理内存中的已分配页。

示例：

DRAM缓存的组织结构

DRAM缓存表示虚拟内存系统的缓存，它在主存中缓存虚拟页。
由于DRAM缓存不命中要由磁盘来服务，所以虚拟页往往很大，通常是$\mathrm{4KB\sim 2MB}$；
DRAM是全相联的，即任何虚拟页都可以放置在任何物理页中；
缓存使用写回，不是直写；

页表

页表简介：

页表(page table)是存放在物理内存中的数据结构；
页表将虚拟页映射到物理页；
每次地址翻译硬件将一个虚拟地址转换为物理地址时，都会读取页表；
操作系统负责维护页表的内容，以及在磁盘与DRAM之间来回传送页；

详细说明：

页表是页表条目(Page Table Entry, PTE)的数组；
虚拟地址空间中的每个页在页表中一个固定偏移量处都有一个 PTE；
这里假设每个PTE是由一个有效位(valid bit)和一个$n$位地址字段组成；
- 有效位表明了该虚拟页当前是否被缓存在DRAM中；
  - 如果设置了有效位，那么地址字段就表示DRAM中相应的物理页的起始位置，这个物理页中缓存了该虚拟页；
  - 如果没有设置有效位，那么一个空地址表示这个虚拟页还末被分配。否则，这个地址就指向该虚拟页在磁盘上的起始位置；

页表示例：

说明：

4个虚拟页（VP1, VP2, VP4, VP7）当前被缓存在DRAM中；
（VP0, VP5）还未被分配；
（VP3, VP6）已经被分配，但是当前还未被缓存；

页命中

当CPU想要读取包含在VP2中的虚拟内存的一个字发生如下内容：

地址翻译硬件将虚拟地址作为一个索引来定位PTE2，并从内存中读取它；
因为设置了有效位，所以地址翻译硬件就知道VP2是缓存在内存中的了；
使用PTE中的物理内存地址构造出这个字的物理地址；

示例：

缺页（页不命中）

DRAM缓存不命中称为缺页(page fault)，一个具体案例如下。

当CPU想要读取包含在VP3中的虚拟内存的一个字时：

地址翻译硬件从内存中读取PTE3，从有效位推断出VP3末被缓存，并且触发一个缺页异常。
缺页异常调用内核中的缺页异常处理程序，该程序会选择一个牺牲页，在此例中就是存放在PP3中的VP4。
- 如果VP4已经被修改了，那么内核就会将它复制回磁盘。
- 无论哪种情况，内核都会修改VP4的页表条目, 反映出VP4不再缓存在主存中这一事实。
内核从磁盘复制VP3到内存中的PP3，更新PTE3，随后返回；
当异常处理程序返回时，它会重新启动导致缺页的指令，该指令会把导致缺页的虚拟地址重发送到地址翻译硬件中；
- 此时VP3已经缓存在主存中，可以正常处理；

缺页前：

缺页后：

说明

虚拟内存和缓存术语不同，但是概念相似，例如：

缓存中的块被称为页；
在磁盘和内存之间传送页的活动叫做交换(swapping)或者页面调度(paging)；

页面分配

这个示例中，VP5的分配过程是在磁盘上创建空间并更新PTE5，使它指向磁盘上这个新创建的页面。

局部性

虚拟内存的效率比想象的高，因为局部性原则保证了在任意时刻，程序将趋向于在一个较小的活动页面(active page)集合上工作，这个集合叫做工作集(working set)或者常驻集合(resident set)。
一开始将工作集页面调度到内存中，接下来对这个工作集的引用将导致命中；
如果工作集的大小超出的物理内存的大小，那么程序将产生一种不幸的状态，叫做抖动(thrashing)，这时页面将不断地换进换出。

虚拟内存作为内存管理的工作

操作系统为每个进程提供一个独立的页表，因而也就是一个独立的虚拟地址空间，示例如下：

VM简化了链接和加载、代码和数据共享，以及应用程序的内存分配：

简化链接：
- 独立的地址空间允许每个进程的内存映像使用相同的基本格式，而不管代码和数据实际存放在物理内存的何处。
简化加载：
- 要把目标文件中.text 和.data节加载到一个新创建的进程中，Linux加载器为代码和数据段分配虚拟页，把它们标记为无效的（即末被缓存的），将页表条目指向目标文件中适当的位置。
简化共享：
- 独立地址空间为操作系统提供了一个管理用户进程和操作系统自身之间共享的一致机制。
- 一般而言，每个进程都有自己私有的代码、数据、堆以及栈区域，是不和其他进程共享的。
- 如果要共享代码或数据，比如printf，操作系统通过将不同进程中适当的虚拟页面映射到相同的物理页面，从而安排多个进程共享这部分代码的一个副本，而不是在每个进程中都包括单独的内核和C标准库的副本。
简化内存分配：
- 当一个运行在用户进程中的程序要求额外的堆空间时（如调用malloc的结果），操作系统分配一个适当数字(例如$k$) 个连续的虚拟内存页面，并且将它们映射到物理内存中任意位置的$k$个任意的物理页面。
  - 由于页表的工作方式，物理页面没有必要连续。

虚拟内存作为内存保护的工具

任何现代计算机系统必须为操作系统提供手段来控制对内存系统的访问，在PTE上增加字段即可做到这点：

说明：

SUP位表示进程是否必须运行在内核（超级用户）模式下才能访问该页。
- 运行在内核模式中的进程可以访问任何页面，但是运行在用户模式中的进程只允许访问那些SUP为0的页面；
READ位和WRITE位控制对页面的读和写访问。
- 例如，如果进程$i$运行在用户模式下，那么它有读VP0和读写VP1的权限。然而，不允许它访问VP2。
如果一条指令违反了这些许可条件，那么CPU就触发一个一般保护故障，将控制传递给一个内核中的异常处理程序。Linux shell一般将这种异常报告为“段错误(segmentation fault)”

地址翻译

符号

基本参数：

$\begin{array}{|l|l|} \hline \text { 符 } \text { 号 } & \text { 描 } \text { 述 } \\ \hline N=2^{n} & \text { 虚拟地址空间中的地址数量 } \\ \hline M=2^{m} & \text { 物理地址空间中的地址数量 } \\ \hline P=2^{p} & \text { 页的大小 (字节) } \\ \hline \end{array}$

虛拟地址 (VA) 的组成部分

$\begin{array}{|c|c|} \hline \text { 符 } \text { 号 } & \text { 描 } \text { 述 } \\ \hline \text { VPO } & \text { 虚拟页面偏移量 (字节) } \\ \hline \text { VPN } & \text { 虚拟页号 } \\ \hline \text { TLBI } & \text { TLB 索引 } \\ \hline \text { TLBT } & \text { TLB 标记 } \\ \hline \end{array}$

物理地址(PA)的组成部分

$\begin{array}{|l|l|} \hline \text { 符号 } & \text { 描 } \text { 述 } \\ \hline \text { PPO } & \text { 物理页面偏移量 (字节) } \\ \hline \text { PPN } & \text { 物理页号 } \\ \hline \text { CO } & \text { 缓冲块内的字节偏移量 } \\ \hline \text { CI } & \text { 高速缓存索引 } \\ \hline \text { CT } & \text { 高速缓存标记 } \\ \hline \end{array}$

简介

地址翻译是一个${N}$元素的虚拟地址空间(VAS)中的元素和一个$M$元素的物理地址空间(PAS)中元素之间的映射：

$\text { MAP: VAS } \rightarrow \text { PAS } \cup \varnothing$

其中

$\operatorname{MAP}(A)=\left\{\begin{array}{l} A^{\prime}\quad \text { 如果虚拟地址 } A \text { 处的数据在 } \mathrm{PAS} \text { 的物理地址 } A^{\prime} \text { 处 } \\ \varnothing\quad \ \text { 如果虚拟地址 } A \text { 处的数据不在物理内存中 } \end{array}\right.$

利用页表实现映射的方式：

作用方式：

CPU中的一个控制寄存器，页表基址寄存器(Page Table Base Register, PTBR)指向当前页表。
$n$位的虚拟地址包含两个部分: 一个$p$位的虚拟页面偏移(Virtual Page Offset, VPO)和一个$(n-p)$位的虚拟页号(Virtual Page Number, VPN)。
MMU利用VPN来选择适当的PTE。例如，VPN 0 选择 PTE 0，VPN 1 选择 PTE 1，以此类推。
将页表条目中物理页号(Physical Page Number, PPN)和虚拟地址中的VPO串联起来，就得到相应的物理地址。
注因为物理和虚拟页面都是$P$字节的，所以物理页面偏移(Physical Page Offset, PPO)和VPO是相同的。

页面命中时CPU硬件执行的步骤（完全由硬件处理）：

第 1 步 : 处理器生成一个虚拟地址，并把它传送给MMU。
第 2 步：MMU生成PTE地址，并从高速缓存/主存请求得到它。
第 3 步：高速缓存/主存向MMU返回PTE。
第 4 步 : MMU构造物理地址, 并把它传送给高速缓存/主存。
第 5 步：高速缓存/主存返回所请求的数据字给处理器。

示例：

缺页时CPU硬件执行的步骤（由硬件和操作系统内核协作完成）：

第1步到第3步：同之前的3步；
第4步：PTE 中的有效位是零, 所以MMU触发了一次异常, 传递CPU中的控制到操作系统内核中的缺页异常处理程序。
第5步：缺页处理程序确定出物理内存中的牺牲页，如果这个页面已经被修改了，则把它换出到磁盘。
第6步：缺页处理程序页面调入新的页面, 并更新内存中的PTE。
第7步：缺页处理程序返回到原来的进程，再次执行导致缺页的指令。
- CPU将引起缺页的虚拟地址重新发送给MMU。因为虚拟页面现在缓存在物理内存中，所以就会命中，主存就会将所请求字返回给处理器。

示例：

结合高速缓存和虚拟内存

使用虚拟内存又使用SRAM高速缓存的系统需要决定使用虚拟内存还是物理内存来访问SRAM高速缓存，大多数系统是选择物理寻址的，具体的结合方式如下：

利用TLB加速地址翻译

MMU中包括一个关于PTE的小缓存，称为翻译后备缓冲器(Translation Lookaside Buffer, TLB)，用来加速翻译。

TLB示例：

用于组选择和行匹配的索引和标记字段是从虚拟地址中的虚拟页号中提取出来的。如果TLB有$T=2^{t}$个组，那么 TLB索引(TLBI)是由VPN的$t$个最低位组成的，而$\mathrm{TLB}$标记($\mathrm{TLBT}$)是由$\mathrm{VPN}$中剩余的位组成的。

TLB命中时的步骤：

第1步：CPU产生一个虚拟地址。
第2步和第3步：MMU从TLB中取出相应的PTE。
第4步：MMU将这个虚拟地址翻译成一个物理地址，并且将它发送到高速缓存/主存。
第5步：高速缓存/主存将所请求的数据字返回给 CPU 。

示例：

TLB不命中时的步骤：

第1步：CPU产生一个虚拟地址。
第2步到第4步：MMU从L1缓存中取出相应的 PTE，存放在TLB中。
第5步：MMU将这个虚拟地址翻译成一个物理地址，并且将它发送到高速缓存/主存。
第6步：高速缓存/主存将所请求的数据字返回给 CPU 。

示例：

多级页表

使用多级页表结构减少内存开销，二级页表示例：

这种方法从两个方面减少了内存要求：

第一，如果一级页表中的一个PTE是空的，那么相应的二级页表就根本不会存在。这代表着一种巨大的潜在节约，因为对于一个典型的程序，4GB的虚拟地址空间的大部分都会是末分配的。
第二，只有一级页表才需要总是在主存中；虚拟内存系统可以在需要时创建、页面调入或调出二级页表，这就减少了主存的压力；只有最经常使用的二级页表才需要缓存在主存中。

$k$级页表层次结构的地址翻译：

虚拟地址被划分成为$k$个VPN和$1$个VPO。
每个VPN $i$都是一个到第$i$级页表的索引，其中 $1 \le i \le k$ 。
第$j$级页表中的每个PTE， $1 \le j\le k-1$, 都指向第$j+1$级的某个页表的基址。
第$k$级页表中的每个PTE包含某个物理页面的PPN，或者一个磁盘块的地址。
为了构造物理地址，在能够确定PPN之前，MMU必须访问$k$个PTE。
对于只有一级的页表结构，PPO和VPO是相同的。