2024q1 第 10 週測驗題

目的: 檢驗學員對 Atomics 操作, probabilistic data structure, Hazard pointer 的認知

作答表單: 測驗 1 (針對 Linux 核心「設計」課程)
作答表單: 測驗 2-3 (針對 Linux 核心「實作」課程)

測驗 `1`

延伸第 6 週測驗題涵蓋的 bloom filter，我們想發展得以在並行環境運作的程式碼。理論與實際性能對比，其中 k=2 與 n=2^28，理論錯誤率採用公式

(1 - e^{\frac{- k \times n}{b}})^{k}

計算得出。使用 k=2 是因為可將一個 64 位元雜湊分割成兩部分來來實作。要達到約 0.05 的錯誤率，需要設定

n = 2^{28}

。雜湊函數使用 xxHash

原始程式碼 (部分遮蔽)

編譯方式:

$ wget https://raw.githubusercontent.com/Cyan4973/xxHash/dev/xxhash.h
$ gcc -Wall -std=gnu11 -g -O2 -I. -o bench bench.c  bloom.c

參考執行輸出:

$ ./bench
50958386 ops/s

作答規範:

AAAA 是以 atomic_ 開頭的 C11 Atomics 函式
BBBB 呼叫 get 函式
CCCC 是 signal 名稱

延伸問題:

解釋上述程式碼運作原理，探討其能否滿足 thread-safe 要求
倘若上述程式碼無法通過 ThreadSanitizer，提出修正

測驗 `2`

〈並行程式設計: Hazard pointer〉提到:

在並行程式設計中，當我們在存取共用的記憶體物件時，需要考慮到其他執行緒是否有可能也正在存取同一個物件，若要釋放該記憶體物件時，不考慮這個問題，會引發嚴重的後果，例如 dangling pointer。

使用 mutex 是最簡單且直觀的方法：存取共用記憶體時，acquire lock 即可保證沒有其他執行緒正在存取同一物件，也就可安全地釋放記憶體。但若我們正在存取的是一種 lock-free 資料結構，當然就不能恣意地使用 lock，因為會違反 lock-free 特性，即無論任何執行緒失敗，其他執行緒都能可繼續執行。於是乎，我們需要某種同為 lock-free 的記憶體物件回收機制。

lfq 嘗試實作精簡的並行佇列 (concurrent queue)，運用 hazard pointer 來釋放並行處理過程中的記憶體，原始程式碼 (部分遮蔽)。

在 lfq.h 中，先定義二個結構體。

struct lfq_node {
    void *data;
    union {
        struct lfq_node *next;
        struct lfq_node *free_next;
    };
    bool can_free;
};

struct lfq_ctx {
    alignas(64) struct lfq_node *head;
    int count;
    struct lfq_node **HP; /* hazard pointers */
    int *tid_map;
    bool is_freeing;
    struct lfq_node *fph, *fpt; /* free pool head/tail */

    /* FIXME: get rid of struct. Make it configurable */
    int MAX_HP_SIZE;

    /* avoid cacheline contention */
    alignas(64) struct lfq_node *tail;
};

struct lfq_node 是 lock-free queue node 的結構，其中除了資料以及代表能否 free 的一個 bool 以外，還嵌入 union 的型別去儲存 next 及 free_next，next 是佇列中的下一個節點，free_next 則是 free pool 中的下個節點。

struct lfq_ctx 是 lock-free queue handler 的結構，儲存佇列及 free pool 的頭尾，及 tid 的 map，還有個 bool 型態的變數用來確認是否正在做 free 的動作，此外，也儲存 hazard pointers 和他的最大長度。

lfq_enqueue 的功能為推入 (push) 資料進入佇列中，作法是將佇列的尾端替換成 insert_node，再將原先舊尾端 old_tail 的 next 指向 insert_node。

lfq_dequeue 的功能為將資料從佇列中取出 (pop)，首先，會先透過 alloc_tid 取得 tid ，如果順利取得非 -1 的值，就會透過 lfq_dequeue_tid 去做 pop，在 lfq_dequeue_tid 中，會先將要 pop 的 old_head 存入 ctx->HP[tid] 之中，然後將佇列的 head 替換成 new_head 也就是 old_head->next，完成後再將 ctx->HP[tid] 重設回 0，再對 old_head 做 safe_free。

若節點能被 free 且不在 hazard pointers 內，safe_free 函式嘗試釋放已配置的資源，否則就藉由 insert_pool 只將節點加入 free pool，倘若 CAS(&ctx->is_freeing, 0, 1) 操作成功的話，就能確實地釋放節點佔用的記憶體空間，但若失敗，就一樣只將節點加入 free pool，最後呼叫 free_pool 以嘗試釋放 free pool 內的節點。

編譯方式:

$ gcc -std=gnu99 -O3 -Wall -Wextra -o test_p1c1  -D MAX_PRODUCER=1 -D MAX_CONSUMER=1 lfq.c test.c -lpthread

這個實作應該要能夠支援以下組態:

-D MAX_PRODUCER=4 -D MAX_CONSUMER=4
-D MAX_PRODUCER=100 -D MAX_CONSUMER=10
-D MAX_PRODUCER=10 -D MAX_CONSUMER=100

預期輸出:

Producer thread [140583962404608] exited! Still 0 running...
Consumer thread [140583970797312] exited 0
Total push 500000 elements, pop 500000 elements. freelist=1, clean = 0
Test PASS!!

補完程式碼，使其運作符合預期。作答規範:

AAAA, BBBB, CCCC 均為傳入 atomic_compare_exchange_strong 的參數，採用作業一規範的程式碼書寫風格

測驗 `3`

對應到並行程式設計: Thread Pool 實作和改進和 Linux 核心設計: 針對事件驅動的 I/O 模型演化

httpd 是個運用 thread pool 和 epoll 系統呼叫的網頁伺服器，原始程式碼 (部分遮蔽)。

書寫規範：

DDDD 為表示式
EEEE 為系統呼叫名稱

延伸問題:

解釋上述程式碼運作原理，探討其能否滿足 thread-safe 要求
倘若上述程式碼無法通過 ThreadSanitizer，提出修正
評估上述 httpd 的性能表現

2024q1 第 10 週測驗題

測驗 1

測驗 2

測驗 3

Read more

單一指令處理器 (OISC)

從 CPU cache coherence 談 Linux spinlock 可擴展能力議題

淺談 Microkernel 設計和真實世界中的應用

並行程式設計: 概念

測驗 `1`

測驗 `2`

測驗 `3`