# 2023 Homework3
contributed by < [tintinjian12999](https://github.com/tintinjian12999) >
## 挑戰一
### 研讀[第 2 次測驗題](https://hackmd.io/@sysprog/linux2023-summer-quiz2)的測驗 1，研讀程式碼註解提及的論文〈Cilk: An Efficient Multithreaded Runtime System〉，解釋程式碼運作原理。
#### 資料結構
``` 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)
Sign in with Wallet
Connect another wallet