RT互斥锁实现设计¶

根据 GNU 自由文档许可证 1.2 版获得许可

本文档试图描述 rtmutex.c 实现的设计。它没有描述 rtmutex.c 存在的原因。请参阅支持 PI 的 RT 互斥锁子系统。虽然本文档确实解释了没有此代码时发生的问题，但这旨在帮助理解代码实际在做什么。

本文档的目标是帮助其他人理解所使用的优先级继承 (PI) 算法，以及做出以这种方式实现 PI 的决策的原因。

无界优先级反转¶

优先级反转是指当较高优先级的进程想要运行时，较低优先级的进程正在执行。发生这种情况有几个原因，而且大多数时候是无法避免的。任何时候，高优先级进程想要使用低优先级进程拥有的资源（例如互斥锁），高优先级进程必须等到低优先级进程完成资源的使用。这就是优先级反转。我们想要防止的是所谓的无界优先级反转。也就是说，高优先级进程在不确定的时间内被低优先级进程阻止运行。

无界优先级反转的经典例子是你有三个进程，我们称它们为进程 A、B 和 C，其中 A 是最高优先级的进程，C 是最低优先级的进程，B 介于两者之间。 A 尝试获取 C 拥有的锁，必须等待并让 C 运行以释放锁。但与此同时，B 执行，并且由于 B 的优先级高于 C，它会抢占 C，但这样做，它实际上是在抢占优先级更高的 A 进程。现在没有办法知道 A 将休眠多长时间等待 C 释放锁，因为就我们所知，B 是一个 CPU 消耗大户，永远不会给 C 释放锁的机会。这被称为无界优先级反转。

这里用一点 ASCII 艺术来展示这个问题

   grab lock L1 (owned by C)
     |
A ---+
        C preempted by B
          |
C    +----+

B         +-------->
                B now keeps A from running.

优先级继承 (PI)¶

有几种方法可以解决这个问题，但其他方法不在本文档的讨论范围之内。这里我们只讨论 PI。

PI 是指如果另一个进程阻塞在当前进程拥有的锁上，则该进程继承另一个进程的优先级。为了更容易理解，让我们再次使用前面的示例，使用进程 A、B 和 C。

这次，当 A 阻塞在 C 拥有的锁上时，C 将继承 A 的优先级。因此，现在如果 B 变为可运行，它不会抢占 C，因为 C 现在具有 A 的高优先级。一旦 C 释放锁，它就会失去其继承的优先级，然后 A 就可以继续使用 C 拥有的资源。

术语¶

在这里，我解释本文档中使用的一些术语，以帮助描述用于实现 PI 的设计。

PI链

PI 链是一系列有序的锁和进程，这些锁和进程导致进程从之前阻塞在其中一个锁上的进程继承优先级。本文档稍后将对此进行更详细的描述。

互斥锁

在本文档中，为了区分实现 PI 的锁和在 PI 代码中使用的自旋锁，从现在开始，PI 锁将被称为互斥锁。

锁

在本文档中，从现在开始，在引用用于保护 PI 算法各部分的自旋锁时，我将使用术语“锁”。这些锁禁用 UP 的抢占（当启用 CONFIG_PREEMPT 时），并在 SMP 上阻止多个 CPU 同时进入关键部分。

自旋锁

与上面的锁相同。

等待者

等待者是一个结构体，存储在阻塞进程的堆栈上。由于等待者的作用域在进程阻塞在互斥锁上的代码内，因此可以在进程的堆栈（局部变量）上分配等待者。此结构体保存指向任务的指针，以及任务阻塞的互斥锁。它还具有 rbtree 节点结构，用于将任务放置在互斥锁的等待者 rbtree 中，以及互斥锁所有者任务的 pi_waiters rbtree 中（如下所述）。

等待者有时用于指代正在等待互斥锁的任务。这与 waiter->task 相同。

等待者列表

阻塞在互斥锁上的进程列表。

顶部等待者

等待特定互斥锁的最高优先级进程。

顶部 PI 等待者

