CSAPP: Chapter 12

僅記錄最粗淺的概念，詳細的例子請直接參考原書籍或者課程投影片:

• Concurrency
• Synchronization-basic
• Synchronization-advanced
• Thread-Level Parallelism

Concurrency

Concurrency 的應用是系統上重要的技巧，不僅僅是在 kernel 中運行多個 process 的機制，在應用層級也扮演重要的角色。

Concurrent programing 並不簡單，有許多經典的問題需要考慮：

• data race: 排程的結果可能導致一個程式每次執行的結果不同，不符合預期
• deadlock: 一個經典的例子是在 signal handler 中使用 printf (signal-safety)

When performing buffered I/O on a file, the stdio functions must maintain a statically allocated data buffer along with associated counters and indexes (or pointers) that record the amount of data and the current position in the buffer.

Suppose that the main program is in the middle of a call to a stdio function such as printf(3) where the buffer and associated variables have been partially updated. If, at that moment, the program is interrupted by a signal handler that also calls printf(3), then the second call to printf(3) will operate on inconsistent data, with unpredictable results.

如果主程式在處理 I/O 時被打斷，此時主程式拿著資源在等待 signal handler 處理完，而 signal handler 中的 printf 在等待該資源而無法進行，就產生了 deadlock。

• Livelock / Starvation / Fairness: 排程可能會導致某個 process 的進度無法推進。

然而好的 concurrency 可以透過恰當的安排執行流程，減少 CPU 把時間花在不必要的等待(等待 I/O、等待可以被推遲的任務等等)。

在應用層級使用 concurrency 的程式稱為 concurrent program，根據架構大致可以分成三種方法：

• Process: 每個 logical flow 都是一個 process，由 kernel 來調度，每個 flow 都擁有獨立的定址空間
• I/O multiplexing: 由應用程序自行調度 logical flow，所有的 flow 會共用同一個 address space
• Thread: thread 可以視為是上述兩種方法的混合，像 process 一樣由 kernel 來調度 logical flow，但是像 I/O multiplexing 一樣每個 flow 會共用同一個 address space

Process-based

Process 是構築 concurrency 最容易的方法，以 server 為例，當 parent process 接收的 client 的連接請求時，就為它建立一個 child process 來提供服務。

Process 擁有非常清晰的共享模型： 共享 file table，卻不共享 address space(file descriptor、global variables)。不共享定址空間表示一個 process 不會輕易的不小心更動到另一個 process 的內容;另一方面，也使得 process 間的共享信息更加困難，需要透過 IPC 機制來達成，導致了較大的 overhead。

I/O multiplexing-based (Event-based)

I/O multiplexing 的基本思想是透過 system call select，讓 kernel block 整個 process 後，使 kernel 可以監聽多個 file descriptor。只有在一個或者多個 I/O 事件發生時，才返回到應用程序。

select() allows a program to monitor multiple file descriptors, waiting until one or more of the file descriptors become "ready" for some class of I/O operation (e.g., input possible).

由於 I/O multiplexing 是在單一個 process 下運作的，address space 直接被所有的 flow 共享，使得數據的共享變得簡單，因此也利於使用 debugger 來除錯。且不需要切換 process 或 thread 來調度 flow，可以減少因此產生的 overhead。此外，基於應用程序層調度 flow，也就代表程式撰寫者可以更容易的控制 flow 的切換。

但是反過來說，也就表示程式撰寫者需要思考如何切換 flow，顯然在 coding 上就變得比較困難。如何設計出 fine-grained 的 concurrency 是一個難解的議題。舉例來說，以一個 event-based 的 server 為例，如果有一個事件切換的條件(回到 select)是讀完一個完整檔案(例如直到 EOF)，那麼惡意的攻擊者可以只發送部份的文件然後就停止，進而導致 server 無法服務其他 client。由於是基於單個 process 的設計，I/O multiplexing 也不能充份運用多核的效益。

有點難翻譯 fine-grained 這東西，或許你可以看看What does "fine-grained" mean?

Thread-based

在現代的作業系統中，一個 process 中被允許運行多個 thread ，thread 可以由 kernel 來排程，擁有自己的 thread context，包含自己獨立的 thread ID(TID)、stack(然而同 process 下 thread 的互相存取並不受保護)、program counter、general purpose register，但同一個 process 下的 thread 共享整個 virtual address space，因此 shared library、heap、code section、data section 等都被共享。

Thread 和 process 有許多相近之處：每個單元各自都是獨立的 logical flow、都是可以被 context switch 的單元。然而 thread 可以共用一個 virtual address space，共享 code 和 data section，也因此 thread 的使用成本比 process 小(context switch 時不需要切換 page table 等優勢)

在 linux 系統上可以使用 Posix thread(Pthread) 來實作 thread，其為處理 thread 的一種標準 interface。

延伸閱讀：

• POSIX thread (pthread) libraries
• POSIX Threads Programming

Synchronization

