# 2023 Homework2 (quiz1)
contributed by < [shhung](https://github.com/shhung) >

## FUTEX (Fast userspace Mutex) 運作原理

### Why and how fast
futex 來源於對一般應用的觀察，大多數的場景下 lock 並不會被競爭，這種時候可以很容易的取得 lock，futex 此時利用 atomic operation 來在 userspace 取得 lock，然而還是可能會有其他的 thread 同時競爭鎖，此時有兩種選擇，
- 迴圈持續使用 atomic operation 競爭鎖 (userspace)
- sleep 讓出資源 (context-switch)

若是選擇 sleep 的話還是需要透過 kernel 來讓出資源，等待 lock 的持有者喚醒。
但是如前所述，大多時候同時競爭的情況相比起來還是比較少，因此滿足 Fast 的形容。

### SYSCALL

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

[futex(2)](https://man7.org/linux/man-pages/man2/futex.2.html)

#### `futex_op`
- `FUTEX_WAIT`
獲取 `uaddr` 的值，是否為預期的值 `val` ，如果相同則進入睡眠，等待 `FUTEX_WAKE` 喚醒，若不同，則失敗並獲得 `EAGAIN` 錯誤。

- `FUTEX_WAKE`
喚醒等待 `uaddr` 的佇列中，最多 `val` 個數量的等待者。

- `FUTEX_REQUEUE`
喚醒等待 `addr` 的佇列中，最多 `val` 個數量的等待者，如果等待者數量超過 `val` ，將未被喚醒的等待者移到等待 `uaddr2` 的佇列， `uaddr2` 的佇列中最多可以有 `val2` 個等待者。

## 測試方法

## Futex Requeue PI
Futex Requeue PI 是為了避免 [Priority Invertion](https://en.wikipedia.org/wiki/Priority_inversion) 的問題，同時也能降低 `pthread_cond_broadcast` 造成的 [Thundering-herd problem](https://en.wikipedia.org/wiki/Thundering_herd_problem) 。
這裡的 PI 是 [Priority inheritance](https://en.wikipedia.org/wiki/Priority_inheritance) 的縮寫，基本的原理是當一個優先權較低的執行緒 A 佔有 lock ，而其他競爭中的執行緒 B, C 優先權都比 A 還高，但是優先權 B < C ，此時會將 A 的優先權暫時提高到和 C 相同，當 A unlock 後再降低優先權，以此避免上面提到的 Priority invertion 。

## 以 futex 修改 qsort-mt 使用的 pthread
最直覺的方法先將 `pthread` 相關函式以 `mutex.h` 和 `cond.h` 裡對應的函式取代，修改後執行並給參數 `v` 做驗證，結果不正確，需要深入去找錯誤的地方。

## 實作 priority inheritance mutex

### 思路
為了以最簡單的方法實現 Priority inheritance ，在 mutex 結構中紀錄 lock 的擁有者以及原本的優先權，並加入以下操作

1. 獲取 lock 後，擁有者除了改變 state 還會記錄自己的 tid 和當下的優先權，這樣在釋放 lock 後如果有調整優先權可以在調整回來
2. 當請求 lock 失敗後，在 `futex_wait` 之前會比較自身的優先權和擁有者的優先權，如果擁有者的優先權較低，將其設定為自己的優先權
3. 釋放 lock ，在 `futex_wake` 之前將優先權設定回原本的優先權

### 改動

#### mutex.h

typedef struct {
    atomic int state;
+    pthread_t owner;
+    int own_prio;
} mutex_t;

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 own_policy;
+    struct sched_param own_param;

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

    while (state & MUTEX_LOCKED) {
+        int policy;
+        struct sched_param param;
+        pthread_getschedparam(mutex->owner, &own_policy, &own_param);
+        pthread_getschedparam(pthread_self(), &policy, &param);
+        if (own_param.sched_priority < param.sched_priority) {
+            pthread_setschedparam(mutex->owner, SCHED_RR, &param);
+        }
        futex_wait(&mutex->state, MUTEX_LOCKED | MUTEX_SLEEPING);
        state = exchange(&mutex->state, MUTEX_LOCKED | MUTEX_SLEEPING, relaxed);
    }

    thread_fence(&mutex->state, acquire);
+    mutex->owner = pthread_self();
+    pthread_getschedparam(mutex->owner, &own_policy, &own_param);
+    mutex->own_prio = own_param.sched_priority;
}

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

在 TSAN 的檢查下 `pthread_setschedprio()` 發生 SEGV