页面置换算法有哪些？

在分页系统里，一个虚拟的页面可能在主存里，也可能在磁盘中，如果CPU发现虚拟地址对应的物理页不在主存里，就会产生一个缺页中断，然后从磁盘中把该页调入主存中。

如果内存里没有空间，就需要从主存里选择一个页面来置换。

常见的页面置换算法：

最佳页面置换算法是一种理想的算法，其基本思路是选择在未来最长时间内不会被访问的页面进行置换。

实现该算法需要计算内存中每个逻辑页面的下一次访问时间，并进行比较，选择未来最长时间不访问的页面。

然而，该算法无法实现，因为当发生缺页中断时，操作系统无法得知每个页面下一次被访问的时间。

由于无法预知页面下一次访问前的等待时间，可以选择在内存中驻留时间最长的页面进行置换，这就是先进先出置换算法的思想。

FIFO的实现机制是使用链表将所有在内存中的页面按照进入时间的先后顺序连接起来，然后每次置换链表头部的页面，新加入的页面则挂在链表末端。

最近最久未使用（LRU）的页面置换算法的基本思路是，在发生缺页时选择最久时间没有被访问的页面进行置换，即假设已经很久没有使用的页面在未来较长时间内仍然不会被使用。

这种算法近似于最优置换算法，而最优置换算法是通过未来的使用情况来推测要淘汰的页面，而LRU则是通过历史的使用情况来推测要淘汰的页面。

在理论上，LRU是可以实现的，但代价很高。为了完全实现LRU，需要在内存中维护一个包含所有页面的链表，最近最多使用的页面在表头，最近最少使用的页面在表尾。

然而，困难之处在于每次访问内存时都需要更新整个链表。在链表中找到一个页面、删除它，然后将其移动到表头是非常费时的操作。

因此，尽管LRU看起来很好，但由于开销较大，在实际应用中很少被使用。

时钟页面置换算法的思路是将所有页面保存在一个类似时钟的环形链表中，一个指针指向最老的页面。

当发⽣缺⻚中断时，算法⾸先检查表针指向的⻚⾯：

如果它的访问位位是 0 就淘汰该⻚⾯，并把新的⻚⾯插⼊这个位置，然后把表针前移⼀个位置；

如果访问位是 1 就清除访问位，并把表针前移⼀个位置，重复这个过程直到找到了⼀个访问位为 0 的⻚⾯为⽌；

最不常用算法（LFU），当发⽣缺⻚中断时，选择访问次数最少的那个⻚⾯，将其置换。

它的实现⽅式是，对每个⻚⾯设置⼀个「访问计数器」，每当⼀个⻚⾯被访问时，该⻚⾯的访问计数器就累加 1。在发⽣缺⻚中断时，淘汰计数器值最⼩的那个⻚⾯。