在进程运行过程中，若其所要访问的页面不在内存而需把它们调入内存，但内存中已无空闲空间时，为了保证该进程能正常运行，

系统必须从内存中调出一页程序或数据到磁盘的对换区中。但应将哪个页面调出，需根据一定的算法来实现。

　　常见的页面置换算法有：

1. 最佳置换算法（Optimal）

　　从内存中移除永远都不再需要的页面或者说是未来最长时间内不再被访问的页面，如果这样的页面存在，则选择最长时间不需要访问的页面。采用最佳置换算法，可以保证较低的页面更新频率。从理论上讲，由于无法预知哪一个页面是未来最长时间内不再被访问的，因而该算法无法实现，但是可用来衡量其他算法。

2.先进先出页面置换算法（FIFO）

　　该算法总是淘汰最早进入内存的页面，即选择在内存中停留时间最久的页面予以淘汰。

　　这个算法的实现简单，只需要将进程已调入内存中的页面，按照先后顺序连接成一个队列，设置一个替换指针，总是指向最老的页面。

　　但是该算法与进程实际的规律并不相适应，因为在进程中，有些页面经常被访问，比如：含有全局变量、常用函数、例程等的页面，FIFO不能保证这些页面不会被淘汰。

3.最近最久未使用页面置换算法（LRU）

　　在之前的FIFO算法中，依据的是各个页面调入内存的时间，这并不能反映页面的真实使用情况。

　　而LRU（Latest Recently Used）是根据页面调入内存之后的使用情况。

　　由于无法预测页面未来的情况，所以只能利用“最近的过去”来作为预测未来的方法，LRU选择的是最近最久未使用的页面予以淘汰。

　　该算法赋予每个页面一个访问字段，用来记录一个页面从上次被访问以来所经历的时间t，当需要淘汰一个页面的时候，选择现有页面中t的值最大的页面进行淘汰。

　　LRU是一种优秀的页面置换算法，但是需要硬件的支持，为了了解一个进程在内存中各个页面各有多少时间未被进程访问，以及如何快速地知道哪一个页面是最近最久未使用的页面，需要 寄存器+栈 来支持。

　　（1）寄存器

　　为了记录某进程在内存中各页的使用情况，需要为每个在内存中的页面设置一个移位寄存器，可表示为：

R=R(n-1)R(n-2)...R2R1R0

当进程访问某物理块时，要将相应寄存器的R(n-1)位置成1。此时，定时信号将每隔一定时间（例如100ms）将寄存器右移一位。如果我们把n位

寄存器的数看做是一个整数，那么具有最小数值的寄存器所对应的页面，就是最近最久未使用的页面。当发生缺页时，首先将它置换出去。

页面置换算法