操作系统中的页面替换算法

在使用分页进行内存管理的操作系统中，需要一个页面替换算法来决定新页面进入时需要替换哪个页面。

页面错误– 当正在运行的程序访问映射到虚拟地址空间但未加载到物理内存中的内存页时，会发生页面错误。

由于实际物理内存比虚拟内存小得多，因此会发生页面错误。如果出现页面错误，操作系统可能必须用新需要的页面替换现有页面之一。不同的页面替换算法提出了不同的方法来决定替换哪个页面。所有算法的目标都是减少页面错误的数量。

页面替换算法：

1.先进先出（FIFO）—— 这是最简单的页面替换算法。在该算法中，操作系统跟踪队列中内存中的所有页面，最早的页面位于队列的前面。当需要替换页面时，将选择队列前面的页面进行删除。 示例-1 考虑页面引用字符串1, 3, 0、3, 5, 6和3个页面框架。查找页面错误数。

最初所有插槽都是空的，所以当1、3、0出现时，它们被分配给空插槽-> 3页错误。 当3出现时，它已经在内存中，所以-> 0页错误。 然后5出现了，它在内存中不可用，因此它将替换最旧的页面插槽，即1。-> 1页错误。 6来了，它在内存中也不可用，因此它取代了最旧的页面插槽，即3-> 1页错误。 最后，当3出现时，它不可用，因此它将替换0 1页错误

贝拉迪畸形 – Belady的异常现象证明，在使用先进先出（FIFO）页面替换算法时，增加页面帧数可能会出现更多页面错误。例如，如果考虑参考字符串3、2, 1、0, 3, 2、4, 3, 2、1, 0、4和3个槽，则得到9个总页错误，但是如果将时隙增加到4，则会得到10页错误。

2.最佳页面替换- 在该算法中，页面被替换，在未来最长的时间内不会被使用。 例2： 考虑页面引用7, 0, 1，2, 0, 3，0, 4, 2，3, 0, 3，2，4页框架。查找页面错误数。

最初，所有插槽都是空的，因此当7 0 1 2分配给空插槽时-> 4页错误 0已经存在，所以-> 0页错误。 当3出现时，它将取代7，因为它不会在未来最长的时间内使用。-> 1页错误。 0已经存在，所以-> 0页错误。 . 4将取代1-> 1页错误。

现在查看进一步的页面参考字符串-> 0页错误 因为它们已经存在于内存中。 最佳页面替换是完美的，但在实践中不可能，因为操作系统无法知道未来的请求。最佳页面替换的使用是为了建立一个基准，以便其他替换算法可以根据它进行分析。

3.最近使用最少的- 在此算法中，将替换最近使用最少的页面。 例3 考虑具有4页帧的页面引用字符串7, 0, 1、2, 0, 3、0, 4, 2、3, 0, 3、2。查找页面错误数。

最初，所有插槽都是空的，因此当7 0 1 2分配给空插槽时-> 4页错误 0已经是他们的so-> 0页错误。 当3出现时，它将取代7，因为它最近使用最少-> 1页错误 0已在内存中，因此-> 0页错误 . 4将取代1-> 1页错误 现在查看进一步的页面参考字符串-> 0页错误 因为它们已经存在于内存中。

盖特CS角问题

练习下列问题将有助于测试你的知识。所有问题都是在前几年的GATE或GATE模拟测试中提出的。强烈建议你练习。

1. 内存管理|问题1
2. 内存管理|问题10
3. GATE CS 2014（第1组），问题65
4. 2012年CS门，问题40
5. 2007年CS门，问题56
6. 2007年CS登机口，问题82
7. 2007年CS门，问题83
8. GATE CS 2014（第三组），问题65
9. 盖特CS 2002问题23
10. CS门2001，问题21
11. CS门2010，问题24

参考—— 贝拉迪异常

这篇文章已经改进了 拉杰斯里瓦斯塔瓦 。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请发表评论