Skip to main content

Concurrency系列(二): 從Sequenced-Before開始說起

multithread環境下，程式會出問題，往往在於執行順序的不確定性。

我們將從如何定義程式執行的順序開始說起，為了簡單起見，我們先從單執行緒的觀點來看執行順序這件事，其中最關鍵知識就是Sequenced-before，你將會發現就連單執行緒的程式，也可能會產生不確定的執行順序。

Sequenced-before​

要了解sequenced-before，首先要了解何謂evaluation(求值)。

Evaluation 求值​

所謂求值，其實說穿了就是兩件事情，一個是value computations，對一串運算式計算的結果；另一個是side effect，也就是對物件狀態的修改，像是修改記憶體內變數的值、呼叫library的I/O function之類的。

對於C++來說，語言並沒有定義運算元的求值順序，因此像是f1() + f2() + f3()這種程式，Compiler可以任意決定要先計算哪一個函式，之後再按照加法運算子的left-to-right associativity從左邊加到右邊。

因此計算結果看起來會像(f1() + f2()) + f3()，但執行時f3()可以是第一個、第二個、或是最後才被呼叫。

sequeced-before就是一種對同一個thread下，求值順序關係的描述

  • 如果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的Rule，舉例來說：

以下提到的先於、先進行之類的用詞，全部的意思都是sequenced-before，也就是先完成之後才開始進行

  • 上一行的求值（包含value computations和side effect），會先於下一行的求值。（所以你寫的程式會看起來像是上一行的效果發生完，才執行下一行）
  • 運算元的value compuation會先於運算子的value compuation（所以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，之後才是assigment的side effect, 最後是整個assigment expression的value computation。

儘管我們定義許多Evaluation Order的規則，但語言依舊保留一些未定義的行為。

舉例來說，像是經典的未定義行為 i = i++ 最後到底i會是什麼，答案沒有人知道，因為如果我們把sequenced-before的關係畫出來的話，如下圖。

figure-1

把每個求值計算的過程和sequenced-before的關係標出來的話，就會有如下的關係

figure-2

可以看到問題在於，i++的side effect只sequenced-before i++本身的result，這個side effect可能發生在assignment之前或之後，我們並沒有定義出他們的順序關係，因此讓整行程式產生了不確定的行為。

小補充​

sequenced-before 是一種 非對稱性(asymmetric), 遞移性(transitive)的關係 for all a, b, and c in P, we have that: - if a < b then ¬ (b < a) (asymmetry) - 舉例來說，實數範圍內的小於就是一種asymmetry的關係，因為如果a

Reference​

Last updated on