OS- -内存之页面置换算法

一、内存之页面置换算法

• 当发生缺页异常时，操作系统会选择一个页面进行换出从而为新进来的页面腾出空间。
• 如果要换出的页 面在内存中已经被修改，那么必须将其写到磁盘中以使磁盘副本保持最新状态。如果页面没有被修改 过，并且磁盘中的副本也已经是最新的，那么就不需要进行重写。那么就直接使用调入的页面覆盖需 要移除的页面就可以了。
• 当发生缺页中断时，虽然可以随机的选择一个页面进行置换，但是如果每次都选择一个不常用的页面会 提升系统的性能。如果一个经常使用的页面被换出，那么这个页面在短时间内又可能被重复使用，那么 就可能会造成额外的性能开销

在关于页面的主题上有很多页面置换算法(page replacement algorithms),这些已经从理论上和实践上得到了证明。

• 需要指出的是，页面置换问题在计算机的其他领域中也会出现。例如，多数计算机把最近使用过的32 字节或者64字节的存储块保存在一个或多个高速缓存中。当缓存满的时候，一些块就被选择和移除。
• 这些块的移除除了花费时间较短外，这个问题同页面置换问题完全一样。之所以花费时间较短，是因为 丢掉的高速缓存可以从内存中获取，而内存没有寻找磁道的时间也不存在旋转延迟。
• 第二个例子是Web服务器。服务器会在内存中缓存一些经常使用到的Web页面。然而，当缓存满了并 且已经引用了新的页面，那么必须决定退出哪个Web页面。
• 在高速缓存中的Web页面不会被修改。因 此磁盘中的Web页面经常是最新的，同样的考虑也适用在虚拟内存中。在虚拟系统中，内存中的页面 可能会修改也可能不会修改。

下面我们就来探讨一下有哪些页面置换算法。

1.最优页面置换算法

最优的页面置换算法很容易描述但在实际情况下很难实现。

• 它的工作流程如下：
• 在缺页中断发生时，这 些页面将在下一条指令（包含该指令的页面）上被引用。其他页面则可能要到10、100或者1000 条指令后才会被访问。每个页面都可以用在该页首次被访问前所要执行的指令数作为标记。
• 最优化的页面算法表明应该标记最大的页面。如果一个页面在800万条指令内不会被使用，另外一个页 面在600万条指令内不会被使用，则置换前一个页面，从而把需要调入这个页面而发生的缺页中断推 迟。

计算机也像人类一样，会把不愿意做的事情尽可能的往后拖。

• 这个算法最大的问题时无法实现。当缺页中断发生时，操作系统无法知道各个页面的下一次将在什么时 候被访问。这种算法在实际过程中根本不会使用。

2.最近未使用页面置换算法

• 为了能够让操作系统收集页面使用信息，大部分使用虚拟地址的计算机都有两个状态位，R和M,来和 每个页面进行关联。
• 每当引用页面（读入或写入）时都设置R,写入（即修改）页面时设置M,这些 位包含在每个页表项中，就像下面所示：
  
• 因为每次访问时都会更新这些位，因此由硬件来设置它们非常重要。一旦某个位被设置为1,就会一 直保持1直到操作系统下次来修改此位。
• 如果硬件没有这些位，那么可以使用操作系统的缺页中断和时钟中断机制来进行模拟。
• 当启动一个进 程时，将其所有的页面都标记为不在内存；一旦访问任何一个页面就会引发一次缺页中断，此时操作 系统就可以设置R位（在它的内部表中），修改页表项使其指向正确的页面，并设置为READ ONLY 模式，然后重新启动引起缺页中断的指令。
• 如果页面随后被修改，就会发生另一个缺页异常。从而允许操作系统设置M位并把页面的模式设置为READ/WRITE。
• 可以用R位和M位来构造一个简单的页面置换算法：当启动一个进程时，操作系统将其所有页面的两 个位都设置为0。R位定期的被清零（在每个时钟中断）。用来将最近未引用的页面和已引用的页面分 开。
• 当出现缺页中断后，操作系统会检查所有的页面，并根据它们的R位和M位将当前值分为四类：
• •第0类：没有引用R,没有修改M
• •第1类：没有引用R,已修改M
• •第2类：引用R,没有修改M
• •第3类：已被访问R,已被修改M
• 尽管看起来好像无法实现第一类页面，但是当第三类页面的R位被时钟中断清除时，它们就会发生。时钟中断不会清除M位，因为需要这个信息才能知道是否写回磁盘中。清除R但不清除M会导致出现 一类页面。

