实时调度与负载均衡

• 任务粒度大小对窃取收益的影响
• 过小粒度窃取开销占比大
• 过大粒度负载不均

工作窃取中，任务切分粒度（granularity）至关重要。任务过小：每个任务只有很少计算量，窃取本身（从其它线程队列取走任务、同步、缓存未命中）的开销相对任务本身过大，导致"窃取开销 > 切分收益"，整体效率下降。任务过大：可分离的任务单元少，负载均衡能力差，某线程任务多、其它线程空闲，负载不均。设置窃取阈值：通常用"切分阈值"（如数组长度小于某阈值则不继续递归切分，直接串行计算），使叶子任务足够大（如 1000-10000 元素）以摊薄切分/窃取开销，同时保持足够任务数支撑负载均衡。队列策略：每个线程用本地双端队列（deque），本线程从队尾（LIFO）取任务（缓存友好），窃取线程从队头（FIFO）取任务（减少竞争），配合"窃取失败就扩大任务"或读阈值调整。这是 ForkJoinPool 与 Cilk 的核心。经验法则：任务粒度使"串行计算量 ≈ 窃取/切分开销的平方根量级"最优。

核心是"粒度权衡"：太细开销大、太粗负载不均。窃取阈值与"本地队尾 LIFO + 异地队头 FIFO"的队列策略配合，平衡缓存局部性与负载均衡。理解"粒度 = 开销与均衡的平衡点"是关键。

• child steal（窃取子任务）与 continuation steal（窃取延续）的区别
• work-first 与 help-first 的调度策略
• 对栈空间与调度开销的影响

在并行递归中，当某个线程产生子任务时，可以"窃取"两种东西：child steal（窃取子任务）——空闲线程取走子任务执行，父线程继续执行父延续；continuation steal（窃取延续）——空闲线程取走父任务剩余部分（延续），父线程等待子任务完成。Cilk 采用 work-first：父线程执行子任务（继续深度优先），窃取者取走延续（continuation），即被窃取的是 continuation。help-first（如 X10）：父线程挂起，子任务被窃取执行。work-first 的优势：正常执行路径（无窃取）时父线程深度优先执行子任务，栈空间紧凑（O(depth)），调度开销极低（无函数分派开销落入热路径）；help-first 的劣势是父线程挂起时要保存帧、栈空间大、调度开销高。因此 Cilk 的 work-first 主打的正是"低调度开销 + 栈空间小"，而 help-first 换来的是更好的负载均衡灵活性（帮助窃取者更快执行子任务）。

work-first 延续窃取 vs help-first 子窃取的核心差异是"谁继续执行"与"栈空间"。Cilk 选 work-first 是为降低热路径调度开销与栈空间，代价是窃取时需处理延续的封存。理解"延续窃取省栈省开销"是关键。

• DM 按截止期（而非周期）排序，RM 按周期排序
• 截止期<周期时按截止期排序更紧
• DM 的可调度条件（利用率上界）

速率单调（RM）按周期 T 从短到长分配静态优先级，隐含假设截止期=周期（D=T）。但当任务截止期 D 小于周期 T（D<T，如截止期紧于周期）时，按周期排序不能反映真正的紧迫性，可能使"截止期短但周期较长"的任务优先级偏低而错过截止期。截止期单调（DM）按截止期 D 从短到长分配优先级，直接反映"离截止期越近越优先"，在 D<T 时更合理。DM 是最优的固定优先级调度（在 D≤T 的约束下），可调度条件与 RM 类似：对 n 个任务，若 Σ(C_i/D_i) ≤ 某个界（取决于截止期相对周期），则一组任务可调度；DM 的充分条件常表述为 Σ(C_i/D_i) ≤ n(2^(1/n)-1)（当 D_i=T_i 时退化为 RM 的条件），或更精确地使用响应时间分析（RTA）判断。当 D=T 时 DM 与 RM 等价。

核心是"排序依据"：RM 按周期，DM 按截止期。当 D<T 时，截止期才反映真实紧迫性，故 DM 更优。可调度条件用"利用率（按 D 归一化）上界"或 RTA 表达。理解"D 与 T 的关系决定用 RM 还是 DM"是关键。

• 定时器链组织超时任务
• 位图就绪队列 O(1) 找最高优先级
• 与 CFS 红黑树（公平调度）的差异

