页面置换算法

页面置换算法简介

• 进程运行时，若其访问的页面不在内存而需将其调入（缺页异常），但内存已无空闲空间时，就需要从内存中调出一页程序或数据，送入磁盘的对换区，其中选择调出页面的算法就称为页面置换算法。
• 好的页面置换算法应有较低的页面更换频率，也就是说，应将以后不会再访问或者以后较长时间内不会再访问的页面先调出。
• 页面置换算法的目标是最小化缺页中断的次数，常见的页面置换算法有最佳⻚⾯置换算法（OPT）、先进先出置换算法（FIFO）、最近最久未使⽤的置换算法（LRU）、时钟页面置换算法和最不常⽤置换算法等。

最佳页面置换算法（淘汰未来不会使用/最长时间不访问的页面）

• 理论上的最佳算法，因为它可以保证最低的缺页率。但在实际应用中，由于无法预知未来的访问模式，OPT 通常无法实现。

先进先出置换算法（优先淘汰最早进入内存的页面）

• FIFO 算法维护一个队列，新来的页面加入队尾，当发生页面置换时，队头的页面（即最早进入内存的页面）被移出。

• FIFO 和 OPT 算法的区别在于：除了在时间上向后或向前看之外，FIFO 算法使用的是页面调入内存的时间，OPT 算法使用的是页面将来使用的时间

最近最久未使用的置换算法（淘汰最近没有使用的页面）

• LRU 算法根据页面的访问历史（维护一个链表）来进行置换，最长时间未被访问的页面将被置换出去。
• 相对更接近最优算法的效果，因为最近未使用的页面可能在将来也不会被使用。但 LRU 算法的实现需要跟踪页面的访问历史，可能会增加系统的开销。

时钟页面置换算法

• 通过一个类似钟面的（环形链表）遍历页面，每个页面有一个使用位，当页面被访问时，使用位设置为 1。
• 当需要页面置换时，时钟指针会顺时针移动，直到找到使用位为 0 的页面进行置换。这个过程类似于给每个页面一个二次机会。算法执行时，会先将使用位从 1 清零，如果该页面再次被访问，它的使用位再次被设置为 1。

最不常用置换算法

• 根据页面被访问的频率进行置换，访问次数最少的页面最先被置换。实现较为复杂，需要记录每个页面的访问频率。
• 它的实现方式是，对每个页面设置⼀个访问计数器，每当⼀个页面被访问时，该页面的访问计数器就累加 1。在发生缺页中断时，淘汰计数器值最小的那个页面。
• 看起来很简单，每个页面加⼀个计数器就可以实现了，但是在操作系统中实现的时候，我们需要考虑效率和硬件成本的。
  1. 要增加⼀个计数器来实现，这个硬件成本是比较高的，另外如果要对这个计数器查找哪个页面访问次数最小，查找链表本身，如果链表很长，是非常耗时的，效率不高。
  2. 还有个问题，LFU 算法只考虑了频率问题，没考虑时间的问题，比如有些页面在过去时间里访问的频率很高，但是现在已经没有访问了，而当前频繁访问的页面由于没有这些页面访问的次数高，在发生缺页中断时，就会可能会误伤当前刚开始频繁访问，但访问次数还不高的页面。
• 这个问题的解决的办法还是有的，可以定期减少访问的次数，比如当发生时间中断时，把过去时间访问的页面的访问次数除以 2，也就说，随着时间的流失，以前的高访问次数的页面会慢慢减少，相当于加大了被置换的概率。