一文看懂页面置换算法

页面置换算法分为两类

1、局部页面置换算法

• 最优页面置换算法（OPT、optimal）
• 先进先出算法（FIFO）
• 最近最久未使用算法（LRU,Least Recently Used）
• 时钟页面置换算法（Clock）
• 最不常用算法（LFU，Least Frequently Used）
• Belady现象
• LRU、FIFO和Clock的比较

2、全局页面置换算法

• 工作集模型
• 工作集页置换算法
• 缺页率置换算法

功能：

当缺页中断发生，需要调入新的页面而内存已满时，选择内存当中哪个物理页面被置换。

目标：

尽可能地减少页面的换进换出次数（既缺页中断的次数）。具体来说，把未来不再使用的或短期内较少使用的页面换出，通常只能在局部性原理指导下依据过去的统计数据来进行预测。

页面锁定（frame locking）：

用于描述必须常驻内存的操作系统的关键部分或时间关键（time-critical）的应用程序。实现的方法是L在页表中添加锁定标志位（lock bit）。使其不在页面置换算法范围之内，也就说不会被换入换出。

通常只需要考虑页号，因为偏移号一般不起作用。只保留页号。基于这个list来设计各种的页面替换算法。
通过模拟一个页面置换的行为并且记录产生页缺失数的数量。一般情况下，产生的缺页次数越少，性能就越高。

1、最优页面置换算法

一、基础

基本思路：

当一个缺页中断发生时，对于保存在内存当中的每一个逻辑页面，计算在它的下一次访问之前，还需要等待多长时间，从中选择等待时间最长的那个，作为被置换的页面。

结论：

• 这只是一个理想的情况，在实际系统中是无法实现的，因为操作系统无从知道每一个页面要等待多长时间以后才会再次被访问。
• 可用作其他算法的性能评价的依据（在一个模拟器上运行某个程序，并记录每一次的页面访问情况，在第二遍运行时即可使用最优算法。然后以此为基础，评价其他的算法。）

二、示例

在上帝视角中，可以看出由于d是最长时间没有被使用，所以d将会被e所替换，如上所示。

【文章福利】小编推荐自己的Linux内核技术交流群： 【977878001】整理一些个人觉得比较好得学习书籍、视频资料共享在群文件里面，有需要的可以自行添加哦！！！前100进群领取，额外赠送一份 价值699的内核资料包（含视频教程、电子书、实战项目及代码）

内核资料直通车：Linux内核源码技术学习路线+视频教程代码资料

学习直通车：Linux内核源码/内存调优/文件系统/进程管理/设备驱动/网络协议栈

2、先进先出算法

一、基础

先进先出算法（First-In First-Out，FIFO）：

1、基本思路：

选择在内存中驻留时间最长的页面并淘汰之。具体来说，系统维护着一个链表，记录了所有位于内存当中的逻辑页面。从链表的排列顺序来看，链首页面的驻留时间最长，链尾页面的驻留时间最短。当发生一个缺页中断时，把链首页面淘汰出局，并把新的页面添加到链表的末尾。

2、评价：

性能较差，调出的页面有可能是经常要访问的页面，并且有Belady现象（给的物理页帧越多，产生缺少的次数越大）。FIFO算法很少单独使用。

二、示例

实现简单，但是产生的缺页次数比较多

3、最近最久未使用算法

一、基础

最近最久未使用算法（LRU,Least Recently Used）

1、基本思路：

当一个缺页中断发生时，选择最久未使用的那个页面，并淘汰之。

2、评价：

它是对最优页面置换算法的一个近似，其依据是程序的局部性原理，既在最近一小段时间（最近几条指令）内，如果某些页面被频繁地访问，那么在将来的一小段时间内。他们还可能会再一次地频繁地访问。反过来说，如果在过去某些页面长时间未被访问，那么在将来他们还可能会长时间地得不到访问。也就是根据过去推算出未来。

二、示例

LRU算法需要记录各个页面使用时间的先后顺序。

开销比较大。两种可能的实现方法是：

方法一：

