最近最久未使用 ( LRU ) 算法 只有FIFO 算法可能出现 Belady 异常，而OPT 算法和 LRU 算法永远不会出现此类异常。 图3.23 Belady 异常 物理块1 3 3 3 0 0 0 4 4 4 物理块2 2 2 2 3 3 3 1 1 物理块3 1 1 1 2 2 2 0 缺页否 √ √ √ √ √ 物理块1。 3 3 3 3 4 4 4 4 0 0 物理块2. 2 2 2 2 3 3 3 3 4 物理块3。 1 1 1 1 2 2 2 2 物理块4. 0 0 0 0 1 1 1 缺页否 √ √ √ √ √ √ √ √ √ √ 访问页面 0 2 值得注意的是，FIFO 算法存在一种反直觉现象：当为进程分配的物理块数增加时，缺页次 数反而可能上升，这一现象称为Belady 异常。其根本原因在于FIFO 仅依据调入时间决策，而忽 略了页面的实际使用情况。例如，页面访问需列为3,2,1,0,3,2,4,3,2,1,0,4,当分配3个物理 块时，缺页次数为9次；当分配4个物理块时，缺页次数反而增至10次，如图3.23所示。 图3.22 FIFO 算法的置换图 物理块1 7 7 7 2 2 2 4 4 4 0 0 0 7 7 7 物理块2 0 0 0 3 3 3 2 2 2 1 1 1 0 0 物理块3 1 1 1 0 0 0 3 3 3 2 2 2 1 缺页否 √ √ √ √ √ √ √ √ √ √ 访问页面 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 仍用上面的例子，采用FIFO 算法进行置换。当访问页面2时发生缺页，淘汰最早进入的页 面7。随后访问页面3时再次缺页，此时将2,0,1中最先进入的页面0换出……以此类推，具体 过程如图3.22所示。可见，共发生15次缺页中断，其中12次触发页面置换。 考点追踪 FIFO 算法的应用分析(2010) 先进先出页面置换算法选择淘汰最早进入内存的页面。该算法实现简单，将内存中的页面按 调入时间组织成一个队列，需要换出时直接移除队首页面。然而，FIFO 算法未利用局部性原理， 与进程实际运行规律不符，最早装入的页面仍可能被频繁访问，因此性能通常较差。

[tag_link]

正确答案：【解答】