最佳置换算法(OPT)
每次选择淘汰的页面将是以后永不使用或者在最长时间内不再被访问的页面
可以保证最低缺页率,操作系统无法提取预判页面访问序列,因此,最佳置换算法无法实现
先进先出(FIFO)
每次选择淘汰的页面是最早进入内存的页面
当为进程分配的物理块数增大时,缺页次数不增反减的异常现象,算法性能差
最近最久未使用置换算法(LRU)
每次淘汰的页面是最近最近未使用的页面
实现方法:赋予每个页面对应的的页表项中,用访问字段记录该页面自上次被访问以来经历的时间t,选择t值最大的
优点
LRU算法利用了计算机程序的局部性原理,即程序倾向于频繁访问一小部分数据。通过保留最近访问的页面,LRU算法可以提高缓存的命中率。
性能提升:在许多情况下,LRU算法能够显著提高系统的性能,因为它减少了不必要的页面置换和I/O操作。
缺点:
实现复杂性:LRU算法需要记录每个页面的访问时间或访问顺序,这可能需要复杂的数据结构(如哈希表和双向链表)来实现。
时钟置换算法(CLOCK)
Clock算法的简单性使其更适合于硬件实现,因为硬件可以更有效地处理循环队列和指针操作。它牺牲了LRU算法的一些精确性,以换取实现的简便和效率
改进时钟置换算法(CLOCK)
如果淘汰的页面没有被修改过,就不需要执行I/O操作写回外存,只有被淘汰的页面修改过,才需要写回外存
在其他条件都相同时,应该优先淘汰没有修改过的页面,避免I/O操作
第一优先级:
最近没访问,且没修改过的页面
第二优先级:
最近没访问,但修改过的页面
第三优先级:
最近访问了,但没修改的页面
第四优先级:
最近访问过,且修改过的页面