【OS】虚存管理—页面置换算法

页面置换概述

页面置换是用于处理缺页错误的一种方法。
基于虚拟内存技术，我们可以使得执行的进程不必完全存在于内存中，即使是需要整个程序的情况下，也不一定是同时需要整个程序。假想我们有一个10页大小的进程，实际只使用其中的5页，那么请求调页就节省了用以加载另外不需要的5页的I/O。这意味着我们可以运行两倍的进程，从而增加多道程序度。如果有40个帧，那么可以运行40/5=8个进程，而不是考虑完整的进程大小对应的4个进程。
但在增加多道程序度的同时，可能会引起一些问题。首先是过度分配(over-allocating)问题，如果在上述假设下我们运行6个进程，那么会有更高的CPU利用率和吞吐量，并且还有着10帧的空闲。但对于某些特定的数据集，该进程可能突然需要使用它的全部10个页面。这就需要60帧，然后我们只有40帧。
其次考虑内存不仅仅用于保存程序页面，用于I/O的缓存也会消耗大量的内存，这样的使用会增大内存置换算法的压力。内存的过度分配会导致发生缺页错误，OS确定了所需页面的磁盘位置，但查找空闲帧列表却发现没有空闲帧——所有的内存都在被使用。OS这时可以选择终止用户进程，但设计请求调页系统的初衷是为了改善计算机系统的使用率和吞吐量，用户在使用计算机的过程中不应该察觉到他们的进程是工作在调页系统上的，也就是说，调页过程对于用户来说应该是透明的。这里最常见的解决方法就是页面置换。
页面置换采用的方法可以这样描述：没有空闲帧时，查找一个当前不在使用的帧，并将其释放。释放意味着将该帧写到交换空间，并修改页表和其他的表，以表示该页不在内存中。从而接下来可以使用空闲帧来保存“缺页错误”的那个页面。
缺页错误处理程序结合页面置换后修改如下：

1. 找到所需页面的磁盘位置
2. 查找一个空闲帧
   a.如果有空闲帧，直接使用.
   b.如果没有空闲帧，就使用页面置换算法来选择一个牺牲帧(victim frame).
   c.将牺牲帧的内容写到磁盘上，修改对应的页表和帧表.
3. 将所需的页面读入(新的)空闲帧，修改页表和帧表
4. 从发生缺页错误的位置继续执行用户进程

注意，如果没有空闲帧，意味着两次页面传输——牺牲帧调出，需要帧调入。这样的选择加倍了缺页错误的处理时间，相应地增加了有效访问时间。对于这样的情况，我们可以采用修改位(modify bit)或脏位(dirty bit)来减少开销。每当页面内的任何字节被写入时，它的修改位就会被设置(由硬件完成)，表示该页面被修改过。这样在上述步骤2.c中，未被修改的页面，就无需写回磁盘(因为已经存在)。

FIFO页面置换

FIFO页面置换算法是最简单的页面置换算法，它为每个页面记录了到达内存的时间，当需要置换时，选择最旧的那个页面完成置换。实际实现中，我们并不需要真的记录下时间，只需要维护一个FIFO的对列Queue。置换时选择Front(Queue)即可，调入页面时只需要Push_back(Queue)添入队列末尾。
我们以【有一个请求分页系统的作业页面请求为1，2，3，4，2，1，5，6，2，1，3，7，6，3，2，1，2，3，6，分配该作业的页框数为5.】为例，模拟执行FIFO页面置换算法。

FIFO算法的性能并不很理想，一方面，被置换的页面可能是很久以前使用过但现在不再使用的初始化模块；另一方面，所置换的页面可能包含一个被大量使用的变量，它很早就被初始化，但不断地被使用。另外我们原本期望，为一个进程提供更多的内存可以改善它的性能。但实际上对于FIFO算法，分配帧数量的增加反而会有缺页错误率随之增加的反常情况——Belady异常。

最优页面置换

最优页面置换算法被称为OPT或MIN，它拥有所有算法中最低的缺页错误率。OPT的思想在于置换最长时间不会被使用的页面，可以确保对于给定数量的帧，产生最低的可能的缺页错误率。沿用FIFO中的页面实例，OPT的置换过程如下：

OPT算法的问题在于难以，或者说无法实现。它需要引用串的未来知识。类似于进程调度中的SJF调度算法——剩余执行时间最少的进程优先，对于页面未来是否被使用，我们很难做出预测。所以OPT算法的意义在于比较研究，如果我们发现一种页面置换算法和OPT相比，最坏情况下不差于12.3%，最好情况下不差于4.7%，那么这样一个页面置换算法也很有效。

LRU页面置换

LRU是Least-Recently-Used的首字母缩略词，顾名思义就是最近最少使用。我们使用最近的过去作为不远将来的近似，置换掉最长时间没有被使用过的页面。LRU算法将每个页面与它上一次被使用的时间联系起来，这种策略可以看作是时间上向后看的OPT算法。引用实例的置换过程如下：
LRU算法通常被用于页面置换算法，是一种不错的选择。实现LRU算法需要一个确定由上次使用时间定义的帧的顺序，这需要重要的硬件辅助。两种实现方法是可行的：

• 【计数器】在最简单的情况下，为每个页表条目关联一个时间域，并为CPU添加一个逻辑时钟或计数器。每次内存引用都会递增时钟，每当进行页面引用时，就将时间寄存器的内容复制到相应页面的页表条目的时间域。如此我们就有了每一个页面的“最后引用时间”。计数器方案需要搜索页表以查找LRU页面，并且每次内存访问也需要写到页表的时间域，另外页表的更改、时钟的溢出也不得不考虑。
• 【堆栈】每当页面被引用时，它就从堆栈中移除并置于栈顶，这样最近使用的页面就位于栈顶，而最近最少使用的页面就位于栈底。由于需要从堆栈的中间删除条目，所以双向链表是一个极佳的实现方式。堆栈方案无需搜索，LRU页面总是位于栈底。

