页面置换算法
当发生缺页中断时，如果操作系统内存中没有空闲页面，则操作系统必须在内存选择一个页面将其移出内存，以便为即将调入的页面让出空间。而用来选择淘汰哪一页的规则叫做页面置换算法
缺页中断
指的是当软件试图访问已映射在虚拟地址空间中，但是目前并未被加载在物理内存中的一个分页时，由中央处理器的内存管理单元所发出的中断。
简而言之，缺页中断就是要访问的页不在主存，需要操作系统将其调入主存后再进行访问。
最优页面置换算法
最理想的状态下，我们给页面做个标记，挑选一个最远才会被再次用到的页面。当然，这样的算法不可能实现，因为不确定一个页面在何时会被用到。
FIFO 及其改进
这种算法的思想和队列是一样的，OS维护一个当前在内存中的所有页面的链表，最新进入的页面在尾部，最久的在头部，每当发生缺页中断，就替换掉表头的页面并且把新调入的页面加入到链表末尾。
这个算法的问题，显然是太过于“公正了”，没有考虑到实际的页面使用频率。
一种合理的改进：即给每个页面增加一个R位，每次先从链表头开始查找，如果R置位，清除R位并且把该页面节点放到链表结尾；如果R是0，那么就是又老又没用到，替换掉。
时钟页面置换算法（clock）
这种算法只是模型像时钟，其实就是一个环形链表的第二次机会算法，表针指向最老的页面。缺页中断时，执行相同的操作，包括检查R位等。
LRU
Least Recently Used的缩写，即最近最少使用，常用于页面置换算法和缓存淘汰算法
实现：
最常见的实现是使用一个链表保存缓存数据；
-
新数据插入到链表头部
-
每当缓存命中（即缓存数据被访问），则将数据移到链表头部
-
当链表满的时候，将链表尾部的数据丢弃
网友评论