编程之禅
0%

虚拟内存的作用，虚拟地址，页表，TLB，缓存原理

发表于 更新于 分类于 阅读次数： Disqus：

9.1 物理地址和虚拟地址

计算机系统的主存是由 M 个连续的字节大小的单元组成的数组。每个字节都有一个唯一的物理地址，地址范围从 0 到 M-1。计算机使用内存最自然的方式是使用物理地址，我们将这种方式称为物理寻址。

CPU 向内存发送一个地址，内存将该地址开始的四个字节信息传送到 CPU 中的一个 4字节寄存器。

另一种方式是使用虚拟地址，CPU 通过生成一个虚拟地址(VA)来访问主存，这个虚拟地址在被送到内存之前先转换成适当的物理地址，负责地址转换的专门硬件叫内存管理单元(MMU)。

9.2 地址空间

地址空间定义：一个非负整数地址的有序集合：{0,1,2,…}

如果地址空间是连续的，被称为线性地址空间(linear address space)

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

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

理解地址空间的概念很重要，因为它清除地区分了数据对象(字节)和它们的属性(地址)。

9.3 虚拟内存作为缓存的工具

虚拟内存系统(VM)通常将虚拟内存分割为称为虚拟页(Virtual Page，VP)的大小固定的块来处理这个问题。每个虚拟页的大小为P=2p字节，类似地，物理内存被分割成物理页(Physical Page，PP)，大小也为 P 字节，物理页也称为页帧。

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

  • 未分配的
  • 缓存的
  • 未缓存的

如下图所示：一个含有 8 个虚拟页的小虚拟内存，虚拟页 0 和 3 还没有被分配，虚拟页1，4和6被缓存在物理内存中。页 2，5，7 已经被分配了，但还未缓存在主存中。

截屏2021-10-31 下午5.23.30

9.3.1 DRAM 缓存的组织结构

使用术语 SRAM 表示位于 CPU 和主存之间的 L1，L2 和 L3 高速缓存，使用术语 DRAM（称为主存） 缓存来表示虚拟内存系统的缓存，它在主存中缓存虚拟页。

通常情况下，DRAM 比 SRAM 满大约 10倍，而磁盘比 DRAM 满大约 100 000 多倍，因此 SRAM 缓存不命中比SRAM缓存不命中的代价要高昂的多。总的来说，DRAM 缓存的组织结构完全是由巨大的不命中开销驱动的。

为了减少不命中产生的开销，虚拟页往往很大，通常是 4KB 到 2MB，DRAM 缓存是全相联的，即任何虚拟页都可以放置在任何的物理页中。因为对磁盘的访问时间很长，DRAM 缓存总是使用写回(Write-Back)，而不是直写(Write-Through)。

写回：将数据写入缓存页中，当缓冲页被替换时再写入磁盘。这样能明显提升系统运行效率，因为访问缓存和访问磁盘的速度不是一个量级的。

直写：不经过缓存，直接将数据写入磁盘，然后将缓存页的脏位置为1，当读取到该缓时再从磁盘读取该页。

9.3.2 页表

同任何缓存一样，虚拟内存必须有某种方法来判定一个虚拟页是否缓存在 DRAM 中的某个地方，如果缓存了的话，还必须确定这个虚拟页存放在哪个物理页中，如果不命中，系统必须判断这个虚拟页存放在磁盘的哪个位置，在物理内存中选择一个将其移出(如果物理内存已经满了的话)，然后将虚拟页从磁盘复制到 DRAM 中。

这些功能由软硬件联合提供，包括操作系统软件，MMU(内存管理单元)中的地址翻译硬件和一个存放在物理内存中叫做页表(Page table)的数据结构，页表将虚拟页映射到物理页。每次地址翻译硬件将一个虚拟地址转换为物理地址时，都会读取页表。操作系统负责维护页表的内容，以及在磁盘和DRAM 之间来回传送页。