系统维护一个页面链表，最近各个使用过的页面作为首节点，最久未使用的页面作为尾节点。每一次访问内存时，找到相应的页面，把它从链表中摘下来，在移动到链表之首。每次缺页中断发生时，也就是没有这个页表，所以会把新的页表查到链表头，然后淘汰链表末尾的页面。

方法二：

设置一个活动页面栈，当访问某页时，将此页号压入栈顶，然后考察栈内是否有与页面相同的页号，若有则抽出。然后压入栈顶。当需要淘汰一个页面时，总是选择栈底的页面，它就是最久未使用的。

效果比较好，但是系统的开销比较大

4、时钟页面置换算法

一、基础

Clock页面置换算法，LRU的近视，对FIFO的一种改进

1、基本思路

1）需要用到页表项当中的访问位，当一个页面被装入内存时，把该位初始化为0。然后如果这个页面被访问（读/写），则把该位置置1。

2）把各个页面组织形成环形链表（类似钟表面），把指针指向最老的页面（最先进来）。

3）当发生一个缺页中断时，考察指针所指向的最老页面。若它的访问位为0，立即淘汰；若访问位为1，则把该位置为0，然后指针往下移动一格。如此下去，直到找到被淘汰的页面，然后把指针移动到它的下一格。

二、具体实现

• resident bit：存在位，代表是否存在。如果是1，代表在物理内存是存在的，表示映射的关系是正常的。如果是0，就不能正常的映射。
• used bit：如果是1代表当前的页被访问过一次，硬件支持将其置为1。（这个位可以硬件自动的操作，同时也可以由软件操作）
• frame number：页帧号

时钟页面置换算法的依据就是第二个位------used bit

三、示例

• 其中的置1操作是由硬件自动实现的。
• 替换的情况是产生缺页中断时候才会执行的。如果本来就有此内存，则指针是不需要向下移动寻找最老页面。也就是说如果存在，则指针保持不动，只需要置1操作既可。

5、二次机会法

一、基础

• resident bit：存在位，代表是否存在。如果是1，代表在物理内存是存在的，表示映射的关系是正常的。如果是0，就不能正常的映射
• used bit：如果是1代表当前的页被访问过一次，硬件支持将其置为1。（这个位可以硬件自动的操作，同时也可以由软件操作）
• dirty bit：如果执行了一个写操作，那么这个位会置为1；如果只是读操作，那么这个位是0。这个bit的设置也是由硬件来完成的。

当某一个运行的程序，对某一页进行访问之后。

• 如果是写操作，硬件会将used bit和dirty bit都置为1.
• 如果是读操作。硬件会将used bit置为1，而dirty bit还是0.

这个bit可以区分读和写，但是对我们的置换算法有什么帮助呢？

解析：

• 因为我们的算法是换入换出算法，所以如果当应用程序对内存进行读操作的时候，这个内存与磁盘的内容是一样的，所以只需要将其释放掉就可以了，不需要进行换入换出的操作。
• 而如果应用程序对内存进行了写操作的时候，这时表面与磁盘的内容不一样，替换的时候就需要把内容换入换出。
• 这时，两个bit都用上了，来减少硬盘的访问也就是减少写回操作的次数。

由于used=1，dirty=1的页会循环两次才会被替换出去，所以很形象生动的称之为二次机会法。

通过这种方式，可以把经常使用dirty bit的这个页有更多的机会留着内存中来。而不会被换到内存中去。对硬盘的访问次数也会减少。

二、示例

带有w表示对此页进行的是写操作而不是读操作，读操作是不带w

此时考虑两个位，used bit和dirty bit

比较接近LRU算法，优先的把只读的页换出去了，对于可写的页减少了换出去的概率，对于可以减少回写的概率。

6、最不常用算法

一、基础

最不常用算法（Least Frequently Used，LFU）

基本思路：

当一个缺页中断发生时，选着访问次数最少的那个页面，并淘汰之。被访问的次数也会很少。

实现方法：

对每个页面设置一个访问计数器，每当一个页面被访问时，该页面的访问计数器加1。每当反生缺页中断时，淘汰计数器最小的那个页面。

