为什么需要虚拟内存?

CPU 访问内存的最自然的方式就是使用物理地址,这种方式称为物理寻址。1,计算机中并不是只有一个程序在运行,如果它们都是用物理寻址的方式,那么所有程序必须在链接之前确定好自己所用到的内存范围,否则两个程序就可能会发生冲突。2,程序大于内存的问题早在上世纪六十年代就出现,后来出现了覆盖技术(Overlay),把程序分割成许多片段。程序开始执行时,将覆盖管理模块装入内存,该管理模块立即装入并运行覆盖 0。执行完成后,覆盖 0 通知管理模块装入覆盖 1,或者占用覆盖 0 的上方位置(如果有空间),或者占用覆盖 0(如果没有空间)。把一个大程序分割成小的、模块化的片段是非常费时和枯燥的,并且易于出错。很少程序员擅长使用覆盖技术。

为了更加有效地管理内存并且少出错,现代系统提供了一种对主存的抽象概念,叫做虚拟内存(VM)。主要有三个功能:

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

什么是虚拟寻址?

如果主存被分为长度为$M$的单字节大小的数组,每个字节都对应一个物理地址,CPU 通过这个唯一的地址访问主存,这样的方式就是物理寻址Responsive Image

现代处理器使用虚拟寻址的方式。CPU 通过生成的虚拟地址来访问内存,这个地址在送到内存之前会被转换成物理地址。这个过程称为地址翻译。CPU 芯片上叫做内存管理单元(Memory Management Unit, MMU)的专用硬件,利用存放在主存中的查询表来动态翻译虚拟地址,该表的内容由操作系统管理。Responsive Image

虚拟内存作为缓存的工具

概念上而言,虚拟内存被组织成为一个由存放在磁盘上的 N 个连续的字节大小的单元组成的数组,也就是字节数组。每个字节都有一个唯一的虚拟地址作为数组的索引。磁盘上活动的数组内容被缓存在主存中。在存储器结构中,较低层次上的磁盘的数据被分割成块,这些块作为和较高层次的主存之间的传输单元。主存作为虚拟内存的缓存

虚拟内存被分割为大小固定的块,这些块叫虚拟页(Virtual Page,VP),类似的物理内存也有物理页(Physical Page, PP)。虚拟页有三种不同的状态:

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

为了有助于清晰理解存储层次结构中不同的缓存概念,我们将使用术语SRAM缓存来表示位于 CPU 和主存之间的 Ll、L2 和 L3 高速缓存,并且用术语 DRAM 缓存来表示虚拟内存系统的缓存,它在主存中缓存虚拟页。

在存储层次结构中,DRAM 缓存的位置对它的组织结构有很大的影响。回想一下,DRAM 比 SRAM 要慢大约 10 倍,而磁盘要比 DRAM 慢大约 100000 多倍。因此,DRAM 缓存中的不命中比起 SRAM 缓存中的不命中要昂贵得多。因此,与硬件对 SRAM 缓存相比,操作系统对 DRAM 缓存使用了更复杂精密的替换算法。(这些替换算法超出了我们的讨论范围)。最后,因为对磁盘的访问时间很长,DRAM 缓存总是使用写回,而不是直写

页表

虚拟内存系统可以完成以下这些功能,

  • 判定一个虚拟页是否缓存在 DRAM 中的某个地方;
  • 可以确定这个虚拟页存放在哪个物理页中;
  • 如果不命中,系统必须判断这个虚拟页存放在磁盘的哪个位置,在物理内存中选择一个牺牲页,并将虚拟页从磁盘复制到 DRAM 中,替换这个牺牲页。

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

图 9-4 展示了一个页表的基本组织结构。页表就是一个页表条目(Page Table Entry,PTE)的数组。虚拟地址空间中的每个页在页表中一个固定偏移量处都有一个 PTE。

PTE 由两部分组成:

  • 有效位:表明了该虚拟页当前是否被缓存在 DRAM 中;
  • 地址:表示 DRAM 中相应的物理页的起始位置,这个物理页中缓存了该虚拟页。

Responsive Image

页命中与缺页

Responsive Image

l

当 CPU 访问已被缓存的地址时,就叫做页命中。如访问上图 VP2,虚拟地址索引到 PTE2,此时有效位为 1,地址翻译硬件就知道该地址被缓存了。

当 CPU 访问未被缓存的地址时,会导致缺页。如访问上图的 VP3,虚拟地址索引到 PTE3,此时有效位为 0,地址翻译硬件就知道该地址未被缓存,需要从磁盘中读取。

