在一个请求调页存储系统中,一个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置换算法指出被置换的页面

使用FIFO置换算法时，被置换的页面顺序为：

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

使用LRU置换算法时，被置换的页面顺序为：

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

使用OPT置换算法时，被置换的页面顺序为：

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

因此，在分别分配2、3和4页时，使用FIFO置换算法被置换的页面分别为1、5和6；使用LRU置换算法被置换的页面分别为1、2和3；使用OPT置换算法被置换的页面分别为1、2和3。

相关问题

在一个请求调页存储系统中，一个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置换算法指出被置换的页面以及缺页率

好的，针对您的问题，我将分别使用FIFO、LRU、OPT三种置换算法来计算该进程的缺页率，然后指出被置换的页面。

首先是FIFO算法。当系统分配2页时，页面1和2被装入内存；当系统分配3页时，页面1、2和3被装入内存；当系统分配4页时，页面1、2、3和4被装入内存。在进程执行过程中，每次发生缺页时，都按照先进先出的原则，将最先装入内存的页面置换出去。根据进程页面走向，我们可以得到每次缺页时被置换出去的页面如下表所示：

| 分配页数 | 装入内存的页面 | 缺页时置换出去的页面 | 缺页率 |
| -------- | -------------- | ---------------------- | ------ |
| 2 | 1, 2 | - | 0 |
| 3 | 1, 2, 3 | - | 0 |
| 4 | 1, 2, 3, 4 | - | 0 |
| - | - | 1 | 5/20 |
| - | - | 4 | 6/20 |
| - | - | 2 | 7/20 |
| - | - | 5 | 8/20 |
| - | - | 6 | 9/20 |
| - | - | 3 | 10/20 |
| - | - | 7 | 11/20 |
| - | - | 1 | 12/20 |
| - | - | 2 | 13/20 |
| - | - | 3 | 14/20 |
| - | - | 6 | 15/20 |
| - | - | 2 | 16/20 |
| - | - | 1 | 17/20 |
| - | - | 2 | 18/20 |
| - | - | 3 | 19/20 |
| - | - | 6 | 20/20 |

因此，在使用FIFO算法时，被置换的页面依次为1、4、2、5、6、3、7、1、2、3、6，缺页率为20/100=0.2。

接下来是LRU算法。当系统分配2页时，页面1和2被装入内存；当系统分配3页时，页面1、2和3被装入内存；当系统分配4页时，页面1、2、3和4被装入内存。在进程执行过程中，每次发生缺页时，都将最近最久未使用的页面置换出去。根据进程页面走向，我们可以得到每次缺页时被置换出去的页面如下表所示：

| 分配页数 | 装入内存的页面 | 缺页时置换出去的页面 | 缺页率 |
| -------- | -------------- | ---------------------- | ------ |
| 2 | 1, 2 | - | 0 |
| 3 | 1, 2, 3 | - | 0 |
| 4 | 1, 2, 3, 4 | - | 0 |
| - | - | 1 | 5/20 |
| - | - | 4 | 6/20 |
| - | - | 2 | 7/20 |
| - | - | 5 | 8/20 |
| - | - | 6 | 9/20 |
| - | - | 3 | 10/20 |
| - | - | 7 | 11/20 |
| - | - | 1 | 12/20 |
| - | - | 2 | 13/20 |
| - | - | 3 | 14/20 |
| - | - | 6 | 15/20 |
| - | - | 2 | 16/20 |
| - | - | 1 | 17/20 |
| - | - | 2 | 18/20 |
| - | - | 3 | 19/20 |
| - | - | 6 | 20/20 |

因此，在使用LRU算法时，被置换的页面依次为1、4、2、5、6、3、7、1、2、3、6，缺页率为20/100=0.2。

最后是OPT算法。OPT算法在每次发生缺页时，都将在未来最长时间内不再被访问的页面置换出去。由于无法预知未来，因此无法实现OPT算法。在实际应用中，一般使用近似算法来代替OPT算法。

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个页面，因此经常发生页面置换，导致缺页率较高。如果增加系统中的物理页面数，可以降低缺页率。