Go back

页面置换算法——从OPT到LRU到Clock的演进

页面置换算法：物理内存不够时淘汰哪一页？

一句话结论（30s）

页面置换的本质是用「有限的物理页框」近似「理想的完整内存」。因为 OPT 要预知未来、不可实现，FIFO 有 Belady 异常，精确 LRU 需要硬件时间戳、开销太大，所以工程上收敛到 Clock 算法——用硬件自动置位的访问位 + 环形指针，以 O(1) 复杂度近似 LRU 效果，成为 Linux 等系统的事实标准。

核心原理（2min）

底层深入（5-10min）

OPT 是永远达不到的理论最优

淘汰”未来最长时间内不再被访问”的页面。需要预知未来的访问序列——不可能实现，但给所有实际算法提供了一个”下界”——任何算法的缺页次数都不低于 OPT。

FIFO：简单粗暴但有反直觉陷阱

淘汰最早进入内存的页面。Belady 异常：给 FIFO 更多的物理页框，缺页次数反而增加——唯一一个有 Belady 异常的算法。因为 FIFO 根本不关心访问频率和最近性，只关心”谁来得早”，增加页框只是让淘汰线往后移，但不保证新淘汰的页面不是热点。

💭 思考穿插：为什么加页框反而缺页更多、会发生 Belady 异常？因为 FIFO 的淘汰决策完全由「入队顺序」决定，跟「这页以后还用不用」毫无关系。页框多了，淘汰线后移，但 FIFO 还是机械地淘汰「最老」的页——而「最老」≠「最不常用」，可能刚好把马上要用的热点踢出去。换句话说，FIFO 的缓存行为不满足「栈性质」（缓存越大，命中集合应单调包含），所以才会出现这种反直觉的退化。

LRU：最近最久未使用

淘汰最近一段时间内最久没有被访问的页面。符合”时间局部性”——最近被访问的页面很可能再次被访问。

精确实现需要每次访存都更新时间戳，硬件开销太大。实践中用近似 LRU。

💭 思考穿插：LRU 为什么要近似实现，而不是老老实实记「最近访问时间」？因为精确 LRU 要求每次访存都更新一个全局有序结构（比如链表把刚访问的页挪到头、或写时间戳），一次访存就得附带一次额外的内存写，这是不可接受的性能开销。而「时间局部性」给了我们偷懒的空间：我们其实不需要知道「最久没用」的精确排名，只需要知道「最近被碰过 / 没被碰过」这一比特信息——于是用硬件自动置位的访问位，就把「精确排序」降级成「近似判断」，性能回来了，效果还差不多。

Clock（二次机会）：近似 LRU 的工程实现

每个页面有一个”访问位”（由硬件自动置位——每次访问页面时 MMU 置该位为 1），OS 维护一个环形指针：

Clock 算法:
  指针指向当前候选页
  检查该页的访问位:
    = 1: 页面最近被访问过 → 清访问位（给"第二次机会"） → 指针前进
    = 0: 页面最近未被访问 → 淘汰该页 → 换入新页

时间复杂度 O(1)——最多转一圈。不需要维护时间戳，硬件自动更新访问位。Linux 使用改进版 Clock 算法——结合活跃链表（active list）和非活跃链表（inactive list），把”最近访问多次”的页从非活跃链提升到活跃链，从活跃链尾部淘汰降级到非活跃链。

💭 思考穿插：Clock 的「访问位」在 Linux 里到底对应什么？不是真的有一个物理位叫「Clock 位」，而是页描述符上的 PG_referenced 和 PG_active 两个标志，配合两条链表（active / inactive）模拟「第二次机会」：第一次被访问只置 referenced，再被访问就从 inactive 提升到 active——这跟 Clock 里「访问位=1 给第二次机会、再转一圈才淘汰」是同一种「两段式判断」。下面看内核真实源码（mm/swap.c）。

