# 2023 Homework2 (quiz1)
contributed by < `backink` >
[github](https://github.com/backink/Linux2023_summer/tree/main/hw2)
## 開發環境
```
$gcc --version
gcc (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0
$lscpu
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Address sizes: 44 bits physical, 48 bits virtual
Byte Order: Little Endian
CPU(s): 16
On-line CPU(s) list: 0-15
Vendor ID: AuthenticAMD
Model name: AMD Ryzen 7 4800HS with Radeon Graphics
CPU family: 23
Model: 96
Thread(s) per core: 2
Core(s) per socket: 8
Socket(s): 1
Stepping: 1
Frequency boost: enabled
CPU max MHz: 2900.0000
CPU min MHz: 1400.0000
BogoMIPS: 5789.25
Virtualization features:
Virtualization: AMD-V
Caches (sum of all):
L1d: 256 KiB (8 instances)
L1i: 256 KiB (8 instances)
L2: 4 MiB (8 instances)
L3: 8 MiB (2 instances)
NUMA:
NUMA node(s): 1
NUMA node0 CPU(s): 0-15
```
## 開發過程
```c
static inline void cond_signal(cond_t *cond, mutex_t *mutex)
{
fetch_add(&cond->seq, BBBB, relaxed);
EEEE(&cond->seq, 1);
}
```
**BBBB** 為 1，因為在cond_wait 中會等待 cond->seq 的值改變，在cond_signal時將 condvar 的值加 1 可以讓在 cond_wait 中等待的執行緒可以往下進行。
**EEEE** 為 futex_wake ，在 cond->seq 值改變後，喚醒一個在 futex_wait 中等待此 condvar 改變的 thread。
```c
static inline void cond_broadcast(cond_t *cond, mutex_t *mutex)
{
fetch_add(&cond->seq, CCCC, relaxed);
futex_requeue(&cond->seq, DDDD, &mutex->state);
}
```
**CCCC** 為 1 ，原因同 BBBB
**DDDD** 為 1 ，因為 broadcast 後所有 thread 都不需要再等待 condvar ，不過還是需要等待 mutex，所以利用 futex_requeue 將原先等待 cond->seq 的 thread 轉到等待 mutex->state 的 wait_queue 中。不過因為最終還是只有一個 thread 可往下執行，所以在此喚醒一個等待中的 thread。
參考 futex man page 中 FUTEX_CMP_REQUEUE 部份說明，和 syscall 參數
* the operation wakes up a maximum of *val* waiters that are waiting on the futex at *uaddr*. If there are more than *val* waiters, then the remaining waiters are removed from the wait queue of the source futex at *uaddr* and added to the wait queue of the target futex at *uaddr2*.
* 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.h 檔案中的函式定義，在此 val 為 1，uaddr 為 &cond->seq， uaddr2 為 &mutex->state。
```c
static inline void mutex_unlock(mutex_t *mutex)
{
int state = exchange(&mutex->state, 0, release);
if (state & MUTEX_SLEEPING)
FFFF(&mutex->state, 1);
}
```
**FFFF** 為 futex_wake，在 mutex_unlock 中如果有 thread 在 mutex->state 的 wait_queue 中則喚醒其中一個 thread。
```c
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, AAAA, relaxed);
}
```
**AAAA** 為 MUTEX_SLEEPING，這裡設定 MUTEX_SLEEPING 的原因是如果 cond->seq 被 broadcast 過，等待 cond->seq 的 thread 會轉至等待 mutex->state，在這個情境下如過沒有設定 MUTEX_SLEEPING 在 mutex_unlock 的時候有可能會因為沒有 MUTEX_SLEEPING 這個 flag 導致雖然有 thread 在等待但卻沒有任何 thread被喚醒。
這個地方我花了不少時間思考，其中遇到兩個問題
1. 如果沒有 MUTEX_SLEEPING 這個 flag 似乎也能正確執行，如果是這樣那設定 MUTEX_SLEEPING 的用意是什麼？
2. 在 cond_wait 和 mutex_lock 中可能有一種情況是拿到 mutex 的 thread 還是需要設定 MUTEX_SLEEPING 的 flag，即使這個 thread 已經脫離 sleeping 的狀態
初步跟同學討論第一個問題的結果認為， futex 是高成本的 syscall ，如果可以在 user space 用某些手段判斷減少呼叫 futex 相關 syscall 的機會，可以降低執行系統成本以及執行時間
第二個問題思考的是，既然 MUTEX_SLEEPING 是用來節制呼叫 futex 的手段，在某些狀況下拿到 mutex 的 thread 仍然會去設定這個 flag 即使自己已經不再需要等待。這樣的方式可以確保在 mutex_unlock的時候會有等待中的 thread 被喚醒，可是如果剛好沒有 thread 正在等待，等於也會呼叫一次無效果的 futex_wake 造成資源浪費。
考慮這樣的情況 MUTEX_SLEEPING 的設計是否有其效益，或是有其他方式可以處理拿到 mutex 還要設定 sleeping 的情況，我需要再思考一下並設計實驗去驗證。
:::success
延伸問題:
* 解釋上述程式碼運作原理，應該涵蓋測試方法、futex 使用方式、Linux 核心開發者針對 POSIX Threads 強化哪些相關 futex 實作機制等等
* 修改第 1 次作業的測驗 γ 提供的並行版本快速排序法實作，使其得以搭配上述 futex 程式碼運作
* 研讀〈並行程式設計: 建立相容於 POSIX Thread 的實作〉，在上述程式碼的基礎之上，實作 priority inheritance mutex 並確認與 glibc 實作行為相同，應有對應的 PI 測試程式碼比照 skinny-mutex，設計 POSIX Threads 風格的 API，並利用內附的 perf.c (斟酌修改) 確認執行模式符合預期，過程中也該比較 glibc 的 POSIX Threads 效能表現
:::
Sign in with Wallet
Connect another wallet