这时会触发一个缺页异常缺页异常调用内核中的缺页异常处理程序,该程序会选择一个牺牲页,在此例中就是存放在 PP 3 中的 VP 4。如果 VP 4 已经被修改了,那么内核就会将它复制回磁盘。无论哪种情况,内核都会修改 VP 4 的页表条目,反映出 VP 4 不再缓存在主存中这一事实。

接下来,内核从磁盘复制 VP 3 到内存中的 PP 3,更新 PTE 3,随后返回。当异常处理程序返回时,它会重新启动导致缺页的指令,该指令会把导致缺页的虚拟地址重发送到地址翻译硬件。但是现在,VP 3 已经缓存在主存中了,那么页命中也能由地址翻译硬件正常处理了。图 9-7 展示了在缺页之后我们的示例页表的状态。

Responsive Image

在虚拟内存的习惯说法中,块被称为页。在磁盘和内存之间传送页的活动叫做交换(swapping)或者页面调度(paging)。页从磁盘换入(或者页面调入)DRAM 和从 DRAM 换出(或者页面调出)磁盘。一直等待,直到最后时刻,也就是当有不命中发生时,才换入页面的这种策略称为按需页面调度(demand paging)。

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

之前我们只讨论了一个页表的情况,但是实际上操作系统为每个进程都分配了一个独立的页表。多个虚拟页面可以映射到同一个共享物理页面上。

Responsive Image

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

  • 简化链接。独立的地址空间允许每个进程的内存映像使用相同的基本格式,而不管代码和数据实际存放在物理内存的何处。例如,一个给定的 Linux 系统上的每个进程都使用类似的内存格式。对于 64 位地址空间,代码段总是从虚拟地址 0x400000 开始。数据段跟在代码段之后,中间有一段符合要求的对齐空白。栈占据用户进程地址空间最高的部分,并向下生长。这样的一致性极大地简化了链接器的设计和实现,允许链接器生成完全链接的可执行文件,这些可执行文件是独立于物理内存中代码和数据的最终位置的
  • 简化加载。虚拟内存还使得容易向内存中加载可执行文件和共享对象文件。要把目标文件中 .text 和 .data 节加载到一个新创建的进程中,Linux 加载器为代码和数据段分配虚拟页,把它们标记为无效的(即未被缓存的),将页表条目指向目标文件中适当的位置。有趣的是,加载器从不从磁盘到内存实际复制任何数据。在每个页初次被引用时,要么是 CPU 取指令时引用的,要么是一条正在执行的指令引用一个内存位置时引用的,虚拟内存系统会按照需要自动地调入数据页。将一组连续的虚拟页映射到任意一个文件中的任意位置的表示法称作内存映射(memory mapping)。Linux 提供一个称为 mmap 的系统调用,允许应用程序自己做内存映射。
  • 简化共享。独立地址空间为操作系统提供了一个管理用户进程和操作系统自身之间共享的一致机制。一般而言,每个进程都有自己私有的代码、数据、堆以及栈区域,是不和其他进程共享的。在这种情况中,操作系统创建页表,将相应的虚拟页映射到不连续的物理页面。
  • 简化内存分配。虚拟内存为向用户进程提供一个简单的分配额外内存的机制。当一个运行在用户进程中的程序要求额外的堆空间时(如调用 malloc 的结果),操作系统分配一个适当数字(例如 k)个连续的虚拟内存页面,并且将它们映射到物理内存中任意位置的 k 个任意的物理页面。由于页表工作的方式,操作系统没有必要分配 k 个连续的物理内存页面。页面可以随机地分散在物理内存中

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

操作系统中的用户程序不应该修改只读的代码段,也不应该读取或者修改内核中的代码和数据结构或者访问私有的以及其他的进程的内存,如果无法对用户进程的内存访问进行限制,攻击者就可以访问和修改其他进程的内存影响系统的安全。

Responsive Image

通过在页表中添加页面的保护属性,可以让操作系统在页面被访问时进行检查,如果页面被保护为只读,则操作系统会报错。

在图 9-10 这个示例中,每个 PTE 中已经添加了三个许可位。SUP 位表示进程是否必须运行在内核(超级用户)模式下才能访问该页。运行在内核模式中的进程可以访问任何页面,但是运行在用户模式中的进程只允许访问那些 SUP 为 0 的页面。READ 位和 WRITE 位控制对页面的读和写访问。例如,如果进程 i 运行在用户模式下,那么它有读 VP 0 和读写 VP 1 的权限。然而,不允许它访问 VP 2。

如果一条指令违反了这些许可条件,那么 CPU 就触发一个一般保护故障,将控制传递给一个内核中的异常处理程序。Linux shell 一般将这种异常报告为段错误(segmentation fault)。

地址翻译

基本参数

符号描述
$$\small N=2^n$$虚拟地址空间中的地址数量
$$\small M=2^m$$物理地址空间中的地址数量
$$\small P=2^p$$页的大小(字节)

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