/* mm/swap.c —— 把页加入 LRU 链表：lru_add */
static void lru_add(struct lruvec *lruvec, struct folio *folio)
{
	int was_unevictable = folio_test_clear_unevictable(folio);
	long nr_pages = folio_nr_pages(folio);

	VM_BUG_ON_FOLIO(folio_test_lru(folio), folio);

	/*
	 * Is an smp_mb__after_atomic() still required here, before
	 * folio_evictable() tests the mlocked flag, to rule out the possibility
	 * of stranding an evictable folio on an unevictable LRU?  I think
	 * not, because __munlock_folio() only clears the mlocked flag
	 * while the LRU lock is held.
	 *
	 * (That is not true of __page_cache_release(), and not necessarily
	 * true of folios_put(): but those only clear the mlocked flag after
	 * folio_put_testzero() has excluded any other users of the folio.)
	 */
	if (folio_evictable(folio)) {
		if (was_unevictable)
			__count_vm_events(UNEVICTABLE_PGRESCUED, nr_pages);
	} else {
		folio_clear_active(folio);
		folio_set_unevictable(folio);
		/*
		 * folio->mlock_count = !!folio_test_mlocked(folio)?
		 * But that leaves __mlock_folio() in doubt whether another
		 * actor has already counted the mlock or not.  Err on the
		 * safe side, underestimate, let page reclaim fix it, rather
		 * than leaving a page on the unevictable LRU indefinitely.
		 */
		folio->mlock_count = 0;
		if (!was_unevictable)
			__count_vm_events(UNEVICTABLE_PGCULLED, nr_pages);
	}

	lruvec_add_folio(lruvec, folio);
	trace_mm_lru_insertion(folio);
}

lru_add 是「新页入链表」的底层动作：判断 folio 是否可回收（folio_evictable），可回收则挂到对应的 active/inactive 链表，否则清掉 active 标记、挂到 unevictable 链表（mlock 锁住的页）。它由 folio_add_lru 通过 folio_batch_add_and_move 批量延迟调用——这也是个性能细节，把逐页的加锁操作合并成批量处理。

/* mm/swap.c —— 访问位：folio_mark_accessed 的「两次机会」状态机（节选） */
 * This function will perform one of the following transitions:
 *
 * * inactive,unreferenced	->	inactive,referenced
 * * inactive,referenced	->	active,unreferenced
 * * active,unreferenced	->	active,referenced
 */
void folio_mark_accessed(struct folio *folio)
{
	if (folio_test_dropbehind(folio))
		return;
	if (lru_gen_enabled()) {
		lru_gen_inc_refs(folio);
		return;
	}

	if (!folio_test_referenced(folio)) {
		folio_set_referenced(folio);
	} else if (folio_test_unevictable(folio)) {
		/*
		 * Unevictable pages are on the "LRU_UNEVICTABLE" list. But,
		 * this list is never rotated or maintained, so marking an
		 * unevictable page accessed has no effect.
		 */
	} else if (!folio_test_active(folio)) {
		/*
		 * If the folio is on the LRU, queue it for activation via
		 * cpu_fbatches.lru_activate. Otherwise, assume the folio is in a
		 * folio_batch, mark it active and it'll be moved to the active
		 * LRU on the next drain.
		 */
		if (folio_test_lru(folio))
			folio_activate(folio);
		else
			__lru_cache_activate_folio(folio);
		folio_clear_referenced(folio);
		workingset_activation(folio);
	}
	if (folio_test_idle(folio))
		folio_clear_idle(folio);
}

这段就是 Clock「访问位」的 Linux 化身。文档注释直接点出状态机：第一次访问 inactive,unreferenced → inactive,referenced（只置 referenced，相当于 Clock 里访问位首次置 1）；再次访问且仍在 inactive，就 folio_activate 提升到 active（相当于给「第二次机会」）；已经 active 的页再访问则维持 active。用两个标志位 + 两条链表，把 Clock 的「环形指针转一圈」翻译成了「多档冷热分级」。

/* mm/swap.c —— inactive → active 的提升（旋转） */
static void lru_activate(struct lruvec *lruvec, struct folio *folio)
{
	long nr_pages = folio_nr_pages(folio);

	if (folio_test_active(folio) || folio_test_unevictable(folio))
		return;


	lruvec_del_folio(lruvec, folio);
	folio_set_active(folio);
	lruvec_add_folio(lruvec, folio);
	trace_mm_lru_activate(folio);

	__count_vm_events(PGACTIVATE, nr_pages);
	count_memcg_events(lruvec_memcg(lruvec), PGACTIVATE, nr_pages);
}

lru_activate 是「热页升级」动作：把 folio 从当前链表摘下来（lruvec_del_folio）、置 PG_active 标志、再挂回 active 链表（lruvec_add_folio）。这一「摘—置位—挂」就是 LRU 链表版 Clock 的「给第二次机会」，PGACTIVATE 计数还供内核统计热页提升频率。

