linux2023 - Homework2

contributed by <NOVBobLee>

GitHub
2023 年暑期 Linux 核心課程第 1 次測驗題
2023 年暑期 Linux 核心課程第 2 次測驗題

延伸問題 `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);

基本參數:

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

futex 操作 (futex_op) 敘述:

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

How does it prevent losing wake-ups?

FUTEX_WAKE: 喚醒屬於 uaddr 上 futex 的等待佇列中之執行緒 (沒有順序保證) ，最大數量為 val 。
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() 說明)

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

futex(2)
futex(7)
A description of what robust futexes are

精簡的 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 見 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) ，達到 de-pipeline 的效果，這在離開迴圈時可以避免掉分支預測錯誤的懲罰。

[PDF] Intel® 64 and IA-32 Architectures Optimization Reference Manual.pdf 見 11.4.2
Stalls and flushes - 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 ，以 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)
pthread_cond_broadcast(3p)

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);

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`

測試方式採多執行緒互相以 condvar 溝通，最終檢查交由 TSan 與 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() 就是提供暫時煞車的功能，使得每個子執行緒運行在不超過自己該有的步調上。

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;
}

程式的運行概述:

第 35 行各子執行緒開始運行，若親執行緒尚未執行第 39 行，則於第 6 行 clock_wait() 等待
第 39 行親執行緒呼叫 clcok_tick() ，使各子執行緒通過 clock_wait() ，然後親執行緒在第 40 行 clock_wait() 等待

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

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

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

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

b04690f (主要: 印出各執行緒最終迴圈 i 數值)
0c4fb1b (修改 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
Adaptive mutexes in user space
Rethinking the futex API
Short subjects: Realtime, Futexes, and ntfs3
1½ Topics: realtime throttling and user-space adaptive spinning
A new futex API

延伸問題 `1`−2

aaa7016

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

POSIX Thread 的函式會回傳 int ，精簡版的則沒有回傳值。
POSIX Thread 的物件需要使用 destory() ，精簡版的則不需要。
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)

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

Priority inheritance in the kernel

設計實驗

執行緒預設使用的排程器是 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)
22.3 Process CPU Priority And Scheduling

圖片來源: Introduction to RTOS - Solution to Part 11 (Priority Inversion)

目標實驗情境是: 在沒有使用 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 一樣，使得此執行緒不會被搶占。

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 的關鍵。

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) 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 。

以結果來推測過程:

task_l 取得 mutex 進入 CS
task_l 讓出處理器或是被搶占， task_m 或 task_h 開始執行
若 task_m 在執行中，則被 task_h 搶佔
task_h 爭取 mutex 失敗，進入睡眠狀態
task_m 或主執行緒 main 開始執行
若 task_m 在執行中，則被主執行緒 main 從睡眠狀態中醒來 (時間到) 搶佔
主執行緒 main 給予停止值 stop = true ，然後等待子執行緒返回
task_m 優先度較高，開始執行
task_m 離開迴圈，記錄返回順序 task_finished()
task_h 還在睡眠中，由 task_l 開始執行
task_l 釋放 mutex ，喚醒 task_h
task_h 優先度較高，搶佔 task_l
task_h 進入 CS ，但 task_m 已執行結束，所以不會更改 h_touched 值
task_h 釋放 mutex ，記錄返回順序 task_finished()
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 ，結果符合預期。

以結果推測過程:

接續上面 4. task_h 爭取 mutex 失敗，進入睡眠狀態
task_l 提升優先度，與 task_h 相同
task_l 優先度高於 task_m ，所以由 task_l 開始執行
task_l 釋放 mutex ，還原優先度，喚醒 task_h
task_h 優先度最高，搶佔 task_l
task_h 進入 CS ，此時 task_m 尚未執行結束，所以會更改 h_touched 值
task_h 釋放 mutex ，記錄返回順序 task_finished()
主執行緒 main 或 task_m 執行
過程略 (同上面 6. 7.)
task_m 離開迴圈，記錄返回順序 task_finished()
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 ，其用法也有特殊的規定:

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

相關 PI-futex 操作:

FUTEX_LOCK_PI: 在 user space 爭取 lock 失敗時 ( futex 不等於 0 ) 使用。
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)

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

Lightweight PI-futexes
futex(2)

9cb26ea
e1e5444 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 爭取看看?

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

Chapter 26. Detecting false sharing

Does cmpxchg write destination cache line on failure? If not, is it better than xchg for spinlock?
Understanding std::atomic::compare_exchange_weak() in C++11

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
Android Audio System: Avoiding priority inversion

延伸問題 `1`−4

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

從圖示可以看出執行緒與 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

linux2023 - Homework2

延伸問題 `1`−1

futex 整理

精簡的 POSIX Thread 實作摘錄

測試程式 `main.c`

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

延伸問題 `1`−2

延伸問題 `1`−3

設計實驗

實作 PI-mutex

測試結果

延伸問題 `1`−4

延伸問題 `2`−1

延伸問題 `2`−2

延伸問題 `2`−3

延伸問題 `2`−4

延伸問題 `3`−1

延伸問題 `3`−2

延伸問題 `3`−3

Reference

linux2023 - Homework2

延伸問題 1−1

futex 整理

精簡的 POSIX Thread 實作摘錄

測試程式 main.c

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

延伸問題 1−2

延伸問題 1−3

設計實驗

實作 PI-mutex

測試結果

延伸問題 1−4

延伸問題 2−1

延伸問題 2−2

延伸問題 2−3

延伸問題 2−4

延伸問題 3−1

延伸問題 3−2

延伸問題 3−3

Reference

Read more

SSH with Pem File

Logitech Gaming Mouse - G102 LightSync

Acer EFI Booting Problem

linux2023 - Homework3

延伸問題 `1`−1

測試程式 `main.c`

延伸問題 `1`−2

延伸問題 `1`−3

延伸問題 `1`−4

延伸問題 `2`−1

延伸問題 `2`−2

延伸問題 `2`−3

延伸問題 `2`−4

延伸問題 `3`−1

延伸問題 `3`−2

延伸問題 `3`−3