---
# System prepended metadata

title: 2023 Homework3

---

# 2023 Homework3
contributed by < [tintinjian12999](https://github.com/tintinjian12999) >

## 挑戰一
### 研讀[第 2 次測驗題](https://hackmd.io/@sysprog/linux2023-summer-quiz2)的測驗 1，研讀程式碼註解提及的論文〈Cilk: An Efficient Multithreaded Runtime System〉，解釋程式碼運作原理。
#### 資料結構
![](https://hackmd.io/_uploads/HJwsUDXA2.png)
``` c
typedef struct work_internal {
    task_t code;
    atomic_int join_count;
    void *args[];
} work_t;
```
如圖所示
`code` 是一個 function pointer。
`join_count` 表示這個 work 缺少的 argument 數
`*args[]` 表示這個 work 需要的 argument
```c
typedef struct {
    atomic_size_t size;
    _Atomic work_t *buffer[];
} array_t;

typedef struct {
    /* Assume that they never overflow */
    atomic_size_t top, bottom;
    _Atomic(array_t *) array;
} deque_t;
```
將上述的 works 加入到 deque 中用於 work steal。 閒置的 thread 會從 deque 的 top 開始竊取任務執行，而被竊取的 thread 會從 bottom 拿取任務執行。
#### take
```c
work_t *take(deque_t *q)
{
    size_t b = atomic_load_explicit(&q->bottom, memory_order_relaxed) - 1;
    array_t *a = atomic_load_explicit(&q->array, memory_order_relaxed);
    atomic_store_explicit(&q->bottom, b, memory_order_relaxed);
    atomic_thread_fence(memory_order_seq_cst);
    size_t t = atomic_load_explicit(&q->top, memory_order_relaxed);
    work_t *x;
    if (t <= b) {
        /* Non-empty queue */
        x = atomic_load_explicit(&a->buffer[b % a->size], memory_order_relaxed);
        if (t == b) {
            /* Single last element in queue */
            if (!atomic_compare_exchange_strong_explicit(&q->top, &t, t + 1,
                                                         memory_order_seq_cst,
                                                         memory_order_relaxed)) /*AAAA*/
                /* Failed race */
                x = EMPTY;
            atomic_store_explicit(&q->bottom, b + 1, memory_order_relaxed); /*BBBB*/
        }
    } else { /* Empty queue */
        x = EMPTY;
        atomic_store_explicit(&q->bottom, b + 1, memory_order_relaxed); /*CCCC*/
    } 
    return x;
}
```
被竊取的 thread 會從 deque 的 bottom 提出任務執行，取出 deque 的第 bottom - 1 個任務(因為 deque 從 0 開始)，並將當前的 bottom 數減一 (因為已經將任務拿出來了)。

接著判斷是否會發生竊取者與被竊取者互相競爭同一個任務的問題:
若 `t < b` 代表兩者不會有競爭的問題，直接回傳該任務。

若 `t = b` 代表該 deque 只剩一個任務，因此要透過 `compare_exchange` 來判斷使否發生 race condition，若 `q->top` 與 `t` 不一樣，代表該任務已經被竊取了，所以要透過 store 將先前改變的 bottom 加回來並回傳 EMPTY。因此 `AAAA` 為 t + 1 (被竊取者拿取任務後該 deque 的有效區間會被清空， 也就是 t > b)，`BBBB` 為 b + 1。

若`t > b` 代表該 deque 的任務已經被拿完，直接將先前改變的 bottom 加回來並回傳 EMPTY。 因此 `BBBB` 為 b + 1。

可以看到這邊先預設竊取者與被竊取者的 race condition 不會發生。
#### push
```c
void push(deque_t *q, work_t *w)
{
    size_t b = atomic_load_explicit(&q->bottom, memory_order_relaxed);
    size_t t = atomic_load_explicit(&q->top, memory_order_acquire);
    array_t *a = atomic_load_explicit(&q->array, memory_order_relaxed);
    if (b - t > a->size - 1) { /* Full queue */
        resize(q);
        a = atomic_load_explicit(&q->array, memory_order_relaxed);
    }
    atomic_store_explicit(&a->buffer[b % a->size], w, memory_order_relaxed);
    atomic_thread_fence(memory_order_release);
    atomic_store_explicit(&q->bottom, b + 1, memory_order_relaxed); /*DDDD*/
}
```
首先判斷 deque 滿了沒，如果滿了就 resize 成兩倍大。接著就是把任務放進 deque 的 bottom 並將 bottom + 1。
#### steal
```c
work_t *steal(deque_t *q)
{
    size_t t = atomic_load_explicit(&q->top, memory_order_acquire);
    atomic_thread_fence(memory_order_seq_cst);
    size_t b = atomic_load_explicit(&q->bottom, memory_order_acquire);
    work_t *x = EMPTY;
    if (t < b) {
        /* Non-empty queue */
        array_t *a = atomic_load_explicit(&q->array, memory_order_consume);
        x = atomic_load_explicit(&a->buffer[t % a->size], memory_order_relaxed);
        if (!atomic_compare_exchange_strong_explicit(
                &q->top, &t, t + 1, memory_order_seq_cst, memory_order_relaxed)) /*EEEE*/
            /* Failed race */
            return ABORT;
    }
    return x;
}
```
與 take 類似，但這 steal 是從 top 開始取，且要考慮 race condition， EEEE 為 t + 1。
#### thread
```c
void *thread(void *payload)
{
    int id = *(int *) payload;
    deque_t *my_queue = &thread_queues[id];
    while (true) {
        work_t *work = take(my_queue);
        if (work != EMPTY) {
            do_work(id, work);
        } else {
            /* Currently, there is no work present in my own queue */
            work_t *stolen = EMPTY;
            for (int i = 0; i < N_THREADS; ++i) {
                if (i == id)
                    continue;
                stolen = steal(&thread_queues[i]);
                if (stolen == ABORT) {
                    i--;
                    continue; /* Try again at the same i */
                } else if (stolen == EMPTY)
                    continue;

                /* Found some work to do */
                break;
            }
            if (stolen == EMPTY) {
                /* Despite the previous observation of all queues being devoid
                 * of tasks during the last examination, there exists
                 * a possibility that additional work items have been introduced
                 * subsequently. To account for this scenario, a state of active
                 * waiting is adopted, wherein the program continues to loop
                 * until the global "done" flag becomes set, indicative of
                 * potential new work additions.
                 */
                if (atomic_load(&done))
                    break;
                continue;
            } else {
                do_work(id, stolen);
            }
        }
    }
    printf("work item %d finished\n", id);
    return NULL;
}
```
這裡定義每個 thread 是如何挑選任務執行的。
首先先從自己的 deque 中取任務，如果自己的取完了再考慮從別的 thread 的 deque 中 steal 任務。此時要判斷發生兩種情況，一種是成功偷到，此時就直接執行，另外一種是 ABORT ，代表竊取者與被竊取者發生 race condition，這時會嘗試在同一個 deque 重新 steal。

當走訪過所有的 thread 之後也不代表所有的 work 都被做完了，有可能有工作在走訪後才產生，此時透過一個額外的 work `done_work` 裡的 `join_count` 來紀錄所有的任務，當任務都做完了才會將 `done` 轉為 true 並結束。
### 指出 [work-stealing](https://github.com/sysprog21/concurrent-programs/tree/master/work-steal) 程式碼可改進之處並著手進行。

### 利用 [work-stealing](https://github.com/sysprog21/concurrent-programs/tree/master/work-steal) 改寫[第 1 次作業](https://hackmd.io/@sysprog/linux2023-summer-quiz0)測驗 γ 提及的並行化快速排序程式碼，並確保能充分運用硬體資源。

### 研讀 Linux 核心的 [CMWQ](https://www.kernel.org/doc/html/next/core-api/workqueue.html)，討論其 work stealing 的實作手法

## 挑戰二

### 目前 [mcslock](https://github.com/sysprog21/concurrent-programs/tree/master/mcslock) 實作採用 [GCC atomic builtins](https://gcc.gnu.org/onlinedocs/gcc/_005f_005fatomic-Builtins.html)，請用 C11 Atomics 改寫，並確認實作行為與上述描述是否符合。 (歡迎提交 pull request 到 concurrent-programs)

### 研讀 Linux 核心的 [locking](https://github.com/torvalds/linux/tree/master/kernel/locking) 實作，闡述你對於 Linux 核心原始程式碼 [mcs_spinlock.h](https://github.com/torvalds/linux/blob/master/kernel/locking/mcs_spinlock.h) 的認知，對照閱讀核心文件 [locking](https://docs.kernel.org/locking/index.html)。

### 針對 MCS lock 所要改進 ticket lock 在多核處理器的效能議題，請設計實驗來說明其效益。

## 挑戰三

### 目前 [seqlock](https://github.com/sysprog21/concurrent-programs/tree/master/seqlock) 實作採用 [GCC atomic builtins](https://gcc.gnu.org/onlinedocs/gcc/_005f_005fatomic-Builtins.html)，請用 C11 Atomics 改寫，並確認實作行為與上述描述是否符合。 (歡迎提交 pull request 到 concurrent-programs)

### 研讀 Linux 核心的 [seqlock.h](https://github.com/torvalds/linux/blob/master/include/linux/seqlock.h) 實作，闡述你對於 Linux 核心原始程式碼的認知，對照閱讀核心文件 [locking](https://docs.kernel.org/locking/index.html)。

### 參照[第 2 次測驗題](https://hackmd.io/@sysprog/linux2023-summer-quiz2)的測驗 2 提及的 [mpmc](https://github.com/sysprog21/concurrent-programs/tree/master/mpmc) 及 [spmc](https://github.com/sysprog21/concurrent-programs/tree/master/spmc) 程式碼，改寫為大量讀取者－單一寫入者 (multiple-reader/single-write) 的場景，並運用上述 seqlock 程式碼，談及其具體效益。 (歡迎提交 pull request 到 concurrent-programs)