3. 单机调度基础：WSPT、EDD 与 Lmax
好，咱们今天聊点实在的。单机调度，听起来好像很简单——就一台机器，任务排排队呗。但你别小看它，我做了这么多年系统优化，发现很多复杂问题的根子，其实都能回溯到单机调度上。今天咱们就啃下这块硬骨头。
我会重点讲三个经典算法：加权最短处理时间优先（WSPT）、最早截止时间优先（EDD），以及最小化最大延迟（Lmax）。说白了，它们分别解决的是「怎么干最划算」、「怎么干不超时」和「超时了怎么让损失最小」这三个问题。
核心观点：单机调度不是简单的「先来后到」，而是要在时间、权重、截止时间之间找到平衡点。这三个算法就是你的三把刀。
3.1 加权最短处理时间优先（WSPT）
先讲 WSPT。这个算法的思路很直接：把权重高的、处理时间短的任务往前排。你想想看，如果有个任务权重很高，但处理时间也很长，你把它放前面，后面一堆小任务全得等着，整体收益反而不高。
WSPT 的排序规则很简单：按 w_i / p_i 的比值从大到小排。其中 w_i 是权重，p_i 是处理时间。
我个人习惯用这个公式来快速判断：比值越大，优先级越高。举个例子：
| 任务 | 处理时间 p_i | 权重 w_i | w_i / p_i | 优先级 |
|---|---|---|---|---|
| A | 3 | 5 | 1.67 | 高 |
| B | 2 | 2 | 1.00 | 中 |
| C | 5 | 3 | 0.60 | 低 |
按 WSPT 排序，顺序应该是 A → B → C。为什么？因为 A 的比值最高，虽然它比 B 多花 1 个单位时间，但权重高出一倍多，值得优先处理。
我的经验：我在做实时任务调度时，经常用 WSPT 来排优先级。但要注意，WSPT 只适用于最小化加权完成时间之和的场景。如果你要最小化最大延迟，它就不灵了。
3.2 最早截止时间优先（EDD）
EDD 就更好理解了——谁先到期，谁先干。这个算法在实时系统中用得特别多。你想想，如果有个任务还有 1 分钟就截止了，另一个还有 1 小时，你肯定先处理前者，对吧？
EDD 的排序规则：按截止时间 d_i 从小到大排。截止时间越早，优先级越高。
我曾经在一个项目中遇到过这种情况：有个任务明明截止时间很紧，但处理时间特别长。按 EDD 排它确实在前面，结果它一跑就是半天，后面一堆小任务全超时了。嗯，这里要注意——EDD 只保证最小化最大延迟，但不保证所有任务都不超时。
避坑指南：我曾经天真地以为 EDD 能解决所有截止时间问题。结果有一次，一个长任务占了机器，后面一堆短任务全炸了。后来我学乖了——如果任务处理时间差异很大，最好结合 WSPT 的思路，或者用后面要讲的 Lmax 来评估。
3.3 最小化最大延迟（Lmax）
Lmax 是个更高级的概念。它不关心单个任务是否超时，而是关心所有任务中，最大的那个延迟是多少。说白了，就是「最惨的那个任务，到底有多惨」。
计算 Lmax 的公式很简单：
L_i = C_i - d_i
Lmax = max(L_i, 0)其中 C_i 是任务的实际完成时间，d_i 是截止时间。如果 L_i 是负数，说明任务提前完成了，延迟为 0。
EDD 算法有一个非常重要的性质：对于单机调度，EDD 能最小化最大延迟 Lmax。这是经过严格数学证明的，不是我瞎说的。
但这里有个坑：EDD 最小化的是 Lmax，而不是「超时任务的数量」。如果你有 10 个任务，EDD 可能让 9 个任务都超时 1 分钟，但第 10 个任务准时完成。而另一种调度可能让 1 个任务超时 10 分钟，其他 9 个都准时。这两种情况，EDD 会选择前者，因为它的 Lmax 更小（1 分钟 vs 10 分钟）。
关键点：选择哪个算法，取决于你的优化目标。如果目标是「别让任何一个任务超时太久」，用 EDD。如果目标是「让加权完成时间之和最小」，用 WSPT。如果两者都要兼顾，那就需要更复杂的混合策略了。
3.4 知识体系总览
为了让你更直观地理解这三个算法的关系，我画了一张图。这张图展示了单机调度的核心逻辑：
从这张图你可以看到，三个算法各有侧重。WSPT 关注「效率」，EDD 关注「时效」，Lmax 关注「底线」。实际项目中，我经常需要根据业务需求，在它们之间做权衡。
3.5 实战对比
咱们用一个具体的例子来对比这三个算法。假设有 4 个任务：
| 任务 | p_i | w_i | d_i |
|---|---|---|---|
| J1 | 2 | 3 | 5 |
| J2 | 4 | 1 | 8 |
| J3 | 1 | 5 | 3 |
| J4 | 3 | 2 | 6 |
咱们分别用三种算法排一下：
- WSPT 排序：按 w_i/p_i 从大到小 → J3(5.0) → J1(1.5) → J4(0.67) → J2(0.25)
- EDD 排序：按 d_i 从小到大 → J3(3) → J1(5) → J4(6) → J2(8)
- Lmax 计算：用 EDD 排序后，计算每个任务的延迟，取最大值
你发现没有？WSPT 和 EDD 的排序结果居然一样！都是 J3 → J1 → J4 → J2。但这不是必然的，只是这个例子恰好如此。换个数据，结果可能完全不同。
我的建议：在实际项目中，不要死板地只用一种算法。我通常的做法是：先用 EDD 排一遍，看看 Lmax 能不能接受。如果不能，再考虑用 WSPT 或者混合策略。说白了，算法是工具，不是教条。
3.6 避坑总结
最后，我把自己踩过的坑总结一下，你记好了：
- WSPT 不是万能的——它只优化加权完成时间，不保证截止时间。如果你有硬截止时间，别用它。
- EDD 不保证所有任务都不超时——它只保证最大延迟最小。如果所有任务都超时了，EDD 也没办法。
- Lmax 是评估指标，不是调度算法——虽然 EDD 能最小化 Lmax，但 Lmax 本身是用来衡量调度质量的。
- 别忘了任务之间的依赖关系——这三个算法都假设任务独立。如果任务之间有先后顺序，那就需要更复杂的拓扑排序了。
好了，单机调度的基础就讲到这里。这三个算法虽然简单，但它们是理解更复杂调度问题的基石。你把它吃透了，后面学多机调度、分布式调度就会轻松很多。