"> "> 操作系统-内存虚拟化 | Yufei Luo's Blog

Yufei Luo's Blog

But I was so much older then, I am younger than that now.

Yufei Luo's Blog

操作系统-内存虚拟化

发表于 更新于 分类于 ， 阅读次数：
本文字数： 15k 阅读时长 ≈ 13 分钟

地址空间与地址转换

内存虚拟化与虚拟地址空间

一个操作系统内部同时运行着多个进程，这些进程之间采用时分共享的方式来使用硬件。对于CPU来说，时分共享是通过让一个进程全部占用CPU运行一段时间，在进程切换的时候通过上下文切换来完成；但是对于内存来说，如果采用这种方式，在进程切换的时候需要将物理内存中当前所有的内容保存到磁盘中去，并从磁盘中读取另一个进程的物理内存数据到物理内存中。根据计算机组成原理的知识，磁盘与物理内存之间的数据传输是很慢的。因此，操作系统的做法是在进程切换的时候仍然将进程信息放在物理内存中，也就意味着许多程序在同一时刻共享着物理内存。

但是这种做法又对操作系统有了新的要求，人们不希望一个进程可以读取甚至修改其他进程使用的物理内存。因此，操作系统使用了虚拟内存（Virtual Memory）的概念，对物理内存进行了抽象，通过这种抽象所形成的地址集合被叫做虚拟地址空间（Virtual Address Space）。相应地，一个物理内存所对应的地址集合被称为物理地址空间。一个进程的虚拟地址空间是运行中的程序看到的系统中的内存，它包含了这个程序的所有内存状态，包括程序代码、栈、堆等部分。为了给进程提供保护，每个进程都有着自己独立的虚拟地址空间，但是不同进程的虚拟内存可能会共享使用部分物理内存，从而实现数据共享。

虚拟内存主要实现了如下几个目标：

  • 透明：程序不会感知到物理内存被虚拟化的现实，相反程序的行为好像它拥有自己的私有物理内存。这是通过操作系统与硬件在幕后完成了这些工作，让不同的工作能够复用物理内存来实现的。
  • 效率：操作系统在实现虚拟化时，不会使程序运行地更慢，也不会需要太多额外的物理内存支持。为了实现高效率的虚拟化，操作系统将会依靠一些硬件支持。
  • 保护：操作系统会确保进程受到保护，不会受到其他进程的影响，同时操作系统本身也不会受进程的影响。这相当于给进程提供了隔离的特性，使得每个进程在自己的独立环境中运行。
  • 简化内存使用：独立的虚拟地址空间允许每个进程的虚拟内存使用相同的基本格式，而不管代码和数据实际存放在物理内存的何处；同时，独立的虚拟地址空间为操作系统提供了一个管理用户进程和操作系统自身之间共享的统一机制；而且物理内存的分配与加载数据也变得简单。

地址转换

为了实现物理内存的虚拟化，需要硬件和操作系统的同时支持。基于硬件的地址转换技术使得程序可以通过任何方式访问它自己的虚拟地址空间。利用地址转换，硬件对每次物理内存访问（指令读取、数据读取、数据写入）进行处理，将指令中的虚拟地址转换为实际存储的物理地址。同时，操作系统对物理内存进行管理，记录被占用和空闲的物理内存位置，并保持对物理内存使用的控制。

CPU中的内存管理单元MMU（Memory Management Unit）可以实现从虚拟地址到物理地址的转换。对于一个使用虚拟地址的系统，它从物理内存中读取数据的过程可以大致表示为下图所示的过程：

image-20201103211021984

动态重定位

操作方法

一个简单的地址转换思想是采用动态重定位技术，这一技术又被称为基址加界限机制。具体来说，为了实现这一机制，每个CPU需要两个硬件寄存器：基址（base）寄存器和界限（bound）寄存器，这一组寄存器使得我们能够把进程的虚拟地址空间放在物理内存的任何位置，同时又能确保进程只能访问自己的虚拟地址空间。通过这种方式，虚拟地址和物理地址便可以根据如下方式来进行对应： \[ \text{Physical Address = Virtual Address + Base} \] 进程中使用的内存引用都是使用虚拟地址，硬件会将虚拟地址加上基址寄存器中的内容，得到物理地址，再发给内存系统（注：汇编代码中的地址是虚拟地址！）。同时界限寄存器对这一过程提供访问保护，当进程要访问的物理地址大于界限寄存器中的地址，CPU将会触发异常。

值得注意的是，这种技术有着空间效率低下的问题。因为这种方式需要将进程的虚拟地址空间完整地加载到物理内存中去，但是虚拟地址空间中常常存在着大量的未使用区域，比如进程的堆区和栈区之间可能有着大块未使用的空间；而且，虚拟地址空间可能会大于物理地址空间，无法被完全载入物理内存。因此我们需要对这种方案做出一些改进，以便更好地利用物理内存。

