---
tags: linux2022
---

# 實作 Thread package
contributed by < [`qwe661234`](https://github.com/qwe661234) >

> GitHub: [MuThread](https://github.com/qwe661234/MuThreadPackage)

以[第 10 週測驗題](https://hackmd.io/@sysprog/linux2022-quiz10)給定的程式碼為基礎，實作類似 POSIX Thread 的套件

## Why futex?
論文 ["Fuss, Futexes and Furwocks: Fast Userlevel Locking in Linux" by Franke, Russell, Kirkwood. Published in 2002 for the Ottawa Linux Symposium.](https://www.kernel.org/doc/ols/2002/ols2002-pages-479-495.pdf) 提到
> 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 模式切換會對效能有負面影響。

:::warning
TODO: 從研究文獻指出原本採用系統呼叫處理 mutex lock 的成本分析，儘量採用權威研究素材。
:notes: jserv

done
:::

### 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 系統呼叫

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
根據 [man page 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 or 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
根據 [man page 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 中等待。

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

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 中的執行緒。

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 && tryolck_errorcheck
檢查同一個執行緒是否重複上鎖。

muthread_t self = muthread_self();
if (mutex->owner == self)
    return -EDEADLK;

取得 lock 後，會將 lock 持有者設為自己，往後才能追蹤 lock 的持有者。

mutex->owner = self;

#### unlock_errorcheck
檢查對 lock 進行釋放的執行緒是否為 lock 的持有者，以及是否對狀態為 unlocked 的 lock 進行釋放。
>`EPERM` : Operation not permitted

if (mutex->owner != muthread_self() || mutex->futex == 0)
    return -EPERM;

釋放 lock 後要將 lock 持有者設為 0 。

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

if (mutex->counter == (uint64_t) -1)
    return -EAGAIN;

#### unlock_recursive
檢查對 lock 進行釋放的執行緒是否為 lock 的持有者。

if (mutex->owner != muthread_self())
    return -EPERM;

如果是 lock 持有者釋放 lock，將 counter - 1，唯有 counter 為 0 時才將 lock 釋放並將 lock 持有者設為 0。
## 程式碼改進
### atomic_bool_cmpxchg
#### 加入 UNIQUE_ID
原本的 atomic_bool_cmpxchg 在 old 以及 new 變數前加上底線作為變數名稱，這樣很容易造成命名衝突，因此參考 [Linux 核心原始程式碼巨集: max, min](https://hackmd.io/@sysprog/linux-macro-minmax#%E9%81%BF%E5%85%8D%E5%91%BD%E5%90%8D%E8%A1%9D%E7%AA%81) 的做法，引入 UNIQUE_ID 來防止命名衝突

#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

__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/https%3A%2F%2Fhackmd.io%2F%40sysprog%2Fconcurrency-atomics#Memory-Ordering-%E5%92%8C-Barrier)

atomic_compare_exchange_strong_explicit(ptr, &varname1, varname2, 
                        __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST);

## 實作 priority inheritance mutex
參考 pthread library 中的 [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 可參考 [man page 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/concurrency/https%3A%2F%2Fhackmd.io%2F%40sysprog%2Fposix-threads#POSIX-Thread) 中的內容，來分別解釋 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~1~ 持有 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 -> T3 -> T1, priority inversion 發生。

#### 測試程式
:::warning
在探討程式碼之前，應該要說明測試目標和方法。
:notes: jserv

done
:::
測試程式必須透過 `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 -> T1 -> T2，而非原本的 T2 -> T3 -> 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 -> T1 -> T2，而非原本的 T2 -> T3 -> T1，使用 priority inheritance lock 來降低 priority inversion 的發生機率。

### priority protection mutex 設定
* `muthread_mutexattr_setprioceiling`: 設定 mutex 的 `prioceiling`

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 -> T3 -> 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` 是一個 singly-linked 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 function 切換成對應的 pthread function。

> 參照 [lock_test.c](https://github.com/attractivechaos/benchmarks/blob/master/lock/lock_test.c)，撰寫 mutex lock 的 benchmark 程式，比對 muthread 和 pthread 的效能表現
> :notes: jserv
## 參照 [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.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.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 man page](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，可以告訴 kernel 這個 futex 沒有和其他 process 共享，且此 process 會擁有自己的 futex hash table queueing structure，允許 kernel 進行其他的優化。

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 function 時我們可以利用 futex 系統呼叫等待在存放執行緒 id 的記憶體位置上，等到執行緒完成任務後，核心會自動將此記憶體位置清除為 0，並利用 futex 系統呼叫喚醒在此記憶體位置等待的執行緒。

:::warning
Note: 這邊是由核心來喚醒，所以在 join function 中 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 是一個在 kernel 中的 lock，PI futex 利用 rt_mutex 作為代理
#### rt_mutex 結構體

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 使用紅黑樹實作，會依照優先權排序，優先權最高的 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~2~，但此時 rt_mutex~2~ 已經被 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 上等待。


:::info
TODO:
- [x] futex system call
- [x] 實作 priority inherit
- [x] 實作 priority protection
- [x] pthread and muthread 切換
- [x] atomic compare -> Unique_ID
- [x] 在 PRIO_INHERIT / PRIO_PROTECT 檢查 lock, unlock 失敗情況
- [x] 調整為可以同時存在多種 mutex attribute
- [x] test case 複雜化 先用 pthread 測試
- [x] make check 執行 test
- [x] mummap, mumunmap, mubrk SYSTEMCALL 改成 systemcall wrapper (brk systemcall wrapper 和原本 systemcall 回傳值不同， glibc 還沒提供 futex wrapper)
- [x] 寫 Readme 描述現有功能，高階描述 Thread package
- [x] PI futex
- [x] 實作 join 接著做 benchmark 程式，比較 muthread and pthread 效能
- [ ] normal 效能比較以及 PI 效能比較
- [ ] 實作 condition variable
:::