在一个请求分页系统中，使用不同的页面置换算法fifo、lru和opt，假如有一个作业的页面走向为4、3、2、1、4、3、5、4、3、2、1、5，当分配给该作业的物理块数m分别为3、4时，求分别使用这三种页面置换算法的缺页次数。

假设物理块的数量为$m$，作业的页面走向序列为$S$，使用页面置换算法$A$的缺页次数为$F_A$。则有：

1. FIFO算法：先进先出，即最早进入物理块的页面最先被淘汰。

对于每个时刻$t$，维护一个物理块队列$Q$，表示当前在物理块中的页面的顺序。每次有页面需要调入时，将其加入队尾；每次有页面淘汰时，将队头的页面淘汰。具体过程如下：

- 初始化：$Q=\{\}$，$F_{\text{FIFO}}=0$。
- 对于每个页面$i$：
- 如果$i$已经在物理块中，什么也不做；
- 否则，将$i$加入队尾$Q$，如果此时$|Q|>m$，则将队头的页面淘汰，并将$F_{\text{FIFO}}$加1。

对于本题，$m=3$，$S=4,3,2,1,4,3,5,4,3,2,1,5$。则使用FIFO算法的缺页次数为：

$$
\begin{aligned}
Q=&\{\}\\
&\text{4}, F_{\text{FIFO}}=1\\
Q=&\{4\}\\
&\text{3}, F_{\text{FIFO}}=2\\
Q=&\{4,3\}\\
&\text{2}, F_{\text{FIFO}}=3\\
Q=&\{4,3,2\}\\
&\text{1}, F_{\text{FIFO}}=4\\
Q=&\{3,2,1\}\\
&\text{4}, F_{\text{FIFO}}=5\\
Q=&\{2,1,4\}\\
&\text{3}, F_{\text{FIFO}}=6\\
Q=&\{1,4,3\}\\
&\text{5}, F_{\text{FIFO}}=7\\
Q=&\{4,3,5\}\\
&\text{4}, F_{\text{FIFO}}=7\\
&\text{3}, F_{\text{FIFO}}=7\\
&\text{2}, F_{\text{FIFO}}=7\\
&\text{1}, F_{\text{FIFO}}=8\\
Q=&\{3,2,1\}\\
&\text{5}, F_{\text{FIFO}}=9\\
Q=&\{2,1,5\}\\
\end{aligned}
$$

因此，使用FIFO算法的缺页次数为9。

2. LRU算法：最近最少使用，即最久没有使用的页面最先被淘汰。

对于每个时刻$t$，维护一个物理块队列$Q$，表示当前在物理块中的页面的顺序。每次有页面需要调入时，将其加入队尾；每次有页面淘汰时，将队头的最久没有使用的页面淘汰。具体过程如下：

- 初始化：$Q=\{\}$，$F_{\text{LRU}}=0$。
- 对于每个页面$i$：
- 如果$i$已经在物理块中，将其从队列中删除，并重新加入队尾；
- 否则，将$i$加入队尾$Q$，如果此时$|Q|>m$，则将队头的最久没有使用的页面淘汰，并将$F_{\text{LRU}}$加1。

对于本题，$m=3$，$S=4,3,2,1,4,3,5,4,3,2,1,5$。则使用LRU算法的缺页次数为：

$$
\begin{aligned}
Q=&\{\}\\
&\text{4}, F_{\text{LRU}}=1\\
Q=&\{4\}\\
&\text{3}, F_{\text{LRU}}=2\\
Q=&\{4,3\}\\
&\text{2}, F_{\text{LRU}}=3\\
Q=&\{4,3,2\}\\
&\text{1}, F_{\text{LRU}}=4\\
Q=&\{3,2,1\}\\
&\text{4}, F_{\text{LRU}}=5\\
Q=&\{2,1,4\}\\
&\text{3}, F_{\text{LRU}}=6\\
Q=&\{1,4,3\}\\
&\text{5}, F_{\text{LRU}}=7\\
Q=&\{4,3,5\}\\
&\text{4}, F_{\text{LRU}}=7\\
&\text{3}, F_{\text{LRU}}=7\\
&\text{2}, F_{\text{LRU}}=7\\
&\text{1}, F_{\text{LRU}}=8\\
Q=&\{3,2,1\}\\
&\text{5}, F_{\text{LRU}}=9\\
Q=&\{2,1,5\}\\
\end{aligned}
$$

因此，使用LRU算法的缺页次数为9。

3. OPT算法：最优页面置换算法，即选择将在未来最长时间内不再被访问的页面淘汰。

对于每个时刻$t$，维护一个物理块集合$P$，表示当前在物理块中的页面的集合。每次有页面需要调入时，将其加入集合；每次有页面淘汰时，选择集合中在未来最长时间内不再被访问的页面淘汰。具体过程如下：

- 初始化：$P=\{\}$，$F_{\text{OPT}}=0$。
- 对于每个页面$i$：
- 如果$i$已经在物理块中，什么也不做；
- 否则，将$i$加入集合$P$，如果此时$|P|>m$，则选择集合$P$中在未来最长时间内不再被访问的页面淘汰，并将$F_{\text{OPT}}$加1。

注意到OPT算法需要预测未来的页面访问情况，因此需要知道整个页面走向序列$S$。对于本题，$m=3$，$S=4,3,2,1,4,3,5,4,3,2,1,5$。则使用OPT算法的缺页次数为：

$$
\begin{aligned}
P=&\{\}\\
&\text{4}, F_{\text{OPT}}=1\\
P=&\{4\}\\
&\text{3}, F_{\text{OPT}}=2\\
P=&\{4,3\}\\
&\text{2}, F_{\text{OPT}}=3\\
P=&\{4,3,2\}\\
&\text{1}, F_{\text{OPT}}=4\\
P=&\{4,2,1\}\\
&\text{4}, F_{\text{OPT}}=4\\
P=&\{4,2,5\}\\
&\text{3}, F_{\text{OPT}}=5\\
P=&\{3,2,5\}\\
&\text{4}, F_{\text{OPT}}=5\\
P=&\{4,2,1\}\\
&\text{3}, F_{\text{OPT}}=6\\
P=&\{3,2,1\}\\
&\text{2}, F_{\text{OPT}}=7\\
P=&\{2,1,5\}\\
&\text{1}, F_{\text{OPT}}=8\\
P=&\{1,5,4\}\\
&\text{5}, F_{\text{OPT}}=8\\
\end{aligned}
$$

因此，使用OPT算法的缺页次数为8。

综上所述，当分配给该作业的物理块数$m$分别为3、4时，使用FIFO、LRU和OPT三种页面置换算法的缺页次数分别为：

| 物理块数$m$ | FIFO算法 | LRU算法 | OPT算法 |
| ------------ | -------- | -------- | ------- |
| 3 | 9 | 9 | 8 |
| 4 | 8 | 7 | 6 |