周期任务的调度器实现常用"定时器链 + 位图就绪队列"降低开销。定时器链把到期的周期性任务按超时时间组织（如时间轮或有序链表），到期时将其加入就绪队列；位图就绪队列用位图（bitmap）表示"每个优先级是否有就绪任务"，用一条指令（如 ffs/clz）找到最高优先级的就绪任务，使"找最高优先级任务"为 O(1)，极大降低调度器开销。Linux CFS 则用红黑树按虚拟运行时间（vruntime）组织就绪任务，每次选 vruntime 最小的任务，实现按 CPU 份额的公平调度，复杂度 O(log n)；它不依赖优先级位图，而是维护"公平性"（每个任务获得与权重成比例的 CPU）。差异：位图就绪队列是"静态优先级 + O(1) 选最高优先级"，适合优先级明确的实时调度；CFS 红黑树是"动态公平 + O(log n) 选最公平任务"，适合通用分时调度。现代内核两者结合（高优先级实时任务用位图，普通任务用 CFS）。

核心是"按时钟/超时组织 + 位图快速选择" vs "按公平性红黑树选择"。位图省去遍历、O(1) 选优先级，适合实时；CFS 红黑树保证公平、O(log n)。理解"实时用优先级位图、通用用公平树"的定位差异是关键。

• 本地队尾 LIFO 取任务利用缓存局部性
• 窃取从队头 FIFO 减少竞争
• 局部性与窃取频率的权衡

工作窃取中，本地线程从自己队列的尾部（LIFO）取任务，因为新产生的任务往往是"最近才分裂出来的、数据最可能还在缓存中"的子任务，从尾部取能最大化缓存局部性（时间局部性：刚创建的任务刚被访问过）。同时本地取尾天然与"窃取者从队头取"分离，减少竞争。窃取从队头（FIFO）取最旧的任务，因为旧任务通常是"最大的、重计算的"单元，窃取它能摊薄窃取成本、提高负载均衡效率。权衡：若本地频繁取尾，窃取者取走的是大任务，负载均衡好但本地缓存局部性保持；若任务分裂频繁，窃取频率高，需平衡"窃取带来的均衡收益"与"窃取打断的缓存局部性"。实际中，本地 LIFO 保证热任务留在本地（缓存友好），窃取 FIFO 保证冷大任务被分享（均衡），两者结合实现"局部性与均衡"的平衡。

核心是"取尾保局部性、取头保均衡"。LIFO 让本地线程处理刚创建的任务（缓存热），FIFO 让窃取者处理最旧的大任务（均衡）。合理设置任务粒度与窃取策略，使窃取频率适中，是权衡的关键。

• 分布式队列 + 空闲窃取
• 窃取从队尾避免竞争
• 与全局队列（中心化）的差异

工作窃取中，每个线程有自己的任务队列，工作线程从自己队列取任务；当某线程队列空（空闲）时，它从其它线程的队列尾"窃取"任务执行，从而把多余负载转移到空闲线程，实现负载均衡，无需全局协调。窃取从队尾（而非队头）可减少与本地线程取队头（LIFO）的竞争，且窃取的是较旧的大任务。与全局队列（中心化）的差异：全局队列用一个共享队列，所有线程竞争取任务，实现简单但有中心化瓶颈（锁竞争、队列成为热点），且无法利用"任务在哪个线程产生"的局部性；工作窃取把队列分散到各线程，减少竞争、利用局部性、可扩展性好，但窃取有额外开销（跨线程取任务、缓存未命中）。工作窃取适合"任务动态生成、计算密集"的并行（如 ForkJoinPool、Cilk），全局队列适合"任务集合固定、简单均匀"的场景。

核心是"去中心化 + 空闲窃取"vs"中心化队列"。工作窃取以"窃取"实现负载均衡，避免全局队列的锁竞争与瓶颈，同时保留局部性；全局队列简单但中心化。两者取舍是"局部性/扩展性 vs 简单性"。

• 全局调度（任务可迁移）与分区调度（任务固定核）的取舍
• 分区调度把多核划分成单核问题
• 分区调度的可调度性分析

全局调度：任务可运行在任意核上（可迁移），由全局调度器统一分配，负载均衡好但迁移开销大、调度复杂性高、可调度性分析困难。分区调度：每个任务在系统初始化时固定分配到某个核，每个核独立运行单核调度器（如 RM/EDF），任务不迁移，调度简单、可调度性分析容易。分区调度的核心价值：把"多核调度"分解为"多个单核调度"，每个核沿用单核的可调度性分析（如 RM 的利用率上界 U≤n(2^(1/n)-1)、EDF 的 U≤1），从而将成熟的单核理论扩展到多核。取舍：分区调度迁移开销为零、分析简单，但负载均衡能力差（任务分配不均时某核过载、其它核空闲）；全局调度负载均衡好但复杂性高。实际常用分区调度（配合分配算法如首次适应、最差适应，或按利用率均衡分配），特定场景用全局调度。

