## 页面置换算法 操作系统将内存按照页面进行管理，在需要的时候才把进程相应的部分调入内存。 当产生缺页中断时，需要选择一个页面写入。 如果要换出的页面在内存中被修改过，变成了“脏”页面，那就需要先写会到磁盘。 页面置换算法，就是要选出最合适的一个页面，使得置换的效率最高。 ### **一、最优页面置换算法** 最理想的状态下，我们给页面做个标记，挑选一个最远才会被再次用到的页面调出。 当然，这样的算法不可能实现，因为不确定一个页面在何时会被用到。 ### **二、先进先出页面置换算法（FIFO）及其改进** 这种算法的思想和队列是一样的，该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予淘汰。 实现：把一个进程已调入内存的页面按先后次序链接成一个队列，并且设置一个指针总是指向最老的页面。 缺点：对于有些经常被访问的页面如含有全局变量、常用函数、例程等的页面，不能保证这些不被淘汰。 ### **三、最近最少使用页面置换算法LRU（Least Recently Used）** 根据页面调入内存后的使用情况做出决策。LRU置换算法是选择最近最久未使用的页面进行淘汰。 1. 为每个在内存中的页面配置一个移位寄存器。 定时信号将每隔一段时间将寄存器右移一位。 最小数值的寄存器对应页面就是最久未使用页面。 2. 利用一个特殊的栈保存当前使用的各个页面的页面号。 每当进程访问某页面时，便将该页面的页面号从栈中移出，将它压入栈顶。 因此，栈顶永远是最新被访问的页面号，栈底是最近最久未被访问的页面号。