操作系统基础 内存换页算法
换页算法的分类
公平算法：
随机算法
先来先出（FIFO）算法
第二次机会算法
时钟算法
非公平算法：
最优算法
NRU算法
LRU算法
工作集算法
工作集时钟算法
随机更换算法
需要替换页面的时候，产生一个随机页面号，替换与该页面对应的物理页面。
先来先出（FIFO）算法
更换最早进入内存的页面。
FIFO的实现机制是使用链表将所有在内存的页面按照进入时间的早晚链接起来，然后每次置换链表头上的页面就行了。
第二次机会算法
就是在使用FIFO更换一个页面时，需要看一下该页面是否在最近被访问过。
如果没有被访问过，则替换该页面。
如果该页面在最近被访问过（通过检查其访问位的取值），则不替换该页面，而是将该页面挂到链表末端，并将该页面进入内存的时间设置为当前时间，并将其访问位清零。
相当于给内存页面第二次机会。
时钟算法
在时钟算法里，我们把页面排成一个时钟的形状。
该时钟有一个针臂。每次需要更换页面时，我们从针臂所指的页面开始检查。如果当前页面的访问位为0，即从上次检查到这次，该页面没有被访问过，将该页面替换。如果当前页面被访问过，那就将其访问位清零，并顺时针移动指针到下一个页面。我们重复这些步骤直到找到一个访问位为0的页面。
时钟算法和第二次机会算法有点相似，但又不一样：
1.数据结构不一样，第二次机会使用的是链表，而时钟算法使用的是索引（整数指针）。
2.第二次机会算法需要使用额外的内存，而时钟算法可以直接使用页表。并且页表的访问位会定期自动清零，这样使得时钟算法的时间分辨粒度较第二次机会算法高。
最优更换算法
在非公平的算法里面，最理想的页面替换算法是选择一个再也不会被访问的页面进行替换；如果不存在这样的页面，那至少选择一个在随后最长时间内不会被访问的页面进行替换——这就是最优更换算法。
其实，最优更换算法就是一种不会实际实现的算法。
存在的意义是为了定义一个标杆，以此来评判其他算法的优劣。
NRU算法
最近未使用算法（Not Recently Used，NRU），就是选择一个最近没有被访问的页面来替换，在所有的最近没有使用的页面里，按照各个页面的修改位和访问位的组合来进行划分。
| 页面类型 | 访问位状态 | 修改位状态 |
|---|---|---|
| 1 | 没有被访问 | 没有被修改 |
| 2 | 没有被访问 | 修改过 |
| 3 | 被访问过 | 没有被修改 |
| 4 | 被访问过 | 被修改过 |
注：2情况是可能的，系统对访问位会定期清零，对修改位却不能清零。
NRU算法就是按照这4类页面的顺序寻找可以替换的页面。
它首先看看内存页面里有没有第1种页面，有的话就将找到的第1个这种页面作为替换对象。
如果没有，则在第2种页面里面寻找；
若还没有，则在第3种页面里面寻找；
以此类推，如果所有页面皆被访问和修改过，那也只能从中替换掉一个页面。
因此，NRU算法总是会终结。
LRU算法
对NRU算法的改进就是LRU算法。LRU算法是最近使用最少算法（LeastRecently Used）。
该算法有多种实现方式：
使用计数器来记录
最简单的办法就是在页表的记录项里增加一个计数域，一个页面被访问一次，这个计数器的值就增加1。这样，当需要更换页面时，只需找到计数域取值最小的页面替换即可，该页面即是最近最少使用的页面。
缺点：
需要使用的计数器个数与虚拟页面数一样多，空间成本巨大。
在遴选页面来替换时，需要比较所有页面的计数器的取值，时间成本也很大。
使用链表来实现
LRU算法的另一种简单实现方式是用一个链表将所有页面链接起来，最近被使用的页面在链表头，最近未被使用的放在链表尾。在每次页面访问时对这个链表进行更新，使其保持最近被使用的页面在链表头。
缺点：
- 每次内存访问都对链表进行更新效率十分低下，因为这种更新需要考虑不同页面之间的关系。
使用矩阵实现
矩阵法，就是使用一个矩阵来记录页面的使用频率和时间。该矩阵为n×n维，n是相关程序当前驻内存的页面数。在一开始矩阵每行每列的初值为0。
每次一个页面被访问时，例如第k个虚拟页面被访问时，我们进行如下操作：
将第k行的值全部设置为1。
将第k列的值全部设置为0。
在每次需要更换一个页面时，选择矩阵里对应行值最小的页面更换即可。此处的行值是指把该行所有的0和1连起来看做一个二进制数时的取值。
例如，假定某个程序有4个虚拟页面，分别是0、1、2、3。该程序虚拟页面的访问顺序是：0，1，2，3，2，1，0，3，2，3。随着页面访问的进行，矩阵的状态变化如图：
在第1步操作后，我们已经保证该页面对应的行值为最大之一。而第2个操作将该页面对应的列置为0，则保证了该页面对应的行值为唯一的最大。
由于每个页面访问都会将某一列置为0，这样，越长时间没有被访问的页面，其对应的行元素里面被置为0的列个数就越多，即它对应的行值将越小，也就保证了其正确性。
优点：
使用矩阵的许多理论来迅速判断哪个矩阵行值最小。
使用矩阵来实现LRU算法的成本比使用计数域要低，因为这个矩阵的行列数并不需要是虚拟页面数，而是在内存中的实际页面数，因此要小多了。
缺点：
但该矩阵仍然太大，因为总的存储位是页面数的平方。
另外，我们将最近的时间限定在最近的9次访问的话，那么应该被更换的是页面0。因为在最近9次访问里，页面0只被访问过1次，而其他页面均被访问过2次或以上。但按照矩阵法的结果是页面1被更换。由于每次页面访问时，矩阵的置1操作都覆盖了之前的信息，所以矩阵法不能体现长时间访问次数的累积。
使用移位寄存器实现
我们给每个存放在内存的页面配备一个移位寄存器。该寄存器用来记录该页面被访问频率和最近的属性。所有移位寄存器的初值皆为0。
然后在每个规定长度的周期内，将移位寄存器的值往右移动一位，并将对应页面的访问位的值加到该移位寄存器的最左位。
这样，当需要寻找一个页面进行更换时，只需要找到对应移位寄存器值最小的页面即可。该页面即是最近最少使用的页面。
例如，假定某程序有6个页面在内存中，页号分别为0、1、2、3、4、5。其对应的6个移位寄存器初值皆设置为0，如a)所示。
在第一个规定周期内，页面0、2、4、5的访问位为1，页面1和3的访问位为0。我们将移位寄存器往右移动一位，并将各个页面的访问位加到相应移位寄存器的左面，就得到图b)的状态。
在第2个规定周期内，页面0、1、4的访问位为1，而2、3、5的访问位为0，我们重复同样的操作获得图c)的状态。
假如第3个规定周期内页面0、1、3、5的访问位为1，2、4的访问位为0，则获得图d)的状态。
第4个周期内页面0、4被访问过，其他页面的访问位为0，得到图e)的状态，第5个周期内页面1、2被访问过，其他页面的访问位为0，得到图f)的状态。
这时如果需要替换页面，第3个页面所对应的移位寄存器里面的值最小，因此页面3将被替换。
优点：
在硬件上节省了空间。因为移位寄存器个数虽然与内存页面数一样，但每个寄存器的长度却没有页面数多。矩阵法需要n×n维的空间，而这里是n×L维。这里的L是移位寄存器的长度。只要移位寄存器的长度少于进程在内存的页面数，这种实现方式就有空间上的优势。
节省时间。在矩阵法里，每次页面访问均需要更新矩阵，而移位寄存器法却不需要每次访问都进行更新。我们只在规定长度的时间内统计更新一次。例如，如果每1秒钟发生100次内存访问，则矩阵法在一秒钟需要更新100次，但在移位寄存器法里，我们完全可以每1秒钟更新一次，或者每5秒钟更新一次。因此更新的粒度（周期）是非常灵活的。而正因为这个灵活性，使得我们的时间成本大大降低。
该实现将最近放在比次数更优先考虑的地位。这是一个常见的“衰老算法”的思想，越是发生时间久远的事件，它对决策的影响越小。
缺点：
精确性不如矩阵法。在某些特定情况下，这样选出的页面有可能不是最近最少使用的页面。
这是用移位寄存器实现的，造价高，需要的寄存器数量较大。
工作集算法
由于不可能精确地确定哪个页面是最近最少使用的，那就干脆不用花费这个力气，只维持少量的信息使得我们选出的替换页面不太可能是马上又会使用的页面即可。这种少量的信息就是工作集信息。
工作集概念来源于程序访问的时空局域性。即在一段时间内，程序访问的页面将局限在一组页面集合上。例如，最近k次访问均发生在某m个页面上，那么m就是参数为k时的工作集。我们用w（k，t）来表示在时间t时k次访问所涉及的页面数量。显然，随着k的增长，w（k，t）的值也随着增长；但在k增长到某个数值后，w（k，t）的值将增长极其缓慢甚至接近停滞，并维持一段时间的稳定。
由此可以看出，如果一个程序在内存里面的页面数与其工作集大小相等或超过工作集，则该程序可在一段时间内不会发生缺页中断。如果其在内存的页面数小于工作集，则发生缺页中断的频率将增加，甚至发生内存抖动。
工作集算法的实现如下：
为页表的每个记录增加一项信息用来记录该页面最后一次被访问的时间。这个时间不必是真实时间，只要是按规律递增的一个虚拟时间即可。同时我们设置一个时间值T，如果一个页面的最后一次访问在当前时间减去T之前，则视为在工作集外，否则视为在工作集内。
这样，在每次需要替换页面时，扫描所有的页面记录，并进行如下操作：
如果一个页面的访问位是1，则将该页面的最后一次访问时间设为当前时间，并将访问位清零。
如果页面的访问位为0，则查看其访问时间是否在当前时间减去T之前。 a）如果在，则该页面将是被替换页面，算法结束。 b）如果不在，记录当前所有被扫描过页面的最后访问时间里面的最小值。扫描下一个页面并重复1、2两个步骤
如果在所有页面扫描后没有找到一个被替换的页面，则所有页面中最后一次访问时间最早的页面将被替换。这也是第b步记录当前最小值的原因。
优点：
工作集算法的优点是实现简单，只需在页表的每个记录增加一个虚拟时间域即可。因此，其空间成本不大。
该时间域不是每次发生访问时都需要修改，而是在需要更换页面时，页面更换算法对其进行修改，因此其时间成本也不大。
缺点：
是每次扫描页面进行替换时，有可能需要扫描整个页表。而我们知道，并不是所有页面都在内存里，因此扫描过程中的一大部分时间将是无用功。
由于其数据结构是线性的，造成每次都按同样的顺序进行扫描，这样就对某些页面不太公平。就好像评选优秀学生，如果大家的表现都同样优秀，就按照学号顺序来确定人选的话，那学号靠后的同学总是吃亏。
工作集时钟算法
工作集时钟算法，即使用工作集算法的原理，但是将页面的扫描顺序按照时钟的形式组织起来。
这样每次需要替换页面时，从指针指向的页面开始扫描，从而达到更加公平的状态。而且，按时钟组织的页面只是在内存里的页面，在内存外的页面不放在时钟圈里，从而提高实现效率。
鉴于其时间和空间上的优势，工作集时钟算法被大多数商业操作系统所采纳。
参考资料： 《操作系统之哲学原理》 邹恒明著