下图所示一个页表的基本组织结构：页表就是一个页表条目的数组(Page Table Entry，PTE)的数组，虚拟地址空间中的每个页在页表中一个固定偏移量处都有一个 PTE。我们假设每个 PTE 都有一个有效位(valid bit)和一个 n 位地址字段组成的。有效位表明该虚拟页当前是否被缓存在 DRAM 中，如果设置了有效位，那么 PTE 的地址字段就表示 DRAM 中相应物理页的起始位置，这个物理页缓存了虚拟页。

截屏2021-10-31 下午5.55.08

如上图所示：展示了一个有 8 个虚拟页和 4 个物理页的系统的页表，4 个虚拟页(VP1，VP2，VP4，VP7)被缓存在 DRAM 中，2 个页(VP0 和 VP5) 还未被分配，剩下的(VP3 和 VP6)已经被分配了，但是当前还未被缓存。

9.3.3 页命中

当 CPU 访问的虚拟页已经被缓存在 DRAM 中时，称为命中，这时直接从 PTE 中取出物理地址，然后从 DRAM 中直接取出数据即可。

9.3.4 缺页

DRAM 中缓存不命中称为缺页(Page fault)，当发生缺页时，触发缺页中断，执行内核中的缺页异常处理程序，如果主存已经满了的话，该程序将主存中的一个物理页换回磁盘，然后将所缺的页调用主存。

截屏2021-10-31 下午6.19.47

如下图所示：内核从磁盘复制 VP 3 到内存中的 PP 3，更新 PTE 3，随后返回。

截屏2021-10-31 下午6.27.55

由上述两图展现的缺页过程，称为按需页面调度：一直等待，直到最后时刻，也就是不命中发生时，才换入页面的这种策略称为按需页面调度(demand paging)。也可以采用其它方式，例如 尝试预测不命中，在页面实际被引用前就换入页面。不过，几乎所有的现代系统都是用按需页面调度。

9.3.5 分配页面

下图展示了分配一个新的虚拟内存页时对页表的影响，当调用 malloc 时便会发生这种过程。

截屏2021-10-31 下午6.36.03

9.3.6 又是局部性救了我们

了解了虚拟内存的基本概念之后，它的不命中通常代价非常高昂，那么虚拟内存的效率是否非常低呢？实际上虚拟内存工作的相当好，这主要归功于局部性原理(locality)。尽管整个运行过程中程序引用的不同页面的总数可能超出物理内存的总大小，但是局部性原则保证了在任意时刻，程序将趋向于在一个较小的活动页面(active page)集合上工作，这个集合叫做工作集(working set)或者常驻集合(resident set)。

当然并不是所有程序都能展现良好的时间局部性。如果工作级的大小超出了物理内存的大小，那么程序将产生一种不幸的状态，叫做抖动(thrashing)，这时页面将不断地换入换出。

可以利用 Linux 的 getrusage 函数监测缺页的数量。

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

虚拟内存大大地简化了内存管理，并提供了一种自然的保护内存的方法。操作系统为每一个进程都提供了一个独立的虚拟地址空间，下图展示了其基本思想。多个页面可以映射到同一个共享物理页面。

截屏2021-10-31 下午8.50.53

按需页面调度和独立的虚拟地址空间的结合，对系统内存的使用和管理造成了深远的影响。特别是，VM 简化了链接和加载，代码和数据共享，以及应用程序的内存分配。

  • 简化链接：独立的地址空间允许每个进程的内存映像使用相同的基本格式，而不管代码和数据实际存放在物理内存的何处。

    截屏2021-10-31 下午8.56.15

  • 简化加载：虚拟内存还使得容易向内存中加载可执行文件和共享对象文件。对于程序需要使用的 .text 和 .data 还可实现按需加载，加载器首先为代码和数据段分配虚拟页，把它们标记为无效的(未被缓存)，当实际用的时候才去磁盘中加载。

    将一组连续的虚拟页映射到任意一个文件中的任意位置的表示法称为内存映射(memory mapping)。Linux 提供了一个称为 mmap 的系统调用，允许应用程序自己做内存映射。

  • 简化共享：独立地址空间为操作系统提供一个管理用户进程和操作系统自身之间共享的一种机制。一般而言，每个进程都有自己的代码，数据，堆以及栈区域，是不和其它进程共享的，在这种情况下，操作系统创建页表，将相应的虚拟页映射到不连续的物理页面。

  • 简化内存分配：虚拟内存向用户进程提供了一个简单的分配额外内存的方式。当一个运行在用户进程中的程序要求额外的堆空间时(如调用 malloc 的结果)，操作系统分配一个适当数字(例如 k )个连续的虚拟内存页面，并且将它们映射到内存中任意位置的 k 个任意的物理页面。由于页表工作的方式，操作系统没有必要分配 k 个连续的物理内存页面。页面可以随机地分散在物理内存中。

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

