【操作系统】页面置换算法
目录
页面置换算法
最佳置换算法（OPT）
其核心思想是选择被淘汰页面将是以后永不使用的，或在最长（未来）时间内不再被访问的页面。
例题：在一个请求分页系统中，采用最佳页面置换算法时，假如一个作业的页面走向为4、3、2、1、4、3、5、4、3、2、1、5，当分配给该作业的物理块数M为3（或4）时，试计算在访问过程中所发生的缺页次数和缺页率。请给出分析过程。
物理块为3时：
4 3 2 1 4 3 5 4 3 2 1 5
| 4 | 4 | 4 | 4 | 4 | 2 | 2 | |||||
| 3 | 3 | 3 | 3 | 3 | 1 | ||||||
| 2 | 1 | 5 | 5 | 5 |
缺页次数为7次，缺页率为f = 7/12 发生了4次缺页中断
置换次数为4次
采用最佳置换算法，保证最低的缺页率。
先入先出置换算法（FIFO）
其核心思想是淘汰最先进入的页面。
例题：在一个请求分页系统中，采用先进先出置换算法时，假如一个作业的页面走向为4、3、2、1、4、3、5、4、3、2、1、5，当分配给该作业的物理块数M为3（或4）时，试计算在访问过程中所发生的缺页次数和缺页率。请给出分析过程。
物理块为3时：
4 3 2 1 4 3 5 4 3 2 1 5
| 4 | 4 | 4 | 1 | 1 | 1 | 5 | 5 | 5 | |||
| 3 | 3 | 3 | 4 | 4 | 4 | 2 | 2 | ||||
| 2 | 2 | 2 | 3 | 3 | 3 | 1 |
缺页次数为9次，缺页率为9/12
置换次数为6次
最近最久未使用算法（LRU）
其核心思想为选择最近（的过去）最久未使用的页面予以淘汰。
例题：在一个请求分页系统中，采用最近最久未使用页面置换算法时，假如一个作业的页面走向为4、3、2、1、4、3、5、4、3、2、1、5，当分配给该作业的物理块数M为3（或4）时，试计算在访问过程中所发生的缺页次数和缺页率。请给出分析过程。
物理块为3时：
4 3 2 1 4 3 5 4 3 2 1 5
| 4 | 4 | 4 | 1 | 1 | 1 | 5 | 2 | 2 | 2 | ||
| 3 | 3 | 3 | 4 | 4 | 4 | 4 | 1 | 1 | |||
| 2 | 2 | 2 | 3 | 3 | 3 | 3 | 5 |
缺页次数为10次，缺页率为10/12
置换次数为7次
最佳置换和最近最久未使用算法的区别是：最佳置换注重“向后看”（未来），而最近最久未使用算法注重“向前看”（最近的过去）。
附：附上物理块为4时的情况
最佳置换算法：
先进先出算法：
最近最久未使用算法：