操作系统中的页面替换算法详细指南

在使用分页进行内存管理的操作系统中, 需要使用页面替换算法来确定新页面进入时需要替换哪个页面。
页面错误–当正在运行的程序访问映射到虚拟地址空间但未加载到物理内存中的内存页面时, 将发生页面错误。
由于实际的物理内存比虚拟内存小得多, 因此会发生页面错误。如果出现页面错误, 操作系统可能必须用新需要的页面替换现有页面之一。不同的页面替换算法建议了不同的方法来决定替换哪个页面。所有算法的目标是减少页面错误的数量。
页面替换算法：
先进先出(FIFO)–
这是最简单的页面替换算法。在这种算法中, 操作系统会跟踪队列中内存中的所有页面, 最早的页面位于队列的前面。当需要替换页面时, 选择要删除队列前面的页面。
示例1-考虑具有3个页面框架的页面参考字符串1、3、0、3、5、6。查找页面错误数。

文章图片
最初所有的槽都是空的，所以当1、3、0到来时，它们被分配到空的槽—> 3页错误。
当3到来的时候，它已经在内存中了-> 0页错误。
然后5来了，它在内存中不可用，所以它取代了最老的页槽，即1。-> 1页面错误。
6来了，它在内存中也不可用，所以它取代了最旧的页槽，即3 - > 1页错误。
最后，当3到来时，它是不可用的，所以它替换0 1页错误
Belady的异常–Belady的异常情况证明, 使用先进先出(FIFO)页面替换算法增加页面帧数时, 可能会出现更多页面错误。例如, 如果考虑参考字符串3、2、1、0、3、2、4、3、2、1、0、4和3个插槽, 则总共会出现9个页面错误, 但是如果将插槽增加到4个, 我们得到10个页面错误。
最佳页面替换–
在此算法中, 将替换将来在最长的时间段内不会使用的页面。
示例2：考虑具有4个页面框架的页面引用7、0、1、2、0、3、0、4、2、3、0、3、2。查找页错误数。

文章图片
最初所有的槽都是空的，所以当7 0 1 2被分配到空的槽-> 4页错误
0已经在那里了-> 0页错误。
当3到来时，它将取代7，因为它在未来使用的时间不是最长的。-> 1页面错误。
0已经在那里了，所以-> 0页错误。
4将代替1 - > 1页错误。
现在为进一步的页引用字符串-> 0页错误，因为它们已经在内存中可用。
最佳页面替换是完美的, 但实际上无法实现, 因为操作系统无法知道将来的请求。最佳页面替换的用途是建立基准, 以便可以针对该基准分析其他替换算法。
最近最少使用–
在该算法中, 将替换最近最少使用的页面。
示例3-考虑具有4个页面框架的页面参考字符串7、0、1、2、0、3、0、4、2、3、0、3、2。查找页面错误数。

文章图片
最初所有的槽都是空的，所以当7 0 1 2被分配到空的槽- > 4页错误
0已经在那里了- > 0页错误。
当3到来时，它将取代7，因为它是最近最少使用的-> 1页错误
0已经在内存中，所以-> 0页错误。
4将代替1 -> 1页错误
现在为进一步的页引用字符串-> 0页错误，因为它们已经在内存中可用。
参考–
Bélády的异常：https://en.wikipedia.org/wiki/B%C3%A9l%C3%A1dy%27s_anomaly
【操作系统中的页面替换算法详细指南】如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请发表评论。