# 2023 Homework2 (quiz1)
> contributed by < Eddie-064 >
> [Github](https://github.com/Eddie-064/linux2023-summer)

## 程式碼運作原理 (待捕)

- Makefile: 這邊定義了兩個 Flag，USE_PTHREADS 與 USE_LINUX，make check 後會分別編譯並執行這兩個程式。

#### `futex`
這邊封裝了三種需要系統呼叫的 futex 操作。
使用 futex lock 相較於使用 pthread mutex lock 較低成本，futex 是在 user space 使用 atomic 指令透過硬體完成最小操作。
:::info
condvar 與 broadcast 概念
當對多個 condvar 進行 broadcast 時，多個等待 condvar 的執行緒回到用戶空間競爭所屬的 mutex，而每個執行緒又因競爭 mutex 回到 kernel 排隊等待，這樣多次的切換使用系統呼叫，容易造成系統資源浪費。
- condvar waiter 在 kernel 等待被喚醒
:::
- `futex_requeue`: 看到上面的圖後才看懂，教材 futex_requeue 的圖，futex_requeue 就是避免多個執行緒被喚醒回到用戶空間，又因競爭 mutex 而再次回到 kernel，直接在 kernel 中移到另一個佇列等待 mutex 喚醒。

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

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

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

#### `mutex`
這邊定義 `mutex_t` 結構，變數 `state` 宣告為 `atomic` 確保在多執行緒環境下變數最小操作，也就是只有完成操作與沒有操作，不會有其他中間狀態。

typedef struct {
    atomic int state;
} mutex_t;

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

- `mutex_trylock` : 這邊首先用 atomic `load` 讀取確認 lock 狀態是不是 locked，如果沒有其他人使用則透過 `fetch_or` 寫入 `MUTEX_LOCKED`。`thread_fence` 用於保護 atomic 操作的前後順序不會因編譯器或 CPU 的優化而更動。

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`: 待補，`__builtin_ia32_pause` 會節省資源的消耗，但不知道和 `futex_wait` 實作的差異。

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

- `mutex_unlock`: 透過 `exchange` 的 atomic 操作讀取值後寫入 0，如果原先狀態是 `MUTEX_SLEEPING` 則需要被喚醒。

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

#### condvar
- 包含 `cond_wait`、`cond_signal`、`cond_broadcast` 三種操作。

#### main

struct clock {
    mutex_t mutex;
    cond_t cond;
    int ticks;
};

### 測試方法

### futex 使用方式

### POSIX Threads 強化哪些相關 futex 實作機制

## 修改並行快速排序實作 futex 版本

## 於 POSIX Thread 實作 priority inheritance mutex

## skinny-mutex POSIX Threads and Performance