等待特定进程拥有的互斥锁之一的最高优先级进程。

注意

任务和进程在本文档中可以互换使用，主要是为了区分正在一起描述的两个进程。

PI链¶

PI 链是一个进程和互斥锁的列表，它们可能导致优先级继承的发生。多个链可能会收敛，但链永远不会发散，因为一个进程不能同时阻塞在多个互斥锁上。

例子

Process:  A, B, C, D, E
Mutexes:  L1, L2, L3, L4

A owns: L1
        B blocked on L1
        B owns L2
               C blocked on L2
               C owns L3
                      D blocked on L3
                      D owns L4
                             E blocked on L4

链将是

E->L4->D->L3->C->L2->B->L1->A

为了显示两个链在哪里合并，我们可以添加另一个进程 F 和另一个互斥锁 L5，其中 B 拥有 L5，F 阻塞在互斥锁 L5 上。

F 的链将是

F->L5->B->L1->A

由于一个进程可能拥有多个互斥锁，但永远不会阻塞在多个互斥锁上，因此链会合并。

这里我们展示了两个链

E->L4->D->L3->C->L2-+
                    |
                    +->B->L1->A
                    |
              F->L5-+

为了使 PI 工作，这些链右端的进程（或者我们也可以称之为链的顶部）必须等于或高于链左侧或下方的进程的优先级。

此外，由于一个互斥锁可能被多个进程阻塞，因此我们可以在互斥锁处合并多个链。如果我们添加另一个阻塞在互斥锁 L2 上的进程 G

G->L2->B->L1->A

再次，为了展示这种增长方式，我将再次展示合并的链

E->L4->D->L3->C-+
                +->L2-+
                |     |
              G-+     +->B->L1->A
                      |
                F->L5-+

如果进程 G 具有链中的最高优先级，那么链中的所有任务（在本例中为 A 和 B）都必须将其优先级提高到 G 的优先级。

互斥锁等待者树¶

每个互斥锁都会跟踪所有阻塞自身的等待者。互斥锁有一个 rbtree，用于按优先级存储这些等待者。此树受位于互斥锁结构体中的自旋锁保护。此锁称为 wait_lock。

任务 PI 树¶

为了跟踪 PI 链，每个进程都有自己的 PI rbtree。这是进程拥有的互斥锁的所有顶部等待者的树。请注意，此树仅保存顶部等待者，而不保存阻塞在进程拥有的互斥锁上的所有等待者。

任务 PI 树的顶部始终是等待任务拥有的互斥锁的最高优先级任务。因此，如果任务继承了优先级，它将始终是此树顶部任务的优先级。

此树作为 rbtree（称为 pi_waiters）存储在进程的任务结构中。它受任务结构中的自旋锁（也称为 pi_lock）保护。此锁也可以在中断上下文中获取，因此在锁定 pi_lock 时，必须禁用中断。

PI链的深度¶

PI 链的最大深度不是动态的，实际上可以定义。但要弄清楚它非常复杂，因为它取决于所有互斥锁的嵌套。让我们看一个例子，我们有 3 个互斥锁 L1、L2 和 L3，以及四个独立的函数 func1、func2、func3 和 func4。以下显示了 L1->L2->L3 的锁定顺序，但实际上可能不是以这种方式直接嵌套的

void func1(void)
{
      mutex_lock(L1);

      /* do anything */

      mutex_unlock(L1);
}

void func2(void)
{
      mutex_lock(L1);
      mutex_lock(L2);

      /* do something */

      mutex_unlock(L2);
      mutex_unlock(L1);
}

void func3(void)
{
      mutex_lock(L2);
      mutex_lock(L3);

      /* do something else */

      mutex_unlock(L3);
      mutex_unlock(L2);
}

void func4(void)
{
      mutex_lock(L3);

      /* do something again */

      mutex_unlock(L3);
}

现在我们添加 4 个进程，它们分别运行每个函数。进程 A、B、C 和 D 分别运行函数 func1、func2、func3 和 func4，并且 D 首先运行，A 最后运行。当 D 在 func4 中的“再次执行某些操作”区域被抢占时，我们有一个遵循的锁定

