操作系统基础39-FIFO页面置换

操作系统基础39-FIFO页面置换

2021-01-04 01:25·重学IT的老猫

进程运行时,若其访问的页面不在内存而需将其调入,但内存已无空闲空间时,就需要从内存中调出一页程序或数据,送入磁盘的对换区,其中选择调出页面的算法就称为页面置换算法

好的页面置换算法应有较低的页面更换频率,也就是说,应将以后不会再访问或者以后较长时间内不会再访问的页面先调出。

FIFO页面置换

假设有 3 个帧并且引用串为:

1
7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1

FIFO 先进先出算法是最简单的页面置换算法。简单的理解:优先淘汰最早进入内存的页面。FIFO页面置换算法为每个页面记录了调到内存的时间,当必须置换页面时会选择最旧的页面。
注意,并不需要记录调入页面的确切时间,可以创建一个 FIFO 队列,来管理所有的内存页面。置换的是队列的首个页面。当需要调入页面到内存时,就将它加到队列的尾部。
对于样例引用串,3个帧开始为空。首次的3个引用(7,0,1)会引起缺页错误,并被调到这些空帧。之后将调入这些空闲帧。
下一个引用(2)置换7,这是因为页面7最先调入。由于0是下一个引用并且已在内存中,所以这个引用不会有缺页错误。

操作系统基础39-FIFO页面置换

FIFO页面置换算法

对3的首次引用导致页面0被替代,因为它现在是队列的第一个。因为这个置换,下一个对0的引用将有缺页错误,然后页面1被页面0置换。该进程按上图所示方式继续进行。每当有缺页错误时,上图显示了哪些页面在这三个帧中。总共有15次缺页错误。

FIFO页面置换算法易于理解和编程。然而,它的性能并不总是十分理想。一方面,所置换的页面可以是很久以前使用过但现已不再使用的初始化模块。另一方面,所置换的页面可以包含一个被大量使用的变量,它早就初始化了,但仍在不断使用。
注意,即使选择正在使用的一个页面来置换,一切仍然正常工作。在活动页面被置换为新页面后,几乎立即发生缺页错误,以取回活动页面。某个其他页面必须被置换,以便将活动页面调回到内存。因此,选择不当的置换会增加缺页错误率,并且减慢处理执行。然而,它不会造成执行不正确。
为了说明使用FIFO页面置换算法可能出现的问题,假设如下引用串:

1
1,2,3,4,1,2,5,1,2,3,4,5

下图为这个引用串的缺页错误数量与可用帧数量的曲线。4帧的缺页错误数(10)比3帧的缺页错误数(9)还要大!这个最意想不到的结果被称为Belady异常,即对于有些页面置换算法,随着分配帧数量的增加,缺页错误率可能会增加,虽然我们原本期望为一个进程提供更多的内存可以改善其性能。

操作系统基础39-FIFO页面置换

一个引用串的FIFO置换的缺页错误曲线

-------------本文结束 感谢阅读-------------