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 核心

目錄

本頁