现在计算机系统必须为操作系统提供手段来控制对内存系统的访问。不应该允许一个用户进程修改它的只读代码段。而且也不允许它读或修改任何内核中的代码和数据结构。不允许它读或写其它进程的私有内存，不允许它修改任何与其它进程共享的虚拟页面，除非所有共享者都显示地允许它这么做(通过进程间通信)。

虚拟内存每次访问内存，都有一个地址翻译的过程，即每次 CPU 生成一个地址时，地址翻译硬件都会读一个 PTE，通过在 PTE 上添加一些额外的许可来控制一个虚拟页面内容的访问十分简单。如下图所示：

截屏2021-10-31 下午9.16.24

在上述实例中，每个 PTE 中已经添加了三个许可，SUB 位表示是否必须运行在内核模式下才能访问该页，READ位和WRITE位控制对页面的读写。如果一条指令违反了这些许可条件，CPU 就触发一个一般保护故障，将控制传递给内核中一个异常处理程序。Linux shell 将这种异常报告称为“段错误(segmentation fault)”

9.6 地址翻译

以下为讨论本节需要的符号：

IMG_BBF2272209FF-1

地址翻译就是一个虚拟地址到一个物理地址的翻译过程。一个虚拟地址包含两部分，虚拟页号(VPN)，虚拟页内偏移(VPO)。通过虚拟页号(可以理解为数组下标)，在页表(可以理解为数组)中找到对应的条目，条目内容为物理页号，将物理页号和虚拟页内偏移结合起来，就可以组成一个物理地址。完整过程如下图所示：

IMG_99886A9EF173-1

当页面命中时，CPU 硬件执行步骤如下：

  1. 处理器生成一个虚拟地址(VA)，并把它传送给MMU。
  2. MMU 从虚拟地址(VA)取出虚拟页号(VPN) ，并从高速缓存/主存请求获得PTE条目
  3. 高速缓存/主存向 MMU 返回 PTE
  4. MMU 根据返回的 PTE 获得物理页号(PPN)，和 VPO 组合形成物理地址，并将物理地址发送给高速缓存/主存
  5. 高速缓存/主存返回所请求的数据给 CPU

具体过程如下：

截屏2021-11-01 下午10.54.23

当页面不命中时，CPU 硬件执行步骤如下：

1-3 步和上图命中时相同

  1. PTE 的有效位是 0，所以 MMU 触发了一次异常，将 CPU 控制权转移给操作系统内核中的缺页异常处理程序。
  2. 缺页处理程序确定物理内存中的牺牲页，如果这个页已经被修改，则把它换出到磁盘。
  3. 缺页处理程序掉入新的页面，并更新内存中的 PTE。
  4. 缺页处理程序返回到原来的进程，再次执行缺页异常的指令。之后的操作就是页面命中的操作。

9.6.1 结合高速缓存和虚拟内存

从 9.6 的分析可以看出，每次访问数据，都至少访问内存两次。为了加快数据的访问速度，现代计算机通常在 CPU 和主存之间加一个页表高速缓存(Cache)，Cache 存储页号和物理页号，这样只需访问一次高速缓存和一次内存即可取出内存中的数据。

带有高速缓存的内存访问过程如下：

高速缓存命中时：

  1. 处理器生成一个虚拟地址(VA)，并把它传送给MMU。
  2. MMU 从虚拟地址(VA)取出虚拟页号(VPN) ，并从高速缓存请求获得物理页号(PPN)。
  3. MMU 将物理页号和虚拟页内偏移组合形成物理地址，并将该地址发送给主存。
  4. 主存返回数据给 CPU

