C 语言 FIFO 页替换算法

在操作系统中，当采用分页方式管理内存，并且接收到新的页面时，需要页面置换算法来决定哪个页面需要被替换。

页面错误（缺页）

当一个活动应用程序尝试访问虚拟内存中已加载但物理上不在系统中的内存页面时，就会发生页面错误（或缺页）。页面错误发生的原因是实际物理内存远小于虚拟内存。当发生页面错误时，操作系统可能需要将当前某个页面换出，以置入当前所需的页面。不同的页面置换算法提供了各种选择合适替换页面的建议。所有算法都致力于减少页面错误的数量。

FIFO

这是最简单的页面置换算法。在此方法中，操作系统为所有内存页面维护一个队列，最旧的页面位于队列的前端。当需要替换页面时，选择队列中的第一个页面进行移除。

示例1：以页面引用字符串 1, 3, 0, 3, 5, 6 和三个页面槽位为例。所有槽位最初都是空的，因此当 1, 3, 0 到达时，它们被分配到空槽位，导致 3 次页面错误。

由于 3 已在内存中，因此当它到达时没有页面错误。然后页面号 5 出现；它无法适应内存，因此它取代了最旧的页面槽位，即 1。-> 1 次页面错误。

最后，页面 6 出现；然而，它也不在内存中，因此它取代了最旧的页面槽位，即 3。-> 1 次页面错误。

因此，总页面错误数为 5。

示例2：考虑引用字符串 0, 2, 1, 6, 4, 0, 1, 0, 3, 1, 2, 1。使用 FIFO 页面置换算法

因此，总共有 9 个页面错误。编写一个函数，根据内存容量（以可容纳的页数衡量）和表示要引用的页面的字符串来查找页面错误的数量。

实施

让内存可以存储的页数作为容量。Set，当前的内存页面集合，应为。

以下是上述方法的代码

输出

Incoming  Frame 1  Frame 2  Frame 3
4                   4              -               - 
1                   4              1              -  
2                   4              1              2 
4                   4              1              2 
5                   5              1              2 
Total Page Faults: 4