“时间局部性指近期访问的数据有机会再次使用；空间局部性指邻近地址的数据有机会被一起使用。它们是访问轨迹的结构特征，是否转化为命中还要结合块大小、容量、映射和替换规则。”
形式陈述
在组相联缓存的某组已无无效way且发生缺失时，替换策略从该组选择一个victim。本文固定两种在线规则：LRU逐次记录最近访问次序，命中或填入都把该块移到最近端；FIFO只记录填入先后，命中不改变次序。
所有算例先用无效way，多个无效way取最低编号。LRU次序用“最近 → 最久”书写，FIFO用“最早填入 → 最晚填入”书写。访问包括读和写命中。逐出是否必须写回，由脏位及写策略另定，不改变这里的受害者身份。
离线MIN作为对照：在已知完整未来轨迹时，淘汰下次访问最晚的块，没有后续访问视为无穷远。它说明“最优替换”可以依赖未来信息，不是一般在线实现可免费调用的接口。
直觉
LRU猜测“刚用过的还可能再用”，FIFO只关心“谁住得最久”。两者在全是缺失的前缀里可能看起来相同，第一次命中会让历史分叉。
替换策略不决定块能放在哪个组。直接映射只有一个候选victim，谈组内LRU不会改变任何行为；全相联才允许在整个容量范围选择。
例子与边界
一个命中改变后面的受害者
同一两路组，冷启动，依次访问 A,B,A,C,A：
| 步 | LRU最近→最久 | FIFO最早→最晚 | 结果差别 |
|---|---|---|---|
| A | A | A | 都缺失 |
| B | B,A | A,B | 都缺失 |
| A | A,B | A,B | 都命中，只有LRU更新历史 |
| C | C,A | B,C | LRU逐出B；FIFO逐出A |
| A | A,C | C,A | LRU命中；FIFO缺失 |
LRU共3次缺失，FIFO共4次。若LRU实现只在填入时更新次序，它在这个例子里实际上做的是FIFO。
过去相同，未来最优不同
容量两块，轨迹 A,B,C,A,B,C。LRU每次都淘汰即将很快被重新使用的块，六次全缺失。MIN在首次C到来时淘汰B，接着A命中；B回来时淘汰之后不再使用的A，最后C命中，共4次缺失。
这不是“任何程序都能比LRU少两次”的定理，只说明有些轨迹需要未来信息才能作出该选择。理想缓存的最优替换是假设，不能把其分析界直接当作某个LRU硬件的逐次轨迹。
脏块不总是正确的保留对象
设A脏、B干净，LRU规定A最久未用。优先逐出B可能省本次写回，却改变了策略，后续缺失数也会变化。若要采用clean-first等规则，应给出自己的优先级，而不能在答案中仍标“LRU”。
推论与应用
复算缓存时，除tag/valid/dirty外还要保存替换历史。最终驻留集合相同，不保证下一次缺失选择相同victim；只对照集合会漏掉历史更新错误。
本文的LRU/FIFO模型为缺失分类提供固定参考。分类依赖所选影子缓存策略，不能一边用LRU判容量、一边拿离线MIN的驻留状态解释结果。
参考资料
- UC Berkeley CS61C，Fully Associative Cache，课程笔记，访问于 2026-10-08，放置与替换接口。
- László A. Bélády, “A Study of Replacement Algorithms for a Virtual-Storage Computer,” IBM Systems Journal 5(2), 1966, pp. 78–101；离线最优替换背景。本文仅用明示的短轨迹比较策略，不把分页实现与CPU缓存完全等同。