内存虚拟化-超越物理内存 | 彩潭有鲤的札记

type

status

date

slug

summary

交换空间

要做的第一件事情就是，在硬盘上开辟一部分空间用于物理页的移入和移出。在操作系统中，一般这样的空间称为交换空间（swap space），将内存中的页交换到其中，并在需要的时候又交换回去。

假设操作系统能够以页大小为单元读取或者写入交换空间。为了达到这个目的，操作系统需要记住给定页的硬盘地址。

一个4 页的物理内存和一个8 页的交换空间：

3 个进程（进程0、进程1 和进程2）主动共享物理内存。但3 个中的每一个，都只有一部分有效页在内存中，剩下的在硬盘的交换空间中。第4 个进程（进程3）的所有页都被交换到硬盘上，因此很清楚它目前没有运行。有一块交换空间是空闲的。

注意，交换空间不是唯一的硬盘交换目的地。例如，假设运行一个二进制程序（自己编译的main 程序）。这个二进制程序的代码页最开始是在硬盘上，但程序运行的时候，它们被加载到内存中（要么在程序开始运行时全部加载，要么在现代操作系统中，按需要一页一页加载）。但是，如果系统需要在物理内存中腾出空间以满足其他需求，则可以安全地重新使用这些代码页的内存空间，因为稍后它又可以重新从硬盘上的二进制文件加载。

存在位

如果希望允许页交换到硬盘，硬件管理TLB 的系统必须添加更多的机制。

当硬件在PTE中查找时，可能发现页不在物理内存中。硬件（或操作系统，在软件管理TLB 时）判断是否在内存中的方法，是通过页表项中的一条新信息，即存在位（present bit）。如果存在位设置为1，则表示该页存在于物理内存中，并且所有内容都如上所述进行。如果存在位设置为零，则页不在内存中，而在硬盘上。访问不在物理内存中的页，这种行为通常被称为页错误（page fault）。

在页错误时，操作系统被唤起来处理页错误。一段称为“页错误处理程序（page-fault handler）”的代码会执行，来处理页错误。

在TLB 未命中的情况下，有两种类型的系统：硬件管理的TLB（硬件在页表中找到需要的转换映射）和软件管理的TLB（操作系统执行查找过程）。不论在哪种系统中，如果页不存在，都由操作系统负责处理页错误。操作系统的页错误处理程序确定要做什么。几乎所有的系统都在软件中处理页错误。即使是硬件管理的TLB，硬件也信任操作系统来管理这个重要的任务。

如果一个页不存在，它已被交换到硬盘，在处理页错误的时候，操作系统需要将该页交换到内存中。那么，操作系统如何知道所需的页在哪儿？在许多系统中，页表是存储这些信息最自然的地方。因此，操作系统可以用PTE 中的某些位来存储硬盘地址，这些位通常用来存储像页的PFN 这样的数据。当操作系统接收到页错误时，它会在PTE 中查找地址，并将请求发送到硬盘，将页读取到内存中。

当硬盘I/O 完成时，操作系统会更新页表，将此页标记为存在，更新页表项（PTE）的PFN 字段以记录新获取页的内存位置，并重试指令。下一次重新访问TLB 还是未命中，然而这次因为页在内存中，因此会将页表中的地址更新到TLB 中（也可以在处理页错误时更新TLB 以避免此步骤）。最后的重试操作会在TLB 中找到转换映射，从已转换的内存物理地址，获取所需的数据或指令。

注意，当I/O 在运行时，进程将处于阻塞状态。因此，当页错误正常处理时，操作系统可以自由地运行其他可执行的进程。因为I/O 操作是昂贵的，一个进程进行I/O（页错误）时会执行另一个进程，这种交叠是多道程序系统充分利用硬件的一种方式。

内存满了怎么办

在上述的过程中假设有足够的空闲内存来从存储交换空间换入（page in）的页。当然，情况可能并非如此。内存可能已满。因此，操作系统可能希望先交换出（page out）一个或多个页，以便为操作系统即将交换入的新页留出空间。选择哪些页被交换出或被替换（replace）的过程，被称为页交换策略（page-replacement policy）。

页错误处理流程

页错误控制流算法（硬件）

当 TLB 未命中时会有 3 种重要情景：

