进程调度算法详解：从FCFS到多级反馈队列

一句话结论（30s）

调度算法的本质是在「公平」与「高效」之间找平衡。因为 FCFS 有护航效应、SJF 需要预知执行时间、静态优先级会饿死低优先级进程，各有致命缺陷，所以现代通用系统最终收敛到 MLFQ（多级反馈队列）——它靠「边运行边学习」动态调整优先级，用五条规则同时兼顾交互进程的响应时间和批处理进程的吞吐量，是 Windows、macOS、Linux 调度器的共同思想源头。

核心原理（2min）

• 评价维度：CPU 利用率、吞吐量、周转时间、等待时间、响应时间（交互式系统核心）
• FCFS：先来先服务，非抢占，长进程”护航”短进程 → 护航效应
• SJF/SRTF：短作业优先，平均等待时间最优，但难点是「如何知道作业执行时间」，靠指数平均预测
• HRRN：响应比 = 1 + 等待时间/执行时间，兼顾长短作业、无饥饿，但需 $O(n)$ 遍历
• RR：时间片轮转，专为分时系统设计，时间片大小需权衡（太大退化为 FCFS，太小切换开销高）
• 优先级调度：静态会饥饿（IBM 7094 低优先级等了 8 年），动态（O(1) 调度器 active/expired 双数组）防饥饿
• MLFQ 五规则：高优先级先调度、同级 RR、新进程进最高队列、用完时间片降级、定期提升防饥饿
• MLFQ 哲学：I/O 密集进程停留高层得响应，CPU 密集进程降到低层得大时间片

底层深入（5-10min）

调度算法的评价维度

在选择和评估调度算法时，通常从以下维度考量：

• CPU 利用率：CPU 保持忙碌的时间占比
• 吞吐量：单位时间内完成的进程数量
• 周转时间：从进程提交到完成的等待 + 执行总时间
• 等待时间：进程在就绪队列中等待被调度的时间
• 响应时间：从提交到第一次得到 CPU 响应的间隔（交互式系统核心指标）

不同场景对这些指标的侧重点不同：批处理系统追求吞吐量和 CPU 利用率，交互式系统追求响应时间，实时系统追求截止时间保证。

FCFS（First Come First Served，先来先服务）

原理

最简单的调度算法，按照进程到达就绪队列的顺序依次分配 CPU。非抢占式——一旦获得 CPU，进程会一直运行到阻塞或完成。

关键问题：护航效应（Convoy Effect）

考虑一组进程：P1（需要运行 100ms），P2（需要 1ms），P3（需要 1ms），都在时刻 0 到达。如果 P1 先到，P2 和 P3 需要等待 100ms 才能开始执行 1ms 的任务，平均等待时间 = (0 + 100 + 101) / 3 ≈ 67ms。如果 P2、P3 先运行，平均等待时间 = (2 + 0 + 1) / 3 = 1ms。

这就是护航效应——一个长进程”护航”了一队短进程，导致平均等待时间急剧恶化。

思考：为什么 FCFS 会产生护航效应？问题的根源到底是「先来先服务」还是「非抢占」？

推理：先来先服务本身没错，错在「非抢占」——长进程一旦获得 CPU 就一路跑完，后面排队的短进程只能干等。如果把 FCFS 改成「可以被抢占」，护航效应立刻消失，但那就已经不是 FCFS 而是时间片轮转了。所以护航效应的本质是「顺序 + 不可中断」两个条件叠加的结果，缺一不可。

优缺点

• 优点：实现极其简单，无额外开销
• 缺点：护航效应严重，对短作业不友好，不适合交互式系统
• 适用场景：批处理系统中对公平性要求不高的场景

SJF（Shortest Job First，短作业优先）

原理

每次调度时选择预估执行时间最短的进程。可以是非抢占式（SJF）或抢占式（SRTF，Shortest Remaining Time First）。

最优性证明

SJF 在平均等待时间上理论上是最优的。证明思路：假设存在一个最优调度序列，其中长进程排在短进程之前，交换两者顺序必然减少（或不增加）平均等待时间，因此最优序列必然是短作业优先。

