页面置换算法

进程运行时，若其访问的页面不在内存而需将其调入，但内存已无空闲空间时，就需要从内存中调出一页程序或数据，送入磁盘的对换区。

选择调出页面的算法就称为页面置换算法。

好的页面置换算法应有较低的页面更换频率，也就是说，应将以后不会再访问或者以后较长时间内不会再访问的页面先调出。

常见的置换算法有以下四种。

1. 最佳置换算法(OPT)

最佳(Optimal, OPT)置换算法所选择的被淘汰页面将是以后永不使用的，或者是在最长时间内不再被访问的页面,这样可以保证获得最低的缺页率。

但由于人们目前无法预知进程在内存下的若千页面中哪个是未来最长时间内不再被访问的，因而该算法无法实现。

最佳置换算法可以用来评价其他算法。假定系统为某进程分配了三个物理块，并考虑有以下页面号引用串：

7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1

进程运行时，先将7, 0, 1三个页面依次装入内存。

进程要访问页面2时，产生缺页中断，根据最佳置换算法，选择第18次访问才需调入的页面7予以淘汰。

然后，访问页面0时，因为已在内存中所以不必产生缺页中断。

访问页面3时又会根据最佳置换算法将页面1淘汰……依此类推，如图3-26所示。从图中可以看出釆用最佳置换算法时的情况。

可以看到，发生缺页中断的次数为9，页面置换的次数为6。

  • 图3-26 利用最佳置换算法时的置换图

输入图片说明

先进先出(FIFO)页面置换算法

优先淘汰最早进入内存的页面，亦即在内存中驻留时间最久的页面。

该算法实现简单，只需把调入内存的页面根据先后次序链接成队列，设置一个指针总指向最早的页面。

但该算法与进程实际运行时的规律不适应，因为在进程中，有的页面经常被访问。

  • 图 3-27 利用FIFO置换算法时的置换图

输入图片说明

这里仍用上面的实例，釆用FIFO算法进行页面置换。进程访问页面2时，把最早进入内存的页面7换出。然后访问页面3时，再把2, 0, 1中最先进入内存的页换出。

由图 3-27可以看出，利用FIFO算法时进行了 12次页面置换，比最佳置换算法正好多一倍。

FIFO算法还会产生当所分配的物理块数增大而页故障数不减反增的异常现象，这是由 Belady于1969年发现，故称为Belady异常，如图3-28所示。只有FIFO算法可能出现Belady 异常，而LRU和OPT算法永远不会出现Belady异常。

  • 图 3-28 Belady 异常

输入图片说明

最近最久未使用(LRU)置换算法

选择最近最长时间未访问过的页面予以淘汰，它认为过去一段时间内未访问过的页面，在最近的将来可能也不会被访问。

该算法为每个页面设置一个访问字段，来记录页面自上次被访问以来所经历的时间，淘汰页面时选择现有页面中值最大的予以淘汰。

再对上面的实例釆用LRU算法进行页面置换，如图3-29所示。

进程第一次对页面2访问时，将最近最久未被访问的页面7置换出去。然后访问页面3时，将最近最久未使用的页面1换出。

  • 图3-29 LRU页面置换算法时的置换图

输入图片说明

在图3-29中，前5次置换的情况与最佳置换算法相同，但两种算法并无必然联系。

实际上，LRU算法根据各页以前的情况，是“向前看”的，而最佳置换算法则根据各页以后的使用情况，是“向后看”的。

LRU性能较好，但需要寄存器和栈的硬件支持。LRU是堆栈类的算法。

理论上可以证明，堆栈类算法不可能出现Belady异常。

FIFO算法基于队列实现，不是堆栈类算法。

时钟(CLOCK)置换算法

LRU算法的性能接近于OPT,但是实现起来比较困难，且开销大；FIFO算法实现简单，但性能差。

所以操作系统的设计者尝试了很多算法，试图用比较小的开销接近LRU的性能，这类算法都是CLOCK算法的变体。