该页存在且有效。在这种情况下，TLB 未命中处理程序可以简单地从 PTE 中获取 PFN，然后重试指令（这次 TLB 会命中），并因此继续前面的流程。

页错误处理程序需要运行。虽然这是进程可以访问的合法页（毕竟是有效的），但是它并不在物理内存中。

访问的是一个无效页，可能由于程序中的错误导致。在这种情况下，PTE 中的其他位都不重要了。硬件捕获这个非法访问，操作系统陷阱处理程序运行，可能会杀死非法进程。

页错误控制流算法（软件）

首先，操作系统必须为将要换入的页找到一个物理帧，如果没有这样的物理帧，我们将不得不等待交换算法的运行，并从内存中踢出一些页，释放帧供这里使用。

在获得物理帧后，处理程序发出 I/O 请求从交换空间读取页。最后，当这个慢操作完成时，操作系统更新页表并重试指令。重试将导致 TLB 未命中，然后再一次重试时，TLB 命中，此时硬件将能够访问所需的值。

交换何时真正发生

为了保证有少量的空闲内存，大多数操作系统会设置高水位线（High Watermark，HW）和低水位线（Low Watermark，LW），来帮助决定何时从内存中清除页。

当操作系统发现有少于LW 个页可用时，后台负责释放内存的线程会开始运行，直到有HW个可用的物理页。这个后台线程有时称为交换守护进程（swap daemon）或页守护进程（page daemon）。通过同时执行多个交换过程，我们可以进行一些性能优化。例如，许多系统会把多个要写入的页聚集（cluster）或分组（group），同时写入到交换区间，从而提高硬盘的效率。

页面替换策略（replacement policy）

在虚拟内存管理程序中，如果拥有大量空闲内存，操作就会变得很容易。页错误发生了，在空闲页列表中找到空闲页，将它分配给不在内存中的页。

遗憾的是，当内存不够时，内存压力迫使操作系统换出一些页，为常用的页腾出空间。确定要踢出哪些页封装在操作系统的替换策略中。

缓存管理

由于内存只包含系统中所有页的子集，因此可以将其视为系统中虚拟内存页的缓存。在为这个缓存选择替换策略时，目标是让缓存未命中最少，即使得从磁盘获取页的次数最少。或者，可以将目标看成让缓存命中最多，即在内存中找到待访问页的次数最多。

知道了缓存命中和未命中的次数，就可以计算程序的平均内存访问时间（Average Memory Access Time，AMAT，计算机架构师衡量硬件缓存的指标），可以按照如下公式计算AMAT：

表示访问内存的成本，表示访问磁盘的成本，表示在缓存中找到数据的概率（命中)，表示在缓存中找不到数据的概率（末命中)。和从变化到，并且。

在现代系统中，磁盘访问的成本非常高，即使很小概率的未命中也会拉低正在运行的程序的总体AMAT。显然，必须尽可能地避免缓存未命中，避免程序以磁盘的速度运行。要做到这一点，有一种方法就是仔细开发一个聪明的策略

策略	解释	演化	缺点
MIN/OPT最优替换策略	替换掉最远的将来才会访问的项目	只是一个假设	无法决定哪个页在最远的将来才会访问，实际上根本无法实现
FIFO	替换掉最先进入的项目	直觉策略	缓存容量非常影响命中率，因为存在抖动（thrashing）现象
随机	随机替换掉一个项目	直觉策略	命中率也很随机
LRU(最近最少使用)	替换掉最长时间没有被使用的项目（使用一个计数器，每次访问项目计数器加1，替换时替换计数器值最低的项目）	考虑时间局部性	实现成本高，因为每次访问都要更改计数器
Approximating LRU（近似LRU）	将被访问的项目做标记（例如将页表项中的accessed bit置1），定期（例如每100ms）清除所有标记（accessed bit置0），替换掉首个没有标记的项目	降低实现成本	清理标记的周期参数影响命中率（但仍为主流实现）
考虑脏页的近似LRU(适用于交换)	在LRU的基础上优先选择干净的（即没有被修改过的）页来替换，修改过的页写回磁盘需要额外开销	考虑IO开销	与近似LRU类似

最优替换策略MIN/OPT

