2. LRU链表基础：LRU（最近最少使用）算法的基本原理、Linux内核中LRU链表的设计初衷与双链结构（active/inactive）

2.1 LRU算法的基本原理

LRU（Least Recently Used，最近最少使用）是一种经典的页面置换算法，其核心思想基于时间局部性原理：如果一个页面最近被访问过，那么它在不久的将来很可能再次被访问；反之，如果一个页面长时间未被访问，那么它被再次访问的概率较低。

LRU算法的基本工作流程如下：

  1. 访问命中：当CPU访问一个页面时，如果该页面已在内存中（页表项有效），则将该页面移动到LRU链表的头部（最近使用端）。
  2. 缺页处理：当发生缺页中断时，操作系统需要从后备存储（如磁盘交换区）加载页面到内存。
  3. 淘汰决策：如果内存已满，则选择LRU链表尾部（最久未使用端）的页面作为牺牲页面，将其换出到磁盘。
  4. 页面插入：新加载的页面被插入到LRU链表的头部。
关键指标：LRU算法的优劣取决于能否精确追踪每个页面的访问时间戳。理想情况下，每次页面访问都需要更新链表结构，这在硬件实现中代价极高。
LRU算法基本原理流程图 LRU算法基本原理流程 CPU访问页面 页面在内存中？ 命中 移到链表头部 缺页中断 淘汰 链表尾部页面 加载新页面 插入链表头部 说明： LRU算法的核心是维护一个按访问时间排序的链表。最近访问的页面在头部，最久未访问的页面在尾部。淘汰时总是选择尾部页面。

2.2 Linux内核中LRU链表的设计初衷

在Linux内核中，直接实现精确的LRU算法面临以下挑战：

挑战 描述 影响
硬件成本 每次页面访问都需要更新链表结构，这在现代CPU的TLB（快表）和MMU（内存管理单元）中无法高效实现 纯硬件LRU实现会显著增加芯片面积和功耗
并发访问 多核CPU同时访问页面时，对LRU链表的并发操作需要复杂的锁机制 锁竞争会降低系统性能，特别是在NUMA架构下
扫描开销 精确LRU需要维护全局有序链表，每次淘汰时扫描链表尾部 当内存页面数量达到百万级别时，扫描开销不可接受
工作集适应性 进程的工作集会动态变化，精确LRU对突发访问模式反应过慢 可能导致频繁的页面抖动（thrashing）
设计哲学：Linux内核采用近似LRU策略，通过双链表结构（active/inactive）和页面访问位（PG_referenced/PG_active）来模拟LRU行为，在精度和性能之间取得平衡。这种设计使得页面回收操作的时间复杂度从O(n)降低到接近O(1)。

Linux内核LRU链表的设计初衷可以概括为以下几点：

  • 降低维护成本：通过双链表结构，将页面分为活跃（active）和不活跃（inactive）两个集合，避免全局排序。
  • 提高回收效率：页面回收时优先从inactive链表尾部扫描，减少扫描范围。
  • 保护工作集：通过页面提升机制（promotion），确保频繁访问的页面不会被错误淘汰。
  • 支持NUMA：每个内存节点（node）和区域（zone）都有独立的LRU链表，减少跨节点访问。

2.3 双链结构：active与inactive链表

Linux内核的LRU系统由两个核心链表组成：active list（活跃链表）和inactive list（不活跃链表）。每个链表都维护着一个双向循环链表，页面通过lru字段链接。

两个链表的核心区别如下：

属性 active list（活跃链表） inactive list（不活跃链表）
存储页面 最近被频繁访问的页面 最近未被频繁访问的页面
淘汰优先级 低（优先保护） 高（优先回收）
页面数量目标 通常为inactive的2倍左右 通常为active的1/2左右
页面提升条件 页面从inactive提升而来 页面从active降级而来或新分配
扫描方向 从尾部扫描，检查是否需要降级 从尾部扫描，检查是否需要回收
Linux内核双链LRU结构图 Linux内核双链LRU结构（active/inactive） active list（活跃链表） 页面A 页面B 页面C 页面D ... ← 头部（最近使用） 尾部（最久未使用） → 降级（demotion） 提升（promotion） inactive list（不活跃链表） 页面E 页面F 页面G 页面H ... ← 头部（最近使用） 尾部（最久未使用） → 回收 关键机制： 页面在active和inactive链表之间通过提升（promotion）和降级（demotion）流动。新页面首先进入inactive链表尾部，被频繁访问后提升到active链表头部；长时间未被访问的active页面会被降级到inactive链表尾部。

2.4 页面状态与链表操作