核心是"任务固定 vs 任务可迁移"。分区调度把多核切割成若干单核问题，复用单核 RM/EDF 分析，简单可靠；全局调度负载均衡但分析难。工程上分区调度更常见，关键是把任务合理分配到各核并保证各核可调度。

• EDF 抢占式的最优性
• EDF 可调度充要条件 U≤1
• 与 RM 的 U≤n(2^(1/n)-1) 对比

EDF 在单核抢占式调度下是最优的：只要任务集总利用率 U≤1，EDF 就能保证所有任务在截止期内完成（充要条件，D=T 时）。EDF 总是执行"截止时间最早"的任务，动态调整优先级，能充分利用 CPU。RM 是静态优先级，其可调度充分条件是 U≤n(2^(1/n)-1)，当 n→∞ 时趋于 ln2≈0.693。因此 EDF 的利用率上界（1）高于 RM 的界（ln2），即 EDF 能调度更多任务集（利用率在 0.693~1 之间的任务集，RM 可能不可调度但 EDF 可调度）。对比本质：EDF 动态优先级更灵活、利用率更高，但分析复杂、实现需动态排序；RM 静态优先级简单、分析容易，但利用率上界低。注意 EDF 的最优性假设是抢占式、D=T、单核。

核心是"利用率上界"：EDF 充要 U≤1，RM 充分 U≤n(2^(1/n)-1)（≈ln2）。EDF 用动态优先级换取更高的可调度利用率，RM 用静态优先级换取简单。理解"EDF 更优但更复杂"是关键。

• 利用率 U=Σ(C_i/T_i) 的定义
• U≤1 是必要条件（CPU 不能超载）
• 非充分（调度器可能失败）

周期性任务集用 (C_i, T_i) 表示：C_i 是任务 i 的最坏执行时间，T_i 是周期（每 T_i 时间释放一次）。利用率 U=Σ(C_i/T_i) 表示任务集对 CPU 的总需求比例。U≤1 是必要条件：若 U>1，CPU 在稳态下无法满足所有任务的需求，必然有任务错过截止期，故任何可调度任务集必须满足 U≤1。但 U≤1 不是充分条件：即使 U≤1，由于调度策略的非最优或任务时序（如非抢占、优先级配置不当、任务同时到达的瞬时过载），某些任务仍可能错过截止期。例如 RM 静态优先级下，即使 U≤1 但 U>n(2^(1/n)-1)，任务集可能不可调度；非抢占调度下即使 U<1 也可能失败。因此 U≤1 只是"不超载"的必要前提，真正可否调度需用具体调度器的可调度性条件（如 RM 的利用率上界、EDF 的 U≤1 充要、或响应时间分析 RTA）判定。

核心是"必要 vs 充分"的区分。U≤1 是资源需求不超 CPU 的下限，但调度成功还取决于策略与时序。EDF 抢占式下 U≤1 恰是充要，而 RM 等静态调度还需要更紧的界。理解"利用率是必要条件，充分性取决于调度器"是关键。

• 一致性哈希的会话固定性
• 最小连接的自适应但可能断开会话
• 节点增删时的会话迁移与重放处理

长连接场景需要会话保持（同一用户的请求命中同一后端节点，以维持会话状态）。一致性哈希：把请求按 key 哈希到环上，同一 key 固定映射到同一节点，天然会话保持，且节点增删时只影响少量 key（哈希环上相邻区域），迁移小；但可能因哈希不均匀导致负载不均。最小连接：把请求发给当前连接数最少的节点，负载均衡好，但同一用户可能被分到不同节点，破坏会话保持（需后端共享会话或 Redis 存会话）。取舍：需要强会话保持用一致性哈希（或 sticky session），需要负载均衡用最小连接。节点增删时的会话迁移：一致性哈希用虚拟节点减少重映射，可把受影响 key 的会话迁移到新节点；对长连接，节点下线时需平滑迁移（先让新连接打住，等待存量连接完成或超时重连），并配合"会话重放/重放安全"——客户端重连到新节点后用幂等键保证重放不产生重复副作用（如重复扣款）。结合方案：会话可共享（存 Redis）时用最小连接，会话不可共享时用一致性哈希 + 故障转移重放。

核心是"会话保持 vs 负载均衡"的取舍。一致性哈希用固定映射换会话保持，最小连接用最优分配换均衡。节点增删时用虚拟节点减少迁移、用幂等重放处理重连是工程要点。

• RM 的充分条件 U≤n(2^(1/n)-1)
• EDF 的充要条件 U≤1
• 两者的保守性（充分 vs 充要）