D owns L3
       C blocked on L3
       C owns L2
              B blocked on L2
              B owns L1
                     A blocked on L1

And thus we have the chain A->L1->B->L2->C->L3->D.

这给了我们一个 4 的 PI 深度（四个进程），但单独查看任何一个函数，似乎它们最多只有两个锁定深度。因此，虽然锁定深度是在编译时定义的，但仍然很难找到该深度的可能性。

现在，由于互斥锁可以由用户空间应用程序定义，我们不希望出现 DOS 类型的应用程序，它嵌套大量的互斥锁以创建大型 PI 链，并且代码在查看大量数据时保持自旋锁。因此，为了防止这种情况，该实现不仅实现了最大锁定深度，而且在遍历 PI 链时，每次最多只保持两个不同的锁。更多关于这方面的内容如下。

互斥锁所有者和标志¶

互斥锁结构包含指向互斥锁所有者的指针。如果互斥锁未被拥有，则此所有者设置为 NULL。由于所有架构的任务结构至少具有两个字节的对齐方式（如果不是这样，rtmutex.c 代码将被破坏！），这允许将最低有效位用作标志。位 0 用作“有等待者”标志。当互斥锁上有等待者时，它将被设置。

有关更多详细信息，请参阅支持 PI 的 RT 互斥锁子系统。

cmpxchg 技巧¶

某些架构实现原子 cmpxchg（比较和交换）。这用于（在适用的情况下）保持获取和释放互斥锁的快速路径较短。

cmpxchg 基本上是以原子方式执行的以下函数

unsigned long _cmpxchg(unsigned long *A, unsigned long *B, unsigned long *C)
{
      unsigned long T = *A;
      if (*A == *B) {
              *A = *C;
      }
      return T;
}
#define cmpxchg(a,b,c) _cmpxchg(&a,&b,&c)

这真的很好，因为它允许你仅在变量是你期望的变量时才更新变量。如果返回值（A 的旧值）等于 B，你就知道它成功了。

宏 rt_mutex_cmpxchg 用于尝试锁定和解锁互斥锁。如果架构不支持 CMPXCHG，那么这个宏只是设置为每次都失败。但如果支持 CMPXCHG，那么这将极大地帮助保持快速路径较短。

使用 rt_mutex_cmpxchg 以及所有者字段中的标志有助于优化支持它的架构的系统。这也将在本文档的后面进行解释。

优先级调整¶

rtmutex.c 中 PI 代码的实现有几个地方需要进程调整其优先级。借助进程的 pi_waiters，很容易知道需要调整什么。

实现任务调整的函数是 rt_mutex_adjust_prio 和 rt_mutex_setprio。 rt_mutex_setprio 仅在 rt_mutex_adjust_prio 中使用。

rt_mutex_adjust_prio 检查任务的优先级，以及等待任务拥有的任何互斥锁的最高优先级进程。由于任务的 pi_waiters 按任务拥有的所有互斥锁的所有顶部等待者的优先级排序，因此我们只需将顶部 pi 等待者与其自身的正常/截止时间优先级进行比较，并取较高的一个。然后调用 rt_mutex_setprio 以将任务的优先级调整为新优先级。请注意，rt_mutex_setprio 在 kernel/sched/core.c 中定义，用于实现优先级的实际更改。

注意: 对于 task_struct 中的“prio”字段，数字越低，优先级越高。“prio”为 5 的优先级高于“prio”为 10 的优先级。

有趣的是，rt_mutex_adjust_prio 可以增加或减少任务的优先级。如果较高优先级的进程刚刚阻塞在任务拥有的互斥锁上，rt_mutex_adjust_prio 将增加/提升任务的优先级。但如果由于某种原因，较高优先级的任务离开互斥锁（超时或信号），则相同的函数将降低/取消提升任务的优先级。这是因为 pi_waiters 始终包含等待任务拥有的互斥锁的最高优先级任务，因此我们只需要将顶部 pi 等待者的优先级与给定任务的正常优先级进行比较即可。

