假设一个物理存储器，有 4 个页框，对下面每种策略，给出引用串： P1、p2、p3、p1、p4、p5、p1、p2、p1、p4、p5、p3、p4、p5 的缺页数目（所有页框最初都是空的，假设所有对页面 p2 的访问都是写请求）。试用下列算 法求出缺页异常次数：(a)OPT、(b)FIFO、(c)SCR、(d)改进的 CLOCK、(e)LRU、(f)MIN(滑 动窗口 τ＝3)、(g)WS(工作集窗口尺寸△＝2)

下面分别给出这些算法的缺页数计算过程：

(a) OPT（最优置换算法）

| 页框 | p1 | p2 | p3 | p4 | 缺页数 |
| ---- | --- | --- | --- | --- | ------ |
| 1 | p1 | | | | 1 |
| 2 | p1 | p2 | | | 1 |
| 3 | p1 | p2 | p3 | | 2 |
| 4 | p4 | p2 | p3 | p1 | 3 |
| 2 | p4 | p2 | p3 | p1 | 3 |
| 1 | p5 | p2 | p3 | p1 | 4 |
| 1 | p5 | p2 | p3 | p1 | 4 |
| 2 | p5 | p1 | p3 | p2 | 5 |
| 2 | p5 | p1 | p3 | p2 | 5 |
| 4 | p5 | p3 | p1 | p4 | 6 |
| 3 | p5 | p3 | p2 | p4 | 7 |
| 4 | p5 | p3 | p2 | p1 | 8 |
| 3 | p5 | p4 | p2 | p1 | 9 |
| 2 | p5 | p4 | p3 | p1 | 10 |
| 2 | p5 | p4 | p3 | p1 | 10 |

因此，OPT算法的缺页数是10。

(b) FIFO（先进先出算法）

| 页框 | p1 | p2 | p3 | p4 | 缺页数 |
| ---- | --- | --- | --- | --- | ------ |
| 1 | p1 | | | | 1 |
| 2 | p1 | p2 | | | 1 |
| 3 | p1 | p2 | p3 | | 2 |
| 4 | p4 | p2 | p3 | p1 | 3 |
| 1 | p4 | p2 | p3 | p1 | 3 |
| 2 | p5 | p2 | p3 | p1 | 4 |
| 3 | p5 | p2 | p3 | p4 | 5 |
| 4 | p5 | p2 | p3 | p1 | 6 |
| 1 | p4 | p2 | p3 | p1 | 6 |
| 2 | p5 | p4 | p3 | p1 | 7 |
| 3 | p5 | p4 | p2 | p1 | 8 |
| 4 | p5 | p4 | p2 | p3 | 9 |
| 1 | p1 | p4 | p2 | p3 | 10 |
| 2 | p1 | p4 | p3 | p2 | 11 |

因此，FIFO算法的缺页数是11。

(c) SCR（二次机会算法）

| 页框 | p1 | p2 | p3 | p4 | 缺页数 |
| ---- | --- | --- | --- | --- | ------ |
| 1 | p1 | | | | 1 |
| 2 | p1 | p2 | | | 1 |
| 3 | p1 | p2 | p3 | | 2 |
| 4 | p4 | p2 | p3 | p1 | 3 |
| 1 | p4 | p2 | p3 | p1 | 3 |
| 2 | p5 | p2 | p3 | p1 | 4 |
| 3 | p5 | p2 | p3 | p4 | 5 |
| 4 | p5 | p2 | p3 | p1 | 6 |
| 1 | p5 | p2 | p3 | p1 | 6 |
| 2 | p5 | p1 | p3 | p2 | 7 |
| 3 | p5 | p1 | p3 | p4 | 7 |
| 4 | p5 | p1 | p3 | p2 | 7 |
| 1 | p4 | p1 | p3 | p2 | 8 |
| 2 | p4 | p5 | p3 | p2 | 8 |

因此，SCR算法的缺页数是8。

(d) 改进的 CLOCK

