轻量级 PI-futex

我们称其为轻量级有 3 个原因

  • 在用户空间快速路径中，启用 PI 的 futex 完全不涉及内核工作（或任何其他的 PI 复杂性）。无需注册，无需额外的内核调用 —— 只有用户空间纯粹的快速原子操作。

  • 即使在慢速路径中，系统调用和调度模式也与普通的 futex 非常相似。

  • 内核中的 PI 实现围绕着互斥锁（mutex）抽象进行了精简，并有严格的规则来保持实现的相对简单：只有一个所有者可以拥有锁（即不支持读写锁）、只有所有者可以解锁、不允许递归加锁等。

优先级继承 - 为什么？

简短的回答是：用户空间 PI 有助于实现/提升用户空间应用程序的确定性。在最佳情况下，它有助于实现确定性和良好的有界延迟。即使在最坏的情况下，PI 也能改善与锁相关的应用程序延迟的统计分布。

详细回答

首先，在多任务之间共享锁是一种常见的编程技术，通常无法用无锁算法替代。正如我们在内核中所看到的（内核本身就是一个相当复杂的程序），无锁结构与其说是常态，不如说是例外 —— 当前共享数据结构的无锁代码与有锁代码的比例大约在 1:10 到 1:100 之间。无锁编程很困难，无锁算法的复杂性往往会危及对所述代码进行健壮审查的能力。也就是说，关键的实时（RT）应用程序通常选择锁结构来保护关键数据结构，而不是使用无锁算法。此外，在某些情况下（如共享硬件或其他资源限制），无锁访问在数学上是不可能的。

媒体播放器（例如 Jack）是合理应用设计的例子，其中多个任务（具有多个优先级）共享短时间持有的锁：例如，一个高优先级的音频播放线程与中优先级的构造音频数据线程以及低优先级的显示色彩处理线程相结合。再加上视频和解码，我们就会有更多的优先级。

因此，一旦我们接受同步对象（锁）是不可避免的现实，一旦我们接受多任务用户空间应用程序对能够使用锁有着非常合理的期望，我们就必须考虑如何为用户空间提供确定性锁实现的选项。

大多数反对实现优先级继承的技术反面论点仅适用于内核空间锁。但用户空间锁则不同，在那里我们无法禁用中断或使任务在临界区中不可抢占，因此“使用自旋锁”的论点并不适用（用户空间自旋锁与其他用户空间锁结构具有相同的优先级反转问题）。事实是，目前几乎唯一能够为用户空间锁（例如基于 futex 的 pthread 互斥锁）带来良好确定性的技术就是优先级继承

目前（没有 PI 的情况下），如果高优先级和低优先级任务共享一个锁 [对于大多数非 trivial 的实时应用程序来说，这是一个相当常见的场景]，即使所有临界区都经过精心编写以确保确定性（即所有临界区持续时间都很短且只执行有限数量的指令），内核也无法保证高优先级任务的任何确定性执行：任何中优先级任务都可以在低优先级任务持有共享锁并执行临界区时抢占该低优先级任务，并将其无限期延迟。

实现

如前所述，启用 PI 的 pthread 互斥锁的用户空间快速路径根本不涉及内核工作 —— 它们的行为与基于普通 futex 的锁非常相似：值为 0 表示未锁，值 == TID 表示已锁定。（这与基于链表的健壮 futex 所使用的方法相同。）用户空间使用原子操作来加锁/解锁这些互斥锁，而无需进入内核。

为了处理慢速路径，我们添加了两个新的 futex 操作

  • FUTEX_LOCK_PI

  • FUTEX_UNLOCK_PI

如果获取锁的快速路径失败 [即从 0 到 TID 的原子转换失败]，则调用 FUTEX_LOCK_PI。内核完成所有其余工作：如果还没有 futex 队列附加到该 futex 地址，则代码会查找拥有该 futex 的任务 [它已将自己的 TID 放入 futex 值中]，并将一个“PI 状态”结构附加到 futex 队列。pi_state 包含一个 rt-mutex，这是一个支持 PI 的、基于内核的同步对象。“另一个”任务成为 rt-mutex 的所有者，并且在 futex 值中原子性地设置 FUTEX_WAITERS 位。然后，该任务尝试对 rt-mutex 加锁，并在其上阻塞。一旦返回，它就已经获取了互斥锁，并将 futex 值设置为它自己的 TID 并返回。用户空间没有其他工作要执行 —— 它现在拥有该锁，并且 futex 值包含 FUTEX_WAITERS|TID。

如果解锁侧的快速路径成功 [即用户空间成功完成 futex 值的 TID -> 0 原子转换]，则不会触发内核工作。

如果解锁快速路径失败（因为设置了 FUTEX_WAITERS 位），则调用 FUTEX_UNLOCK_PI，内核代表用户空间解锁该 futex —— 它还解锁所附加的 pi_state->rt_mutex，从而唤醒任何潜在的等待者。

请注意，在这种方法下，与以前的 PI-futex 方法相反，没有对 PI-futex 的事前“注册”。[由于 pthread 互斥锁现有的 ABI 属性，无论如何这都是不太可能的。]

此外，在此方案下，“健壮性”和“PI”是 futex 的两个正交属性，所有四种组合都是可能的：futex、robust-futex、PI-futex、robust+PI-futex。

有关优先级继承的更多详细信息，请参见 支持 PI 的 RT-mutex 子系统。