简单版本

简单的CLOCK算法是给每一帧关联一个附加位，称为使用位。

当某一页首次装入主存时，该帧的使用位设置为1;当该页随后再被访问到时，它的使用位也被置为1。

对于页替换算法，用于替换的候选帧集合看做一个循环缓冲区，并且有一个指针与之相关联。

当某一页被替换时，该指针被设置成指向缓冲区中的下一帧。当需要替换一页时，操作系统扫描缓冲区，以查找使用位被置为0的一帧。

每当遇到一个使用位为1的帧时，操作系统就将该位重新置为0；如果在这个过程开始时，缓冲区中所有帧的使用位均为0，则选择遇到的第一个帧替换；如果所有帧的使用位均为1,则指针在缓冲区中完整地循环一周，把所有使用位都置为0，并且停留在最初的位置上，替换该帧中的页。

由于该算法循环地检查各页面的情况，故称为CLOCK算法，又称为最近未用(Not Recently Used, NRU)算法。

改进型的 clock 算法

CLOCK算法的性能比较接近LRU，而通过增加使用的位数目，可以使得CLOCK算法更加高效。在使用位的基础上再增加一个修改位，则得到改进型的CLOCK置换算法。

这样，每一帧都处于以下四种情况之一：

最近未被访问，也未被修改(u=0, m=0)。
最近被访问，但未被修改(u=1, m=0)。
最近未被访问，但被修改(u=0, m=1)。
最近被访问，被修改(u=1, m=1)。

步骤

算法执行如下操作步骤：

从指针的当前位置开始，扫描帧缓冲区。在这次扫描过程中，对使用位不做任何修改。选择遇到的第一个帧(u=0, m=0)用于替换。

如果第1)步失败，则重新扫描，查找(u=0, m=1)的帧。选择遇到的第一个这样的帧用于替换。在这个扫描过程中，对每个跳过的帧，把它的使用位设置成0。

如果第2)步失败，指针将回到它的最初位置，并且集合中所有帧的使用位均为0。重复第1步，并且如果有必要，重复第2步。这样将可以找到供替换的帧。

改进型的CLOCK算法优于简单CLOCK算法之处在于替换时首选没有变化的页。由于修改过的页在被替换之前必须写回，因而这样做会节省时间。

页面分配策略：驻留集大小、调入页面的时机以及从何处调入页面

驻留集大小

对于分页式的虚拟内存，在准备执行时，不需要也不可能把一个进程的所有页都读取到主存，因此，操作系统必须决定读取多少页。

也就是说，给特定的进程分配多大的主存空间，这需要考虑以下几点：

  1. 分配给一个进程的存储量越小，在任何时候驻留在主存中的进程数就越多，从而可以提高处理机的时间利用效率。

  2. 如果一个进程在主存中的页数过少，尽管有局部性原理，页错误率仍然会相对较高。

  3. 如桌页数过多，由于局部性原理，给特定的进程分配更多的主存空间对该进程的错误率没有明显的影响。

基于这些因素，现代操作系统通常釆用三种策略：

（1）固定分配局部置换。

它为每个进程分配一定数目的物理块，在整个运行期间都不改变。若进程在运行中发生缺页，则只能从该进程在内存中的页面中选出一页换出，然后再调入需要的页面。

实现这种策略难以确定为每个进程应分配的物理块数目：太少会频繁出现缺页中断，太多又会使CPU和其他资源利用率下降。

（2）可变分配全局置换。

这是最易于实现的物理块分配和置换策略，为系统中的每个进程分配一定数目的物理块,操作系统自身也保持一个空闲物理块队列。

当某进程发生缺页时，系统从空闲物理块队列中取出一个物理块分配给该进程，并将欲调入的页装入其中。

（3）可变分配局部置换。

它为每个进程分配一定数目的物理块，当某进程发生缺页时，只允许从该进程在内存的页面中选出一页换出，这样就不会影响其他进程的运行。