PI链遍历的高级概述¶

PI 链遍历由函数 rt_mutex_adjust_prio_chain 实现。

该实现经历了多次迭代，并最终达到了我们认为是最好的。它通过每次最多获取两个锁来遍历 PI 链，并且非常有效。

rt_mutex_adjust_prio_chain 可用于提升或降低进程优先级。

调用 rt_mutex_adjust_prio_chain 时，需要提供以下参数：要检查 PI（取消）提升的任务（进程阻塞的互斥锁的所有者）、用于检查死锁的标志、任务拥有的互斥锁、指向等待者的指针，该指针是进程阻塞在互斥锁上的等待者结构体（尽管此参数可能为 NULL 以进行取消提升）、指向任务阻塞的互斥锁的指针，以及作为互斥锁的顶部等待者的 top_task。

对于此解释，我不会提及死锁检测。此解释将尝试保持在较高层次。

当调用此函数时，没有持有任何锁。这也意味着所有者和锁的状态在进入此函数时可能会发生变化。

在此函数被调用之前，已经对任务执行了 rt_mutex_adjust_prio。这意味着任务已设置为其应具有的优先级，但任务等待者的 rbtree 节点尚未更新为新的优先级，并且该任务可能不在该任务阻塞的 pi_waiters 和等待者树中的正确位置。此函数解决了所有这些问题。

此函数的主要操作由 Thomas Gleixner 在 rtmutex.c 中总结。请参阅“链遍历基础和保护范围”注释以获取更多详细信息。

获取互斥锁 (遍历过程)¶

好的，现在让我们详细了解一下获取互斥锁时发生的情况。

首先尝试的是快速获取互斥锁。这是在启用 CMPXCHG 时完成的（否则快速获取将自动失败）。只有当互斥锁的所有者字段为 NULL 时，才能使用 CMPXCHG 获取锁，并且不需要执行任何其他操作。

如果锁上存在争用，我们将进入慢速路径 (rt_mutex_slowlock)。

慢速路径函数是在堆栈上创建任务的等待者结构体的地方。这是因为仅在此函数的作用域内才需要等待者结构体。等待者结构体保存用于将任务存储在互斥锁的等待者树上的节点，并且如果需要，还保存所有者的 pi_waiters 树。

获取互斥锁的 wait_lock，因为解锁互斥锁的慢速路径也会获取此锁。

然后我们调用 try_to_take_rt_mutex。这是未实现 CMPXCHG 的架构将始终获取锁的地方（如果没有争用）。

每次任务尝试在慢速路径中获取互斥锁时，都会使用 try_to_take_rt_mutex。这里首先要做的是原子设置互斥锁所有者字段的“有等待者”标志。通过立即设置此标志，当前争用互斥锁的所有者无法在不进入慢速解锁路径的情况下释放互斥锁，然后它需要获取 wait_lock，而此代码当前持有该锁。因此，设置“有等待者”标志会强制当前所有者与此代码同步。

如果以下条件为真，则获取锁

锁没有所有者

当前任务是相对于锁的所有其他等待者的最高优先级

如果任务成功获取锁，则该任务设置为锁的所有者，并且如果锁仍然有等待者，则将 top_waiter（等待锁的最高优先级任务）添加到该任务的 pi_waiters 树。

如果 try_to_take_rt_mutex() 未获取锁，则调用 task_blocks_on_rt_mutex() 函数。这会将任务添加到锁的等待者树，并传播锁的 pi 链以及锁所有者的 pi_waiters 树。这将在下一节中描述。

任务阻塞在互斥锁上¶

互斥锁和进程的记帐是通过进程的等待者结构体完成的。“task”字段设置为进程，“lock”字段设置为互斥锁。等待者的 rbtree 节点初始化为进程的当前优先级。

