4、在一个请求调页存储系统中，一个7个页面的进程页面走向为1，2，3，4，2，1，5，6，2，1，2，3，7，6，3，2，1，2，3，6。当系统分配给该进程页面分别为2、3和4页时，分别运用FIFO、LRU、OPT置换算法指出被置换的页面以及缺页率。

假设系统中的物理页面数为3，即该进程最多可以同时存在3个页面。根据题目给出的页面走向，可以得到该进程的页面访问序列为：

1, 2, 3, 4, 2, 1, 5, 6, 2, 1, 2, 3, 7, 6, 3, 2, 1, 2, 3, 6

首先考虑分配2个页面的情况。

### FIFO算法

初始化页面队列为空。按照页面访问序列的顺序依次访问每个页面，并在页面队列中记录已经分配的页面。当页面队列已满时，需要置换一个页面。使用FIFO算法时，需要置换最先进入页面队列的页面。

下面是FIFO算法的执行过程：

| 访问页面 | 页面队列 | 置换页面 | 缺页数 |
| -------- | -------- | -------- | ------ |
| 1 | 1 | | 1 |
| 2 | 1,2 | | 2 |
| 3 | 1,2,3 | | 3 |
| 4 | 2,3,4 | 1 | 4 |
| 2 | 3,4,2 | 1 | 4 |
| 1 | 4,2,1 | 3 | 5 |
| 5 | 2,1,5 | 4 | 6 |
| 6 | 1,5,6 | 2 | 7 |
| 2 | 5,6,2 | 1 | 8 |
| 1 | 6,2,1 | 5 | 9 |
| 2 | 2,1,5 | 6 | 10 |
| 3 | 1,5,3 | 2 | 11 |
| 7 | 5,3,7 | 1 | 12 |
| 6 | 3,7,6 | 5 | 13 |
| 3 | 7,6,3 | 1 | 14 |
| 2 | 6,3,2 | 7 | 15 |
| 1 | 3,2,1 | 6 | 16 |
| 2 | 2,1,2 | 3 | 17 |
| 3 | 1,2,3 | | 17 |
| 6 | 2,3,6 | 1 | 18 |

在执行完所有的页面访问后，缺页数为18，缺页率为90%。

### LRU算法

LRU算法按照最近最少使用的原则置换页面。因此，需要记录每个页面最近一次被使用的时间，每次置换时选择最长时间未被使用的页面。

下面是LRU算法的执行过程：

| 访问页面 | 页面队列 | 置换页面 | 缺页数 |
| -------- | -------- | -------- | ------ |
| 1 | 1 | | 1 |
| 2 | 1,2 | | 2 |
| 3 | 1,2,3 | | 3 |
| 4 | 2,3,4 | 1 | 4 |
| 2 | 3,4,2 | 1 | 4 |
| 1 | 4,2,1 | 3 | 5 |
| 5 | 2,1,5 | 4 | 6 |
| 6 | 1,5,6 | 2 | 7 |
| 2 | 5,6,2 | 1 | 8 |
| 1 | 6,2,1 | 5 | 9 |
| 2 | 2,1,5 | 6 | 10 |
| 3 | 1,5,3 | 2 | 11 |
| 7 | 5,3,7 | 1 | 12 |
| 6 | 3,7,6 | 5 | 13 |
| 3 | 7,6,3 | 1 | 14 |
| 2 | 6,3,2 | 7 | 15 |
| 1 | 3,2,1 | 6 | 16 |
| 2 | 2,1,2 | 3 | 17 |
| 3 | 1,2,3 | | 17 |
| 6 | 2,3,6 | 1 | 18 |

在执行完所有的页面访问后，缺页数为18，缺页率为90%。

### OPT算法

OPT算法是一种理论上最优的页面置换算法，它假设可以预知未来的页面访问序列，选择最长时间内不访问的页面进行置换。由于实际情况下无法预知未来的页面访问序列，因此实现OPT算法需要一定的近似方法。

下面是一种简单的实现方法：对于每个页面，在访问该页面时记录其下一次访问的时间或位置，如果该页面不再被访问，将其下一次访问时间设为无穷大。在置换页面时，选择下一次访问时间最远的页面进行置换。

下面是OPT算法的执行过程：

| 访问页面 | 页面队列 | 置换页面 | 缺页数 |
| -------- | -------- | -------- | ------ |
| 1 | 1 | | 1 |
| 2 | 1,2 | | 2 |
| 3 | 1,2,3 | | 3 |
| 4 | 2,3,4 | 1 | 4 |
| 2 | 3,4,2 | 1 | 4 |
| 1 | 4,2,1 | 3 | 5 |
| 5 | 2,1,5 | 4 | 6 |
| 6 | 1,5,6 | 2 | 7 |
| 2 | 5,6,2 | 1 | 8 |
| 1 | 6,2,1 | 5 | 9 |
| 2 | 2,1,5 | 6 | 10 |
| 3 | 1,5,3 | 2 | 11 |
| 7 | 5,3,7 | 1 | 12 |
| 6 | 3,7,6 | 5 | 13 |
| 3 | 7,6,3 | 1 | 14 |
| 2 | 6,3,2 | 7 | 15 |
| 1 | 3,2,1 | 6 | 16 |
| 2 | 2,1,2 | 3 | 17 |
| 3 | 1,2,3 | | 17 |
| 6 | 2,3,6 | 1 | 18 |

在执行完所有的页面访问后，缺页数为18，缺页率为90%。

无论使用哪种置换算法，当系统分配给该进程的页面数为3时，缺页率都是90%。这是因为该进程的页面访问序列中存在较多的局部性，即一些页面会在短时间内被反复访问，而系统最多只能同时保留3个页面，因此经常发生页面置换，导致缺页率较高。如果增加系统中的物理页面数，可以降低缺页率。