和OPT算法一样，LRU算法也不会有Belady异常。LRU和OPT算法都属于堆栈算法，绝对不可能有Belday异常。堆栈算法可以证明为：帧数为n的内存页面集合是帧数为n+1的内存页面集合的子集。对于LRU算法，页面集合是最近使用过的n个页面，倘若帧数增加，最近使用过的n个页面依然是这n个，依旧存在于内存中。同样的，对于OPT算法，页面集合是未来会被使用的n个页面，帧数增加后，这n个页面依旧是未来会使用的。

近似LRU页面置换

上面我们提到的LRU算法似乎很理想了，兼顾可实现性和效率。但实际上很少有计算机能够提供足够的硬件支持来实现真正的LRU页面置换算法。有一些系统不提供硬件支持，并且必须使用其它的页面置换算法(例如上面提到的FIFO算法)。事实上，许多系统通过引用位(reference bit)的形式提供一定的支持。引用位是这样工作的，每当引用一个页面时(包括对页面进行读或写)，它的硬件引用位就被置1.页表内的每个条目都被关联着一个引用位。
最初，所有的引用位都被清零。当用户进程执行时，硬件设置引用到页面的引用位(置1).一段时间后，我们可以通过检查引用位来确定哪些页面被使用而哪些页面尚未使用，即使这样的策略下我们并不知道使用的次序，这样的信息是很多近似LRU算法使用的。

1.额外引用位算法

通过定期记录引用位，我们可以获得额外的排序信息。考虑为内存中的页表的每个页面保留一个8位的字节。操作系统将每个页面引用位移到该8位字节的最高位，其余位一次右移一位，抛弃最低位。如此一来，这样的8位字节就表示了最近8个时间周期内某一个页面的使用情况。举例说明，如果一个页面具有00000000的值，就代表它在最近的8个周期内都没有被使用过。再例如，具有值为11011010的页面要比值为01010011的页面更加接近最近使用的。在进行页面置换时，将这样的8位字节解释为无符号整数，那么具有最小值的页面就成为LRU页面，被选中替换。
额外引用位算法很灵活，8位字节的长度也可以被减少，以求更快的信息更新。在极端情况下，长度减少为0，即只剩了引用位本身。这样的算法称为第二次机会算法。

2.第二次机会算法

第二次机会算法的基本算法是FIFO算法。当需要一个帧时，检查页面的引用位，若为0则直接可以替换；否则将引用位置1(第二次机会)，继续查找下一个FIFO页面。当一个页面获得第二次机会时，它的到达时间被设置为当前时间。所以这样一个获得第二次机会的页面，在其他所有页面都获得第二次机会之前，是不会被替换的。
实现第二次机会算法，有时也被称为时钟算法的一种方式是采用循环队列。指针指向接下来要置换哪个页面。当需要一个帧时，指针向前移动直到找到一个引用位为0的页面，并置换它。在指针向前移动时，它会清除沿途的引用位(给予第二次机会)。一旦找到牺牲帧，就置换这一页面，并且在该位置插入新的页面。
不难发现，在最坏的情况下——所有页面的引用位都被设置，指针就会遍历整个对列，并且清除每一个页面的引用位，给予它们第二次机会。这时的Clock算法(时钟算法)退化成FIFO算法，选择最先进入对列的那个页面替换。

3.增强型第二次机会算法

将引用位和修改位作为一组有序对来改进第二次机会算法。

• (0,0)代表近期既没有被使用过，也没有被修改过，是最佳的页面置换。
• (0,1)代表近期没有被使用过但是被修改过的页面，是不太好的页面置换，因为需要将该页面写回磁盘。
• (1,0)代表近期被使用过但是没有被修改的页面，可能很快会被再次使用。
• (1,1)代表近期既被使用过又被修改过，可能很快会再次使用，并且置换时需要写回磁盘。

每个页面必然都属于上述这四种类型的集合。当需要页面置换时，可以采用与Clock算法一样的策略：检查页面的类型(不是仅仅检查引用位)，我们替换掉最低类型中的一个页面(如果这一类型的页面有的话)。因为可能并不存在(0,0)类型的页面，这时就选择(0,1)类型的页面，依此类推。增强型第二次机会算法的亮点在于它赋予了那些被修改过的页面更高的优先级，从而降低了所需要I/O的数量。

基于计数的页面置换

1. LFU，最不经常使用页面置换算法.
2. MFU，最经常使用页面置换算法.

这两种算法的使用很少，原因在于它们的实现代价较大，并且也不能很好地近似OPT算法。LFU和MFU都需要维护一个计数器来保存页面的引用次数。LFU要求置换引用次数最少的页面，而MFU算法认为具有最小计数的页面可能刚刚被引入并且尚未使用，它替换掉引用次数最多的页面。

页面缓冲算法(其它缺页错误处理)

除了页面置换算法以外，系统通常也保留一个空闲的缓冲池。当出现缺页错误时，也选择出一个牺牲帧。但在牺牲帧写出之前，会先将所需的页面放入缓冲池内的空闲帧，使得进程能够快速启动，而无需等待牺牲帧的写出。然后，当牺牲帧完成它的写出任务后，它就作为空闲帧被加入到缓冲池。