| 页框 | p1 | p2 | p3 | p4 | 缺页数 |
| ---- | --- | --- | --- | --- | ------ |
| 1 | p1 | | | | 1 |
| 2 | p1 | p2 | | | 1 |
| 3 | p1 | p2 | p3 | | 2 |
| 4 | p4 | p2 | p3 | p1 | 3 |
| 1 | p4 | p2 | p3 | p1 | 3 |
| 2 | p5 | p2 | p3 | p1 | 4 |
| 3 | p5 | p2 | p3 | p4 | 5 |
| 4 | p5 | p2 | p3 | p1 | 6 |
| 1 | p5 | p2 | p3 | p1 | 6 |
| 2 | p5 | p1 | p3 | p2 | 7 |
| 3 | p5 | p1 | p3 | p4 | 7 |
| 4 | p5 | p1 | p3 | p2 | 7 |
| 1 | p4 | p1 | p3 | p2 | 8 |
| 2 | p4 | p5 | p3 | p2 | 8 |

因此，改进的 CLOCK算法的缺页数是8。

(e) LRU（最近最久未使用算法）

| 页框 | p1 | p2 | p3 | p4 | 缺页数 |
| ---- | --- | --- | --- | --- | ------ |
| 1 | p1 | | | | 1 |
| 2 | p1 | p2 | | | 1 |
| 3 | p1 | p2 | p3 | | 2 |
| 4 | p4 | p2 | p3 | p1 | 3 |
| 1 | p4 | p2 | p3 | p1 | 3 |
| 2 | p5 | p2 | p3 | p1 | 4 |
| 3 | p5 | p2 | p3 | p4 | 5 |
| 4 | p5 | p1 | p3 | p4 | 6 |
| 1 | p5 | p1 | p2 | p4 | 7 |
| 2 | p1 | p5 | p2 | p4 | 8 |
| 3 | p1 | p5 | p3 | p4 | 9 |
| 4 | p1 | p5 | p3 | p2 | 10 |
| 1 | p4 | p5 | p3 | p2 | 11 |
| 2 | p4 | p5 | p1 | p2 | 12 |

因此，LRU算法的缺页数是12。

(f) MIN（滑动窗口 τ＝3）

| 页框 | p1 | p2 | p3 | p4 | 缺页数 |
| ---- | --- | --- | --- | --- | ------ |
| 1 | p1 | | | | 1 |
| 2 | p1 | p2 | | | 1 |
| 3 | p1 | p2 | p3 | | 2 |
| 4 | p4 | p2 | p3 | p1 | 3 |
| 1 | p4 | p2 | p3 | p1 | 3 |
| 2 | p5 | p2 | p3 | p1 | 4 |
| 3 | p5 | p2 | p3 | p4 | 5 |
| 4 | p5 | p1 | p3 | p4 | 6 |
| 1 | p5 | p1 | p2 | p4 | 7 |
| 2 | p1 | p5 | p2 | p4 | 8 |
| 3 | p1 | p5 | p3 | p4 | 8 |
| 4 | p1 | p5 | p3 | p2 | 9 |
| 1 | p4 | p5 | p3 | p2 | 10 |
| 2 | p4 | p5 | p1 | p2 | 11 |

因此，MIN算法的缺页数是11。

(g) WS（工作集窗口尺寸△＝2）

| 页框 | p1 | p2 | p3 | p4 | 缺页数 |
| ---- | --- | --- | --- | --- | ------ |
| 1 | p1 | | | | 1 |
| 2 | p1 | p2 | | | 1 |
| 3 | p1 | p2 | p3 | | 2 |
| 4 | p4 | p2 | p3 | p1 | 3 |
| 2 | p4 | p2 | p3 | p1 | 3 |
| 1 | p5 | p2 | p3 | p1 | 4 |
| 1 | p5 | p2 | p3 | p1 | 4 |
| 2 | p5 | p1 | p3 | p2 | 5 |
| 2 | p5 | p1 | p3 | p2 | 5 |
| 4 | p5 | p3 | p1 | p4 | 6 |
| 4 | p5 | p3 | p1 | p4 | 6 |
| 4 | p5 | p3 | p1 | p4 | 6 |
| 4 | p5 | p3 | p1 | p4 | 6 |
| 4 | p5 | p3 | p1 | p4 | 6 |

因此，WS算法的缺页数是6。