在一个请求分页系统中，采用 LRU 页面置换算法时，假如一个作业的页面走向为 1,3,2,1,1,3,5,1,3,2,1,5。当分配给该作业的物理块数分别为 3 和 4 时，则在访问过程中所发生的缺页率分别为（ ）。

A. 50%、33% B. 25%、100% C. 25%、33% D. 50%、75%

缺页异常

[tag_link]

正确答案：A

首先计算物理块数为 3 时的缺页率。

采用 LRU 算法，模拟访问过程：初始物理块为空，页面走向为

$$1,3,2,1,1,3,5,1,3,2,1,5$$

当物理块数为 3 时，访问过程中缺页发生情况如下：

• 访问 1、3、2 时均缺页（加载页面）； >
• 访问第 4 个页面 1 时命中； >
• 第 5 个页面 1 命中； >
• 第 6 个页面 3 命中； >
• 第 7 个页面 5 缺页（置换最近最少使用的页面 2）； >
• 第 8 个页面 1 命中； >
• 第 9 个页面 3 命中； >
• 第 10 个页面 2 缺页（置换页面 5）； >
• 第 11 个页面 1 命中； >
• 第 12 个页面 5 缺页（置换页面 3）。 >

总计缺页次数为 6 次，总访问次数为 12 次，缺页率为

$$\frac{6}{12}=50\%$$

再计算物理块数为 4 时的缺页率。

物理块数为 4 时，模拟过程如下：

• 访问 1、3、2 时均缺页（加载页面）； >
• 访问第 4 个页面 1 命中； >
• 第 5 个页面 1 命中； >
• 第 6 个页面 3 命中； >
• 第 7 个页面 5 缺页（此时物理块未满，加载页面 5）； >
• 之后第 8 至 12 个页面 $1,3,2,1,5$ 均在物理块中命中。 >

总计缺页次数为 4 次，总访问次数为 12 次，缺页率约为

$$\frac{4}{12}\approx 33\%$$

因此，物理块数 3 和 4 对应的缺页率分别为 $50\%$ 和 $33\%$ ，对应选项 A。