Try   HackMD

2023 Homework2 (quiz1)

contributed by <doodoodog>
題目: 2023_sumer_quiz1

Homework2 quiz 1-1

解釋上述程式碼運作原理，應該涵蓋測試方法、futex 使用方式、Linux 核心開發者針對 POSIX Threads 強化哪些相關 futex 實作機制等等

程式碼運作原理

此程式碼的目的是在 Multi-Thread 的情況下能滿足所有 Task 能夠按順序完成。(範例 : 如果要執行 Task 3 就必須先執行 Task 2，如果要執行 Task 2 就必須先執行 Task 1 以此類推)。

在沒有 parent node 的情況下：

  1. 在 node 0 從clock_wait()中喚醒後因為沒有 parent node 存在。









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;
}
  1. 會做clock_tick()透過cond_broadcast()喚醒所有等待在 condvar 上的執行緒。








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);
}
  1. 並且 node 0 會進入到競爭 condvar 的狀態。
  2. 成功拿到 condvar 後便可以用node_signal()來喚醒 node 0 獲取 mutex lock。
wakeup node : 0
node run : 0
...
tick (i : 1, clock ticks : 2) node : 0, cnt : 1
wakeup node : 0
node run : 0
signal (i : 2, clock ticks : 2) node : 0, cnt : 1

在有 parent node 的情況下：

  1. 在 node 1 從clock_wait()中喚醒後因為存在 parent node 1。


if (self->parent)
    node_wait(self->parent);
  1. 為了確保 node 0 執行在 node 1 前面，這邊回先把 node 0 狀態設成 not ready。








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);
}
  1. 做clock_tick()透過cond_broadcast()喚醒所有等待在 condvar 上的執行緒，並且進入到競爭 condvar 等狀態等待 node 0 完成。
  2. node 0 再次從clock_wait()中喚醒後會先做clock_tick()透過cond_broadcast()喚醒等待在 condvar 上的執行緒。
  3. node 0 拿到 condvar 後便可以透過node_signal()來喚醒 node 0 獲得 mutex lock。
  4. 這邊已經確定 node 0 執行完畢後 node 1 便會跳出node_wait()並且透過node_signal()來喚醒 node 1 獲得 mutex lock
wakeup node : 1
node : 1, wait parent : 0
...
node : 0 rdy 1 -> 0
node run : 1
tick (i : 1, clock : 3) node : 1, cnt : 1
wakeup node : 1
node : 1, wait parent : 0
...
wakeup node : 0
node run : 0
tick (i : 3, clock : 4) node : 0, cnt : 2
wakeup node : 0
node run : 0
signal (i : 4, clock : 4) node : 0, cnt : 2
node : 0 rdy 1 -> 0
...
node run : 1
signal (i : 2, clock : 4) node : 1, cnt : 1

futex

介紹

futex 允許在最低程度的 Linux 核心參與，達到執行緒之間的同步。futex 的操作幾乎全部在使用者空間完成；只有當操作結果不一致從而需要仲裁時，才需要進入作業系統核心空間執行。這讓以 futex 為基礎的 lock 得高效進行：由於絕大多數的操作並不需要在多個行程之間進行仲裁，所以絕大多數操作都可以在應用程式空間執行，而不需要使用（相對高代價的）核心系統呼叫。

使用方式

futex_wait

futex_wait 透過 System Call 在 User Spacee 來完成 sleep lock 的功能，sleep lock 與 busy lock 差異在於 sleep lock 在等待過程中不會占用 CPU 資源。
FUTEX_WAIT_PRIVATE 用 bit 來表示 futex 的屬性代表是 wait and non-share

#define FUTEX_WAIT_PRIVATE	(FUTEX_WAIT | FUTEX_PRIVATE_FLAG)






/* Atomically check if '*futex == value', and if so, go to sleep */
static inline void futex_wait(atomic int *futex, int value)
{
    syscall(SYS_futex, futex, FUTEX_WAIT_PRIVATE, value, NULL);
}

mutex_trylock

透過 atomic_load_explicit 來檢查是否被上鎖，再用 atomic_fetch_or_explicit 嘗試上鎖。














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

mutex_lock

在 mutex_trylock 失敗後，這邊會短暫 Spin 來嘗試 mutex_trylock 目的是如果很快就可以拿到 lock 就不用進入 sleep(避免執行緒太頻繁進入到 sleep stage)。最後才會讓執行緒進入 sleep 等待 lock 資源。



















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

futex_wake

futex_wake 透過 System Call 來喚醒因為沒有搶到 futex_wait 而進入睡眠的執行緒






/* Wake up 'limit' threads currently waiting on 'futex' */
static inline void futex_wake(atomic int *futex, int limit)
{
    syscall(SYS_futex, futex, FUTEX_WAKE_PRIVATE, limit);
}

mutex_unlock

