反馈与份额

Adaptive Scheduling

SJF/SRTF 的问题是需要知道未来 job length 或 CPU burst length。现实系统不知道未来，只能利用过去行为做估计。一个常见形式是指数平滑：

1

tau_(n+1) = alpha * t_n + (1 - alpha) * tau_n

其中 t_n 是刚观察到的 burst，tau_n 是旧估计。直觉是程序行为通常有一定稳定性：过去经常 I/O block 的任务，将来也可能继续短 burst；过去持续计算的任务，将来也更像 CPU-bound。如果程序行为完全随机，反馈调度就没有信息可用。

现代调度器不可能知道未来，只能把历史行为转换成优先级、时间片或 CPU 份额。Adaptive scheduling 依赖程序行为在短时间内具有一定延续性。

Lottery Scheduling

Lottery scheduling 给每个任务一些 tickets。每个时间片抽一张中奖票，持有该票的任务运行。长期平均看，任务获得的 CPU 份额约等于：

1

job_tickets / total_tickets

票数可以表达策略。短任务或重要任务给更多票，长任务给少一些票，就能概率性近似 SRTF 或 priority。每个 job 至少保留一张票，可以避免 strict priority 那种绝对饿死；但这不保证短任务一定快完成，负载过高时所有任务都会变慢。

相比固定优先级，Lottery 的一个优点是负载变化更平滑。新增或删除任务会按比例影响所有任务，而不是突然跨过某个优先级边界。它适合表达 proportional share，但不适合需要严格 deadline 保证的场景。

MLFQ

Multi-Level Feedback Queue 使用多个优先级队列，每个队列可以有自己的时间片和内部策略。任务通常从最高优先级开始；如果用完整个时间片，说明更像 CPU-bound，就降低优先级；如果经常提前阻塞、睡眠或等待 I/O，说明更像交互任务，就留在高优先级或被提升。

这让 MLFQ 不用提前知道 job 长度，也能近似 SRTF：短 CPU burst 的任务靠近高优先级，长期占用 CPU 的任务逐步下沉。队列内部常用 RR，低优先队列可以给更长时间片；队列之间可以 strict priority，也可以按比例分配 CPU。

MLFQ 的风险是 gaming。程序可以故意在时间片快用完前 yield、sleep 或做无意义 I/O，让调度器误以为它是交互任务。常见反制包括统计累计 CPU 使用而不只看单次是否用完整片、周期性 priority boost、防止任务永远停在高优先级。

“短 burst = 交互任务”只是经验规则。同一应用可能先睡很久再大量计算，也可能是必须周期运行的后台任务。调度器只能在交互、吞吐和可预测性之间不断校准。

多核与实时

多核调度

多核调度在策略层和单核类似，工程层却多了不少成本。Cache affinity 是其中一个核心词：线程最好回到上次运行的 CPU，复用 warm cache，减少跨核迁移和 cache coherence 成本。Per-core run queue 能降低全局队列锁竞争，但会带来负载均衡问题；某个 core 空闲时，可能需要从其他 core 偷任务。

锁的等待策略在多核上也要重看。自旋锁在短等待时可能比睡眠好，尤其在 barrier 附近只差最后几个线程；等待较长时仍应睡眠。基础 test_and_set 每次尝试都是写，会让同一个 cache line 在多个 core 之间 ping-pong。test_and_test_and_set 先普通读，看到可能空闲时再执行原子写，可以减少无意义写争用。

并行程序还需要协同调度。Gang scheduling 尽量让相关线程一起运行，避免某个线程 spin-wait 等待一个已经被 OS 挂起的伙伴。Scheduler activations 则让 OS 告知应用当前可用核心数，应用据此调整并行度。这里调度的不只是“线程还是进程”，还包括空间共享、缓存局部性和同步等待的总成本。

Real-Time

实时系统的目标是性能可预测，尤其是最坏情况响应时间。Hard real-time 用在安全关键系统中，deadline 必须满足，通常需要 admission control：只有系统能提前判断任务可完成，才允许任务进入。Soft real-time 常见于多媒体场景，目标是高概率满足 deadline。

