---
tags: concurrency
---
# [並行程式設計](https://hackmd.io/@sysprog/concurrency): 建立相容於 POSIX Thread 的實作
> 貢獻者: qwe661234, jserv
在 [Linux 核心設計: 不僅是個執行單元的 Process](https://hackmd.io/@sysprog/linux-process) 提及 [futex](https://man7.org/linux/man-pages/man2/futex.2.html)，我們可用來實作 lock，可見:
* [Linux futex based Read-Write Lock implementation](https://smoku.xiaoka.com/post/147930509718/linux-futex-based-read-write-lock-implementation)
* [Basics of Futexes](https://eli.thegreenplace.net/2018/basics-of-futexes/)
futex 允許在最低程度的 Linux 核心參與，達到執行緒之間的同步。以執行成本來說，系統呼叫大於 atomic 操作，因此 Linux 核心開發者儘量使用 atomic 操作，但仍要考慮以下:
1. busy wait
2. syscall
以 busy wait 來說，若等待時間過長，則會消耗所在處理器核的運算資源，相對來說，使用 syscall (如 `clock_nanosleep`)可將 cpu 的資源讓出，但要作業系統核心介入。
futex 的操作幾乎全部在使用者空間完成；只有當操作結果不一致從而需要仲裁時，才需要進入作業系統核心空間執行。這讓以 futex 為基礎的 lock 得高效進行：由於絕大多數的操作並不需要在多個行程之間進行仲裁，所以絕大多數操作都可以在應用程式空間執行，而不需要使用（相對高代價的）核心系統呼叫。
futex 在核心中藉由特製的佇列來管理執行緒或行程，可要求某個行程/執行緒 suspend 直到某個條件成立，或 signal 某個條件，來喚醒行程/執行緒。
在 [並行程式設計: POSIX Thread](https://hackmd.io/@sysprog/posix-threads)，提及案例: "Mutex and Semaphore" (你今天用對 mutex 了嗎？)，提醒要留意細節。參考 [`pthread_mutex_unlock(3p)`](https://man7.org/linux/man-pages/man3/pthread_mutex_lock.3p.html):
> If the mutex type is **`PTHREAD_MUTEX_DEFAULT`**, attempting to recursively lock the mutex results in undefined behavior. **Attempting to unlock the mutex if it was not locked by the calling thread results in undefined behavior.** Attempting to unlock the mutex if it is not locked results in undefined behavior.
仔細地看 [`pthread_mutex_unlock(3p)`](https://man7.org/linux/man-pages/man3/pthread_mutex_lock.3p.html) 會發現:
> If the mutex type is **`PTHREAD_MUTEX_ERRORCHECK`**, then error checking shall be provided. If a thread attempts to relock a mutex that it has already locked, an error shall be returned. **If a thread attempts to unlock a mutex that it has not locked or a mutex which is unlocked, an error shall be returned.**
我們需要在初始化 mutex 之際，就指定型態。
`mu` 是我們嘗試使用 futex 的多執行緒執行環境的實作，介面比照 POSIX Thread，針對 Linux/x86-64。原始程式碼: [MuThread](https://github.com/qwe661234/MuThreadPackage)
## futex 系統呼叫
〈[Fuss, Futexes and Furwocks: Fast Userlevel Locking in Linux](https://www.kernel.org/doc/ols/2002/ols2002-pages-479-495.pdf)〉(2002) 提及:
> In traditional UNIX systems, System V IPC (inter process communication) such as semaphores, msgqueues, sockets and the file locking mechanism (flock()) are the basic mechanisms for two processes to synchronize. These mechanisms expose an opaque handle to a kernel object that naturally provides the shared state and atomic operations in the kernel. Services must be requested through system calls (e.g., semop()). The drawback of this approach is that every lock access requires a system call. When locks have low contention rates, the system call can constitute a significant overhead.
傳統 kernel-based lock 機制在切換 locked 以及 unlocked 時，需要藉由系統呼叫進到核心模式，以確認是否有在等待 lock 的執行緒，但在執行緒間很少競爭共享資源 (low contention rate) 的情況下，沒有其他執行緒在 wait queue 中等待 lock，但還是要從使用者層級切換到核心模式去檢查，這樣頻繁的 CPU 模式切換會對效能有負面影響。
### futex
而 futex 是上述問題的解法之一, futex 是由一個位於核心空間中的 wait queue 以及一個在使用者層級空間中的 atomic integer 組成。 透過這個 atomic integer，我們可以知道是否有執行緒在 wait queue 中等待。 在沒有競爭 (contention) 的情況下，我們不需要進行 CPU 模式切換，進到核心喚醒其他執行緒或是到 wait queue 中等待。
不過, 在有競爭 (contention) 的情況下還是需要利用 futex 系統呼叫搭配 `FUTEX_WAIT` 和 `FUTEX_WAKE`，來喚醒其他執行緒或是到 wait queue 中等待。雖然可以做到不讓作業系統介入，也就是等待時利用 while-loop，不斷去嘗試取得 lock，但這樣的作法會消耗大量 CPU 效能，因為執行緒卡在 CPU 上持續運作。 因此，還是需要作業系統的介入，等待 lock 的執行緒到 wait queue 中等待被喚醒，讓 CPU 可以去進行別的任務。
## futex 系統呼叫
```c
long syscall(SYS_futex, uint32_t *uaddr, int futex_op, uint32_t val,
const struct timespec *timeout,
uint32_t *uaddr2, uint32_t val3);
```
* `uint32_t *uaddr`: futex 中使用者層級 atomic integer 所存放地址
* `int futex_op`: futex operator
1. `FUTEX_WAIT`
2. `FUTEX_WAKE`
* `uint32_t val`:
1. 在 `FUTEX_WAIT` 代表我們預期使用者層級 atomic integer 的值
2. 在 `FUTEX_WAKE` 代表喚醒的執行緒數量
### `FUTEX_WAIT`
根據 [futex(2)](https://man7.org/linux/man-pages/man2/futex.2.html)
>This operation tests that the value at the futex word pointed to by the address uaddr still contains the expected value val, and if so, then sleeps waiting for a FUTEX_WAKE operation on the futex word. ... If the thread starts o sleep, it is considered a waiter on this futex word.
If the futex value does not match val, then the call fails immediately with the error EAGAIN.
FUTEX_WAIT operation 會先去比較在 uaddr 中的值，也就是 futex 的值是不是 expected value，相同的話代表目前 futex 是 locked 的狀態，將此執行緒插入 wait queue 中等待， 不同則回傳 error number EAGAIN。
### FUTEX_WAKE
根據 [futex(2)](https://man7.org/linux/man-pages/man2/futex.2.html)
> This operation wakes at most val of the waiters that are waiting (e.g., inside FUTEX_WAIT) on the futex word at the address uaddr. Most commonly, val is specified as either 1 (wake up a single waiter) or INT_MAX (wake up all waiters). No guarantee is provided about which waiters are awoken (e.g., a waiter with a higher scheduling priority is not guaranteed to be awoken in preference to a waiter with a lower priority).
`FUTEX_WAKE` operation 用來喚醒在 futex wait queue 上等待的執行緒，喚醒執行緒個數由參數 val 決定，喚醒哪個或哪些執行緒是由排程器來決定。
## mutex.c
* futex = 0 時代表 unlocked
* futex = 1 時代表 locked
### 1. `NORMAL_MUTEX`, `DEFAULT_MUTEX`
#### `lock_normal`
利用 `atomic_bool_cmpxchg` 判斷 futex 是否 unlocked，如果是則將 futex 設為 1，取得 lock，否則呼叫 futex 系統呼叫，到 wait queue 中等待。
```c
static int lock_normal(muthread_mutex_t *mutex)
{
while (1) {
if (atomic_bool_cmpxchg(&mutex->futex, 0, 1))
return 0;
SYSCALL3(__NR_futex, &mutex->futex, FUTEX_WAIT, 1);
}
}
```
#### `trylock_normal`
利用 `atomic_bool_cmpxchg` 判斷 futex 是否 unlocked，如果是則將 futex 設為 1，取得 lock，否則回傳 error。
>`EBUSY` : Device or resource busy
```c
static int trylock_normal(muthread_mutex_t *mutex)
{
if (atomic_bool_cmpxchg(&mutex->futex, 0, 1))
return 0;
return -EBUSY;
}
```
#### `unlock_normal`
利用 `atomic_bool_cmpxchg` 判斷 futex 是否 locked，如果是則將 futex 設為 0， 否則代表有其他執行緒在等待，利用 futex 系統呼叫喚醒在 wait queue 中的執行緒。
```c
static int unlock_normal(muthread_mutex_t *mutex)
{
if (atomic_bool_cmpxchg(&mutex->futex, 1, 0))
SYSCALL3(__NR_futex, &mutex->futex, FUTEX_WAKE, 1);
return 0;
}
```
### 2. `ERRORCHECK_MUTEX`
#### `lock_errorcheck && trylock_errorcheck`
檢查同一個執行緒是否重複上鎖。
```c
muthread_t self = muthread_self();
if (mutex->owner == self)
return -EDEADLK;
```
取得 lock 後，會將 lock 持有者設為自己，往後才能追蹤 lock 的持有者。
```c
mutex->owner = self;
```
#### `unlock_errorcheck`
檢查對 lock 進行釋放的執行緒是否為 lock 的持有者，以及是否對狀態為 unlocked 的 lock 進行釋放。
>`EPERM` : Operation not permitted
```c
if (mutex->owner != muthread_self() || mutex->futex == 0)
return -EPERM;
```
釋放 lock 後要將 lock 持有者設為 0 。
```c
mutex->owner = 0;
```
### 3. `RECURSIVE_MUTEX`
Recursive lock 允許 lock 持有者重複取得 lock，利用 counter 來紀錄 lock 持有者重複取得 lock 的次數，取得 lock 次數與釋放 lock 的次數必須相等。
#### `lock_recursive && trylock_recursive`
如果為 lock 持有者重複取得 lock 則將 counter + 1，若為非 lock 持有者取得 lock 則須重新設定 lock 持有者。
recursive mutex 需要檢查 counter 是否 overflow，如果 overflow 則回傳 error。
>`EAGAIN` : Resource temporarily unavailable
```c
if (mutex->counter == (uint64_t) -1)
return -EAGAIN;
```
#### `unlock_recursive`
檢查對 lock 進行釋放的執行緒是否為 lock 的持有者。
```c
if (mutex->owner != muthread_self())
return -EPERM;
```
如果是 lock 持有者釋放 lock，將 counter - 1，唯有 counter 為 0 時才將 lock 釋放並將 lock 持有者設為 0。
## Thread Local Storage
[A Deep dive into (implicit) Thread Local Storage](https://chao-tic.github.io/blog/2018/12/25/tls)
- 允許執行緒擁有私自的資料。對於每個執行緒來說，TLS 是獨一無二，不會相互影響。案例: 全域變數 `errno` 可能在多執行緒並行執行時錯誤，透過 TLS 處理 `errno` 是個解決方案
- `__thread`, 在 POSIX Thread 稱為 thread-specific data，可見 [pthread_key_create](https://linux.die.net/man/3/pthread_key_create), [pthread_setspecific](https://linux.die.net/man/3/pthread_setspecific)
- 在 x86/x86_64 Linux，[fs segment 用以表示 TLS 的起始位置](https://www.kernel.org/doc/html/latest/x86/x86_64/fsgs.html)，讓執行緒知道該用的空間位於何處
> 對照 Fuchsia 的文件 [Thread Local Storage
](https://fuchsia.googlesource.com/fuchsia/+/refs/heads/main/docs/development/kernel/threads/tls.md)
在 mu 中，TLS 用來保存 per-thread stack 資訊。
## 程式碼改進
### `atomic_bool_cmpxchg`
#### 加入 `UNIQUE_ID`
原本的 `atomic_bool_cmpxchg` 在 old 以及 new 變數前加上底線作為變數名稱，這樣很容易造成命名衝突，因此參考 [Linux 核心原始程式碼巨集: max, min](https://hackmd.io/@sysprog/linux-macro-minmax) 的做法，引入 UNIQUE_ID 來防止命名衝突
```c
#define ___PASTE(a , b) a##b
#define __PASTE(a , b) ___PASTE(a, b)
#define __UNIQUE_ID(prefix) \
__PASTE(__PASTE(__UNIQUE_ID_, prefix), __COUNTER__)
#define _atomic_bool_cmpxchg(ptr, varname1, varname2, old, new) \
({ \
typeof(*ptr) varname1 = (old), varname2 = (new); \
bool r = atomic_compare_exchange_strong_explicit( \
ptr, &varname1, varname2, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST); \
r; \
})
#define atomic_bool_cmpxchg(ptr, old, new) \
_atomic_bool_cmpxchg(ptr, __UNIQUE_ID(old), __UNIQUE_ID(new), old, new) \
```
#### 改以 C11 Atomics 實作
原本的實作是透過第四個變數來決定 memory order 是 weak 或 strong
```c
__atomic_compare_exchange(ptr, &_old, &_new, false,
__ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST);
```
改成 C11 Atomics 後，strong order 與 weak order 分別對應到不同函式， 此外C11 標準引入 `_Atomic` 關鍵字，將特定的型態轉變為對應的 atomic 型態，這邊的第一個參數 ptr 就必須是 atomic 型態。
`_explicit` 結尾的函式可指定 memory_order 參數，可參考 [並行程式設計: Atomics 操作](https://hackmd.io/@sysprog/concurrency-atomics)
```c
atomic_compare_exchange_strong_explicit(ptr, &varname1, varname2,
__ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST);
```
## 實作 priority inheritance mutex
參考 POSIX Thread 中的 [`pthread_attr_setschedparam`](https://code.woboq.org/userspace/glibc/nptl/pthread_attr_setschedparam.c.html) 及 [`pthread_attr_setschedpolicy`](https://code.woboq.org/userspace/glibc/nptl/pthread_attr_setschedpolicy.c.html)，這二個函式分別用來設定執行緒在排程器中的優先權 (priority) 以及排程策略 (policy)，設定完成後會在函式 `start_thread` 中利用系統呼叫 `sched_setscheduler` 來設定執行緒的排程策略以及優先權，不同的排程策略會有不同的優先權，在設定前會先檢查優先權是否在正確的範圍內。
我們可用命令 `$ chrt -m` 印出所有的排程策略以及對應的最高和最低優先權
```
SCHED_OTHER min/max priority : 0/0
SCHED_FIFO min/max priority : 1/99
SCHED_RR min/max priority : 1/99
SCHED_BATCH min/max priority : 0/0
SCHED_IDLE min/max priority : 0/0
SCHED_DEADLINE min/max priority : 0/0
```
詳細 scheduler policy 可參考 [sched(7)](https://man7.org/linux/man-pages/man7/sched.7.html)
:::info
Note: 設定執行緒在排程器中的優先權 (priority) 以及排程策略 (policy)需要呼叫 `muthread_attr_setinheritsched` 並設定第二個參數為 `TBTHREAD_EXPLICIT_SCHED`，才能成功設定執行緒的優先權以及排程策略。
:::
### priority inversion
實作 priority inheritance mutex 是為了解決 priority inversion，取用 [並行程式設計: POSIX Thread](https://hackmd.io/@sysprog/posix-threads) 中的內容，來分別解釋 priority inversion 發生的情況以及如何利用 priority inheritance(PI) 來解決這個問題。
> 優先權: Task~1~(H) > Task~2~(M) > Task ~3~(L)
* 針對上圖解析
* `(1)` Task~3~ 正在執行，而 Task~1~ 和 Task~2~ 正等待特定事件發生，例如 timer interrupt
* `(2)` Task~3~ 為了存取共用資源，必須先獲取 lock
* `(3)` Task~3~ 使用共用資源 (灰色區域)。
* `(4)` Task~1~ 等待的事件發生 (可以是 "delay n ticks"，此時 delay 結束)，作業系統核心暫停 Task~3~ 改執行 Task~1~，因為 Task~1~ 有更高的優先權
* `(5)` `(6)` Task~1~ 執行一段時間直到試圖存取與 Task~3~ 共用的資源，但 lock 已被 Task~3~ 取走了，Task~1~ 只能等待 Task~3~ 釋出 lock
* `(7)` `(8)` Task~3~ 恢復執行，直到 Task~2~ 因特定事件被喚醒，如上述 `(4)` 的 Task~3~
* `(9)` `(10)` Task~2~ 執行結束後，將 CPU 資源讓給 Task~3~
* `(11)` `(12)` Task~3~ 用完共享資源後釋放 lock。作業系統核心知道尚有個更高優先權的任務 (即 Task~1~) 正在等待此 lock，執行 context switch 切換到 Task~1~
* `(13)` Task~1~ 取得 lock，開始存取共用資源。
Task~1~ 原本該有最高優先權，但現在卻降到 Task~3~ 的等級，於是反到是 Task~2~ 和 Task~3~ 有較高的優先權，優先權順序跟預期不同，這就是 Priority Inversion(優先權反轉)。
priority inheritance (PI) 是其中一種 Priority Inversion 解法:
針對上圖解析
* `(1)` `(2)` 同上例，Task~3~ 取得 lock
* `(3)` `(4)` `(5)` Task~3~ 存取資源時被 Task ~1~ 搶佔
* `(6)` Task~1~ 試圖取得 lock。作業系統核心發現 Task~3~ 持有 lock，但 Task~3~ 優先權卻低於 Task~1~，於是作業系統核心將 Task~3~ 優先權提升到與 Task~1~ 的等級
* `(7)` 作業系統核心讓 Task~3~ 恢復執行，Task~1~ 則繼續等待
* `(8)` Task~3~ 用畢資源，釋放 lock，作業系統核心將 Task~3~ 恢復成原本的優先權，恢復 Task~1~ 的執行
* `(9)` `(10)` Task~1~ 用畢資源，釋放 lock
* `(11)` Task~1~ 釋出 CPU，Task~2~ 取得 CPU 控制權。在這個解法中，Task~2~ 不會導致 priority inversion
### priority inheritance mutex
priority inheritance mutex 利用和上述相似的手法，假設低優先權的執行緒先取得 lock，當高優先權的執行緒嘗試去取得 lock 時，發現 lock 已經被持有了並且持有 lock 的執行緒其優先權比自己低，此時高優先權的執行緒會利用系統呼叫，將目前持有 lock 的執行緒的優先權暫時提高到和自己一樣，以此來降低 priority inversion 發生的機率，在 unlock 後，優先權被暫時提高的執行緒會降回到原始的優先權。
## priority inheritance mutex 實驗
### 實驗目的
為了測試 priority inheritance mutex 是否可以成功降低 priority inversion 發生的機率，首先我們利用一般的 mutex 來重現 priority inversion，接著引入 priority inheritance mutex 來測試 priority inversion 發生的機率是否降低。
### 實作 priority inversion
為了實作 priority inversion，首先必須建立三個擁有不同優先權的執行緒，依照優先權高、中、低，分別稱執行緒為 T1, T2, T3，及二個不同的 mutex，Lock1、Lock2，T1 和 T3 使用到 Lock1，T2 會使用 Lock2。
#### 使用一般 mutex 發生 priority inversion 步驟解析
根據《Demystifying the Linux CPU Scheduler》的 3.3.2 一節 Reschedule when adding a task to the runqueue
> A task can be added to the runqueue in 2 cases: when it is created, and when it is woken up. ...
> Waking up a process is similar to creating a new one: the task is first inserted into the runqueue and then the system checks if the currently running task needs to be rescheduled.
> Before inserting the task into the runqueue, the sched_waking event is trig-gered and the task’s state is set to `TASK_WAKING`. The task is then inserted into the runqueue by `activate_task()`. Once it is on the runqueue, the `task_struct->on_rq` field is set to `TASK_ON_RQ_QUEUED`. Finally, `ttwu_do_wakeup()`(`ttwu` = Try To Wake Up) is called, which checks if the current task can be preempted with `check_preempt_curr()`; then it sets the task's state to `TASK_RUNNING` and triggers the `sched_wakeup` event.
我們可知當執行緒從 sleep 狀態被 wake up 後，會被加入 runqueue 中，接著排程器會檢查目前正在 running 狀態的執行緒是否可被搶佔 (preempt)。
* T3 取得 Lock1，接著透過系統呼叫 `nanosleep` 進入 sleep 並讓出 CPU 資源
* T1 取得 CPU 資源並嘗試取得 Lock1，但發現 Lock1 已經被 T3 持有，因此讓出 CPU 資源等待 T3 釋放 Lock1
* T2 取得 Lock2，接著透過系統呼叫 `nanosleep` 進入 sleep 並讓出 CPU 資源
* T3 和 T2 被 wake up
因為有 interrupt 發生，因此實際 sleep 的時間會比設定的時間多，無法確定 T3 和 T2 誰會先被 wake up，以下兩種情形會導致 priority inversion。
1. T2 先被 wake up 插入 runqueue，排程器發現目前無其他執行緒使用 CPU 資源，T2 取得 CPU 資源
2. T3 先被 wake up 插入 runqueue，排程器發現目前無其他執行緒使用 CPU 資源，T3 取得 CPU 資源，但接著 T2 被 wake up 插入 runqueue 中，排程器發現正在使用 CPU 資源的 T3 優先權較低，因此 T2 preempt T3，取得 CPU 資源，T3 則插入 runqueue 中等待排程
* T2 結束 task，釋放 Lock2 並讓出 CPU 資源
* T3 取得 CPU 資源，T3 結束 task，釋放 Lock1 並讓出 CPU 資源
* T1 取得 Lock1 和 CPU 資源，T1 結束 task，釋放 Lock1 並讓出 CPU 資源
實際優先權是 T1 > T2 > T3, 但完成任務的順序卻是 T2 $\to$ T3 $\to$ T1, priority inversion 發生。
#### 測試程式
測試程式必須透過 `sudo taskset -c ${cpu num}` 以 root 權限執行固定在特定 cpu 上，另外，排程器相關的系統呼叫也需要以 root 權限執行。
[測試程式 source code](https://github.com/qwe661234/MuThreadPackage/tree/main/Tests)
#### 使用 priority inheritance mutex 步驟解析
* T3 取得 Lock1，接著透過系統呼叫 `nanosleep` 進入 sleep 並讓出 CPU 資源
* T1 取得 CPU 資源並嘗試取得 Lock1，但發現 Lock1 已經被 T3 持有且 T3 的優先權比自己低，因此先將 T3 提升到和自己擁有相同的優先權，接著讓出 CPU 等待 T3 釋放 Lock1
* T2 取得 Lock2，接著透過系統呼叫 `nanosleep` 進入 sleep 並讓出 CPU 資源
* T3 和 T2 被 wake up
因為有 interrupt 發生，因此實際 sleep 的時間會比設定的時間多，無法確定 T3 和 T2 誰會先被 wake up，但之前會發生 priority inversion 的情況被解決了。
1. T2 先被 wake up 插入 runqueue 中，排程器發現目前無其他執行緒使用 CPU 資源，T2 取得 CPU 資源，但接著 T3 被 wake up 插入 runqueue 中，排程器發現正在使用 CPU 資源的 T2 優先權較低，因此 T3 preempt T2，取得 CPU 資源，T2 則插入 runqueue 中等待排程
2. T3 先被 wake up，排程器發現目前無其他執行緒使用 CPU 資源，T3 取得 CPU 資源，因為 T3 的優先權已經被 T1 提升，所以後來被 wake up 的 T2 無法搶佔 T3，只能到 runqueue 中等待排程
* T3 結束 task，釋放 Lock1，讓出 CPU 資源並將優先權回復到原本的優先權
* T1 取得 Lock1 和 CPU 資源，T1 結束 task，釋放 Lock1 並讓出 CPU 資源
* T2 取得 CPU 資源，T2 結束 task，釋放 Lock2 並讓出 CPU 資源
完成任務的順序是 T3 $\to$ T1 $\to$ T2，而非原本的 T2 $\to$ T3 $\to$ T1，使用 priority inheritance lock 來降低 priority inversion 的發生機率。
### 測試結果
重複執行測試程式 100 次並計算 priority inversion 發生次數
#### 使用 normal mutex
在 100 次執行中，發生 82 次 priority inversion (每次執行結果可能不同)，即執行順序為 T2 -> T3 -> T1
```
priority_inversion times = 82 for 100.0 runs
```
#### 使用 priority inheritance mutex
在 100 次執行中，發生 0 次 priority inversion，對比使用 normal mutex 發生 82 次 priority inversion，使用 priority inheritance mutex 成功降低 priority inversion 發生機率。
```
priority_inversion times = 0 for 100.0 runs
```
## 實作 priority protection mutex
另一種解決 priority inversion 的方法為 priority protection, 根據 [IBM AIX Document - Synchronization scheduling](https://www.ibm.com/docs/en/aix/7.2?topic=programming-synchronization-scheduling)
> **Priority protection protocol**
Sometimes called priority ceiling protocol emulation. In the priority protection protocol, each mutex has a priority ceiling. It is a priority level within the valid range of priorities. When a thread owns a mutex, it temporarily receives the mutex priority ceiling, if the ceiling is higher than its own priority. It recovers its original priority when it unlocks the mutex. The priority ceiling should have the value of the highest priority of all threads that may lock the mutex. Otherwise, priority inversions or even deadlocks may occur, and the protocol would be inefficient.
priority protection 又稱 priority ceiling, 其手法是在建立 mutex 前會提前設定一個特定值 `prioceiling`，`prioceiling` 為一個比所有可能取得此 mutex 的其他執行緒之優先權高的值，且必須在該排程策略 (policy) 的合法優先權範圍內。 一旦執行緒取得 mutex ，將持有 mutex 的執行緒的優先權提高到 `prioceiling`，在釋放 mutex 時再降回到原始的優先權，以此來降低 priority inversion 的機率。
priority protection 有另位一種實作方式，就是當執行緒取得 mutex 時，將持有 mutex 的執行緒的優先權提高到該排程策略 (policy) 的優先權最大值，不過這樣的作法可能會過度提升執行緒的優先權，造成其他執行重要任務的執行緒無法搶佔 CPU 資源。
### priority protection mutex 實驗
目的為測試 priority protection mutex 是否可以成功降低 priority inversion 發生的機率，透過和上述 priority inheritance mutex 實驗一樣的方式來以一般的 mutex 來重現 priority inversion, 並改以 priority protection mutex 來測試 priority inversion 發生的機率是否下降。
#### 使用 priority protection mutex 步驟解析
* T3 取得 Lock1，將自己的優先權提升到，接著透過系統呼叫 `nanosleep` 進入 sleep 並讓出 CPU 資源
* T1 取得 CPU 資源並嘗試取得 Lock1，但發現 Lock1 已經被 T3 持有，讓出 CPU 等待 T3 釋放 Lock1
* T2 取得 Lock2，接著透過系統呼叫 `nanosleep` 進入 sleep 並讓出 CPU 資源
* T3 和 T2 被 wake up
因為有 interrupt 發生，因此實際 sleep 的時間會比設定的時間多，無法確定 T3 和 T2 誰會先被 wake up，但之前在使用一般 mutex 會發生 priority inversion 的情況被解決了。
1. T2 先被 wake up 插入 runqueue 中，排程器發現目前無其他執行緒使用 CPU 資源，T2 取得 CPU 資源，但接著 T3 被 wake up 插入 runqueue 中，排程器發現正在使用 CPU 資源的 T2 優先權較低，因此 T3 preempt T2，取得 CPU 資源，T2 則插入 runqueue 中等待排程
2. T3 先被 wake up，排程器發現目前無其他執行緒使用 CPU 資源，T3 取得 CPU 資源，因為 T3 的優先權已經提升到最高，所以後來被 wake up 的 T2 無法搶佔 T3，只能到 runqueue 中等待排程
* T3 結束 task，釋放 Lock1，讓出 CPU 資源並將優先權回復到原本的優先權
* T1 取得 Lock1 和 CPU 資源，將自己的優先權提升到該排程策略合法優先權的最大值，T1 結束 task，釋放 Lock1 並讓出 CPU 資源，將優先權回復到原本的優先權
* T2 取得 CPU 資源，T2 結束 task，釋放 Lock2 並讓出 CPU 資源
完成任務的順序是 T3 $\to$ T1 $\to$ T2，而非原本的 T2 $\to$ T3 $\to$ T1，使用 priority inheritance lock 來降低 priority inversion 的發生機率。
### priority protection mutex 設定
* `muthread_mutexattr_setprioceiling`: 設定 mutex 的 `prioceiling`
```c
muthread_mutexattr_setprioceiling(&mattr, 30);
muthread_mutexattr_setprotocol(&mattr, TBTHREAD_PRIO_PROTECT);
muthread_mutex_init(&mutex_normal, &mattr);
```
### 測試結果
重複執行測試程式 100 次並計算 priority inversion 發生次數
#### 使用 normal mutex
在 100 次執行中，發生 79 次 priority inversion (每次執行結果可能不同)，即執行順序為 T2 $\to$ T3 $\to$ T1
```
priority_inversion times = 79 for 100.0 runs
```
#### 使用 priority protection mutex
在 100 次執行中，發生 0 次 priority inversion，對比使用 normal mutex 發生 79 次 priority inversion，使用 priority protection mutex 成功降低 priority inversion 發生機率。
```
priority_inversion times = 0 for 100.0 runs
```
## 實作上需考慮的議題
### 1. priority inheritance mutex 連鎖效應
連鎖效應是指在多個執行緒競爭多個資源時，使用 priority inheritance mutex，在提升某個執行緒的優先權時，必須連帶提升持有該執行緒等待資源的其他執行緒。
以上圖(實線代表已持有資源，虛線則代表嘗試取得)為例，三個執行緒依照優先權高到低分別為 TASK~1~、TASK~2~、TASK~3~，二個資源分別為 A 和 B，且假設 TASK~3~ 已持有資源 A，TASK~2~ 已持有資源 B 並嘗試取得資源 A， TASK~1~ 則嘗試取得資源 B，假如資源 A 和 B 皆為 priority inheritance mutex，在上述情況下會有連鎖效應。
> [圖片來源](https://www.embedded.com/how-to-use-priority-inheritance/)
針對上圖解析
1. TASK~3~ 取得 CPU 資源並取得資源 A
2. TASK~2~ 擁有較高優先權，因此搶佔 TASK~3~ 取得 CPU 資源並取得資源 B，接著 TASK~2~ 嘗試取得資源 A，發現資源 A 已經被 TASK~3~ 持有且 TASK~3~ 的優先權比自己低，因此先將 TASK~3~ 提升到和自己擁有相同的優先權，接著讓出 CPU 資源等待 TASK~3~ 釋放資源 A
3. TASK~3~ 取得 CPU 資源，繼續執行
4. TASK~1~ 擁有較高優先權，因此搶佔 TASK~3~ 取得 CPU 資源並嘗試取得資源 B，發現資源 B 已經被 TASK~2~ 持有且 TASK~2~ 的優先權比自己低，因此先將 TASK~2~ 提升到和自己擁有相同的優先權，但在提升 TASK~2~ 優先權的同時，發現 TASK~2~ 正在等待 TASK~3~ 讓出資源 A，因此連帶將 TASK~3~ 提升到和自己擁有相同的優先權，並讓出 CPU 資源等待 TASK~2~ 釋放資源 B
5. TASK~3~ 取得 CPU 資源
6. TASK~3~ 結束 task，釋放資源 A，讓出 CPU 資源並將優先權回復到原本的優先權
7. TASK~2~ 取得資源 A 和 CPU 資源，TASK~2~ 結束 task，釋放資源 A 和資源 B 並讓出 CPU 資源，將優先權回復到原本的優先權
8. TASK~1~ 取得資源 B 和 CPU 資源，TASK~1~ 結束 task，釋放資源 B 並讓出 CPU 資源
在步驟 4 中 TASK~1~ 發現資源 B 已經被 TASK~2~ 持有，所以提升 TASK~2~ 的優先權，同時又發現 TASK~2~ 正在等待 TASK~3~ 讓出資源 A，因此連帶提升 TASK~3~ 的優先權，這種情形即為連鎖效應。
#### 透過 `wait list` 實作連鎖效應
`wait list` 是個單向鏈結串列，用以實作連鎖效應。 每個執行緒都有自己的 `wait list`，當一執行緒正在等待某個 mutex 釋放時，將該 mutex 加入 `wait list` 中，並在取得 mutex 時，將其從 `wait list` 中移除。因為 priority inheritance mutex 會記錄 mutex 的持有者，因此可以透過 `wait list` 來追蹤執行緒正在等待的資源持有者，在提升執行緒的優先權時，連帶提升該執行緒等待的資源持有者之優先權。
由於 `wait list` 中的 mutex 是在取得後才會移除，因此查看 mutex 持有者時有可能目前 mutex 是 `unlocked` 狀態，只是目前的執行緒尚未取得該 mutex，所以嘗試提升 mutex 持有者的優先權時，要判斷目前 mutex 是否有持有者。
### 2. 釋放 lock 後回復執行緒優先權
在執行緒釋放 lock 後回復優先權的實作上，會等到執行緒釋放完所有資源才回復，不會每釋放一個資源就回復一次，亦即執行緒會持續擁有高優先權，直到完成任務釋放所有資源才會回復優先權。
以 priority protection mutex 來舉例， 假設有一個原始優先權為 10 執行緒 TASK~1~ 以及資源 A 和資源 B，二個資源的 `prioceiling` 分別為 20 以及 30， TASK~1~ 取得資源 A 後，優先權提升到 20，接著 TASK~1~ 取得資源 B，優先權提升到 30，接著 TASK~1~ 釋放資源 B，但此時並不會改變優先權，而是讓 TASK~1~ 持續擁有優先權 30，直到釋放資源 A，才回將 TASK~1~ 的優先權回復到 10。
#### 透過 `priomap` 實作
透過陣列 `priomap`，每當執行緒的優先權改變時，就會在 `priomap` 中新增一筆紀錄，當執行緒釋放 lock 時，會刪除 `priomap` 中的一筆紀錄，當刪除完紀錄且發現 `priomap` 為空時，代表執行緒釋放完全部的資源，此時才會回復原始優先權。
## priority inheritance mutex 和 priority protection mutex 效能比較
### priority inheritance mutex 無法解決的問題
#### 1. Deadlock
以上圖(實線代表已持有資源，虛線則代表嘗試取得)為例，二個執行緒依照優先權高到低分別為 TASK~2~、TASK~1~，二個資源分別為 A 和 B，且資源 A 和 B 皆為 priority inheritance mutex。
* 發生 Deadlock 情形
1. TASK~1~ 取得 CPU 資源並取得資源 A
2. TASK~2~ 擁有較高優先權，因此搶佔 TASK~1~ 取得 CPU 資源並取得資源 B，接著 TASK~2~ 嘗試取得資源 A，發現資源 A 已經被 TASK~1~ 持有且 TASK~1~ 的優先權比自己低，因此先將 TASK~1~ 提升到和自己擁有相同的優先權，接著讓出 CPU 資源等待 TASK~1~ 釋放資源 A
3. TASK~1~ 取得 CPU 資源，嘗試取得資源 B，發現資源 B 已經被 TASK~2~ 持有，接著讓出 CPU 資源等待 TASK~2~ 釋放資源 B
4. Deadlock 發生，TASK~1~ 和 TASK~2~ 互相等待對方釋放資源
* 如果將資源 A 改成 priority protection mutex 且將 `prioceiling` 設為比 TASK~2~ 的優先權高的值
1. TASK~1~ 取得 CPU 資源並取得資源 A， TASK~1~ 的優先權提升至 `prioceiling`， 接著取得資源 B
2. TASK~1~ 完成執行，釋放資源 A 和 B 並讓出 CPU 資源
3. TASK~2~ 取得 CPU 資源和資源 B，接著取得資源 A
4. TASK~2~ 完成執行，釋放資源 A 和 B 並讓出 CPU 資源
改用 priority protection mutex 有機會解決 Deadlock。
#### 2. Chained Blocking
Chained Blocking: 一個高優先權執行緒為了取得 n 個資源，被 n 個低優先權執行緒執行緒 block 住，這種情形就稱為 Chained Blocking。
以上圖(實線代表已持有資源，虛線則代表嘗試取得)為例，三個執行緒依照優先權高到低分別為 TASK~1~、TASK~2~、TASK~3~，二個資源分別為 A 和 B，且假設 TASK~3~ 已持有資源 A，TASK~2~ 已持有資源 B， TASK~1~ 則嘗試取得資源 A 和資源 B，資源 A 和 B 皆為 priority inheritance mutex。
> [圖片來源](http://osnet.cs.nchu.edu.tw/powpoint/Embedded/part2/Chapter%204.pdf)
* 針對上圖發生 Chained Blocking 情形解析
1. TASK~3~ 取得 CPU 資源並取得資源 A
2. TASK~2~ 擁有較高優先權，因此搶佔 TASK~3~ 取得 CPU 資源並取得資源 B
3. TASK~1~ 擁有較高優先權，因此搶佔 TASK~2~ 取得 CPU 資源並嘗試取得資源 A，發現資源 A 已經被 TASK~3~ 持有且 TASK~3~ 的優先權比自己低，因此先將 TASK~3~ 提升到和自己擁有相同的優先權，並讓出 CPU 資源等待 TASK~3~ 釋放資源 A
4. TASK~3~ 取得 CPU 資源
5. TASK~3~ 結束 task，釋放資源 A，讓出 CPU 資源並將優先權回復到原本的優先權
6. TASK~1~ 取得 CPU 資源並取得資源 A， 接著嘗試取得資源 B，發現資源 B 已經被 TASK~2~ 持有且 TASK~2~ 的優先權比自己低，因此先將 TASK~2~ 提升到和自己擁有相同的優先權，並讓出 CPU 資源等待 TASK~2~ 釋放資源 B
7. TASK~2~ 取得 CPU 資源
8. TASK~2~ 結束 task，釋放資源 B，讓出 CPU 資源並將優先權回復到原本的優先權
9. TASK~1~ 取得資源 B 和 CPU 資源，TASK~1~ 結束 task，釋放資源 A 和 B 並讓出 CPU 資源
高優先權的 TASK~1~ 為了取得資源 A 和 B，分別被低優先權的 TASK~2~ 和 TASK~3~ block 住，這樣的情形即為 Chained Blocking。
* 如果將資源 A 改成 priority protection mutex 且將 `prioceiling` 設為比 TASK2 的優先權高的值
1. TASK~3~ 取得 CPU 資源並取得資源 A，TASK~3~ 的優先權提升至 `prioceiling`
3. TASK~1~ 擁有較高優先權，因此搶佔 TASK~3~ 取得 CPU 資源並嘗試取得資源 A，發現資源 A 已經被 TASK~3~ 持有，讓出 CPU 資源等待 TASK~3~ 釋放資源 A
4. TASK~3~ 取得 CPU 資源
5. TASK~3~ 結束 task，釋放資源 A，讓出 CPU 資源並將優先權回復到原本的優先權
6. TASK~1~ 取得 CPU 資源並取得資源 A，接著取得資源 B
7. TASK~1~ 完成執行，釋放資源 A 和 B 並讓出 CPU 資源
8. TASK~2~ 取得 CPU 資源並取得資源 B
9. TASK~2~ 結束 task，釋放資源 B，讓出 CPU 資源
改用 priority protection mutex 有機會解決 Chained Blocking，將 `prioceiling` 設為比 TASK~3~ 的優先權高的值也有機會解決 Chained Blocking。
### 小結
在執行緒很少競爭資源的情況下，會選擇使用 priority inheritance mutex，而不是 priority protection mutex。 因為 priority protection mutex 是只要取得 mutex 就會利用系統呼叫來提升優先權，不管有沒有其他執行緒來競爭 mutex。 而 priority inheritance mutex 則是當有較高優先權的執行緒嘗試取得 mutex 且發現 mutex 已被較低優先權的執行緒持有時，才會利用系統呼叫來提升持有 mutex 的執行緒的優先權。由於系統呼叫有較大的 overhead，因此 priority inheritance mutex 效能表現較好。
但如果會遇到上述 priority inheritance mutex 無法解決的問題，就需要考慮資源分配的問題或改以 priority protection mutex 來作為 mutex，避免高優先權執行緒無法即時完成任務。不過改以 priority protection mutex 只是有機會解決並不是保證能解決，因為除非特別設計執行緒的執行順序，不然無法保證執行緒的生成順序和執行順序，且 DeadLock 和 Chained Blocking 也是有機會發生，並不保證一定會發生，都是要看執行緒的建立和執行順序而定。
## 自動將 muthread 切換成 pthread
Muthread Package 支援藉由 `$ make PTHREAD=1` 自動將 muthread 函式切換成對應的 pthread 函式。
## 參照 [lock_test.c](https://github.com/attractivechaos/benchmarks/blob/master/lock/lock_test.c) 設計效能分析程式並改進程式碼
測試程式 [test-08-benchmark.c](https://github.com/qwe661234/MuThreadPackage/blob/main/Tests/test-08-benchmark-PI.c) 參考 [lock_test.c](https://github.com/attractivechaos/benchmarks/blob/master/lock/lock_test.c)，利用測試程式 [test-08-benchmark.c](https://github.com/qwe661234/MuThreadPackage/blob/main/Tests/test-08-benchmark-PI.c) 來比較 muthread 和 pthread 之間的效能差異。
### `muthread_join`
在進行比較前，我們必須先讓 muthread 可以進行 join，原本的 muthread 是利用 `musleep`，讓執行緒等待特定秒數後完成任務，不過這樣的作法無法得到正確的執行時間，因此必須實做 `muthread_join`。
`muthread_join` 參考 `pthread_join`，實做方式類似 lock 和 unlock，首先會確認 thread id 是否等於 0，如果非 0 則利用 `futex` 系統呼叫並以 `FUTEX_WAIT` 操作進行等待，接著修改原本的 `start_funciton`，在執行緒完成任務時，將 thread id 設為 0，利用 `futex` 系統呼叫並以 `FUTEX_WAKE` 操作喚醒 `main_thread` 完成 join。
### 改進 lock 和 unlock
在比較時發現到，以單一執行緒進行比較時，執行時間差距近 10 倍，而多執行緒的情況下雖比 pthread 慢，但差異沒有到單執行緒如此顯著，於是利用工具 `strace`，比較兩者系統呼叫的差異。
透過比較兩者系統呼叫發現，在單執行緒時，pthread 在 unlock 時完全沒有用到 `futex` 系統呼叫來喚醒其他執行緒，而 muthread 原本的實作則大量使用到 `futex` 系統呼叫。進一步追蹤 glibc 的實作發現，和 muthread 的 futex 0 代表 unlocked, 1 代表 locked 不同，glibc 中的 futex 有三個狀態： 0, 1, 2。
0 代表 unlocked, 1 代表 locked 且沒有其他執行緒在等待，而 2 則代表 locked 且有其他執行緒在等待，因此實作上唯有 futex 狀態為 2 時才會利用 `futex` 系統呼叫來喚醒其他執行緒，這也說明為什麼 pthread 在單一執行緒時 unlock 時沒有利用到 `futex` 系統呼叫來喚醒其他執行緒。
### 加上 `FUTEX_PRIVATE_FLAG`
另一項改進是將原本的操作 `FUTEX_WAIT` 和 `FUTEX_WAKE` 改為 `FUTEX_WAIT_PRIVATE` 和 `FUTEX_WAKE_PRIVATE`，在 [futex(2)](https://man7.org/linux/man-pages/man2/futex.2.html) 中提到
> It tells the kernel that the futex is process-private and not shared with another process (i.e., it is being used for synchronization only between threads of the same process). This allows the kernel to make some additional performance optimizations.
加入 `FUTEX_PRIVATE_FLAG`，可告知核心該 futex 沒有和其他行程共享，且該行程擁有自己的 futex hash table queueing structure，允許核心進行其他改進。
```c
static int lock_normal(muthread_mutex_t *mutex)
{
if (atomic_bool_cmpxchg(&mutex->futex, 0, 1))
return 0;
else {
if (atomic_load_explicit(&mutex->futex, memory_order_relaxed) == 2)
goto futex;
while (atomic_exchange_explicit(&mutex->futex, 2, memory_order_acquire) != 0) {
futex:
SYSCALL3(__NR_futex, &mutex->futex, FUTEX_WAIT_PRIVATE, 2);
}
}
return 0;
}
static int unlock_normal(muthread_mutex_t *mutex)
{
if (atomic_exchange_explicit(&mutex->futex, 0, memory_order_release) == 2)
SYSCALL3(__NR_futex, &mutex->futex, FUTEX_WAKE_PRIVATE, 1);
return 0;
}
```
### 新增 clone flag
新增二個 clone flag `CLONE_CHILD_CLEARTID` 和 `CLONE_PARENT_SETTID`， `CLONE_PARENT_SETTID` 設定後，在進行 clone 系統呼叫時，核心會把執行緒 id 寫入第五個參數 (parent_tid) 指定的記憶體位置，而設定 `CLONE_CHILD_CLEARTID` 後，在執行緒結束時，核心會將存放執行緒 id 的記憶體位置清除為 0，並利用 futex 系統呼叫喚醒在此記憶體位置等待的執行緒。
透過設定這二個 clone flag，執行 join 函式時，我們可用 futex 系統呼叫等待在存放執行緒 id 的記憶體位置上，等到執行緒完成任務後，核心會自動將此記憶體位置清除為 0，並利用 futex 系統呼叫喚醒在此記憶體位置等待的執行緒。
:::warning
Note: 這邊是由核心來喚醒，所以在 join 函式中，futex 系統呼叫的 futex operation 不可以加上 `PRIVATE_FLAG`
:::
## 改以 PI futex operation 來實作 priority inheritance mutex
為了解決 priority inversion 問題，Linux 提供 priority-inheritance (PI) futexes 的支援，如果 futex operation 後面有加上 PI flag，即代表此 operation 使用的是 PI futexes，如 `FUTEX_LOCK_PI` 和 `FUTEX_UNLOCK_PI` 等。
PI futex 是透過在 kernel 中的 rt_mutex 來實作， PI futex 和一般 futex 的狀態不同， PI 的狀態有三種， unlocked 時為 0， 有執行緒持有 lock 時為該執行緒的 tid，如果有執行緒持有 lock 且有其他執行緒在等待時為 `FUTEX_WAITERS | 該執行緒的 tid`，`FUTEX_WAITERS` 用來標記有其他執行緒在等待。
### `rt_mutex`
`rt_mutex` 是一個在 Linux 核心中的 lock，PI futex 利用 `rt_mutex` 作為代理
#### `rt_mutex` 結構體
```c
struct rt_mutex {
raw_spinlock_t wait_lock; // lock
struct rb_root_cached waiters; // wait_list
struct task_struct *owner; // lock owner
};
struct rb_root_cached {
struct rb_root rb_root;
struct rb_node *rb_leftmost;
};
```
在 `rt_mutex` 中記錄 owner，而 waiters 是個 `wait_list` 用來記錄所有等待該 `rt_mutex` 的執行緒。waiters 使用[紅黑樹](https://hackmd.io/@sysprog/linux-rbtree)實作，會依照優先權排序，優先權最高的 waiter 稱為 top waiter。
接在 waiters 這個 `wait_list` 上面的是另一個結構 `rt_mutex_waiter`，`rt_mutex_waiter` 是用來鏈接 rt_mutex 和等待中的執行緒，紀錄了是哪個執行緒（`task_struct`）在等待哪個 lock（rt_mutex）。
而 `task_struct` 結構體中也有一個成員 `pi_waiters`，這個 `pi_waiters` 同樣也是利用紅黑樹實作的 `wait_list`，會依照優先權排序，這個 wait_list 中包含此執行緒持有的所有 rt_mutex wait_list 中的 top waiter。 舉例來說，有 5 個 Task 分別為 Task~A~、Task~B~、Task~C~、Task~D~、Task~E~，優先權大小為 A > B > C > D > E，以及二個 lock 分別為 rt_mutex~1~ 和 rt_mutex~2~，當 Task~A~ 持有 rt_mutex~1~ 和 rt_mutex~2~，而 Task~B~、Task~C~ 在等待 rt_mutex~1~，Task~D~、Task~E~ 在等待 rt_mutex~2~，關係如下圖所示
由圖中可以看出綠色線是 waiters，代表 `rt_mutex` 的 `wait_list`，這條 wait_list 會依照優先權來排序，他會挑選出優先權最高的 top waiter，接在持有該 rt_mutex 的執行緒的 pi_waiters 上，由圖中的紅色線可看出，Task~A~ 的 pi_waiters 分別接上 rt_mutex~1~ 和 rt_mutex~2~ 的 top waiter，也就是指向 Task~B~ 和 Task~A~ 的 rt_mutex_waiter。
### 如何利用 rt_mutex 實作 priority inheritance
當今天有新的執行緒被加入 rt_mutex 的 wait_list 中時，因為 wait_list 會依照優先權排序，如果這個後來被加入的執行緒是 top waiter，這樣他就會取代原本接在持有該 rt_mutex 的執行緒的 pi_waiters 上的舊的 top_waiter，成為新的 top_waiter 接在 pi_waiters 上，此時就會檢查這個新的 pi_waiters 的優先權是否比持有該 rt_mutex 的執行緒的優先權高，如果有就讓該執行緒繼承新的 top_waiter 的優先權，以這樣的方式來實作 priority inheritance。
### rt_mutex PI-chain
利用 rt_mutex, rt_mutex_waiter 和 pi_waiters 三個結構體可組合出 PI-chain，PI-chain 是一個樹狀結構，用來實作連鎖效應和檢查是否有 deadlock 發生，由上面的案例組出的 PI-chain 如下圖所示
#### 連鎖效應
舉例來說，三個執行緒依照優先權高到低分別為 Task~A~、Task~B~、ask~C~，二個資源分別為 rt_mutex~1~ 和 rt_mutex~2~，且假設 Task~C~ 已持有資源 rt_mutex~1~，Task~B~ 已持有資源 rt_mutex~2~ 並嘗試取得資源 rt_mutex~1~， Task~A~ 則嘗試取得資源 rt_mutex~2~，在上述情況下會有連鎖效應。
PI-chain 如下圖所示
如上圖紅色線，當 Task~A~ 成為 rt_mutex~2~ 的 top waiter 時，Task~B~ 會繼承 Task~A~ 的優先權，透過 PI-chain 得知 Task~B~ 正在等待 rt_mutex~1~，因此連帶讓 rt_mutex~1~ 的持有者 Task~C~ 繼承 Task~A~ 的優先權，以此機制透過 PI-chain 來實作連鎖效應。
#### deadlock
`rt_mutex_waiter` 要接到 `wait_list` 上時，`rt_mutex` 會先檢查是否有 deadlock 發生，如果有會拒絕將 `rt_mutex_waiter` 接到 `wait_list` 上來避免 deadlock。
舉例來說，二個執行緒依照優先權高到低分別為 Task~A~、Task~B~，二個資源分別為 rt_mutex~1~ 和 rt_mutex~2~。
1. Task~A~ 持有 rt_mutex~1~，Task~B~ 持有 rt_mutex~2~
2. Task~B~ 嘗試取得 rt_mutex~1~，但此時 rt_mutex~1~ 已經被 Task~A~ 持有了，因此被接到 rt_mutex~1~ 的 wait_list 上等待，
3. Task~A~ 嘗試取得 rt_mutex~2~，但此時 rt_mutex~2~ 已經被 Task~B~ 持有了，因此被接到 rt_mutex~2~ 的 wait_list 上等待，不過此時 rt_mutex 透過 PI-chain 檢查 deadlock 發現有 deadlock 發生，如下圖紅色線，因此 Task~A~ 不會被接到 rt_mutex~2~ 的 wait_list 上等待。
Sign in with Wallet
Connect another wallet