📘 第 7 章：进程调度

这一篇在干嘛？

多个进程”同时”运行是调度器变出来的魔术：它在极短时间内决定”什么时候切换、切换给谁”。本章讲清 Linux 2.6 调度器的策略与实现——静态/动态优先级、时间片、active/expired 双队列、O(1) 的进程挑选算法，以及多处理器系统上的负载均衡。这是全书最”工程”的一章，看懂它你就能回答”为什么我的交互程序不卡、编译却跑得慢”。

图 1：第 7 章章首插图

调度策略基础

传统 Unix 调度算法要在多个相互冲突的目标间走钢丝：快速响应、后台作业高吞吐、避免进程饿死、兼顾高低优先级。调度策略（scheduling policy）就是”何时以及如何挑选下一个运行进程”的整套规则。

Linux 调度的基础是分时（time sharing）：CPU 时间被切成片，每个可运行进程分一片。单处理器同一瞬间当然只能跑一个进程，但如果正在跑的进程在其时间片（time slice / quantum）用尽时还没结束，就可能发生进程切换。分时依赖定时器中断驱动，因此对进程完全透明——程序不用写任何额外代码就能被公平分时。

调度策略还基于优先级给进程排序。Linux 的优先级是动态的：调度器持续观察进程的行为、周期性调整优先级——长期没轮到 CPU 的进程被提优先级，长期霸占 CPU 的进程被降优先级。

谈到调度，进程有两个经典分类法。传统上分 I/O-bound（大量时间等 I/O）与 CPU-bound（埋头算数）两类；另一种分类更贴近调度器视角：

交互式进程：不断与用户打交道，大量时间等按键和鼠标。输入一来必须尽快唤醒，否则用户觉得系统迟钝——平均延迟要落在 50~150 毫秒之间，且波动也要小，否则用户觉得系统忽快忽慢。典型：shell、文本编辑器、图形程序。
批处理进程：不需要交互，常在后台跑，不需要响应性，调度器常”惩罚”它们。典型：编译器、数据库搜索引擎、科学计算。
实时进程：要求极其严格——绝不能被低优先级进程挡住，响应时间短且波动小。典型：视频音频程序、机器人控制器、传感器数据采集。

两种分类法相对独立：批处理进程既可能是 I/O-bound（数据库服务器）也可能是 CPU-bound（图像渲染）。Linux 调度算法明确识别实时程序，但没有简单办法区分交互式和批处理程序——Linux 2.6 用一个基于进程历史行为的启发式算法做判断，并天然偏向交互式进程（细节见后文的平均睡眠时间）。

程序员可通过一组系统调用影响调度：

系统调用	说明
`nice()`	修改常规进程的静态优先级
`getpriority()` / `setpriority()`	取/设一组常规进程的静态优先级
`sched_getscheduler()` / `sched_setscheduler()`	取/设进程的调度策略与实时优先级
`sched_getparam()` / `sched_setparam()`	取/设进程的实时优先级
`sched_yield()`	不阻塞地自愿让出处理器
`sched_get_priority_min()` / `sched_get_priority_max()`	取某策略的最小/最大实时优先级
`sched_rr_get_interval()`	取轮转策略的时间片
`sched_setaffinity()` / `sched_getaffinity()`	设/取进程的 CPU 亲和掩码

进程抢占与时间片长度的权衡

Linux 进程是可抢占的。当某进程进入 TASK_RUNNING 状态时，内核检查它的动态优先级是否高于当前运行进程——是则中断 current、调用调度器（通常就选刚变可运行的那个）。时间片用尽也会触发抢占：置位 current 的 thread_info 的 TIF_NEED_RESCHED 标志，定时器中断处理程序结束时调度器被调用。

一个具体场景感受全流程：系统里跑着文本编辑器（交互式，动态优先级高）和编译器（批处理）。编辑器大部分时间睡眠等按键；用户一敲键，键盘中断唤醒编辑器，内核发现它优先级高于 current（编译器），置编译器的 TIF_NEED_RESCHED；中断处理完毕，调度器选中编辑器、执行切换——用户敲的字符几乎立刻回显到屏幕。编辑器处理完字符又睡等下一键，编译器继续跑。

两个易混点要澄清：被抢占的进程不是被挂起——它仍处于 TASK_RUNNING 状态，只是暂时不再用 CPU；另外 Linux 2.6 内核本身是抢占式的，进程在内核态、用户态都可能被抢占（见 /linux内核/lk05）。

时间片多长才合适？

时间片长度对系统性能至关重要，太短太长都不行：

太短：进程切换的开销占比过高。假设一次切换要 5 毫秒、时间片也是 5 毫秒，那至少 50% 的 CPU 周期全耗在切换上。
太长：进程不再”看起来”在并发执行。假设时间片 5 秒，每个进程跑 5 秒就停很久（约 5 秒 × 可运行进程数）。

一个常见误解是”时间片长会拖慢交互程序的响应”——通常不对：交互进程优先级高，无论时间片多长都能迅速抢占批处理进程。但极端情况下长时间片确实伤响应性：两个用户同时敲命令，一个启动 CPU-bound 程序、一个启动交互程序，两个新进程初始优先级相同（Linux 无法预知程序是批处理还是交互）。若调度器先选中 CPU-bound 进程，交互进程就得干等一整个时间片——时间片越长，用户越觉得系统没反应。