高速缓存未命中时：

  1. 处理器生成一个虚拟地址(VA)，并把它传送给MMU。
  2. MMU 从虚拟地址(VA)取出虚拟页号(VPN) ，并从高速缓存请求获得物理页号(PPN)。
  3. 该页不在高速缓存中，高速缓存使用 VPN 从内存请求获得 PTE。
  4. 若高速缓存已经满了，则剔除一个较旧的页，将新返回的 PTE 插入高速缓存中。
  5. 高速缓存将物理页号和虚拟页内偏移组成物理地址，并发送给内存。
  6. 内存返回数据给高速缓存。
  7. 高速缓存将数据发送给 CPU。

具体过程如下：

IMG_F0C51817CA3B-1

9.6.2 利用 TLB 加速地址翻译

每次 CPU 产生一个虚拟地址，MMU 就必须查阅一个 PTE，以便将虚拟地址翻译为物理地址。最糟糕的情况下，这会要求从内存多取一次数据，代价是几十到几百个周期，如果碰巧 PTE 缓存在 L1 中，那么开销就会降到 1 个或 2 个周期。

为了更快地从内存获取数据，许多系统在 MMU 中设计一个关于 PTE 的小的缓存，称为翻译后备缓冲器(Translation Lookaside Buffre, TLB)，也称之为快表。

TLB 是一个小的，虚拟寻址的缓存，其中的每一行都保存着一个由单个 PTE 组成的块，用于行匹配的索引和标记字段是从虚拟地址中的虚拟页号中提取出来的。如果 TLB 中有 T=2t个组，那么 TLB 索引由 VPN 的 t 个最低位组成，而 TLB 标记由 VPN 的剩余位组成。

下图展示了 TLB 命中时包括的步骤。这里的关键是，所有的地址翻译步骤都是在芯片上的 MMU 中执行的，因此非常快。

截屏2021-11-01 下午11.43.11

  1. CPU 产生一个虚拟地址。

    1. MMU 从TLB 中取出 PTE

  3. MMU 将这个虚拟地址翻译为一个物理地址，并且将它发送到高速缓存/主存。

  4. 高速缓存/主存将所请求的数据返回给 CPU。

当 TLB 不命中时，MMU 必须从 L1 中取出相应的 PTE，新取出的 PTE 存放在 TLB 中，可能会覆盖一个已经存在的条目。具体过程如下图所示：

截屏2021-11-01 下午11.47.19

9.6.3 多级页表

对于32位地址空间，4KB 的页面和一个 4 字节的 PTE，即便我们所引用的只是虚拟地址空间中很小的一部分，也总是需要一个 4MB 的页表驻留在内存中，对于地址空间为 64位的系统来说，问题将变得更复杂。

用来压缩页表的常用方法是使用层次结构的页表。假设 32位 虚拟地址空间被分为 4KB 的页，而每个页表条目都是 4 字节，假设在这一时刻，虚拟地址空间有如下形式：内存的前 2K 个页面分配给了代码和数据，接下来的 6K 个页面还未分配，再接下来的 2013 个页面也未分配，接下来的 1 个页面分配给了用户栈。下图展示了如何为这个虚拟地址空间构造一个2 级的页表层次结构。

IMG_2F8D7239EB81-1

一级页表中的每个 PTE负责映射虚拟地址空间中的一个 4MB 的片，这个的每个片都是由 1024 个连续的页面组成。假设地址空间是 4GB，1024 个PTE足以覆盖整个空间。从上图可以看出，一级页表中 PTE2 为空，这样就不用为它分配二级页表，只有在需要的时候才需要分配二级页表。

多级页表好处：如果一级页表中一个 PTE 是空的，那么相应的二级页表就根本不会存在，这代表一种巨大的潜在的节约。

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

IMG_138FFAB7F9E9-1

表面上看似乎多级页表的代价高昂，然而，这里 TLB 能够起作用，正是通过将不同层次上页表的 PTE 缓存起来。实际上，多级页表的地址翻译并不比单级页表慢很多。