about 1 year ago

我們先前談過了Sequenced-Before,現在我們來談什麼是Happens-Before

Java對Happens-Before的定義

Java的官方文件定義了什麼是Happens-Before,先不管那些volatile, synchronized等用詞,我只看最簡單的一句

If one action happens-before another, then the first is visible to and ordered before the second.

解釋的很簡單,當行為A happens-before B時,代表A的效果可見,而且發生於B之前。

通俗的解釋

讓我們用比較通俗一點的方式解釋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的定義是差不多的,都在說明前一個操作的效果在後一個操作執行之前必須要可見。舉個簡單的例子就是

// example provided by Jeff Preshing
int A, B;

void foo()
{
    // This store to A ...
    A = 5;

    // ... effectively becomes visible before the following loads. Duh!
    B = A * A;
}

在上述的簡單的程式碼中,第一行的效果必須要讓第二行的效果可見,B才會正確的得到25,你說這不是很理所當然嗎?寫在前面一行的程式不是本來就應該先執行,之後才執行下一行嗎?

不,並不見得。

這裡有個關鍵是,Happens-before強調的是visible,而不是實際上執行的順序。
實際上程式在執行時,只需要"看起來有這樣的效果"就好,編譯器有很大的空間可以對程式執行的順序做優化。

舉例來說,像是下面的程式,

int A = 0;
int B = 0;

void foo()
{
    A = B + 1;              // (1)
    B = 1;                  // (2)
}

int main()
{
    foo();
}

如果你只下gcc file.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

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可見就可以了,實際上怎麼執行的並不需要深究。

現在我們來看C++對happens-before的定義,其實也是相同的概念

C++對Happens-Before的定義

再來看C++的定義

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包含兩種情況,一種是同一個thread內的happens-before關係,另一個是不同thread間的happens-before關係。

我們平常程式一行一行寫下來,我們本來就預期上一行的程式效果會對下一行的程式可見。我們先前已經清楚的解釋什麼是Sequenced-before,現在你可以發現,Sequenced-before其實就是同一個thread內的happens-before。

在跨thread的情況下,如果沒有保證happens-before的關係,程式常常會出現意料之外的結果。舉例來說

int counter = 0;

現在有兩個thread同時執行,thread A執行counter++,thread B把counter的值印出來。因為這兩個thread沒有具備happens-before的關係,沒有保證counter++後的效果對於印出counter是可見的,導致印出來的結果可能是1,也可能是0。

因此,語言必須提供適當的手段,讓程式設計師能夠建立跨thread間的happens-before的關係,如此一來才能確保程式執行的結果正確。這也就是剛剛C++ happens-before定義裡的第二點,A inter-thread happens before B

Inter-thread happens before

[Java定義清楚用何種語法能夠建立happens-before的關係,在此先不贅述。
C++定義了五種情況都能夠建立跨thread間的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點都是遞迴定義,因此我們只關注前兩點,不過再解釋下去會讓篇幅過長,影響閱讀和理解的順暢,目前只要先有個概念就好,我們後續再解釋什麼是Synchoronizes-with和dependency-ordered before。

Reference

← Concurrency系列(二): 從Sequenced-Before開始說起 Concurrency系列(四): 與Synchronizes-With同在 →
 
comments powered by Disqus