替换内存中在最远将来才会被访问到的页，可以达到缓存未命中率最低。

假设一个程序按照以下顺序访问虚拟页：0，1，2，0，1，3，0，3，1，2，1，缓存可以存3个页。

前3个访问是未命中，因为缓存开始是空的。这种未命中有时也称作冷启动未命中（cold-start miss，或强制未命中，compulsory miss）。页2在最远的将来被访问，最优策略的选择踢出页面2。

计算缓存命中率：有6次命中和5次末命中，缓存命中率是，也可以计算命中率中除去强制末命中为。

简单策略：FIFO

许多早期的系统避免了尝试达到最优的复杂性，采用了非常简单的替换策略。例如，一些系统使用FIFO（先入先出）替换策略。页在进入系统时，简单地放入一个队列。当发生替换时，队列尾部的页（“先入”页）被踢出。FIFO 有一个很大的优势：实现简单。

先进先出（FIFO）根本无法确定页的重要性：即使页0已被多次访问，FIFO 仍然会将其踢出，因为它是第一个进入内存的。

另一简单策略：随机

在内存满的时候它随机选择一个页进行替换。随机具有类似于FIFO 的属性。实现我来很简单，但是它在挑选替换哪个页时不够智能。

利用历史数据：LRU

使用的一个历史信息是频率（frequency）。如果一个页被访问了很多次，也许它不应该被替换，因为它显然更有价值。页更常用的属性是访问的近期性（recency），越近被访问过的页，也许再次访问的可能性也就越大。

这一系列的策略是基于人们所说的局部性原则（principle of locality），基本上只是对程序及其行为的观察。程序倾向于频繁地访问某些代码（例如循环）和数据结构（例如循环访问的数组）。因此，应该尝试用历史数据来确定哪些页面更重要，并在需要踢出页时将这些页保存在内存中。

一系列简单的基于历史的算法诞生了

最不经常使用 (LFU) 策略：替换最不经常使用的页

最少最近使用 (LRU) 策略：替换最少使用的页面

计数器 (Counter) 的实现：

每个页表条目都有一个计数器。每次通过这个条目引用一个页面时，就把（逻辑）时钟复制到计数器中。每一次内存引用，时钟都会被递增。

当需要改变一个页面时，看一下计数器，以确定要改变哪个页面。

栈的实现：

以双链表的形式保存一个页号的栈。

每当一个页面被引用，就把它移到顶部；栈的顶部总是最近使用的页面，底部是 LRU 页面。

每一次更新都会有一些代价，无搜索替换。

遗憾的是，随着系统中页数量的增长，扫描所有页的时间字段只是为了找到最精确最少使用的页，这个代价太昂贵。

局部性类型

程序倾向于表现出两种类型的局部：

第一种是空间局部性（spatial locality），它指出如果页P 被访问，可能围绕它的页（比如P−1 或P+1）也会被访问

第二种是时间局部性（temporal locality），它指出近期访问过的页面很可能在不久的将来再次访问

假设存在这些类型的局部性，对硬件系统的缓存层次结构起着重要作用，硬件系统部署了许多级别的指令、数据和地址转换缓存，以便在存在此类局部性时，能帮助程序快速运行。当然，局部性原则并不是硬性规定，所有的程序都必须遵守。事实上，一些程序以相当随机的方式访问内存（或磁盘），并且在其访问序列中不显示太多或完全没有局部性。因此，尽管在设计任何类型的缓存（硬件或软件）时，局部性都是一件好事，但它并不能保证成功。相反，它是一种经常证明在计算机系统设计中有用的启发式方法。

近似LRU

由于实现完美的LRU 代价非常昂贵，我们能否实现一个近似的LRU 算法，并且依然能够获得预期的效果？

从计算开销的角度来看，近似更为可行，这实际上也是很多现代操作系统的做法。

该想法需要硬件增加一个引用位 (Reference Bit) ，系统每个页有一个引用位，然后这些使用位存储在某个地方，当页被引用 (即读或写) 时，硬件将引用位设置为 1，但是硬件不会清除该位，取而代之的是将其设置为0 (有操作系统负责) 。如此一来，我们就知道哪些页被引用，哪些页没有被引用了。

