页替换如何工作，什么导致 thrashing？

Question

IT Interview Practice · Accepted Answer

当物理 RAM 满了但进程仍需要更多页时，操作系统必须**驱逐（evict）**一个驻留页来腾出空间——如果它是脏的（dirty）就把它写到 **swap**（磁盘）。驱逐哪个页是**页替换（page replacement）**的决策，做错它会毁掉性能。

## 替换策略

理论最优是驱逐将来最久才会被用到的页（**Bélády 的 OPT**）——这不可能实现，因为你看不到未来。所以我们近似 **LRU（least recently used，最近最少使用）**：驱逐最久未被使用的页。真正的 LRU 需要在每次访问时打一个时间戳（代价太高），所以真实的 kernel 使用 **clock（second-chance）算法**：

```text
Frames arranged in a ring; each has a REFERENCE bit the hardware sets on access.
A "hand" sweeps around the ring:
   ref bit = 1 → clear it, give the page a second chance, move on
   ref bit = 0 → evict THIS page (approximates "least recently used")

[1]→[1]→[0] ← evict here   (the sweep clears 1s until it finds a 0)
         ▲___________|
```

Clock 以 O(1) 的成本给出类似 LRU 的结果。Linux 用 **active/inactive LRU 链表**进一步细化它。

## Working set 与 thrashing

一个进程的 **working set** 是它在一个时间窗口内主动使用的那组页。*只要各 working set 之和能放进 RAM*，paging 就工作得很好。当放不下时：

```text
working set > RAM → evict a page that's about to be needed → immediate page fault →
evict another needed page → ... → the CPU spends ~all its time paging to disk, ~0% on real work
                            = THRASHING
```

Thrashing 是一道悬崖，不是一个斜坡：只要稍微越过极限，吞吐量就崩塌，因为几乎每次访问都 miss。症状：CPU 近乎空闲但磁盘 I/O 饱和，且延迟爆炸。

## 修复 / 避免它

- **加 RAM** 或**减负载**（更少的并发进程），让各 working set 放得下。
- Scheduler 可以**挂起并 swap-out** 整个进程以缩小需求（medium-term scheduling）。
- Linux 的 **OOM killer** 是最后手段——杀掉一个进程也好过永远 thrash。
- 改善**局部性（locality）**，让 working set 本身变小。

## 为什么这很重要

这把整个内存故事串在一起，也是一道受欢迎的 senior 题，因为 thrashing 是真实的生产故障模式：一个在 N 个用户时安然无恙的 service，会在 N+1 时随着 working set 超过 RAM 而跌落悬崖。识别其特征（大量 paging、磁盘饱和、CPU 停滞）并知道那些杠杆（RAM、减负载、局部性——以及 swap 会把内存不足变成延迟灾难），就是在几分钟内诊断出它、与对着一台神秘冻住的机器发呆之间的区别。

替换策略

Working set 与 thrashing

修复 / 避免它

为什么这很重要

相关问题