---
tags: CSAPP, 作業系統
---

# CSAPP: Chapter 12

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

* [Concurrency](http://www.cs.cmu.edu/afs/cs/academic/class/15213-m19/www/lectures/23-concprog.pdf)
* [Synchronization-basic](http://www.cs.cmu.edu/afs/cs/academic/class/15213-m19/www/lectures/24-sync-basic.pdf)
* [Synchronization-advanced](http://www.cs.cmu.edu/afs/cs/academic/class/15213-m19/www/lectures/25-sync-advanced.pdf)
* [Thread-Level Parallelism](http://www.cs.cmu.edu/afs/cs/academic/class/15213-m19/www/lectures/26-parallelism.pdf)
:::

## Concurrency

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

Concurrent programing 並不簡單，有許多經典的問題需要考慮：
* data race: 排程的結果可能導致一個程式每次執行的結果不同，不符合預期
* deadlock: 一個經典的例子是**在 signal handler 中使用 printf** ([signal-safety](https://www.man7.org/linux/man-pages/man7/signal-safety.7.html))

> 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](https://en.wikipedia.org/wiki/Inter-process_communication) 機制來達成，導致了較大的 overhead。

### I/O multiplexing-based (Event-based)

I/O multiplexing 的基本思想是透過 system call [select](https://man7.org/linux/man-pages/man2/select.2.html)，讓 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 也不能充份運用多核的效益。

:::info
:laughing: 有點難翻譯 fine-grained 這東西，或許你可以看看[What does "fine-grained" mean?](https://english.stackexchange.com/questions/8348/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)](https://en.wikipedia.org/wiki/POSIX_Threads) 來實作 thread，其為處理 thread 的一種標準 interface。

> 延伸閱讀：
> * [POSIX thread (pthread) libraries](https://www.cs.cmu.edu/afs/cs/academic/class/15492-f07/www/pthreads.html)
> * [POSIX Threads Programming](https://computing.llnl.gov/tutorials/pthreads/)
## 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](https://en.wikipedia.org/wiki/Producer%E2%80%93consumer_problem)
* [Readers-Writers problem](https://en.wikipedia.org/wiki/Readers%E2%80%93writers_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 就請不要這麼做 :+1:

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

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

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

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

:::info
有點不太會解釋 :cry:，可以參考 [Concurrency系列(五): Sequential Consistency的代價](http://opass.logdown.com/posts/809449-concurrency-series-5-the-price-of-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](https://en.wikipedia.org/wiki/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](https://en.wikipedia.org/wiki/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](https://software.intel.com/content/www/us/en/develop/articles/avoiding-and-identifying-false-sharing-among-threads.html)
> * [Mechanical Sympathy - False Sharing](https://mechanical-sympathy.blogspot.com/2011/07/false-sharing.html)



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