OS 页面置换算法(OPT,FIFO,LRU)颠簸/抖动

介绍

置换算法

• 置换算法（replacement algorithm）又称为淘汰算法、替换算法，用于确定页面的调出原则。
• 在地址映射过程中，若在页面中发现所要访问的页面不在内存中，则产生缺页中断。当发生缺页中断时，如果操作系统内存中没有空闲页面，则操作系统必须在内存选择一个页面将其移出内存，以便为即将调入的页面让出空间。而用来选择淘汰哪一页的规则叫做页面置换算法。
• 在页面置换算法中主要需要掌握的是 先进先出算法(FIFO) 和 最近最少使用算法(LRU)。

颠簸 / 抖动

• 颠簸（thrashing）又称“抖动”，是指页面在内存与外存储器之间频繁地调度，以致系统用于调度页面的时间比进程实际运行所占用的时间还要长。
• 颠簸是由于页故障率过高而产生的结果，它将严重地影响系统的效率，甚至可能使系统全面崩溃。
• 通俗来讲就是一个进程的页面放入内存中，被淘汰出去后，进程又需要使用这个页面然后重新把他放入内存的过程。即你把我赶走之后，又叫我回来。

最佳算法（optimal，OPT）

算法思想

• 从理论上来讲，最佳算法是淘汰以后不再需要的或者在最长的时间以后才会用到的页面。
• 当要调入一新页而必须淘汰一旧页时，所淘汰的页是以后不再使用的，或者是以后相当长的时间内不会使用的。

特点

• 这是一种理想情况下的页面置换算法，页面故障率最低，但实际上不可能实现。
• 这是因为无法准确的预期页面“将来”的被访问情况。

例子

• 假设内存中为一个进程分配3个物理页框，开始时内存页框为空，页面置换情况如下所示：

• 缺页故障次数为9
• 缺页率 = 缺页次数 / 访问次数 = 9 / 20 = 45%

关于图的解释将在下面的例题中进行叙述。

先进先出算法（first-in first-out，FIFO）

算法思想

• 总是选择在主存中停留时间最长（即最老）的一页置换，即先进入内存的页，先退出内存。
• 实质是：淘汰在内存中驻留时间最长的的页面。
• 理由是：最早调入内存的页面，不再被使用的可能性比近期调入内存的大。

特点

• 这种算法只是在按线性顺序访问地址空间时才是理想的，否则效率不高。
• 算法简单，但执行效率不高。
• FIFO的另一个缺点是，它有一种异常现象（Belady 异常），即在增加存储块的情况下，反而使缺页中断率增加了。当然，导致这种异常现象的页面走向实际上是很少见的。

例题

在一个请求分页系统中，假设系统分配给某进程的物理块数为3，开始时内存为空，执行如下访问页号序列： 1，2，3，4，1，2，5，1，2，3，4，5 。

注意：上表的数据要竖着看，一列一列的看，不要横向看。
这里为了方便理解，淘汰的页面我是吧页号写在上面了，而3个X是未命中，但没有淘汰页面。后面我会统一用红X来表示发生缺页中断。
引用串：最上方灰色部分，是访问页号序列，即需要调用的页面号；
物理块：中间绿色部分，是系统分配给某进程的物理块数；
缺页：最下方红色部分，是系统发生缺页故障的次数；
/------------------------------------------------------------------------------/
访问的页在内存中，则称访问成功，否则为失败发生缺页中断。