问题：

增加计数器会消耗硬件资源，会浪费空间，而选择次数最少的那个意味在要遍历整个链表，耗费时间，实现比较费时费力。而且当一个页面在进程开始的时使用得很多，但是以后就不再使用了，LFU还是会保留。（根据该点的解决方法：定时的把次数寄存器右移一位）

LRU和LFU的区别：

LRU考察的是多久未访问，时间越短越好；而LFU考察的是访问的次数或频度，访问次数越多越好。

二、示例

以上操作是将访问次数最多的替换出去。

7、Belady现象、LRU、FIFO、Clock的比较

一、Belady现象

Belady是一个科学家的名字，不必纠结）

定义：

在采用FIFO算法时，有时会出现分配的物理页面数增加，缺页率反而提高的异常现象

Belady现象的原因：

FIFO算法的置换特征与进程访问内存的动态特征是矛盾的，与置换算法的目标是不一致的（既替换较少使用的页面），因此，被它替换出去的页面并不一定是进程不会访问的。

二、Belady现象示例

1、当分3个物理页的情况—出现9次中断缺失

2、当分4个物理页的情况—出现10次中断缺失

结果：
出现了物理页，给了更多的物理页，但是出现页缺失的情况更多

相比之下，LRU算法是符合预期情况的，给的硬件资源越多，产生中断页缺失的情况就会越少。

原因：
LRU算法满足某种栈的属性，而FIFO算法不满足某种栈的属性，所以会导致Belady现象。

三、LRU、FIFO、Clock的比较
1、性质的比较

2、性能的比较

8、局部页面替换算法的问题、工作集模型

局部页面置换算法都是针对一个正在运行的程序来讲的，但是操作系统支持多个应用程序。

以上可见，只是仅仅增加了一个物理页帧，就对整个页面置换算法造成很大的效果影响。如果对一个程序固定一个物理页帧，其实是在某一个程度上限制了这个程序产生缺页的特点。因为其对物理内存的需求是动态可变的。

而前面所诉的前提是物理页帧是假设为固定的。这样就限制了灵活性。但是可以根据不同的运行阶段，动态分配调整物理页帧的大小，这点就是全局页面置换算法要考虑的问题。

一、工作集模型

前面介绍的各种页面置换算法都是基于一个前提的，既程序的局部性原理。

• 如果局部性原理不成立，那么各种页面置换算法就没有什么分别，也没有什么意义。例如：假设进程对逻辑页面的访问顺序是1,2,3,4,5,6,7,8,9…,即单调递增，那么在物理页面数有限的前提下，不管采用何种置换算法，每次的页面访问都必然导致缺页中断。
• 如果局部性原理是成立的，那么如何来证明它的存在，如何来对它进行定量地分析？这就是工作集模型。

1、工作集的定义：

一个进程当前正在使用的逻辑页面集合，可以用一个二元函数W(t，△)来表示。

二元函数W(t，△) 其中参数如下：

例子：

这表明t2具有良好的局部性，t1有一定的局部性，但是整体的局部性不如t2的效果好。

2、工作集大小的变化：

进程开始执行后，随着访问新页面逐步建立较稳定的工作集。当内存访问的局部性区域的位置大致稳定时，工作集带下也大致稳定；局部性区域的位置改变时，工作集快速扩张和收缩过渡到下一个稳定值。

二、常驻集模型

常驻集是指在当前时刻，进程实际驻留在内存当中的页面集合。

• 工作集是进程运行过程中固有的性质，而常驻集取决于系统分配给进程的物理页面数目（物理空间的大小），以及所采用的页面置换算法。来决定到底把哪些页面放在内存中来。
• 常驻集是当前运行的程序访问的页在哪些在内存中；而工作集指的是程序运行中所需要访问的页是哪些，这表示有些页是不在内存中的，只有部分页是在内存中的。
• 如果一个进程的整个工作集读在内存当中，既常驻集属于工作集，那么进程将很顺利地进行运行，而不会造成太多的缺页中断（直到工作集发生剧烈变动，从而过渡到另一个状态）。
• 当进程常驻集的大小达到某个数目之后，再给它分配更多的物理页面，缺页率也不会明显下降，可以给其他运行的程序，使总的缺页比较少。