RM 的利用率上界 U≤n(2^(1/n)-1) 是"充分非必要"条件：只要满足该界，任务集必然可调度；但任务集实际利用率可超过该界仍可调度（界偏保守）。该界来自 Liu & Layland 的最坏情况分析：当任务周期满足特定比例关系（周期递增且最小周期为 1 时，临界负载）时，RM 的可调度性边界恰好是 n(2^(1/n)-1)。EDF 的 U≤1 是"充要"条件（抢占式、D=T 时）：只要总利用率不超过 1，EDF 必然可调度；超过 1 则必然不可调度。保守性差异：RM 的界是充分但非必要（保守，可能漏判实际可调度的任务集），EDF 的界是充要（精确，无保守）。因此利用率在 (n(2^(1/n)-1), 1] 之间的任务集，RM 可能不可调度但 EDF 可调度，EDF 能利用更多 CPU 资源。n→∞ 时 n(2^(1/n)-1)→ln2≈0.693，RM 的界趋于 0.693，明显低于 EDF 的 1。

核心是"充分 vs 充要"与"静态 vs 动态优先级"。RM 静态优先级用保守界换取简单，EDF 动态优先级用充要界实现更高利用率。理解"RM 平均只能利用约 70% CPU，EDF 可到 100%"是关键。

• RM 在静态优先级下的最优性
• 利用率上界 n(2^(1/n)-1) 的极限
• ln2 的含义（CPU 利用率上限）

Liu & Layland 证明了在"静态优先级（固定优先级）抢占式调度"下，RM 是最优的：若存在任何静态优先级调度能调度某任务集，则 RM 也一定能调度它。原因：RM 按周期从短到长分配优先级，周期越短、释放越频繁的任务优先级越高，这是静态优先级下"能保证所有任务及时完成"的最优排序。利用率上界 U≤n(2^(1/n)-1) 是 RM 可调度的充分条件。当 n→∞ 时，n(2^(1/n)-1) 趋于 ln2≈0.693。含义：在任务数极多（n 很大）时，即使任务集利用率高达 0.693，RM 也能保证可调度；但若超过 0.693（平均），静态优先级（RM）可能无法保证所有任务及时完成，即使 CPU 还有 30% 空闲——这是静态优先级调度"最坏情况"下的利用率天花板。它说明 RM 虽简单最优，但利用率上界约 69%，动态优先级（如 EDF）可突破到 100%。

核心是"RM 的最优性范围"与"ln2 上界"。RM 在静态优先级内最优，但静态优先级整体有约 69% 的利用率天花板。ln2 是"平均意义上静态优先级调度能保证的 CPU 利用率上限"，解释了为何需要动态优先级（EDF）提升利用率。

• 硬实时与软实时任务的共存
• 轮询服务器与零星服务器的机制
• 用服务器预算隔离硬/软任务

硬实时系统要求所有硬任务必须满足截止期，若直接把软实时任务插进调度，可能挤占硬任务的执行时间、破坏保证。服务器（server）机制把软任务放到一个"服务器"任务中，该服务器有自己的执行预算（capacity）与周期（replenishment），以服务器的优先级参与调度。轮询服务器（polling server）：周期性地以一个固定优先级被调度，有预算就执行软任务，无预算就空转，预算用完则本周期不再执行软任务。零星服务器（sporadic server）：允许软任务在服务器"预算充足"时被"提前"执行（不局限于周期边界），一旦预算耗尽，须等预算补充周期才恢复，从而既能及时服务软任务，又不占用超过预算的硬任务时间。关键：服务器预算上限保证"软任务最多占用这么多 CPU 时间"，从而硬任务的可用带宽有保证，硬任务可调度性不受破坏。这是优先级继承/带宽隔离的典型应用。

核心是"用预算隔离硬/软任务"。服务器把软任务包装成受预算限制的实体，保证其占用不超过预算，从而不破坏硬任务保证。零星服务器比轮询更灵活（预算充足时可提前执行），但要精确跟踪预算补充。

• RM 上界适用条件（静态优先级、D=T）
• EDF 上界适用条件（抢占、D=T）
• 判定方法与 RTA 的补充

RM 的利用率上界 U≤n(2^(1/n)-1) 适用于单核、抢占式、静态优先级（RM）、截止期=周期（D=T）的周期性任务集；它是充分条件，含"最坏情况"的保守估计。EDF 的 U≤1 适用于单核、抢占式、动态优先级（EDF）、D=T 的条件，是充要条件。检查步骤：1) 计算每个任务利用率 C_i/T_i 并求和得 U；2) 若 U>1，必然不可调度（EDF 下直接判不可调度）；3) 若用 RM，检查 U≤n(2^(1/n)-1)，满足则可调度，不满足则需进一步用响应时间分析（RTA）精确判定（RM 的界是充分非必要，可能漏判真实可调度的任务集）；4) 若用 EDF，U≤1 即充要，直接判定。当 D<T（截止期短于周期）时，需用 DM 并相应调整分析，或直接用 RTA。RTA 比利用率测试更精确，适合界不满足时进一步确认。