• 缺页中断次数 = 9
• 过程：
• 开始时内存为空，前三个页面每次进入都会发生缺页中断；
• 当前三个页面进入内存后；缺页3次；内存中为3-2-1
• 访问4号页面，但内存中没有（未命中，发生1次缺页），1号页面淘汰；缺页4次；内存中为4-3-2；
• 访问1号页面，但内存中没有（未命中，发生1次缺页），2号页面淘汰；缺页5次；内存中为1-4-3；
• 访问2号页面，但内存中没有（未命中，发生1次缺页），3号页面淘汰；缺页6次；内存中为2-1-4；
• 访问5号页面，但内存中没有（未命中，发生1次缺页），4号页面淘汰；缺页7次；内存中为5-2-1；
• 访问1号页面，内存中有（命中，不发生缺页中断），没有页面淘汰；缺页7次；内存中为5-2-1；
• 访问2号页面，内存中有（命中，不发生缺页中断），没有页面淘汰；缺页7次；内存中为5-2-1；
• 访问3号页面，但内存中没有（未命中，发生1次缺页），1号页面淘汰；缺页8次；内存中为3-5-2；
• 访问4号页面，但内存中没有（未命中，发生1次缺页），2号页面淘汰；缺页9次；内存中为4-3-5；
• 访问5号页面，内存中有（命中，不发生缺页中断），没有页面淘汰；缺页9次；内存中为4-3-5；
• 共缺页9次

Belady 异常
当上题中的内存块数增加到4个时，其置换表为：

• 此时缺页10次，印证了Belady 异常的内存块增加缺页次数也不会一定减小。

最近最少使用算法（least recently used，LRU）

算法思想

• 淘汰最后一次访问时间距离当前时间间隔最长的页面。

特点

• FIFO算法和OPT算法之间的主要差别是，FIFO算法利用页面进入内存后的时间长短作为置换依据，而OPT算法的依据是将来使用页面的时间。

例题

在虚拟存储器系统采用页式内存管理，使用LRU页面替换算法，考虑下面的页面访问地址流（每次访问在一个时间单位内完成）：1、8、1、7、8、2、7、2、1、8、3、8、2、1、3、1、7、1、3、7
假定内存容量为4个页面，开始时是空的，则页面失效次数是_____。

共缺页6次；

• 这里我是将4个物理块当成一个队列，只要某个页面重新调用了，就把它又放到最上面，然后一直往下压，最下面的物理块4就会被淘汰掉。然后循环。这样就不用一直记住是哪一个是未使用时间最长的了。

资料参考

• 《计算机操作系统教程》（第四版 编著：左万利 王英）
• 百度百科：页面置换算法FIFO 、LRU求缺页中断次数
• 百度百科：页面置换算法

OS 页面置换算法(OPT,FIFO,LRU)颠簸/抖动

介绍

置换算法

• 置换算法（replacement algorithm）又称为淘汰算法、替换算法，用于确定页面的调出原则。
• 在地址映射过程中，若在页面中发现所要访问的页面不在内存中，则产生缺页中断。当发生缺页中断时，如果操作系统内存中没有空闲页面，则操作系统必须在内存选择一个页面将其移出内存，以便为即将调入的页面让出空间。而用来选择淘汰哪一页的规则叫做页面置换算法。
• 在页面置换算法中主要需要掌握的是 先进先出算法(FIFO) 和 最近最少使用算法(LRU)。

颠簸 / 抖动

• 颠簸（thrashing）又称“抖动”，是指页面在内存与外存储器之间频繁地调度，以致系统用于调度页面的时间比进程实际运行所占用的时间还要长。
• 颠簸是由于页故障率过高而产生的结果，它将严重地影响系统的效率，甚至可能使系统全面崩溃。
• 通俗来讲就是一个进程的页面放入内存中，被淘汰出去后，进程又需要使用这个页面然后重新把他放入内存的过程。即你把我赶走之后，又叫我回来。

最佳算法（optimal，OPT）

算法思想

• 从理论上来讲，最佳算法是淘汰以后不再需要的或者在最长的时间以后才会用到的页面。
• 当要调入一新页而必须淘汰一旧页时，所淘汰的页是以后不再使用的，或者是以后相当长的时间内不会使用的。

特点

• 这是一种理想情况下的页面置换算法，页面故障率最低，但实际上不可能实现。
• 这是因为无法准确的预期页面“将来”的被访问情况。

例子

• 假设内存中为一个进程分配3个物理页框，开始时内存页框为空，页面置换情况如下所示：

• 缺页故障次数为9
• 缺页率 = 缺页次数 / 访问次数 = 9 / 20 = 45%

关于图的解释将在下面的例题中进行叙述。

先进先出算法（first-in first-out，FIFO）

算法思想