由于在慢速锁的入口处获取了 wait_lock，因此我们可以安全地将等待者添加到任务等待者树。如果当前进程是当前等待此互斥锁的最高优先级进程，则我们从所有者的 pi_waiters 中删除先前的顶部等待者进程（如果存在），并将当前进程添加到该树。由于所有者的 pi_waiter 发生了更改，我们调用所有者的 rt_mutex_adjust_prio 以查看所有者是否应相应地调整其优先级。

如果所有者也阻塞在锁上，并且其 pi_waiters 已更改（或者正在进行死锁检查），我们解锁互斥锁的 wait_lock 并继续在所有者上运行 rt_mutex_adjust_prio_chain，如前所述。

现在所有锁都已释放，并且如果当前进程仍然阻塞在互斥锁上（等待者“task”字段不为 NULL），则我们进入休眠状态（调用 schedule）。

循环唤醒¶

然后任务可以因以下几个原因而唤醒

先前的锁所有者释放了锁，并且该任务现在是 top_waiter
我们收到了信号或超时

在这两种情况下，任务都将再次尝试获取锁。如果确实如此，它将从等待者树中删除自身，并将其自身设置回 TASK_RUNNING 状态。

在第一种情况下，如果在该任务可以获取锁之前，该锁被另一个任务获取，那么它将返回休眠状态并等待再次唤醒。

第二种情况仅适用于正在获取互斥锁的任务，该互斥锁可以在获取锁之前唤醒，无论是由于信号还是超时（即 rt_mutex_timed_futex_lock()）。唤醒后，它将再次尝试获取锁，如果成功，则任务将在持有锁的情况下返回，否则，如果任务被信号唤醒，它将返回 -EINTR，如果超时，则返回 -ETIMEDOUT。

释放互斥锁¶

对于具有 CMPXCHG 的那些架构，解锁互斥锁也有一个快速路径。由于争用时获取互斥锁始终设置互斥锁所有者的“有等待者”标志，因此我们使用它来了解在解锁互斥锁时是否需要进入慢速路径。如果互斥锁没有任何等待者，则互斥锁的所有者字段将等于当前进程，并且可以通过仅将所有者字段替换为 NULL 来解锁互斥锁。

如果所有者字段设置了“有等待者”位（或者 CMPXCHG 不可用），则采用慢速解锁路径。

在慢速解锁路径中完成的第一件事是获取互斥锁的 wait_lock。这同步了互斥锁的锁定和解锁。

进行检查以查看互斥锁是否具有等待者。在没有 CMPXCHG 的架构上，这是互斥锁所有者将确定是否需要唤醒等待者的位置。在具有 CMPXCHG 的架构上，该检查是在快速路径中完成的，但它仍然需要在慢速路径中完成。如果互斥锁的等待者由于信号或超时而在所有者未能通过快速路径 CMPXCHG 检查和获取 wait_lock 之间的时间唤醒，则互斥锁可能没有任何等待者，因此所有者仍然需要进行此检查。如果没有等待者，则互斥锁所有者字段设置为 NULL，释放 wait_lock，并且不需要执行任何其他操作。

如果有等待者，那么我们需要唤醒一个。

在唤醒代码上，获取当前所有者的 pi_lock。找到锁的顶部等待者并从互斥锁的等待者树以及当前所有者的 pi_waiters 树中删除它。“有等待者”位被标记为防止较低优先级的任务窃取锁。

最后，我们解锁挂起所有者的 pi_lock 并唤醒它。

联系方式¶

有关此文档的更新，请发送电子邮件至 Steven Rostedt <rostedt@goodmis.org>

致谢¶

作者：Steven Rostedt <rostedt@goodmis.org>

更新者：Alex Shi <alex.shi@linaro.org> - 2017 年 7 月 6 日

原始审阅者: Ingo Molnar、Thomas Gleixner、Thomas Duetsch 和 Randy Dunlap

更新（2017 年 7 月 6 日）审阅者：Steven Rostedt 和 Sebastian Siewior

更新¶

本文档最初是为 2.6.17-rc3-mm1 编写的，已于 4.12 更新

Linux 内核

目录

本页