Obsidian-Knowledge-Base/X-Knowledge-Base/raw/Joplin/深度解析/05-Linux内核设计与实现-原理与本质.md

---

tags: [source-summary] type: source source: "Linux内核设计与实现-原理与本质" author: "AI助手" date: 2026-09-19

created: 2026-09-19

Linux内核设计与实现：原理与本质

读完本文，你能理解

1. 为什么CFS选红黑树而不是其他数据结构
2. 伙伴系统怎么解决外部碎片
3. slab为什么要存在
4. 自旋锁irqsave为什么必须保存中断状态
5. 互斥体和信号量的关键区别
6. 中断下半部五种机制怎么选

---

1. 为什么选红黑树做CFS

锚点：CFS需要一个数据结构支持O(log n)的插入删除 + 快速获取vruntime最小的进程。红黑树通过rb_root_cached缓存最左节点，实现O(1)获取最小值。

红黑树的5个约束

graph TD
    A[红黑树性质] --> B[每个节点是红色或黑色]
    A --> C[根节点是黑色]
    A --> D[叶子节点NIL是黑色]
    A --> E[红色节点的子节点必须是黑色]
    A --> F[从任意节点到叶子的所有路径黑色节点数相同]

这些约束保证：最长路径不超过最短路径的2倍，查找/插入/删除都是O(log n)。

为什么不用其他数据结构

数据结构	查找最小值	插入	删除	问题
有序数组	O(1)	O(n)	O(n)	插入删除太慢
链表	O(n)	O(1)	O(1)	查找最小值太慢
二叉搜索树	O(log n)	O(log n)	O(log n)	可能退化成链表O(n)
红黑树	O(1)(cached)	O(log n)	O(log n)	平衡方案
哈希表	不适用	O(1)	O(1)	无法按顺序获取最小值

rb_root_cached的优化

早期Linux(<4.14)：每次获取最小vruntime需要从根遍历到最左节点(O(log n))。

优化后：rb_root_cached把rb_root和rb_node指针打包在一起，插入/删除时同步更新最左节点指针，获取最小值变成O(1)。

调度周期怎么影响vruntime

默认调度周期约6ms（HZ=250时）。每次时钟中断触发scheduler_tick()：

1. 更新当前进程的vruntime
2. 检查是否需要重调度
3. 如需重调度，设置TIF_NEED_RESCHED标志
4. 中断返回时检查此标志，触发schedule()

易错点

• ❌ 红黑树比AVL树好：不是，AVL更严格平衡（查找更快），但红黑树插入/删除更快（旋转次数少）。CFS选红黑树是因为调度器频繁插入删除
• ❌ vruntime越小优先级越高：不是，vruntime越小说明获得CPU时间越少，调度器会优先选择它
• ❌ CFS完全靠vruntime决策：还有唤醒抢占机制，刚唤醒的进程vruntime会被调整
• ❌ 红黑树最左节点就是最高优先级：最左节点是vruntime最小的，即最需要运行的，不等于优先级最高

来源：Linux内核04-进程调度与中断管理

---

2. 伙伴系统怎么解决外部碎片

锚点：伙伴系统按2的幂次管理空闲页，释放时检查伙伴是否也空闲，是则合并。这是解决外部碎片的经典方案。

什么是外部碎片

内存总空闲量够用，但没有连续的大块，分配大内存失败。就像停车场有10个空位但分散在各处，停不进一辆大巴。

伙伴系统的工作原理

graph TD
    A[空闲页总数16页] --> B[分配4页]
    B --> C[16页拆成8+8]
    C --> D[8页拆成4+4]
    D --> E[返回4页给请求者]
    E --> F[释放4页]
    F --> G{伙伴也空闲?}
    G -->|是| H[合并成8页]
    G -->|否| I[保持4页空闲]

11个free_list

order	页数	大小(4KB页)	用途
0	1	4KB	最小分配
1	2	8KB	小对象
2	4	16KB	常见分配
...	...	...	...
10	1024	4MB	大块分配

易错点

