---
tags: linux2024
---

# [2024q1](https://wiki.csie.ncku.edu.tw/linux/schedule) 第 17 週測驗題

:::info
目的: 檢驗學員對[並行和多執行緒程式設計](https://hackmd.io/@sysprog/concurrency)的認知
:::

==[作答表單](https://docs.google.com/forms/d/e/1FAIpQLSdvFOx0sNu6Ag0OBDA3FNaPFf8Aff9Pg1qIfu_43DQLhtjxdw/viewform)== (針對 Linux 核心「設計」課程)
==[作答表單](https://docs.google.com/forms/d/e/1FAIpQLScHo6gxeiVRzj15YxoMuvib3EaavWE7oD90Xz0M7BlAiInREw/viewform)== (針對 Linux 核心「實作」課程)

### 測驗 `1`

考慮一個 lock-free stack 的實作。使用者可推入 `void *` 到堆疊中，檢查堆疊的大小，並從堆疊中彈出 `void *`。除了初始化和銷毀，這些操作在多個執行緒中都是安全的。當彈出時，兩個不同的執行緒永遠不會獲得相同的元素。如果兩個執行緒同時嘗試推入元素，也不會有元素丟失。最重要的是，當存取堆疊時，執行緒永遠不會在 lock 上阻塞。C 語言標準函式庫無法保證 `malloc()` 是不依賴 lock，於是 lock-free 實作意味著不呼叫 `malloc()`。預先配置堆疊記憶體的另一個重要好處是，該實作不需要使用 hazard pointers，後者比堆疊本身要複雜得多。

最大堆疊空間應該實際上是所需的最大空間加上存取堆疊的執行緒數量。這是因為一個執行緒可能從堆疊中移除一個節點，在該節點被釋放以供重用之前，另一個執行緒嘗試推入。這個執行緒可能找不到任何可用的節點，導致它放棄，儘管堆疊實際上「未滿」。

`lstack_init()` 和 `lstack_push()` 的整數返回值是用來表示錯誤代碼，成功時返回 `0`。這些操作唯一可能失敗的情況是記憶體不足。這無論是否使用 lock 都是一個問題：系統可能會用完記憶體。在推入的情況下，這意味著堆疊已滿。

[lstack 原始程式碼](https://gist.github.com/jserv/b9ee99c63bd0ea4c85b8024e9f74e7e9)

參考執行輸出:

Using 64 threads.
Found 564 hashes ...

注意: 無法通過 ThreadSanitizer

---

### 測驗 `2`

(mutex) lock 可能會導致 deadlock，但若始終按照一致的順序去 acquire lock，即可避免該情況。以下程式碼提供追蹤功能，確保使用者採取正確的順序。程式會跟蹤目前執行緒持有的 lock，每當 acquire 獲取新 lock 時，就會從最後一個 lock 到新 lock 建立一個依賴關係，後者構成一個 graph，只要該 graph 不包含任何循環，就不會發生 deadlock。
> 延伸閱讀: [Deadlock-free Mutexes and Directed Acyclic Graphs](https://bertptrs.nl/2022/06/23/deadlock-free-mutexes-and-directed-acyclic-graphs.html)

考慮以下的程式碼:

/* Task A locks mutex1 then mutex2, simulating a resource access pattern. */
void *taskA(void *thread_id)
{
    long tid = (long) thread_id;
    printf("[%s] thread #%ld\n", __func__, tid);

    for (int i = 0; i < N_TESTS; i++) {
        mutex_lock(&mutex1);
        sleep(1);
        mutex_lock(&mutex2);
        printf("task A in loop %d \n", i);
        sleep(1);
        mutex_unlock(&mutex2);
        sleep(1);
        mutex_unlock(&mutex1);
        sleep(1);
    }
    pthread_exit(NULL);
}

/* Task B locks mutex2 then mutex1, simulating a different resource access
 * pattern.
 */
void *taskB(void *thread_id)
{
    long tid = (long) thread_id;
    printf("[%s] thread #%ld\n", __func__, tid);

    for (int i = 0; i < N_TESTS; i++) {
        mutex_lock(&mutex2);
        sleep(1);
        mutex_lock(&mutex1);
        printf("task B in loop %d \n", i);
        sleep(1);
        mutex_unlock(&mutex1);
        sleep(1);
        mutex_unlock(&mutex2);
        sleep(1);
    }
    pthread_exit(NULL);
}

參考執行輸出: (ok 那行可能不出現)

[taskA] thread #0
[taskB] thread #1
will_lock: --- pid 0xddf9a700 deadlock lock 0x94120442286208x (id=0) -> lock 0x94120442286144x (id=1)
current mutex with holding threads (PID)
========================================
pid 0x0 holds lock 0x1f875080 (id=0)
pid 0x1 holds lock 0x1f875040 (id=1)

Recorded lock dependency
========================================
pid 0x0 lock 0x1f875080 (id=0) -> lock 0x1f875040 (id=1) deadlock
pid 0x1 lock 0x1f875040 (id=1) -> lock 0x1f875080 (id=0) ok

Linux 核心也有 lock 相依性的偵測機制，參見 [Runtime locking correctness validator](https://www.kernel.org/doc/Documentation/locking/lockdep-design.txt)，對應的程式碼:
* [kernel/locking/lockdep.c](https://github.com/torvalds/linux/blob/master/kernel/locking/lockdep.c)
* [kernel/locking/lockdep_proc.c](https://github.com/torvalds/linux/blob/master/kernel/locking/lockdep_proc.c)
* [kernel/locking/lockdep_internals.h](https://github.com/torvalds/linux/blob/master/kernel/locking/lockdep_internals.h)
* [include/linux/lockdep_types.h](https://github.com/torvalds/linux/blob/master/include/linux/lockdep_types.h)
* [include/linux/lockdep_api.h](https://github.com/torvalds/linux/blob/master/include/linux/lockdep_api.h)
* [include/linux/lockdep.h](https://github.com/torvalds/linux/blob/master/include/linux/lockdep.h)

補完程式碼，使 [lockdep](https://gist.github.com/jserv/ec0dc4ba871a9efca79115eb902504ee) 運作符合預期。

作答規範：
* AAAA, CCCC, DDDD 為表示式，注意遞迴呼叫
* BBBB 為 bool 型態，必為 `true` 或 `false`