2023 Homework2 (quiz1)
======================

#### contributed by <[shlin41](https://github.com/shlin41)>
---
## Q1：解釋程式碼運作原理
> 註：解釋上述程式碼運作原理，應該涵蓋測試方法、futex 使用方式、Linux 核心開發者針對 POSIX Threads 強化哪些相關 futex 實作機制等等

### [atomic.h]
* 目的：用 MACRO 簡化 <stdatomic> 中function 的名字
* read_fense: thread_fence(state, acquire) -> 用來避免 LL, LS 互換。保護前面的那個 L。

digraph orderAcquire {
    node [shape=box]
    {
        a [label="L"]
        c [label="L"]
    }
    {
        a1 [label="L"]
        c1 [label="S"]
    }
    {
        a->a1 [dir="both" fontsize="20" color = "red" headlabel="×" labeldistance="3.5" labelangle="0" minlen="2"]
        
        c->c1 [dir="both" fontsize="20" color = "red" headlabel="×" labeldistance="3.5" labelangle="0" minlen="2"]
        
    }
}

* write_fense: thread_fence(state, release) -> 用來避免 SS, LS 互換。保護後面的那個 S。

digraph orderRelease {
    node [shape=box]
    {
        a [label="S"]
        c [label="L"]
    }
    {
        a1 [label="S"]
        c1 [label="S"]
    }
    {
        a->a1 [dir="both" fontsize="20" color = "red" headlabel="×" labeldistance="3.5" labelangle="0" minlen="2"]
        
        c->c1 [dir="both" fontsize="20" color = "red" headlabel="×" labeldistance="3.5" labelangle="0" minlen="2"]
        
    }
}

