核心结论:FIFO 是先进先出页面置换算法,缺页率计算公式是 缺页次数 ÷ 页面访问总次数 ×100%。做题第一步先根据页面访问序列,按照先进先出规则,把最先进入内存的页面在内存满的时候淘汰,统计一共发生多少次缺页,再代入公式算出缺页率,同时还要区分首次调入内存也算缺页,这个是考试最容易丢分的点。

核心公式

缺页率 = 缺页总次数 / 页面访问总次数 × 100%

补充配套概念

命中率 = 1 − 缺页率

缺页中断:访问的页面不在内存,需要从外存调入内存,记为一次缺页

命中:访问页面已经存在内存,不产生缺页

FIFO 算法执行规则

内存分配固定数量页框,也就是物理块数

1 访问页面,如果页面不在内存,发生缺页,把该页面调入内存

2 如果内存物理块已经占满,淘汰最早进入内存的那一页,新页面放入,队列更新

3 如果页面已经在内存,属于命中,不置换,队列顺序保持不变

特点:只看进入内存先后顺序,不考虑页面最近使用情况,会出现 Belady 异常,也就是物理块增加,缺页次数反而变多,这个是 FIFO 独有的考点。

完整例题演示

页面访问序列:1,2,3,4,1,2,5,1,2,3,4,5

物理块数 = 3

逐步推演

1 访问 1,内存空,缺页,内存 [1]

2 访问 2,缺页,内存 [1,2]

3 访问 3,缺页,内存 [1,2,3] 内存已满

4 访问 4,缺页,淘汰最先进入的 1,内存 [2,3,4]

5 访问 1,缺页,淘汰 2,内存 [3,4,1]

6 访问 2,缺页,淘汰 3,内存 [4,1,2]

7 访问 5,缺页,淘汰 4,内存 [1,2,5]

8 访问 1,命中

9 访问 2,命中

10 访问 3,缺页,淘汰 1,内存 [2,5,3]

11 访问 4,缺页,淘汰 2,内存 [5,3,4]

12 访问 5,命中

统计:缺页一共 9 次,总访问次数 12 次

缺页率 = 9 / 12 ×100% = 75%

做题易错点

1 初始内存为空,前面几次页面调入全部算缺页,很多同学会漏掉初始缺页

2 已经在内存的页面再次访问,只是命中,不会改变 FIFO 队列顺序,这个和 LRU 不一样

3 Belady 异常,FIFO 是唯一会出现 Belady 异常的经典置换算法,选择题高频考点

4 题目如果问置换次数,注意区分,有些题目置换次数 = 缺页次数 − 初始装入内存的页面数量,要看题干表述,不要和缺页次数混淆

【常见问题】

问题 1 fifo 算法缺页率怎么算,FIFO 和 LRU 缺页率计算方法一样吗

回答 1 fifo 算法缺页率怎么算,缺页率公式是相同的,都是缺页次数除以总访问次数,差别是置换淘汰规则不同,FIFO 淘汰最先进入页面,LRU 淘汰最近最久未使用页面,推演过程不一样。

问题 2 fifo 算法缺页率怎么算,什么是 Belady 异常

回答 2 fifo 算法缺页率怎么算,Belady 异常就是增加物理块数量之后,FIFO 算法缺页次数反而上升,这是 FIFO 特有现象,LRU 不会出现。

问题 3 fifo 算法缺页率怎么算,页面已经在内存的时候要不要重新排队

回答 3 fifo 算法缺页率怎么算,FIFO 命中的时候页面已经在内存,不改变队列先后顺序,不需要重新排到队尾。

问题 4 fifo 算法缺页率怎么算,缺页次数和置换次数是同一个数字吗

回答 4 fifo 算法缺页率怎么算,不一定,缺页包含初始调入,置换次数是内存装满之后发生淘汰的次数,需要看题目定义,考试审题要留意。

免责申明:本文为操作系统考研与期末统考知识点讲解,例题为标准题型演示,考试答题以教材和题目给定条件为准。