页面置换算法是虚拟内存系统的核心机制。当进程访问一个不在物理内存中的虚拟页时，CPU 触发缺页中断（Page Fault），操作系统必须从磁盘将该页调入物理内存，同时如果内存已满，还须选择一个牺牲页将其换出。这个"选谁出局"的策略，就是页面置换算法。
本文从缺页中断的完整处理流程讲起，逐一分析 FIFO、LRU、Clock、LFU 等经典算法及其变种，深入探讨 Belady 异常、栈算法理论与工作集模型，并最终剖析 Linux 内核实际的 LRU 平衡策略与 thrashing 抖动预防。
一、缺页中断处理流程
1.1 缺页中断的触发
当 CPU 尝试访问一个 Present 位为 0 的页表条目（PTE）时，MMU 产生页表遍历失败，通知 CPU 触发缺页异常（#PF，Page Fault Exception）。在 x86 架构中，页错误的错误码（Error Code）由硬件压入栈，包含以下关键信息：
- P（Present）：0 表示缺页，1 表示保护异常（权限不足）
- W/R：1 表示写入操作触发，0 表示读取
- U/S：1 表示用户态触发，0 表示内核态
操作系统的中断处理程序（do_page_fault 在 Linux 中）根据错误码和发生缺页的地址做决策。
1.2 缺页处理的核心路径
Linux 内核的缺页处理逻辑大致为：
1. 获取发生缺页的虚拟地址（cr2 寄存器）
2. 查找该进程的 VMA（Virtual Memory Area）结构
3. 检查访问权限合法性（读/写/执行与 vma->vm_page_prot 比对）
4. 分配物理页框（alloc_page）
5. 从磁盘/交换区读取数据填充页框
6. 更新页表（设置 PTE Present=1、PFN、访问权限）
7. 刷新 TLB（invlpg 或 flush_tlb_mm）
8. 恢复原进程执行
// Linux 4.x do_page_fault 简化的逻辑骨架
static noinline void
__do_page_fault(struct pt_regs *regs, unsigned long hw_error_code)
{
struct mm_struct *mm = current->mm;
unsigned long address = read_cr2(); // 触发缺页的地址
struct vm_area_struct *vma;
// 查找地址所在的 VMA
vma = find_vma(mm, address);
if (unlikely(!vma || vma->vm_start > address)) {
// 栈自动增长等特殊情况
if (unlikely(!expand_stack(vma, address)))
goto bad_area;
}
// 权限检查
if (unlikely(access_error(hw_error_code, vma)))
goto bad_area;
// 如果页表已存在但 Present=0，说明被 swap 出去了
// 如果页表不存在，需要新分配
fault = handle_mm_fault(vma, address, flags);
if (unlikely(fault & VM_FAULT_ERROR))
goto handle_error;
}
第 6 步中，handle_mm_fault 会调用底层的 alloc_page，此时如果空闲页框不足，就需要页面置换——选择一个牺牲页换出到交换区。
二、FIFO 先进先出算法
2.1 基本实现思路
FIFO（First-In-First-Out）是最朴素的置换策略：选择驻留内存时间最长的页面换出。维护一个队列即可实现。
#define MAX_FRAMES 4
#define MAX_PAGES 10
typedef struct {
int page_number;
int load_time; // 进入内存的时间戳
} Frame;
// FIFO 置换：选择 load_time 最小的页作为牺牲页
int fifo_replace(Frame frames[], int frame_count, int page, int current_time) {
// 检查是否已在内存中
for (int i = 0; i < frame_count; i++) {
if (frames[i].page_number == page)
return 0; // 命中，无需替换
}
// 查找最早进入的页
int victim = 0;
for (int i = 1; i < frame_count; i++) {
if (frames[i].load_time < frames[victim].load_time)
victim = i;
}
printf("Page %d replaces Page %d (FIFO victim)\n",
page, frames[victim].page_number);
frames[victim].page_number = page;
frames[victim].load_time = current_time;
return 1; // 发生缺页
}
2.2 Belady 异常
FIFO 存在一个反直觉的现象——Belady 异常（Belady’s Anomaly）：当分配的物理页框数增加时，缺页率不降反升。
以一个经典序列为例：1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
- 3 个页框时：缺页 9 次
- 4 个页框时：缺页 10 次
这是因为 FIFO 没有考虑页面的访问模式——一个很久前加载但频繁使用的页，和一个刚加载但只用一次的页，在 FIFO 眼中地位相同。Belady 异常的存在促使学术界寻找更优的替代算法。
三、LRU 最近最少使用算法
3.1 理论基础：最优算法的近似
理论上最优的置换策略是 OPT（Optimal Page Replacement）：选择未来最长时间不会被访问的页换出。由于需要预知未来访问序列，OPT 不可实现，但它为实际算法提供了性能上界。
LRU（Least Recently Used）基于"时间局部性"假设：如果一个页最近被访问过，它很可能在不久的将来再次被访问。因此选择最久未被使用的页换出。
// LRU 链表节点
typedef struct LRUSlot {
int page_number;
struct LRUSlot *prev;
struct LRUSlot *next;
} LRUSlot;
// 双向链表实现：表头为最新、表尾为最久未用
typedef struct {
LRUSlot *head;
LRUSlot *tail;
int capacity;
int size;
} LRUCache;
// 初始化 LRU 缓存
LRUCache* lru_init(int capacity) {
LRUCache *cache = calloc(1, sizeof(LRUCache));
cache->capacity = capacity;
return cache;
}
// 将节点移到表头（表示最近使用）
static void move_to_head(LRUCache *cache, LRUSlot *node) {
if (node == cache->head) return;
// 从原位置摘除
if (node->prev) node->prev->next = node->next;
if (node->next) node->next->prev = node->prev;
if (node == cache->tail) cache->tail = node->prev;
// 移到表头
node->next = cache->head;
node->prev = NULL;
if (cache->head) cache->head->prev = node;
cache->head = node;
}
// LRU 访问/替换
int lru_access(LRUCache *cache, int page) {
// 查找是否已在缓存中
LRUSlot *node = cache->head;
while (node) {
if (node->page_number == page) {
move_to_head(cache, node); // 命中，更新为最近使用
return 0;
}
node = node->next;
}
// 未命中，需要插入新页
LRUSlot *new_node = calloc(1, sizeof(LRUSlot));
new_node->page_number = page;
if (cache->size < cache->capacity) {
// 仍有空闲页框
new_node->next = cache->head;
if (cache->head) cache->head->prev = new_node;
cache->head = new_node;
if (!cache->tail) cache->tail = new_node;
cache->size++;
} else {
// 淘汰最久未使用的（表尾）
LRUSlot *victim = cache->tail;
cache->tail = victim->prev;
if (cache->tail) cache->tail->next = NULL;
printf("Page %d replaces Page %d (LRU victim)\n",
page, victim->page_number);
free(victim);
new_node->next = cache->head;
if (cache->head) cache->head->prev = new_node;
cache->head = new_node;
}
return 1; // 发生缺页
}
// 释放 LRU 缓存
void lru_free(LRUCache *cache) {
LRUSlot *node = cache->head;
while (node) {
LRUSlot *next = node->next;
free(node);
node = next;
}
free(cache);
}
3.2 LRU 的实现复杂度
双向链表 + 哈希表组合可以将 LRU 操作降到 O(1) 时间复杂度，但空间开销较大。实际操作系统中无法为每个页维护指针（内存占用过高），因此需要更轻量的近似方案——Clock 算法。
四、Clock 时钟算法与改进
4.1 第二次机会算法（Clock）
Clock 算法用**一个循环链表 + 一个引用位（reference bit）**近似 LRU。每个页框有一个访问位（硬件通常在 TLB 命中时置位）。算法维护一个指针在循环链表上移动：
- 遇到 reference bit = 1 的页，将其清零并给予"第二次机会"
- 遇到 reference bit = 0 的页，选择它作为牺牲页
#define NUM_FRAMES 4
typedef struct {
int page_number;
int ref_bit; // 访问位（硬件在访问时置位，Clock 扫描时清零）
int valid; // 是否被占用
} ClockFrame;
ClockFrame frames[NUM_FRAMES];
int clock_hand = 0; // 指针位置
// 模拟硬件设置访问位
void access_page(int page) {
for (int i = 0; i < NUM_FRAMES; i++) {
if (frames[i].valid && frames[i].page_number == page) {
frames[i].ref_bit = 1; // 命中，硬件置位
return;
}
}
}
// Clock 置换算法
int clock_replace(int page) {
// 检查命中
for (int i = 0; i < NUM_FRAMES; i++) {
if (frames[i].valid && frames[i].page_number == page) {
frames[i].ref_bit = 1;
return 0; // 命中
}
}
// 未命中，需要置换
while (1) {
int idx = clock_hand;
if (!frames[idx].valid || frames[idx].ref_bit == 0) {
// 找到牺牲页
if (frames[idx].valid) {
printf("Page %d replaces Page %d at hand=%d\n",
page, frames[idx].page_number, idx);
} else {
printf("Page %d loaded into empty frame %d\n",
page, idx);
}
frames[idx].page_number = page;
frames[idx].ref_bit = 0;
frames[idx].valid = 1;
clock_hand = (clock_hand + 1) % NUM_FRAMES;
return 1; // 缺页
}
// 给第二次机会，清零并前移指针
frames[idx].ref_bit = 0;
clock_hand = (clock_hand + 1) % NUM_FRAMES;
}
}
4.2 增强型时钟算法
Linux 内核实际上使用的是增强型时钟（Enhanced Clock），同时考虑：
- Referenced bit（R bit）：是否被访问过
- 修改位（Dirty bit / D bit）：页内容是否被修改过
四种组合给出不同的淘汰优先级：
| 优先级 | R bit | D bit | 说明 |
|---|---|---|---|
| 1（首选淘汰） | 0 | 0 | 未被访问、未修改——无额外开销直接回收 |
| 2 | 0 | 1 | 未被访问、已修改——需要写回磁盘 |
| 3 | 1 | 0 | 被访问、未修改——清零 R 后给予第二次机会 |
| 4（最后淘汰） | 1 | 1 | 被访问、已修改——最活跃，延后淘汰 |
五、LFU 最不经常使用与老化算法
5.1 LFU 基本思路
LFU（Least Frequently Used）选择访问次数最少的页换出。它与 LRU 的区别在于：LRU 关注"多久没用了"，LFU 关注"总共用了几次"。
#define NUM_PAGES 100
typedef struct {
int page_number;
int freq; // 访问计数
int timestamp; // 最后一次访问时间（解决频率相同的情况）
int valid;
} LFUSlot;
// LFU 置换：选择 freq 最小的页，频率相同则选 timestamp 最小的
int lfu_replace(LFUSlot slots[], int n, int page, int current_time) {
int found = -1;
for (int i = 0; i < n; i++) {
if (slots[i].valid && slots[i].page_number == page) {
slots[i].freq++;
slots[i].timestamp = current_time;
return 0; // 命中
}
}
// 未命中，找 victim
int victim = -1;
for (int i = 0; i < n; i++) {
if (!slots[i].valid) {
victim = i;
break;
}
if (victim == -1 ||
slots[i].freq < slots[victim].freq ||
(slots[i].freq == slots[victim].freq &&
slots[i].timestamp < slots[victim].timestamp)) {
victim = i;
}
}
printf("Page %d replaces Page %d (freq=%d)\n",
page, slots[victim].page_number, slots[victim].freq);
slots[victim].page_number = page;
slots[victim].freq = 1;
slots[victim].timestamp = current_time;
slots[victim].valid = 1;
return 1;
}
5.2 老化算法（Aging）
LFU 的问题是"历史包袱"——一个曾经频繁使用但当前不再使用的页不会很快被淘汰。老化算法（Aging）用移位寄存器解决此问题：
#define NUM_FRAMES 4
#define AGE_BITS 8
unsigned char age[NUM_FRAMES]; // 8 位老化寄存器
int page_in_frame[NUM_FRAMES];
// 每次时钟中断执行一次
void aging_tick(void) {
for (int i = 0; i < NUM_FRAMES; i++) {
age[i] = age[i] >> 1; // 右移一位
if (/* 硬件检测到该页被访问 */) {
age[i] = age[i] | 0x80; // 最高位置 1
}
}
}
// 选择 age 值最小的（最久未被集中访问）作为 victim
int aging_select_victim(void) {
int victim = 0;
for (int i = 1; i < NUM_FRAMES; i++) {
if (age[i] < age[victim])
victim = i;
}
return victim;
}
老化算法是 LRU 的近似，用 O(1) 空间和 O(1) 时间实现了近似 LRU 的行为。
六、工作集模型（Working Set）
6.1 局部性原理与工作集
Denning 提出的工作集模型（Working Set Model）认为：进程在某段时间内集中访问的页面集合是相对稳定的，称为工作集（Working Set）。工作集会随时间缓慢变化，但在短窗口内保持相对稳定。
工作集的正式定义为：在时间 t 之前的 Delta 时间窗口内，进程访问的所有不同页面的集合，记为 W(t, Delta)。
// 时间窗口 Delta = 4 的工作集计算示例
// 页面访问序列: 1, 2, 1, 3, 7, 4, 5, 6, 4, 5, 2, 1, 3, 5
typedef struct {
int page;
int last_access; // 最近访问时间
} PageInfo;
// 计算 t 时刻工作集：last_access >= t - Delta 的页面集合
#define DELTA 4
void compute_working_set(PageInfo pages[], int n, int current_time) {
int ws_size = 0;
printf("Working Set at t=%d (Delta=%d): { ", current_time, DELTA);
for (int i = 0; i < n; i++) {
if (pages[i].page != -1 &&
pages[i].last_access >= current_time - DELTA) {
printf("P%d ", pages[i].page);
ws_size++;
}
}
printf("} size=%d\n", ws_size);
}
// 示例序列分析：在 t=7 时，最近 Delta=4 次访问是 {4,5,6,4}，工作集为 {4,5,6}
// 在 t=10 时，最近 4 次访问是 {5,2,1,3}，工作集为 {5,2,1,3}
6.2 工作集模型的内存分配策略
基于工作集模型，操作系统可为每个进程分配等于其工作集大小的物理页框数：
- 如果所有进程的工作集之和 < 物理内存总量：系统运行良好
- 如果工作集之和 > 物理内存总量：发生 thrashing（抖动），页频繁换入换出
WS-Clock 算法将工作集与 Clock 算法结合：只考虑落在工作集窗口内的页作为受害者候选，保证不会把工作集中的活跃页换出。
七、Thrashing 抖动与预防
7.1 为什么会发生 Thrashing
当系统负载过高（进程数过多或进程内存需求过大），所有进程的工作集之和超过物理内存时，每触发一次缺页换入一个新页就必须换出一个正在使用的页，导致几乎所有进程都在等待页面 I/O，CPU 利用率骤降。
// 抖动检测：通过页错误频率（Page Fault Frequency, PFF）判断
#define PFF_THRESHOLD_HIGH 50 // 每秒缺页数过高
#define PFF_THRESHOLD_LOW 5 // 每秒缺页数正常
void monitor_thrashing(int pid, int page_faults_per_sec) {
if (page_faults_per_sec > PFF_THRESHOLD_HIGH) {
// 进程缺页过多，说明分到的页框不足
printf("PID %d: High PFF, increasing frame allocation\n", pid);
increase_frames(pid);
} else if (page_faults_per_sec < PFF_THRESHOLD_LOW) {
// 进程缺页很少，说明持有太多页框
printf("PID %d: Low PFF, frames can be reduced\n", pid);
}
}
7.2 抖动预防措施
- 工作集模型：为每个进程分配至少等于工作集大小的帧
- 页错误频率控制：动态调整各进程的页框配额
- 负载控制：当检测到抖动时，将部分进程换出到磁盘，降低内存压力
八、Linux 内核的实际策略
Linux 内核并未使用单一的页面置换算法，而是采用分层设计：
8.1 匿名页与文件页的分离
ew
Linux 将物理页分为两类：
- 匿名页（Anonymous pages）：进程堆栈、malloc 分配的内存——只能换出到 swap 分区
- 文件页（File-backed pages）：mmap 映射的文件、可执行文件代码段——可直接丢弃（因为文件本身就是 back store）
文件页的回收成本远小于匿名页，因此内核优先回收清洁的文件页。
8.2 Active/Inactive 双 LRU 列表
Linux 为每类页面维护了两个 LRU 列表：
- Active List：最近被访问过的页，更不容易被淘汰
- Inactive List：较久未访问的页，页面的"冷"状态
内核通过 page_referenced() 检查页是否被访问过（清除 Young bit），如果 inactive 列表中的页未被访问，则作为牺牲页；如果 active 列表中的页长期未被访问，则降级到 inactive。
8.3 swappiness 参数
/proc/sys/vm/swappiness（0-200）控制内核回收匿名页与文件页的倾向。默认值 60 表示在有足够文件缓存时优先回收文件页，但系统也会适度使用 swap。
相关阅读
- https://plumephp.com/os-virtual-memory/ —— 虚拟内存与分页机制的基础原理，是理解页面置换的必备背景
- https://plumephp.com/os-linux-memory/ —— Linux 内存子系统中关于 OOM Killer、cgroup 内存限制与 swap 机制的深入讲解
- https://plumephp.com/os-memory-allocation/ —— 从 malloc 到 mmap 的用户态内存分配底层实现
延伸阅读
- 《Operating System Concepts》第 10 章 —— 内存管理与页面置换的经典教材
- Peter Denning, “The Working Set Model for Program Behavior”, CACM 1968
- Linux Kernel Documentation:
Documentation/mm/ - ARC（Adaptive Replacement Cache）算法 —— IBM 提出的现代缓存管理方案
- 2Q 算法与 CAR（Clock with Adaptive Replacement）— 数据库缓存系统中的先进策略
// ============================================================
// 完整可运行示例：FIFO + LRU + Clock 的对比模拟
// 编译: gcc -o page_replace page_replace.c
// ============================================================
#include <stdio.h>
#include <stdlib.h>
#define NUM_FRAMES 3
#define SEQ_LEN 12
// FIFO 结构
typedef struct { int page; int load_time; } FIFOFrame;
int fifo_sim(int seq[], int len) {
FIFOFrame frames[NUM_FRAMES] = {{0}};
int faults = 0, time = 0;
for (int s = 0; s < len; s++) {
int page = seq[s], hit = 0;
for (int i = 0; i < NUM_FRAMES; i++)
if (frames[i].page == page && frames[i].load_time > 0) { hit = 1; break; }
if (!hit) {
int victim = 0;
for (int i = 1; i < NUM_FRAMES; i++)
if (frames[i].load_time == 0 ||
frames[i].load_time < frames[victim].load_time) victim = i;
frames[victim] = (FIFOFrame){page, ++time};
faults++;
}
}
return faults;
}
// Clock 结构
typedef struct { int page; int ref; int valid; } ClockFrame;
int clock_sim(int seq[], int len) {
ClockFrame frames[NUM_FRAMES] = {{0}};
int faults = 0, hand = 0;
for (int s = 0; s < len; s++) {
int page = seq[s], hit = 0;
for (int i = 0; i < NUM_FRAMES; i++)
if (frames[i].valid && frames[i].page == page) {
frames[i].ref = 1; hit = 1; break;
}
if (!hit) {
while (frames[hand].valid && frames[hand].ref == 1) {
frames[hand].ref = 0;
hand = (hand + 1) % NUM_FRAMES;
}
frames[hand] = (ClockFrame){page, 0, 1};
hand = (hand + 1) % NUM_FRAMES;
faults++;
}
}
return faults;
}
// LRU 结构
typedef struct { int page; int last_use; } LRUFrame;
int lru_sim(int seq[], int len) {
LRUFrame frames[NUM_FRAMES] = {{0}};
int faults = 0, time = 0;
for (int s = 0; s < len; s++) {
int page = seq[s], hit = 0;
for (int i = 0; i < NUM_FRAMES; i++)
if (frames[i].page == page && frames[i].last_use > 0) {
frames[i].last_use = ++time; hit = 1; break;
}
if (!hit) {
int victim = 0;
for (int i = 1; i < NUM_FRAMES; i++)
if (frames[i].last_use == 0 ||
frames[i].last_use < frames[victim].last_use) victim = i;
frames[victim] = (LRUFrame){page, ++time};
faults++;
}
}
return faults;
}
int main() {
int seq[SEQ_LEN] = {1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5};
printf("访问序列: 1 2 3 4 1 2 5 1 2 3 4 5\n");
printf("帧数: %d\n", NUM_FRAMES);
printf("FIFO 缺页次数: %d\n", fifo_sim(seq, SEQ_LEN));
printf("LRU 缺页次数: %d\n", lru_sim(seq, SEQ_LEN));
printf("Clock 缺页次数: %d\n", clock_sim(seq, SEQ_LEN));
return 0;
}
继续阅读
探索更多技术文章
浏览归档，发现更多关于系统设计、工具链和工程实践的内容。