* 心得：[Atomic_thread_fence](https://en.cppreference.com/w/cpp/atomic/atomic_thread_fence)
* ==memory_order_acquire: 先 atomic_action 再 read_fence==

    atomic_exchange_explicit(state, true, acquire);
                等於
    atomic_exchange_explicit(state, true, relaxed); // 先 atomic action
    atomic_thread_fence(acquire);                   // 再 read memory barrier

* ==memory_order_release: 先 write_fence 再 atomic_action==

    atomic_exchange_explicit(state, true, release);
                等於
    atomic_thread_fence(release);                   // 先 write memory barrier
    atomic_exchange_explicit(state, true, relaxed); // 再 atomic action

* ==memory_order_acq_rel: 先 write_fence 再 atomic_action 再 read_fence==

    atomic_exchange_explicit(state, true, acq_rel);
                等於
    thread_fence(release);                          // 先 write memory barrier
    atomic_exchange_explicit(state, true, relaxed); // 再 atomic action
    thread_fence(acquire);                          // 再 read memory barrier
    
### [futex.h]
* SystemCall 宣告: (six arguments)

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

* kernel 對應的 function: (7  arguments)

long do_futex(u32 __user *uaddr, int op, u32 val, ktime_t *timeout,
u32 __user *uaddr2, u32 val2, u32 val3)

* 對照看 [man futex(2)](https://man7.org/linux/man-pages/man2/futex.2.html)：
    *    FUTEX_WAIT
    *    FUTEX_WAKE
    *    FUTEX_REQUEUE
    *    FUTEX_CMP_REQUEUE
    *    FUTEX_CMP_REQUEUE_PI
    
### [mutex.h] 
* 實做 mutex_trylock, mutex_lock, mutex_unlock
* int state： 搭配 {MUTEX_LOCKED, MUTEX_SLEEPING} 紀錄狀態
    *    int state： 因為至少需要兩個 bits，所以直接使用 int 
* MUTEX_SLEEPING: 設計得很怪
    *    應該是為了紀錄有沒有人在 queue 裡面等待
    *    如果有 (i.e. MUTEX_SLEEPING is set) 則 futex_wake
    *    但是 state == b01 的機會很少
            *    用到 cond_wait 時，每次都設定 state == b11
            *    只有在使用 mutex_trylock / mutex_lock 的第一個人，才有機會 state = b01
    *    ==不設計/處理 MUTEX_SLEEPING，每次都 futex_wake，其實程式也可正常執行==

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 中的 memory fence 擺放的位置搞不懂== [Release-Acquire_ordering](https://en.cppreference.com/w/cpp/atomic/memory_order#Release-Acquire_ordering)
    > Q1: 為什麼 mutex_lock 要在最後面擺一個 read_fence？      為什麼 mutex_unlock 要在最前面擺一個 write_fence？
      Q2: read_fence 和 write_fence 夾出了一個區間，和滿足 Visible 有何關係？

### [spinlock.h] 
* 實做 spin_trylock, spin_lock, spin_unlock
* bool state: 因為只需要紀錄 locked / unlocked
* 因為 spinlock 屬於 busy wait，因此不需要借助 futex 進入 queue 中睡覺
* 利用 spin_hint()：生成對應平台的 pause 機器指令
* 和 mutex 有一樣的 memory_fence 設計
    *    spin_trylock / spin_lock 最後面擺一個 read_fence
    *    spin_unlock 最前面擺一個 write_fence

### [cond.h]
* 實做 cond_wait, cond_signal, cond_broadcast
* int seq：很有趣的設計，流水號遞增。
    *    為了讓 cond_wait 當時的 seq 和之後 cond_signal 當時的 seq 不同
    *    如果用 bool seq：會有如下問題
    > 假設：
    step 1: waiter_1, waiter_2 都讀到 seq == 0 進入 queue
    step 2: server 呼叫 cond_signal(seq = 1) 可以叫醒一個 waiter
    step 3: server 呼叫 cond_signal(seq = 0) 無法叫醒另一個 waiter
    *    那 int seq 就沒問題嗎? 
    > Ans: 
    當然不是
    同時 max_uint 個人 wait，server 一個一個叫，一樣會有最後一個人叫不醒的問題
    
### [main.c]
* node 連接方式：

digraph mygraph{
node1 -> node0;
node2 -> node1;
nodeN -> node2;
}

* 每個 node 做的事情：(clock 是共享的)
    *    clock_wait(clock, tick)：等到 tick 時間到
    (即 clock >= tick)
    *    如果有 parent，則等 parent ready
    *    交替地 clock_tick(clock) 和 node_signal(self)
* 程式停止條件：clock == 2^16^，由 main 去停止 (set clock = -1)
* 其他討論：
    *    為什麼不會卡在 node_wait?
    > Ans: 因為 node0 不會 wait，導致 node1 一定可以起床。以此類推。
    *    為什麼不會卡在 clock_wait?
    > Ans: 比較難解釋。原則上 clock 上漲飛快。在地一次由 main 呼叫 clock_tick 後，所有 node 被喚醒且都會去跑一次 clock_tick。
    
    
---
## Q2：修改第 1 次作業的測驗 γ 
>註：修改第 1 次作業的測驗 γ提供的並行版本快速排序法實作，使其得以搭配上述 futex 程式碼運作
    
修改完的版本：[Source Code](https://github.com/shlin41/GammaModify)
* 把 USE_PTHREAD 的部份刪除，只保留 USE_LINUX 的部份 (避免不小心又用到原本的 pthread)
* 把 pthread_mutex_XXX / pthread_cond_XXX 的 functions 都改成 mutex_XXX / cond_XXX
* function 的 argus 和 return 以 pthread 的 templete 為主：mutex.h, cond.h 搭配修改。主要是補 return 0。
==注意：mutex_trylock 原本的邏輯剛好相反，改過來。==


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


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

## Reference
* [man futex(2)](https://man7.org/linux/man-pages/man2/futex.2.html)
* [Atomic_thread_fence](https://en.cppreference.com/w/cpp/atomic/atomic_thread_fence)、[Release-Acquire_ordering](https://en.cppreference.com/w/cpp/atomic/memory_order#Release-Acquire_ordering)