每个页面在LRU系统中的状态由两个关键标志位控制：

  • PG_active：表示页面是否在active链表中。置位表示在active链表，清零表示在inactive链表。
  • PG_referenced：表示页面最近是否被访问过。每次页面访问时，MMU会设置页表项中的访问位（Accessed bit），内核通过ptep_clear_flush_young()等函数检查并清除该位。

页面在双链之间的流动遵循以下状态机：

当前状态 事件 下一状态 操作
inactive（未引用） 页面被访问 inactive（已引用） 设置PG_referenced
inactive（已引用） 再次被访问 active 提升到active链表头部，清除PG_referenced
active 长时间未被访问 inactive 降级到inactive链表尾部，清除PG_active
inactive（未引用） kswapd扫描 回收 尝试回收页面（如果为脏页则先写回）
注意：PG_referenced标志位与硬件页表项中的访问位（Accessed bit）不同。硬件访问位由MMU自动设置，内核通过定期检查并清除该位来模拟引用计数。PG_referenced是内核软件维护的二级引用标志，用于在inactive链表中区分页面是否被引用过。

2.5 内核数据结构与代码实现

在Linux内核源码中，LRU链表的核心数据结构定义在include/linux/mmzone.h中：

// 每个内存区域（zone）的LRU链表集合
struct lruvec {
    struct list_head        lists[NR_LRU_LISTS];  // 各类LRU链表头
    spinlock_t              lru_lock;             // 保护LRU链表的自旋锁
    unsigned long           anon_cost;            // 匿名页面的回收代价
    unsigned long           file_cost;            // 文件页面的回收代价
    // ... 其他字段
};

// LRU链表类型枚举
enum lru_list {
    LRU_INACTIVE_ANON = 0,  // 不活跃匿名页面
    LRU_ACTIVE_ANON = 1,    // 活跃匿名页面
    LRU_INACTIVE_FILE = 2,  // 不活跃文件页面
    LRU_ACTIVE_FILE = 3,    // 活跃文件页面
    LRU_UNEVICTABLE = 4,    // 不可回收页面
    NR_LRU_LISTS            // 链表总数
};

页面在LRU链表中的操作核心函数位于mm/vmscan.c：

// 将页面添加到LRU链表
static void lru_add_fn(struct lruvec *lruvec, struct page *page)
{
    int active = PageActive(page);      // 检查PG_active标志
    int file = page_is_file_lru(page);  // 判断是文件页还是匿名页
    int lru = page_lru(page);           // 计算LRU链表类型

    // 根据active和file确定链表索引
    if (active)
        lru += LRU_ACTIVE;
    else
        lru += LRU_INACTIVE;

    // 将页面添加到对应链表的尾部
    list_add_tail(&page->lru, &lruvec->lists[lru]);
}

// 页面提升：从inactive提升到active
static void activate_page(struct page *page)
{
    struct lruvec *lruvec = lock_page_lruvec(page);

    // 从当前链表删除
    del_page_from_lru_list(page, lruvec);
    // 设置active标志
    SetPageActive(page);
    // 添加到active链表头部
    add_page_to_lru_list(page, lruvec);
    unlock_page_lruvec(lruvec);
}

// 页面降级：从active降级到inactive
static void deactivate_page(struct page *page)
{
    struct lruvec *lruvec = lock_page_lruvec(page);

    // 从当前链表删除
    del_page_from_lru_list(page, lruvec);
    // 清除active标志
    ClearPageActive(page);
    // 清除引用标志
    ClearPageReferenced(page);
    // 添加到inactive链表尾部
    add_page_to_lru_list(page, lruvec);
    unlock_page_lruvec(lruvec);
}
性能优化：Linux内核使用批量操作来减少锁竞争。页面在加入LRU链表时，先被收集到per-CPU的lru_add_pvec向量中，当向量满或发生上下文切换时，再批量将页面添加到LRU链表。这种设计显著降低了自旋锁lru_lock的争用。

2.6 双链结构的优势与局限

Linux内核的双链LRU结构相比传统单链LRU具有以下优势：

  • 减少扫描开销：回收时只扫描inactive链表，避免遍历整个页面集合。
  • 保护工作集：active链表作为缓冲区，防止频繁访问的页面被错误淘汰。
  • 支持页面类型区分：通过NR_LRU_LISTS枚举，将匿名页和文件页分开管理，适应不同的回收策略。
  • NUMA友好：每个内存节点有独立的lruvec，页面回收在本地进行。

然而，该设计也存在一些局限性：

  • 近似性：双链结构只能近似模拟LRU行为，无法保证精确的最近最少使用顺序。
  • 提升延迟：页面需要两次访问才能从inactive提升到active，对于突发访问模式响应不够快。
  • 内存开销：每个页面需要额外的标志位（PG_active、PG_referenced）和链表指针。
  • 锁竞争：在内存压力大的场景下，lru_lock仍然是热点锁。
← 上一章 📖 返回目录 下一章 →