硬件支持

动态重定位所需的硬件支持可以总结为下表：

硬件要求 解释
特权模式 用户模式的进程需要执行一些特权操作
基址/界限寄存器 每个CPU需要一对寄存器来支持地址转换和界限检查
转换虚拟地址并检查是否越界 使用电路来完成转换和检查界限
修改基址/界限寄存器的特权指令 在让用户程序运行之前，操作系统必须将这些值设置好
注册异常处理程序的特权指令 操作系统需要告诉硬件，如果异常发生时执行哪些代码
能够触发异常 当进程试图使用特权指令或越界的内存时需要触发异常

操作系统支持

为了支持动态重定位，操作系统也要提供如下的支持：

  • 进程创建时操作系统必须采取行动，为进程的虚拟地址空间找到物理内存空间来保存；
  • 在进程终止时，操作系统需要回收它使用的所有物理内存，给其他的进程或是操作系统使用；
  • 在上下文切换时，操作系统需要保存和恢复基址和界限寄存器。这也使得当一个进程暂停时，操作系统可以很容易地修改其虚拟地址空间的物理位置；
  • 操作系统需要提供异常处理程序，或一些要调用的函数。

分段

## 引言

分段最初的概念是通过在MMU中引入不止一对基址/界限寄存器对，给虚拟地址空间内的每个逻辑段一对。通过这种方式，操作系统能够将不同的段放到不同的物理内存区域，从而避免虚拟地址空间中的未使用部分占用物理内存。

C语言中的段错误：在支持分段的机器上发生了非法的内存访问（即使在不支持分段的机器上也仍然沿用这一术语）。

实现

使用分段机制，硬件在地址转换的时候需要考虑如下问题：

  • 引用哪个段：硬件在地址转换时需要知道地址引用的是哪个段，以及段内的偏移量。一种方式是使用显式方式，使用虚拟地址的开头几位来标识不同的段，后面几位来表示段内偏移量；另一种是隐式方法，硬件通过地址产生的方式来确定段，如地址由程序计数器产生则地址在代码段等。
  • 栈的处理：栈在使用过程中是反向增长的，也就是在栈中添加数据时栈顶的地址会减小。为了实现这一功能，硬件记录了每个段的增长方向，同时也相应地实现了反方向地址增长的处理方法。
  • 支持共享：不同的进程之间可能会共享其虚拟地址空间中的一些段，比如代码共享。为了支持共享，硬件为每个段增加了几个位，用于标识程序能否读写或执行其中的内容。同时这也要求硬件检查特定的访问是否允许。
  • 段的粒度：粗粒度的分段只将虚拟地址空间分为较大的、粗粒度的块；而在细粒度分段时，允许将虚拟地址空间划分为大量较小的段，而这种分段方式需要进一步的硬件支持，并在物理内存中保存某种段表。
  • 操作系统的支持：操作系统需要确保上下文切换时，各个段寄存器中的内容被保存和恢复；同时也需要有一些算法来管理物理内存的空闲空间。这是因为操作系统需要在物理内存中为每个段寻找空间，由于段的大小很可能不同，因此物理内存很快充满许多空闲空间的小洞，很难再分配给新的段或是扩大已有的段，这种问题也被称为外部碎片问题。相对应地，一个已分配单元（例如一个段）内部出现的类似问题被称为内部碎片问题，这种情况在堆的内部会经常出现。这一问题将在后面进行讨论。

分页

引言

由于分段的方法会造成物理地址空间的碎片化，随着时间的推移，分配物理内存会变得更加困难。因此，人们提出了分页的方法。分页是将一个进程的虚拟地址空间分割为若干个固定大小的单元，每个单元称为一页。相应地，也将物理内存看成是定长槽块的阵列，叫做页帧，每个页帧包含一个虚拟内存页。

注意：在下面的讨论中我们先暂时假设物理内存足够大，后面会提到如何应对物理内存空间不足的问题。

地址转换

对于一个虚拟地址，如果要将其转换为物理地址，我们需要将虚拟地址从左至右分为两部分：虚拟页面号（Virtual page number, VPN）和页内的偏移量（offset）。然后，根据页的大小，便可以确定offset所占的字节数，进而确定VPN所占的字节数。通过虚拟页号，我们可以找到这个虚拟页在物理内存中所对应的物理帧号（PFN，有时也成为物理页号PPN），同时保持偏移量不变，即可将虚拟地址转换为物理地址。需要注意，VPN和PFN所对应的字节数不一定相等。这一过程如下图所示：

image-20201101185821278

页表

