---
# System prepended metadata

title: 2023 Homework2 (quiz1)

---

# 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 效能表現
:::