该算法的功能与目标

功能：

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

目标：

尽可能地减少页面地换进换出地次数（即缺页中断地次数）。

具体地来说，把未来不再使用的或短期内较少使用的页面换出, 通常只能在局部性原理指导下依据过去的统计数据来进行预测.

局部页面置换算法

最优页面置换算法

基本思路 :

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

这是一种理想情况, 在实际系统中是无法实现的, 因为操作系统无法知道每一个页面要等待多长时间以后才会再次被访问.

先进先出算法

基本思路 ：

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

性能较差, 调出的页面有可能是经常要访问的页面. 并且有 belady现象. FIFO算法很少单独使用.

举例：

最近最久未使用算法LRU(Least Recently Used)

基本思路 ：

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

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

LRU算法需要记录各个页面使用时间的先后顺序, 开销比较大.

举例：

两种可能的实现方法是 :

• 系统维护一个页面链表, 最近刚刚使用过的页面作为首节点, 最久未使用的作为尾结点. 再一次访问内存时, 找出相应的页面, 把它从链表中摘下来, 再移动到链表首. 每次缺页中断发生时, 淘汰链表末尾的页面.
• 设置一个活动页面栈, 当访问某页时, 将此页号压入栈顶, 然后, 考察栈内是否有与此页面相同的页号, 若有则抽出. 当需要淘汰一个页面时, 总是选择栈底的页面, 它就是最久未使用的.

时钟置换算法

基本思路 :

• 需要用到页表项的访问位, 当一个页面被装入内存时, 把该位初始化为0. 然后如果这个页面被访问, 则把该位置设为1;
• 把各个页面组织成环形链表(类似钟表面), 把指针指向最老的页面(最先进来);
• 当发生一个缺页中断时, 考察指针所指向的最老页面, 若它的访问位为0, 立即淘汰; 若访问位为0, 然后指针往下移动一格. 如此下去, 直到找到被淘汰的页面, 然后把指针移动到下一格.

流程 :

如果访问页在物理内存中, 访问位置1.

如果不在物理页, 从指针当前指向的物理页开始, 如果访问位0, 替换当前页, 指针指向下一个物理页; 如果访问位为1, 置零以后访问下一个物理页再进行判断. 如果所有物理页的访问位都被清零了, 又回到了第一次指针所指向的物理页进行替换.

二次机会算法

因为考虑到时钟页面置换算法, 有时候会把一些 dirty bit 为1(有过写操作)的页面进行置换, 这样的话, 代价会比较大. 因此, 可以结合访问位和脏位一起来决定应该置换哪一页.

相当于说, 替换的优先级, 没有读写也没写过, 那么直接走, 如果写过或者访问过, 那么给你一次机会, 如果又写过, 又访问过, 那么久给你两次机会

举例

最不常用算法（Least Frequently used, LFU）

**基本思路 : **

当一个缺页中断发生时, 选择访问次数最少的那个页面, 并淘汰.

实现方法 :

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

LRU和LFU的对比 : LRU考察的是多久未访问, 时间越短越好. 而LFU考察的是访问的次数和频度, 访问次数越多越好.

Belady现象(科学家名字)

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

出现原因 :

FIFO算法的置换特征与进程访问内存的动态特征是矛盾的, 与置换算法的目标是不一致的(即替换较少使用的页面), 因此**, 被他置换出去的页面不一定是进程不会访问的.**

LRU / FIFO 和 Clock 的比较

全局页面置换算法

bc ：

操作系统是支持多进程的， 但是如果我们使用每个应用程序都使用各自的算法， 那势必是不行地。 所以我们就需要一个全局地算法.

工作集模型

工作集 : 一个进程当前正在（一个时间段）使用的逻辑页面集合.

可以使用一个二元函数 W(t, derta) 来表示 :

• t 是当前的执行时刻;
• delta 称为工作集窗口, 即一个定长的页面访问的时间窗口;
• W(t, derta) = 在当前时刻 t 之前的 derta 时间窗口当中的所有页面所组成的集合(随着 t 的变化, 该集合也在不断的变化)
• | W(t, derta) | 是工作集的大小, 即逻辑页的数量.

举例 ：

**工作集大小的变化 : **

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

常驻集：

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

• 工作集是进程在运行过程中固有的性质, 而常驻集取决于系统分配给进程的物理页面数目, 以及所采用的页面置换算法;
• 如果一个进程的整个工作集都在内存当中, 即常驻集 包含 工作集, 那么进程将很顺利地运行, 而不会造成太多的缺页中断(直到工作集发生剧烈变动, 从而过渡到另一个状态);
• 当进程常驻集的大小达到某个数目之后, 再给它分配更多的物理页面, 缺页率也不会明显下降.

工作集页置换算法

当工作集窗口在滑动过程中, 如果页面不在集合中, 那么就会直接丢失这个不在窗口中页面, 而不会等待缺页中断再丢弃.

**实例： **

缺页率置换算法

可变分配策略 : 常驻集大小可变. 例如 : 每个进程在刚开始运行的时候, 先根据程序大小给它分配一定数目的物理页面, 然后在进程运行过程中, 再动态地调整常驻集的大小.

• 可采用全局页面置换的方式, 当发生一个缺页中断时, 被置换的页面可以是在其他进程当中, 各个并发进程竞争地使用物理页面.
• 优缺点 : 性能较好, 但增加了系统开销.
• 具体实现 : 可以使用缺页率算法来动态调整常驻集的大小.

缺页率 : 表示 “缺页次数 / 内存访问次数”

影响因素 : 页面置换算法, 分配给进程的物理页面数目, 页面本身的大小, 程序的编写方法.

抖动问题

概念 ：

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

产生抖动的原因 :

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