hosteons中文网

本节，讨论几种页面置换算法。为此，假设有 3 个帧并且引用串为：

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

FIFO页面置换

FIFO 算法是最简单的页面置换算法。FIFO 页面置换算法为每个页面记录了调到内存的时间，当必须置换页面时会选择最旧的页面。

注意，并不需要记录调入页面的确切时间，可以创建一个 FIFO 队列，来管理所有的内存页面。置换的是队列的首个页面。当需要调入页面到内存时，就将它加到队列的尾部。

对于样例引用串，3 个帧开始为空。首次的 3 个引用（7，0，1）会引起缺页错误，并被调到这些空帧。之后将调入这些空闲帧。

下一个引用（2）置换 7，这是因为页面 7 最先调入。由于 0 是下一个引用并且已在内存中，所以这个引用不会有缺页错误。

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

图 1 FIFO页面置换算法