# Linux 核心專題: 並行程式設計
> 執行人: MathewSu-001
> [專題解說影片](?)
## 任務簡介
研讀[並行程式設計教材](https://hackmd.io/@sysprog/concurrency) 並動手確認
## TODO: 研讀[並行程式設計教材](https://hackmd.io/@sysprog/concurrency)
> 涵蓋概念, 排程器原理, 執行順序, Atomics 操作, POSIX Threads, 實作輕量級的 Mutex Lock, Lock-free 程式設計, 案例: Ring buffer 等議題。在此紀錄你的認知和疑惑，務必動手確認。
> 對照 [Linux 核心專題: 並行程式設計教材修訂](https://hackmd.io/@sysprog/H1dCuDxQR)，包含其錄影解說。
### [並行程式設計：概念](https://hackmd.io/@sysprog/concurrency/%2F%40sysprog%2Fconcurrency-concepts#%E4%B8%A6%E8%A1%8C%E7%A8%8B%E5%BC%8F%E8%A8%AD%E8%A8%88-%E6%A6%82%E5%BF%B5)
(一)並行的重要性
從[軟體開發現況](https://hackmd.io/@sysprog/concurrency/%2F%40sysprog%2Fconcurrency-concepts#%E8%BB%9F%E9%AB%94%E9%96%8B%E7%99%BC%E7%8F%BE%E6%B3%81)裡，可以發現自 2005 年以前， 工程師可以透過提昇 CPU 的時脈來提高程式運行的效能。但自 2005 年後， CPU 的時脈在技術層面上已經無法在提高，所以想要再提高效能，多工與多執行緒成為解法，並行的應用就在此產生。
(二)並行 vs. 平行
在[Concurrency (並行) vs. Parallelism (平行)](https://hackmd.io/@sysprog/concurrency/%2F%40sysprog%2Fconcurrency-concepts#Concurrency-%E4%B8%A6%E8%A1%8C-vs-Parallelism-%E5%B9%B3%E8%A1%8C)的圖例中，就可以做到很好的解釋。
- 並行：將一個工作拆解成多個讓執行緒可以分工合作，並且是在單個 CPU 上執行。
- 平行：多個工作在多個 CPU 上一起進行，為了達成目的可能會運用到並行。
(三)排程器
在並行上，透過排程器來決定 CPU 下一個所要執行的工作。而溝通的管道分為兩種：
- mutex 確保數個 process 在一個時間點上，只能有一個 process 存取單項資源;
- semaphore 讓數個 producer 與數個 consumer 在計數器的基礎上進行合作;
### [並行程式設計: 排程器原理](https://hackmd.io/@sysprog/concurrency/%2F%40sysprog%2Fconcurrency-sched)
在 [Building Coroutines](https://www.csl.mtu.edu/cs4411.ck/www/NOTES/non-local-goto/coroutine.html) 有簡單示範 `setjmp` 以及 `longjmp` 的用法:
:::danger
注意書寫規範：
* 使用 lab0 規範的程式碼書寫風格，務必用 clang-format 確認一致
* 注意看[程式碼規範](https://hackmd.io/@sysprog/linux2024-lab0-a)的「clang-format 工具和一致的程式撰寫風格」，筆記列出的程式碼依循指定的風格。
:::
```c
int max_iteration;
int iter;
jmp_buf Main;
jmp_buf PointPing;
jmp_buf PointPong;
void Ping(void);
void Pong(void);
void main(int argc, char *argv[]) {
if (argc != 2) {
printf("Use %s max-#-of-lines\n", argv[0]);
exit(1);
}
max_iteration = abs(atoi(argv[1]));
iter = 1;
if (setjmp(Main) == 0)
Ping();
if (setjmp(Main) == 0)
Pong();
longjmp(PointPing, 1);
}
```
首先定義全域變數 `iter` 來計算迭代次數，第一次的 `setjmp` 會儲存 main 函式現在的狀態到 `Main` 裡，然後呼叫函式 Ping 。
在 `setjmp` 的描述中有提到
>The setjmp() function saves various information about the calling environment (typically, the stack pointer, the instruction pointer, possibly the values of other registers and the signal mask) in the buffer env for later use by longjmp(). **In this case, setjmp() returns 0.**
:::danger
注意用語：
* call 是「呼叫」，而非「調用」
務必使用本課程教材規範的術語。
:::
所以在第一次呼叫時， `setjmp` 會返回值 0。
:::danger
注意書寫規範：
* 使用 lab0 規範的程式碼書寫風格，務必用 clang-format 確認一致
* 注意看[程式碼規範](https://hackmd.io/@sysprog/linux2024-lab0-a)的「clang-format 工具和一致的程式撰寫風格」，筆記列出的程式碼依循指定的風格。
:::
```c
void Ping(void) {
if (setjmp(PointPing) == 0)
longjmp(Main, 1);
while (1) {
printf("%3d : Ping-", iter);
if (setjmp(PointPing) == 0)
longjmp(PointPong, 1);
}
}
```
當 Ping 函式被呼叫後，`setjmp` 一樣的會儲存 函式現在的狀態到 `PointPing` 中，然後透過 `longjmp` 去返回到 `Main` 儲存的狀態上。
在 [longjmp](https://man7.org/linux/man-pages/man3/longjmp.3p.html) 裡有提到：
>After longjmp() is completed, program execution continues as if the corresponding invocation of **setjmp() had just returned the value specified by val.** The longjmp() function shall not cause setjmp() to return 0; if val is 0, setjmp() shall return 1.
:::danger
via 或 through 不該翻譯成「通過」，否則無法區分 "pass" 的譯詞。
:::
意思即可以透過 `setjmp` 的返回值來判斷，現在是第一次調用還是通過 `longjmp` 返回。
所以整體流程為 `main -> Ping(儲存狀態) -> main -> Pong(儲存狀態) -> main -> Ping -> Pong -> ...`，完整圖如下。
不過這邊有個有趣的現象是，假設今天把全域變數 `iter` 轉換為局部變數
```diff=27
void Ping(void) {
+ int i;
if (setjmp(PointPing) == 0) {
+ i = 1;
longjmp(Main, 1);
}
while (1) {
printf("Ping (%2d) - ", i);
i++;
if (setjmp(PointPing) == 0)
longjmp(PointPong, 1);
}
}
```
整個輸出結果會變得不一樣，以我的電腦為例：
```shell
$ ./pingpong2 4
Ping (32767) - Pong (32768)
```
裡面有說原因為，當 Ping Pong 兩個函式互相交替時，他們的局部變數只有一個，而導致其實儲存的記憶體位址是相同的，而有了錯亂的現象。
但是這邊我沒有很懂為何我的輸出成果，會跟網站上的不一樣，i 跟 j 的數字跟理想上差很多
:::danger
用 GDB 追蹤。
:::
利用 GDB 追蹤的結果如下：
```shell
$ gdb -q pingpong
(gdb) b 31
Breakpoint 1 at 0x1299: file pingpong2.c, line 31.
(gdb) r 4
31 i = 1;
(gdb) info local
i = 32767
(gdb) stepi
32 longjmp(Main, 1);
(gdb) info local
i = 1
```
跳轉到第二次呼叫 `setjmp(PointPing)`
```shell
(gdb) n
0x0000555555555291 in Ping () at pingpong2.c:30
30 if (setjmp(PointPing) == 0) {
(gdb) print i
$1 = 32767
```
可以發現是在這個時候 i 的值從原本的 1 變成 32767。所以我猜測是否跟 `setjmp` 回歸的狀態有關。閱讀 [動態追蹤 Stack](https://hackmd.io/@sysprog/c-function#%E5%8B%95%E6%85%8B%E8%BF%BD%E8%B9%A4-Stack) 我學習到如何去追蹤程式碼的操作
```shell
$ gdb -q pingpong
(gdb) set disassembly-flavor intel
(gdb) disassemble Ping
Dump of assembler code for function Ping:
0x0000000000001276 <+0>: endbr64
0x000000000000127a <+4>: push rbp
0x000000000000127b <+5>: mov rbp,rsp
0x000000000000127e <+8>: sub rsp,0x10
0x0000000000001282 <+12>: lea rax,[rip+0x2eb7] # 0x4140 <PointPing>
0x0000000000001289 <+19>: mov rdi,rax
0x000000000000128c <+22>: call 0x10a0 <_setjmp@plt>
0x0000000000001291 <+27>: endbr64
0x0000000000001295 <+31>: test eax,eax
0x0000000000001297 <+33>: jne 0x12b4 <Ping+62>
0x0000000000001299 <+35>: mov DWORD PTR [rbp-0x4],0x1
0x00000000000012a0 <+42>: mov esi,0x1
0x00000000000012a5 <+47>: lea rax,[rip+0x2db4] # 0x4060 <Main>
0x00000000000012ac <+54>: mov rdi,rax
0x00000000000012af <+57>: call 0x10b0 <longjmp@plt>
0x00000000000012b4 <+62>: mov eax,DWORD PTR [rbp-0x4]
0x00000000000012b7 <+65>: mov esi,eax
0x00000000000012b9 <+67>: lea rax,[rip+0xd5b] # 0x201b
0x00000000000012c0 <+74>: mov rdi,rax
0x00000000000012c3 <+77>: mov eax,0x0
0x00000000000012c8 <+82>: call 0x1090 <printf@plt>
0x00000000000012cd <+87>: add DWORD PTR [rbp-0x4],0x1
0x00000000000012d1 <+91>: lea rax,[rip+0x2e68] # 0x4140 <PointPing>
0x00000000000012d8 <+98>: mov rdi,rax
0x00000000000012db <+101>: call 0x10a0 <_setjmp@plt>
0x00000000000012e0 <+106>: endbr64
0x00000000000012e4 <+110>: test eax,eax
0x00000000000012e6 <+112>: jne 0x12b4 <Ping+62>
0x00000000000012e8 <+114>: mov esi,0x1
0x00000000000012ed <+119>: lea rax,[rip+0x2f2c] # 0x4220 <PointPong>
0x00000000000012f4 <+126>: mov rdi,rax
0x00000000000012f7 <+129>: call 0x10b0 <longjmp@plt>
End of assembler dump.
```
觀察到在 `<+35>` 行將 i 初始化為 1，並儲存在 `DWORD PTR [rbp-0x4]` 中。直到重新呼叫 `<longjmp@plt>` 後，才會將值加載到 eax 寄裡，因此理論上沒有做更動，追朔到這邊就不知道為何了？
#### [協同式多工](https://hackmd.io/@sysprog/concurrency/%2F%40sysprog%2Fconcurrency-sched#%E5%8D%94%E5%90%8C%E5%BC%8F%E5%A4%9A%E5%B7%A5)
>[coro](https://github.com/MathewSu-001/concurrent-programs/tree/master/coro): 使用 setjmp/longjmp
在一開始， schedule 會透過第 9 行來分別調用任務函式 `task0 -> task0 -> task1` 產生三個不同的 jmp_buf ，並且每次任務函式會因為第一次調用 `setjmp` 回到第 5 行執行下一個 while 迴圈直到 `ntasks-- > 0` 條件失敗。
:::danger
注意書寫規範：
* 使用 lab0 規範的程式碼書寫風格，務必用 clang-format 確認一致
* 注意看[程式碼規範](https://hackmd.io/@sysprog/linux2024-lab0-a)的「clang-format 工具和一致的程式撰寫風格」，筆記列出的程式碼依循指定的風格。
:::
```c=
void schedule(void)
{
static int i;
setjmp(sched);
while (ntasks-- > 0) {
struct arg arg = args[i];
tasks[i++](&arg);
printf("Never reached\n");
}
task_switch();
}
```
schedule 會呼叫 `task_switch(&tasklist)`，其中，會根據 list 的 first entry `longjmp` 回該 task 的 `setjmp` 位置中。
`task0` 的功用為計算 Fibonacci 數；`task1` 為計算次數。由於兩個程式碼大致相同，這邊以 `task0` 做舉例：
```c=
void task0(void *arg)
{
...
if (setjmp(task->env) == 0) {
task_add(task);
longjmp(sched, 1);
}
task = cur_task;
for (; task->i < task->n; task->i += 2) {
if (setjmp(task->env) == 0) {
long long res = fib_sequence(task->i);
printf("%s fib(%d) = %lld\n", task->task_name, task->i, res);
task_add(task);
task_switch();
}
task = cur_task;
printf("%s: resume\n", task->task_name);
}
printf("%s: complete\n", task->task_name);
longjmp(sched, 1);
}
```
在每一次的 for 迴圈當中，會先計算 `Task0` 的 Fibonacci 數，然後透過 `task_add` 將其放回佇列尾部，再透過 `task_switch` 切換到 `Task1`，接著 `Task1` 會重新執行相同的步驟。
:::danger
print 不是「打印」？誰「打」你？
改說「在終端機輸出」或「輸出」
:::
當再次回到 `Task0` 的環境時，由於不是第一次調用 `setjmp`，會跳過 if 條件句的指令，並輸出 `Task 0: resume`。然後繼續下一個 for 迴圈，直到完成該任務。任務完成後，會呼叫 `longjmp(sched, 1)` 跳回 schedule 函式，接著會執行 `task_switch`，切換到尚未執行完的任務。
這邊列出我的疑問：
1. 當 schedule 完成 while 迴圈後，透過 `task_switch` 進入 `Task0` 的 `setjmp` 儲存位置時，理應會由於非第一次呼叫 `setjmp` 而無法進入兩次的 if 條件句指令裡？
2. 當打印出 `Task 0: resume` 後，為何再進入下一次迴圈後，為何 `setjmp(task->env) == 0` 可以成立？
:::info
在重新觀看了 `setjmp` 的描述後，我發現
>Following a successful longjmp(), execution continues as if setjmp() had returned for a second time. **This "fake" return can be distinguished from a true setjmp() call because the "fake" return returns the value provided in val.**
以第一個疑問為例，當 schedule 完成 while 迴圈後，透過 task_switch 進入 Task0 的 setjmp 儲存位置後，`setjmp(task->env)` 會因為 **fake return** 而跳過 if 條件句。
但在進入 for 迴圈後，會因為是重新保存了有關調用環境的各種信息，所以會返回值 0 ，而可以進入 if 條件句裡。
:::
:::danger
作實驗來確認你的說法。
:::
#### [搶佔式多工](https://hackmd.io/@sysprog/concurrency/%2F%40sysprog%2Fconcurrency-sched#%E6%90%B6%E4%BD%94%E5%BC%8F%E5%A4%9A%E5%B7%A5)
>[preempt_sched](https://github.com/MathewSu-001/concurrent-programs/tree/master/preempt_sched): 使用 SIGALRM
整體的程式碼解讀如下：
首先用 `time_init()` 和 `task_init()` 來設置定時器信號處理函式跟設定任務。在 [Setting an Alarm](https://www.gnu.org/software/libc/manual/html_node/Setting-an-Alarm.html) 裡頭有提到：
>You should **establish a handler for the appropriate alarm signal using signal or sigaction** before issuing a call to setitimer or alarm. Otherwise, an unusual chain of events could cause the timer to expire before your program establishes the handler.
因此在 `time_init()` 中會透過 `sigaction` 來建立 SIGALRM 與 `time_handler` 之間的聯繫。
在函式 `taskadd` 中有 `makecontext`，查閱 `man makecontext` 給出下面解釋
>**void makecontext(ucontext_t \*ucp, void (\*func)(), int argc, ...);**
>The makecontext() function modifies the context pointed to by ucp (which was obtained from a call to getcontext(3)). Before invoking makecontext(), the caller must allocate a new stack for this context and assign its address to ucp->uc_stack, and define a successor context and assign its address to ucp->uc_link.
搭配下文
>When this context is later activated (using setcontext(3) or swapcontext()) the function func is called, and passed the series of integer (int) arguments that follow argc.
於是每 10 ms 觸發 `time_handler` ，呼叫 `schedule` 選擇下一個執行的任務，然後透過 `swapcontext` 去切換 context。在這個時候就會激發函式 sort 進行排序。所以透過 `SIGALRM` 可以達到搶佔的作用。
在這邊對於 `timer_wait` 與 `time_handler` 之間的關聯性不是很瞭解。該函式用來實現等待定時器中斷的到來，以觸發排程運行下一個任務。
```c
static void timer_wait(void)
{
sigset_t mask;
sigprocmask(0, NULL, &mask);
sigdelset(&mask, SIGALRM);
sigsuspend(&mask);
}
```
在進行實驗時會發現是觸發一次 `timer_wait` 後，`time_handler` 會觸發四次將三個任務循環過一遍後的一個迴圈，這樣好像就沒有搶佔上的功能？
#### [Go 語言的多工特徵](https://hackmd.io/@sysprog/concurrency/%2F%40sysprog%2Fconcurrency-sched#Go-%E8%AA%9E%E8%A8%80%E7%9A%84%E5%A4%9A%E5%B7%A5%E7%89%B9%E5%BE%B5)
>[channel](https://github.com/MathewSu-001/concurrent-programs/tree/master/channel) 模擬 Go 程式語言的 goroutine 及 channel 機制。
等 atomic 讀完重看程式碼
### [並行程式設計: 執行順序](https://hackmd.io/@sysprog/concurrency/%2F%40sysprog%2Fconcurrency-ordering)
- Sequenced-before
當 A sequenced-before B 時，強調的是 A 的求值必須先完成於 B 的求值之前。
- Happens-before
當 A happens-before B 時，強調的是 A 效果可見，且在 B 之前。與前者不同的是，由於電腦會以最佳化的方式執行程式，所以有可能 B 的 "執行順序" 會在 A 前面，但不影響 A 的效果在 B 執行之前。
- Synchronized-with
就是多執行緒版本的 happens-before。
#### [Peterson's algorithm](https://en.wikipedia.org/wiki/Peterson%27s_algorithm)實作
Sign in with Wallet
Connect another wallet