符号描述
VPO虚拟页面偏移量(字节)
VPN虚拟页号
TLBITLB 索引
TLBTTLB 标记

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

符号描述
PPO物理页面偏移量(字节)
PPN物理页号
CO缓冲块内的字节偏移量
CI高速缓存索引
CT高速缓存标记

Responsive Image

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

Responsive Image

图 9-13a 展示了当页面命中时,CPU 硬件执行的步骤。

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

页面命中完全是由硬件来处理的,与之不同的是,处理缺页要求硬件和操作系统内核协作完成,如图 9-13b 所示。

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

利用 TLB 加速地址翻译

每次 CPU 访问一个虚拟地址,MMU 就必须查找 PTE,以便将虚拟地址翻译为物理地址。在最糟糕的情况下,这会要求从内存多取一次数据,代价是几十到几百个周期。如果 PTE 碰巧缓存在 L1 中,那么开销就下降到 1 个或 2 个周期。为了消除这样的开销,在 MMU 中包括了一个关于 PTE 的小的缓存,称为翻译后备缓冲器(Translation Lookaside Buffer,TLB)。

TLB 是一个小的、虚拟寻址的缓存,其中每一行都保存着一个由单个 PTE 组成的块。TLB 通常有高度的相联度。如图 9-15 所示,用于组选择和行匹配的索引和标记字段是从虚拟地址中的虚拟页号中提取出来的。如果 TLB 有$\small T = 2^t$个组,那么 TLB 索引(TLBI)是由 VPN 的 $t$ 个最低位组成的,而 TLB 标记(TLBT)是由 VPN 中剩余的位组成的。

Responsive Image

图 9-16a 展示了当 TLB 命中时(通常情况)所包括的步骤。这里的关键点是,所有的地址翻译步骤都是在芯片上的 MMU 中执行的,因此非常快。

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

Responsive Image

当 TLB 不命中时,MMU 必须从 L1 缓存中取出相应的 PTE,如图 9-16b 所示。新取出的 PTE 存放在 TLB 中,可能会覆盖一个已经存在的条目。

多级页表

32 位环境下,虚拟地址空间共 4GB。如果分成 4KB 一个页,那就是 1M 个页。每个页表项需要 4 个字节来存储,那么整个 4GB 空间的映射就需要 4MB 的内存来存储映射表。如果每个进程都有自己的映射表,100 个进程就需要 400MB 的内存。对于内核来讲,有点大了。

页表中所有页表项必须提前建好,并且要求是连续的。如果不连续,就没有办法通过虚拟地址里面的页号找到对应的页表项了。

那怎么办呢?我们可以试着将页表再分页,4G 的空间需要 4M 的页表来存储映射。我们把这 4M 分成 1K(1024)个 4K,每个 4K 又能放在一页里面,这样 1K 个 4K 就是 1K 个页,这 1K 个页也需要一个表进行管理,我们称为页目录表,这个页目录表里面有 1K 项,每项 4 个字节,页目录表大小也是 4K。

页目录有 1K 项,用 10 位就可以表示访问页目录的哪一项。这一项其实对应的是一整页的页表项,也即 4K 的页表项。每个页表项也是 4 个字节,因而一整页的页表项是 1K 个。再用 10 位就可以表示访问页表项的哪一项,页表项中的一项对应的就是一个页,是存放数据的页,这个页的大小是 4K,用 12 位可以定位这个页内的任何一个位置。

这样加起来正好 32 位,也就是用前 10 位定位到页目录表中的一项。将这一项对应的页表取出来共 1k 项,再用中间 10 位定位到页表中的一项,将这一项对应的存放数据的页取出来,再用最后 12 位定位到页中的具体位置访问数据。

Responsive Image

你可能会问,如果这样的话,映射 4GB 地址空间就需要 4MB+4KB 的内存,这样不是更大 了吗?当然如果页是满的,当时是更大了,但是,我们往往不会为一个进程分配那么多内 存。 比如说,上面图中,我们假设只给这个进程分配了一个数据页。如果只使用页表,也需要完 整的 1M 个页表项共 4M 的内存,但是如果使用了页目录,页目录需要 1K 个全部分配,占用内存 4K,但是里面只有一项使用了。到了页表项,只需要分配能够管理那个数据页的页表项页就可以了,也就是说,最多 4K,这样内存就节省多了

当然对于 64 位的系统,两级肯定不够了,就变成了四级目录,分别是全局页目录项 PGD(Page Global Directory)、上层页目录项 PUD(Page Upper Directory)、中间 页目录项 PMD(Page Middle Directory)和页表项 PTE(Page Table Entry)。也就是一级页表,二级页表,三级页表,四级页表。

Responsive Image