页面置换算法

过程运转时，若其拜访的页面不在内存而需将其调入，但内存已无闲暇空间时，就需求从内存中调出一页程序或数据，送入磁盘的对调区。
选择调出页面的算法就称为页面置换算法。好的页面置换算法应有较低的页面改换频率，也就是说，应将今后不会再拜访或许今后较长工夫内不会再拜访的页面先调出。
罕见的置换算法有以下四种。

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  应用最佳置换算法时的置换图

2. 先辈先出(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 异常

3. 比来最久未运用(LRU)置换算法

选择比来最长工夫未拜访过的页面予以镌汰，它以为过来一段工夫内未拜访过的页面，在比来的未来能够也不会被拜访。该算法为每一个页面设置一个拜访字段，来记载页面自前次被拜访以来所阅历的工夫，镌汰页面时选择现有页面中值最大的予以镌汰。
再对下面的实例釆用LRU算法停止页面置换，如图3-29所示。过程第一次对页面2拜访时，将比来最久未被拜访的页面7置换出去。然后拜访页面3时，将比来最久未运用的页面1换出。

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

在图3-29中，前5次置换的状况与最佳置换算法相反，但两种算法并无必定联络。实践上，LRU算法依据各页以前的状况，是“向前看”的，而最佳置换算规律依据各页今后的运用状况，是“向后看”的。
LRU功能较好，但需求存放器和栈的硬件支撑。LRU是客栈类的算法。实际上可以证实，客栈类算法弗成能呈现Belady异常。FIFO算法基于队列完成，不是客栈类算法。

4. 时钟(CLOCK)置换算法

LRU算法的功能接近于OPT,然则完成起来比拟艰苦，且开支大；FIFO算法完成复杂，但功能差。所以操作零碎的设计者测验考试了许多算法，试图用比拟小的开支接近LRU的功能，这类算法多是CLOCK算法的变体。
复杂的CLOCK算法是给每一帧联系关系一个附加位，称为运用位。当某一页初次装入主存时，该帧的运用位设置为1;当该页随后再被拜访到时，它的运用位也被置为1。关于页交换算法，用于交换的候选帧聚集看做一个轮回缓冲区，而且有一个指针与之相干联。当某一页被交换时，该指针被设置成指向缓冲区中的下一帧。当需求交换一页时，操作零碎扫描缓冲区，以查找运用位被置为0的一帧。每当碰到一个运用位为1的帧时，操作零碎就将该位从新置为0；假如在这个进程开端时，缓冲区中一切帧的运用位均为0，则选择碰到的第一个帧交换；假如一切帧的运用位均为1,则指针在缓冲区中完好地轮回一周，把一切运用位都置为0，而且逗留在最后的地位上，交换该帧中的页。因为该算法轮回地反省各页面的状况，故称为CLOCK算法，又称为比来未用(Not Recently Used, NRU)算法。
CLOCK算法的功能比拟接近LRU，而经过添加运用的位数量，可以使得CLOCK算法愈加高效。在运用位的根底上再添加一个修正位，则失掉改良型的CLOCK置换算法。如许，每一帧都处于以下四种状况之一：

1. 比来未被拜访，也未被修正(u=0, m=0)。

2. 比来被拜访，但未被修正(u=1, m=0)。

3. 比来未被拜访，但被修正(u=0, m=1)。

4. 比来被拜访，被修正(u=1, m=1)。

算法履行如下操作步调：

1. 从指针的以后地位开端，扫描帧缓冲区。在此次扫描进程中，对运用位不做任何修正。选择碰到的第一个帧(u=0, m=0)用于交换。

2. 假如第1)步掉败，则从新扫描，查找(u=0, m=1)的帧。选择碰到的第一个如许的帧用于交换。在这个扫描进程中，对每一个跳过的帧，把它的运用位设置成0。

3. 假如第2)步掉败，指针将回到它的最后地位，而且聚集中一切帧的运用位均为0。反复第1步，而且假如有需要，反复第2步。如许将可以找到供交换的帧。

改良型的CLOCK算法优于复杂CLOCK算法之处在于交换时首选没有变更的页。因为修正过的页在被交换之前必需写回，因此如许做会节俭工夫。