典型算法包括 EDF、RMS 和 DM。EDF, Earliest Deadline First, 每次选择 absolute deadline 最近的 active task。周期任务的一种可行性测试是：

1

sum(C_i / D_i) <= 1

其中 C_i 是任务每次释放需要的 CPU 计算时间，D_i 是相对 deadline。所有周期任务要求的 CPU 利用率总和不能超过 100%。这个公式只适用于任务独立、可抢占并满足相应 period/deadline 条件的模型。

实时调度和普通吞吐调度的差别在目标函数。普通系统可以先运行再观察平均表现；实时系统需要在运行前证明或高度确信 deadline 能满足。

前向进展

Forward progress 关心系统是否真的在推进。Starvation、deadlock 和 priority inversion 很容易混在一起，但它们不同：

Strict priority、LCFS、SRTF/MLFQ 下短任务不断到来，都可能造成 starvation。Deadlock 的关键是资源循环等待。Priority inversion 的经典场景是低优先级 L 持锁，高优先级 H 等锁，中优先级 M 不需要锁却不断抢占 L，导致 H 间接停住。

Priority donation 或 inheritance 让持锁的低优先级线程临时继承高优先级，尽快释放锁。代价是实现复杂，调度行为也更难预测。调度策略必须与锁策略配合，否则系统仍在运行，关键任务却可能没有进展。

Linux 调度器

O(1) Scheduler

Linux O(1) scheduler 的名字来自选择下一个任务的时间与 runnable task 数量无关。它维护 140 个优先级队列，并用 bitmap 快速找到当前最高优先级的非空队列。优先级数字越小越高：0-99 是实时/内核范围，100-139 是普通用户任务范围。

它有 active 和 expired 两组队列。Active 中任务用完时间片后进入 expired；active 空了，两组交换。这避免同一轮里某些任务无限重复运行。同一优先级内部通常 RR，不同优先级有不同 timeslice，nice 值会映射到普通任务的优先级和时间片。

O(1) scheduler 也使用大量 heuristic：sleep_avg、interactive credit、I/O-bound 奖励、starvation 保护。睡得久、经常等待 I/O 的任务更像交互任务，会得到优先级奖励；跑得久的 CPU-bound 任务则可能被压低。它很工程化，也因此规则多、调参多。

CFS

Completely Fair Scheduler 试图少猜“谁是交互任务”，转而直接记录每个 runnable task 已经用了多少 CPU。核心变量是 vruntime，可以理解成按权重归一化后的已用 CPU 时间。实际运行越多，vruntime 越大；权重越高，同样实际运行时间增加的 vruntime 越慢。

CFS 选择红黑树中 vruntime 最小的 runnable task，也就是当前“相对最没被服务”的任务；插入和删除是 O(log n)。睡眠线程睡着时不增加 vruntime，醒来后相对落后，因此自然获得一定交互性 boost；实现上也会防止落后太多导致过度补偿。相比 O(1) scheduler，CFS 的味道更像把公平目标直接落到数据结构和权重公式上。

两个约束让 CFS 不只是纯公平公式。Target latency 希望在一段固定时间内每个 runnable task 至少运行一次；minimum granularity 防止任务太多时每个时间片小到上下文切换开销爆炸。等权时可以近似理解为：

1

Q_i = Target Latency / N

带权重时：

1

Q_i = (w_i / sum(w_p)) * Target Latency

nice 在 CFS 中主要映射为权重：nice 越低，权重越大，获得的 CPU 份额越高。它不是简单的固定优先级，而是 proportional share。

调度评估

评估调度算法可以用确定性建模、排队模型或真实实现。确定性建模给定 workload，手算各策略指标；排队模型用数学分布分析随机 workload；真实实现则在实际系统和实际数据上测量。

资源不紧张时，各种调度策略的差别可能不明显；利用率接近饱和后，响应时间会在 knee 附近急剧变坏。因此系统要在饱和前预留余量，并权衡公平、延迟、吞吐和可预测性。