# Experiments on Concurrency - Happens-before contributed by < [jeffrey.w](https://github.com/jeffrey-minwei/experiments-on-concurrency/tree/master/c11-standard) > ## Introduction C 語言在 C99 的時候還沒有將並行 (concurrency) 納入到語言的標準，但到了[C11 standard](http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1570.pdf) 就開始將並行、memory order 相關的機制加入到規格裡，本文將透過學習 [C11 standard](http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1570.pdf) 和 [C++11 standard](http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2012/n3376.pdf) 來理解並行在語言層面的機制，然後使用 C11 來實驗並行。 ## Modification 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** ### Total order §5.1.2.4/7 所說的 particular total order 是指什麼？ > All modifications to a particular atomic object M occur in some **particular total order** 數學上的 total order 是指一個集合裡的 binary relation [[1](https://en.wikipedia.org/wiki/Total_order)]，這個二元關係具有三個特性：反對稱、遞移和 Connexity： - 反對稱 ([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}$ - [Connexity](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{ A -> B -> C; }  :::warning 上圖只是 total order，還沒有提到 modification order ::: 初始條件: - binary relation ${R}$ 表示 **happens-before relation** - ${\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 (A, B) \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 relation 符合 total order 的定義。 所以 ${A, B, C}$ 的 modification order 符合規格書的順序就會是 ${A \rightarrow B \rightarrow C}$。 ### Example 寫一段 code 來實驗 modification order，底下的範例改寫自 [Preshing on Programming, Memory Ordering at Compile Time](https://preshing.com/20120625/memory-ordering-at-compile-time/) clike #include <stdatomic.h> atomic_int a = ATOMIC_VAR_INIT(0); atomic_int 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; }  先看 test 的組合語言在 gcc -O2 -S -masm=intel 和 gcc -S -masm=intel 的差別 **gcc -O2 -S -masm=intel**  test: ... mov eax, DWORD PTR d[rip] mov DWORD PTR d[rip], 42 add eax, 5 ...  **沒有最佳化** gcc -S -masm=intel  test: ... add eax, 5 mov DWORD PTR c[rip], eax mov DWORD PTR d[rip], 42 ...  再使用 gcc -O2 -S -masm=intel，從組合語言來比較 test 和 test_atomic  test_atomic: ... lock add DWORD PTR b[rip], 5 mov eax, DWORD PTR b[rip] mov DWORD PTR a[rip], eax mfence mov DWORD PTR b[rip], 42 ...   test: ... mov eax, DWORD PTR d[rip] mov DWORD PTR d[rip], 42 add eax, 5 ...  我們從幾個角度來看上述幾種結果在 [C11 規格](http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1570.pdf) 的意義： - test 在 -O2 的 assembly 有沒有違反 happens-before？ - test_atomic 在 -O2 的 assembly 有沒有符合 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$ 的前面 - 所以，加了 -O2 仍然符合 modification order 參考維基百科對 [全序關係](https://zh.wikipedia.org/wiki/%E5%85%A8%E5%BA%8F%E5%85%B3%E7%B3%BB) 的說明，我們知道全序關係是一個二元關係，全序集是指一個**滿足全序關係的集合**，在全序集裡，元素任意一對都是可以比較的。 至此，重新再看一次 [C11 規格, §5.1.2.4/7](http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1570.pdf) 所定義的 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... - 有一個全序集，裡面的元素都是**對 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$ 之前。 ## Happens before ## References - [ ] [並行程式設計](https://hackmd.io/@sysprog/concurrency) - [ ] [Preshing on Programming, Memory Ordering at Compile Time, JUN 25, 2012](https://preshing.com/20120625/memory-ordering-at-compile-time/) - [ ] [Concurrency系列(二): 從Sequenced-Before開始說起](http://opass.logdown.com/posts/788206-concurrency-series-2-starting-from-sequenced-before) ###### tags: concurrency c11 c++11 happens-before