思考：既然 SJF 在平均等待时间上最优，为什么现代通用系统几乎不用它？

推理：因为最优性有一个隐藏前提——「已经知道每个作业的执行时间」。现实里交互式进程的执行时间根本无法预知，指数平均只是猜测。一旦预估错了，长作业被误判成短作业频繁抢占、短作业被误判成长作业长期饥饿，所谓「最优」就崩塌了。这提醒我们：一个算法的理论最优，只在它的前提成立时才成立。

核心难点

如何知道作业的执行时间？ 这是 SJF 的根本问题。对于批处理作业，用户可以提供预估时间但不靠谱；对于交互式进程完全无法预估。实践中通常使用指数平均法基于历史 CPU 爆发时间（CPU Burst）来预测：

$$\tau_{n+1} = \alpha \cdot t_n + (1-\alpha) \cdot \tau_n$$

其中 $t_n$ 是第 $n$ 次实际的 CPU 爆发时间，$\tau_n$ 是第 $n$ 次的预测值，$\alpha$（通常 0.5）控制近期数据的权重。

HRRN（Highest Response Ratio Next，高响应比优先）

原理

HRRN 是对 FCFS 和 SJF 的折中方案。每次调度时计算每个进程的响应比：

$$响应比 = \frac{等待时间 + 执行时间}{执行时间} = 1 + \frac{等待时间}{执行时间}$$

• 短作业天然响应比高（分母小）
• 长作业等待越久响应比越高，不会饿死
• 响应比 = 1 表示进程刚到达

HRRN 是非抢占式的，在进程完成或阻塞时才触发调度。它既照顾了短作业的优先权，又保证了长作业不会饿死（等待时间足够长后必然被调度）。

优缺点

• 优点：兼顾长短作业，不会产生饥饿
• 缺点：每次调度需要遍历所有就绪进程计算响应比，$O(n)$ 复杂度
• 适用场景：批处理系统

时间片轮转（Round Robin, RR）

原理

给每个进程分配一个固定长度的时间片（通常 10ms-100ms），进程按 FIFO 顺序轮流执行。时间片到期后，时钟中断触发调度，当前进程被放到就绪队列末尾，切换到下一个进程。

时间片大小的权衡

• 太大（比如 1 秒）：退化为 FCFS，响应时间长
• 太小（比如 1ms）：上下文切换开销占比过高。假设每次切换开销为 0.1ms，时间片 1ms 时切换开销占比 10%，CPU 有效利用率只有 90%
• 经验值：时间片应远大于上下文切换开销，同时保证 80% 的 CPU 爆发能在单片内完成

思考：时间片为什么不能太大、也不能太小？有没有一个「刚刚好」的值？

推理：太大退化成 FCFS（响应慢），太小切换开销占比过高（吞吐低），两者不可兼得。经验法则是让 80% 的 CPU 爆发能在单片内完成——本质上是在「切换开销」和「响应时间」之间取一个平衡点。这也说明：调度算法没有绝对最优，只有「针对目标负载」的最优。

特点

RR 是专为分时系统设计的调度算法，核心指标是响应时间而非周转时间。它对所有进程一视同仁，是公平性最好的算法之一。

最高优先级调度

静态优先级

进程创建时分配固定优先级，运行期间不变。简单但可能造成低优先级进程饥饿——1983 年的 IBM 7094 就出现过低优先级作业运行了 8 年仍未被调度的情况。

动态优先级

优先级随运行历史动态调整。经典案例是 Linux 的 CFS（完全公平调度器）的前身 O(1) 调度器，它使用两个数组（active 与 expired）管理动态优先级：

• 进程在 active 数组中按优先级调度
• 用完后进入 expired 数组
• active 数组为空时交换两个数组
• 有效防止饥饿：每个进程在掉入 expired 之前都有机会执行

这种设计保证了 $O(1)$ 的调度时间复杂度，这也是其名称的由来。

