页面置换算法

简单的说就是物理内存页淘汰算法

它其实就是我们在虚拟内存里面提到的，当物理内存不够的时候，要将一部分物理页的内容写到交换区中。页面替换算法就是用来计算，究竟哪些页应该写到交换区上。

有很多种算法，每种算法都有自己的特色。

第一种是先进先出（FIFO）算法：这是最简单的页面替换算法。它基于“先进先出”的原则，即最早进入内存的页面将首先被替换。这种算法易于实现，但可能不适合实际的工作负载，因为它不考虑页面的使用频率。

第二种是最近最少使用（LRU）算法：LRU算法认为过去一段时间内最少被使用的页面，在未来的使用概率也相对较低。因此，当需要替换页面时，它会选择最长时间未被使用的页面进行替换。

第三种是最久未使用（LFU）算法：LFU算法是基于页面访问频率来替换页面的。它替换掉访问次数最少的页面，认为这些页面在将来可能也不常被使用。

第四种是最优（OPT）算法：这是一种理想化的算法，但在实际中很难实现。OPT算法在每次页面请求时都会选择将来最长时间内不会被访问的页面进行替换，因此它也被称为“未来导向”的算法。

第五种是时钟（Clock）算法：这是一种简单并且实用的近似算法，用来模拟OPT算法。它通过一个循环的列表来跟踪页面，给每个页面一个“访问位”。当需要替换时，它会检查访问位，如果未被访问过，则替换这个页面；如果已被访问，则重新标记并继续。

第六种是第二次机会（SCR）算法：这是对FIFO算法的一种改进。在FIFO的基础上，每个页面都有一个引用位。如果页面被访问，则设置引用位。在替换页面时，如果页面的引用位是0，则替换；如果是1，则将其置为0并给它“第二次机会”。

第七种是老化（Aging）算法：用于模拟LFU算法，但避免了LFU算法中可能出现的页面饥饿问题。它通过一组位来表示页面的使用情况，并定期右移这些位，以减少旧的使用记录的影响。

第八种是WSClock算法：结合了LRU和Clock算法的特点，使用一个钟表算法的列表来选择可能的页面替换候选，然后检查这些页面的引用位来决定是否替换。

Linux内核使用了多种页面替换算法的组合，主要是基于LRU的变种，同时考虑了文件页面和匿名页面的不同特性。它不是一个固定的算法，而是根据系统负载和内存使用模式动态调整的策略。随着内核版本的更新，页面替换算法也在不断地得到改进和优化。

进一步来说，LRU 算法虽然简单，但是 LRU 其实深刻反应了计算机的时间局部性和空间局部性，所以在计算机里面应用非常广泛。最典型的就是缓存淘汰算法，比如说本地缓存已经满了，但是还需要继续放入内容，那么就需要淘汰一部分缓存，以腾出空间。