为了记录虚拟地址空间的每个虚拟页放在物理内存中的位置，操作系统通常为每个进程保存了一个数据结构，称为页表（注意：每个进程有自己独自的页表）。页表的主要作用是为虚拟地址空间的每个虚拟页面保存地址转换，从而让我们知道每个页在物理内存中的位置。

页表中元素被称为页表项（PTE），一个PTE通常包含如下的内容：

  • 有效位（Valid bit）：指示这一页表项对应的地址转换是否有效。有效位对于支持稀疏的虚拟地址空间至关重要。
  • 保护位（Protection bit）：表明页是否可以读取、写入或执行。
  • 存在位（Present bit）：表示该页在物理存储器还是磁盘上。这使得操作系统可以支持大于物理内存的虚拟地址空间（参见页错误一节）。
  • 脏位（Dirty bit）：表明页面被带入物理内存后是否被修改过（用途参见下文的近似LRU一节）。
  • 参考位（Reference bit）：又称为访问位，用于追踪页是否被访问。这在页面替换时非常重要（参见下文的近似LRU一节）。

在x86架构中，一个页表项的示例图如下：

image-20201101192142649

图中P表示存在位，R/W表示读写位，U/S表示用户模式进程是否可以访问该页面的用户/超级用户位，A表示访问位，D表示脏位，PWT、PCD、PAT和G确定硬件缓存如何为这些页面工作，PFN为页帧号。同时根据页表项也可推断出一个页面的大小为\(2^{12}\text{Byte}=4\text{KB}\)。

使用页表之后，地址转换的过程如下图所示：

image-20201103232245909

优缺点

分页的方法具有许多优点。首先是灵活性，通过完善的分页方法，不管进程如何使用虚拟地址空间，操作系统都可以高效地提供虚拟地址空间的抽象；另一个优点是分页也使得空闲空间的管理变得更加简单。

通过对页表原理的分析，我们也能够发现分页机制的一些缺点。首先是页表项需要占用大量的空间。以上述的页表项为例，如果每个进程使用32位的虚拟地址空间，那么操作系统需要为每个进程管理\(2^{20}\)个地址转换，对应于每个进程需要维护\(4\times 2^{20}\text{Byte}=4\text{MB}\)大小的页表。考虑到一个操作系统内部通常有许多进程，而且在64位的操作系统中按照这种方式所构造的页表所占用的空间将会比32位的虚拟地址空间大出几个数量级，因此页表会存储在虚拟内存当中，甚至可以交换到磁盘上。

另外一个缺点是会让速度变慢。进程在读取数据时，操作系统需要将虚拟地址转换成物理地址，这需要首先从页表中获取地址转换，造成了额外的内存引用开销。

加速：快速地址转换

机制

为了加速虚拟地址转换，在硬件中增加了地址转换旁路缓冲存储器（Translation-lookaside buffer, TLB），作为频繁发生的虚拟地址到物理地址转换的硬件缓存。

在使用TLB之后，每次内存访问的过程如下：首先从虚拟地址中提取页号VPN，然后检查TLB，看其中是否有期望的转换映射。如果TLB命中，则可以从相关的TLB项中取出页帧号PFN，与虚拟地址中的偏移量组合形成期望的物理地址并访问物理内存，不需要访问页表；如果没有，那么硬件访问页表来寻找转换映射，并用该转换映射更新TLB（这一过程开销很大，需要额外的内存引用），并在更新完成之后重新执行内存访问指令。

因此，TLB的原理类似于其他的缓存，它对运行速度的提升依赖于程序的空间和时间局部性。

需要注意的是，TLB也存在一些问题。第一个问题是TLB无法满足所有的程序需求，如果当一个程序在短时间内访问的页数超过了TLB中的页数则会产生大量的未命中，导致运行速度变慢，这种现象被称为超出TLB覆盖范围。另一个问题是访问TLB容易成为CPU流水线的瓶颈，尤其是使用物理地址索引缓存。

未命中处理

对于TLB未命中之后的操作，可以由硬件或是软件来处理。

如果交给硬件处理，硬件需要知道页表在物理内存中的确切位置（通过页表基址寄存器）以及页表的确切格式。在发生TLB未命中时，硬件会遍历页表，找出正确的页表项并取出所需的转换映射，用于更新TLB，并重试该指令。

如果使用软件处理，在TLB未命中时将会跳转至陷阱处理程序，进入内核态来处理TLB未命中。这段操作系统的代码会查找页表中的转换映射，然后使用特权指令来更新TLB，并从陷阱中返回。注意此时返回用户态之后，仍需要执行导致陷阱的那条指令，这要求系统在进入内核态时保存相应的程序计数器。同时也要注意，在运行TLB未命中的代码时，操作系统需要避免引起TLB未命中的无限递归（也就是读取TLB未命中的代码时又引起了TLB不命中）。为了解决这一问题，可以将TLB未命中的陷阱处理程序直接放到物理内存中，或是在TLB中保存一些永久有效的地址转换。使用软件管理的方法比较灵活，可以用任意的数据结构实现页表；同时也比较简单，硬件不需要为未命中做太多的操作。