執行緒在完成任務後需要釋放 lock，透過 futex_wake 系統呼叫來喚醒陷入沉睡在等待 lock 資源的執行緒 limit = 1 表示只有一個 lock 資源被釋放。







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

futex_requeue

futex_requeue 喚醒所有等待在 condvar 上的執行緒。limit 表示釋放的資源數量 INT_MAX 表示喚醒多少執行緒來競爭。








/* Wake up 'limit' waiters, and re-queue the rest onto a different futex */
static inline void futex_requeue(atomic int *futex,
                                 int limit,
                                 atomic int *other)
{
    syscall(SYS_futex, futex, FUTEX_REQUEUE_PRIVATE, limit, INT_MAX, other);
}

cond_broadcast 避免浪費喚醒操作所導致的執行緒切換，可以呼叫一次來減少競爭 mutex lock 的次數。






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

Homework2 quiz 1-2

修改第 1 次作業的測驗 γ 提供的並行版本快速排序法實作，使其得以搭配上述 futex 程式碼運作

完整 程式碼。效能比較：

pthread futex
Run Time 15.9s 10.4

Homework2 quiz 1-3

研讀〈並行程式設計: 建立相容於 POSIX Thread 的實作〉，在上述程式碼的基礎之上，實作 priority inheritance mutex 並確認與 glibc 實作行為相同，應有對應的 PI 測試程式碼

完整 程式碼。

































static inline void futex_lock_pi(atomic int *futex, struct timespec *timeout)
static inline bool mutex_trylock_pi(mutex_t *mutex)
{
    pid_t zero = 0;
    pid_t tid = GETTID;

    if (cmpxchg(&mutex->state, &zero, tid))
        return true;

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

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

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

static inline void mutex_unlock_pi(mutex_t *mutex) {
    pid_t tid = GETTID;
    if(cmpxchg(&mutex->state, &tid, 0))
        return;
    futex_unlock_pi(&mutex->state);
}










static inline void futex_lock_pi(atomic int *futex, struct timespec *timeout)
{
    syscall(SYS_futex, futex, FUTEX_LOCK_PI_PRIVATE, 0, timeout);
}

static inline void futex_unlock_pi(atomic int *futex)
{
    syscall(SYS_futex, futex, FUTEX_UNLOCK_PI_PRIVATE);
}

實際優先權是 T1 > T2 > T3，執行順序 T3 → T2 → T1。以下做兩種實測，T3、T1 持有 Lock1，T2 持有 Lock2：

Normal mutex - 發生 Priority Inversion (9 / 10) :

  1. T3 獲得 CPU 資源且拿到 Lock1 後，進入 sleep 並讓出 CPU 資源。
  2. T2 獲得 CPU 資源且拿到 Lock2 後，進入 sleep 並讓出 CPU 資源。
  3. T1 獲得 CPU 資源但因為 Lock1 被 T3 持有，所以進入 wait。
  4. T3 wake up 插入 runqueue 同時 T2 wake up 也插入 runqueue，T2 發現 T3 Priority 比較低 Preempt T3 獲得 CPU 資源。
  5. T3 等待 T2 完成並釋放 Lock1 和 CPU 資源。
  6. T1 獲得 CPU 資源且拿到 Lock1。 (Occur priority inversion)

Priority Inheritance mutex - 發生 Priority Inversion (0 / 10) :

  1. T3 獲得 CPU 資源且拿到 Lock1 後，進入 sleep 並讓出 CPU 資源。
  2. T2 獲得 CPU 資源且拿到 Lock2 後，進入 sleep 並讓出 CPU 資源。
  3. T1 獲得 CPU 資源但因為 Lock1 被 T3 持有，所以進入 wait 此時發現 T3 priority 比 T1 低，調整 T3 priority 和 T1 相同。
  4. T3 wake up 插入 runqueue 同時 T2 wake up 也插入 runqueue，T2 發現 T3 priority 比較高等待 T3 釋放 CPU 資源。
  5. T3 完成後釋放 CPU 資源和 Lock1，同時 wakeup T1 此時 T1 有策略上最高的 priority。
  6. T2 和 T1 同時插入 runqueue，因 T1 有較高的 priority 所以 preempt T2 CPU 資源。
  7. T2 等待 T1 完成後，取得 CPU 資源。

Homework2 quiz 1-4

比照 skinny-mutex，設計 POSIX Threads 風格的 API，並利用內附的 perf.c (斟酌修改) 確認執行模式符合預期，過程中也該比較 glibc 的 POSIX Threads 效能表現

Reference

Last changed by 
 
Benjamin Lin
0
131

Read more

linux2023: doodoodog

The template is for facilitating hiring process, with which interviewers and HRs can evaluate the candidates. Two versions of score card are provided so that you can choose one that fits your culture better.

Aug 19, 2023
Read more from Benjamin Lin
Published on HackMD