最近最久未使用置换算法
缺页中断
缺页中断就是 CPU 要访问的页不在主存，需要操作系统将其调入主存后再进行访问
访问的页面不在内存时，会产生一次缺页中断，缺页中断是由于所要访问的页面不存在主内存时触发，属于由硬件所产生的一种特殊的中断，也称之为硬中断。
缺页本身是一种中断，与软中断一样，需要经过4个处理步骤
- 保护CPU现场
- 分析中断原因
- 转入缺页中断处理程序进行处理
- 恢复CPU现场，继续执行
缺页中断更多可以阅读程序员的自我修养（七）：内存缺页错误
页面置换算法
进程运行过程中，如果发生缺页中断，而此时内存中有没有空闲的物理块时，
为了能够把所缺的页面装入内存，系统必须从内存中选择一页调出到磁盘的对换区。
但此时应该把那个页面换出，则需要根据一定的页面置换算法（Page Replacement Algorithm)来确定。
页面置换算法有 OPT、FIFO、LRU 三种算法。OPT、FIFO 大家自行阅读缺页中断算法(FIFO,LRU)
LRU
最近最久未使用置换算法（Least Recently Used）
置换最近一段时间以来最长时间未访问过的页面。根据程序局部性原理，刚被访问的页面，可能马上又要被访问；而较长时间内没有被访问的页面，可能最近不会被访问。
采用固定分配局部置换的策略，假定系统为某进程在内存中分配了3个物理页，页面访问顺序为2、3、2、1、5、2、4、5、3、2、5、2。假定系统未采用预调页策略，即未事先调入任何页面。
中断次数为7，缺页中断率为7/12*100% = 58.3%
数据结构实现实现 LRU
哈希表 + 双向链表
用哈希表，辅以双向链表记录键值对的信息。所以可以在 O(1) 时间内完成 put 和 get 操作，同时也支持 O(1) 删除第一个添加的节点。
使用双向链表的一个好处是不需要额外信息删除一个节点，同时可以在常数时间内从头部或尾部插入删除节点。
一个需要注意的是，在双向链表实现中，这里使用一个伪头部和伪尾部标记界限，这样在更新的时候就不需要检查是否是 null 节点。
感兴趣可以到 LeetCode 做这道题——146. LRU缓存机制
参考链接