# 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`