/* mm/swap.c —— 旋转：把页挪回 inactive 链表尾部 */
static void lru_move_tail(struct lruvec *lruvec, struct folio *folio)
{
	if (folio_test_unevictable(folio))
		return;

	lruvec_del_folio(lruvec, folio);
	folio_clear_active(folio);
	lruvec_add_folio_tail(lruvec, folio);
	__count_vm_events(PGROTATED, folio_nr_pages(folio));
}

/*
 * Writeback is about to end against a folio which has been marked for
 * immediate reclaim.  If it still appears to be reclaimable, move it
 * to the tail of the inactive list.
 *
 * folio_rotate_reclaimable() must disable IRQs, to prevent nasty races.
 */
void folio_rotate_reclaimable(struct folio *folio)
{
	if (folio_test_locked(folio) || folio_test_dirty(folio) ||
	    folio_test_unevictable(folio) || !folio_test_lru(folio))
		return;

	folio_batch_add_and_move(folio, lru_move_tail);
}

这是 Linux LRU 里最接近字面「旋转」的部分：lru_move_tail 把一个还没写回完（dirty/writeback）的页清掉 active 标记、挪到 inactive 链表尾部（lruvec_add_folio_tail），相当于 Clock 里「访问位=1 先清位、把页甩到队尾再给一次机会」。淘汰扫描从 inactive 头部开始，挪到尾部就等于「延后淘汰」，PGROTATED 记录旋转次数。

LFU：最不频繁使用

淘汰被访问次数最少的页面。解决了 LRU 可能被偶发性的大规模读取冲掉热点的问题——偶发访问增加一次时间戳不代表”频繁使用”。

Redis 的 allkeys-lfu 内存淘汰用的就是 LFU：复用 lru 字段的高 16 bit 存衰减时间（ldt）、低 8 bit 存对数频次（logc），概率递增+时间衰减，避免历史热点长期霸占缓存。

总结

算法淘汰策略开销适用场景
OPT未来最远不可实现理论下界
FIFO最早进入O(1)简单场景（但有 Belady）
LRU最近最久未用高（需时间戳）时间局部性
Clock近似 LRUO(1)Linux 默认
LFU最少使用计数+衰减明显冷热分区

章末提问

Q1：为什么精确 LRU 不可行？Clock 到底省掉了什么开销？

回答思路：精确 LRU 要求每次访存更新全局有序结构（挪链表 / 写时间戳），等于每次访存附带一次额外内存写，硬件撑不住。Clock 把「精确最近性排序」降级成「一比特访问位 + 环形指针」，O(1) 且无额外时间戳写。省的是每次访存的维护成本，换来的是近似效果。

Q2：Clock 的访问位是谁置的？置位时机是什么？

回答思路：是**硬件（MMU）**在每次访问页时自动把该页的访问位（access bit）置 1，软件只负责读和清。置位发生在翻译/访问那一刻，对软件零开销；OS 淘汰时读访问位判断冷热，判断完清 0 重新计时，从而形成「上一轮有没有被访问过」的近似最近性信息。

Q3：Clock 和 Linux 的 active/inactive 双链表，是什么关系？

回答思路：Clock 是「单环 + 一比特」的一维近似；Linux 把它扩展成「双链表 + 多标志位」的多档分级：第一次访问置 referenced（inactive 内），再次访问提升到 active，active 尾部降级回 inactive，inactive 头部被回收。本质还是「访问位二次机会」思想，只是用链表位置代替了环形指针的位置。

Q4：FIFO 为什么有 Belady 异常，而 LRU / OPT 没有？

回答思路：LRU 和 OPT 满足「栈性质」——增加页框后，原缓存集合仍是新缓存集合的子集，所以缺页只减不增。FIFO 的淘汰依据「入队顺序」与访问模式脱钩，增加页框只是整体后移淘汰线，可能把本该保留的热点提前淘汰，于是加页框反而缺页更多。

Q5：LFU 相比 LRU 解决了什么问题，又有什么代价？

回答思路：LFU 解决「偶发大规模读取冲掉热点」——LRU 只认「最近」，一次扫描就把热点的「最近性」抹掉了；LFU 看「累计频率」，偶发访问加一次计数不足以撼动高频热点。代价是要维护计数，且历史热点会「长期霸占」缓存，所以工程上（如 Redis）要做对数频次 + 时间衰减，让旧热点随时间退热。

Share this post on:
Share this post via WhatsAppShare this post on FacebookShare this post on XShare this post via TelegramShare this post on PinterestShare this post via email
Previous Post
Cookie、Session、JWT——三种会话机制的选型与实践
Next Post
零拷贝——为什么Kafka和Nginx这么快？