Linux 的经验法则是：在保持良好响应时间的前提下，时间片尽可能长。

常规进程的调度

静态优先级与基本时间片

每个常规进程有一个静态优先级，取值 100（最高）到 139（最低）——数值越大优先级越低。新进程继承父进程的静态优先级；用户可用 nice()/setpriority() 传入”nice 值”修改自己进程的静态优先级。

静态优先级本质上决定进程的基本时间片（base time quantum）——时间片耗尽后重新获得的时长：

$base time quantum (ms) = {(140 - static priority) \times 20 (140 - static priority) \times 5 若 static priority < 120 若 static priority \geq 120$

静态优先级越高（数值越小），基本时间片越长——高优先级进程每次抢到 CPU 都跑得更久。几个典型值：

描述	静态优先级	Nice 值	基本时间片
最高静态优先级	100	-20	800 ms
高静态优先级	110	-10	600 ms
默认静态优先级	120	0	100 ms
低静态优先级	130	+10	50 ms
最低静态优先级	139	+19	5 ms

动态优先级与平均睡眠时间

调度器实际挑选进程时看的是动态优先级（同样 100~139），由经验公式给出：

$dynamic priority = max (100, min (static priority - bonus + 5, 139))$

bonus 取 0~10：小于 5 是惩罚（压低动态优先级数值会增大……注意方向），大于 5 是奖励。bonus 由进程的过去行为——精确说是平均睡眠时间（average sleep time）——决定。

平均睡眠时间粗略说是进程睡眠所花的平均纳秒数，但要注意它不是简单的时间平均：睡在 TASK_INTERRUPTIBLE 与 TASK_UNINTERRUPTIBLE 的”计分方式”不同；进程运行时平均睡眠时间会衰减；且上限 1 秒。对应关系：

平均睡眠时间	Bonus
0 ~ 100 ms	0
100 ~ 200 ms	1
200 ~ 300 ms	2
300 ~ 400 ms	3
400 ~ 500 ms	4
500 ~ 600 ms	5
600 ~ 700 ms	6
700 ~ 800 ms	7
800 ~ 900 ms	8
900 ~ 1000 ms	9
1 秒	10

背后的逻辑直白而聪明：睡得多说明在等外部事件，是交互式进程，多给 CPU；睡得少说明在狂算，是批处理进程，少给。这就是 Linux 区分交互式/批处理程序的核心启发式。

形式化的判据：一个进程被认定为”交互式”当且仅当

$dynamic priority \leq 3 \times static priority /4 + 28$

等价于 bonus - 5 ≥ static priority/4 - 28，其中 static priority/4 - 28 称为交互增量（interactive delta）。注意：静态优先级越高的进程越容易成为交互式。静态优先级 100 的进程 bonus 超过 2（平均睡眠超 200 ms）就算交互式；默认优先级 120 的进程要平均睡眠超 700 ms 才行；而最低优先级 139 的进程永远不可能被认定为交互式（需要的 bonus 11 超出了上限 10）。

Active 与 Expired：防饿死的双队列

高优先级进程拿到更大的时间片，但绝不能让低优先级进程彻底饿死。为此调度器维护两个不相交的可运行进程集合：

Active 进程：还没用完时间片，允许运行；
Expired 进程：时间片已用尽，必须等所有 active 进程过期后才能运行。

普通规则是：批处理进程时间片用完就进 expired；交互式进程时间片用完通常留在 active——调度器直接给它续满时间片。但有两条防止 expired 集饿死的例外：若最老的 expired 进程已等了很久，或某个 expired 进程的静态优先级高于这个交互式进程，交互式进程照样被丢进 expired。这样 active 集合终会变空，expired 进程终有出头之日。

实时进程的调度

每个实时进程有一个实时优先级，取值 1（最高）到 99（最低）。调度器永远偏向更高优先级的可运行进程——换句话说，只要实时进程还可运行，它就压制所有低优先级进程。与常规进程不同，实时进程总被视为 active。

实时进程有三种调度类：

SCHED_FIFO：先进先出。拿到 CPU 后进程描述符保持在运行队列当前位置，只要没有更高优先级的实时进程可运行，它想用多久用多久——即使同优先级的实时进程在排队也不让。
SCHED_RR：轮转。拿到 CPU 时进程描述符被放到运行队列末尾，同优先级的 SCHED_RR 进程公平分享 CPU。
SCHED_NORMAL（又称 SCHED_OTHER）：常规分时进程。

同一最高优先级有多个实时进程可运行时，调度器选本地 CPU 运行队列对应链表中的第一个（见 /linux内核/lk03）。

实时进程只有在以下事件发生时才会被换下：被更高实时优先级的进程抢占；执行阻塞操作入睡（TASK_INTERRUPTIBLE/TASK_UNINTERRUPTIBLE）；被停止或终止；自愿调用 sched_yield()；或是 SCHED_RR 且时间片用尽。

一个细节：对 SCHED_RR 进程施加 nice()/setpriority() 改的不是实时优先级，而是基本时间片——轮转实时进程的时间片不取决于实时优先级，而取决于静态优先级（用常规进程的公式 1 计算）。

调度器数据结构

runqueue：每个 CPU 一套

运行队列（runqueue）是 Linux 2.6 调度器最重要的数据结构，每个 CPU 一个，全部存于 per-CPU 变量 runqueues。this_rq() 取本地 CPU 的运行队列，cpu_rq(n) 取第 n 个的。关键字段：

字段	说明
`lock`	保护进程链表的自旋锁
`nr_running`	队列中可运行进程数
`cpu_load`	基于队列平均进程数的 CPU 负载
`nr_switches`	本 CPU 执行的进程切换次数
`nr_uninterruptible`	曾在队列中、现已睡入 `TASK_UNINTERRUPTIBLE` 的进程数（所有 CPU 之和才有意义）
`expired_timestamp`	expired 集合中最老进程的插入时刻
`timestamp_last_tick`	最近一次定时器中断的时间戳
`curr` / `idle`	当前运行进程 / 本 CPU swapper 进程的描述符指针
`prev_mm`	进程切换期间暂存被换下进程的内存描述符地址
`active` / `expired` / `arrays`	活跃集合指针 / 过期集合指针 / 两个集合本体
`best_expired_prio`	expired 进程中最好的静态优先级
`nr_iowait`	队列中曾可运行、现正等磁盘 I/O 的进程数

系统中每个可运行进程恰好属于一个运行队列，只要待在里面，就只能被拥有该队列的 CPU 执行——但后面会看到进程可以在队列间迁移。

图 2：runqueue 结构与两个可运行进程集合（active 指针指向一组 prio_array，expired 指向另一组）

arrays 字段是两个 prio_array_t 结构的数组。每个 prio_array_t 表示一组可运行进程，包含：140 个双向链表头（每个可能优先级一条链表）、一个优先级位图、进程计数。如图所示，active 指向其中一个 prio_array_t（active 进程），expired 指向另一个（expired 进程）。周期性地，两组的角色会整体对调——调度器只需交换 active 和 expired 两个字段的内容，active 进程瞬间变成 expired，反之亦然。

进程描述符中的调度字段

字段	说明
`thread_info->flags`	存放 `TIF_NEED_RESCHED` 标志
`thread_info->cpu`	所属运行队列的 CPU 逻辑号
`state`	进程当前状态
`prio` / `static_prio`	动态优先级 / 静态优先级
`run_list`	在所属运行队列链表中的前后指针
`array`	指向包含本进程的 prio_array_t
`sleep_avg`	平均睡眠时间
`timestamp`	最近一次插入运行队列 / 最近一次涉及本进程的切换时刻
`last_ran`	最近一次本进程被换下时刻
`activated`	进程被唤醒时的条件码（见后文表）
`policy`	调度类（SCHED_NORMAL/RR/FIFO）
`cpus_allowed`	允许执行本进程的 CPU 位掩码
`time_slice`	时间片剩余 tick 数
`first_time_slice`	从未用尽过时间片则置 1
`rt_priority`	实时优先级

新进程创建时，copy_process() 调用的 sched_fork() 这样切分时间片：

p->time_slice = (current->time_slice + 1) >> 1;   /* 子进程拿一半 */
current->time_slice >>= 1;                        /* 父进程留一半 */

父进程剩余的 tick 被一分为二。这是防”fork 轰炸”的妙招：如果没有它，用户可以让父进程不断 fork 出跑同一段代码的子进程再自杀，只要控制好节奏，子进程总能在父进程时间片耗尽前拿到全新时间片——CPU 时间被无限套取。切分之后这条路走不通了：内核不奖励 fork。同理，开一堆后台进程、开一堆窗口也占不到便宜。若父进程只剩 1 个 tick，切分会把 current->time_slice 变成 0，此时 copy_process() 把它恢复为 1 再调 scheduler_tick() 减掉。

copy_process() 还初始化子进程的两个字段：

p->first_time_slice = 1;   /* 从未耗尽时间片 */
p->timestamp = sched_clock();

first_time_slice 置 1 是因为子进程还没用完过时间片——若进程在第一个时间片内终止或执行新程序，父进程会得到孩子剩余的时间片作为奖励。sched_clock() 基本上返回 64 位 TSC 寄存器内容换算成的纳秒数（见 /linux内核/lk06）。

scheduler_tick：每个 tick 一次的调度脉搏

scheduler_tick() 每 tick 被 update_process_times() 调用一次（见 /linux内核/lk06），维护时间片计数器。主流程：

把 sched_clock() 的时间戳存入本地运行队列的 timestamp_last_tick；
若 current 是本地 CPU 的 swapper 进程：只要队列里还有别的可运行进程就置 TIF_NEED_RESCHED 强制重新调度，然后跳到第 7 步。（支持超线程时，逻辑 CPU 可能空闲而队列里有可运行进程——只要这些进程的优先级明显低于同一物理 CPU 另一逻辑 CPU 上正在运行的进程。）
若 current->array 不指向本地运行队列的 active 集合——进程已过期但还没被换下——置 TIF_NEED_RESCHED，跳到第 7 步；
拿 this_rq()->lock 自旋锁；
递减 current 的时间片并检查是否耗尽（按调度类分路处理，见下）；
放锁；
调 rebalance_tick() 做多核负载均衡。

实时进程的时间片更新

SCHED_FIFO 进程：什么都不做——它不可能被低或同优先级进程抢占，维护时间片毫无意义。

SCHED_RR 进程：递减并检查耗尽：

if (current->policy == SCHED_RR && !--current->time_slice) {
    current->time_slice = task_timeslice(current);  /* 按静态优先级续满 */
    current->first_time_slice = 0;
    set_tsk_need_resched(current);                  /* 强制重新调度 */
    list_del(&current->run_list);
    list_add_tail(&current->run_list,
        this_rq()->active->queue + current->prio);  /* 挪到队尾 */
}

时间片耗尽后：续满时间片、清 first_time_slice、置 TIF_NEED_RESCHED，再把进程描述符从优先级链表摘下、插回末尾——同优先级的其他实时进程先轮流各拿一片，这就是轮转的含义。

常规进程的时间片更新

递减 current->time_slice；
若耗尽：
- dequeue_task() 把 current 移出 active 集合；
- set_tsk_need_resched() 置 TIF_NEED_RESCHED；
- 更新动态优先级：current->prio = effective_prio(current)——按公式 2 由 static_prio 和 sleep_avg 算出；
- 续满时间片：current->time_slice = task_timeslice(current); current->first_time_slice = 0;
- 若运行队列的 expired_timestamp 为 0（expired 集空），写入当前 tick；
- 决定去向：

if (!TASK_INTERACTIVE(current) || EXPIRED_STARVING(this_rq())) {
    enqueue_task(current, this_rq()->expired);
    if (current->static_prio < this_rq()->best_expired_prio)
        this_rq()->best_expired_prio = current->static_prio;
} else
    enqueue_task(current, this_rq()->active);

TASK_INTERACTIVE() 按公式 3 判断是否交互式；EXPIRED_STARVING() 检查最老的 expired 进程是否已等待超过 1000 tick × (可运行进程数+1)，或 current 的静态优先级低于某个已过期进程（数值更大）——任一成立都说明 expired 集在挨饿，交互式进程也必须去 expired 排队。 3. 若时间片未耗尽，检查剩余时间片是否”太长”：

if (TASK_INTERACTIVE(p) &&
    !((task_timeslice(p) - p->time_slice) % TIMESLICE_GRANULARITY(p)) &&
    (p->time_slice >= TIMESLICE_GRANULARITY(p)) &&
    (p->array == rq->active)) {
    list_del(&current->run_list);
    list_add_tail(&current->run_list, this_rq()->active->queue + current->prio);
    set_tsk_need_resched(p);
}

TIMESLICE_GRANULARITY 是 CPU 数与随 bonus 变化的常数的乘积。效果：高静态优先级的交互式进程的时间片被切成几段，每段耗完就挪到本优先级链表尾部并触发重调度——防止它借超长时间片独霸 CPU。

唤醒与优先级重算

try_to_wake_up()

try_to_wake_up() 把睡眠或停止的进程唤醒：置状态为 TASK_RUNNING、插入运行队列。等待队列上的进程、等信号的进程都靠它唤醒。参数：进程描述符指针 p、可唤醒状态掩码 state、sync 标志（禁止被唤醒进程抢占本地 CPU 的当前进程）。

流程要点：

task_rq_lock() 关本地中断并拿进程上次所在 CPU 的运行队列锁（不一定是本地 CPU，CPU 号在 p->thread_info->cpu）；
检查 p->state 是否落在掩码内，否则收工返回 0；
若 p->array 非 NULL，进程已在某运行队列里，跳到第 8 步；
（SMP）决定要不要把进程迁移到别的运行队列。启发式规则：
- 有空闲 CPU 就选它——优先考虑上次执行它的 CPU，其次本地 CPU；
- 上次执行的 CPU 负载明显低于本地 CPU → 选老队列（进程缓存还在那边）；
- 进程最近刚执行过 → 选老队列（硬件缓存里可能还留着它的数据）；
- 把进程挪到本地 CPU 能减少不均衡 → 选本地队列。
若进程处于 TASK_UNINTERRUPTIBLE，目标队列的 nr_uninterruptible 减 1，并置 p->activated = -1；
activate_task() 完成插入：
- 取纳秒时间戳；若目标 CPU 不是本地 CPU，用两个 CPU 上最近定时器中断的时间戳补偿漂移；
- 调 recalc_task_prio() 重算动态优先级；
- 按表设置 p->activated；
- 更新 p->timestamp；
- enqueue_task(p, rq->active); rq->nr_running++; 插入 active 集合。
若目标 CPU 非本地或 sync 未设：比较新进程与 rq->curr 的动态优先级，更高（数值更小）则 resched_task() 抢占之。UP 上就是置 TIF_NEED_RESCHED；SMP 上若目标 CPU 的 TIF_NEED_RESCHED 原值为 0 且它没在轮询该标志，还会发 IPI（处理器间中断） 强制目标 CPU 重新调度；
置 p->state = TASK_RUNNING；
放锁、开中断、返回 1。

recalc_task_prio() 与 activated 字段

recalc_task_prio() 更新进程的平均睡眠时间和动态优先级，参数是描述符指针 p 和时间戳 now：

算 sleep_time = min(now - p->timestamp, 10^9)——上次入睡以来睡了多少纳秒，封顶 1 秒；
sleep_time 非正就跳过更新；
特殊照顾：若进程不是内核线程、正从 TASK_UNINTERRUPTIBLE 醒来（activated == -1）、且连续睡眠时间超过睡眠时间阈值（随静态优先级变化，见表 7-2），则直接把 sleep_avg 置为约 900 ticks 的等效值。这条经验规则的意图：长时间不可中断睡眠的进程通常在等磁盘 I/O，给它一个足够大（能快速被服务）又不至于引发饿死的平均睡眠时间；
用 CURRENT_BONUS 算旧 bonus，把 sleep_time 乘以 (10−bonus)——当前平均睡眠越低，涨得越快，避免睡惯了的进程一夜暴富；
若进程处于 TASK_UNINTERRUPTIBLE 且非内核线程：若 sleep_avg 已达睡眠时间阈值，sleep_time 清零；若 sleep_time + sleep_avg 超阈值，则 sleep_avg 钉在阈值上、sleep_time 清零。这一限制防止长睡的批处理进程被过度奖励；
sleep_avg += sleep_time；
sleep_avg 上限 1000 ticks 的纳秒数；
p->prio = effective_prio(p) 更新动态优先级。

activated 字段记录唤醒来源：

值	含义
0	进程原本就在 `TASK_RUNNING` 状态
1	从 `TASK_INTERRUPTIBLE`/`TASK_STOPPED` 被系统调用服务例程或内核线程唤醒
2	从 `TASK_INTERRUPTIBLE`/`TASK_STOPPED` 被中断处理程序或可延迟函数唤醒
-1	从 `TASK_UNINTERRUPTIBLE` 被唤醒

schedule() 里对 activated 的利用很讲究：若 next 是常规进程且正从 TASK_INTERRUPTIBLE/TASK_STOPPED 醒来，调度器把进程在运行队列里排队等待的时长也计入睡眠时间：

if (next->prio >= 100 && next->activated > 0) {
    unsigned long long delta = now - next->timestamp;
    if (next->activated == 1)
        delta = (delta * 38) / 128;   /* 同步唤醒只记 30% */
    array = next->array;
    dequeue_task(next, array);
    recalc_task_prio(next, next->timestamp + delta);
    enqueue_task(next, array);
}
next->activated = 0;

为什么区分唤醒来源？异步唤醒（中断处理程序、可延迟函数——想想用户敲键盘）更可能是交互式进程的特征，全额记入；同步唤醒（系统调用、内核线程）只记约 30%。

schedule 全流程

schedule() 实现调度器本体：从运行队列挑进程、把 CPU 交给它。调用方式有两种：

直接调用：current 需要立刻阻塞（所需资源不可用）时，内核例程按固定套路来：插入等待队列 → 置 TASK_INTERRUPTIBLE 或 TASK_UNINTERRUPTIBLE → 调 schedule() → 醒来后检查资源可用否，不可用回到第二步循环 → 可用则移出等待队列。很多执行长循环任务的设备驱动也直接调用：每轮迭代检查 TIF_NEED_RESCHED，置位就主动 schedule() 让出 CPU。

惰性调用：把 current 的 TIF_NEED_RESCHED 置 1——返回用户态前内核总会检查该标志，schedule() 注定很快被执行。典型触发者：时间片耗尽（scheduler_tick()）、唤醒了优先级更高的进程（try_to_wake_up()）、sched_setscheduler() 系统调用。

切换前的准备

need_resched:
preempt_disable();
prev = current;
rq = this_rq();

禁抢占，存下 prev 和本地运行队列。先处理大内核锁——若 prev 持有 BKL（lock_depth >= 0）就释放（up(&kernel_sem)）但不改 lock_depth，prev 恢复执行时会自动重新获取（见 /linux内核/lk05）。

接着记账：

now = sched_clock();
run_time = now - prev->timestamp;   /* prev 本次用了多久 */
if (run_time > 1000000000)
    run_time = 1000000000;          /* 封顶 1 秒 */
run_time /= (CURRENT_BONUS(prev) ? : 1);  /* 平均睡眠越久，记账越少 */

注意最后一行：平均睡眠时间长的进程（交互式）少记 CPU 使用量，从而运行时 sleep_avg 衰减得慢——交互性得以保持。

然后 spin_lock_irq(&rq->lock) 关中断拿运行队列锁，并处理 prev 的状态：

if (prev->flags & PF_DEAD)
    prev->state = EXIT_DEAD;
if (prev->state != TASK_RUNNING && !(preempt_count() & PREEMPT_ACTIVE)) {
    if (prev->state == TASK_INTERRUPTIBLE && signal_pending(prev))
        prev->state = TASK_RUNNING;   /* 有挂起信号：留在队列 */
    else {
        if (prev->state == TASK_UNINTERRUPTIBLE)
            rq->nr_uninterruptible++;
        deactivate_task(prev, rq);    /* 移出运行队列 */
    }
}

prev 是正在终止的进程就标 EXIT_DEAD；prev 不可运行且非内核态被抢占，则移出运行队列——但若它是 TASK_INTERRUPTIBLE 且有未阻塞的挂起信号，就改回 TASK_RUNNING 留在队列里（这不是把 CPU 给它，只是给它被选中的机会）。

挑选下一个进程

队列里还有可运行进程时，先问 dependent_sleeper()（超线程专用：若候选进程优先级明显低于同一物理 CPU 另一逻辑 CPU 上正在跑的进程，宁可跑 swapper 也不选它）。

队列空了就先自救：调 idle_balance() 试图从别的运行队列搬进程过来（类似 load_balance()）；再失败则 wake_sleeping_dependent() 唤醒空闲逻辑 CPU 上的进程（超线程场景）；还不行，next 就是 swapper 进程。

有可运行进程后，检查 active 集是否为空——空则交换 active 和 expired 两个字段：

array = rq->active;
if (!array->nr_active) {
    rq->active = rq->expired;
    rq->expired = array;
    ...
}

expired 集合整体转正。然后 O(1) 挑选：

idx = sched_find_first_bit(array->bitmap);
next = list_entry(array->queue[idx].next, task_t, run_list);

bitmap 中置位的位对应非空的优先级链表；sched_find_first_bit() 基于 bsfl 指令找出第一个置位位——就是最高优先级链表的索引，取该链表第一个进程。挑选时间与可运行进程数量无关，这正是 2.6 调度器被称为 O(1) 调度器的原因。

对刚唤醒进程的特殊处理

如前节所述，若 next 是常规进程且 activated > 0，把在队列里等待的时间（按唤醒来源打折）计入平均睡眠时间后重算优先级，再插回队列。

执行切换

switch_tasks:
prefetch(next);                       /* 预取 next 描述符进缓存 */
clear_tsk_need_resched(prev);         /* 清惰性调度标志 */
rcu_qsctr_inc(prev->thread_info->cpu);/* 记录一次 RCU 静息状态 */
prev->sleep_avg -= run_time;          /* 收 CPU 使用费 */
if ((long)prev->sleep_avg <= 0)
    prev->sleep_avg = 0;
prev->timestamp = prev->last_ran = now;
if (prev == next) {                   /* 没有更合适的人选 */
    spin_unlock_irq(&rq->lock);
    goto finish_schedule;
}
next->timestamp = now;
rq->nr_switches++;
rq->curr = next;
prev = context_switch(rq, prev, next);

context_switch() 负责地址空间切换，关键在 mm 与 active_mm 两个字段：普通进程两者相同；内核线程没有自己的地址空间，mm 恒为 NULL。若 next 是内核线程，就借用 prev 的地址空间：

if (!next->mm) {
    next->active_mm = prev->active_mm;
    atomic_inc(&prev->active_mm->mm_count);
    enter_lazy_tlb(prev->active_mm, next);   /* 惰性 TLB 模式 */
}

这是历史教训换来的优化：Linux 2.2 之前内核线程有自己的地址空间，每次切换都要改页表——但内核线程只在内核态跑、只使用第 4 个 GB 的线性地址空间（全系统映射相同），改页表纯属浪费，何况写 cr3 寄存器会使所有 TLB 项失效，性能损失巨大。如今内核线程切换完全不碰页表，还顺手进入惰性 TLB 模式（见 /linux内核/lk02）。

反之，next 是普通进程就正式换地址空间：

if (next->mm)
    switch_mm(prev->active_mm, next->mm, next);
if (!prev->mm) {              /* prev 是内核线程或退出中的进程 */
    rq->prev_mm = prev->active_mm;
    prev->active_mm = NULL;
}
switch_to(prev, next, prev);  /* 真正的进程切换 */
return prev;

切换之后

switch_to 之后的指令不会立刻被 next 执行，而是等 prev 将来再次被调度时才接着跑——而且那时的 prev 局部变量指向的是”当初替换了我们主角的那个进程”（想不通就回去重读 /linux内核/lk03 的进程切换一节）。恢复后的第一步：

barrier();
finish_task_switch(prev);

finish_task_switch() 取出 rq->prev_mm（借给内核线程 prev 的内存描述符），放锁开中断；mm 非空则 mmdrop() 递减其引用计数（减到 0——多半因为 prev 是僵尸进程——就连页表和虚拟内存区域一起释放）；若 prev 带着 PF_DEAD 标志，put_task_struct() 清理最后的引用。

schedule() 的收尾：

prev = current;
if (prev->lock_depth >= 0)
    __reacquire_kernel_lock();     /* 重新拿大内核锁 */
preempt_enable_no_resched();
if (test_bit(TIF_NEED_RESCHED, &current_thread_info()->flags))
    goto need_resched;             /* 期间又被要求调度？重头再来 */
return;

常见坑：把"被抢占"当成"被挂起"

被抢占的进程仍在 TASK_RUNNING 状态、仍在运行队列里，只是暂时不用 CPU；被挂起（睡眠）的进程已移出运行队列、状态变成了 TASK_INTERRUPTIBLE/TASK_UNINTERRUPTIBLE。调度器决定要不要把 prev 移出队列时正是靠区分这两种情况（preempt_count() & PREEMPT_ACTIVE 就是”内核态被抢占”的标记）。

多核负载均衡

三种多处理器架构

schedule() 从本地 CPU 的运行队列挑进程，而每个可运行进程只待在一个队列里——所以可运行进程通常绑定在一个 CPU 上。这对缓存友好，但会造成失衡：一堆 CPU 密集的批处理进程挤进同一个队列，一个 CPU 忙死、其他 CPU 闲死。内核必须周期性地在运行队列之间搬进程。而”怎么搬”取决于硬件拓扑：

经典 SMP：所有 CPU 共享同一组 RAM 芯片，内存仲裁器是瓶颈；
超线程：一个物理芯片同时执行多条线程（内部寄存器有多份，线程间快速切换），利用当前线程等内存时的空转周期跑另一条线程。Linux 把一个超线程物理 CPU 看成多个逻辑 CPU；
NUMA：CPU 和 RAM 分组为本地”节点”（通常一节点一 CPU 加几块 RAM）。访问本地内存几乎无争用、很快；访问远程节点的内存慢得多。

这些形态还会组合：一块插两颗超线程 CPU 的主板在内核眼里是 4 个逻辑 CPU。

调度域

从 2.6.7 起，负载均衡基于调度域（scheduling domain）：一组由内核保持负载均衡的 CPU。调度域按层级组织——最顶层域通常横跨全系统所有 CPU，向下包含子域。每个域再分成一个或多个组（group），负载均衡永远发生在同一域内的组之间：只有某组的总负载显著低于同域另一组时，才在它们之间搬进程。层级结构让均衡操作在”就近”的 CPU 之间进行，尊重硬件拓扑。

图 2：三种调度域层级示例（(a) 2-CPU 经典 SMP：单层域两个组；(b) 2 物理核超线程：顶层域跨 4 逻辑 CPU、每个物理 CPU 一个子域；(c) 8-CPU 双节点 NUMA：顶层按节点分组、每节点一个基本域）

每个调度域由 sched_domain 描述符表示，域内每个组由 sched_group 描述符表示；sched_domain.groups 指向组链表，parent 指向父域。所有物理 CPU 的域描述符存于 per-CPU 变量 phys_domains：不支持超线程时它们就是基本域（runqueue 的 sd 字段指向它们）；支持超线程时基本域存于 cpu_domains。

rebalance_tick() / load_balance() / move_tasks()

scheduler_tick() 每 tick 调 rebalance_tick()：先更新运行队列的 nr_running 和平均负载 cpu_load，然后从基本域到顶层域逐层循环，按 idle 参数和域内参数决定是否到点调 load_balance()。本地 CPU 空闲（SCHED_IDLE）时调用很勤（逻辑/物理 CPU 对应的域大约每 1~2 tick 一次）；忙碌（NOT_IDLE）时很省（逻辑 CPU 域约每 10 毫秒、物理 CPU 域约每 100 毫秒一次）。

load_balance() 检查某调度域是否显著失衡——能否通过把进程从最忙组挪到本地运行队列来减小不均衡。流程：

拿 this_rq->lock；
find_busiest_group() 分析域内各组负载，返回最忙组的描述符（前提是该组不含本地 CPU）和应搬入的进程数；最忙组含本地 CPU 或各组基本均衡则返回 NULL——此时放锁、调整域参数推迟下次检查、结束；
find_busiest_queue() 找出最忙组里最忙的 CPU，得其运行队列 busiest；
拿 busiest->lock——为防死锁，须先放 this_rq->lock，再按 CPU 编号递增顺序依次获取两把锁；
move_tasks() 尝试搬进程；
若一个都没搬动（域仍失衡），置 busiest->active_balance = 1 并唤醒 busiest->migration_thread 迁移内核线程——它沿调度域链从基本域走到顶层找一个空闲 CPU，找到就把一个进程挪过去；
放两把锁，结束。

move_tasks() 先扫最忙队列的 expired 进程（从高优先级开始），再扫 active 进程。对每个候选进程调 can_migrate_task()，满足以下全部条件才可搬：

进程当前没在远端 CPU 上执行；
本地 CPU 在进程的 cpus_allowed 掩码内；
以下至少一条成立：本地 CPU 空闲（支持超线程时要求本地物理芯片的所有逻辑 CPU 都空闲）；或调度域反复搬迁都失败、均衡陷入困境；或进程不”cache 热”（最近没在远端 CPU 执行，其数据大概率不在远端缓存里——搬走不亏）。

可搬则 pull_task()：dequeue_task() 摘出 → enqueue_task() 插入本地队列 → 若搬来的进程动态优先级高于本地 current，resched_task() 抢占之。

通关标准

能不看书画出 Linux 2.6 调度器的全图：每个 CPU 一个 runqueue，内含 active/expired 两个 prio_array（各 140 条优先级链表 + 位图）；scheduler_tick 每 tick 减时间片、按交互式与否决定进 active 续片还是进 expired；schedule() 用 sched_find_first_bit 在位图上 O(1) 找最高优先级链表的头一个进程；唤醒路径经 try_to_wake_up → recalc_task_prio 按平均睡眠时间调动态优先级；多核由 rebalance_tick/load_balance 沿调度域层级搬进程。

调度系统调用

通用规则：用户随时可以降低自己进程的优先级；要提高优先级或修改他人进程的优先级，必须有超级用户权限（CAP_SYS_NICE 能力）。

nice() 与 getpriority()/setpriority()

nice() 用 increment 参数修改进程描述符的 nice 字段（Unix 的 nice 命令基于它）。绝对值超过 40 的增量被裁剪到 40；负增量（提高优先级）需要 CAP_SYS_NICE 能力，还要过 security_task_setnice() 安全钩子。sys_nice() 把 current->static_prio 换算到 nice 值域、加增量，然后 set_user_nice() 更新静态优先级并 resched_task() 允许其他进程抢占 current。该调用仅为向后兼容保留，已被 setpriority() 取代。

getpriority() 返回 20 减去某组进程中最低的 nice 值（即组内最高优先级）；setpriority() 给整组进程设优先级。两者的 which 参数选组方式：PRIO_PROCESS（按 pid）、PRIO_PGRP（按进程组 pgrp）、PRIO_USER（按 uid）；who 是对应的 id 值（0 表示 current 自己的）。由于系统调用出错才返回负值，getpriority() 不返回 -20~+19 的 nice 值，而是返回 1~40 的非负值。

CPU 亲和性：sched_getaffinity()/sched_setaffinity()

亲和掩码是允许执行该进程的 CPU 位掩码，存于 cpus_allowed 字段。sys_sched_getaffinity() 用 find_task_by_pid() 找到描述符，返回 cpus_allowed 与可用 CPU 位图按位与的结果。sys_sched_setaffinity() 复杂些：更新掩码后要检查进程是否还在新掩码之外的 CPU 的运行队列里，最坏情况要把进程搬到别的运行队列——为避免死锁和竞态，搬家交给每 CPU 一个的迁移内核线程：唤醒 rq1->migration_thread，由它把进程从 rq1 摘出插入 rq2。

实时进程相关

sched_getscheduler(pid)：查询策略（SCHED_FIFO/SCHED_RR/SCHED_NORMAL，后者也叫 SCHED_OTHER）；pid 为 0 表示调用进程自己。
sched_setscheduler(pid, policy, param)：同时设策略和参数。do_sched_setscheduler() 校验策略与 param->sched_priority 的合法性、检查 CAP_SYS_NICE 能力，然后把进程从运行队列摘出（若可运行）、更新静态/实时/动态优先级、插回队列，必要时 resched_task() 抢占队列当前进程。
sched_getparam(pid) / sched_setparam(pid, param)：取/设实时优先级；setparam 与 setscheduler 的区别是不能改 policy 字段。
sched_yield()：进程自愿让出 CPU 而不被挂起——保持 TASK_RUNNING，但常规进程被挪进 expired 集合、实时进程被挪到运行队列链表尾部，然后调 schedule()。主要被 SCHED_FIFO 实时进程使用。
sched_get_priority_min(policy) / sched_get_priority_max(policy)：返回某策略可用的最小/最大实时优先级（min 返回 1、max 返回 99，仅当 current 是实时进程，否则返回 0）。
sched_rr_get_interval(pid)：把 pid 进程的轮转时间片换算成秒+纳秒写回用户态结构；按惯例 FIFO 实时进程的时间片为 0。

为什么 Linux 2.6 调度器被称为 O(1) 调度器？

因为选中下一个进程的时间与可运行进程的数量无关：active 集合的位图上，sched_find_first_bit() 一条 bsfl 指令就能找到第一个（最高优先级的）非空链表索引，取链表头即可。旧版调度器每次切换要扫描全部可运行进程、逐一计算优先级，进程数上千时开销不可接受。

平均睡眠时间如何既奖励交互进程、又不让长睡的批处理进程冒充交互进程？

三重机制：bonus 由 sleep_avg 分档映射，动态优先级 = static − bonus + 5；recalc_task_prio 里 sleep_time 先乘 (10−旧bonus)，睡得越少涨得越快，睡多了涨得慢；对不可中断长睡（典型是等磁盘 I/O 的批处理）专门设了按静态优先级变化的睡眠时间阈值，超过就钉住 sleep_avg 不再增长。此外 schedule() 记账时 run_time 除以 bonus，交互进程的 sleep_avg 衰减也更慢。

交互式进程时间片用完后"留在 active 续片"，会不会让 expired 进程永远饿死？

不会。两条保险丝：EXPIRED_STARVING() 检查最老 expired 进程是否等待超过 1000×(可运行数+1) ticks，超时则交互式进程也强制进 expired；若某 expired 进程静态优先级高于该交互式进程，同样强制过期。极端情况下 active 集必会清空、触发 active/expired 整体交换。

为什么内核线程切换时不必切换页表，而普通进程切换必须切换？

内核线程没有自己的地址空间（mm 为 NULL），只在内核态运行、只使用所有进程共享相同映射的线性地址空间第 4 个 GB。context_switch() 让它借用 prev 的 active_mm，页表一个字都不用改，还进入惰性 TLB 模式；写 cr3 换页表会清空整个 TLB，代价巨大。

fork 时为什么要把父进程剩余时间片对半分给子进程？

防止 fork 轰炸套取 CPU 时间：若无此规则，父进程可以不断 fork 出执行相同代码的子进程再自杀，只要节奏合适，子进程总能在父进程时间片耗尽前拿到全新时间片，CPU 时间被无限复制。对半分后，fork 出来的”新生命”消耗的是父进程自己的预算。同样道理，开一堆后台进程或窗口也占不到便宜。

description	拆解 Linux 2.6 O(1) 调度器：优先级、时间片、active/expired 双队列与多核负载均衡
tags	linux内核

嵌入式开发之路

探索

📘 第 7 章：进程调度

调度策略基础

进程抢占与时间片长度的权衡

时间片多长才合适？

常规进程的调度

静态优先级与基本时间片

动态优先级与平均睡眠时间

Active 与 Expired：防饿死的双队列

实时进程的调度

调度器数据结构

runqueue：每个 CPU 一套

进程描述符中的调度字段

scheduler_tick：每个 tick 一次的调度脉搏

实时进程的时间片更新

常规进程的时间片更新

唤醒与优先级重算

try_to_wake_up()

recalc_task_prio() 与 activated 字段

schedule 全流程

切换前的准备

挑选下一个进程

对刚唤醒进程的特殊处理

执行切换

切换之后

多核负载均衡

三种多处理器架构

调度域

rebalance_tick() / load_balance() / move_tasks()

调度系统调用

nice() 与 getpriority()/setpriority()

CPU 亲和性：sched_getaffinity()/sched_setaffinity()

实时进程相关

关系图谱

目录

反向链接