linux2023 - Homework2
=====================

contributed by <`NOVBobLee`>
> [GitHub](https://github.com/NOVBobLee/sysprog202308) \
> [2023 年暑期 Linux 核心課程第 1 次測驗題](https://hackmd.io/@sysprog/linux2023-summer-quiz1) \
> [2023 年暑期 Linux 核心課程第 2 次測驗題](https://hackmd.io/@sysprog/linux2023-summer-quiz2)

## 延伸問題 `1`−1
### futex 整理
futex (Fast User-space muTEX) 為 Linux 系統呼叫之一，代號 `SYS_futex` ，是 Linux 提供給開發者實作 locking 與 semaphore 等機制的組件，目的在減少不必要的 user-kernel space 轉換。在沒有競爭的情況下， futex 的操作可以只在 user space 中完成，相反地，在有競爭的情況下，才會進入 kernel space ，執行將等待者排進等待佇列，進入睡眠狀態等。

當一群執行緒持有一共享記憶體 (限定 32-bit 長度， 64 位元架構也不例外，因此也被稱為 futex word ) ，各執行緒根據各自使用的 futex 操作和 futex 的值，可以自己進入睡眠狀態或是被其他執行緒喚醒。根據 futex 不同的操作，有各自相異的帶入參數。

long syscall(SYS_futex, uint32_t *uaddr, int futex_op, uint32_t val,
             const struct timespec *timeout,   /* or: uint32_t val2 */
             uint32_t *uaddr2, uint32_t val3);

基本參數:
1. `uaddr`: futex 的地址 (需 4 位元組對齊) 。
2. `futex_op`: futex 的操作代號，如 `FUTEX_WAIT` 、`FUTEX_WAKE` 等。
3. `val`: 此值對於不同 futex 操作會有不同的意義。

futex 操作 (`futex_op`) 敘述:
1. `FUTEX_WAIT`: 若位於 `uaddr` 上的 futex 等於 `val` ，此執行緒進入睡眠狀態，同時也會進入此 futex 的等待佇列。若有使用 `timeout` ，可以在時間到以後被喚醒；若沒有使用，則必須等待其他執行緒使用 `FUTEX_WAKE` 等方式，喚醒 futex 等待佇列裡的執行緒 (沒有順序保證) 。最初的比較若不相等，則會得到 `EAGAIN` 的回傳值，比較目的是避免錯過任何喚醒機會。

:::warning
How does it prevent losing wake-ups?
:::

2. `FUTEX_WAKE`: 喚醒屬於 `uaddr` 上 futex 的等待佇列中之執行緒 (沒有順序保證) ，最大數量為 `val` 。

3. `FUTEX_REQUEUE`: 若位於 `uaddr` 上的 futex 等於 `val3` ，則喚醒最多 `val` 數量於此 futex 等待佇列中的執行緒，而在此佇列中剩下的執行緒將會被移動到位於 `uaddr2` 上的 futex 等待佇列中。移動上限數量為 `val2` 。此操作目的為增加被喚醒的時機，比起原本只有 timeout 和 `FUTEX_WAKE` 方式， `FUTEX_REQUEUE` 可以移動到不同 futex 上，增加被喚醒的時機，同時也可以減少使用系統呼叫次數所帶來的成本。

比方移動到 mutex 上，由於 mutex 各自互斥，喚醒的方式變成一次喚醒一個，相比使用 `FUTEX_WAKE` 一次喚醒 `INT_MAX` 個 futex 產生競爭的情況，失敗又要回到 kernel space 裡等待下一次喚醒的不小成本。 (見下面 `cond_broadcast()` 說明)

4. `FUTEX_PRIVATE_FLAG`: 告訴 kernel 此 futex 限制在此 process 內 (只於此 process 中的執行緒間分享) 。可以使用 `<linux/futex.h>` 使此操作與其他 futex 操作結合，如 `FUTEX_WAIT_PRIVATE` 等。

> [futex(2)](https://man7.org/linux/man-pages/man2/futex.2.html) \
> [futex(7)](https://man7.org/linux/man-pages/man7/futex.7.html) \
> [A description of what robust futexes are](https://docs.kernel.org/locking/robust-futexes.html)

### 精簡的 POSIX Thread 實作摘錄

static inline bool spin_trylock(spinlock_t *lock)
{
    /* Do a read first to avoid bouncing the cache line if it is locked */
    return !load(&lock->state, relaxed) &&
           !exchange(&lock->state, true, acquire);
}

static inline void spin_lock(spinlock_t *lock)
{
    /* Given the specific implementation of spin_trylock(), this results in
     * a test-and-test-and-set (TTAS) loop. Refer to
     * https://rigtorp.se/spinlock/ for more information.
     */
    while (!spin_trylock(lock))
        spin_hint();
}

當一處理器 A 持有 lock ，而一個處理器 B 等待其釋放 `spin_lock()` ，此時處理器 B 會不停去讀取自己 lock 的 cache line ，等其結果變為 `false` 時，才會進入下一個動作 `exchange()` ，試著去爭取 lock 。

在兩個以上處理器都在等待釋放的情況下，各自的 cache line 就停留在 Shared 狀態。相反得，假如沒有先 `load()` ，而是直接 `exchange()` ，這些處理器會不停地互相進行 RFO (Request for Ownership) ，然後傳送自己的 cache line 給得到擁有權的處理器 cache 上，再進行寫入動作，這些 cache line 會在 Modified 和 Invalid 之間不停變換狀態，這將會大大影響效能。

> [What every programmer should know about memory, part 2: CPU caches](https://lwn.net/Articles/252125/#:~:text=3.3.4%20Multi) 見 3.3.4 MESI Protocol

#define spin_hint() __builtin_ia32_pause()

`pasue` 是設計給 spin_wait 使用的處理器指令， spin_wait 在等待的期間，會不停查看 `lock` 的狀態，若沒有在迴圈內使用 `pause` ，讀取所佔的時間會變得相當高，由於 cache coherency 的關係，這會影響到持有 `lock` 的執行緒釋放 (寫入) 的時機點。若加入 `pause` ，則可以讓讀取的頻率降低，同時也能減少能源消耗。此外， `pause` 本身會產生 bubble ([pipeline stall](https://en.wikipedia.org/wiki/Pipeline_stall)) ，達到 de-pipeline 的效果，這在離開迴圈時可以避免掉[分支預測](https://en.wikipedia.org/wiki/Branch_predictor)錯誤的懲罰。

> [[PDF] Intel® 64 and IA-32 Architectures Optimization Reference Manual.pdf](https://software.intel.com/content/www/us/en/develop/download/intel-64-and-ia-32-architectures-optimization-reference-manual.html) 見 11.4.2 \
> [Stalls and flushes - lec13.pdf](https://courses.cs.washington.edu/courses/cse378/09wi/lectures/lec13.pdf)

enum {
    MUTEX_LOCKED = 1 << 0,
    MUTEX_SLEEPING = 1 << 1,
};

static bool mutex_trylock(mutex_t *mutex)
{
    int state = load(&mutex->state, relaxed);
    if (state & MUTEX_LOCKED)
        return false;

    state = fetch_or(&mutex->state, MUTEX_LOCKED, relaxed);
    if (state & MUTEX_LOCKED)
        return false;

    thread_fence(&mutex->state, acquire);
    return true;
}

static inline void mutex_lock(mutex_t *mutex)
{
#define MUTEX_SPINS 128
    for (int i = 0; i < MUTEX_SPINS; ++i) {
        if (mutex_trylock(mutex))
            return;
        spin_hint();
    }

    int state = exchange(&mutex->state, MUTEX_LOCKED | MUTEX_SLEEPING, relaxed);

    while (state & MUTEX_LOCKED) {
        futex_wait(&mutex->state, MUTEX_LOCKED | MUTEX_SLEEPING);
        state = exchange(&mutex->state, MUTEX_LOCKED | MUTEX_SLEEPING, relaxed);
    }

    thread_fence(&mutex->state, acquire);
}

static inline void mutex_unlock(mutex_t *mutex)
{
    int state = exchange(&mutex->state, 0, release);
    if (state & MUTEX_SLEEPING)
        futex_wake(&mutex->state, 1);
}

當 `mutex_lock()` 沒取得 lock 時，會使用 `futex_wait()` 進入睡眠。當擁有 lock 的執行緒釋放 lock 時，會更改 `mutex` 的狀態，然後呼叫 `futex_wake()` ，喚醒一個睡眠中的執行緒。

只要存在睡眠中的執行緒， `mutex` 會維持著 `MUTEX_LOCKED | MUTEX_SLEEPING` 的狀態 (註: 呼叫 `mutex_unlock()` 會變回 `0` 的狀態，但只要存在 futex 在等待，就會回到 `futex_wait()` 的位置，狀態又變回 `MUTEX_LOCKED | MUTEX_SLEEPING` ) ，直到沒有睡眠中的執行緒。

static inline void cond_wait(cond_t *cond, mutex_t *mutex)
{
    int seq = load(&cond->seq, relaxed);

    mutex_unlock(mutex);

#define COND_SPINS 128
    for (int i = 0; i < COND_SPINS; ++i) {
        if (load(&cond->seq, relaxed) != seq) {
            mutex_lock(mutex);
            return;
        }
        spin_hint();
    }

    futex_wait(&cond->seq, seq);

    mutex_lock(mutex);

    fetch_or(&mutex->state, MUTEX_SLEEPING, relaxed);
}

static inline void cond_signal(cond_t *cond, mutex_t *mutex)
{
    fetch_add(&cond->seq, 1, relaxed);
    futex_wake(&cond->seq, 1);
}

照字面上看， `cond_wait()` 在等待 `cond_signal()` 或 `cond_broadcast()` 的信號，若在一定時間內沒等到，則會進入睡眠，直到有信號來通知才會被喚醒。 `cond_` 函數外面一定會被 mutex 包住，其中一個作用在保護 [predicate](https://stackoverflow.com/a/32383037/16257547) ，以 `qsort_mt.c` (下面程式碼) 舉例，就是 `qs->st` 。另一個則是保護 condvar (condition variable) ，也就是 `cond->seq` (註: 在 `cond_wait()` 裡，CS 就第 `3, 20` 行而已，中間必須放掉 mutex ，否則就沒其他執行緒可以改變 predicate 和 condvar ) 。

第 `3` 行將 `cond->seq` 記錄下來，然後在第 `8~14` 行測試 `cond->seq` 是否有改變 (包括第 `16` 行 `futex_wait()` 也會測試 `cond->seq` 是否改變) ，亦即是否有執行緒呼叫 `cond_signal()` 或 `cond_broadcast()` 。若有改變，則取回 mutex 然後返回，否則在 `futex_wait()` 那進入睡眠等待。

> [pthread_cond_wait(3p)](https://man7.org/linux/man-pages/man3/pthread_cond_wait.3p.html) \
> [pthread_cond_broadcast(3p)](https://man7.org/linux/man-pages/man3/pthread_cond_broadcast.3p.html)

mutex_lock(&qs->mtx_st);
while (qs->st == ts_idle)
    cond_wait(&qs->cond_st, &qs->mtx_st);
mutex_unlock(&qs->mtx_st);

mutex_lock(&qs->mtx_st);
qs->st = ts_term;
cond_signal(&qs->cond_st, &qs->mtx_st);
mutex_unlock(&qs->mtx_st);

:::warning
Why add `MUTEX_SLEEPING` flag after `futex_wait()` ?

回到 mutex 的程式碼，mutex 的睡眠也是用 futex 去實現。而喚醒是在 `mutex_unlock()` 中執行 `futex_wake()` ，執行條件為 mutex 在 `MUTEX_SLEEPING` 的狀態下。

但這是針對 mutex <--- `cond_broadcast()` ?
:::

static inline void cond_broadcast(cond_t *cond, mutex_t *mutex)
{
    fetch_add(&cond->seq, 1, relaxed);
    futex_requeue(&cond->seq, 1, &mutex->state);
}

`cond_broadcast()` 使用 `futex_requeue()` ，先喚醒一個 `cond_wait()` ，之後的喚醒則是交由 mutex 內的 futex 來執行。由於在 `cond_` 函式外面會有 mutex 包住，每個 `cond_` 各自互斥，取代 `futex_wake(INT_MAX)` 互相競爭的狀況， mutex 會一次喚醒一個執行緒，直到所有在等待的 mutex 都喚醒完。

### 測試程式 `main.c`

digraph {
    nodesep=.5;

    graph [rankdir=LR];
    node [shape=record];
    #edge [color=Blue, style=dashed];
    
    clock [xlabel="clcok", label="<f0> mutex | cond | ticks"];
    
    node15 [xlabel="nodes[15]", label="<f0> clock | <f1> parent | ready | cond | mutex"];
    
    many_nodes [label="...", color=transparent];
    
    node1 [xlabel="nodes[1]", label="<f0> clock | <f1> parent | ready | cond | mutex"];
    
    node0 [xlabel="nodes[0]", label="<f0> clock | <f1> parent | ready | cond | mutex"];
    
    node0:f0 -> node1:f1 [dir=back];
    node1:f0 -> many_nodes [dir=back];
    many_nodes -> node15:f1 [dir=back];
    
    node0:f0 -> clock:f0;
    node1:f0 -> clock:f0;
    node15:f0 -> clock:f0;
}

測試方式採多執行緒互相以 condvar 溝通，最終檢查交由 [TSan](https://github.com/google/sanitizers) 與 `pthread_join()` 檢測。上圖為程式中使用的物件圖示，每個執行緒會擁有各自的 `node` ，同時共享一個 `clock` ， `node` 之間會有 `parent` 的指標表示親子的關係，其中存在一個 `node` 是沒有 `parent` 的。

static bool clock_wait(struct clock *clock, int ticks)
{
    mutex_lock(&clock->mutex);
    while (clock->ticks >= 0 && clock->ticks < ticks)
        cond_wait(&clock->cond, &clock->mutex);
    bool ret = clock->ticks >= ticks;
    mutex_unlock(&clock->mutex);
    return ret;
}

static void clock_tick(struct clock *clock)
{
    mutex_lock(&clock->mutex);
    if (clock->ticks >= 0)
        ++clock->ticks;
    mutex_unlock(&clock->mutex);
    cond_broadcast(&clock->cond, &clock->mutex);
}

static void clock_stop(struct clock *clock)
{
    mutex_lock(&clock->mutex);
    clock->ticks = -1;
    mutex_unlock(&clock->mutex);
    cond_broadcast(&clock->cond, &clock->mutex);
}

`clock` 是在執行緒間共享的物件，其中 `ticks` 成員為程式中的共用計數器，同時也是控制所有執行緒繼續運行或停止的旗號。 `clock_wait()` 在之後的子執行緒中， `ticks` 增加速度通常會大於 `clock->ticks` 的速度，那個 `while` 和 `cond_wait()` 就是提供暫時煞車的功能，使得每個子執行緒運行在不超過自己該有的步調上。

:::warning
Should `cond_broadcast()` be calling inside a mutex?
:::

static void node_wait(struct node *node)
{
    mutex_lock(&node->mutex);
    while (!node->ready)
        cond_wait(&node->cond, &node->mutex);
    node->ready = false;
    mutex_unlock(&node->mutex);
}

static void node_signal(struct node *node)
{
    mutex_lock(&node->mutex);
    node->ready = true;
    mutex_unlock(&node->mutex);
    cond_signal(&node->cond, &node->mutex);
}

`node_` 函式控制各執行緒的運行許可。

static void *thread_func(void *ptr)
{
    struct node *self = ptr;
    bool bit = false;

    for (int i = 1; clock_wait(self->clock, i); ++i) {
        if (self->parent)
            node_wait(self->parent);

        if (bit) {
            node_signal(self);
        } else {
            clock_tick(self->clock);
        }
        bit = !bit;
    }

    node_signal(self);
    return NULL;
}

int main(void)
{
    struct clock clock;
    clock_init(&clock);

#define N_NODES 16
    struct node nodes[N_NODES];
    node_init(&clock, NULL, &nodes[0]);
    for (int i = 1; i < N_NODES; ++i)
        node_init(&clock, &nodes[i - 1], &nodes[i]);

    pthread_t threads[N_NODES];
    for (int i = 0; i < N_NODES; ++i) {
        if (pthread_create(&threads[i], NULL, thread_func, &nodes[i]) != 0)
            return EXIT_FAILURE;
    }

    clock_tick(&clock);
    clock_wait(&clock, 1 << N_NODES);
    clock_stop(&clock);

    for (int i = 0; i < N_NODES; ++i) {
        if (pthread_join(threads[i], NULL) != 0)
            return EXIT_FAILURE;
    }

    return EXIT_SUCCESS;
}

程式的運行概述:
1. 第 `35` 行各子執行緒開始運行，若親執行緒尚未執行第 `39` 行，則於第 `6` 行 `clock_wait()` 等待
2. 第 `39` 行親執行緒呼叫 `clcok_tick()` ，使各子執行緒通過 `clock_wait()` ，然後親執行緒在第 `40` 行 `clock_wait()` 等待

(開始第 `6-16` 行的迴圈。子執行緒名稱由所擁有的 `node` 序數命名，例如第 0 號執行緒。)

3. 除了沒有 `parent` 的第 0 號執行緒，其餘執行緒在第 `8` 行 `node_wait()` 等待
4. 由於 `bit` 的關係，子執行緒的迴圈會是一次 `clock_tick()` ，一次 `node_signal()` ，當第 0 號執行緒執行第二次迴圈時，會呼叫 `node_signal()` ，使得第 1 號執行緒可以運行。同理，當第 1 號執行緒執行第二次會圈時，會呼叫 `node_signal()` ，使第 2 號執行緒可以運行。換句話說， `parent` 執行緒的迴圈數會是自己的兩倍，以第 0, 1, 2 號執行緒來看，其迴圈數比等於 $4:2:1$ 。

(當第 `40` 行的 `clock_wait()` 達到停止條件時。)

5. 只要 `clock->ticks` 為非負整數，子執行緒的迴圈就不會停下來，唯有第 `41` 行的 `clock_stop()` 或者整數溢位會變成負數。整數溢位理論上 (如果親執行緒在一定時間內沒被排程到) 可以排除， `1 << N_NODES` 離溢位還差個 $2^{15}$ 倍。
6. 每次迴圈都會用 `clock_wait()` 檢查是否 `clock->ticks` 為負數，一旦為負，則跳出迴圈，呼叫 `node_signal()` 通知下一個執行緒執行，最終每個子執行緒都完成自己的工作。
7. 子執行緒完成工作後， `pthread_join()` 會回傳 `0` ，表示子執行緒有順利返回。在沒有子執行緒返回失敗的情況下，這次對精簡版 POSIX Thread 和 NPTL (Native POSIX Thread Library) 的檢驗就通過了。

> [b04690f](https://github.com/NOVBobLee/sysprog202308/commit/b04690fa452426b91d851187b71a0bdea66573cd) (主要: 印出各執行緒最終迴圈 `i` 數值) \
> [0c4fb1b](https://github.com/NOVBobLee/sysprog202308/commit/0c4fb1bd36bb9d155af42fc82e348374d95367d6) (修改 bug)

觀察每個執行緒自己的計數器 `i` 最後一個 (有進入) 迴圈的數值:

[Thread 0] tick=65536
[Thread 1] tick=32768
[Thread 2] tick=16384
[Thread 3] tick=8192
[Thread 4] tick=4096
[Thread 5] tick=2048
[Thread 6] tick=1024
[Thread 7] tick=512
[Thread 8] tick=256
[Thread 9] tick=128
[Thread 10] tick=64
[Thread 11] tick=32
[Thread 12] tick=16
[Thread 13] tick=8
[Thread 14] tick=4
[Thread 15] tick=2

此數值並不會完全固定，多執行幾次會發現些許差異。以上面的數值為例， `tick` 的總和是 $131070$ ，由於 `bit` 的關係，將之除以二得 $65535$ (即 $2^{16} - 1$) ，再加上第 `39` 行的 `clock_tick()` ，這樣就達到第 `40` 行的通行條件 $2^{16}$ 了。

### Linux 針對 POSIX Threads 強化 futex 相關實作機制

(消化中)
> [In pursuit of faster futexes](https://lwn.net/Articles/685769/) \
> [Adaptive mutexes in user space](https://lwn.net/Articles/704843/) \
> [Rethinking the futex API](https://lwn.net/Articles/823513/) \
> [Short subjects: Realtime, Futexes, and ntfs3](https://lwn.net/Articles/866112/) \
> [1½ Topics: realtime throttling and user-space adaptive spinning](https://lwn.net/Articles/931789/) \
> [A new futex API](https://lwn.net/Articles/940944/)

## 延伸問題 `1`−2
> [aaa7016](https://github.com/NOVBobLee/sysprog202308/commit/aaa7016718ace9872e8534bd4bace239f0d9e0f7)

精簡版 POSIX Thread 與 POSIX Thread 使用上有幾個差異:

1. POSIX Thread 的函式會回傳 `int` ，精簡版的則沒有回傳值。
2. POSIX Thread 的物件需要使用 `destory()` ，精簡版的則不需要。
3. POSIX Thread 的 `pthread_cond_signal()` 和 `pthread_cond_broadcast()` 參數只有 condvar ，精簡版則需多加 mutex 。

#include "cond.h"
#include "mutex.h"

加入精簡版 POSIX Thread 函式庫。

@@ -91,8 +94,8 @@ struct qsort {
     void *a;                /* Array base. */
     size_t n;               /* Number of elements. */
     pthread_t id;           /* Thread id. */
-    pthread_mutex_t mtx_st; /* For signalling state change. */
-    pthread_cond_t cond_st; /* For signalling state change. */
+    mutex_t mtx_st;                    /* For signalling state change. */
+    cond_t cond_st;                    /* For signalling state change. */
 };

替換成精簡版 POSIX Thread 物件。

@@ -163,31 +160,28 @@ void qsort_mt(void *a,

    /* Hand out the first work batch. */
    qs = &c.pool[0];
-   verify(pthread_mutex_lock(&qs->mtx_st));
+   mutex_lock(&qs->mtx_st);
    qs->a = a;
    qs->n = n;

@@ -127,23 +130,17 @@ void qsort_mt(void *a,
         goto f1;
     errno = 0;
     /* Try to initialize the resources we need. */
-    if (pthread_mutex_init(&c.mtx_al, NULL) != 0)
-        goto f1;
+    mutex_init(&c.mtx_al);
     if ((c.pool = calloc(maxthreads, sizeof(struct qsort))) == NULL)
         goto f2;

初始化函式替換成精簡版的，將回傳值處理的部份去掉。

@@ -127,23 +130,17 @@ void qsort_mt(void *a,
        qs->st = ts_idle;
        qs->common = &c;
        if (pthread_create(&qs->id, NULL, qsort_thread, qs) != 0) {
-           verify(pthread_mutex_destroy(&qs->mtx_st));
-           verify(pthread_cond_destroy(&qs->cond_st));
            goto f3;
        }
    }

`destroy()` 的部份直接捨棄掉。

## 延伸問題 `1`−3
在搶佔式系統中，當有高優先權的 process 是就緒狀態時，則可以搶佔低優先權 process ，讓高優先權 process 優先執行。現在假設一情況，有一低優先權的 process 正在處理 CS (Critical Sectoin) 時被搶佔，高優先權 process 開始執行自己的工作，然後準備進入同一個 CS ，此時 lock 的所有權還是在原本的低優先權 process 手上，為了不破壞 CS ，會轉讓給擁有 lock 的低優先權 process 優先執行，此時即構成了 Priority Inversion 。


> 圖片來源: [Introduction to RTOS - Solution to Part 11 (Priority Inversion)](https://www.digikey.tw/en/maker/projects/introduction-to-rtos-solution-to-part-11-priority-inversion/abf4b8f7cd4a4c70bece35678d178321)

對應 Priority Inversion 的解法有許多種，其中之一為 PI (Priority Inheritance) 。當一高優先權 process 試圖取得 lock ，但擁有者為低優先權 process 時，會暫時性的將低優先權 process 的優先權暫時提昇成高優先權 process 的優先權，以防止其他不低於高優先權的 process 搶佔。等 lock 釋放後，才將優先權還原。

> [Priority inheritance in the kernel](https://lwn.net/Articles/178253/)

### 設計實驗
執行緒預設使用的排程器是 `SCHED_OTHER` ，其優先度永遠只有 `0` 。實驗需要使用到優先度，這部分需要指定其他排程器，比方說　`SCHED_FIFO` 和 `SCHED_RR` ，優先度從 `1` 到最大 `99` ，可以在　`pthread_create()` 指定執行緒排程方式和優先度。要注意的是使用 `SCHED_OTHER` 的優先度 `0` 永遠低於 `SCHED_FIFO` 和 `SCHED_RR` 的 `1` 到 `99` 。

## check the min/max priority w.r.t. the real-time policies
$ 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

> [sched(7)](https://man7.org/linux/man-pages/man7/sched.7.html) \
> [22.3 Process CPU Priority And Scheduling](https://www.gnu.org/software/libc/manual/html_node/Priority.html)


> 圖片來源: [Introduction to RTOS - Solution to Part 11 (Priority Inversion)](https://www.digikey.tw/en/maker/projects/introduction-to-rtos-solution-to-part-11-priority-inversion/abf4b8f7cd4a4c70bece35678d178321)

目標實驗情境是: 在沒有使用 PI 的情況下，會發生 Priority Inversion (如前一個示意圖) ，所以 `task_h` 會比 `task_m` 晚完成。而若是在使用 PI 的情況下，則不會發生 Priority Inversion ，執行緒完成順序會是按照優先度高到低的順序完成 (如上圖) 。

實驗中我們會限制執行在一個處理器上，簡化實驗易於觀察。使用的排程器為 `SCHED_FIFO` 。總共會創造三個執行緒，執行緒優先度由低到高分別為 `task_l` 、 `task_m` 、 `task_h` 。 `task_l` 跟 `task_h` 會使用同一個 CS ，而 `task_m` 則是單純占用處理器，流程會像 Priority Inversion 示意圖那樣，剛開始由 `task_l` 先進入 CS 並佔據，然後放 `task_m` 和 `task_h` 運行，觀察執行緒完成的順序，還有 `task_h` 進入 CS 的時間點。

static void *task_l(void *arg)
{
    struct ctx *ctx = (struct ctx *) arg;
    struct cs *cs = &ctx->cs;
    struct state *st = &ctx->st;

    mutex_lock(&cs->lock);

    /* wake other tasks if they are waiting for task_l acquired lock */
    store(&st->l_locked, 1, release);
    futex_wake(&st->l_locked, N_TASKS);

    /* yield after all tasks are created */
    while (!load(&st->all_created, acquire))
        spin_hint();
    sched_yield();

    mutex_unlock(&cs->lock);

    task_finished(st, TASK_L);
    return NULL;
}

此執行緒為最低優先度，為了達成 Priority Inversion ，必須讓此執行緒比 `task_h` 早取得 mutex 進入 CS ，目的是讓低優先度執行緒占用 mutex ，以觀察其他執行緒對此執行緒的行為，比方說在沒有使用 PI 的情況下，此執行緒會被 `task_m` 搶佔，相反地，在有使用 PI 的情況下，由於優先度被拉升到跟 `task_h` 一樣，使得此執行緒不會被搶占。

:::info
Make sure `task_l` use `sched_yield()` after at least one thread is created, or `task_l` cannot yield and finishes first.
:::

static void *task_m(void *arg)
{
    struct ctx *ctx = (struct ctx *) arg;
    struct state *st = &ctx->st;

    /* wait until task_l acquired lock */
    if (0 == load(&st->l_locked, acquire))
        futex_wait(&st->l_locked, 0);

    while (!load(&st->stop, relaxed))
        spin_hint();

    task_finished(st, TASK_M);
    return NULL;
}

此執行緒單純占用處理器，直到主執行緒說停 (主執行緒 `main` 在實驗結束時會改變 `stop` 的狀態) ，由於優先度在中間，在有和沒有使用 PI 的情況下，其搶佔行為會是觀察 Priority Inversion 的關鍵。

:::info
We simplify the experiment by using one CPU with one blocking task `task_m`. You can use multiple CPUs by using `N` CPUs with `N` blocking tasks `task_m` instead.
:::

static void *task_h(void *arg)
{
    struct ctx *ctx = (struct ctx *) arg;
    struct cs *cs = &ctx->cs;
    struct state *st = &ctx->st;

    /* wait until task_l acquired lock */
    if (0 == load(&st->l_locked, acquire))
        futex_wait(&st->l_locked, 0);

    mutex_lock(&cs->lock);

    /* if task_m, task_l are still runnable */
    if (!load(&st->stop, acquire))
        cs->h_touched = true;

    mutex_unlock(&cs->lock);

    task_finished(st, TASK_H);
    return NULL;
}

此執行緒與 `task_l` 共用 CS ，但由於 `task_l` 先進入 CS 的關係，所以會在爭取 mutex 失敗後進入睡眠的狀態，此時剩下 `task_l` 與 `task_m` 可以執行，在沒有使用 PI 的情況下，會由 `task_m` 開始執行，只要 `task_m` 還沒執行完，優先度較低的 `task_l` 就沒有機會去釋放 mutex ，導致 `task_h` 無法在 `task_m` 可執行的狀態下進入 CS ，第 `15` 行的 `h_touched` 也就不會碰到。相反地，在有使用 PI 的情況下， `task_m` 是無法搶佔暫時性高優先度的 `task_l` ，所以可以在 `task_m` 可執行的狀態下釋放 mutex ，進而讓 `task_h` 進入 CS 碰到第 `15` 行。

void task_finished(struct state *st, enum task_idx idx)
{
    int order = fetch_add(&st->n_finished, 1, acquire);
    st->finished_order[idx] = order;
}

每個執行緒完成時都會執行 `task_finished()` ，紀錄自己執行緒執行完成的順位。

## only run on #0 CPU
$ sudo sh -c "taskset -c 0 ./test_pthread"

由於要指定執行緒排程和優先度，所以需要 root 權限，使用 `taskset` 限制運行於某處理器，這裡指定在 `0` 號處理器。

> [shced(7)](https://man7.org/linux/man-pages/man7/sched.7.html#:~:text=Privileges%20and%20resource%20limits) See Privileges and resource limits

以下結果為使用的是 glibc 的 pthread 。

## no PI
$ sudo sh -c "taskset -c 0 ./test_pthread"
TASK_L: #2 finished
TASK_M: #0 finished
TASK_H: #1 finished
h_touched: false

這是沒有使用 PI 的結果，執行緒完成的順序為 `task_m` > `task_h` > `task_l` ，結果符合預期，有發生 Priority Inversion 。

以結果來推測過程:

1. `task_l` 取得 mutex 進入 CS
2. `task_l` 讓出處理器或是被搶占， `task_m` 或 `task_h` 開始執行
3. 若 `task_m` 在執行中，則被 `task_h` 搶佔
4. `task_h` 爭取 mutex 失敗，進入睡眠狀態
5. `task_m` 或主執行緒 `main` 開始執行
6. 若 `task_m` 在執行中，則被主執行緒 `main` 從睡眠狀態中醒來 (時間到) 搶佔
7. 主執行緒 `main` 給予停止值 `stop = true` ，然後等待子執行緒返回
8. `task_m` 優先度較高，開始執行
9. `task_m` 離開迴圈，記錄返回順序 `task_finished()`
10. `task_h` 還在睡眠中，由 `task_l` 開始執行
11. `task_l` 釋放 mutex ，喚醒 `task_h`
12. `task_h` 優先度較高，搶佔 `task_l`
13. `task_h` 進入 CS ，但 `task_m` 已執行結束，所以不會更改 `h_touched` 值
14. `task_h` 釋放 mutex ，記錄返回順序 `task_finished()`
15. `task_l` 開始執行，記錄返回順序 `task_finished()`

## use PI
$ sudo sh -c "taskset -c 0 ./test_pthread"
TASK_L: #2 finished
TASK_M: #1 finished
TASK_H: #0 finished
h_touched: true

這是有使用 PI 的結果
執行緒完成的順序為 `task_h` > `task_m` > `task_l` ，結果符合預期。

以結果推測過程:

1. 接續上面 4. `task_h` 爭取 mutex 失敗，進入睡眠狀態
2. `task_l` 提升優先度，與 `task_h` 相同
3. `task_l` 優先度高於 `task_m` ，所以由 `task_l` 開始執行
4. `task_l` 釋放 mutex ，還原優先度，喚醒 `task_h`
5. `task_h` 優先度最高，搶佔 `task_l`
6. `task_h` 進入 CS ，此時 `task_m` 尚未執行結束，所以會更改 `h_touched` 值
7. `task_h` 釋放 mutex ，記錄返回順序 `task_finished()`
8. 主執行緒 `main` 或 `task_m` 執行
9. 過程略 (同上面 6. 7.)
10. `task_m` 離開迴圈，記錄返回順序 `task_finished()`
11. `task_l` 開始執行，記錄返回順序 `task_finished()`

### 實作 PI-mutex
這裡我們會使用 Linux 的 PI-futex 系統呼叫，過程大概都是若在 user space 使用 atomic 操作爭取 lock 失敗時，就會使用 kernel 的 RT-mutex 實作 PI 的次系統。

對於 PI 機制， futex 有提供相關的操作: `FUTEX_LOCK_PI`, `FUTEX_TRYLOCK_PI`, `FUTEX_UNLOCK_PI` 等，其字尾會用 PI ，其用法也有特殊的規定:

1. 當 lock 沒有執行緒取得時，則 futex 應設為 `0` 。
2. 當 lock 被某執行緒取得時，則 futex 應設為該執行緒的 ID (TID, Thread ID) 。
3. 當 lock 被某執行緒取得，且有其他執行緒也在爭取 (等待) 這個 lock 時，則 kernel 會幫 futex 加上 `FUTEX_WAITERS` bit ，變成 `FUTEX_WAITERS | TID` 。這個情況表示，在釋放 lock 的時候，不能只在 user space 裡釋放 (將 futex 改為 `0` ) ，而必須使用系統呼叫，請 kernel 去做釋放 lock 與後續的動作。

相關 PI-futex 操作:

1. `FUTEX_LOCK_PI`: 在 user space 爭取 lock 失敗時 ( futex 不等於 `0` ) 使用。
2. `FUTEX_TRYLOCK_PI`: 由於 lock 處於 stale state ( futex 有 `FUTEX_WAITERS` 或 `FUTEX_OWNER_DIED` bit) ，此時 futex 不能單純於 user space 處理，必須交由 kernel 來執行 trylock 。如此情況像是 lock 的擁有者執行緒終止且尚未釋放，此時可以由 kernel 當中間人，讓其他執行緒取得 lock 。其他情況像是偷取 lock 的功能， PI-mutex 會有自己的優先度佇列，取得 lock 的順序會依照優先度高排到低，此時若使用 `FUTEX_TRYLOCK_PI` 的執行緒與原下一順位的執行緒有著一樣的優先度，且下一順位的執行緒尚未取得 lock 時，則可以偷取 lock 。

#define STALE_STATE (FUTEX_WAITERS | FUTEX_OWNER_DIED)

3. `FUTEX_UNLOCK_PI`: 在 user space 無法釋放 lock 時使用 (futex 不等於 TID ，可能有 `FUTEX_WAITERS` bit) ，此操作將會釋放 lock 並喚醒位於等待佇列中最高優先權的執行緒。

> [Lightweight PI-futexes](https://docs.kernel.org/locking/pi-futex.html) \
> [futex(2)](https://man7.org/linux/man-pages/man2/futex.2.html#:~:text=inheritance)

> [9cb26ea](https://github.com/NOVBobLee/sysprog202308/commit/9cb26eae4e117d6698eae6c212fad9024505c143) \
> [e1e5444](https://github.com/NOVBobLee/sysprog202308/commit/e1e544470904c6a9fad0556a718b9e0427699173) Fix thread fence in `mutex_unlock_pi()`

static bool _mutex_trylock_pi(mutex_t *mutex)
{
    pid_t tid = gettid();
    int zero = 0;

    if (compare_exchange_strong(&mutex->state, &zero, tid, acquire, relaxed))
        return true;

    if (load(&mutex->state, relaxed) & STALE_STATE) {
        if (0 == futex_trylock_pi(&mutex->state)) {
            thread_fence(&mutex->state, acquire);
            return true;
        }
    }

    return false;
}

有兩次爭取 lock 的機會，一次在 user space ，就一般的 atomic CAS 操作，若 `state` 等於 `0` ，則改成自己的執行緒 ID `tid` ，表示取得成功。另一次在 kernel space ，由於處於 stale state ，必須請 kernel 來爭取 lock 。

/* Specified for _mutex_lock_pi() using */
static bool _mutex_trylock_pi_loop(mutex_t *mutex)
{
    int zero = 0;
    pid_t tid = gettid();

    /* cheaper than compare_exchange() ? */
    if (0 != load(&mutex->state, acquire))
        return false;

    /* loop exists in _mutex_lock_pi() */
    return compare_exchange_weak(&mutex->state, &zero, tid, acquire, relaxed);
}

static inline void _mutex_lock_pi(mutex_t *mutex)
{
    int state = load(&mutex->state, relaxed);

    /* Need futex (kernel) when it contains stale state */
    if (state & STALE_STATE)
        goto FAILED;

    for (int i = 0; i < MUTEX_SPINS; ++i) {
        if (_mutex_trylock_pi_loop(mutex))
            return;
        spin_hint();
    }

FAILED:
    futex_lock_pi(&mutex->state);

    thread_fence(&mutex->state, acquire);
}

`_mutex_lock_pi()` 會先在 user space 嘗試爭取 lock ，失敗時呼叫 futex ，若在 kernel space 爭取到 lock 則會馬上回到 user space ，否則進入睡眠狀態，等待 lock 釋放時，照優先度的順序被喚醒。

`_mutex_trylock_pi_loop()` 由於是處於 loop 中，所以使用的 CAS 是 `compare_exchange_weak()` ，速度較快，相對地有可能出現偽錯，這可以靠 loop 彌補。

在 `_mutex_lock_pi()` 剛開始會檢測是否處於 stale state，若看到 `FUTEX_OWNER_DIED` 那一定需要 kernel 處理。另一方面，若看到 `FUTEX_WAITERS` ，則代表除了 lock 擁有者，還有其他執行緒在等待這個 lock ，這邊是否也是要偵測到直接呼叫 futex ，或是可以放寬，偵測到一樣先在 user space 爭取看看?

:::warning
Is there cache line bouncing problem for using CAS? \
Experiment: Use `perf` and compare the cache missing.

> [Chapter 26. Detecting false sharing](https://access.redhat.com/documentation/en-us/red_hat_enterprise_linux/8/html/monitoring_and_managing_system_status_and_performance/detecting-false-sharing_monitoring-and-managing-system-status-and-performance)
:::

> [Does cmpxchg write destination cache line on failure? If not, is it better than xchg for spinlock?](https://stackoverflow.com/questions/63008857/does-cmpxchg-write-destination-cache-line-on-failure-if-not-is-it-better-than) \
> [Understanding std::atomic::compare_exchange_weak() in C++11](https://stackoverflow.com/questions/25199838/understanding-stdatomiccompare-exchange-weak-in-c11)

static inline void _mutex_unlock_pi(mutex_t *mutex)
{
    pid_t tid = gettid();

    if (compare_exchange_strong(&mutex->state, &tid, 0, release, relaxed))
        return;

    /* Need futex (kernel) when it contains FUTEX_WAITERS */
    futex_unlock_pi(&mutex->state);
    thread_fence(&mutex->state, release);
}

先在 user space 嘗試釋放，若失敗則使用 futex 呼叫，這代表有 `FUTEX_WAITERS` bit ，需要 kernel 進一步處理。

### 測試結果
測試結果與使用 glibc 的 pthread 相同。

> [Requeue-PI: Making Glibc Condvars PI-Aware](https://static.lwn.net/images/conf/rtlws11/papers/proc/p10.pdf) \
> [Android Audio System: Avoiding priority inversion](https://source.android.com/docs/core/audio/avoiding_pi?hl=en)

## 延伸問題 `1`−4
`perf.c` 中有兩種對 mutex 的效能測試，一種是在沒有競爭的情況下，測試 `lock()` 和 `unlock()` 的時間。而另一種則是在競爭情況下，測試 `lock()` 與 `unlock()` 的時間，其中競爭的方式以下面圖示: 由 4 個執行緒競爭 5 個 mutex ，這邊可以想像 mutex 是一個有序的環狀，最初每一個執行緒會持有一個 mutex (藍線)，第一個動作是先` lock()` 下一個 mutex (紅虛線)，第二個動作在 mutex 得到後 `unlock()` 自己原本持有的 mutex (紅虛線)，每個執行緒都反覆這兩個動作 `25000` 次。

digraph {
    layout="circo";
    overlap="false";
    splines="polylines";

    node [shape=record, color=black] m0, m1, m2, m3, m4;
    node [shape=circle, color=red] t0, t1, t2, t3;

    m4 [label="M4"];
    m3 [label="M3"];
    m2 [label="M2"];
    m1 [label="M1"];
    m0 [label="M0"];

    m0 -> m1 [style=dotted, dir=none];
    m1 -> m2 [style=dotted, dir=none];
    m2 -> m3 [style=dotted, dir=none];
    m3 -> m4 [style=dotted, dir=none];
    m4 -> m0 [style=dotted, dir=none];

    t3 [label="T3"];
    t2 [label="T2"];
    t1 [label="T1"];
    t0 [label="T0"];

    t0 -> m0 [color=blue];
    t1 -> m1 [color=blue];
    t2 -> m2 [color=blue];
    t3 -> m3 [label="", color=blue];

    t3 -> m4 [label="1. lock()", color=red, style=dashed];
    m3 -> t3 [label="2. unlock()", color=red, style=dashed];
}

從圖示可以看出執行緒與 mutex 間爭取的樣貌會是環狀的，此為一種「可能」發生 deadlock 的情況，所以 TSan 有時候會給出潛在 deadlock 的警告。不過實際上，這段程式並不會發生 deadlock ，由於 mutex 數量是比執行緒數量多一，這可以保證至少一個執行緒 `lock()` 是不會失敗的，然後此一執行緒在 `unlock()` 後，又會喚醒原本 `lock()` 失敗的執行緒，致使整個流程是一直有進展的。

$ sudo sh -c "taskset -c 0,1 ./perf_pthread"
==================
WARNING: ThreadSanitizer: lock-order-inversion (potential deadlock) (pid=3054)
  Cycle in lock order graph: M0 (0x7ffc510e3080) => M1 (0x7ffc510e30a8) => M2 (0x7ffc510e30d0) => M3 (0x7ffc510e30f8) => M4 (0x7ffc510e3120) => M0

  Mutex M1 acquired here while holding mutex M0 in thread T1:
    #0 pthread_mutex_lock /usr/src/debug/gcc/gcc/libsanitizer/sanitizer_common/sanitizer_common_interceptors.inc:4481 (libtsan.so.2+0x560df) (BuildId: 7e8fcb9e
d0a63b98f2293e37c92ac955413efd9e)
    #1 contention_thread /home/zz4t/test/sysporg-linux2023/quiz1/perf/perf.c:121 (perf_pthread+0x1d94) (BuildId: f3b7cbb69e4329f2b3b685b3d2ac1ab0e90394e0)

    Hint: use TSAN_OPTIONS=second_deadlock_stack=1 to get more informative warning message

  Mutex M2 acquired here while holding mutex M1 in thread T2:
    #0 pthread_mutex_lock /usr/src/debug/gcc/gcc/libsanitizer/sanitizer_common/sanitizer_common_interceptors.inc:4481 (libtsan.so.2+0x560df) (BuildId: 7e8fcb9e
d0a63b98f2293e37c92ac955413efd9e)
    #1 contention_thread /home/zz4t/test/sysporg-linux2023/quiz1/perf/perf.c:121 (perf_pthread+0x1d94) (BuildId: f3b7cbb69e4329f2b3b685b3d2ac1ab0e90394e0)

  Mutex M3 acquired here while holding mutex M2 in thread T3:
    #0 pthread_mutex_lock /usr/src/debug/gcc/gcc/libsanitizer/sanitizer_common/sanitizer_common_interceptors.inc:4481 (libtsan.so.2+0x560df) (BuildId: 7e8fcb9e
d0a63b98f2293e37c92ac955413efd9e)
    #1 contention_thread /home/zz4t/test/sysporg-linux2023/quiz1/perf/perf.c:121 (perf_pthread+0x1d94) (BuildId: f3b7cbb69e4329f2b3b685b3d2ac1ab0e90394e0)

  Mutex M4 acquired here while holding mutex M3 in thread T4:
    #0 pthread_mutex_lock /usr/src/debug/gcc/gcc/libsanitizer/sanitizer_common/sanitizer_common_interceptors.inc:4481 (libtsan.so.2+0x560df) (BuildId: 7e8fcb9e
d0a63b98f2293e37c92ac955413efd9e)
    #1 contention_thread /home/zz4t/test/sysporg-linux2023/quiz1/perf/perf.c:121 (perf_pthread+0x1d94) (BuildId: f3b7cbb69e4329f2b3b685b3d2ac1ab0e90394e0)

  Mutex M0 acquired here while holding mutex M4 in thread T4:
    #0 pthread_mutex_lock /usr/src/debug/gcc/gcc/libsanitizer/sanitizer_common/sanitizer_common_interceptors.inc:4481 (libtsan.so.2+0x560df) (BuildId: 7e8fcb9e
d0a63b98f2293e37c92ac955413efd9e)
    #1 contention_thread /home/zz4t/test/sysporg-linux2023/quiz1/perf/perf.c:121 (perf_pthread+0x1d94) (BuildId: f3b7cbb69e4329f2b3b685b3d2ac1ab0e90394e0)

  Thread T1 (tid=3056, running) created by main thread at:
    #0 pthread_create /usr/src/debug/gcc/gcc/libsanitizer/tsan/tsan_interceptors_posix.cpp:1036 (libtsan.so.2+0x44219) (BuildId: 7e8fcb9ed0a63b98f2293e37c92ac9
55413efd9e)
    #1 contention /home/zz4t/test/sysporg-linux2023/quiz1/perf/perf.c:152 (perf_pthread+0x14aa) (BuildId: f3b7cbb69e4329f2b3b685b3d2ac1ab0e90394e0)
    #2 measure /home/zz4t/test/sysporg-linux2023/quiz1/perf/perf.c:214 (perf_pthread+0x1944) (BuildId: f3b7cbb69e4329f2b3b685b3d2ac1ab0e90394e0)
    #3 main /home/zz4t/test/sysporg-linux2023/quiz1/perf/perf.c:226 (perf_pthread+0x11dd) (BuildId: f3b7cbb69e4329f2b3b685b3d2ac1ab0e90394e0)

  Thread T2 (tid=3057, running) created by main thread at:
    #0 pthread_create /usr/src/debug/gcc/gcc/libsanitizer/tsan/tsan_interceptors_posix.cpp:1036 (libtsan.so.2+0x44219) (BuildId: 7e8fcb9ed0a63b98f2293e37c92ac9
55413efd9e)
    #1 contention /home/zz4t/test/sysporg-linux2023/quiz1/perf/perf.c:152 (perf_pthread+0x14aa) (BuildId: f3b7cbb69e4329f2b3b685b3d2ac1ab0e90394e0)
    #2 measure /home/zz4t/test/sysporg-linux2023/quiz1/perf/perf.c:214 (perf_pthread+0x1944) (BuildId: f3b7cbb69e4329f2b3b685b3d2ac1ab0e90394e0)
    #3 main /home/zz4t/test/sysporg-linux2023/quiz1/perf/perf.c:226 (perf_pthread+0x11dd) (BuildId: f3b7cbb69e4329f2b3b685b3d2ac1ab0e90394e0)

  Thread T3 (tid=3058, running) created by main thread at:
    #0 pthread_create /usr/src/debug/gcc/gcc/libsanitizer/tsan/tsan_interceptors_posix.cpp:1036 (libtsan.so.2+0x44219) (BuildId: 7e8fcb9ed0a63b98f2293e37c92ac9
55413efd9e)
    #1 contention /home/zz4t/test/sysporg-linux2023/quiz1/perf/perf.c:152 (perf_pthread+0x14aa) (BuildId: f3b7cbb69e4329f2b3b685b3d2ac1ab0e90394e0)
    #2 measure /home/zz4t/test/sysporg-linux2023/quiz1/perf/perf.c:214 (perf_pthread+0x1944) (BuildId: f3b7cbb69e4329f2b3b685b3d2ac1ab0e90394e0)
    #3 main /home/zz4t/test/sysporg-linux2023/quiz1/perf/perf.c:226 (perf_pthread+0x11dd) (BuildId: f3b7cbb69e4329f2b3b685b3d2ac1ab0e90394e0)

  Thread T4 (tid=3059, running) created by main thread at:
    #0 pthread_create /usr/src/debug/gcc/gcc/libsanitizer/tsan/tsan_interceptors_posix.cpp:1036 (libtsan.so.2+0x44219) (BuildId: 7e8fcb9ed0a63b98f2293e37c92ac9
55413efd9e)
    #1 contention /home/zz4t/test/sysporg-linux2023/quiz1/perf/perf.c:152 (perf_pthread+0x14aa) (BuildId: f3b7cbb69e4329f2b3b685b3d2ac1ab0e90394e0)
    #2 measure /home/zz4t/test/sysporg-linux2023/quiz1/perf/perf.c:214 (perf_pthread+0x1944) (BuildId: f3b7cbb69e4329f2b3b685b3d2ac1ab0e90394e0)
    #3 main /home/zz4t/test/sysporg-linux2023/quiz1/perf/perf.c:226 (perf_pthread+0x11dd) (BuildId: f3b7cbb69e4329f2b3b685b3d2ac1ab0e90394e0)

SUMMARY: ThreadSanitizer: lock-order-inversion (potential deadlock) /home/zz4t/test/sysporg-linux2023/quiz1/perf/perf.c:121 in contention_thread
==================

## 延伸問題 `2`−1
## 延伸問題 `2`−2
## 延伸問題 `2`−3
## 延伸問題 `2`−4
## 延伸問題 `3`−1
* Check cache line size

## index3 -> L3
$ cat /sys/devices/system/cpu/cpu0/cache/index3/coherency_line_size

## 延伸問題 `3`−2
## 延伸問題 `3`−3
## Reference
* [SeqCst as a default atomic ordering considered harmful #166](https://github.com/rust-lang/nomicon/issues/166)
* [What does memory_order_consume really do?](https://stackoverflow.com/a/65353549/16257547)