並行程式設計: 執行順序

--- tags: concurrency --- # [並行程式設計](https://hackmd.io/@sysprog/concurrency): 執行順序 > 資料整理: [jserv](https://wiki.csie.ncku.edu.tw/User/jserv) ## 為何關注執行順序？多執行緒環境下，程式會出問題，往往在於執行順序的不確定性。一旦顧及分散式系統 (distributed systems)，執行順序和衍生的時序 (timing) 問題更加複雜。我們將從如何定義程式執行的順序開始說起，為了簡單起見，我們先從單執行緒的觀點來看執行順序這件事，其中最關鍵知識就是 `Sequenced-before`，你將會發現就連單執行緒的程式，也可能會產生不確定的執行順序。要了解 `sequenced-before`，首先要理解 evaluation(求值)。 ## Evaluation (求值) 所謂求值，其實指二件事情，一是 value computations，對一串運算式計算的結果；另一是 side effect，亦即修改物件狀態，像是修改記憶體內變數的值、呼叫函式庫的 I/O 處理函式之類的操作。對於 C 程式語言來說，語言層級並沒有定義運算元的求值順序，因此像是 `f1() + f2() + f3()` 這種敘述，編譯器可自行決定要先計算哪一個函式，之後再按照加法運算子的 left-to-right associativity 從左邊加到右邊。因此計算結果看起來會像 `(f1() + f2()) + f3()`，但執行時 `f3()` 可以是第一個、第二個、或是最後才被呼叫。 ## Sequenced-before `sequenced-before` 是種對同一個執行緒下，求值順序關係的描述。 * 若 A is sequenced-before B，代表 A 的求值會先完成，才進行對 B 的求值 * 若 A is not sequenced before B 而且 B is sequenced before A，代表 B 的求值會先完成，才開始對 A 的求值。 * 若 A is not sequenced before B 而且 B is not sequenced before A，代表兩種可能，一種是順序不定，甚至這兩者的求值過程可能會重疊（因為 CPU 重排指令交錯的關係）或不重疊。而程式語言的工作，就是定義一連串關於 `sequenced-before` 的規範，舉例來說：以下提到的先於、先進行之類的用詞，全部的意思都是 `sequenced-before`，也就是「先完成之後才開始進行」 * 上一行的求值 (包含 value computations 和 side effect)，會先於下一行的求值。（所以你寫的程式會看起來像是上一行的效果發生完，才執行下一行） * 運算元的 value computation 會先於運算子的 value computation（所以 `f1() + f2()` 會先計算完 `f1()` 和 `f2()`，才計算兩者加起來的結果），這條規則並不包含 side effect * `i++` 這類的後置運算子，value computation 會先於 side effect * `++i` 這類的前置運算子，side effect 會先於 value computation * `&&`, `||` 這類的運算子，有著比較特殊的例外，左邊的運算元的 evaluation 會先於右邊的 evaluation。因此 `i++ && (i + j)`，右邊的 `i` 會是副作用產生後的結果。 * 對於 assignment operator 而言 (`=`, `+=`, `-=` 一類)，會先進行運算元的 value computation，之後才是 assignment 的 side effect，最後是整個 assignment expression 的 value computation。儘管我們定義許多 evaluation order 的規則，但語言依舊保留一些未定義的行為。舉例來說，像是經典的 C 語言未定義行為: ```c i = i++ ``` 最後到底 `i` 是什麼，沒辦法事先準確告知，這取決於編譯器和執行環境。將 `sequenced-before` 的關係畫成下圖: ![](https://i.imgur.com/ex3xMob.png) 將每個求值運算的過程和 `sequenced-before` 的關係標出，會有如下的關係: ![](https://i.imgur.com/6D8EBmH.png) 可看到問題在於，`i++` 的 side effect 只 `sequenced-before` `i++` 本身的運算結果，這個 side effect 可能發生在 assignment 之前或之後，我們並未定義其順序關係，因此讓整行程式產生不確定的行為。延伸閱讀:〈[你所不知道的 C 語言: 未定義行為篇](https://hackmd.io/@sysprog/c-undefined-behavior)〉 > 注意: 在 `C++17` 後，上方敘述不是未定義行為 > 假設 i 初始值為 0，由於 `=` 在 `C++17` 後為 sequenced，因此 `i++` 的計算與 side effect 都會先完成，所以 `i++` 得到 `0`，隨後 side-effect 導致 i 遞增 1，因此此時 i 為 1；之後執行 `i =` 這邊，所以利用右側表達式的值來指定數值，亦即剛才的 `0`，因此 i 最後結果為 0。所以 i 值轉變的順序為 $0 \to 1 \to 0$，第一個箭頭為 side effect 造成的結果，第二個則是 `+=` 造成的結果。 sequenced-before 具備非對稱性 (asymmetric) 及遞移性 (transitive) 的性質: for all a, b, and c in P, we have that: * if a < b then ¬ (b < a) (asymmetry) - 舉例來說，實數範圍內的小於就是一種 asymmetry 的關係，因為如果 $a < b$ 的話，必然 $b \nless a$，而實數範圍的小於等於就不是種 asymmetry 的關係，因為 $x \leq x$，反之亦成立 * if $a < b$ and $b < c$ then $a < c$ (transitivity) ### Sequenced-before 參考資訊 * [C++ sequenced-before graphs](http://josephmansfield.uk/articles/c++-sequenced-before-graphs.html) * 對於 sequenced-before 提供清楚簡易的解釋 * [Order of evaluation from cppreference](http://en.cppreference.com/w/cpp/language/eval_order) * sequenced-before 明確的定義和規範 * [Undefined behavior and sequence points from stackoverflow](http://stackoverflow.com/questions/4176328/undefined-behavior-and-sequence-points) * Sequenced before 的數學性質解釋 ## Happens-before > 短片: [Happened Before Relationship](https://youtu.be/gGilgOSYbaI), [Happened Before Relation (cont)](https://youtu.be/q-CwESo9UsM) [Java 的官方文件](https://docs.oracle.com/javase/specs/jls/se17/html/jls-17.html#jls-17.4.5)對 Happens-Before 的定義: > If one action happens-before another, then the first is visible to and ordered before the second. 當行為 A happens-before B 時，代表 A 的效果可見 (visible)，而且發生於 B 之前。換言之，若望文生義說 "Happens-Before" 是「先行發生」，那就南轅北轍。Happens-Before 並非說前一操作發生在後續操作的前面，它真正要表達的是：「前面一個操作的效果對後續操作是==可見==」。 Jeff Preshing 提出較通俗的解釋。 > Let A and B represent operations performed by a multithreaded process. If A *happens-before B*, then the memory effects of A effectively become *visible* to the thread performing B before B is performed. 說明前一個操作的效果在後一個操作執行之前必須要==可見==。舉例來說，考慮下方的 Java 程式: ```java= int A, B; void foo() { // This store to A ... A = 5; // ... effectively becomes visible before the following loads. B = A * A; } ``` 在上述程式碼中，第 5 行的效果必須在第 8 行之前==可見==，方可確保 `B` 正確地取得 `25` 這數值。這似乎很合理，不是嗎？按照一般的認知，應該是先執行前面的敘述，然後才執行後面的敘述，對吧？但事實未必如此！這裡的關鍵是，Happens-before 強調 visible，而非實際執行的順序。實際程式在執行時，只需要「看起來有這樣的效果」即可，編譯器有很大的空間可調整程式執行順序，亦即 [compile-time memory ordering](https://en.wikipedia.org/wiki/Memory_ordering#Compile-time_memory_ordering)。舉例來說，下面的 C 程式 (檔名 `file.c`): ```c int A = 0, B = 0; void foo() { A = B + 1; // (1) B = 1; // (2) } int main() { foo(); } ``` 如果執行 `gcc -O0 file.c` (抑制最佳化)，產生的 x86-64 組合語言輸出: ```c movl B(%rip), %eax addl $1, %eax movl %eax, A(%rip) movl $1, B(%rip) ``` 可發現先把 B 放到 eax 暫存器，之後 eax + 1 放到 A，然後才執行 `B = 1`。但若執行 `gcc -O2 file.c` (開啟常見最佳化): ```c movl B(%rip), %eax movl $1, B(%rip) addl $1, %eax movl %eax, A(%rip) ``` 可見機械碼變成先把 B 放到 eax，接著把 `B = 1`，再執行 eax + 1，最後才把結果存到 A。換言之，**B 比 A 更早先完成**。但這違反 happens-before 的關係嗎？沒有！因為 happens-before 只關注是否看起來有這樣的效果，從外界看起來，就彷彿是先執行第一行，完成之後，再執行第二行。因此我們得知一個關鍵概念: A happens-before B 不代表實際上 A happening before B (注意時態，後者強調進行中，前者則是從結果來看)，亦即只要 A 的效果在 B 執行之前，對於 B 是 visible 即可，實際的執行順序不用細究。建立初步的 happens-before 認知後，我們來看 C 語言的規範。C99 制訂時，並行程式設計尚未納入到語言的標準，[C11](http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1570.pdf) 則正式涵蓋並行和 memory order 相關的規範，其中 §5.1.2.4/7 定義 **modification order**，如下: > All modifications to a particular atomic object M occur in some particular total order, called the modification order of M. If A and B are modifications of an atomic object M, and A happens before B, then A shall precede B in the modification order of M... §5.1.2.4/7 提到以下： 1. particular total order 2. 假設 A 和 B 代表對 **atomic object** M 的 modification，然後 A happens before B ${\Rightarrow}$ 對於 M 的 modification order，**A 會先於 B** 前述 particular total order 是什麼？ > All modifications to a particular atomic object M occur in some **particular total order** 數學上的 [total order](https://en.wikipedia.org/wiki/Total_order) 是指一個集合裡的二元關係 (在數學上可簡稱「關係」)，其具備以下三個特性： - 反對稱 ([antisymmetric](https://en.wikipedia.org/wiki/Antisymmetric_relation)) ${\displaystyle \forall a, b\in X, \ aRb \ and \ bRa\;\Rightarrow \;a=b}$ - 遞移 ([transitive](https://en.wikipedia.org/wiki/Transitive_relation)) ${\displaystyle \forall a,b,c\in X,\ aRb\ and \ bRc\;\Rightarrow aRc}$ - 連通 ([Connected](https://en.wikipedia.org/wiki/Connex_relation)) ${\displaystyle \forall a, b\in X, \ \displaystyle aRb}$ or ${\displaystyle bRa}$ 這三個特性如果從 modification order 的角度來看會怎樣？假設 A, B, C 各自代表**一個 atomic object 的 modification**，底下就可用 `binary relation` ${R}$ 來表示 **happens-before relation** - ${\displaystyle \forall A, B, C\in X}$ - ${\ R(A, B)}$ and${\ R(B, A)}$ ${\Rightarrow \;A=B}$. - ${\ R(A, B)}$ and${\ R(B, C)}$ ${\Rightarrow \ R(A, C)}$ - ${\ R(A, B)}$ or${\ R(B, A)}$ 回到 §5.1.2.4/7 所說的 particular total order，假設其中一種 `total order` 如下圖： ```graphviz digraph G { rankdir="LR"; A -> B -> C; } ``` > 上圖僅展現 total order，而非 modification order 初始條件: - 二元關係 ${R}$ 表示 **happens-before** 關係 - ${\displaystyle A, B, C\in X}$ - ${\displaystyle (A, B), (B, C), (A, C)\in R}$ 逐一檢視這幾個 modification 的順序是否符合 total order 的定義 - ${(A, B)}$, ${(B, A) \in R}$ ${\Rightarrow \ A=B}$ - ${(B, A) \notin R}$, ${(C, B) \notin R}$, ${(C, A) \notin R}$ - ${(A, B)}$, ${(B, C) \in R}$ ${\Rightarrow \ (A, C) \in R}$ - trivial - ${(A, B) \in R}$ or ${(B, A) \in R}$ - ${(A, B) \in R \Rightarrow (B, A) \notin R}$ - ${(B, C) \in R \Rightarrow (C, B) \notin R}$ - ${(A, C) \in R \Rightarrow (C, A) \notin R}$ 至此，確立 ${A, B, C}$ 這三個 modification 的 happens-before 關係符合 total order 的定義。因此 ${A, B, C}$ 的 modification order 符合規格書的順序就會是 ${A \rightarrow B \rightarrow C}$。考慮以下 C11 程式碼: (檔名: `atomic.c`) ```c #include <stdatomic.h> atomic_int a = ATOMIC_VAR_INIT(0), b = ATOMIC_VAR_INIT(0); int c, d; void test_atomic() { atomic_fetch_add(&b, 5); atomic_store(&a, b); b = ATOMIC_VAR_INIT(42); } void test(){ c = d + 5; d = 42; } int main(int argc, char **argv) { test(); test_atomic(); return 0; } ``` 在 x86-64 使用 GNU toolchain 編譯。 - [ ] 抑制最佳化 ```shell $ gcc -std=c11 -O0 -S atomic.c ``` - [ ] 開啟最佳化 ```shell $ gcc -std=c11 -O2 -S atomic.c ``` 對照 `test` 函式對應的指令序列: (省略[呼叫慣例](https://en.wikipedia.org/wiki/Calling_convention)所需的指令) | 抑制最佳化 | 開啟最佳化 | |:------------|:---------| | `addl $5, %eax` | `movl d(%rip), %eax` | | `movl %eax, c(%rip)` | `movl $42, d(%rip)` | | `movl $42, d(%rip)` | `addl $5, %eax ` | 對照 `test_atomic` 函式對應的指令序列: (省略[呼叫慣例](https://en.wikipedia.org/wiki/Calling_convention)所需的指令) | 抑制最佳化 | 開啟最佳化 | |:------------------------|:------------------------| | `lock addl $5, b(%rip)` | `lock addl $5, b(%rip)` | | `leaq a(%rip), %rax` | `movl b(%rip), %eax` | | `movq %rax, -16(%rbp)` | `xchgl a(%rip), %eax` | | `movl b(%rip), %eax` | `movl $42, %eax` | | `movl %eax, -24(%rbp)` | `xchgl b(%rip), %eax` | | `movl -24(%rbp), %eax` | | | `movl %eax, -20(%rbp)` | | | `movl -20(%rbp), %eax` | | | `movl %eax, %edx` | | | `movq -16(%rbp), %rax` | | | `xchgl (%rax), %edx` | | | `movl $42, -20(%rbp)` | | | `movl -20(%rbp), %eax` | | | `xchgl b(%rip), %eax` | | 在 x86(-64) 指令集架構中，`lock` 開頭用以標示其後的指令轉變為 atomic 操作，支援 ADD, ADC, AND,BTC, BTR, BTS, CMPXCHG, CMPXCH8B, DEC, INC, NEG, NOT, OR, SBB, SUB, XOR, XADD 及 XCHG 等。注意: XCHG 和 XADD 指令本身就是 atomic，但亦可用 `lock` 標示。接著思考開啟最佳化後，GNU Toolchain 產生的指令序列是否違反 happens-before，這問題等同於詢問： > `atomic.c` 編譯後是否符合 modification order？依據 [C11 規格](http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1570.pdf)<sub>(§5.1.2.4/7)</sub> 對 modification order 的定義 > If A and B are modifications of an atomic object M, and A happens before B, then A shall precede B in the modification order of M... 假設 $A$ 和 $B$ 是對 atomic object 的 modification，於是 $A$ happens before $B$ ${\Rightarrow}$ $A$ 的 modification order 在 $B$ 的前面。因此開啟編譯器最佳化後，仍符合 modification order。 [total order](https://en.wikipedia.org/wiki/Total_order) 關係是**滿足全序關係的集合**，在全序集中，元素任意一對都可比較。回顧 [C11 規格](http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1570.pdf) §5.1.2.4/7 定義的 modification order - 有一個全序集，裡面的元素都是**對 atomic object 的 modification**，這個全序集上的二元關係就是 happens-before - 因為**任意一對**元素都是可以比較的，所以，任意兩個 `modification` $A$, $B$，比較的結果可以是 $A$ happens before $B$ 也可以是 $B$ happens-before $A$。 - 若 $A$ happens-before $B$ 且 $B$ happens-before $A$ $\Rightarrow$ $A$ = $B$ - 若 $A$ happens before $B$ $\Rightarrow$ $A$ 的 modification order 會在 $B$ 之前。再來看 [C++ 的定義](http://en.cppreference.com/w/cpp/atomic/memory_order#Happens-before): > Regardless of threads, evaluation A happens-before evaluation B if any of the following is true: > 1. A is sequenced-before B > 2. A inter-thread happens before B 在 C++ 的解釋中，Happens-before 包含兩種情況: 1. 同一個執行緒內的 happens-before 關係 2. 不同執行緒之間的 happens-before 關係。通常程式開發者逐行撰寫程式，期望前一行的效果會影響到後一行的程式碼。稍早已解釋何謂 Sequenced-before，現在可注意到，Sequenced-before 實際就是同一個執行緒內的 happens-before 關係。然而，涉及多個執行緒的情況下，若無法確保 happens-before 關係，程式往往會產生意料之外的結果。舉例來說 ```c int counter = 0; ``` 現在有二個執行緒同時執行，執行緒 A 執行 `counter++`，執行緒 B 把`counter` 的值印出來。因為這二個執行緒不具備 happens-before 的關係，沒有保證 `counter++` 後的效果對於印出 `counter` 是可見的，導致印出來的結果可能是 `1`，也可能是 `0`。因此，程式語言必須提供適當的手段，讓程式開發者得以建立跨越執行緒間的 happens-before 的關係，如此一來才能確保程式執行的結果正確。這也就是剛剛 C++ happens-before 定義裡的第二點，A inter-thread happens before B。 ### Inter-thread happens before Java 定義清楚用何種語法能夠建立 happens-before 的關係。C++ 定義 5 種情況都能夠建立跨執行緒之間的 happens-before，如下: 1. A synchronizes-with B (A 和 B 有適當的同步) 2. A is dependency-ordered before B (A 和 B 有相依的順序關係) 3. A synchronizes-with some evaluation X, and X is sequenced-before B 4. A is sequenced-before some evaluation X, and X inter-thread happens-before B 5. A inter-thread happens-before some evaluation X, and X inter-thread happens-before B 其中第 3, 4, 5 點都是遞迴定義，因此我們只關注第 1 和第 2 點。 Happens-Before 參考資訊 * [C++ Memory Order之Happens-Before](http://en.cppreference.com/w/cpp/atomic/memory_order#Happens-before) * [Java Happens-Before Order](https://docs.oracle.com/javase/specs/jls/se7/html/jls-17.html#jls-17.4.5) * [The Happens-Before Relation in Preshing's Blog](http://preshing.com/20130702/the-happens-before-relation/) ## Synchronized-with synchronized-with 是個發生在二個不同執行緒間的同步行為，當 A synchronized-with B 時，代表 A 對記憶體操作的效果，對於 B 是可見的。而 A 和 B 是二個不同的執行緒的某個操作。不難發現，其實 synchronized-with 就是跨越多個執行緒版本的 happens-before。 ### 從 Java 切入在多執行緒的執行環境中，要如何確定執行緒 A 執行 `someVariable = 3`，且其他執行緒得以看到 `3` 真的被寫入指定的變數 `someVariable` 呢? 有很多原因會讓其他執行緒無法立刻看到 `someVariable` 設定為 `3`，以下列舉部分原因： * 編譯器進行指令重排 (instruction reorder)，提升程式執行效率 * `someVariable` 還在暫存器中、或是被處理器更新到 cache，但尚未寫到主記憶體中 * 其他執行緒嘗試讀取 `someVariable` 時，讀到舊的 cache 資料因此，Java 必須要定義一些特殊的語法，像是 `volatile`, `synchronized`, `final`，以確保針對同一個變數的跨越執行緒記憶體操作能夠正確的同步。 - [ ] synchronized 關鍵字 ```java public class SynchronizedCounter { private int c = 0; public synchronized void increment() { c++; } public synchronized void decrement() { c--; } public synchronized int value() { return c; } } ``` 可以看到上面的程式碼中，每個方法前面都有關鍵字 `synchronized`，該關鍵字的效果如下: * Mutual Exclusive > 對同一個物件而言，不可能有二個前綴 `synchronized` 的方法同時交錯執行，當一個執行緒正在執行前綴 synchronized 的方法時，其他想執行 synchronized 方法的執行緒會被阻擋 (block)。 * 確立 Happens-before 關係 > 對同一個物件而言，當一個執行緒離開 synchronized 方法時，會自動對接下來呼叫 synchronized 方法的執行緒建立一個 Happens-before 關係，前一個 synchronized 的方法對該物件所做的修改，保證對接下來進入 synchronized 方法的執行緒可見。要確保這件事情，代表 JVM 必須要做兩件事，一是在離開 synchronized 區段時，把 local processor 的 cache 寫入到記憶體內，另一是在進入下一個 synchronized 前，要讓 local cache 失效 (invalidate)，使處理器重新去主記憶體抓正確的值。這樣才能夠確保每次進入 synchronized 區段時，物件的狀態是最新的。 - [ ] volatile 關鍵字若你將物件內的變數宣告為 volatile，那麼不同執行緒對該變數的讀寫，會讀到最新寫入的數值。用正式術語描述是: > A write to a volatile field happens-before every subsequent read of that same volatile - [ ] thread create/join Java 在建立新的執行緒時，也會建立起跨執行緒的 happens-before 關係 (其實就是 synchronized-with)。當執行緒 A 呼叫 `Thread.start` 建立執行緒 B 時，執行緒 A 呼叫 `start` 之前，對記憶體產生的影響對於執行緒 B 可見。當執行緒 A 要結束時，執行緒 B 呼叫 `Thread.join` 等待執行緒 A 結束，此時也會建立起跨執行緒的 happens-before 關係，執行緒 A 結束前對記憶體的影響對於呼叫 `join` 之後的執行緒 B 可見。 #### 圖解 ![](https://i.imgur.com/BWLFl2m.png) 左邊執行緒 A 確保每一行都 happens-before 下一行，右邊的執行緒 B 也確保每一行都 happens-before 下一行，因此如果我對 unlock M 和 lock M 建立 synchronized-with (或說，跨執行緒的 happens-before) 的關係，那麼所有 unlock M 之前的效果，對於 lock M 之後都可見。 ### C++ 的觀點 Java 力求隱藏各種底層複雜性，並透過 JVM 提供一致的執行環境，以實現 "Write Once, Run Anywhere" 的理念（儘管實際情況可能與理想有所差距）。而 C++ 則更傾向於提供所有可能的功能，即便這可能導致某些工具被誤用。在 2014 年 C++ 的官方標準文件（Standard for Programming Language C++）N4296 的第 12 頁，提示 C++ 提供的同步操作，也就是使用 [atomic operation](https://hackmd.io/@sysprog/concurrency-atomics) 或 mutex： > The library defines a number of atomic operations and operations on mutexes that are specially identified as synchronization operations. These operations play a special role in making assignments in one thread visible to another. 正如前文所述，C++ 提供一系列的 atomic operation 和 mutex，以協助開發者建立跨執行緒之間的同步關係。實際上，尚有更多的語法可用。以下是個簡單的 mutex 範例： ```cpp #include <iostream> // std::cout #include <thread> // std::thread #include <mutex> // std::mutex std::mutex mtx; // mutex for critical section int count = 0; void print_thread_id (int id) { // critical section (exclusive access to std::cout signaled by locking mtx): mtx.lock(); std::cout << "thread #" << id << " count:" << count << '\n'; count++; mtx.unlock(); } int main () { std::thread threads[10]; // spawn 10 threads: for (int i=0; i<10; ++i) threads[i] = std::thread(print_thread_id,i+1); for (auto& th : threads) th.join(); return 0; } ``` 上述程式碼建立 10 個執行緒，每個執行緒進行相同的操作：列出傳入的參數和目前的 `counter` 值，然後遞增 `counter` 內容。若未使用 mutex lock，由於執行緒之間交錯執行，無法確保 **synchronized-with**，因此前一個執行緒的操作結果無法確保傳遞給後續的執行緒。結果將變得混亂不堪，且 `counter` 的數值也會變得混亂不一致。不使用 mutex lock 的結果是: ``` thread #thread #thread #thread #12 count: count:00 3 count:0 thread #5 count:0 thread #4 count:0 6 count:2 thread #7 count:6 thread #8 count:7 thread #9 count:8 thread #10 count:9 ``` 加上 lock 後，結果就符合預期，每個執行緒都正確地把內容印出來 ``` thread #2 count:0 thread #1 count:1 thread #8 count:2 thread #4 count:3 thread #5 count:4 thread #6 count:5 thread #9 count:6 thread #7 count:7 thread #3 count:8 thread #10 count:9 ``` ### 深入 Synchronizes-with 實際上，要建立 synchronizes-with 的關係有很多種不同層次的方法，Jeff Preshing 在〈[The Synchronizes-With Relation](http://preshing.com/20130823/the-synchronizes-with-relation/)〉提供以下示意圖，實際尚有其他方法可建立同步關係。 ![](https://i.imgur.com/qrgwQni.png) 可見 synchronizes-with 是一種跨執行緒間的 happens-before 關係，此外我們可藉由 mutex lock, thread create/join, Aquire and release Semantic 來建立 synchronized-with 關係。 ### Synchronizes-with 參考資料 * Java theory and practice: Fixing the Java Memory * [Cppreference std::mutex](http://en.cppreference.com/w/cpp/thread/mutex) * [Cplusplus std:mutex lock](http://www.cplusplus.com/reference/mutex/mutex/lock/) * [Memory Consistency Error from Java Doc](https://docs.oracle.com/javase/tutorial/essential/concurrency/memconsist.html) --- ## Memory Consistency Models 前面提到，實際上程式在編譯與執行的時候，不一定會真的照你所寫的順序發生。而是可能改變順序、盡量最佳化，同時營造出彷彿一行一行執行下來的幻象，只要實際的結果和照順序執行沒有差別就好。這樣的幻象要成立，在於程式設計師和該系統（硬體、編譯器等產生、執行程式的平台）達成一致的協定，系統保證程式設計師只要照著規則走，程式執行結果會是正確的。但什樣叫做正確？正確的意思不是保證只會發生一種執行結果，而是定義在所有可能發生的執行結果中，哪些是允許的。我們把這樣的約定稱為 Memory Consistency Models，系統要想辦法在保證正確的情況下，盡可能的最佳化，讓程式跑的又快又好。 Memory Consistency Models 存在於許多不同的層次中，像是機械碼運作於硬體時，因為處理器可進行指令重排和最佳化 (例如 [instruction scheduling](https://en.wikipedia.org/wiki/Instruction_scheduling))，雙方得確保執行結果和預期相同。或者，在將高階語言轉換成組合語言時，因為編譯器能夠將組合語言重排，雙方也要確保產生的結果和預期一致。換言之，從原始程式碼到最終執行於實際硬體，大家都必須做好約定，才會得到預期結果。 ### 最直覺的約定: Sequential Consistency 1970 年代，[Leslie Lamport](https://en.wikipedia.org/wiki/Leslie_Lamport) 就在思考這個問題，他提出一個如今最常見的 Memory consistency model —— Sequential Consistency (SC)，其定義如下 > A multiprocessor system is sequentially consistent if the result of any execution is the same as if the operations of all the processors were executed in some sequential order, and the operations of each individual processor appear in this sequence in the order specified by its program. 我們可分成二個觀點來看 Sequential Consistency 的定義， 1. 對於每個獨立的處理單元，執行時都維持程式的順序 (Program Order) 2. 整個程式以某種順序在所有處理器上執行 Lamport 的定義相當洗鍊：第一點言明程式在處理器內會照順序執行，第二點則說所有處理器會以某種順序執行程式。看似平實的話語，但真實世界卻可能不是這樣。之所以會有這樣的感覺，是因為讀者一直生活在這樣的世界裡，就像活在牛頓時代之前的人一樣，認為只要把手上的東西放開，它自然會掉下來。然而，我們將會發現，在現代處理器上，要確保這種現象發生，會有許多限制最佳化的方法，這將減緩程式的執行速度。如果您同意放棄一些約定，例如不保證每個處理單元維持程式執行的順序，我們還可以進一步提升效能。 Memory consistency model 只是種虛構的約定，換句話說，程式的執行結果必須呈現這種形式，然而實際上，經過程式編譯並運行在電腦硬體上，對於執行順序的調整有著極大的靈活性。只要執行結果和事先定義的約定相符，實際的執行順序會因情況而異。 > 由於漢字缺乏抽象 (abstract) 概念的對應，因此 [consistency](https://www.merriam-webster.com/dictionary/consistency) 被稱為一致性、[consensus](https://www.merriam-webster.com/dictionary/consensus) 喚作一致性、[coherence](https://www.merriam-webster.com/dictionary/coherence) 翻譯成一致性，甚至 [congruent](https://www.merriam-webster.com/dictionary/congruent) 也譯為一致，不過這些詞彙的寓意其實截然不同。 ### Weak Memory Model vs. Strong Memory Model ![](https://i.imgur.com/Z0LWi07.png) 所謂的 Weak (也稱為 relaxed) 就是指很可能會將 load/store 指令進行重排，而 Strong 則相反。4 種模式 * Weak memory model: 可能存在所有的 memory reordering * Weak with data dependency ordering: 可能存在 storeload 和 storestore 的 reordering (load 的順序必能被保證) * Usually Strong: 保證 acquire and release semantic 的執行,所以只存在 storeload reordering * Sequentially consistent: 全部保證順序為了理解 weak (或 relaxed) memory order 如何運作，我們想像每個變數都是一個獨立的房間裡拿著一本筆記本的人，該筆記本上有一系列的數值。你有以下二個主要動作選項： * 打電話給某人，要求他告訴你其中一個數值：他會從這份清單中選擇一個給你 * 請某人記下一個新的數值：他會將它寫在這個清單的最後一個位置 ![](https://hackmd.io/_uploads/Byzgv5lhn.png =50%x) 當首次請某人告訴你數值時，他可能會提到此時他在清單上，看到的任何一個值。若你之後再問他一個數值，他可能會回答與上次相同的數值，或者是清單中後面的數值。他絕對不會告訴你清單前面的數值。現在，假設清單的初始內容是 $5, 10, 23, 3, 1, 2$。如果你詢問他一個數值，你可能會得到其中的任何一個。如果他告訴你是 `10`，那麼下一次詢問可能再次得到 `10`，或者是 `10` 之後的任何一個值 (例如 `23` 和 `3`)，但絕對不會是 `5`。以此類推，如果你詢問 5 次，你可能會得到 $10, 10, 1, 2, 2$ 這樣的清單。如果你要求他寫下 `42`，他會將 `42` 加到最後面。然後，如果你再次詢問數值，他會持續告訴你 `42`，直到他清單中有下一個數值，且他認為該告訴你為止。現在，想像你的朋友 Carl 也有某人的電話號碼。Carl 可打電話詢問或記下一個數值，而某人會以相同的方式對待 Carl，就像對待你一樣。由於這個人只有一支電話，所以他同時間只能處理一個人的需求，這使得他筆記本上的清單就像是一個簡單的列表。然而，當你要求他寫下一個數值時，並不代表他會告訴 Carl，反之亦然。舉例來說，如果 Carl 詢問得到 `23`，而你之後請求寫下 `42`，並不表示他下一次就會告訴 Carl。他可能會選擇在 $23, 3, 1, 2, 42$ 中選擇一個數值告知 Carl，甚至可能是另一個人告訴他寫下的 `67`。因此，Carl 可能會得到 $23, 3, 3, 1, 67$ 這樣的清單，與你收到的數值可能不同。就存在個人專屬的指示器，記錄每個人現在的進度，如下圖所示。 ![](https://hackmd.io/_uploads/B1O8nOx3n.png) 現在，讓我們再進一步想像：不只有一個人在小房間內，而是一群人聚集在一個農場上，每個人都配備電話和筆記本。這些人所擁有的全都是 atomic 變數。每個變數都有自己的修改順序 (即清單上的列表)，但彼此之間的順序沒有任何關聯。在這個場景中，每個撥號者 (你, Carl, Anne, Dave, Fred）都是一個執行緒，而這種情況就如同每個操作都使用 `memory_order_relaxed`。這些人在小房間內所能執行的操作有些是：記下一個數值並告訴我目前清單的最後一個值（`exchange`），或者在清單的最後一個值是某個特定值時，記下該數值。還有一個操作是，當最後一個數值是某個特定值時，告訴我是否猜對（`compare_exchange_strong`）。然而，這些操作都不會影響 consistency 原則。接著我們考慮以下 C++ 程式碼： ```cpp #include <atomic> #include <thread> #include <assert.h> std::atomic<bool> x, y; std::atomic<int> z; void write_x_then_y() { x.store(true, std::memory_order_relaxed); // 1 y.store(true, std::memory_order_relaxed); // 2 } void read_y_then_x() { while (!y.load(std::memory_order_relaxed)); // 3 if (x.load(std::memory_order_relaxed)) ++z; // 4 } int main() { x = false, y = false, z = 0; std::thread a(write_x_then_y); std::thread b(read_y_then_x); a.join(); b.join(); assert(z.load() != 0); // 5 } ``` 在程式碼中的 `write_x_then_y` 就好比前面提到的情境中，某人打電話給房間內的 `x`，並告訴他記下 true。接著，再打電話給 `y`，告訴他也要寫下 true。而在執行緒中，不斷反覆執行 `read_y_then_x` 就像是打電話給 `y`，不斷詢問他所要數值，直到得到 true，然後再打電話給 `x`，繼續詢問值。值得注意的是，`x` 只需要告訴你清單上的任何一個數值，因此他也可以回答 false。這次 :five: 會觸發 assert，因為 load of x :four: 可能是 false，即使 load of y :three: 是 true 且 store of x :one: 比 store of y :two: 還要早發生。`x` 和 `y` 是不同的變數，無法保證個別操作後的數值可視性的順序。在不同變數的 relaxed 操作中，只要它們遵循受限制的 happens-before 關係，就可以自由地調整執行順序，而不需要伴隨著同步關係。即使在 store 操作之間和 load 操作之間存在 happens-before 關係，任何一個 store 操作和 load 操作之間都沒有必然的相互關聯。因此，在這種情況下，load 操作可能會獲得不同順序的結果，參見下圖： ![](https://hackmd.io/_uploads/r1Rqztg22.png) 這就讓 relaxed atomic operations 很難處理，他們必須與 atomic operation 結合，為了讓 inter-thread 的同步更為有用，這些 atomic operation 必須有較強的排序語意。這使得處理 relaxed atomic 操作變得相對困難。為了加強執行緒間的同步效果，這些 relaxed atomic 操作需要與 atomic 操作結合，而為了實現更有意義的執行緒間同步，這些 atomic 操作必須具備較強的執行順序語義。另一種可達成額外同步效果的方法，無需全域執行順序一致，即為 acquire-release ordering。在這個模型中，atomic load 操作屬於 acquire 操作（`memory_order_acquire`），atomic store 操作屬於 release 操作（`memory_order_release`）。而 atomic read-modify-write (RMW) 操作（例如 `fetch_add()` 或 `exchange()`）可能屬於 acquire, release，或同時屬於這二者（`memory_order_acq_rel`）。 > 英語中的 acquire 和 obtain 詞源不同，但漢語缺乏直接對應的詞彙，其中 "acquire" 指通過努力逐步獲得人才、知識、習慣等，也可用於財產的獲取等，該詞強調「一旦獲得，它將長期持有」的含義，例如：You should know how to use the skills you have acquired. (你該知道如何使用你學到的技術)。obtain 指較正式的「獲得、得到」，例如 I obtained the property with a bank loan. (我用銀行貸款買下、得到我的房地產)。對照觀看〈[揭秘斯諾登 10 年流亡史](https://youtu.be/ojfAfMpgWJk)〉8 分 32 秒開始的釋義。 acquire-release ordering 模型有二種效果，其一是限制 CPU 指令的重排： * 在 store 之前的所有讀寫操作，**不允許**被移動到該 store 的後面。 * 在 load 之後的所有讀寫操作，**不允許**被移動到該 load 的前面。再者，假設 Thread~1~ store 的某個數值，成功被 Thread~2~ load，那麼 Thread~1~ 在 store 之前對記憶體的所有寫入操作，此時對 Thread~2~ 來說，都是==可見==。以經典的[生產者－消費者問題](https://en.wikipedia.org/wiki/Producer%E2%80%93consumer_problem)來舉例，見下方 C++ 程式碼： ```cpp #include <thread> #include <atomic> #include <cassert> #include <string> std::atomic<bool> ready{ false }; int data = 0; void producer() { data = 100; // 1 ready.store(true, std::memory_order_release); // 2 } void consumer() { while (!ready.load(std::memory_order_acquire)); // 3 assert(data == 100); // never failed // 4 } int main() { std::thread t1(producer); std::thread t2(consumer); t1.join(); t2.join(); return 0; } ``` 過程分析： * 首先 :one: 不允許被移動到 :two: 的後面。 * 同樣 :four: 也不允許被移動到 :three: 的前面。 * 當 :three: 脫離 while 迴圈中，說明 :three: 讀取到 :two: store 的那個值，此時，Thread~2~ 保證能夠看見 Thread~1~ 執行 :two: 之前的所有寫入操作（也即是 :one:）。同步發生於執行 release 操作的執行緒與執行 acquire 操作的執行緒之間，成對進行。一個 release 操作對一個讀取寫入值的 acquire 操作，確保 synchronizes-with 關係。考慮以下 C++ 程式碼: ```cpp #include <atomic> #include <thread> #include <assert.h> std::atomic<bool> x, y; std::atomic<int> z; void write_x() { x.store(true, std::memory_order_release); } void write_y() { y.store(true, std::memory_order_release); } void read_x_then_y() { while (!x.load(std::memory_order_acquire)); if (y.load(std::memory_order_acquire)) ++z; // 1 } void read_y_then_x() { while (!y.load(std::memory_order_acquire)); if (x.load(std::memory_order_acquire)) ++z; // 2 } int main() { x = false, y = false, z = 0; std::thread a(write_x); std::thread b(write_y); std::thread c(read_x_then_y); std::thread d(read_y_then_x); a.join(); b.join(); c.join(); d.join(); assert(z.load() != 0); // 3 } ``` 上面的例子，:three: 可能會被觸發，因為 load of x :two: 和 load of y :one: 可能讀到 `false`。`x` 和 `y` 在不同的執行緒中被寫入，所以二個讀取導向的執行緒可能會有不同的結果，下圖展現 happens-before 關係： ![](https://hackmd.io/_uploads/SymQTtx2h.png) 接下來介紹使用 acquire-release ordering 的好處，下面的例子將 store x 和 store y 在同一個執行緒處理： ```cpp #include <atomic> #include <thread> #include <assert.h> std::atomic<bool> x, y; std::atomic<int> z; void write_x_then_y() { x.store(true,std::memory_order_relaxed); // 1 y.store(true,std::memory_order_release); // 2 } void read_y_then_x() { // Spin, waiting for y to be set to true while (!y.load(std::memory_order_acquire)); // 3 if(x.load(std::memory_order_relaxed)) ++z; // 4 } int main() { x = false, y = false, z = 0; std::thread a(write_x_then_y); std::thread b(read_y_then_x); a.join(); b.join(); assert(z.load() != 0); // 5 } ``` 最終 load from y :three: 會從 :two: 讀到 `true`，因為這邊 store 使用 `memory_order_release`，load 使用 `memory_order_acquire`，於是 store synchronizes-with load。而 store to x :one: happens-before store to y :two:，因此 load from x 一定是 `true`，且 assert :five: 不會觸發。。參考資料: * 《C++ Concurrency in Action》, Anthony Williams * 《C++ Concurrency in Action》中文筆記: [第 1, 2 章](https://hackmd.io/@ZGt0WcJQQ_enG8iTXTGNWw/SkWEUg14O), [第 3 章](https://hackmd.io/@ZGt0WcJQQ_enG8iTXTGNWw/BkYQjwgVu), [第 4 章](https://hackmd.io/@ZGt0WcJQQ_enG8iTXTGNWw/S1VsZU1EO), [第 5 章](https://hackmd.io/@ZGt0WcJQQ_enG8iTXTGNWw/S16JsDl4O), [第 6 章](https://hackmd.io/@ZGt0WcJQQ_enG8iTXTGNWw/HkXR-IkEO), [第 7 章](https://hackmd.io/@ZGt0WcJQQ_enG8iTXTGNWw/H1DFcPe4d), [第 8 章](https://hackmd.io/@ZGt0WcJQQ_enG8iTXTGNWw/ryHxzUJVO), [第 9 章](https://hackmd.io/@ZGt0WcJQQ_enG8iTXTGNWw/B1hV9DxEd), [第 10, 11 章](https://hackmd.io/@ZGt0WcJQQ_enG8iTXTGNWw/Hk_GMIJVO) ### 確保執行順序 [Dekker's Algorithm ](https://en.wikipedia.org/wiki/Dekker%27s_algorithm) 是首個 mutual exclusion 的解法，1965 年 Edsger W. Dijkstra 證明並提出時並未考慮到 memory model。其演算法用 C 程式碼表示如下: (flag~0~ 和 flag~1~ 均初始為 `false`) ```c Processor 1 | Processor 2 =========== | =========== 0: while (true) { | while (true) { 1: /* non-critical code */ | /* non-critical code */ 2: flag[0] = true; | flag[1] = true; 3: while (flag[1]) { | while (flag[0]) { 4: if (turn != 0) { | if (turn != 1) { 5: flag[0] = false; | flag[1] = false; 6: while (turn != 0) ; | while (turn != 1) ; 7: flag[0] = true; | flag[1] = true; 8: } | } 9: } | } 10: /* critical section */ | /* critical section */ 11: turn = 1; | turn = 0; 12: flag[0] = false; | flag[1] = false; 13: } | } ``` 若我們要確保 Sequential Consistency，即在每個處理器核確保程式執行的順序，那麼上述程式確保同一時間只有一個處理器能夠進入臨界區 (critical section)。這是因為程式確保先設定旗標，然後再檢查對方的旗標是否已設置，僅在對方未設置旗標的情況，方可進入臨界區。然而，我們仍要考慮另一種情境：同一個處理器可能會認為 Flag~0~ 和 Flag~1~ 這兩個變數之間不存在相依性，因此即使改變它們的執行順序也不會影響程式的結果。若處理器 P~1~ 和 P~2~ 都先執行第 3 行，再執行第 2 行，那麼就會發生同時進入臨界區的情況，這將違反 [Dekker's Algorithm ](https://en.wikipedia.org/wiki/Dekker%27s_algorithm) 的原理。 [Peterson's algorithm](https://en.wikipedia.org/wiki/Peterson%27s_algorithm) 在 1981 年提出，作為 mutual exclusion 的解法，最初只能針對 2 個任務 (後來可擴充，適用於更多任務)，使用以下共享變數: * `bool flag[2] = {false, false}` : 分別代表 T0 及 T1 是否想進入臨界區域 * `int turn` : 1 或 0，代表這一回合，該讓何者進入臨界區域該演算法對於硬體的假設是，load 和 store 為 atomic 操作，且為共享記憶體模型。其演算法用 C 程式碼表示如下: ```c Thread 0 | Thread 1 ======== | ======== 0: while (true) { | while (true) { 1: /* non-critical code */ | /* non-critical code */ 2: flag[0] = true; | flag[1] = true; 3: turn = 1; | turn = 0; 4: while (flag[1] && turn == 1) | while (flag[0] && turn == 0) 5: ; | ; 6: /* critical section */ | /* critical section */ 7: flag[0] = false; | flag[1] = false; 8: } | } ``` 改寫為通用的 C 程式: ```c volatile bool flag[2] = {false, false}; volatile int turn = 0; void lock(int id) { int other_id = 1 - id; flag[id] = true; /* we want in */ turn = other_id; /* ... but let the other in first */ while (flag[other_id] && turn == other_id) /* spin */ ; } void unlock(int id) { flag[id] = false; /* we don't want in anymore */ } ``` [Peterson's algorithm](https://en.wikipedia.org/wiki/Peterson%27s_algorithm) 的使用案例: ```c volatile int counter = 0; void counting_thread(int my_id) { for (int i = 0; i < thread_cycles; i++) { lock(my_id); counter++; unlock(my_id); } } int main(void) { while (true) { ... create threads ... ... wait for threads to exit ... printf("counter: %i (%i)\n", counter, 2 * thread_cycles - counter); } return 0; } ``` 上述程式碼在 x86-64 處理器執行結果: ``` counter: 19999865 (135) counter: 19999775 (225) counter: 19999839 (161) counter: 19999881 (119) counter: 19999802 (198) counter: 19999832 (168) counter: 19999844 (156) ... ``` 既然 [Peterson's algorithm](https://en.wikipedia.org/wiki/Peterson%27s_algorithm) 已被證明是正確的演算法，上述 x86-64 執行結果就表示演算法對硬體的假設不成立，也就是「load 和 store 都該是 atomic 操作」不能在 x86-64 滿足。依據《[Intel® 64 and IA-32 Architectures Developer's Manual: Volume 3A: System Programming Guide](https://www.intel.com/content/www/us/en/architecture-and-technology/64-ia-32-architectures-software-developer-vol-3a-part-1-manual.html)》的 Section 8.2.3.4: > **Loads May Be Reordered with Earlier Stores to Different Location** > The Intel-64 memory-ordering model allows a load to be reordered with an earlier store to a different location. > However, loads are not reordered with stores to the same location. 從 Intel 手冊，我們可推測：處理器修改數值，將其寫入 cache 中，但將這些 store 操作推遲，從而減少處理器提交到主記憶體的效能影響。在此同時，可能會進行一些來自其他位置的讀取。重新檢視 `lock` 實作: ```c void lock(int id) { int other_id = 1 - id; flag[id] = true; /* STORE flag[id] */ turn = other_id; /* STORE turn */ while (flag[other_id] && /* LOAD flag[other_id] */ turn == other_id) /* LOAD turn */ /* spin */ ; } ``` 考慮以下情境: ![](https://hackmd.io/_uploads/Sy10c7Znn.png) ![](https://hackmd.io/_uploads/ryxAqmWh3.png) ![](https://hackmd.io/_uploads/B1lowmb32.png) 由於 LOAD 和 STORE 未能保證 Sequential Consistency，於是 mutual exclusion 就不能滿足。在 x86(-64) 處理器上，有個 `mfence` 指令可抑制指令重排 (為行文的便利，這裡使用不精準的詞彙)，我們可改寫上述程式碼，如下: ```c #define MFENCE() { __asm__("mfence" ::: "memory"); } void lock(int id) { int other_id = 1 - id; flag[id] = true; // STORE flag[id] turn = other_id; // STORE turn MFENCE(); while (flag[other_id] && // LOAD flag[other_id] turn == other_id) // LOAD turn /* spin */ ; } ``` 至此，針對 `flag[other_id]` 的 STORE 操作就不再被重排，也就滿足 mutual exclusion。不過，在 Arm 一類的處理器，尚需要額外的調整，可參見 [並行程式設計: Atomics 操作](https://hackmd.io/@sysprog/concurrency-atomics)。 ### 確保對所有處理器都是一致的考慮以下執行順序: (initially, A = B = 0) | P~1~ | P~2~ | P~3~ | |:-----|:-----|:-----| | A = 1 | | | | | if (A == 1) B = 1; | | | | | if (B == 1) register = A; | 當處理器 P~1~ 執行 `A = 1` 後，處理器 P~2~ 運行 if 判斷，結果為 true，接著執行 `B = 1`。之後處理器 P~3~ 執行 if 判斷，確認 `B = 1` 成立，最終將 A 的值寫入 `register`。這樣的程式順序確保 `register` 讀取到的 A 值是 `1`。前提是在處理器 P~1~ 將共享變數 A 設為 `1` 後，處理器 P~2~ 和 P~3~ 能夠確保讀取到 `A = 1`。換句話說，需要確保整個程式在所有處理器上以某種順序執行，使得每個處理器都能**看到**其他先執行指令的效果我們接下來將探討三個經典範例，討論就算是缺乏 cache 的硬體架構，稍不注意也可能會違反 Sequential Consistency。 - [ ] Store buffers with Bypassing Capability > 這個範例強調維持 Write $\to$ Read 順序的重要性。 ![](https://i.imgur.com/DqAwRGV.png) 上圖左側展示每個處理器都有自己的寫入緩衝區 (store buffer，亦稱 write buffer)。在程式執行時，處理器可先將資料寫入 store buffer，稍後再將其寫回主記憶體。其中一個最佳化手法是，當處理器將資料寫入 store buffer 時，不會等待資料完全寫入主記憶體，而是直接繼續執行後續的程式碼。在此之後，如果有讀取操作發生，只要該讀取的位址並位在 store buffer 中等待寫回主記憶體，系統即允許進行讀取。這樣的最佳化手法在單核處理器上相當普遍，藉由避免等待耗時的寫入操作，可縮短程式等待的時間。然而，這種方法可能會導致違反 Sequential Consistency（SC）。請參考上圖右側的程式示例。儘管程式看起來是逐行執行，但實際上，當進行寫入操作時，資料首先被寫入 store buffer，然後直接允許下一行進行讀取操作，即從主記憶體讀取資料。因此實際程式對記憶體的操作，會是上圖左的 t1 (讀取 Flag2) $\to$ t2 (讀取 Flag1) $\to$ t3 (寫入 Flag1) $\to$ t4 (寫入 Flag2)，二個 Flag 都讀到 0，於是都進入 critical section，從而違反 SC。 - [ ] Overlapping Write Operations > 這個範例強調維持 Write $\to$ Write 順序的重要性。 ![](https://i.imgur.com/wE4wDox.png) 在一個沒有共享匯流排 (bus) 且各個記憶體模組之間相互連結的系統中，我們可考慮這樣的情境：假設處理器按照程式的順序發出寫入請求，且不等待前一個請求執行完畢，而是直接發出下一個請求。上圖右側的程式執行時，根據 Sequential Consistency（SC）的要求，我們應該能夠看到 Data 變數的值最終會是最新的值 `2000`。然而，在這種架構下，這個保證無法被確保，因為處理器 P1 可能先將 Head 的寫入操作完成，然後才是 Data 的寫入操作，這將導致 Head 在記憶體中的更新發生在 Data 之前。因此，實際的執行序列可能會是 t1 (寫入 Head 成功) $\to$ t2 (讀取 Head 為 1) $\to$ t3 (讀取 Data 讀到舊的值) $\to$ t4 (寫入 Data 成功)，這將完全違反 Sequential Consistency 的原則。在單核處理器上，針對不同位址的寫入操作進行重排不會引發大問題，只要確保資料之間的相依性。然而，在這種情境下，上述的問題可能會發生。要解決這個問題，我們需要等待前一個寫入操作完成，也就是等待獲得確認回應 (acknowledgement response)，然後再發出下一個寫入請求。 - [ ] Non-Blocking Read Operations > 這個範例強調維持 Read $\to$ Read, Read $\to$ Write 順序的重要性。 ![](https://i.imgur.com/1Q69YHY.png) 這種情況也常見於最佳化中，讓我們能變更讀取的順序。舉例來說，假設處理器 P1 循序執行程式碼，但處理器 P2 不等待讀取 Head 完成就立即發出讀取 $Data$ 的請求。這種情況下，可能會發生這樣的執行序列 t1 (Read Data 先回傳結果為 0) $\to$ t2 (寫入 Data 2000) $\to$ t3 (寫入 Head 1) $\to$ t4 (讀取 Head 為 1)，這將導致違反 Sequential Consistency（SC）的結果。 ### Cache Architechture 與 Sequential Consistency 上述三個案例都是非常典型的情況，若程式存取記憶體的順序發生變化，就有可能違反 Sequential Consistency（SC）。即便在具有 cache 的系統架構中，我們也會遭遇類似的問題。在具備 cache 的系統中，同一份資料可能存在於多個處理器的 cache 中。為了維持 Sequential Consistency，系統必須確保同一份資料在不同處理器的 cache 中保持一致，否則某些處理器可能讀取到較新的資料，而其他處理器則讀取到較舊的資料。這樣每個處理器所觀察到的行為就不一致，容易違反 SC。即使某個處理器發現所需資料已經存在於其 cache 中，也不能立即讀取該資料，必須確保前一個操作已經完成，才能進行讀取動作。 #### Cache Coherence and Sequential Consistency ![](https://hackmd.io/_uploads/rJiH1sgh3.png) 我們需要一種名為 [cache coherence protocol](https://en.wikipedia.org/wiki/Cache_coherence) 的機制，以確保在系統中不同處理器上的 cache 保持一致。若 [cache coherence protocol](https://en.wikipedia.org/wiki/Cache_coherence) 足夠嚴格，我們就能確保系統中的程式不會出現違反 Sequential Consistency 的結果。我們可以將 [cache coherence protocol](https://en.wikipedia.org/wiki/Cache_coherence) 理解為以下二個主要原則： * 所有的寫入最終都會被所有處理器==看見== * 對於相同位址的寫入順序對所有處理器而言都是一致的這意味著當寫入發生時，最終所有處理器都將能夠看到這個寫入的效果，而針對相同位址的寫入，所有處理器都會一致地看到相同的順序，因此不會發生重排順序的情況。如果我們希望遵守順序的一致性，還要確保對於不同位址的寫入，所有處理器也會看到相同的順序，從而避免任何寫入順序重排的情況。 #### Detecting the Completion of Write Operations 想要維持程式執行的順序，意味著我們要確保上一個寫入操作完成後，才能執行下一道指令。因此，我們需要從記憶體模組收到一個完成的信號，表示該次寫入操作已完成。對於沒有 cache 的系統來說，這個過程相對簡單，只需等待主記憶體回傳完成的信號。然而，在具有 cache 的系統中，「寫入完成」的真正意義是，所有處理器都能夠==看到==新的寫入值，因此我們必須確保每個快取都被正確地更新或無效化 (必須重新從記憶體中取出正確的值)。這麼做是為了確保每個處理器都能以正確的值進行後續的操作，從而避免出現不一致的情況。 #### Maintaining the Illusion of Atomicity for Writes 在把新的值更新到每個 cache 上時，要知道這樣的操作並不是 atomic 的，並不是一瞬間，所有的 cache 統統都更新完成。可能有的 cache 會先被更新，有的之後才更新。 ![](https://i.imgur.com/P4hfnZx.png) 考慮上圖，假設 P1 和 P2 都照著程式順序來執行，但要是寫入 `A = 1` 和 `A = 2` 用不同的順序抵達 P3 和 P4，就會發生 register1 和 register2 讀到二個不同的值的情形。例如 P3 看到的是 `A=1` `A=2` `B=1` `C=1`, P4 看到的是 `A=2` `A=1` `B=1` `C=1`，致使 P3, P4 明明是讀取相同的 A 值，卻出現不一致的情形。避免這種狀況的方式是確保「寫入相同的位址的順序對所有處理器而言都是一致的」。 ![](https://i.imgur.com/JYsRrFD.png) 然而，僅保證寫入相同位址時，所有處理器都能看到相同的更新順序是不夠的。考慮上圖的程式碼範例，當 P1 寫入 `A = 1` 後，假設 P2 已看到 `A = 1` 並執行 `B = 1`。然而，對於 P3 來說，它可能還沒有收到 `A = 1` 的修改，但已看到 `B = 1` 的修改。這導致 P3 讀取 `A` 的值為 `0`。為避免發生這種情況，在讀取剛寫入的值之前，必須確保所有處理器的 cache 都被正確地更新。唯有如此，方可確保所有處理器對於整個程式的執行順序都保持一致，並滿足Sequential Consistency的要求。參考資訊 * [Shared Memory Consistency Models: A Tutorial 1995 Sarita V. Adve, Kourosh Gharachorloo](http://www.hpl.hp.com/techreports/Compaq-DEC/WRL-95-7.pdf) * [Memory Models, Russ Cox](https://research.swtch.com/mm)

Read more

2024 年 Linux 核心設計/實作課程作業 —— ktcp

並行程式設計: Lock-Free Programming

建構 User-Mode Linux 的實驗環境

你所不知道的 C 語言: 開發工具和規格標準