思考：O(1) 调度器已经做到 $O(1)$ 复杂度、还能防饥饿，Linux 为什么在 2.6.23 又把它换成 CFS？

推理：因为 O(1) 的「动态优先级」靠启发式规则（交互进程加分、CPU 密集进程减分）来猜测进程是交互型还是批处理型，猜错时行为很糟；而 CFS 换了一个更本质的度量——虚拟运行时间 vruntime，谁的 vruntime 小谁先跑，公平性由数学保证而非启发式猜测。这是「规则驱动」向「模型驱动」的一次范式升级。

多级反馈队列（Multilevel Feedback Queue, MLFQ）

核心设计

MLFQ 是目前最经典的通用调度算法，被 Windows、macOS、现代 Linux（CFS）以不同形式采纳。其结构如下：

优先级高（时间片小，8ms）
  队列 0  ←──── 所有新进程从这里进入
     │ 用完时间片 → 降级
  队列 1  （时间片 16ms）
     │ 用完时间片 → 降级
  队列 2  （时间片 32ms）
     │ 用完时间片 → 降级
  队列 N  （时间片最大，FCFS）
优先级低

五条基本规则

规则 1：高优先级队列优先调度（严格的优先级抢占）

规则 2：同级队列内 Round Robin 调度

规则 3：新进程进入最高优先级队列

规则 4：用完一个时间片后降级到下一级队列（长作业惩罚）

规则 5：定期将所有进程提升回最高优先级（防止饥饿 + CPU 爆发型进程的适应性）

设计哲学

MLFQ 的精妙之处在于”边运行边学习”：它不需要预先知道进程的执行时间，通过观察进程的 CPU 使用行为来动态调整优先级。

• 交互式进程（I/O 密集型）：大多数时间在等待 I/O，偶尔需要短时间 CPU，在 MLFQ 中这类进程用完时间片前就主动释放 CPU，始终停留在高优先级队列，获得良好的响应时间
• 批处理进程（CPU 密集型）：持续消耗 CPU，很快被降到低优先级队列，获得更大的时间片以减少切换开销

规则 4 与规则 5 的博弈

如果没有规则 5（优先级提升），一个偶尔需要 CPU 的交互式进程可能因为某次长时间计算被降级到底层，之后即使恢复为 I/O 密集型也无法回升。规则 5 通过周期性将所有进程提升回最高优先级队列来解决这个问题，本质上是对进程行为变化的再适应。

思考：CFS 为什么用 vruntime 而不是时间片？它和 MLFQ 的「多级队列」是什么关系？

推理：MLFQ 用「队列层级 + 时间片大小」来近似「谁占 CPU 更少」，是一个离散的、靠规则维护的近似；CFS 直接用 vruntime 连续刻画「每个进程应得的 CPU 份额」，用一棵红黑树按 vruntime 排序、永远挑最小者运行，天然实现了「最短 CPU 使用时间优先」。二者殊途同归，但 CFS 把「边运行边学习」换成了「边运行边记账」，下面看真实源码。

Linux 内核源码：CFS 的 vruntime 与红黑树就绪队列

说明：以下源码摘自本仓库 brain/library/linux/kernel/sched/。该内核（6.6+）已把经典 CFS 的「按 vruntime 排序红黑树」演进为 EEVDF（Earliest Eligible Virtual Deadline First，最早合格虚拟截止期优先），但 vruntime 仍是核心记账量、红黑树仍是就绪队列数据结构，只是排序键从 vruntime 换成了虚拟截止期 deadline。为便于阅读只摘关键片段，代码逐字保留原文。

1. vruntime 的计算：calc_delta_fair

CFS 的核心是把「真实运行时间」按权重换算成「虚拟运行时间」，权重（nice 值）越高、vruntime 涨得越慢。换算函数 calc_delta_fair（fair.c）：

/*
 * delta /= w
 */
static inline u64 calc_delta_fair(u64 delta, struct sched_entity *se)
{
	if (unlikely(se->load.weight != NICE_0_LOAD))
		delta = __calc_delta(delta, NICE_0_LOAD, &se->load);

	return delta;
}