由於 Thread 可以由 kernel 來排程，卻又可共享資源的原因，對於程式撰寫者來說是極具吸引力的 concurrency model。然而，為了寫出正確的 multi-thread 程式，我們需要了解哪些資源是被共享的，在 multi-thread 的情境下，答案並非 global variables 是共享而 stack-variables 不共享這麼單純(因為共享的 address space)。我們需要考量：

• thread 的 memory model 是甚麼？
• 根據這個 model，variables 怎麼 mapping 到 memory？
• 多少個 thread reference 這些 instances?

Thread memory model

從 thread 的概念來說，運行在一個 process context 中的 concurrent thread 擁有自己的 id、stack、stack pointer、program counter、general purpose register， 而共享 code、heap、shared library 等等。

從實際的運作的角度來說，一個 thread 無法去存取另一個 thread 的 register。另一方面，任何 thread 都可以去存取 virtual address space 下的所有位址。

由於 thread 可以存取任何的定址位址，因此可能會導致一些錯誤與誤解。一般來說，每個 thread stack 是專屬所在的 thread 存取的。但是如果一個 thread 以某種方式得到了指向其他 thread stack 的 pointer，則他可以讀寫這個 stack 的任何部份。

以上圖的程式為例，msgs 雖然是放在 main thread 的 stack 中，但是由於 global pointer ptr，peer thread 可以間接存取到 main thread 的 stack。

Mapping Variables instances to memory

multi-thread 的 C 程式中變量根據其儲存的類型被 mapping 到 virtual address:

• global variables: 定義在 function 之外的 variables。virtual memory 中只會有一份，且任何 thread 都可以使用
• local variables: 在 function 內且沒有用 static 修飾的 variables。每個 thread stack 對於一個 local variables 都會各自擁有一份
• local static variables: 在 function 內且透過 static 修飾的 variables。和 global variables 一樣，在 virtual memory 中只有一份，區別在於 local static variables 只能在宣告的 scope 中被操作

Thread 的同步機制

Shared variables 帶來了便利性，但也可能導致非程式撰寫者預期的錯誤的行為。

在以下的範例中，看起來 cnt 會被兩個 thread 加 niters 次，所以理論上只會印出 OK cnt=...。然而每次的執行結果可能會不同，為甚麼呢？

我們可以透過下面的 assembly code 看到原因。

由於 cnt++ 的行為可以被拆解成

1. $L_i$ : 把 cnt 讀到 register
2. $U_i$ : 把 register 上的數值加一
3. $S_i$ : 把 register 數值存回 cnt
   三道步驟。

如前面所說，因為 multi-thread 的 register 非共享但是定址空間是，因此這三個步驟會是一個 critical section，為保持程式的行為符合預期，不應該和其他 thread 的 critical section 交互執行。

為了保證程式正確的執行，必須以某種方式同步 thread，保護 critical section 達到 mutually exclusive access，一種經典的方法為 Semophores。

Semophores

Semophores s 是一個非負的 global interger，並只能透過 P 和 V 兩種操作來處理:

• P(s):

  • 如果 s 為非零，則將 s 減一且立刻 return
  • 如果 s 為零，則 thread 會被 suspend，直到有 V 被執行時重啟，將 s 減一後 return

• V(s):

  • 將 s 加一
  • 如果有任何 thread 在被 block 的狀態，則重啟其中一個，並完成它的 P 操作

Semophores 對 s 的加減操作、判斷是否為零被保證是不可分割的(load -> add/sub -> store 之間沒有中斷)，因此可以被用來實現互斥。

我們可透過將每個共享變數和一個 Semaphore(初始為 1)聯繫起來，然後用 P 和 V 將 critical section 包圍的方式得到保護的效果。

Semaphore 的應用可以延伸到兩個經典的議題:

• Producer-Consumer problem
• Readers-Writers problem
  • First readers–writers problem
  • Second readers–writers problem

Concurrency issues

Race

當一個程式的正確性依賴於 thread A 必須在thread B 到達 y 前先抵達 x 時，就發生了 race。

從上面的程式為例，我們預期 thread 的輸出 pattern 是

Hello from thread 1
Hello from thread 2
...
Hello from thread N-1
Hello from thread N

如果你足夠幸運，也許可以得到這個輸出，但情況並非總是如此。因為 Pthread_create 傳遞的參數 i 是在 main thread 的 stack 上，因此所有的 thread reference 的會是同一個位址。這就導致當 thread 1 創建時的參數雖然是 1，但是如果尚未執行至 dereference vargp 前又建立了 thread 2，則 thread 的參數就會被更動成 2。

解決問題的方法是為輸入參數在 heap 上建立一個新的空間，注意 thread 需為此進行釋放以避免 memory leak。

Deadlock

顯而易見的，由於兩個 thread 對 mutex 的使用順序不一致，想像當 thread 0 先拿了 mutex 0，thread 1 又拿了 mutex 1，此時 thread 0 在等 mutex 1，thread 1 在等 mutex 0，產生 deadlock。

