LRU与CLOCK页面置换算法

复习定位

OPT(理论上最优但不可实现)告诉我们——页面置换应该置换未来不会使用的页——但未来不可知。LRU(最近最久未使用)——置换最长没被用过的页——基于"过去的使用模式大概率延续"。LRU理论效果接近OPT但实现昂贵——CLOCK算法通过访问位近似LRU——是系统实际使用的方案。改进型CLOCK同时考虑脏位来选择避免I/O写入的干净页。

LRU算法

LRU——置换最长时间没有被访问的页。当需要选一页换出时——找到访问时间戳最小的页。

硬件实现：每个页框配一个计数器——每次访问某页时将该页的时间寄存器置为当前时钟值。选择时间值最小的页换出。每页一个计数器是昂贵硬件实现——现代CPU很少装。

软件近似——系统维护一个页的链表——每次访问某页时将该页移到链表头。链表尾自然是最久未使用的页。这样的代价是在每次访存(包括命中)时都必须调整链表——链表的随机移动非常耗时。因此操作系统常使用CLOCK近似算法。

CLOCK算法(二次机会算法)

CLOCK是LRU的近似——实现简单——效果接近LRU。

将所有在内存中的页框组织成一个循环链表(就像时钟盘面一样)。增加一个指针(指向"当前"候选页)。每个页有一个访问位A(硬件自动置1——每当该页被访问)。

置换步骤：

1. 检查指针当前页的A位——如果是0(该页自上次扫描以来没有被访问过)——则选择这一页换出。
2. 如果A=1——将A清零(给该页第二次机会)——指针移动到下一页——重复这个过程。
3. 如果扫过一圈所有页的A位都曾是1——它们都被清零——指针回到最初的位置——该页此时A=0即被换出。

这个算法关键的精妙是——被频繁访问的页A位反复被硬件置1——多次给二次机会不被换出——只有长时间没被访问的页"A被清0后不再置1"才被置换。

改进型CLOCK

在CLOCK的基础上增加脏位D(该页是否被修改过——换出时是否需要写回磁盘)。

改进型CLOCK采用多轮扫描——优先级顺序：

• 第一轮：寻找(A=0,D=0)的页——最理想的置换对象——不需要写回。
• 第二轮：寻找(A=0,D=1)的页——需要写回磁盘但至少访问需求低。
• 第三轮：寻找(A=1,D=0)的页——访问频繁但不需要写回。
• 第四轮：寻找(A=1,D=1)的页——最差的换出对象。

实际上在扫描中如果遇到A=1的页——全程将其清0——这样随着时间的推移——所有没有被访问的页最终都会被转为A=0。结合D位的判断——优先选择未修改的干净页以节省写回磁盘的I/O开销。

复习检查

1. LRU需要硬件支持——每页记录最近一次访问的时钟或堆栈——为什么CLOCK近似算法可以在Linux中通过扫描和清除访问位实现类似的换入换出判定？

2. CLOCK算法在淘汰页时——对于"A位被清0后再次访问前的时间窗口"有什么含义——如果某一页在A为0的极短时间内又被访问了——CLOCK无法提前知道这页即将被访问并将它保留——所以CLOCK的准确度不如LRU。

3. 改进型CLOCK为什么在(A=0,D=0)时是最高优先级——因为不必写回磁盘(A=0,D=0)也就是说从未被修改——直接丢弃不写磁盘——因为磁盘上的副本数据是旧的——但可能永远也不需要再为它写磁盘——完全相当于读缓存失效换出0开销。

4. 如果CLOCK指针扫描了一圈回到原点——同时所有页的A位都曾为1且已被清0——指针回到原位时发现了刚刚被清0、又被访问的页——那么它的A=1——指针还要继续扫吗？因为此时A已经被重新置1了——所以指针会继续移动直到找到A=0(那些最近真正没有被访问的)。

5. CLOCK算法在系统缺页频繁时——每次置换都需扫过多页——开销上升——这种场景如何处理(通过调整缺页率阈值触发工作集及驻留集调节——尽量增加分配给进程的页框以减少缺页)？