它把一段真实执行时间 delta 按实体权重 se->load.weight 折算。在 32 位路径上，__calc_delta 的实现就是一次「除以权重」（fair.c）：

static u64 __calc_delta(u64 delta_exec, unsigned long weight, struct load_weight *lw)
{
	return (delta_exec * weight) / lw->weight;
}

分析：weight 越大（进程越”重要”、nice 越低），delta_exec * weight / lw->weight 中放大的倍数越大，但最终折算回 NICE_0_LOAD 基准时，等价于高权重进程每运行 1ms 实际累积的 vruntime 更少。于是「谁 vruntime 小谁优先」就自然实现了「高权重多分 CPU」。64 位路径不用除法、改用定点乘法求逆（__update_inv_weight），本质是同一件事——避免热路径上的整数除法。

每次时钟 tick，CFS 更新当前进程的 vruntime（fair.c 的 update_curr，关键行）：

	delta_exec = update_se(rq, curr);
	if (unlikely(delta_exec <= 0))
		return;

	curr->vruntime += calc_delta_fair(delta_exec, curr);
	resched = update_deadline(cfs_rq, curr);

分析：curr->vruntime += calc_delta_fair(delta_exec, curr) 是整条 CFS 公平性的「记账语句」——每运行一段 delta_exec，就把它按权重折算后累加到 vruntime 上。运行得越多 vruntime 越大，越可能被换下去，这就是「完全公平」的数学来源：最终所有进程的 vruntime 趋同。

2. 红黑树就绪队列：__enqueue_entity

CFS 的每个 CPU 就绪队列 cfs_rq 里，就绪实体不是挂在链表上，而是挂在一棵红黑树上（sched.h）：

struct cfs_rq {
	struct load_weight	load;
	unsigned int		nr_queued;
	...
	struct rb_root_cached	tasks_timeline;
	...
	struct sched_entity	*curr;
	struct sched_entity	*next;
	...
};

入队/出队即红黑树的插入/删除（fair.c）：

static void __enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
	sum_w_vruntime_add(cfs_rq, se);
	se->min_vruntime = se->vruntime;
	se->min_slice = se->slice;
	rb_add_augmented_cached(&se->run_node, &cfs_rq->tasks_timeline,
				__entity_less, &min_vruntime_cb);
}

static void __dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
	rb_erase_augmented_cached(&se->run_node, &cfs_rq->tasks_timeline,
				  &min_vruntime_cb);
	sum_w_vruntime_sub(cfs_rq, se);
}

分析：tasks_timeline 的类型是 rb_root_cached，即「带最左缓存的红黑树根」——因为调度永远取”最小”的那个实体，缓存最左节点可以让 __pick_first_entity 以 $O(1)$ 拿到候选、整体查找仍是 $O(\log n)$。每个 sched_entity 内嵌一个 rb_node run_node 作为树节点，进程就绪/睡眠就是在这棵树上插入/删除。

排序键由 __entity_less 决定（fair.c）：

static inline bool entity_before(const struct sched_entity *a,
				 const struct sched_entity *b)
{
	/*
	 * Tiebreak on vruntime seems unnecessary since it can
	 * hardly happen.
	 */
	return vruntime_cmp(a->deadline, "<", b->deadline);
}

分析：注意——经典 CFS 按 vruntime 排序，而这个内核已经升级为 EEVDF，改按虚拟截止期 deadline 排序（deadline = vruntime + slice/weight）。所以「红黑树按 vruntime 排序」这句八股在这个内核里已经不再准确；但 vruntime 仍然是计算 deadline 的底座，理解 vruntime 依然是理解 CFS 的钥匙。

3. 调度入口：schedule() 与 __schedule()

所有调度算法最终都由同一个入口 schedule() 触发（core.c）：

asmlinkage __visible void __sched schedule(void)
{
	struct task_struct *tsk = current;

#ifdef CONFIG_RT_MUTEXES
	lockdep_assert(!tsk->sched_rt_mutex);
#endif

	if (!task_is_running(tsk))
		sched_submit_work(tsk);
	__schedule_loop(SM_NONE);
	sched_update_worker(tsk);
}