使用TLB之后，TLB命中与不命中的操作大致如下图所示：

image-20201103233443092

TLB的内容

典型的TLB有32、64或128项，并且是全相联的，这意味着一条地址映射可能存储在TLB的任何位置。硬件会并行地查找TLB，找到期望的转换映射。

一条TLB项的内容可能为：VPN|PFN|其他位

其中VPN和PFN同时存在于TLB中，这是因为一条地址映射可能会出现在任何位置。在其他位中也包含了一些有用的信息，比如用于标识转换映射是否有效的有效位，用来标识访问权限的保护位，以及一些其他的信息。

注意：TLB的有效位与页表的有效位不等价！在页表中，页表项被标记为无效意味着它对应的页没有被使用，如果试图访问会引起异常，操作系统将会杀掉这一进程；而在TLB中，有效位指出的是这一项是否为有效的地址映射。

上下文切换时TLB的处理

由于TLB中包含的每一条映射关系对于一些进程来说是没有意义的，因此在发生进程切换时，硬件和操作系统需要确保进程不会误读地址映射。一些解决方案如下：

  • 在上下文切换时清空TLB（把全部的有效位置0）。这样使得进程不会读取到错误的地址映射，但是使用这种方法的话，每次进程切换完毕开始运行的时候一定会触发TLB不命中。如果操作系统频繁的切换进程则会带来很大的开销。
  • 跨上下文切换的TLB共享。这种方法需要硬件支持，为TLB中的表项添加了一个虚拟地址空间标识符（ASID），它类似于进程标识符。通过这种方法，TLB便可以缓存不同进程的虚拟地址空间映射，不会形成冲突。

TLB的替换策略

常用的TLB替换策略包括替换最近最少使用（Least recently used, LRU）的项、随机替换等。LRU策略可以利用内存引用流中的局部性；而随机策略则避免了LRU可能会出现的一种极端情况，即程序循环访问n+1个页但是TLB只能存储n个页。

减少空间占用：缩小页表

对于线性页表来说，它所需的空间太大，因此会在系统中消耗大量内存，给系统带来很大的空间负担。有一些办法可以让页表变得更小。

更大的页

使用更大的页是一种简单的缩小页表的办法。但是这种方法会很容易导致每页内的浪费，形成内部碎片问题。结果会造成应用程序分配页，但是却只使用了每一页的一小部分，物理内存便会很快地充满这些过大的页。因此，大多数系统通常使用相对较小的页大小，如x86为4KB。

分页与分段结合

在一个进程的虚拟地址空间中，可能会有堆和栈使用部分很小的情况。这时便会有大量的分页表没有被使用，充满了无效项，而在页表中保存这些无效项显然是没有意义的。

将分页与分段结合的办法是为每个逻辑分段提供一个单独的页表，同时使用基址寄存器保存段的页表的物理地址，使用界限寄存器指示页表的结尾。此时，虚拟地址空间的格式变为：Segment|VPN|Offset，在TLB未命中时也需要硬件使用分段位来确定使用哪一个基址和界限对。

通过这种方式，在栈和堆之间未分配的页将不再占用页表中的空间。但是这种方式也存在一些问题，使用分段的时候对虚拟地址空间有一定的使用模式要求，如果使用大而稀疏的堆仍然会导致大量的页表浪费；由于页表变为任意大小也会导致外部碎片。

多级页表

在x86系统中，使用的是多级页表的方法。多级页表将线性页表变成了类似于树的结构：树的每一个叶结点都对应了一个页表项，如果某一页的页表项无效则不分配页表，相当于没有叶结点；每个叶结点的父结点是一个被称为页目录的结构，页目录用于保存页表的存放位置（相当于存放指向页表的指针，如果对应的页没有使用则为空）。一个页目录可以覆盖所有的虚拟地址空间，也可以覆盖一部分虚拟地址空间，通过这种方式形成了多级页表的结构。

下图所示的是一个二级页表的结构：

image-20201101233633914

在使用多级页表时，虚拟地址与页表的对应关系如下图所示：

image-20201101234734378

使用多级页表的优缺点如下：

  • 优点：
    • 多级页表分配的页表空间与虚拟地址空间的使用量成正比，因此它通常很紧凑，并且支持稀疏的虚拟地址空间。
    • 如果仔细地去构造多级页表，可以将页表的每个部分都能够整齐地放入一页中，从而更容易管理物理内存。
    • 页表的树形结构使得它可以存放在物理内存的任何地方。
  • 缺点：
    • 造成了时间上的额外开销，在TLB未命中时需要从物理内存加载多次才能获取正确的地址转换信息（先加载页目录，一直到最底层的PTE本身）。
    • 比较复杂，在硬件或是操作系统的实现上都比线性页表更复杂一些。