如果进程在运行中频繁地缺页，系统再为该进程分配若干物理块，直至该进程缺页率趋于适当程度；

反之，若进程在运行中缺页率特别低，则可适当减少分配给该进程的物理块。

调入页面的时机

为确定系统将进程运行时所缺的页面调入内存的时机，可釆取以下两种调页策略：

（1）预调页策略。

根据局部性原理，一次调入若干个相邻的页可能会比一次调入一页更高效。

但如果调入的一批页面中大多数都未被访问，则又是低效的。

所以就需要釆用以预测为基础的预调页策略，将预计在不久之后便会被访问的页面预先调入内存。

但目前预调页的成功率仅约50%。故这种策略主要用于进程的首次调入时，由程序员指出应该先调入哪些页。

（2）请求调页策略。

进程在运行中需要访问的页面不在内存而提出请求，由系统将所需页面调入内存。

由这种策略调入的页一定会被访问，且这种策略比较易于实现，故在目前的虚拟存储器中大多釆用此策略。

它的缺点在于每次只调入一页，调入调出页面数多时会花费过多的I/O开销。

从何处调入页面

请求分页系统中的外存分为两部分：用于存放文件的文件区和用于存放对换页面的对换区。

对换区通常是釆用连续分配方式，而文件区釆用离散分配方式，故对换区的磁盘I/O速度比文件区的更快。

这样从何处调入页面有三种情况：

（1）系统拥有足够的对换区空间：

可以全部从对换区调入所需页面，以提髙调页速度。

为此，在进程运行前，需将与该进程有关的文件从文件区复制到对换区。

（2）系统缺少足够的对换区空间：

凡不会被修改的文件都直接从文件区调入；而当换出这些页面时，由于它们未被修改而不必再将它们换出。

但对于那些可能被修改的部分，在将它们换出时须调到对换区，以后需要时再从对换区调入。

（3）UNIX方式：

与进程有关的文件都放在文件区，故未运行过的页面，都应从文件区调入。

曾经运行过但又被换出的页面，由于是被放在对换区，因此下次调入时应从对换区调入。进程请求的共享页面若被其他进程调入内存，则无需再从对换区调入。

页面抖动(颠簸)和工作集(驻留集)

页面抖动（颠簸）

在页面置换过程中的一种最糟糕的情形是，刚刚换出的页面马上又要换入主存，刚刚换入的页面马上就要换出主存，这种频繁的页面调度行为称为抖动，或颠簸。

如果一个进程在换页上用的时间多于执行时间，那么这个进程就在颠簸。

频繁的发生缺页中断（抖动），其主要原因是某个进程频繁访问的页面数目高于可用的物理页帧数目。

虚拟内存技术可以在内存中保留更多的进程以提髙系统效率。在稳定状态，几乎主存的所有空间都被进程块占据，处理机和操作系统可以直接访问到尽可能多的进程。

但如果管理不当，处理机的大部分时间都将用于交换块，即请求调入页面的操作，而不是执行进程的指令，这就会大大降低系统效率。

工作集（驻留集）

工作集（或驻留集）是指在某段时间间隔内，进程要访问的页面集合。

经常被使用的页面需要在工作集中，而长期不被使用的页面要从工作集中被丢弃。为了防止系统出现抖动现象，需要选择合适的工作集大小。

工作集模型的原理是：让操作系统跟踪每个进程的工作集，并为进程分配大于其工作集的物理块。

如果还有空闲物理块，则可以再调一个进程到内存以增加多道程序数。如果所有工作集之和增加以至于超过了可用物理块的总数，那么操作系统会暂停一个进程，将其页面调出并且将其物理块分配给其他进程，防止出现抖动现象。

正确选择工作集的大小，对存储器的利用率和系统吞吐量的提嵩，都将产生重要影响。

参考资料

操作系统的基本概念

https://lgwain.gitbooks.io/os/content/unit11.html