饥饿与公平性

形式陈述 ​

饥饿是个体级进展失败：参与者 $p$ 的请求保持未完成，系统却继续执行并完成其他请求。更精确地说，需要先规定 $p$ 何时有资格推进。若请求从某时刻起持续 pending，$p$ 按模型要求持续获得执行机会，且完成所需条件持续成立或反复成立，但该请求仍永不完成，则 $p$ 在这次执行中饥饿。

公平性是筛选可容许执行公理库可容许执行Admissible execution满足给定调度、公平性和故障模型约束的执行。或约束服务策略的假设。对动作 $a$，两种常见形式是：

• 弱公平（justice）：若从某时刻起 $a$ 持续处于 enabled 状态，则 $a$ 最终发生；
• 强公平（compassion）：若 $a$ 在无限多个时刻处于 enabled 状态，即使中间反复失效，也最终发生。

强公平处理“机会不断出现又消失”的动作，因此严格排除了更多调度；弱公平只保护持续可执行的动作。两者都不自带时间上界。“最终”允许等待任意长但有限的时间，所以公平不等于低延迟，也不等于实时调度。

还必须区分调度器公平与同步对象公平。前者决定可运行线程是否取得处理器步骤；后者决定多个已到达锁或队列的请求以何种顺序被选择。公平调度可以让每个线程不断运行，却无法阻止 TAS 锁每次都被同一竞争者先取得；FIFO 锁可以按入队顺序服务，却无法帮助一个从不被操作系统调度到入队代码的线程。

有界等待是算法提供的更强性质：请求提出后，在它完成前，其他参与者最多可越过它 $B$ 次，或它至多执行 $B$ 个自身/系统步骤，其中界 $B$ 的参数必须写清。它不仅排除无限饥饿，还给出结构上界；但步数界仍不是 wall-clock 截止期，实际时间受处理器速度和调度停顿影响。

直觉 ​

“系统一直有车通过收费站”只说明整体有吞吐，不说明最左车道的一辆车会被放行。饥饿关注的正是这辆车。公平性则说明交通管理员愿意承诺什么：持续举牌的车最终被看见，还是连反复被遮住、但不断重新出现的车也最终被服务。

公平假设越强，活性定理越容易成立，但定理覆盖的执行越少。把公平性藏在“线程当然会运行”这种直觉里，会让证明在不同调度器和负载下失去含义；应把 enabled 条件、参与者正确性和服务策略明确放进量化范围。

例子与边界 ​

简单 TAS 自旋锁公理库自旋锁Spinlock · Spin lock获取失败时以原子操作持续轮询、等待锁在短时间内释放的互斥锁实现族。释放后，所有等待线程重新争抢同一原子位。线程 A 可能因缓存位置或调度时机总是先成功，线程 B 虽持续运行并反复尝试，却无限失败；系统不断完成临界区，B 仍饥饿。ticket lock 让每个到达者取得递增票号，serving 依次推进。在持锁者最终释放、票号规则正确且各等待线程获得执行的前提下，先取票者不会被后来者无限插队。

公平调度不自动修复算法内部资格撤销。设线程每次看到冲突就清除自己的请求标志，调度器轮流给每个线程同样多的步骤，它们仍可能在真正 enabled 前互相迫使对方退回。反过来，一个 FIFO mutex 也无法对抗永久不调度某线程的环境；对象保证只覆盖已经进入其等待协议的请求。

优先级反转是另一条边界。低优先级线程持锁，高优先级线程等待，中优先级任务持续抢占持锁者；即使锁等待队列严格 FIFO，高优先级线程仍可能很久无法前进。优先级继承可缓解这类调度交互，却不是 FIFO 公平的同义词，也不解决任意资源依赖中的所有饥饿。

推论与应用 ​

审阅活性声明时，应同时问三个问题：谁需要完成、什么条件使它有资格推进、执行集合采用何种公平约束。lock-free公理库无锁进展Lock-free progress · Lock-freedom系统整体保证在有限步内有某个操作完成，而不保证指定线程。只保证系统不断有人完成，允许指定线程饥饿；wait-free公理库Wait-free 进展Wait-free progress · Wait-freedom · 无等待进展每个正确参与者的每次操作都在有限个自身步骤内完成的个体级非阻塞保证。按参与者自身步骤给出完成保证，因而不需要依靠其他线程被公平调度来推动该操作，但仍需调用者本身持续取步骤。

工程指标中的尾延迟与形式公平相关却不等价。FIFO、轮转和配额可以改善可预测性，优先级策略则可能有意偏离平等服务。选择策略时应先声明业务需要的是无饥饿、有界越过、按权重分配还是截止期；用一个含糊的“公平锁”无法覆盖这些不同合同。

参考资料

• Leslie Lamport, “Proving the Correctness of Multiprocess Programs,” IEEE Transactions on Software Engineering SE-3(2), 1977, pp. 125–143。
• Nancy A. Lynch, Distributed Algorithms, Morgan Kaufmann, 1996，公平执行与活性相关章节。
• Maurice Herlihy and Nir Shavit, The Art of Multiprocessor Programming, rev. 1st ed., Morgan Kaufmann, 2012，Chs. 2–3, 7。