将页表放入磁盘

由于页表可能太大无法一次装入物理内存，因此操作系统会将页表存放在内核虚拟内存中，从而允许系统在物理内存压力较大的时候，将页表中的一部分交换到磁盘中去。

超越物理空间

引言

操作系统常常为一个进程创造一个巨大的虚拟地址空间，从而使得人们在写程序的时候，不必担心程序的数据结构是否有充足的空间去存储，这是操作系统提供的一个强大的假象。但是这样便会出现虚拟地址空间大于实际物理地址空间的情况（比如在一个64位的计算机上有很大的可能性会这样）。而且，一个操作系统内部有多个正在运行的进程，操作系统需要同时为它们提供巨大地址空间的假象。

这就要求操作系统提供支持，能够从物理内存中换出一些当前没有使用的页并将他们妥善保存。具体来说，操作系统会使用硬盘来保存虚拟内存页，并在需要的时候从硬盘中读取，这也就相当于是将物理内存作为了硬盘的缓存。

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

  • 未分配的：虚拟内存系统还没有分配或者创建的页。未分配的块中没有任何数据，因此也不占用任何磁盘空间；
  • 缓存的：当前已缓存在物理内存中的已分配页；
  • 未缓存的：未缓存在物理内存中的已分配页。

一个进程的虚拟内存和物理内存的关系如下图所示：

image-20201103221844357

交换空间

操作系统使用了硬盘上的一部分空间，用于物理页的移入与移出，这样的空间被称为交换空间（swap space）。交换空间的大小设置很重要，这决定了系统在某个时刻可以使用的最大物理内存页数。

为了能够让操作系统读取或写入交换空间，操作系统需要记住给定页的磁盘地址。操作系统通过使用PTE中的某些位（比如存储页的PFN的这些位，因为存储在硬盘中时没有对应的物理页）来存储硬盘数据。在需要引用这一页时，操作系统便会在PTE中查找硬盘中的存储位置，并向硬盘发送请求来将数据读取到物理内存中去。

但是需要注意的是，交换空间并不是唯一的硬盘交换目的地。例如运行一个二进制程序，这个二进制程序的代码页原本位于硬盘上，在运行时被加载到物理内存中，当系统需要在物理内存中腾出空间满足其他操作时，便可以安全的直接覆盖掉代码页使用的物理内存空间，在重新运行的时候仍然从原来的位置加载该程序。

页错误

概念

在使用交换空间之后，物理内存引用的过程也会发生一些变化。当出现TLB未命中时，此时便可能出现页表位于硬盘上的情况。判断要引用的页是否位于物理内存中，需要使用到页表项中的存在位（参见上文的页表一节），如果存在位为1则表示该页在物理内存中，存在位为0则表示在硬盘上。访问不在物理内存中的页通常被称为页错误。

无论是硬件管理TLB还是软件管理TLB，页错误的处理都是由操作系统负责的。这是因为页错误导致的硬盘操作很慢，同时处理页故障时需要知道很多细节。

处理流程

操作系统在接收到页错误之后，首先需要为将要换入的页找到一个空闲的物理帧，如果没有这样的物理帧，则需要运行交换算法，将物理内存中的一些页保存到硬盘上并释放掉。之后，操作系统会从PTE中查找硬盘地址，并向硬盘发出I/O请求，将该页读取到物理内存。当硬盘I/O操作完成之后，操作系统便会更新页表，将此页标记为存在，更新页表项的PFN字段以记录页的物理内存位置，然后重试指令。重试会导致TLB未命中，然后再一次尝试时TLB命中，硬件能够访问所需的值。

由于物理内存与硬盘的I/O操作的时间代价是昂贵的，因此当I/O运行时，进程将处于阻塞状态。当页错误正常处理时，操作系统可以自由运行其他可执行的进程，从而充分地利用硬件。

页交换

操作流程

当物理内存已满或是接近满的时候，操作系统便会交换出一个或多个页到硬盘上去，以便为操作系统即将换入的新页留出空间。操作系统通常会预留一小部分空闲的物理内存，为此操作系统会设置高水位线（High Watermark, HW）和低水位线（Low Watermark, LW）来决定何时从物理内存中清除页。当操作系统发现可用的页少于LW时，后台负责释放物理内存的线程便会开始运行，直到有HW个可用的物理页，这个后台线程被称为交换守护进程或页守护进程。

页交换的过程可以做一些优化，例如将多个要写入的页聚集或分组，将它们同时写入交换空间。这种合并操作减少了硬盘的寻道和旋转开销，从而提高了硬盘的效率。

替换策略