核心是"各界适用条件"与"充分 vs 充要"。RM 界保守（充分），EDF 界精确（充要）。判定时先算 U，超 1 必不可调度；RM 界不满足时用 RTA 补充。理解"何时用哪个界、何时需要 RTA"是关键。

• 优先级反转的成因（持锁+中优先级抢占）
• 优先级继承提升持锁者优先级
• Mars Pathfinder 案例

优先级反转：高优先级任务 H 需要低优先级任务 L 持有的锁，H 阻塞等待 L；此时中优先级任务 M（优先级介于 L 和 H 之间）抢占 L，使 L 无法释放锁，H 被"间接"阻塞——而 M 优先级低，H 却等不到锁，形成"无界阻塞"（M 不停执行，H 一直等）。解决：优先级继承——当 L 持有 H 需要的锁时，把 L 的优先级临时提升到 H 的优先级，使 L 不被 M 抢占，及时执行完并释放锁，H 得以继续，从而消除无界阻塞。Mars Pathfinder 案例：1997 年火星探测器因优先级反转导致数据总线任务被阻塞而反复重启，通过启用优先级继承（用 priority inheritance 修复）解决。优先级继承的注意点：继承只在持锁期间临时提升，会带来"优先级可能被多个任务继承"的复杂性，需防死锁与链式继承。

核心是"持锁被抢占导致无界阻塞"。优先级继承通过临时提升持锁者优先级，使其不被中优先级抢占，及时释放锁，消除无界阻塞。分清"反转"（症状）与"继承"（解法）是关键。

• 利用率测试的充分性
• RTA 的迭代方程与精确性
• 何时需要 RTA

利用率测试 U≤n(2^(1/n)-1) 是"充分非必要"：满足则必可调度，但任务集实际可调度却不满足该界时，会漏判（false negative）。需要 RTA 的场景：当利用率测试不满足（U>n(2^(1/n)-1)）但 U≤1 时，任务集可能仍可调度，此时需用 RTA 精确判定。RTA 用迭代方程 R_i = C_i + Σ_{j∈hp(i)} ⌈R_i/T_j⌉·C_j 计算任务 i 的最坏响应时间 R_i：初始 R_i=C_i，迭代直到 R_i 收敛（或超过截止期 D_i）。若 R_i≤D_i 则任务可调度，否则不可调度。RTA 考虑了高优先级任务的干扰（⌈R_i/T_j⌉ 表示在 R_i 期间任务 j 释放的次数），比利用率测试更精确，是"充分且必要"的判定（在给定优先级分配下）。RTA 也适用于 D<T 或非 RM 的优先级分配，通用性更强。

核心是"充分 vs 必要"的精确性。利用率测试简单但保守（充分非必要），RTA 精确（充要）但需迭代计算。当利用率测试不满足时用 RTA 确认，避免误判不可调度。理解"何时升级到 RTA"是关键。

• RTA 迭代方程的含义
• 高优先级任务的干扰项
• 迭代求解与收敛判定

RTA 计算任务 i 的最坏响应时间 R_i，方程 R_i = C_i + Σ_{j∈hp(i)} ⌈R_i/T_j⌉·C_j 中：C_i 是任务 i 自身的执行时间；hp(i) 是优先级高于任务 i 的任务集合；⌈R_i/T_j⌉ 表示在 R_i 这段时间内，高优先级任务 j 释放的次数（ceil 向上取整）；因此 Σ⌈R_i/T_j⌉·C_j 是任务 i 在响应期间被高优先级任务抢占的总时间。迭代求解：令 R_i 初始为 C_i，代入方程右边计算新值，并与旧值比较，不断迭代直到收敛（R_i 不再变大）或超过截止期 D_i。若最终 R_i≤D_i，任务 i 可调度；否则不可调度。RTA 是"充分且必要"的精确判定，考虑了释放抖动与高优先级干扰，比利用率上界更准确，适用于 RM/DM 等固定优先级调度。

核心是"响应时间 = 自身执行 + 高优先级干扰"。⌈R_i/T_j⌉ 是请求次数计数，迭代收敛法因为 R_i 出现在方程两端，需反复代入直到稳定。RTA 比利用率测试精确，是固定优先级调度的标准可调度性分析工具。