• NRU（Not Recently Used）算法从编号最小的非空类中随机删除一个页面。
• 此算法隐含的思想是， 在一个时钟内（约20ms）淘汰一个已修改但是没有被访问的页面要比一个大量引用的未修改页面好， NRU的主要优点是易于理解并且能够有效的实现。

3.先进先出页面置换算法

• 另一种开销较小的方式是使用FIF0（First-In,First-Out）算法，这种类型的数据结构也适用在页 面置换算法中。
• 由操作系统维护一个所有在当前内存中的页面的链表，最早进入的放在表头，最新进入 的页面放在表尾。
• 在发生缺页异常时，会把头部的页移除并且把新的页添加到表尾。
• 还记得缺页异常什么时候发生吗？我们知道应用程序访问内存会进行虚拟地址到物理地址的映 射，缺页异常就发生在虚拟地址无法映射到物理地址的时候。因为实际的物理地址要比虚拟地址 小很多，所以缺页经常会发生。
• 先进先出页面可能是最简单的页面替换算法了。在这种算法中，操作系统会跟踪链表中内存中的所有 页。

下面我们举个例子看一下

• •初始化的时候，没有任何页面，所以第一次的时候会检查页面1是否位于链表中，没有在链表中，那么就是MISS ,页面1进入链表，链表的先进先出的方向如图所示。
• •类似的，第二次会先检查页面2是否位于链表中，没有在链表中，那么页面2进入链表，状态为 MISS ,依次类推。
• •我们来看第四次，此时的链表为12 3,第四次会检查页面2是否位于链表中，经过检索后， 发现2在链表中，那么状态就是HIT ,并不会再进行入队和出队操作，第五次也是一样的。
• •下面来看第六次，此时的链表还是12 3,因为之前没有执行进入链表操作，页面5会首先进 行检查，发现链表中没有页面5,则执行页面5的进入链表操作，页面2执行出链表的操作，执 行完成后的链表顺序为235。

4.第二次机会页面置换算法

• 我们上面学到的FIFO链表页面有个缺陷，那就是出链和入链并不会进行check检查，这样就会容 易把经常使用的页面置换出去(无法显示热点数据)
• 为了避免这一问题，我们对该算法做一个简单的修改：我们检查最老页 面的R位，如果是0,那么这个页面就是最老的而且没有被使用，那么这个页面就会被立刻换出。
• 如果R位是1,那么就清除此位，此页面会被放在链表的尾部，修改它的装入时间就像刚放进来的一 样。然后继续搜索。
• 这种算法叫做 第二次机会(second chance)算法，就像下面这样，我们看到页面A到H保留在链表 中，并按到达内存的时间排序。
  
• a）按照先进先出的方法排列的页面；
• b）在时刻20处发生缺页异常中断并且A的R位已经设置时的 页面链表。
• 假设缺页异常发生在时刻20处，这时最老的页面是A ,它是在0时刻到达的。如果A的R位是03 那么它将被淘汰出内存，或者把它写回磁盘（如果它已经被修改过），或者只是简单的放弃（如果它是 未被修改过）。
• 另一方面，如果它的R位已经设置了，则将A放到链表的尾部并且重新设置装入时间 为当前时刻（20处），然后清除R位。然后从B页面开始继续搜索合适的页面。
• 寻找第二次机会的是在最近的时钟间隔中未被访问过的页面。如果所有的页面都被访问过，该算法就会 被简化为单纯的FIFO算法。
• 具体来说，假设图a中所有页面都设置了 R位。操作系统将页面依次 移到链表末尾，每次都在添加到末尾时清除R位。
• 最后，算法又会回到页面A,此时的R位已经被清 除，那么页面A就会被执行出链处理，因此算法能够正常结束。

