資料依賴性
如果兩個操作存取同一個變量,且這兩個操作中有一個為寫入操作,此時這兩個操作之間就存在資料依賴性。資料依賴分成下列三種:
名稱
程式碼範例
說明
寫後讀
a = 1;b = a;
寫一個變數之後,再讀這個位置。
寫後寫
a = 1;a = 2;
寫一個變數之後,再寫這個變數。
讀後寫
a = b;b = 1;
讀一個變數之後,再寫這個變數。
上面三種情況,只要重排序兩個操作的執行順序,程式的執行結果將會被改變。
前面提到過,編譯器和處理器可能會對操作做重排序。編譯器和處理器在重新排序時,會遵守資料依賴性,編譯器和處理器不會改變存在資料依賴關係的兩個操作的執行順序。
注意,這裡所說的資料依賴性僅針對單一處理器中執行的指令序列和單一執行緒中執行的操作,不同處理器之間和不同執行緒之間的資料依賴性不被編譯器和處理器考慮。
as-if-serial語意
as-if-serial語意的意思是指:不管怎麼重排序(編譯器和處理器為了提高並行度),(單執行緒)程式的執行結果不能被改變。編譯器,runtime 和處理器都必須遵守as-if-serial語意。
為了遵守as-if-serial語義,編譯器和處理器不會對存在資料相依性的操作做重排序,因為這種重排序會改變執行結果。但是,如果操作之間不存在資料依賴關係,這些操作可能會被編譯器和處理器重新排序。為了具體說明,請看下面計算圓面積的程式碼範例:
double pi = 3.14; //A double r = 1.0; //B double area = pi * r * r; //C
上面三個操作的資料相依性如下圖所示:
如上圖所示,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;
這裡的第3個happens- before關係,是根據happens- before的傳遞性推導出來的。
這裡A happens- before B,但實際執行時B卻可以排在A之前執行(看上面的重排序後的執行順序)。在第一章提到過,如果A happens- before B,JMM並不要求A一定要在B之前執行。 JMM只要求前一個操作(執行的結果)對後一個操作可見,且前一個操作依序排在第二個操作之前。這裡操作A的執行結果不需要對操作B可見;而且重排序操作A和操作B後的執行結果,與操作A和操作B按happens- before順序執行的結果一致。在這種情況下,JMM會認為這種重新排序並不非法(not illegal),JMM允許這種重新排序。
在電腦中,軟體技術和硬體技術有一個共同的目標:在不改變程式執行結果的前提下,盡可能的開發並行度。編譯器和處理器遵從這個目標,從happens- before的定義我們可以看出,JMM同樣遵從這個目標。
重排序對多執行緒的影響
現在讓我們來看看,重排序是否會改變多執行緒程式的執行結果。請看下面的範例程式碼:
class ReorderExample { int a = 0; boolean flag = false; public void writer() { a = 1; //1 flag = true; //2 } Public void reader() { if (flag) { //3 int i = a * a; //4 …… } } }
flag變數是個標記,用來識別變數a是否已被寫入。這裡假設有兩個執行緒A和B,A先執行writer()方法,接著B執行緒接著執行reader()方法。執行緒B在執行操作4時,能否看到執行緒A在操作1對共享變數a的寫入?
答案是:不一定能看到。
由於操作1和操作2沒有資料依賴關係,編譯器和處理器可以對這兩個操作重排序;同樣,操作3和操作4沒有資料依賴關係,編譯器和處理器也可以對這兩個操作重排序。讓我們先來看看,當操作1和操作2重排序時,可能會產生什麼效果?請看下面的程式執行時序圖:
如上圖所示,操作1和操作2做了重排序。程式執行時,執行緒A先寫標記變數flag,隨後執行緒B讀這個變數。由於條件判斷為真,因此線程B將讀取變數a。此時,變數a還根本沒有被線程A寫入,在這裡多執行緒程式的語意被重排序破壞了!
※註:本文統一以紅色的虛箭線表示錯誤的讀取操作,以綠色的虛箭線表示正確的讀取操作。
下面再讓我們看看,當操作3和操作4重排序時會產生什麼效果(借助這個重排序,可以順便說明控制依賴性)。以下是操作3和操作4重新排序後,程式的執行時序圖:
在程式中,操作3和操作4有控制依賴關係。當程式碼中存在控制依賴性時,會影響指令序列執行的平行度。為此,編譯器和處理器會採用猜測(Speculation)執行來克服控制相關性對平行度的影響。以處理器的猜測執行為例,執行緒B的處理器可以提前讀取併計算a*a,然後把計算結果暫時保存到一個名為重排序緩衝(reorder buffer ROB)的硬體快取中。當接下來操作3的條件判斷為真時,就把該計算結果寫入變數i中。
從圖中我們可以看出,猜測執行實質上對操作3和4做了重新排序。重排序在這裡破壞了多執行緒程式的語意!
在單執行緒程式中,對存在控制依賴的操作重排序,不會改變執行結果(這也是as-if-serial語義允許對存在控制依賴的操作做重排序的原因);但在多執行緒程序中,對存在控制依賴的操作重排序,可能會改變程式的執行結果。
以上就是Java記憶體模型深度解析:重新排序的內容,更多相關內容請關注PHP中文網(www.php.cn)!