• ❌ 伙伴系统管理所有内存：只管理页(4KB)级别的分配，更小的由slab管理
• ❌ 碎片完全消除：内部碎片仍然存在，只是减少了外部碎片
• ❌ 释放时立即合并：不一定，取决于伙伴是否空闲
• ❌ FreeRTOS也有伙伴系统：FreeRTOS没有伙伴系统（没有MMU），Linux才有

来源：Linux内核04-进程调度与中断管理

---

3. slab为什么要存在

锚点：slab = 对象缓存池。频繁分配/释放小对象会导致页级内存碎片化，slab预分配一批对象，避免碎片+加速分配。

问题：伙伴系统分配小对象会怎样

假设频繁kmalloc(sizeof(struct task_struct))（几百字节）：

• 每次分配从伙伴系统取一个4KB页
• 页中只用了一小部分
• 大量半空的页导致内部碎片严重

slab的解决方案

graph TD
    A[slab缓存] --> B[对象池预分配]
    B --> C[kmalloc取一个: O1]
    C --> D[kfree归还: O1]
    D --> B
    A --> E[不够时向伙伴系统申请一整页]
    E --> B

易错点

• ❌ slab可以管理任意大小：slab适合小对象（几十到几千字节），大对象直接用伙伴系统
• ❌ slab和伙伴系统是替代关系：不是，slab在伙伴系统之上
• ❌ slab不会浪费内存：如果对象很少被使用，预留的对象会浪费内存
• ❌ kmalloc和__get_free_pages通用：kmalloc用kfree，__get_free_pages用free_pages，不能混用

来源：Linux内核04-进程调度与中断管理

---

4. 自旋锁irqsave为什么必须保存中断状态

锚点：spin_lock_irqsave()在获取自旋锁的同时禁止本地中断并保存之前的中断状态。因为无条件开关中断可能破坏中断状态。

问题场景：为什么不直接用spin_lock_irq

local_irq_disable();    // 中断已关闭
spin_lock_irq(&lock);   // 内部会 local_irq_enable() -> 错误地打开了中断！
// 临界区执行（中断竟然是开的）
spin_unlock_irq(&lock); // 中断状态被破坏

spin_lock_irq()无条件打开中断，如果之前中断已经被禁止，释放锁时会错误地改变中断状态。

irqsave的解决方案

unsigned long flags;
spin_lock_irqsave(&lock, flags);     // 禁止中断 + 保存状态到flags
// 临界区（中断关闭，安全）
spin_unlock_irqrestore(&lock, flags); // 恢复之前保存的中断状态

flags记录了进入前中断是开还是关，退出时恢复原状，不破坏任何状态。

自旋锁临界区的约束

• 可以：访问共享数据、短时间计算
• 不能：调用可能睡眠的函数（kmalloc GFP_KERNEL、msleep、mutex_lock）
• 不能：长时间占用（其他CPU空转等待，浪费资源）

spin_lock变体选择

函数	禁止什么	保存状态	适用场景
spin_lock	无	无	只需防止任务抢占
spin_lock_bh	下半部(softirq)	无	进程上下文与下半部竞态
spin_lock_irq	本地中断	无	确定中断之前是开的
spin_lock_irqsave	本地中断	是	不确定中断之前的状态

易错点

• ❌ spin_lock_irq和spin_lock_irqsave一样：不一样，irq无条件开中断可能破坏状态，irqsave保存恢复
• ❌ 自旋锁可以递归获取：不行，会死锁（自己等自己）
• ❌ spin_lock在SMP和UP上行为不同：是的，UP上spin_lock可能被编译为空操作
• ❌ 持有自旋锁可以睡眠：绝对不行，睡眠后其他CPU一直空转

来源：Linux驱动03-并发同步与原子操作

---

5. 互斥体和信号量的关键区别

锚点：互斥体(mutex)和信号量(semaphore)都能做互斥，但互斥体支持优先级继承，信号量不支持。这是两者最关键的区别。

对比表

特性	互斥体	信号量
计数	只能为1（互斥）	可以大于1（计数）
优先级继承	支持	不支持
持有者跟踪	记录持有者TCB	不记录
递归获取	不可以（会死锁）	不可以
ISR中使用	不可以	可以Give
临界区可以睡眠	可以	可以

