Linux 核心專題: 並行程式設計

執行人: MathewSu-001
專題解說影片

任務簡介

研讀並行程式設計教材 並動手確認

TODO: 研讀並行程式設計教材

涵蓋概念, 排程器原理, 執行順序, Atomics 操作, POSIX Threads, 實作輕量級的 Mutex Lock, Lock-free 程式設計, 案例: Ring buffer 等議題。在此紀錄你的認知和疑惑，務必動手確認。
對照 Linux 核心專題: 並行程式設計教材修訂，包含其錄影解說。

並行程式設計：概念

(一)並行的重要性

從軟體開發現況裡，可以發現自 2005 年以前， 工程師可以透過提昇 CPU 的時脈來提高程式運行的效能。但自 2005 年後， CPU 的時脈在技術層面上已經無法在提高，所以想要再提高效能，多工與多執行緒成為解法，並行的應用就在此產生。

(二)並行 vs. 平行
在Concurrency (並行) vs. Parallelism (平行)的圖例中，就可以做到很好的解釋。

• 並行：將一個工作拆解成多個讓執行緒可以分工合作，並且是在單個 CPU 上執行。
• 平行：多個工作在多個 CPU 上一起進行，為了達成目的可能會運用到並行。

(三)排程器
在並行上，透過排程器來決定 CPU 下一個所要執行的工作。而溝通的管道分為兩種：

• mutex 確保數個 process 在一個時間點上，只能有一個 process 存取單項資源;
• semaphore 讓數個 producer 與數個 consumer 在計數器的基礎上進行合作;

並行程式設計: 排程器原理

在 Building Coroutines 有簡單示範 setjmp 以及 longjmp 的用法:

注意書寫規範：

• 使用 lab0 規範的程式碼書寫風格，務必用 clang-format 確認一致
• 注意看程式碼規範的「clang-format 工具和一致的程式撰寫風格」，筆記列出的程式碼依循指定的風格。

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.

注意用語：

• call 是「呼叫」，而非「調用」

務必使用本課程教材規範的術語。

所以在第一次呼叫時， setjmp 會返回值 0。

注意書寫規範：

• 使用 lab0 規範的程式碼書寫風格，務必用 clang-format 確認一致
• 注意看程式碼規範的「clang-format 工具和一致的程式撰寫風格」，筆記列出的程式碼依循指定的風格。

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 裡有提到：

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.

via 或 through 不該翻譯成「通過」，否則無法區分 "pass" 的譯詞。

意思即可以透過 setjmp 的返回值來判斷，現在是第一次調用還是通過 longjmp 返回。

所以整體流程為 main -> Ping(儲存狀態) -> main -> Pong(儲存狀態) -> main -> Ping -> Pong -> ...，完整圖如下。

不過這邊有個有趣的現象是，假設今天把全域變數 iter 轉換為局部變數

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); 
  }
}

整個輸出結果會變得不一樣，以我的電腦為例：

$ ./pingpong2 4
Ping (32767) - Pong (32768)

裡面有說原因為，當 Ping Pong 兩個函式互相交替時，他們的局部變數只有一個，而導致其實儲存的記憶體位址是相同的，而有了錯亂的現象。

但是這邊我沒有很懂為何我的輸出成果，會跟網站上的不一樣，i 跟 j 的數字跟理想上差很多

用 GDB 追蹤。

利用 GDB 追蹤的結果如下：

$ 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)

(gdb) n
0x0000555555555291 in Ping () at pingpong2.c:30
30        if (setjmp(PointPing) == 0) {
(gdb) print i
$1 = 32767

可以發現是在這個時候 i 的值從原本的 1 變成 32767。所以我猜測是否跟 setjmp 回歸的狀態有關。閱讀 動態追蹤 Stack 我學習到如何去追蹤程式碼的操作

$ 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 寄裡，因此理論上沒有做更動，追朔到這邊就不知道為何了？

協同式多工

coro: 使用 setjmp/longjmp

在一開始， schedule 會透過第 9 行來分別調用任務函式 task0 -> task0 -> task1 產生三個不同的 jmp_buf ，並且每次任務函式會因為第一次調用 setjmp 回到第 5 行執行下一個 while 迴圈直到 ntasks-- > 0 條件失敗。

注意書寫規範：

• 使用 lab0 規範的程式碼書寫風格，務必用 clang-format 確認一致
• 注意看程式碼規範的「clang-format 工具和一致的程式撰寫風格」，筆記列出的程式碼依循指定的風格。

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 做舉例：

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 會重新執行相同的步驟。

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 可以成立？

在重新觀看了 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 條件句裡。

作實驗來確認你的說法。

搶佔式多工

preempt_sched: 使用 SIGALRM

整體的程式碼解讀如下：

首先用 time_init() 和 task_init() 來設置定時器信號處理函式跟設定任務。在 Setting an Alarm 裡頭有提到：

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 之間的關聯性不是很瞭解。該函式用來實現等待定時器中斷的到來，以觸發排程運行下一個任務。

static void timer_wait(void)
{
    sigset_t mask;
    sigprocmask(0, NULL, &mask);
    sigdelset(&mask, SIGALRM);
    sigsuspend(&mask);
}

在進行實驗時會發現是觸發一次 timer_wait 後，time_handler 會觸發四次將三個任務循環過一遍後的一個迴圈，這樣好像就沒有搶佔上的功能？

Go 語言的多工特徵

channel 模擬 Go 程式語言的 goroutine 及 channel 機制。

等 atomic 讀完重看程式碼

並行程式設計: 執行順序

• 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實作