操作系统如何利用使用位来实现近似LRU？可以有很多方法，有一个简单的方法称作时钟算法（clock algorithm）。想象一下，系统中的所有页都放在一个循环列表中。时钟指针（clock hand）开始时指向某个特定的页（哪个页不重要）。当必须进行页替换时，操作系统检查当前指向的页P 的使用位是1 还是0。如果是1，则意味着页面P 最近被使用，因此不适合被替换。然后，P 的使用位设置为0，时钟指针递增到下一页（P + 1）。该算法一直持续到找到一个使用位为0 的页，使用位为0 意味着这个页最近没有被使用过（在最坏的情况下，所有的页都已经被使用了，那么就将所有页的使用位都设置为0）。

注意：这种方法不是通过使用位来实现近似LRU 的唯一方法。实际上，任何周期性地清除使用位，然后通过区分使用位是1和0来判定该替换哪个页的方法都是可以的。Corbato 的时钟算法只是一个早期成熟的算法，并且具有不重复扫描内存来寻找未使用页的特点，也就是它在最差情况下，只会遍历一次所有内存。

下图展示了时钟算法的一个变种的行为。该变种在需要进行页替换时随机扫描各页，如果遇到一个页的引用位为1，就清除该位（即将它设置为0）。直到找到一个使用位为0的页，将这个页进行替换。如你所见，虽然时钟算法不如完美的LRU 做得好，但它比不考虑历史访问的方法要好。

考虑脏页

时钟算法的一个小修改（最初也由Corbato提出），是对内存中的页是否被修改的额外考虑。这样做的原因是：如果页已被修改（modified）并因此变脏（dirty），则踢出它就必须将它写回磁盘，这很昂贵。如果它没有被修改（因此是干净的，clean），踢出就没成本。物理帧可以简单地重用于其他目的而无须额外的I/O。因此，一些虚拟机系统更倾向于踢出干净页，而不是脏页。

为了支持这种行为，硬件应该包括一个修改位（modified bit，又名脏位，dirty bit）。每次写入页时都会设置此位，因此可以将其合并到页面替换算法中。例如，时钟算法可以被改变，以扫描既未使用又干净的页先踢出。无法找到这种页时，再查找脏的未使用页面，等等。

其他虚拟内存策略

页面替换不是虚拟内存子系统采用的唯一策略（尽管它可能是最重要的）。例如，操作系统还必须决定何时将页载入内存。该策略有时称为页选择（page selection）策略，它向操作系统提供了一些不同的选项。

对于大多数页而言，操作系统只是使用按需分页（demand paging），这意味着操作系统在页被访问时将页载入内存中，“按需”即可。当然，操作系统可能会猜测一个页面即将被使用，从而提前载入。这种行为被称为预取（prefetching），只有在有合理的成功机会时才应该这样做。例如，一些系统将假设如果代码页P 被载入内存，那么代码页P + 1 很可能很快被访问，因此也应该被载入内存。

另一个策略决定了操作系统如何将页面写入磁盘。当然，它们可以简单地一次写出一个。然而，许多系统会在内存中收集一些待完成写入，并以一种（更高效）的写入方式将它们写入硬盘。这种行为通常称为聚集（clustering）写入，或者就是分组写入（grouping），这样做有效是因为硬盘驱动器的性质，执行单次大的写操作，比许多小的写操作更有效。

抖动

当内存被超额请求时，操作系统应该做什么？在这种情况下，系统将不断地进行换页，这种情况有时被称为抖动（thrashing）。

一些早期的操作系统有一组相当复杂的机制，以便在抖动发生时检测并应对。例如，给定一组进程，系统可以决定不运行部分进程，希望减少的进程工作集（它们活跃使用的页面）能放入内存，从而能够取得进展。这种方法通常被称为准入控制（admission control）。

目前的一些系统采用更严格的方法处理内存过载。例如，当内存超额请求时，某些版本的Linux 会运行“内存不足的杀手程序（out-of-memory killer）”。这个守护进程选择一个内存密集型进程并杀死它，从而以不怎么委婉的方式减少内存。虽然成功地减轻了内存压力，但这种方法可能会遇到问题，例如，如果它杀死X服务器，就会导致所有需要显示的应用程序不可用。