Chapter 1-2. Reorder
Last updated
Last updated
如果兩個操作存取同一個變數, 且這兩個操作中有一個為寫操作, 此時這兩個操作之間就存在資料相依性.
資料相依性基本上可分為以下三種類型: 上面三種情況, 只要重排序兩個操作的執行順序, 程式的執行結果就會被改變.
前面提到過, 編譯器和處理器可能會對操作做重排序. 編譯器和處理器在重排序時, 會遵守資料相依性, 編譯器和處理器不會改變存在資料相依性的兩個操作的執行順序.
要注意的是, 這裡所說的資料相依性僅針對單個處理器中執行的指令序列和單個執行緒中執行的操作, 不同處理器之間和不同執行緒之間的資料相依性不被編譯器與處理器考慮.
as-if-serial語意的意思指: 無論怎麼重排序(編譯器和處理器為了提升平行程度), (單執行緒)程式的執行結果不能被改變. 編譯器, runtime以及處理器都必須遵守as-if-serial語意.
為了遵守as-if-serial語意, 編譯器和處理器不會對存在資料相依性的操作進行重排序, 因為這種重排序會改變執行結果. 但是, 若操作之間不存在資料相依性, 這些操作可能被編譯器和處理器重排序. 更具體一點的說明, 可以看下面的圓面積計算程式範例:
上面三個操作的資料相依性如下圖所示:
如上圖所示, A與C之間存在資料相依性, 同時B與C之間也存在資料相依性. 因此在最終執行的指令序列中, C不能被重排序到A跟B的前面(C排到A和B的前面, 程式的結果就會被改變), 但A與B之間沒有資料相依性, 編譯器和處理器可以重排序A和B之間的執行順序, 下圖是該程式的兩種執行順序: as-if-serial語意把單執行緒程式保護了起來, 遵守as-if-serial語意的編譯器, runtime以及處理器共同為 編寫單執行緒程式的開發者創造了一個幻覺: 單執行緒程式是按程式的順序來執行的. as-if-serial語意使單執行緒程式開發者不需要擔心重排序會干擾他們, 也不需要擔心記憶體可見性的問題.
根據happens-before的程式順序規則, 上面計算圓面積的範例程式存在三個happens-before關係:
A happens-before B;
B happens-before C;
A happens-before C; 此處的第三個happens-before關係, 是根據happens-before的傳遞性推導出來的.
這裡A happens-before B, 但實際執行時B卻可以排在A之前執行(看上面的重排序後的執行順序). 在前一個章節(Basics)裡有提到過, 若A happens-before B, JMM並不要求A一定要在B之前執行. JMM僅僅要求前一個操作(執行的結果)對後一個操作可見, 且前一個操作按順序排在第二個操作之前. 此處操作A的執行結果不需要對操作B可見, 而且重排序操作A和操作B後的執行結果, 與操作A和操作B按happens-before順序執行的結果一致. 在這種情況下, JMM會認為這種重排序並不違法(not illegal), JMM會允許這種重排序.
在計算機中, 軟體技術跟硬體技術都有一個共同的目標: 在不改變程式執行結果的前提下, 盡可能的開發平行程度. 編譯器和處理器遵從這個目標, 從happens-before的定義我們就可以看出, JMM同樣遵從這一個目標.
從圖中我們不難看出, 猜測執行實質上對操作3與4進行了重排序. 重排序在這裡一樣破壞了多執行緒程式的語意.
在單執行緒程式中, 對存在控制相依性的操作進行重排序, 不會改變執行結果(這也是as-if-serial語意允許對存在控制相依性的操作進行重排序的原因); 但在多執行緒程式中, 對存在控制相依性的操作進行重排序, 可能會改變程式的執行結果.
根據 <JSR-133: JavaTM Memory Model and Thread Specification> (以下皆稱JSR133 SPEC)
第三章中對happens-before relationship的定義: Two actions can be ordered by a happens-before relationship.If one action happens-before another, then the first is visible to and ordered before the second.It should be stressed that a happens-before relationship between two actions does not imply that those actions must occur in that order in a Java platform implementation.
第五章的倒數第三段的原文: It should be noted that the presence of a happens-before relationship between two actions does not necessarily imply that they have to take place in that order in an implementation. If the reordering produces results consistent with a legal execution, it is not illegal.
由上面兩點我們可以這樣想:
對於一個Java的具體實作來說, 當兩個操作之間具有happens-before關係時, 該實作可以不按照這個happens-before關係指定的順序來執行. 若重排序之後執行產生的結果, 與程式按happens-before指定的順序執行產生的結果一致. 那麼這種重排序行為在JMM看來並不違法. 從上面這段話來看, JSR-133規範中的happens-before關係指定的是兩個操作之間的執行順序. 但Java的具體實作在保證程式正確性(程式的執行結果不被改變)的前提下, 可以不按照這個指定的順序來執行這兩個操作, 以下舉兩個例子:
此處的操作A happens-before B, 且兩者之間有資料相依性, 重排序會改變程式結果, 因此Java也會按照這個順序來執行操作.
此處的操作A happens-before B, 但兩者之間沒有資料相依性, 重排序不會改變程式結果, 因此Java可以違反這個順序來執行操作.
講白一點, 儘管兩個操作之間具有happens-before關係, 但Java實作可以違反這個順序來執行, 不過必須要滿足一個前提: 程式正確性(程式的執行結果不被改變).
這剛好也說明了一件事: JSR-133記憶體模型從表面上來看, 關注的是操作之間的執行順序(因為happens-before指定的是操作之間的執行順序); 但實際上, 其關注的是程式執行時語意的正確性(即程式的執行結果不能被改變). 這是個非常關鍵的差異, JSR-133的設計者通過這個差異, 在開發者/編譯器/處理器三者之間取得了一個很好的平衡: 一方面通過happens-before向開發者提供足夠強的記憶體可見性保證, 另一方面又盡可能少去束縛編譯器與處理器. 以文中的A happens-before B來說, JMM通過這個happens-before關係向開發者承諾: A的執行結果對B可見且A的執行順序排在B之前, 但私底下JMM會允許編譯器和處理器對這兩個操作進行重排序, 因為這種重排序不會改變程式的結果. 所以, 也可以把這種陽奉陰違的行為理解為JMM對開發者們的善意的謊言.
最後, 回到前面提到的, JSR-133 SPEC第3章對happens-before關係的定義:
若A happens-before B, 那麼JMM將向開發者保證: A操作的結果將對B可見, 且A的執行順序排在B之前. 但是, 這僅僅是JMM向開發者做出的保證, 倘若重排序A和B的執行順序後, 程式的結果不會被改變, 那麼JMM就允許編譯器和處理器對這兩個操作進行重排序.這麼做的原因是因為: 開發者對於這兩個操作是否真的被重排序並不關心, 開發者最關心的是程式執行時的語意不能被改變(即執行結果不能被改變).
因此, happens-before關係其本質上和as-if-serial語意是同一回事:
保證程式執行結果不改變
as-if-serial語意保證單執行緒內程式的執行結果不被改變
happens-before關係保證正確同步的多執行緒程式其結果不被改變
一切都是幻覺
as-if-serial給開發單執行緒程式的開發者建立了一個幻覺: 單執行緒程式是按照程式的順序來執行的.
happens-before給開發正確同步的多執行緒程式的開發者建立了一個幻覺: 正確同步的多執行緒程式是按照happens-before指定的順序來執行的
其實這就跟婚姻或兩性關係中, 其中一方陽奉陰違的行為(?)是一樣的, 只要表面看起來是好的就好.
至於重排序是否會影響多執行緒程式的執行結果呢? 以下是說明用的範例: 其中, flag變數是一個標記, 用來標示變數a是否已經被寫入. 此處假設有兩個執行緒A與B, A首先執行writer method, 隨後B執行緒接著執行reader method. 執行緒B在執行操作4時, 能否看到執行緒A在操作1對共享變數a的寫入?
由於操作1和操作2沒有資料相依性, 編譯器和處理器可以對這兩個操作進行重排序; 同樣, 操作3和操作4沒有資料相依性, 編譯器和處理器也可以對這兩個操作進行重排序. 以下就先以一張程式執行時序圖示範操作1和操作2重排序時, 會有什麼效果: 如圖所示, 操作1和操作2做了重排序. 程式執行時, 執行緒A首先寫入變數flag, 隨後執行緒B讀取這個變數. 由於條件判斷為真, 執行緒B將讀取變數a. 此時, 變數a根本還沒有被執行緒A寫入, 在這裡多執行緒程式的語意就被重排序給破壞了. (註: 本篇文章一律用紅虛線表示錯誤的讀操作, 用綠色虛線表示正確的讀操作.)
再來, 下面這張圖示範了操作3跟操作4重排序會產生什麼效果(借助這個重排序也可以順便解釋控制相依性). 在程式中, 操作3與操作4存在著控制相依性. 當程式中存在控制相依性時, 會影響指令序列執行的平行程度. 為此, 編譯器和處理器會採用猜測執行(Speculative Execution)來克服控制相依性對平行度的影響. 以處理器的猜測執行為例, 執行了執行緒B的處理器可以提前讀取並且計算a*a, 然後把計算結果臨時保存至 一個名為重排序緩衝(reorder buffer, ROB)的硬體快取中. 當接下來操作3的判斷條件為真時, 就把該計算結果寫入變數i中.
