内存管理(三)

超越物理内存：机制

操作系统如何利用大而慢的设备，透明地提供巨大虚拟地址空间的假象？

不仅是一个进程，增加交换空间让操作系统为多个并发运行的进程都提供巨大地址空间的假象。

交换空间

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

交换空间的大小是非常重要的，它决定了系统在某一时刻能够使用的最大内存页数。

存在位

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

当TLB 未命中发生的时候有3 种重要情景：

  1. 第一种情况，该页存在（present）且有效（valid）（第18～21 行）。在这种情况下，TLB 未命中处理程序可以简单地从PTE 中获取PFN，然后重试指令（这次TLB 会命中），并因此继续前面描述的流程。
  2. 第二种情况（第22～23 行），页错误处理程序需要运行。虽然这是进程可以访问的合法页（毕竟是有的），但它并不在物理内存中。
  3. 第三种情况，访问的是一个无效页，可能由于程序中的错误（第13～14 行）。在这种情况下，PTE 中的其他位都不重要了。硬件捕获这个非法访问，操作系统陷阱处理程序运行，可能会杀死非法进程。

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

交换何时真正发生

为了保证有少量的空闲内存，大多数操作系统会设置高水位线（High Watermark，HW）和低水位线（Low Watermark，LW），来帮助决定何时从内存中清除页。原理是这样：当操作系统发现有少于LW 个页可用时，后台负责释放内存的线程会开始运行，直到有HW 个可用的物理页。这个后台线程有时称为交换守护进程（swap daemon）或页守护进程（pagedaemon），它然后会很开心地进入休眠状态，因为它毕竟为操作系统释放了一些内存。

内存页替换策略

最优替换策略

Belady展示了一个简单的方法（但遗憾的是，很难实现！），即替换内存中在最远将来才会被访问到的页，可以达到缓存未命中率最低。

遗憾的是，正如我们之前在开发调度策略时所看到的那样，未来的访问是无法知道的，你无法为通用操作系统实现最优策略①。因此，在开发一个真正的、可实现的策略时，我们将聚焦于寻找其他决定把哪个页面踢出的方法。因此，最优策略只能作为比较，知道我们的策略有多接近“完美”。

简单策略：FIFO

页在进入系统时，简单地放入一个队列。当发生替换时，队列尾部的页（“先入”页）被踢出。FIFO 有一个很大的优势：实现相当简单。

对比FIFO 和最优策略，FIFO 明显不如最优策略，FIFO 命中率只有36.4%（不包括强制性未命中为57.1%）。先进先出（FIFO）根本无法确定页的重要性：即使页0 已被多次访问，FIFO 仍然会将其踢出，因为它是第一个进入内存的。

另一简单策略：随机

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

利用历史数据：LRU

正如在调度策略所做的那样，为了提高后续的命中率，我们再次通过历史的访问情况作为参考。例如，如果某个程序在过去访问过某个页，则很有可能在不久的将来会再次访问该页。

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

系统的每个页有一个使用位，然后这些使用位存储在某个地方（例如，它们可能在每个进程的页表中，或者只在某个数组中）。每当页被引用（即读或写）时，硬件将使用位设置为1。但是，硬件不会清除该位（即将其设置为0），这由操作系统负责。

实现方法：

操作系统如何利用使用位来实现近似LRU？可以有很多方法，有一个简单的方法称作时钟算法（clock algorithm）。

image-20230430100109881

Clock算法逻辑如下：

  1. 每个缓存槽都有一个对应的状态，每当这个缓存槽中的数据被访问后，将状态至为 1，否则为0 （图中用绿色表示状态为1，红色表示状态为0）
  2. 使用一个指针A指向下一个将要被淘汰的位置
  3. 每次需要淘汰缓存中，从A指针开始，顺时针遍历，找到第一个状态为0的槽，将其淘汰
  4. 而B指针会定时顺时针遍历，把所有的缓存槽的状态为都重置为0

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

当内存就是被超额请求时，操作系统应该做什么，这组正在运行的进程的内存需求是否超出了可用物理内存？

在这种情况下，系统将不断地进行换页，这种情况有时被称为抖动（thrashing）