翻译：kernel-5.10\Documentation\locking\rt-mutex-design.rst
==============================
RT-mutex实现设计
==============================
版权所有 (c) 2006 Steven Rostedt
根据 GNU 自由文档许可证 1.2 版获得许可
本文档试图描述 rtmutex.c 实现的设计。 它没有描述 rtmutex.c 存在的原因。 为此，请参阅 Documentation/locking/rt-mutex.rst。 尽管本文档确实解释了没有此代码时发生的问题，
但这是在概念上理解代码实际在做什么。
本文档的目标是帮助其他人了解所使用的优先级继承 (PI) 算法，以及决定以已完成的方式实施 PI 的原因。
Unbounded Priority Inversion
----------------------------
优先级反转是指低优先级进程执行而高优先级进程想要运行(等待)。 发生这种情况的原因有很多，而且大多数时候是无可奈何的。 任何时候高优先级进程想要使用低优先级进程拥有的资源
（例如互斥体），高优先级进程必须等到低优先级进程用完该资源。 这是优先级倒置。 我们要防止的是一种叫做无限优先级倒置的东西。 也就是说，当高优先级进程被低优先级进程阻止运
行一段不确定的时间时。
无限优先级倒置的经典示例是你有三个进程，我们称它们为进程 A、B 和 C，其中 A 是最高优先级进程，C 是最低优先级，B 介于两者之间。 A 试图获取 C 拥有的锁并且必须等待并让 C
运行以释放锁。 但同时，B在执行，由于B的优先级高于C，所以它抢占了C，但这样做实际上是抢占了A，而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.
Priority Inheritance (PI)
-------------------------
有多种方法可以解决此问题，但其他方法超出了本文档的范围。 这里只讨论PI。
PI 是一个进程继承另一个进程的优先级的地方，如果另一个进程阻塞在当前进程拥有的锁上。 为了使这一点更容易理解，让我们再次使用前面的示例，其中包含进程 A、B 和 C。
这一次，当 A 阻塞在 C 拥有的锁上时，C 将继承 A 的优先级。所以现在如果 B 变得可运行，它不会抢占 C，因为 C 现在拥有 A 的高优先级。一旦 C 释放 锁，它失去了继承的优先级，
然后 A 可以继续使用 C 拥有的资源。
Terminology
-----------
在这里，我解释了本文档中使用的一些术语，以帮助描述用于实现 PI 的设计。
PI chain
- PI 链是一系列有序的锁和进程，这些锁和进程会导致进程从先前被其中一个锁阻塞的进程继承优先级。 这将在本文档的后面部分进行更详细的描述。
mutex
- 在本文档中，为了区分实现 PI 的锁和 PI 代码中使用的自旋锁，从现在开始，PI 锁将称为互斥体。
lock
- 从现在起，在本文档中，当指代用于保护 PI 算法部分的自旋锁时，我将使用术语锁。 这些锁禁用 UP 的抢占（当启用 CONFIG_PREEMPT 时）并且在 SMP 上防止多个 CPU 同时进入
临界区。
spin lock
- 与上面的锁相同。
waiter
- waiter 是存储在阻塞进程的堆栈中的结构。 由于等待程序的范围在被互斥量阻塞的进程的代码内，因此可以在进程的堆栈（局部变量）上分配等待程序。 这个结构包含一个指向任
务的指针，以及任务被阻塞的互斥量。 它还具有 rbtree 节点结构，用于将任务放置在互斥体的 waiters rbtree 以及互斥体所有者任务的 pi_waiters rbtree 中（如下所述）。
waiter 有时用于指代正在等待互斥体的任务。 这与 waiter->task 相同。
waiters
- 阻塞在mutex上的进程列表。
top waiter
- 等待特定互斥量的最高优先级进程。
top pi waiter
- 等待特定进程拥有的互斥量之一的最高优先级进程。
注意：
任务和进程在本文档中可互换使用，主要是为了区分一起描述的两个流程。
PI chain
----------
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
The chain would be::
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 的优先级。
Mutex Waiters Tree
------------------
每个互斥量都会跟踪所有被自身阻塞的等待者。 mutex 有一个 rbtree 来按优先级存储这些等待者。 该树由位于互斥体结构中的自旋锁保护。 这个锁叫做 wait_lock。
Task PI Tree
--------------
为了跟踪 PI 链，每个进程都有自己的 PI rbtree。 这是进程拥有的互斥体的所有top等待者的树。 请注意，这棵树只包含最上面的等待者，而不是被进程拥有的互斥锁阻塞的所有等待者。
任务 PI 树的顶部始终是等待任务拥有的互斥体的最高优先级任务。 因此，如果任务继承了优先级，则它始终是位于这棵树顶部的任务的优先级。
这棵树作为 rbtree 存储在进程的任务结构中的 pi_waiters 成员上。 它受任务结构中的名为 pi_lock 自旋锁的保护。 该锁也可以在中断上下文中获取，因此在锁定 pi_lock 时，必须禁
用中断。
Depth of the PI Chain
---------------------
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 链时一次最多只持有两个不同的锁。 更多关于下面的内容。
Mutex owner and flags
----------------------
互斥锁结构包含指向互斥锁所有者的指针。 如果不拥有互斥量，则此所有者设置为 NULL。 由于所有体系结构都具有至少两个字节对齐的任务结构（如果不是这样，rtmutex.c 代码将被
破坏！），这允许将最低有效位用作标志。 位 0 用作“有waiters”标志。 只要互斥体上有waiters，它就会被设置。
有关更多详细信息，请参阅 Documentation/locking/rt-mutex.rst。
cmpxchg Tricks
--------------
一些架构实现原子 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 与 owner 字段中的标志一起使用有助于针对支持它的体系结构进行优化。 这也将在本文档的后面部分进行解释。
Priority adjustments
--------------------
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 等待者与它自己的 normal/deadline 优先级进行比较，并取更高的优先级。 然后调用 rt_mutex_setprio 将任务的优先级调整为新的优先级。 请注意，rt_mutex_setprio
在 kernel/sched/core.c 中定义，以实现优先级的实际更改。
笔记：对于task_struct中的“prio”字段，数字越小，优先级越高。 5 的“prio”比 10 的“prio”具有更高的优先级。
有趣的是，rt_mutex_adjust_prio 可以增加或降低任务的优先级。 如果更高优先级的进程刚刚阻塞在任务拥有的互斥量上，rt_mutex_adjust_prio 将增加/提高任务的优先级。 但是，如果
更高优先级的任务由于某种原因离开了互斥量（超时或信号），这个相同的函数将降低/取消提高任务的优先级。 这是因为 pi_waiters 总是包含正在等待任务拥有的互斥体的最高优先级的任务，
所以我们只需要将最高 pi 等待者的优先级与给定任务的正常优先级进行比较。
High level overview of the PI chain walk
----------------------------------------
PI chain walk 由函数 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 和任务被阻塞的等待者树中的正确位置 。 这个函数解决了这一切。
Thomas Gleixner 在 rtmutex.c 中总结了该函数的主要操作。 有关详细信息，请参阅“Chain walk basics and protection scope”评论。
Taking of a mutex (The walk through)
------------------------------------
好的，现在让我们详细了解一下使用互斥量时会发生什么。
尝试的第一件事是快速获取互斥量。 这是在我们启用 CMPXCHG 时完成的（否则快速获取会自动失败）。 只有当 mutex 的 owner 字段为 NULL 时，才能使用 CMPXCHG 获取锁，无需执行任何其他
操作。
如果锁存在争用，我们将采用慢速路径 (rt_mutex_slowlock)。
慢路径函数是在堆栈上创建任务的waiter结构的地方。 这是因为只有在这个函数的范围内才需要 waiter 结构。 waiter 结构具有节点以将任务存储在互斥体的 waiters 树上，如果需要，还有所
有者的 pi_waiters 树。
互斥锁的 wait_lock 被占用，因为解锁互斥锁的慢速路径也占用了这个锁。
然后我们调用 try_to_take_rt_mutex。 这是不实现 CMPXCHG 的架构总是会获取锁的地方（如果没有争用）。
try_to_take_rt_mutex 每次任务尝试在慢速路径中获取互斥锁时使用。 这里要做的第一件事是对互斥量所有者字段的“Has Waiters”标志进行原子设置。 通过现在设置这个标志，被争用的互斥量
的当前所有者在不进入慢速解锁路径的情况下无法释放互斥量，然后它需要获取这段代码当前持有的 wait_lock。 因此设置“Has Waiters”标志会强制当前所有者与此代码同步。
如果满足以下条件，则锁定：
1）锁没有主人
2) 当前任务相对于锁的所有其他等待者具有最高优先级
如果任务成功获取锁，则将该任务设置为锁的所有者，如果该锁还有等待者，则将top_waiter（等待锁的最高优先级任务）添加到该任务的 pi_waiters 树中。
如果 try_to_take_rt_mutex() 没有取得锁，则调用 task_blocks_on_rt_mutex() 函数。 这会将任务添加到锁的等待者树中，并传播锁的 pi 链以及锁的所有者的 pi_waiters 树。 这将在下一
节中描述。
Task blocks on mutex
--------------------
互斥量和进程的记账是通过进程的等待者结构完成的。 “task”字段设置为进程，“lock”字段设置为互斥体。 waiter 的 rbtree 节点被初始化为进程的当前优先级。
由于 wait_lock 是在慢锁的入口处获取的，我们可以安全地将等待者添加到任务等待者树中。 如果当前进程是当前等待此互斥量的最高优先级进程，那么我们从所有者的 pi_waiters 中删除先前
的顶级等待进程（如果存在），并将当前进程添加到该树。 由于所有者的 pi_waiter 发生了变化，我们调用所有者的 rt_mutex_adjust_prio 来查看所有者是否应该相应地调整其优先级。
如果所有者也被锁阻塞，并且其 pi_waiters 已更改（或启用死锁检查），我们将解锁互斥体的 wait_lock 并继续在所有者上运行 rt_mutex_adjust_prio_chain，如前所述。
现在所有的锁都被释放了，如果当前进程仍然阻塞在一个互斥量上（等待者 "task" 字段不为 NULL），那么我们就进入睡眠状态（调用 schedule）。
Waking up in the loop
---------------------
该任务随后会因以下几个原因而唤醒：
1）之前的锁拥有者释放了锁，现在的任务是top_waiter
2）我们收到信号或超时
在这两种情况下，任务都会再次尝试获取锁。 如果是，那么它将自己从服务员树中取出并将自己设置回 TASK_RUNNING 状态。
在第一种情况下，如果在这个任务获得锁之前锁被另一个任务获得，那么它将回到睡眠状态并等待再次被唤醒。
第二种情况仅适用于正在获取互斥量的任务，这些互斥量可以在获得锁之前唤醒，无论是由于信号还是超时（即 rt_mutex_timed_futex_lock()）。 当被唤醒时，它将尝试再次获取锁，如果成功，
则任务将返回并持有锁，否则如果任务被信号唤醒，它将返回-EINTR，如果超时则返回-ETIMEDOUT。
Unlocking the Mutex
-------------------
互斥锁的解锁对于那些具有 CMPXCHG 的架构也有一条快速路径。 由于在争用时获取互斥体总是会设置互斥体所有者的“Has Waiters”标志，因此我们使用它来了解在解锁互斥体时是否需要采用慢
速路径。 如果互斥锁没有任何等待者，则互斥锁的所有者字段将等于当前进程，并且可以通过将所有者字段替换为 NULL 来解锁互斥锁。
如果所有者字段设置了“Has Waiters”位（或 CMPXCHG 不可用），则采用慢速解锁路径。
在慢速解锁路径中做的第一件事是获取互斥锁的wait_lock。 这同步了互斥量的锁定和解锁。
检查互斥体是否有等待者。 在没有 CMPXCHG 的体系结构上，这是互斥锁的所有者将确定是否需要唤醒waiter的位置。 在具有 CMPXCHG 的体系结构上，该检查在快速路径中完成，但在慢速路径中
仍然需要。 如果互斥量的等待者因为信号或所有者在快速路径 CMPXCHG 检查失败和获取 wait_lock 之间的超时而唤醒，则互斥量可能没有任何等待者，因此所有者仍然需要进行此检查。 如果没
有等待者，则互斥锁所有者字段设置为 NULL，wait_lock 被释放，不再需要其他任何东西。
如果有waiter，那么我们需要唤醒一个。
在唤醒代码中，当前所有者的 pi_lock 被占用。 找到锁的顶级等待者并将其从互斥体的等待者树以及当前所有者的 pi_waiters 树中删除。 “Has Waiters”位被标记以防止低优先级任务窃取锁。
最后我们解锁 pending owner 的 pi_lock 并唤醒它。
Contact
-------
如需本文档的更新，请发送电子邮件至 Steven Rostedt <[email protected]>
Credits
-------
作者：Steven Rostedt <[email protected]>
更新：Alex Shi <[email protected]> - 2017 年 7 月 6 日
原审稿人：
Ingo Molnar、Thomas Gleixner、Thomas Duetsch 和 Randy Dunlap
更新 (7/6/2017) 审稿人：Steven Rostedt 和 Sebastian Siewior
Updates
-------
本文档最初是为 2.6.17-rc3-mm1 编写的，更新于 4.12
标签：RT,rt,优先级,互斥,mutex,进程,PI From： https://www.cnblogs.com/hellokitty2/p/17006029.html