换入页面时有可能需要将别的页面换出去。
换页算法的目标一方面是最小化缺页异常,另一方面是减少算法开销。
最优策略是一种理想策略,如果你知道未来将要访问哪些页,那么最优策略选择未来不会再访问或者最长时间内不会再访问的页换出。
但是实际应用中不可能事先知道要用到哪些页,因此OPT作为一种标准,用于衡量某个换页算法的优劣。
换出最早换入的页,需要维护一个换页队列。
效果很差,因为换页顺序与使用是否频繁没有关系。
FIFO的改进版本。
维护一个换页队列,同时为每个页维护一个访问标志位。
每个页被访问时,都将其标志位置位。当然刚换进来的页也置位。
需要换页时,在队头先查看访问标志位。如没有置位,则直接换出;如置位,则将其清空并放到队尾。
优先换出最久未被访问的页。基于时间局部性原理。
维护一个链表,按照内存页的访问顺序将内存页号插入链表,其中最近访问的页在尾端。
每次访问某个内存页后,就将其调整到链表尾端。
从链表首段开始换出。