优先级继承为什么是关键

场景：TaskL(优先级2)持有互斥锁，TaskH(优先级4)等待锁，TaskM(优先级3)抢占TaskL，TaskH被间接阻塞（优先级翻转）。

互斥体的解决方案：记录持锁者TCB，当高优先级任务等待时，临时提升持锁任务优先级，TaskM无法抢占，TaskL尽快释放锁。

信号量没有这个机制，所以优先级翻转问题不解决。

选择决策

graph TD
    A{需要互斥?} -->|否| B[不需要锁/per-CPU变量]
    A -->|是| C{临界区能睡眠?}
    C -->|否| D[自旋锁/原子操作]
    C -->|是| E{需要优先级继承?}
    E -->|是| F[互斥体mutex]
    E -->|否| G[信号量semaphore]

易错点

• ❌ 互斥体和信号量完全一样：不一样，优先级继承是关键区别
• ❌ 计数信号量等于互斥体：不是，计数信号量没有优先级继承，且初始值可以大于1
• ❌ 互斥体可以递归获取：普通互斥体不行（死锁），只有递归互斥体才行
• ❌ ISR可以获取互斥体：不行，互斥体可能睡眠，ISR不能睡眠

来源：Linux驱动03-并发同步与原子操作

---

6. 中断下半部五种机制怎么选

锚点：中断处理分为上半部（硬中断，快速响应硬件）和下半部（延迟处理，做耗时工作）。下半部有五种机制，核心区别是：能否睡眠、并发约束、开销大小。

五种机制对比

机制	执行上下文	能否睡眠	同一实例能并发?	开销
softirq	中断上下文	不能	可以	最低
tasklet	中断上下文	不能	不能（同tasklet串行）	低
workqueue	进程上下文	可以	可以	中
threaded_irq	内核线程	可以	可以	中

softirq：固定数量，编译时确定

• 只有10种类型（如NET_RX_SOFTIRQ、TIMER_SOFTIRQ）
• 驱动开发者不能添加新的softirq类型
• 每个CPU上串行执行
• 适用：网络收发、定时器等内核核心子系统

tasklet：基于softirq，可以动态创建

关键约束：同一个tasklet只能在一个CPU上运行，不同tasklet可以并行。同一tasklet内部不需要加锁保护共享数据。

workqueue：进程上下文，可睡眠

适用：需要等待硬件响应（如I2C传输完成、DMA完成）、需要分配大量内存、需要获取互斥锁。

threaded_irq

• 上半部：快速响应硬件，设置状态
• 内核线程：在普通进程上下文执行复杂后处理

选择流程

graph TD
    A[中断发生] --> B{需要睡眠?}
    B -->|是| C{需要复杂处理?}
    C -->|是| D[threaded_irq]
    C -->|否| E[workqueue]
    B -->|否| F{同一tasklet不能并发?}
    F -->|需要串行| G[tasklet]
    F -->|不需要| H[softirq]

易错点

• ❌ tasklet和softirq完全一样：不一样，同一tasklet不能并发（无需加锁），softirq可以
• ❌ workqueue在中断上下文执行：不是，在进程上下文（内核线程），可以睡眠
• ❌ 下半部不需要加锁：同一tasklet不需要，但不同tasklet之间、tasklet和进程上下文之间需要
• ❌ softirq可以无限扩展：只有10种，编译时固定，驱动应该用tasklet或workqueue
• ❌ 线程化中断性能很差：threaded_irq上半部仍然很快，只有后处理在线程中

来源：Linux驱动03-中断下半部处理

---

总结：Linux内核设计的核心思路

设计选择	原因
CFS用红黑树	O(log n)插入删除 + O(1)获取最小值
伙伴系统管理页	2的幂次分配+合并，减少外部碎片
slab管理小对象	O(1)分配释放，零碎片，cache友好
自旋锁irqsave	不破坏中断状态，安全保护临界区
互斥体有优先级继承	解决优先级翻转，保证实时性
中断下半部分层	上半部快（关中断），下半部慢（可睡眠）