物理内存包含了系统中所有页的子集，因此可以将其看作是系统中虚拟内存页的缓存。由于磁盘访问的成本非常高，因此在替换物理内存页的时候，需要选用合适的替换策略，使得缓存未命中最少，从而使得从磁盘获取页的次数最少。

最优替换策略

这一策略替换物理内存中在最远将来才会被访问到的页，因此具有最低的缓存未命中率。但是这一策略是很难实现的，因此常常拿这一策略与其他的优化策略进行对比。

先入先出替换策略

这一策略的实现很简单，使用一个队列来放置所有进入系统的页，在替换页的时候按照先入先出的策略进行替换。这一策略无法确定页的重要性，因此明显不如最优策略。

随机替换策略

这种策略在物理内存满的时候随机选择一个页进行替换。这种策略的实现简单，但是性能表现完全取决于运气。

基于历史数据的策略

由于程序的局部性原理，页的一个重要属性便是访问的近期性，越近被访问的页再次被访问的概率也越大。因此页替换策略可以使用访问频率这一历史信息，比如最不经常使用（LFU）策略会替换掉最不经常使用的页，最少最近使用（LRU）策略替换最近最少使用的页面。

但是为了实现这种策略，系统需要对每次页访问都记录一个对应的时间字段，在需要替换页时便可以扫描系统中所有页的时间字段以找到最近最少使用的页。随着系统中页数量的增长，这一操作将会付出很高的时间代价。

近似LRU

从计算开销的角度来看，许多现代系统都使用了近似LRU的做法，其中一个简单的方法被称作时钟算法，为了实现这一算法需要使用一个使用位（Use bit，也可以被称为参考位，Reference bit）。这一算法将系统中的所有页放入一个循环列表中，时钟指针开始时指向某个页。当必须进行页替换时，操作系统检查当前指向的页P的使用位，如果是1则表明页面P最近被使用，操作系统将其置为0然后将时钟指针递增；如果是0则表明页面P最近没有被使用过，可以被替换掉。

时钟算法的一个改进是额外考虑了物理内存中的页是否被修改。如果页已经被修改，踢出它时需要将其写回磁盘；而如果没有被修改则踢出时无需额外的I/O开销。因此一些系统会倾向于踢出干净页，为了支持这种行为，需要使用到一个脏位（dirty bit，又叫修改位，modified bit），每次写入页面的时候都要设置此位。通过这种方式，时钟算法可以修改成先踢出未被使用又干净的页，无法找到这种页时再找脏的未使用页面，或是一些其他的策略。

其他使用策略

为了提高页交换的效率，除了页面替换策略之外，操作系统还为虚拟内存子系统设置了一些其他策略，例如：

  • 页选择策略：操作系统决定何时将页载入物理内存。对于大多数页而言，操作系统只需要按需分页，在页被访问的时候载入即可。由于程序具有局部性，操作系统可能会猜测一个页面即将被使用，从而提前载入，这种行为被称为预取（prefetching）。
  • 写入策略：因为硬盘驱动器在执行单次大的写操作比许多小的写操作要有效，因此操作系统可能会在物理内存中收集一些待完成的写入内容，然后将它们以更高效的方式写入硬盘。这种行为被称为聚集写入或分组写入。

抖动

当物理内存被超额请求时，也就是进程的物理内存需求超过了可用物理内存（内存过载），系统将不断地进行换页，这种情况被称为抖动。

操作系统可以使用准入控制的方法来应对抖动，也就是系统不运行部分进程，这样能够使得进程工作集减少，它们活跃的页面可以放入物理内存。

一些系统也使用更严格的方法来处理物理内存过载。比如一些版本的Linux有一个守护进程，它会在内存过载的时候选择一个内存密集型的进程并杀死它。但是这种方法存在一定风险，可能会杀掉关键的进程。

实际案例

Core i7的地址翻译

一个Core i7处理器的内存系统如下图所示：

image-20201103233705149

在这一处理器中，实现支持48位的虚拟地址空间和52位的物理地址空间。

备注：在使用计算机时，其最大支持的内存是由操作系统和硬件两方面决定的。

CPU的地址总线数目决定了物理地址的寻址范围，比如32根地址总线的CPU就只能支持\(2^{32}\approx 4\text{GB}\)的物理地址范围（注意平时所说的32位和64位CPU指的是CPU能够一次处理的数据宽度，而不是地址总线的数目）。而64位CPU一般具有更多的地址总线，因此支持的物理地址范围也更大。

操作系统决定了逻辑地址（即虚拟地址）的寻址范围。因此，对于32位的操作系统，它逻辑地址的寻址范围是4GB。而对于64位操作系统，它支持的逻辑地址空间更大，例如Linux 64位系统使用的是48位的逻辑地址空间。

处理器中的地址翻译流程如下图所示，其中省略掉了i-cache（指令缓存）、i-TLB、L2、L3级缓存和统一TLB：