• 总是选择在主存中停留时间最长（即最老）的一页置换，即先进入内存的页，先退出内存。
• 实质是：淘汰在内存中驻留时间最长的的页面。
• 理由是：最早调入内存的页面，不再被使用的可能性比近期调入内存的大。

特点

• 这种算法只是在按线性顺序访问地址空间时才是理想的，否则效率不高。
• 算法简单，但执行效率不高。
• FIFO的另一个缺点是，它有一种异常现象（Belady 异常），即在增加存储块的情况下，反而使缺页中断率增加了。当然，导致这种异常现象的页面走向实际上是很少见的。

例题

在一个请求分页系统中，假设系统分配给某进程的物理块数为3，开始时内存为空，执行如下访问页号序列： 1，2，3，4，1，2，5，1，2，3，4，5 。

注意：上表的数据要竖着看，一列一列的看，不要横向看。
这里为了方便理解，淘汰的页面我是吧页号写在上面了，而3个X是未命中，但没有淘汰页面。后面我会统一用红X来表示发生缺页中断。
引用串：最上方灰色部分，是访问页号序列，即需要调用的页面号；
物理块：中间绿色部分，是系统分配给某进程的物理块数；
缺页：最下方红色部分，是系统发生缺页故障的次数；
/------------------------------------------------------------------------------/
访问的页在内存中，则称访问成功，否则为失败发生缺页中断。

• 缺页中断次数 = 9
• 过程：
• 开始时内存为空，前三个页面每次进入都会发生缺页中断；
• 当前三个页面进入内存后；缺页3次；内存中为3-2-1
• 访问4号页面，但内存中没有（未命中，发生1次缺页），1号页面淘汰；缺页4次；内存中为4-3-2；
• 访问1号页面，但内存中没有（未命中，发生1次缺页），2号页面淘汰；缺页5次；内存中为1-4-3；
• 访问2号页面，但内存中没有（未命中，发生1次缺页），3号页面淘汰；缺页6次；内存中为2-1-4；
• 访问5号页面，但内存中没有（未命中，发生1次缺页），4号页面淘汰；缺页7次；内存中为5-2-1；
• 访问1号页面，内存中有（命中，不发生缺页中断），没有页面淘汰；缺页7次；内存中为5-2-1；
• 访问2号页面，内存中有（命中，不发生缺页中断），没有页面淘汰；缺页7次；内存中为5-2-1；
• 访问3号页面，但内存中没有（未命中，发生1次缺页），1号页面淘汰；缺页8次；内存中为3-5-2；
• 访问4号页面，但内存中没有（未命中，发生1次缺页），2号页面淘汰；缺页9次；内存中为4-3-5；
• 访问5号页面，内存中有（命中，不发生缺页中断），没有页面淘汰；缺页9次；内存中为4-3-5；
• 共缺页9次

Belady 异常
当上题中的内存块数增加到4个时，其置换表为：

• 此时缺页10次，印证了Belady 异常的内存块增加缺页次数也不会一定减小。

最近最少使用算法（least recently used，LRU）

算法思想

• 淘汰最后一次访问时间距离当前时间间隔最长的页面。

特点

• FIFO算法和OPT算法之间的主要差别是，FIFO算法利用页面进入内存后的时间长短作为置换依据，而OPT算法的依据是将来使用页面的时间。

例题

在虚拟存储器系统采用页式内存管理，使用LRU页面替换算法，考虑下面的页面访问地址流（每次访问在一个时间单位内完成）：1、8、1、7、8、2、7、2、1、8、3、8、2、1、3、1、7、1、3、7
假定内存容量为4个页面，开始时是空的，则页面失效次数是_____。

共缺页6次；

• 这里我是将4个物理块当成一个队列，只要某个页面重新调用了，就把它又放到最上面，然后一直往下压，最下面的物理块4就会被淘汰掉。然后循环。这样就不用一直记住是哪一个是未使用时间最长的了。

资料参考

• 《计算机操作系统教程》（第四版 编著：左万利 王英）
• 百度百科：页面置换算法FIFO 、LRU求缺页中断次数
• 百度百科：页面置换算法