真正的调度逻辑在 __schedule() 里（core.c，关键路径摘录）：

static void __sched notrace __schedule(int sched_mode)
{
	struct task_struct *prev, *next;
	...
	cpu = smp_processor_id();
	rq = cpu_rq(cpu);
	prev = rq->curr;
	...
	rq_lock(rq, &rf);
	smp_mb__after_spinlock();
	...
pick_again:
	assert_balance_callbacks_empty(rq);
	next = pick_next_task(rq, &rf);
	rq->next_class = next->sched_class;
	...
	if (likely(is_switch)) {
		rq->nr_switches++;
		...
		++*switch_count;
		...
		trace_sched_switch(preempt, prev, next, prev_state);

		/* Also unlocks the rq: */
		rq = context_switch(rq, prev, next, &rf);
	}
	...
}

分析：schedule() 先拿到当前任务 current，处理掉 IO 等收尾工作，然后进入 __schedule_loop 反复调用 __schedule 直到没有新的抢占需求。__schedule 的核心三步是：锁住本 CPU 的 runqueue → pick_next_task 按调度类优先级挑出下一个任务 → context_switch 切换地址空间和寄存器。这也回答了「调度算法在哪儿生效」——MLFQ、CFS 这些算法，最终都体现为 pick_next_task 里「挑谁」的那一步。

总结对比

多级反馈队列是经过数十年实践检验的最优秀的通用调度框架。Linux 的 CFS 虽然用红黑树替代了显式队列层级，但其核心思想——根据 CPU 使用时间动态调整调度权重——与 MLFQ 的”边运行边学习”如出一辙。理解了 MLFQ，就能理解几乎任何现代操作系统的调度器设计思路。

章末提问

1. 为什么 FCFS 会产生护航效应，而 RR 不会？

回答思路：核心区别在「抢占」。FCFS 非抢占，长进程独占 CPU 直到完成/阻塞，短进程只能排队；RR 有固定时间片 + 时钟中断抢占，任何进程最多占一个时间片就被轮换，天然打散”护航”。最后点一句：护航效应的本质是「顺序 + 不可中断」两个条件叠加，缺一不可。

2. SJF 平均等待时间最优，为什么通用系统不用它？

回答思路：先承认「给定执行时间已知」前提下 SJF 最优；然后指出现实瓶颈是「执行时间不可预知」，只能靠指数平均猜测，猜错就崩；最后收尾——SJF 只适合批处理且能拿到预估时间的场景，交互式系统用不了。

3. MLFQ 的规则 4（降级）和规则 5（提升）是不是矛盾？为什么要同时存在？

回答思路：不矛盾，二者是「惩罚」与「再适应」的配合。规则 4 把 CPU 密集进程压到底层、给大时间片省切换；规则 5 定期把所有人抬回高层，防止「曾经是 CPU 密集、后来变成 I/O 密集」的进程被永久锁死在底层饿死。本质是让调度器「边运行边学习」，对进程行为的动态变化再适应。

4. CFS 的红黑树现在是按 vruntime 排序的吗？

回答思路：经典 CFS 是按 vruntime 排序；Linux 6.6+ 已改成 EEVDF，按「虚拟截止期 deadline = vruntime + slice/weight」排序，红黑树结构不变、只是排序键变了。能说出这一点会加分——说明你跟进了内核演进，而不是只背八股。接着补一句 vruntime 仍是 deadline 的底座。

5. 一个进程运行的时间片用完，从「被换下」到「重新被挑中」，内核里发生了什么？

回答思路：按 __schedule 三步走——时钟 tick 更新 vruntime 并触发 resched_curr，schedule() 进入 __schedule，pick_next_task 从红黑树挑出 vruntime/deadline 最小者，context_switch 切换上下文。强调「就绪队列是红黑树、挑选是 $O(\log n)$、切换是存/恢复寄存器与页表」即可。