10 months ago

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的關係畫出來的話,如下圖。

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

可以看到問題在於,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<b的話,必然not b < a
    • 而實數範圍的小於等於就不是一種asymmetry的關係,因為x <= x,交換過來亦成立
  • if a < b and b < c then a < c (transitivity)
    • 遞移性應該就不需要解釋了

Reference

← Concurrency系列(一): 理解Concurrency之路 Concurrency系列(三): 朝Happens-Before邁進 →
 
comments powered by Disqus