在一个请求页式存储管理系统中，一个程序的页面走向是： 6，5，4，3，2，1，5，4，3，6，5，4，3，2，1，6，5 请分别采用FIFO 算法和LRU 算法，求出在作业分得的内存块数分别为M=4 和M=5 时， 缺页中断次数和缺页率各为多少？

假设请求队列为Q，内存块数为M，缺页中断次数为P，页面总数为N，则缺页率= P/N。

首先，我们需要将请求队列按照时间顺序分配到内存块中，以便于后续的缺页中断次数计算。

当M=4时：

### FIFO算法：

| 请求页面 | 内存块状态 | 缺页中断 | 缺页率 |
| -------- | ---------- | -------- | ------ |
| 6 | 6 | 1 | 1/1 |
| 5 | 6 5 | 1 | 2/2 |
| 4 | 6 5 4 | 1 | 3/3 |
| 3 | 6 5 4 3 | 1 | 4/4 |
| 2 | 5 4 3 2 | 1 | 5/5 |
| 1 | 4 3 2 1 | 1 | 6/6 |
| 5 | 4 3 2 1 | 0 | 6/7 |
| 4 | 4 3 2 1 | 0 | 6/8 |
| 3 | 4 3 2 1 | 0 | 6/9 |
| 6 | 3 2 1 6 | 1 | 7/10 |
| 5 | 2 1 6 5 | 1 | 8/11 |
| 4 | 1 6 5 4 | 1 | 9/12 |
| 3 | 6 5 4 3 | 1 | 10/13 |
| 2 | 5 4 3 2 | 0 | 10/14 |
| 1 | 4 3 2 1 | 0 | 10/15 |
| 6 | 3 2 1 6 | 0 | 10/16 |
| 5 | 2 1 6 5 | 0 | 10/17 |

因此，当M=4时，FIFO算法的缺页中断次数为10，缺页率为10/17。

### LRU算法：

| 请求页面 | 内存块状态 | 缺页中断 | 缺页率 |
| -------- | ---------- | -------- | ------ |
| 6 | 6 | 1 | 1/1 |
| 5 | 6 5 | 1 | 2/2 |
| 4 | 6 5 4 | 1 | 3/3 |
| 3 | 6 5 4 3 | 1 | 4/4 |
| 2 | 5 4 3 2 | 1 | 5/5 |
| 1 | 4 3 2 1 | 1 | 6/6 |
| 5 | 4 3 2 5 | 1 | 7/7 |
| 4 | 4 3 4 5 | 1 | 8/8 |
| 3 | 4 3 4 3 | 1 | 9/9 |
| 6 | 3 4 6 3 | 1 | 10/10 |
| 5 | 4 6 5 3 | 1 | 11/11 |
| 4 | 6 5 4 3 | 1 | 12/12 |
| 3 | 6 5 4 3 | 0 | 12/13 |
| 2 | 5 4 3 2 | 1 | 13/14 |
| 1 | 4 3 2 1 | 1 | 14/15 |
| 6 | 3 2 1 6 | 1 | 15/16 |
| 5 | 2 1 6 5 | 1 | 16/17 |

因此，当M=4时，LRU算法的缺页中断次数为15，缺页率为15/17。

当M=5时：

### FIFO算法：

| 请求页面 | 内存块状态 | 缺页中断 | 缺页率 |
| -------- | ----------- | -------- | ------ |
| 6 | 6 | 1 | 1/1 |
| 5 | 6 5 | 1 | 2/2 |
| 4 | 6 5 4 | 1 | 3/3 |
| 3 | 6 5 4 3 | 1 | 4/4 |
| 2 | 5 4 3 2 6 | 1 | 5/5 |
| 1 | 4 3 2 1 6 | 1 | 6/6 |
| 5 | 4 3 2 1 5 | 1 | 7/7 |
| 4 | 3 2 1 5 4 | 1 | 8/8 |
| 3 | 2 1 5 4 3 | 1 | 9/9 |
| 6 | 1 5 4 3 6 | 1 | 10/10 |
| 5 | 5 4 3 6 5 | 0 | 10/11 |
| 4 | 4 3 6 5 4 | 0 | 10/12 |
| 3 | 3 6 5 4 3 | 0 | 10/13 |
| 2 | 6 5 4 3 2 | 1 | 11/14 |
| 1 | 5 4 3 2 1 | 1 | 12/15 |
| 6 | 4 3 2 1 6 | 1 | 13/16 |
| 5 | 3 2 1 6 5 | 1 | 14/17 |

因此，当M=5时，FIFO算法的缺页中断次数为14，缺页率为14/17。

### LRU算法：

| 请求页面 | 内存块状态 | 缺页中断 | 缺页率 |
| -------- | ----------- | -------- | ------ |
| 6 | 6 | 1 | 1/1 |
| 5 | 6 5 | 1 | 2/2 |
| 4 | 6 5 4 | 1 | 3/3 |
| 3 | 6 5 4 3 | 1 | 4/4 |
| 2 | 5 4 3 2 6 | 1 | 5/5 |
| 1 | 4 3 2 1 5 | 1 | 6/6 |
| 5 | 3 2 1 5 4 | 1 | 7/7 |
| 4 | 2 1 5 4 3 | 1 | 8/8 |
| 3 | 1 5 4 3 2 | 1 | 9/9 |
| 6 | 5 4 3 2 6 | 1 | 10/10 |
| 5 | 4 3 2 6 5 | 0 | 10/11 |
| 4 | 3 2 6 5 4 | 1 | 11/12 |
| 3 | 2 6 5 4 3 | 0 | 11/13 |
| 2 | 6 5 4 3 2 | 0 | 11/14 |
| 1 | 5 4 3 2 1 | 1 | 12/15 |
| 6 | 4 3 2 1 6 | 1 | 13/16 |
| 5 | 3 2 1 6 5 | 0 | 13/17 |

因此，当M=5时，LRU算法的缺页中断次数为13，缺页率为13/17。