最近最久未使用

选择最近时期最久没被使用的页面予以淘汰。淘汰的标准是时间

最少使用

选择在最近时期使用最少的页面作为淘汰页。淘汰的标准是一段时间之内的使用频率

硬件实现

两种算法都可以采用寄存器这一硬件实现。栈只适用于最近最久未使用置换算法

寄存器

该寄存器是移位寄存器，需要为每个页面都配置一个，用于记录某个进程在内存中各页的使用情况

假设该移位寄存器有n位
$R=R_{(}n?1)R_{(}n?2)R_{(}n?3)\dots R_2{R}_1{R}_0$

• 进程访问一次物理块就将最高位$R_{(}n?1)$置为1
• 寄存器每隔一定时间就右移一位

对于两种算法，当需要页面置换时：

• 最近最久未使用：将R值最小的页面置换出去
• 最少使用：将$R_1+R_2+...+R_{(}n?2)+R_{(}n?1)$值最小的页面置换出去

栈

这是一个特殊的栈，入栈时只能从栈顶入，出栈时能从任意位置出。该栈用于保存当前使用的各个页面的页面号

栈可存储的最大页号数，表示进程分有的物理块数

• 进程访问页面时，如果该页面的页号未存储在栈中，将该页号压入栈顶（如果栈已满，则将栈底的页号弹出）。否则执行下一步
• 在栈中找到该页号，将其从栈中移出，之后再压入栈顶

栈顶保存的是最近访问过的页面号