解決的方法?就是讓資源的要求保持既定的順序。

Thread safe

對於一個 function，如果被多個 thread 反覆呼叫仍能得到正確的結果，則為 thread safe，反之則非。

非 thread safe 的 function 可以分成四類:

• 未對共享的變數進行保護

  • 解決方法： 使用 semaphore 等機制保護共享變數
  • 缺點： 同步操作可能影響執行的時間

• 函數的結果依賴前一次呼叫的狀態

  • 舉例來說，這個 random 的實作：
    

    如果是在單一的 thread 下，設定固定的 seed，rand() 產生的亂數就會呈現固定的 pattern。然而多執行緒的狀況下，因為排程結果的不確定性，產生亂數的 pattern 自然也就無從得知。

  • 解決方法： 把 thread 各自的狀態作為參數傳遞
    

• 回傳 static pointer

  • 
    由於回傳的是一個 static pointer，表示其在記憶體中實際上只有一份，如果 thread A 得到 return 而尚未使用前，thread B 進入函式更動了其內容，thread A 上的結果也會產生改變
  • 解決方法：
    1. 重寫函式讓其接受傳入地址並把回傳值寫在上面(但是 caller 跟 callee 都要修改，對於使用函式庫來說就比較不方便)
    2. lock and copy: 只需要更動 caller，在得到回傳結果時先鎖住並複製一份。需注意額外配置空間的釋放。

• 使用非 thread safe 的 function

  • 解決方法： 想要 thread safe 就請不要這麼做

Reentrant function

在 thread safe function 中有一種類型稱為 reentrant function。當他們被多個 thread 使用時，不會使用任何共享資料。

reentrant function 不需要同步機制，因此可以有更高效的運行機制。

Memory Consistency

對於以下的程式架構，會印出甚麼結果呢？

事實上，這取決於硬體的 memory model，也就是程式邏輯對應硬體的行為。一種最直覺的模型稱為 Seqential consistency，在這種模型下，每個獨立的處理單元，執行時都維持程式的順序，而處理單元間則會交錯執行。

有點不太會解釋

，可以參考 Concurrency系列(五): Sequential Consistency的代價)

在 Sequentila model 下，因為在任何一個 print 以前 a 和 b 其一一定會有一個發生 assign，因此不可能得到 1 100 或者 100 1 的輸出結果。

然而如果是在 non-coherent cache 的情境下，thread 1 和 thread 2 使用不同的 cache 和相同的 memory 但不同的 cache，且 assign 的結果不會立刻寫回 memory，則情況和上面的例子並不相同，如下圖：

Snoopy cache 是可以應對此問題的機制。

Parrell

在現代的多核心電腦下，我們可以透過平行來加速程式的運行，然後並非總是用上最多的 CPU 就可以得到最快的速度，有許多值得考量的點。

以上面的程式為例，我們是有機會得到錯誤的結果的。原因就如同前面所說，因為 global_sum += i 涉及 load global_sum 到 register -> register = register + i -> store register 回 global_sum 的過程。一旦 for 迴圈中每個 global_sum += i 的這三個步驟交錯執行就可能得到錯誤的結果。

解決方法很容易，我們可以透過前面提到的 semaphore 來保護 critical section。

但是從上面的圖可以看到，使用 semaphore 或者 mutex 來保護執行的正確性是有成本的，其中 semaphore 和 mutex 的成本也不相同。

往下的另一個實驗，我們可以不要讓 thread 把 sum 的結果放在共享的變數中，而是先把各自計算的結果放在不同的地方，在 main thread 再把這些結果加總起來就好了。如此一來，就不需要對變數做互斥了。那實驗中也比較了把結果放在連續的位置上(contiguous array)，或者是空間有稍微分開的位置上(spaced-apart array)。

從這個實驗裡可以看出一些有趣的現象，放在連續的 array 上的結果竟然效益沒有比稍微分開的 array 上的結果來得好!難道以前說的 locality 是騙人的嗎?

這個現象的原因來自 false sharing。在多核心的架構下，如果有多個 CPU access 相同的記憶體位置，當 CPU A 更動了自己對應該記憶體位置的 cache line 內容，為了保證 cache 中資料的正確性，cache invalidate 會發生，把其他 CPU 上的 cache line 也更新成 CPU A 更動後的結果。

而 false sharing 就是因為 cache 的這個特性導致的。舉例來說，因為 psum0 到 psum 7 對應同一個 cache line，psum0 的更新會導致需要更新 psum1 到 psum7 的 CPU 要做 cache invalidate，即使我們知道 psum0 的更新和 psum1 到 psum7 的正確性是沒有關係的，但因為他們對應同一個 cache line，而導致了 cache invalidate 的啟動，造成額外的成本。

延伸閱讀:

• Avoiding and Identifying False Sharing Among Threads
• Mechanical Sympathy - False Sharing

如果把 sum 的結果先透過 register (local variable)儲存，再把結果寫到 psum，可以減少對 memory 的存取，可以增加程式執行的效率。