https://www.kernel.org/doc/html/v6.6/locking/rt-mutex-design.html

RT-mutex 实现设计

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

本文档试图描述 rtmutex.c 实现的设计。它并不描述 rtmutex.c 存在的原因。有关此内容，请参阅带 PI 支持的 RT-mutex 子系统。尽管本文档确实解释了没有此代码会发生的问题，但这是为了理解代码实际在做什么。

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

无界优先级反转

优先级反转是指当一个较低优先级的进程在一个较高优先级的进程想要运行时执行时发生的情况。这出现的原因有很多，大多数情况下是无法避免的。每当一个高优先级的进程想要使用一个较低优先级的进程拥有的资源（例如互斥锁），高优先级的进程必须等到低优先级的进程完成对资源的使用。这就是优先级反转。我们想要防止的是所谓的无界优先级反转。这是指高优先级的进程由于较低优先级的进程而被阻止运行，时间长短不确定。

无界优先级反转的经典例子是有三个进程，我们称它们为进程 A、B 和 C，其中 A 是最高优先级进程，C 是最低优先级进程，B 介于两者之间。A 尝试获取由 C 拥有的锁，并且必须等待并让 C 运行以释放锁。但与此同时，B 执行，由于 B 的优先级高于 C，它抢占了 C，但实际上，它也抢占了 A，而 A 是一个更高优先级的进程。现在我们无法知道 A 将等待多长时间才能运行，因为我们不知道 B 是否会一直占用 CPU，从而永远不会让 C 有机会释放锁。这就是所谓的无界优先级反转。

下面是一个简单的 ASCII 图来展示这个问题：

   获取锁 L1（由 C 拥有）
     |
A ---+
        C 被 B 抢占
          |
C    +----+

B         +-------->
                B 现在阻止 A 运行。

优先级继承（PI）

解决这个问题有几种方法，但本文档只讨论 PI。

PI 是指一个进程在当前进程拥有的锁上阻塞时，会继承另一个进程的优先级。为了更容易理解，让我们使用之前的例子，再次考虑进程 A、B 和 C。

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

术语

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

PI 链
- PI 链是一系列有序的锁和进程，导致进程从被阻塞在其锁上的前一个进程那里继承优先级。本文档稍后会对此进行更详细的描述。
互斥锁
- 在本文档中，为了区分实现 PI 的锁和在 PI 代码中使用的自旋锁，从现在开始 PI 锁将被称为互斥锁。
锁
- 从现在开始，在本文档中，当提到用于保护 PI 算法部分的自旋锁时，我将使用术语锁。这些锁在启用 CONFIG_PREEMPT 时禁用抢占，在 SMP 上防止多个 CPU 同时进入临界区。
自旋锁
- 与上面的锁相同。
等待者
- 等待者是存储在被阻塞进程的堆栈上的结构。由于等待者的范围在被阻塞在互斥锁上的进程的代码内，因此可以在进程的堆栈（局部变量）上分配等待者，这是可以接受的。此结构保存了指向任务的指针，以及任务被阻塞在的互斥锁。它还具有 rbtree 节点结构，用于将任务放入互斥锁的等待者 rbtree 以及互斥锁所有者任务的 pi_waiters rbtree（稍后描述）。
- 有时会用等待者来指代正在等待互斥锁的任务。这与等待者->任务相同。
等待者们
- 一组被阻塞在互斥锁上的进程。
最高等待者
- 在特定互斥锁上等待的最高优先级进程。
最高 PI 等待者
- 在特定进程拥有的互斥锁中等待的最高优先级进程。

PI 链

PI 链是可能导致优先级继承发生的进程和互斥锁的列表。多个链可能会汇聚，但链永远不会分叉，因为一个进程一次只能被阻塞在一个互斥锁上。

示例：

进程：A、B、C、D、E
互斥锁：L1、L2、L3、L4

A 拥有：L1
        B 被阻塞在 L1 上
        B 拥有 L2
               C 被阻塞在 L2 上
               C 拥有 L3
                      D 被阻塞在 L3 上
                      D 拥有 L4
                             E 被阻塞在 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-+
                |     |
              G-+     +->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 rbtree。这是拥有的互斥锁的所有顶部等待者的树。请注意，此树仅保存顶部等待者，而不是所有被阻塞在进程拥有的互斥锁上的等待者。

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

此树存储在进程的任务结构中，称为 pi_waiters 的 rbtree。它也由任务结构中的自旋锁 pi_lock 保护。在锁定 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，使得 D 首先运行，A 最后运行。当 D 在 func4 中的“再次做一些事情”区域被抢占时，我们有一个遵循以下锁定的情况：

D 拥有 L3
       C 被阻塞在 L3 上
       C 拥有 L2
              B 被阻塞在 L2 上
              B 拥有 L1
                     A 被阻塞在 L1 上

因此，我们有链 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”字段，数字越小，优先级越高。优先级为5的任务比优先级为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（de）boosting的任务（进程正在阻塞的互斥锁的所有者）、检查死锁的标志、任务拥有的互斥锁、指向被阻塞在互斥锁上的进程的等待者结构的指针（尽管对于deboosting，此参数可能为NULL）、任务被阻塞的互斥锁的指针以及作为互斥锁的顶级等待者的top_task。

在本说明中，我将不提及死锁检测。本说明将尽量保持在高层次上。

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

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

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

获取互斥锁（遍历）

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

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

如果锁上存在争用，我们就会走慢路径（rt_mutex_slowlock）。

慢路径函数是在堆栈上创建任务的等待者结构。这是因为等待者结构仅在此函数的范围内需要。等待者结构保存了存储任务在互斥锁的等待者树上的节点，如果需要，还保存了所有者的pi_waiters树。

由于慢锁的解锁路径也会获取等待锁，因此我们会获取互斥锁的等待锁。

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

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

锁没有所有者
当前任务是所有等待者中优先级最高的任务

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

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

任务在互斥锁上阻塞

对于进程和互斥锁的计数是通过进程的等待者结构来完成的。将“任务”字段设置为进程，“锁”字段设置为互斥锁。等待者的rbtree节点被初始化为进程的当前优先级。

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

如果所有者也被阻塞在锁上，并且其pi_waiters已更改（或者死锁检查已开启），则我们释放互斥锁的等待锁，并继续运行rt_mutex_adjust_prio_chain对所有者进行调整，如前所述。

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

在循环中唤醒

任务可能因为以下几个原因而被唤醒：

先前的锁所有者释放了锁，而任务现在是顶级等待者
我们收到了信号或超时

在这两种情况下，任务将再次尝试获取锁。如果成功，那么它将从等待者树中移除自己，并将自己设置回TASK_RUNNING状态。

在第一种情况下，如果在此任务获取锁之前另一个任务已经获取了锁，那么它将再次进入睡眠状态，并等待再次被唤醒。

第二种情况仅适用于在获取锁之前就可以被唤醒的任务，这可能是由于信号或超时（例如rt_mutex_timed_futex_lock()）。被唤醒时，它将再次尝试获取锁，如果成功，则任务将带着锁返回，否则如果任务被信号唤醒，则将返回-EINTR，如果超时则返回-ETIMEDOUT。

解锁互斥锁

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

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

慢解锁路径的第一步是获取互斥锁的等待锁。这会同步互斥锁的锁定和解锁。

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

如果有等待者，则需要唤醒其中一个。

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

最后，释放待定所有者的pi_lock并唤醒它。