页面置换算法

复习定位

当CPU访问的页不在物理内存中——缺页中断触发——OS从磁盘读入该页。如果此时内存中没有空闲页框——必须选择一个已在内存中的页换出。换出谁——这就是页面置换算法的决策。缺页率(缺页次数/总访问次数)是评价置换算法好坏的核心指标——好的算法用少的缺页率保证慢速磁盘I/O不拖垮性能。

为什么需要页面置换

在请求分页系统中——进程在开始运行时仅有部分页在内存中——随着继续执行——不断遇到新页→缺页→从磁盘读入。物理内存大小有限——当空闲页框用完后——必须选择一个已在内存中的页框"牺牲"——将它的内容写回磁盘(如果被修改过)或直接丢弃(如果是干净页)然后被新页覆盖替换。页面置换算法决定了每次该"牺牲"哪个页框。

OPT最佳置换算法

置换未来最长时间内不会访问的页。OPT实现自由——已知全部引用序列——每次选择最远将要被使用的页换出。OPT是不可实现的——因为OS不能预知未来的访问模式。但OPT提供了一个理论的缺页率下限——其他算法的缺页率必须高于OPT。以引用串"70120304230321201701"、页框数=3做OPT模拟——比较其他算法时用OPT作基准说明A算法比OPT多发生多少次缺页。

FIFO先入先出

FIFO认为最早调入的页最不可能再被使用——因此在队列中维护页进入的顺序。换出时总是选择最早进入的页这个策略的实际效果差——因为它完全忽略了页的访问频率。

Belady异常：通常情况下——增加可用页框数应该减少缺页次数——但FIFO可能违反这一直觉——增加页框数反而缺页率上升。例如引用串"123412512345"——在3页框时缺页9次而在4页框时缺页10次——这个反直觉的异常由Belady发现——这是FIFO独有的病态——OPT和LRU不存在此类异常。

LRU最近最久未使用

LRU基于时间局部性原理——最近一段时间最久未使用过的页最不可能在短期内被再次使用。选择最长时间没有被访问的页换出。

硬件实现：每次访问页时——将该页的时间戳记录为一个硬件计数器(内存中每个页框有一个专用的接近寄存器)跟踪最近访问的时间。置换时找到时间戳最小的页——需要全表扫描O(n)更换为慢速的扫描。现代CPU几乎不使用纯硬件LRU实现——造价太高。

近似实现——Clock置换算法：将页框组织为循环链表——指针初始指向第一项。当需要置换时——检查指针指向的页框的访问位：

• 访问位=0(该页自从指针上次到达后没有被访问过)←置换它
• 访问位=1清除为0——移动指针到下一位——继续扫描

Clock算法近似于LRU——因为访问位被硬件的每次读写自动置1——但在页面置换之前的扫描中清楚1的操作在多次扫描后提供了"最近没有被访问"的判定信息。性能接近LRU但实现开销远小于全硬件LRU。改进型Clock还考虑了脏位(Dirty)——优先置换(A=0,M=0)的干净页——将I/O写入减到最小。这种双层扫描按(A=0,M=0)→(A=0,M=1)→(A=1,M=0)→(A=1,M=1)顺序找牺牲页。

工作集与缺页抖动

工作集是进程在时间τ内访问的页面集合。若分配给进程的物理页框数小于工作集大小——进程在运行中频繁产生缺页——缺页处理程序把等待缺页读入的同时换出其他页——刚换出的页很快被再次访问触发了新的缺页——CPU被缺页处理大量占用——实际指令执行几乎停滞。这个现象叫颠簸(Thrashing)。

解决方法——操作系统通过监控缺页率来判断进程是否在颠簸——如果缺页率超过阈值——增加有效驻留集大小(分配更多页框给该进程——启动页面调度将其他进程挂起以释放内存)。工作集模型实现上述动态分配。

复习检查

1. OPT不可实现——为什么还是学习它的必要(它让所有其他算法有一个基准：理论最小缺页率)？

2. FIFO的Belady异常为什么发生——给出一个具体的引用串和页框数增加的例子说明为什么FIFO异常而LRU不会。

3. Clock算法如何模拟LRU——它扫描到的访问位为0的页是被何时清除为0的？在哪些条件下这一近似会偏离纯LRU的正确决策？

4. 改进Clock优先换出(A=0,M=0)的页比(A=1,M=0)更聪明——减少些磁盘写出次数如何提升置换过程的整体I/O性能？

5. 缺页抖动(Thrashing)——如何通过工作集模型确定给每个进程的最小物理页框数？