linux LRU

<think>我们正在讨论Linux内核中的LRU（Least Recently Used）机制。根据引用内容，LRU机制用于管理内存回收，特别是文件页（file page）和匿名页（anon page）的回收。引用中提到了LRU链表的设计：分为活跃（ACTIVE）和非活跃（INACTIVE）两个状态，并且针对匿名页（ANON）和文件页（FILE）分别维护了四条LRU链表：LRU_INACTIVE_ANON, LRU_ACTIVE_ANON, LRU_INACTIVE_FILE, LRU_ACTIVE_FILE。 此外，引用[3]还提到，LRU链表是per cgroup和per node的，即每个内存控制组（cgroup）在每个NUMA节点上都有自己的一套LRU链表。 现在，我将详细解释Linux的LRU机制。 ### Linux LRU机制详解 在Linux内核中，当物理内存不足时，系统需要回收一些页面以释放内存。LRU（最近最少使用）是一种常用的页面置换算法，它根据页面的访问历史来决定哪些页面应该被回收。Linux对LRU算法进行了扩展，以适应不同的页面类型和内存管理需求。 #### 1. LRU链表分类 Linux内核将页面分为两种主要类型： - **匿名页（Anonymous pages）**：如进程的堆栈等，没有对应的文件背景。这些页面在回收时需要被交换到交换分区（swap）中。 - **文件页（File pages）**：有对应的文件背景（如缓存的文件数据）。这些页面在回收时可以直接丢弃（如果是干净页）或写回磁盘（如果是脏页）。 为了更精细地管理，内核为每种页面类型维护了两条链表： - **活跃链表（ACTIVE list）**：存放最近被访问过的页面。这些页面被认为是“热”的，不太可能被回收。 - **非活跃链表（INACTIVE list）**：存放最近未被访问的页面。这些页面是回收的主要候选。 因此，共有四条LRU链表： 1. `LRU_INACTIVE_ANON`：非活跃匿名页链表 2. `LRU_ACTIVE_ANON`：活跃匿名页链表 3. `LRU_INACTIVE_FILE`：非活跃文件页链表 4. `LRU_ACTIVE_FILE`：活跃文件页链表 #### 2. LRU链表的管理 当页面被首次访问时，它会被加入到对应类型的非活跃链表的头部。随着访问次数的增加，页面可能会被提升到活跃链表。内核通过“二次机会”算法（或类似机制）来管理这些链表：当页面被访问时，它会获得一个“机会”（通过设置访问标志），在页面回收时，如果该标志被置位，则页面会被重新放回链表头部并清除标志；否则，页面会被回收。 #### 3. 页面在链表间的移动 - **激活（Activation）**：当页面被访问时，如果它在非活跃链表中，内核可能会将其移动到活跃链表。但为了避免频繁移动，内核使用了一种策略：只有非活跃链表中的页面在被访问时，才会被移动到活跃链表。而活跃链表中的页面再次被访问时，通常只是更新其访问标志，并不立即移动（以避免锁竞争）。 - **回收（Reclaim）**：内存回收时，内核主要扫描非活跃链表。对于非活跃链表中的页面，如果它们最近没有被访问（即访问标志未被设置），则会被回收。回收匿名页需要交换到swap分区，而回收文件页（如果是干净的）则可以直接丢弃。 #### 4. Per-NUMA和Per-Cgroup的LRU 现代服务器通常是非一致性内存访问（NUMA）架构，即每个CPU节点有本地内存，访问远程内存较慢。为了优化性能，Linux为每个NUMA节点维护独立的LRU链表（引用[3]提到每个cgroup在每个node上都有自己的LRU链表）。这样，内存回收可以优先在本地节点进行，减少跨节点操作。 此外，为了支持控制组（cgroup），每个cgroup在每个NUMA节点上都有自己的LRU链表（即lruvec结构体）。这使得内存回收可以针对每个cgroup进行，从而实现更精细的资源控制。 #### 5. 内存回收过程 当内存不足时，内核会触发内存回收（kswapd或直接回收）。回收过程大致如下： 1. 首先尝试回收文件页（因为文件页回收通常更快，且不需要交换）。 2. 如果文件页回收不足，则回收匿名页。 3. 在回收时，优先扫描非活跃链表，然后才是活跃链表（活跃链表中的页面需要先被“老化”到非活跃链表）。 引用[1]提到，Linux设计优先回收文件页（因为文件页回收代价较低），所以文件页的非活跃链表（LRU_INACTIVE_FILE）是回收的首选。 #### 6. 引用计数和锁 每个页面都有一个引用计数（struct page的_refcount）和标志（flags）。LRU链表操作需要自旋锁保护（lruvec->lru_lock）。 ### 总结 Linux的LRU机制通过将页面按类型（文件页/匿名页）和活跃状态（活跃/非活跃）分类管理，实现了高效的内存回收。同时，结合NUMA架构和cgroup支持，提供了灵活的内存管理能力。 §§相关问题§§ 1. Linux中的LRU链表是如何维护页面访问历史的？ 2. 在内存回收过程中，文件页和匿名页的回收策略有何不同？ 3. 如何理解Linux LRU机制中的“二次机会”算法？ 4. NUMA架构对Linux的LRU机制有什么影响？ 5. 控制组（cgroup）如何利用LRU链表进行内存资源控制？</think>### Linux LRU 机制详解 Linux 的 LRU（Least Recently Used）机制是内核内存回收的核心算法，通过维护多个链表跟踪页面使用频率，优先回收最近最少使用的内存页。其设计充分考虑了**匿名页**（进程堆栈等无文件背景的内存）和**文件页**（缓存的文件数据）的不同特性。 #### 一、LRU 链表分类 内核维护四类 LRU 链表（详见引用[1][^1]）： 1. **活跃匿名页链表** - `LRU_ACTIVE_ANON`：存放频繁访问的匿名页（如进程堆、栈数据） 2. **非活跃匿名页链表** - `LRU_INACTIVE_ANON`：存放近期未访问的匿名页（回收时需交换到Swap） 3. **活跃文件页链表** - `LRU_ACTIVE_FILE`：存放高频访问的文件缓存页（如读写的文件数据） 4. **非活跃文件页链表** - `LRU_INACTIVE_FILE`：存放低频访问的文件缓存页（可直接丢弃或写回磁盘） > 设计优先回收文件页（因无需Swap操作），其次才是匿名页[^1]。 #### 二、LRU 工作机制 1. **页面访问与晋升** - 新分配的页面首先加入对应类型的**非活跃链表尾部** - 当页面被再次访问时，内核将其移至**活跃链表头部**（体现"最近使用"原则） - 示例流程： ```c // 伪代码：页面访问处理 mark_page_accessed(page) { if (page在非活跃链表) 移至活跃链表头部; else 设置页面访问标志(PG_referenced); } ``` 2. **页面老化与回收** - **双时钟扫描算法**：内核周期扫描活跃链表 - 若活跃页面的`PG_referenced`标志未置位（表示未再访问），则移至非活跃链表 - 保留访问频繁的页面在活跃链表 - 回收时优先扫描非活跃链表（先文件页后匿名页）： ```mermaid graph LR A[内存不足] --> B{扫描非活跃文件页链表} B -->|回收足够| C[结束] B -->|不足| D{扫描非活跃匿名页链表} D -->|仍不足| E[触发OOM Killer[^2]] ``` 3. **NUMA 与 Cgroup 优化** - **Per-NUMA-Node**：每个NUMA节点独立维护LRU链表，减少跨节点锁竞争 - **Per-Cgroup**：每个控制组（cgroup）拥有专属LRU链表（`lruvec`结构体），实现容器级内存隔离（引用[3][^3]） ```c struct lruvec { struct list_head lists[NR_LRU_LISTS]; // 四类LRU链表头 }; ``` #### 三、回收策略优化 1. **文件页 vs 匿名页** | 特性 | 文件页回收 | 匿名页回收 | |--------------|-------------------------------|--------------------------| | 代价 | 低（干净页直接丢弃） | 高（需Swap I/O） | | 优先级 | 优先回收（LRU_INACTIVE_FILE） | 次优先（LRU_INACTIVE_ANON）| | 二次机会 | 可重新从磁盘读取 | 交换区写入后不可恢复 | 2. **Swappiness 参数** 通过 `/proc/sys/vm/swappiness`（默认值60）调整匿名页回收倾向： - 值=0：禁用匿名页回收（除非内存耗尽） - 值=100：积极回收匿名页 #### 四、与 OOM Killer 的协同 当 LRU 回收无法释放足够内存时，触发 OOM Killer[^2]： 1. 计算进程的 `oom_score`（基于内存占用、CPU时间等） 2. 选择得分最高的进程终止以释放内存 > 引用案例：数据库服务因未限制 Cgroup 内存，触发 OOM 杀死关键进程[^2]。 ---