5.时钟页面置换算法

• 即使上面提到的第二次页面置换算法也是一种比较合理的算法，但它经常要在链表中移动页面，既降低 了效率，而且这种算法也不是必须的。
• 一种比较好的方式是把所有的页面都保存在一个类似钟面的环形 链表中，一个表针指向最老的页面。

如下图所示：

• 当缺页错误出现时，算法首先检查表针指向的页面，如果它的R位是。就淘汰该页面，并把新的页面插入到这个位置，然后把表针向前移动一位；如果R位是1就清除R位并把表针前移一个位置。重复这个过程直到找到了一个R位为0的页面位置。

了解这个算法的工作方式，就明白为什么它被称为 时 钟(clokc)算法了。

6.最近最少使用页面置换算法(LRU)

• 最近最少使用页面置换算法的一个解释会是下面这样：在前面几条指令中频繁使用的页面和可能在后面 的几条指令中被使用。
• 反过来说，已经很久没有使用的页面有可能在未来一段时间内仍不会被使用。这 个思想揭示了一个可以实现的算法：在缺页中断时，置换未使用时间最长的页面。这个策略称为 LRU(Least Recently Used),最近最少使用页面置换算法。
• 虽然LRU在理论上是可以实现的，但是从长远看来代价比较高。为了完全实现LRU,会在内存中维护 —个所有页面的链表，最频繁使用的贞位于表头，最近最少使用的贞位于表尾。
• 困难的是在每次内存引 用时更新整个链表。在链表中找到一个页面，删除它，然后把它移动到表头是一个非常耗时的操作，即 使使用硬件来实现也是一样的费时。
• 然而，还有其他方法可以通过硬件实现LRU。让我们首先考虑最简单的方式。这个方法要求硬件有一个 64位的计数器，它在每条指令执行完成后自动加1,每个页表必须有一个足够容纳这个计数器值的域。
• 在每次访问内存后，将当前的值保存到被访问页面的页表项中。一旦发生缺页异常，操作系统就检查所 有页表项中计数器的值，找到值最小的一个页面，这个页面就是最少使用的页面。

7.用软件模拟LRU