9、两个全局置换算法

一、工作集页置换算法

1、基本思想

有一个size，代表了其过去形成工作集的大小。窗口里面的页是当前时间内被访问到的页。随着时间的挪动平移，如果某一个不在这个时间的窗口之内，这个页也会被丢到，而并不是说要等到缺页的时候才会丢页。也就是这个页不属于这个窗口了，就会被替换。

2、示例

结果如下：

1----edac----abcd 6----dbce----bcde

2----dacc----acd 7----bcec----bce

3----accd----acd 8----cece----ce

4----ccdb----bcd 9----ecea----ace

5----cdbc----bcd 10—cead----acde

分析：

并不是因为缺页而丢弃，而是因为不在这个窗口当中的所以老页都会被换出去。这样可以确保物理内存中有足够的页存在，可以减少页面置换降低，这个是站着整个系统层面上看的。

二、缺页率页面置换算法

1、可变分配策略：

常驻集大小可变。例如：每个进程在刚开始运行的时候，先根据程序大小给它分配一定数目的物理页面，然后在进程运行过程中，再动态地调整常驻集的大小。根据缺页率来改变，缺页率高，可以增加常驻集；缺页率降低，可以减小常驻集。

缺页率算法（PFF，page fault frequency）

2、缺页率
定义：
表示“缺页次数/内存访问次数”（比率）或“缺页的平均时间间隔的倒数”。

影响缺页率的因素：

• 页面置换算法
• 分配给进程的物理页面数目
• 页面本身的大小
• 程序的编写方法

使整个系统保持一个平衡，使所有的程序到保持一个较低的缺页率。

一个交替的工作集计算明确的试图最小化页缺失

• 当缺页率高的时候-增加工作集
• 当缺页率低的时候-减少工作集

3、算法的实现

4、示例

分析：

当前的阈值是2，也就是如果两次产生中断的时间大雨2的话，话增加工作;而如果中断的时间小于等于2的话，就会动态的减少工作集。

• 在时间1时刻，产生一个缺失中断。
• 在时间4时刻，由于没有b，所以也产生了一次缺失中断。并且，由于1-4之间的时刻大于2，所以会动态的去除在这段时刻中没有读取的页，也是就是ae，所以此时只有bcd三个工作页。
• 在时间6时刻，由于没有e，产生了一次缺失中断。并且，由于4-6之间的时刻等于2，所以会动态的增加所需要的页。
• 在时间9时刻，由于没有页a，所以产生了一次缺失中断。并且，由于6-9之间的时刻大于2，所以也会动态的去除在这段时间中没有读取的页，也就是bd，因为这段时间只有ec的页需要操作，此时就只有ace三个工作页。

5、小结
这两个算法是根据工作集的大小动态的调整的，前面只是满的时候才调整，这个是他们之间的主要区别。所有对于操作系统而言，为了应对多个应用程序，采用全局的页面置换算法更加的合适。

10、抖动问题

抖动问题是对工作集和常驻集做进一步的讲解。

1、抖动的定义

如果分配给一个进程的物理页面太少，不能包含整个的工作集，既常驻集属于工作集，那么进程将会造成很多的缺页中断，需要频繁地在内存与外存之间替换页面，从而使进程的运行速度变得很慢，将这种状态称为“抖动”。

2、产生抖动的原因

随着驻留内存的进程的数目增加，分配给每个进程的物理页面数不断减小，缺页率不断上升。所以操作系统要选择一个适当的进程数目和进程需要的帧数，以便在并发水平和缺页率之间达到一个平衡。

3、解决

当运行的程序过多时，cpu要执行多次的换入换出换出io操作，而导致程序没有执行，导致cpu的利用率降低，造成了电脑的卡顿。

蓝线的比值越大，表示缺页的频率很低，cpu利用率较高。（其中页缺失的服务时间是不变的）

当平均页缺失时间 = 页缺失服务时间 的时候，这时候的效率就接近最完美的点。