3.2.4 页面置换算法

专题讲解：虚拟内存与页面置换

LRU 淘汰的是最久没用，不是最早装入

上一课地址翻译可能遇到页不在内存。现有3个页框，访问串 7,0,1,2,0,3,0,4，用 LRU 计算缺页次数并写每步页框。LRU 每次命中也要刷新最近使用时刻。

def lru(reference,capacity):
    frames=[]; last={}; faults=0; trace=[]
    for time,page in enumerate(reference):
        hit=page in frames
        if not hit:
            faults+=1
            if len(frames)==capacity:
                victim=min(frames,key=lambda p:last[p])
                frames.remove(victim)
            frames.append(page)
        last[page]=time
        trace.append((page,tuple(frames),hit))
    return faults,trace

faults,trace=lru([7,0,1,2,0,3,0,4],3)
assert faults==6
assert [hit for _,_,hit in trace]==[False,False,False,False,True,False,True,False]

7、0、1 前三次装满；访问2淘汰最久未用7；访问0命中并刷新；访问3时1最久未用，淘汰1；再访0命中；访问4时2最久未用，淘汰2，共6次缺页。

为何正确：last[p] 精确记录驻留页最近一次访问时刻，最小者定义上就是 LRU 牺牲页。模拟每次从最多 capacity 个页中找最小，时间 O(N×capacity)，空间 O(capacity)；真实系统用近似硬件/链表降低代价。

典型错误：命中不更新时间会把常用页误判为旧页；FIFO 依据装入先后，与 LRU 不同；增加页框数时 FIFO 可能出现 Belady 异常，栈算法 LRU 不会；缺页次数不含初始页框预装，除非题目明确。

迁移答案：若问 OPT，访问2时应淘汰未来最晚再用或不再用的7；OPT 需要未来信息，只用于理论下界比较，不能在线实现。

下一课把内存中的页换成磁盘文件块，计算 inode 直接块和间接块能覆盖多大文件。

专题讲解：页面置换逐次模拟

页框更多，FIFO 反而可能缺页更多

主章手算过 LRU。强化题使用经典访问串 1,2,3,4,1,2,5,1,2,3,4,5，分别给3、4个页框，比较 FIFO 与 LRU 缺页次数。

from collections import deque

def fifo(ref,capacity):
    frames=set(); order=deque(); faults=0
    for page in ref:
        if page in frames: continue
        faults+=1
        if len(frames)==capacity:
            frames.remove(order.popleft())
        frames.add(page); order.append(page)
    return faults

def lru(ref,capacity):
    frames=set(); recent=[]; faults=0
    for page in ref:
        if page not in frames:
            faults+=1
            if len(frames)==capacity:
                victim=recent.pop(0); frames.remove(victim)
            frames.add(page)
        else:
            recent.remove(page)
        recent.append(page)
    return faults

ref=[1,2,3,4,1,2,5,1,2,3,4,5]
assert (fifo(ref,3),fifo(ref,4)) == (9,10)
assert (lru(ref,3),lru(ref,4)) == (10,8)

FIFO 3框缺页9次，4框反而10次，出现 Belady 异常。原因是 FIFO 只看装入时间，增加页框会改变淘汰节奏，4框驻留集合不保证包含3框集合。LRU 3框10次、4框8次；它是栈算法，同一时刻较少页框的驻留页是较多页框的子集，所以页框增加不会使缺页上升。

逐步模拟时，FIFO 命中不改变队列；LRU 命中必须把该页更新为最近使用。代码中 recent 从旧到新，淘汰下标0，始终与定义一致。

每种模拟时间 O(N×capacity)（列表更新实现），空间 O(capacity)。错解反馈：把 FIFO 命中页移到队尾就偷偷变成 LRU；Belady 异常不是“所有算法都可能”；只报总数不给逐次页框状态，在大题中难拿过程分。

变式答案：OPT 同样具有随页框增多缺页不增的性质，但依赖未来访问；本串可用它作为理论最优下界，不可在线实现。

下一步把“多级索引”扩到直接、一级、二级、三级，计算容量并定位某个逻辑块的索引路径。

专题讲解：页面置换、缺页率与Belady异常

新困难：Clock 命中只置访问位，缺页扫描才推进并清零

3个页框，初始为空，Clock指针从框0开始。引用串 1,2,3,1,4,2,5。装入或命中都把访问位R置1；缺页时从指针扫描，R=1则清0并前进，R=0或空框则替换，装入后指针移到下一框。

def clock_replace(refs,capacity):
    frames=[None]*capacity; bits=[0]*capacity; hand=0; faults=0; trace=[]
    for page in refs:
        if page in frames:
            i=frames.index(page); bits[i]=1; hit=True
        else:
            faults+=1; hit=False
            while frames[hand] is not None and bits[hand]==1:
                bits[hand]=0; hand=(hand+1)%capacity
            frames[hand]=page; bits[hand]=1; hand=(hand+1)%capacity
        trace.append((page,hit,frames.copy(),bits.copy(),hand))
    return faults,trace

faults,trace=clock_replace([1,2,3,1,4,2,5],3)
assert faults==5
assert trace[3]==(1,True,[1,2,3],[1,1,1],0)
assert trace[4]==(4,False,[4,2,3],[1,0,0],1)
assert trace[-1]==(5,False,[4,2,5],[1,0,1],0)

陪走：前三页依次填满，指针回0，三位均1；再次访问1命中，仅保持R1=1。访问4缺页，从框0开始把1、2、3的R依次清0，绕回框0淘汰1，装4后hand=1。访问2命中置R=1；访问5缺页，从hand1清2的R，框2的3为R0，故淘汰3，最终 [4,2,5]，共5次缺页。

依据：R=1表示自上次扫描以来被访问，清0相当于给一次“第二机会”；扫描最终找到未在最近一轮获得机会的页。每次替换后hand指向下一候选，循环顺序不变量不能在命中时随意移动。

单次缺页最坏扫描 O(frame数)，模拟整串的时间常用摊还分析；空间 O(frame数)。错误反馈：命中不推进hand；扫描R1要清零；装入后R应为1；Clock是LRU近似而非严格LRU；Belady异常结论不能从本短串推广，Clock也不具LRU的严格栈包含性质。

迁移答案：增强Clock再加入修改位M时，通常优先找 (R,M)=(0,0)，必要时再找 (0,1)，清R后重扫；淘汰脏页还要增加写回开销。

桥接：页替换决定数据页是否驻留；下一课用稀疏文件说明“逻辑上很大”也不等于所有文件块都真实分配。