• 尽管上面的LRU算法在原则上是可以实现的，但是很少有机器能够拥有那些特殊的硬件。
• 上面是硬件 的实现方式，那么现在考虑要用软件来实现LRU。一种可以实现的方案是NFU(Not Frequently Used,最不常用）算法。
• 它需要一个软件计数器来和每个页面关联，初始化的时候是0。在每个时钟中 断时，操作系统会浏览内存中的所有页，会将每个页面的R位（0或1）加到它的计数器上。
• 这个计数 器大体上跟踪了各个页面访问的频繁程度。当缺页异常出现时，则置换计数器值最小的页面。
• NFU最主要的问题是它不会忘记任何东西，想一下是不是这样？例如，在一个多次（扫描）的编译器 中，在第一遍扫描中频繁使用的页面会在后续的扫描中也有较高的计数。
• 事实上，如果第一次扫描的执 行时间恰好是各次扫描中最长的，那么后续遍历的页面的统计次数总会比第一次页面的统计次数小。 结果是操作系统将置换有用的页面而不是不再使用的页面。
• 幸运的是只需要对NFU做一个简单的修改就可以让它模拟LRU,这个修改有两个步骤:
• •首先，在R位被添加进来之前先把计数器右移一位；
• •第二步，R位被添加到最左边的位而不是最右边的位。

修改以后的算法称为老化Caging）算法，下图解释了老化算法是如何工作的：

• 我们假设在第一个时钟周期内页面0-5的R位依次是1, 0, 1, 0, 1, 1,（也就是页面0是1,页 面1是0,页面2是1这样类推）。
• 也就是说，在0个时钟周期到1个时钟周期之间，0, 2, 4, 5 都被引用了，从而把它们的R位设置为1,剩下的设置为0。
• 在相关的六个计数器被右移之后R位被 添加到 左侧，就像上图中的a。剩下的四列显示了接下来的四个时钟周期内的六个计数器变化。

• CPU正在以某个频率前进，该频率的周期称为时钟滴答或时钟周期。
• 一个10OMhz的处理器每 秒将接收100,000,000个时钟滴答。

• 当缺页异常出现时，将置换（就是移除）计数器值最小的页面。如果一个页面在前面4个时钟周期内 都没有被访问过，那么它的计数器应该会有四个连续的0,因此它的值肯定要比前面3个时钟周期内 都没有被访问过的页面的计数器小。

这个算法与LRU算法有两个重要的区别：看一下上图中的e ,第三列和第五列

• 它们在两个时钟周期内都没有被访问过，在此之前的时钟周期内都引用了两个页面。
• 根据LRU算法， 如果需要置换的话，那么应该在这两个页面中选择一个。那么问题来了，我萌应该选择哪个？
• 现在的问 题是我们不知道时钟周期1到时钟周期2内它们中哪个页面是后被访问到的。因为在每个时钟周期内 只记录了一位，所以无法区分在一个时钟周期内哪个页面最早被引用，哪个页面是最后被引用的。
• 因 此，我们能做的就是置换页面3 ,因为页面3在周期0-1内都没有被访问过，而页面5却被引用 过。
• LRU与老化之前的第2个区别是，在老化期间，计数器具有有限数量的位(这个例子中是8位)，这 就限制了以往的访问记录。
• 如果两个页面的计数器都是0,那么我们可以随便选择一个进行置换。实际 上，有可能其中一个页面的访问次数实在9个时钟周期以前，而另外一个页面是在1000个时钟周期之 前，但是我们却无法看到这些。
• 在实际过程中，如果时钟周期是20 ms, 8位一般是够用的。所以我们 经常拿20 ms来举例。

8.工作集页面置换算法

• 在最单纯的分页系统中，刚启动进程时，在内存中并没有页面。此时如果CPU尝试匹配第一条指令，就会得到一个缺贞异常，使操作系统装入含有第一条指令的页面。
• 其他的错误比如全局变量和堆栈 引起的缺贞异常通常会紧接着发生。一段时间以后，进程需要的大部分页面都在内存中了，此时进程开 始在较少的缺页异常环境中运行。这个策略称为请求调页(demand paging),因为页面是根据需要被 调入的，而不是预先调入的。
• 在一个大的地址空间中系统的读所有的页面，将会造成很多缺贞异常，因此会导致没有足够的内存来容 纳这些页面。
• 不过幸运的是，大部分进程不是这样工作的，它们都会以局部性方式(locality of reference)来访问，这意味着在执行的任何阶段，程序只引用其中的一小部分。
• 一个进程当前正在使用的页面的集合称为它的 工作集(working set),如果整个工作集都在内存中， 那么进程在运行到下一运行阶段(例如，编译器的下一遍扫面)之前，不会产生很多缺贞中断。
• 如果内 存太小从而无法容纳整个工作集，那么进程的运行过程中会产生大量的缺页中断，会导致运行速度也会 变得缓慢。
• 因为通常只需要几纳秒就能执行一条指令，而通常需要十毫秒才能从磁盘上读入一个页面。 如果一个程序每10 ms只能执行一到两条指令，那么它将需要很长时间才能运行完。如果只是执行几条指令就会产生中断，那么就称作这个程序产生了颠簸(thrashing)。
• 在多道程序的系统中，通常会把进程移到磁盘上(即从内存中移走所有的页面)，这样可以让其他进程 有机会占用CPU。
• 有一个问题是，当进程想要再次把之前调回磁盘的页面调回内存怎么办？从技术的 角度上来讲，并不需要做什么，此进程会一直产生缺页中断直到它的工作集 被调回内存。
• 然后，每次 装入一个进程需要20、100甚至1000次缺页中断，速度显然太慢了，并且由于CPU需要几毫秒时间 处理一个缺页中断，因此由相当多的CPU时间也被浪费了。
• 因此，不少分页系统中都会设法跟踪进程的工作集，确保这些工作集在进程运行时被调入内存。这个方 法叫做工作集模式(working set model)
• 它被设计用来减少缺页中断的次数的。在进程运行前首 先装入工作集页面的这一个过程被称为 预先调页(prepaging),工作集是随着时间来变化的。
• 根据研究表明，大多数程序并不是均匀的访问地址空间的，而访问往往是集中于一小部分页面。一次内 存访问可能会取出一条指令，也可能会取出数据，或者是存储数据。
• 在任一时刻t,都存在一个集合， 它包含所哟欧最近k次内存访问所访问过的页面。这个集合w(k,t)就是工作集。因为最近k=1次 访问肯定会访问最近k>1次访问所访问过的页面，所以w(k,t)是k的单调递减函数。
• 随着k的增 大，w(k,t)是不会无限变大的，因为程序不可能访问比所能容纳页面数量上限还多的页面。
  
• 事实上大多数应用程序只会任意访问一小部分页面集合，但是这个集合会随着时间而缓慢变化，所以为 什么一开始曲线会快速上升而k较大时上升缓慢。
• 为了实现工作集模型，操作系统必须跟踪哪些页面在 工作集中。一个进程从它开始执行到当前所实际使用的CPU时间总数通常称作当前实际运行时间。
• 进程的工作集可以被称为在过去的t秒实际运行时间中它所访问过的页面集合。
• 下面来简单描述一下工作集的页面置换算法，基本思路就是找出一个不在工作集中的页面并淘汰它。

下 面是一部分机器页表：

• 因为只有那些在内存中的页面才可以作为候选者被淘汰，所以该算法忽略了那些不在内存中的页面。
• 每 个表项至少包含两条信息：上次使用该页面的近似时间和R （访问）位。空白的矩形表示该算法不需要其他字段，例如页框数量、保护位、修改位。
• 算法的工作流程如下：
• 假设硬件要设置R和M位。同样的，在每个时钟周期内，一个周期性的时钟中 断会使软件清除Referenced（引用）位。在每个缺贞异常，页表会被扫描以找出一个合适的页面把它 置换。
• 随着每个页表项的处理，都需要检查R位。如果R位是1,那么就会将当前时间写入页表项的 上次使 用时间域，表示的意思就是缺贞异常发生时页面正在被使用。因为页面在当前时钟周期内被访问过，那 么它应该出现在工作集中而不是被删除（假设t是横跨了多个时钟周期）。
• 如果R位是0,那么在当前的时钟周期内这个页面没有被访问过，应该作为被删除的对象。为了查看 是否应该将其删除，会计算其使用期限（当前虚拟时间-上次使用时间），来用这个时间和t进行对 比。如果使用期限大于t,那么这个页面就不再工作集中，而使用新的页面来替换它。然后继续扫描更 新剩下的表项。
• 然而，如果R位是0但是使用期限小于等于t,那么此页应该在工作集中。此时就会把页面临时保存起 来，但是会记生存时间最长（即上次使用时间的最小值）的页面。
• 如果扫描完整个页表却没有找到适合 被置换的页面，也就意味着所有的页面都在工作集中。在这种情况下，如果找到了一个或者多个R = 0 的页面，就淘汰生存时间最长的页面。
• 最坏的情况下是，在当前时钟周期内，所有的页面都被访问过了（也就是都有R = 1）,因此就随机选择一个页面淘汰，如果有的话最好选一个未被访问的页面，也就 是干净的页面。

9.工作集时钟页面置换算法

• 当缺页异常发生后，需要扫描整个页表才能确定被淘汰的页面，因此基本工作集算法还是比较浪费时间 的。
• 一个对基本工作集算法的提升是基于时钟算法但是却使用工作集的信息，这种算法称为 WSClock(工作集时钟）。由于它的实现简单并且具有高性能，因此在实践中被广泛应用。

与时钟算法一样，所需的数据结构是一个以页框为元素的循环列表，就像下面这样:

• 工作集时钟页面置换算法的操作：a）和b）给出R = 1时所发生的情形；c）和d）给出R = 0的例子
• 最初的时候，该表是空的。当装入第一个页面后，把它加载到该表中。随着更多的页面的加入，它们形 成一个环形结构。每个表项包含来自基本工作集算法的上次使用时间，以及R位（已标明）和M位 （未标明）。
• 与时钟算法一样，在每个缺页异常时，首先检查指针指向的页面。如果R位被是设置为1,该页面在当 前时钟周期内就被使用过，那么该页面就不适合被淘汰。
• 然后把该页面的R位置为0,指针指向下一个 页面，并重复该算法。该事件序列化后的状态参见图b。
• 现在考虑指针指向的页面R = 0时会发生什么，参见图c,如果页面的使用期限大于t并且页面为被访 问过，那么这个页面就不会在工作集中，并且在磁盘上会有一个此页面的副本。
• 申请重新调入一个新的 页面，并把新的页面放在其中，如图d所示。另一方面，如果页面被修改过，就不能重新申请页面，因 为这个页面在磁盘上没有有效的副本。
• 为了避免由于调度写磁盘操作引起的进程切换，指针继续向前 走，算法继续对下一个页面进行操作。毕竟，有可能存在一个老的，没有被修改过的页面可以立即使 用。
• 原则上来说，所有的页面都有可能因为磁盘I/O在某个时钟周期内被调度。为了降低磁盘阻塞，需要 设置一个限制，即最大只允许写回n个页面。一旦达到该限制，就不允许调度新的写操作。
• 那么就有个问题，指针会绕一圈回到原点的，如果回到原点，它的起始点会发生什么？这里有两种情 况：
  •👏至少调度了一次写操作
  •👏没有调度过写操作
• 在第一种情况中，指针仅仅是不停的移动，寻找一个未被修改过的页面。由于已经调度了一个或者多个 写操作，最终会有某个写操作完成，它的页面会被标记为未修改。
• 置换遇到的第一个未被修改过的页 面，这个页面不一定是第一个被调度写操作的页面，因为硬盘驱动程序为了优化性能可能会把写操作重 排序。
• 对于第二种情况，所有的页面都在工作集中，否则将至少调度了一个写操作。由于缺乏额外的信息，最 简单的方法就是置换一个未被修改的页面来使用，扫描中需要记录未被修改的页面的位置，如果不存在 未被修改的页面，就选定当前页面并把它写回磁盘。

10.页面置换算法小结

我们到现在已经研究了各种页面置换算法，现在我们来一个简单的总结，算法的总结归纳如下:

• •最优算法在当前页面中置换最后要访问的页面。不幸的是，没有办法来判定哪个页面是最后一个要访问的，因此实际上该算法不能使用。然而，它可以作为衡量其他算法的标准。
• •NRU算法根据R位和M位的状态将页面分为四类。从编号最小的类别中随机选择一个页面。 NRU算法易于实现，但是性能不是很好。存在更好的算法。
• •FIFO会跟踪页面加载进入内存中的顺序，并把页面放入一个链表中。有可能删除存在时间最长 但是还在使用的页面，因此这个算法也不是一个很好的选择。
• •第二次机会算法是对FIFO的一个修改，它会在删除页面之前检查这个页面是否仍在使用。如果 页面正在使用，就会进行保留。这个改进大大提高了性能。
• •时钟算法是第二次机会算法的另外一种实现形式，时钟算法和第二次算法的性能差不多，但是会 花费更少的时间来执行算法。
• •LRU算法是一个非常优秀的算法，但是没有特殊的硬件（TLB）很难实现。如果没有硬件，就不能使用LRU算法。
• • NFU算法是一种近似于LRU的算法，它的性能不是非常好。
• •老化算法是一种更接近LRU算法的实现，并且可以更好的实现，因此是一个很好的选择
• •最后两种算法都使用了工作集算法。工作集算法提供了合理的性能开销，但是它的实现比较复杂。WSClock是另外一种变体，它不仅能够提供良好的性能，而且可以高效地实现。

总之，最好的算法是老化算法和WSClock算法。他们分别是基于LRU和工作集算法。

他们都具有良好 的性能并且能够被有效的实现。还存在其他一些好的算法，但实际上这两个可能是最重要的