image-20201103233915879

Linux内存系统

在Linux系统中，虚拟内存中的内容大致如下图所示：

image-20201103235156839

Linux为每一个进程都维护了一个像上图所示单独的虚拟地址空间。其中主要包括内核虚拟内存和进程虚拟内存两部分。

内核虚拟内存与进程虚拟内存

内核虚拟内存包含内核中的代码和数据结构，其中内核虚拟内存的某些区域被映射到所有进程共享的物理页面。比如每个进程共享内核的代码和全局数据结构。其中值得注意的是，Linux 也将一组连续的虚拟页面(大小等于系统中DRAM 的总量）映射到相应的一组连续的物理页面。这就为内核提供了一种便利的方法来访问物理内存中任何特定的位置：例如，当它需要访问页表，或在一些设备上执行内存映射的I/O操作，而这些设备被映射到特定的物理内存位置时。

内核虚拟内存的其他区域包含每个进程都不相同的数据。比如说，页表、内核在进程的上下文中执行代码时使用的找，以及记录虚拟地址空间当前组织的各种数据结构。

进程虚拟内存中主要存放的是该进程对应的代码、数据、堆、共享库以及栈段。

虚拟内存区域

Linux 将虚拟内存组织成一些区域（也叫做段）的集合。一个区域就是已分配的虚拟内存的连续片，这些页是以某种方式相关联的。例如，代码段、数据段、堆、共享库段，以及用户栈都是不同的区域。

也就是说，Linux系统在管理虚拟内存时，使用的是段页结合的方式。

内存映射

Linux 通过将一个虚拟内存区域与一个磁盘上的对象（object）关联起来，以初始化这个虚拟内存区域的内容，这个过程称为内存映射（memory mapping）。

虚拟内存区域可以映射到以下两种类型的对象之一：

  1. 文件系统中的普通文件。
  2. 匿名文件：由内核创建的，内容全为二进制0。

一个对象可以被映射到虚拟内存的一个区域，要么作为共享对象，要么作为私有对象。如果一个进程将一个共享对象映射到它的虚拟地址空间的一个区域内，那么这个进程对这个区域的任何写操作，对于那些也把这个共享对象映射到它们虚拟内存的其他进程而言，也是可见的。而且，这些变化也会反映在磁盘上的原始对象中。一个映射到共享对象的虚拟内存区域叫做共享区域。

另一方面，对于一个映射到私有对象的区域做的改变，对于其他进程来说是不可见的，并且进程对这个区域所做的任何写操作都不会反映在磁盘上的对象中。映射到私有对象的区域叫做私有区域。但是需要注意的是，两个进程将一个私有对象映射到它们虚拟内存的不同区域，但是共享这个对象同一个物理副本。在物理内存中这一区域结构被标记为私有的写时复制，页表条目被标记为只读。只要没有进程试图写它自己的私有区域，它们就可以继续共享物理内存中对象的一个单独副本。然而，只要有一个进程试图写私有区域内的某个页面，那么这个写操作就会触发一个保护故障，在物理内存中创建这个页面的一个新副本，更新页表条目指向这个新的副本，然后恢复这个页面的可写权限。这一过程如下图所示：

image-20201104002631085

内存使用

内存类型

在C程序中有两种不同类型的内存：

  • 栈内存：它的申请和释放操作通过编译器隐式管理，又被称为自动内存。
  • 堆内存：它的申请和释放操作都由程序员显式完成。

堆内存的使用

库调用

在C语言中，内存操作使用的是内存分配库，而不是系统调用。它是建立在一些系统调用之上的，这些系统调用会进入操作系统来请求内存或是释放内存。

常用的库函数有：

  • malloc()函数：用于申请堆内存。函数的输入参数是一个size_t类型的参数，表示需要申请多少字节的堆内存。如果成功就返回一个指向新申请空间的指针（类型为void），失败则返回NULL。
  • calloc()函数：与malloc函数类似，在返回之前将申请到的内存空间中的内容初始化为0。
  • free()函数：用于释放之前申请的堆内存。函数的输入参数是一个由malloc()返回的指针。在释放空间时，程序员不用考虑分配的堆内存的大小，它是由内存分配库本身记录与追踪的。
  • realloc()函数：创建一个新的更大的内存区域，将旧区域复制到其中，并返回新区域的指针。

常见错误

  • 忘记分配内存。一些例程在调用之前默认已经将内存空间分配好，如函数strcpy(dst, src)
  • 没有分配足够的内存，又叫缓冲区溢出。这可能会导致其他的变量被修改，带来严重的后果，也是安全漏洞的来源。
  • 忘记初始化分配的内存。如果没有初始化这块内存区域，程序在读取其内容时会得到一些未知值的数据，这些数据可能是有害的。
  • 忘记释放内存。这种错误被称为内存泄漏，在长时间运行的应用程序或系统中，这会导致内存不足。但是对于一些运行时间很短的程序，由于进程结束之后操作系统会清理掉为它分配的所有页面，所以不会发生内存泄漏。
  • 在用完之前释放内存。这样会导致之前使用malloc()函数得到的指针变为悬挂指针，随后再次使用时可能会导致程序崩溃，或是覆盖掉有效内存。
  • 反复释放内存。这种行为是未定义的，会使得内存分配库做出未知的行为，可能造成崩溃。
  • 错误地调用free()。free()函数只期望传入malloc()函数得到的指针，传入一些其他的值属于危险操作。

空闲空间管理

无论是malloc()库还是操作系统本身，都会遇到碎片处理问题，因此我们最后讨论一些关于空闲空间如何管理的知识。在下面的讨论中，我们假设分配程序管理的是连续的字节区域，而且内存一旦被分配就不能被重定位到其他位置。

底层机制

空闲列表

空闲空间的管理通常是通过空闲列表来实现的。空闲列表包含了一组元素，记录堆中的哪些连续的地址空间还没有分配。其中，每个元素包含了空闲空间的起始位置与大小。

空闲列表是在空闲空间的内部建立的，具体是在每个空闲空间的头部放入一些信息，记录这个空闲块的大小以及下一个空闲块的指针。因此，一个空闲块的内部大致如下图所示：

image-20201101164740664

分割与合并

在申请空间时，假如要申请的空间大小比一个空闲块的空间要小，则分配程序会执行分割动作，将空闲块分成两份：一份返回给用户使用；另一份留在空闲列表中，同时修改对应的起始地址以及块长度信息。

如果用户归还了一个空间，需要将这块空间插入到空闲列表中，并查看其邻近的空闲空间块是否可以合并。如果可以，就将几个小空间合并为一个大空间。

追踪已分配空间的大小

在调用free()函数时，并没有传入块大小的参数，这是因为大多数的分配程序都会使用头块来保存一些额外信息。头块通常位于分配的内存块之前，包含了分配空间的大小、用于完整性检查的幻数、用于加速空间释放的额外指针等信息。因此，在释放块的空间时，实际上释放的是头块大小加上分配给用户的空间大小。一个已分配区域与头块所构成的大致结构如下图所示：

image-20201101154639000

让堆增长

分配程序会从一个很小的堆开始使用，当堆的虚拟内存空间耗尽时，再向操作系统申请更大的空间。这一过程需要进行系统调用，操作系统会找到空闲的物理内存页，将它们映射到请求进程的虚拟地址空间中去，并返回新的堆尾地址。这样便有了更大的堆，可以处理新的空间请求。

空间分配策略

用户在申请一个空间之后，分配程序便选择合适的空闲空间分配给用户。一些常用的分配策略如下：

  • 最优匹配：遍历整个空闲列表，找到和请求大小一样或者更大的空闲块，然后返回这组候选者中最小的一块。这种方式可以避免空间浪费，但是付出的性能代价较高。
  • 最差匹配：尝试寻找最大的空闲块，分割并满足用户需求之后，将剩余的块加入空闲列表。这种方式会导致过量的碎片，同时还有很高的开销。
  • 首次匹配：找到第一个足够大的块，将请求的空间返回给用户。这种方法具有速度优势，但是会让空闲列表的开头出现很多小块。
  • 下次匹配：这种算法多维护一个指针，指向上一次查找结束的位置，然后下次从这个指针处开始搜索。这样就将查找操作扩散到整个列表中去，避免了对列表开头频繁的分割。这种匹配的性能与首次匹配接近，避免了遍历查找。
  • 分离空闲列表：如果一个应用程序经常申请一种或几种大小的内存空间，那就用一个独立的列表只管理这种大小的对象，对于其他大小的请求都交给更通用的内存分配程序。这样就避免了碎片的问题，同时特定大小的内存分配和释放都很快。
  • 伙伴系统：将空闲空间看作是大小为\(2^N\)的空间，当有一个内存分配请求时，将空闲空间递归地一分为二，直到刚好可以满足所请求的大小（再分下去就无法满足）。由于分配的空间只允许为2的幂指数大小，因此会有内部碎片的麻烦。但是这种方法在内存释放时，空闲块的合并很方便（每对互为伙伴的块在二进制地址中只有一位不同）

参考

  1. Operating Systems: Three Easy Pieces
  2. 深入理解计算机系统 第三版
  3. https://www.zhihu.com/question/276578129/answer/908341878
  4. https://blog.csdn.net/wagsyang/article/details/79234491
  5. https://blog.csdn.net/weixin_38972910/article/details/97631720
  6. https://zhuanlan.zhihu.com/p/73696670