重排序

一、重排序。

1、為什么需要重排序？

? ?現在的CPU一般采用流水線來執行指令。一個指令的執行被分成：取指、譯碼、訪存、執行、寫回、等若干個階段。然后，多條指令可以同時存在于流水線中，同時被執行。

指令流水線并不是串行的，并不會因為一個耗時很長的指令在“執行”階段呆很長時間，而導致后續的指令都卡在“執行”之前的階段上。我們編寫的程序都要經過優化后（編譯器和處理器會對我們的程序進行優化以提高運行效率）才會被運行，優化分為很多種，其中有一種優化叫做重排序，重排序需要遵守as-if-serial規則和happens-before規則，不能說你想怎么排就怎么排，如果那樣豈不是亂了套。重排序的目的是為了性能。

Example:
理想情況下：
過程A：cpu0—寫入1—> bank0；
過程B：cpu0—寫入2—> bank1；
如果bank0狀態為busy, 則A過程需要等待
如果進行重排序，則直接可以先執行B過程。

2、重排序分類。

在執行程序時，為了提高性能，編譯器和處理器會對指令做重排序。

編譯器優化重排序：編譯器在不改變單線程程序語義的前提下，可以重新安排語句的執行順序。
指令級并行的重排序：如果不存l在數據依賴性，處理器可以改變語句對應機器指令的執行順序。
內存系統的重排序：處理器使用緩存和讀寫緩沖區，這使得加載和存儲操作看上去可能是在亂序執行。

但是，可以通過插入特定類型的Memory Barrier來禁止特定類型的編譯器重排序和處理器重排序。

3、重排序過程。

一個好的內存模型實際上會放松對處理器和編譯器規則的束縛，也就是說軟件技術和硬件技術都為同一個目標而進行奮斗：在不改變程序執行結果的前提下，盡可能提高并行度。JMM對底層盡量減少約束，使其能夠發揮自身優勢。因此，在執行程序時，為了提高性能，編譯器和處理器常常會對指令進行重排序。一般重排序可以分為如下三種：

從源碼到最終執行的指令序列的示意圖

編譯器優化的重排序。編譯器在不改變單線程程序語義的前提下，可以重新安排語句的執行順序；
指令級并行的重排序。現代處理器采用了指令級并行技術來將多條指令重疊執行。如果不存在數據依賴性，處理器可以改變語句對應機器指令的執行順序；
內存系統的重排序。由于處理器使用緩存和讀/寫緩沖區，這使得加載和存儲操作看上去可能是在亂序執行的。

如圖，1屬于編譯器重排序，而2和3統稱為處理器重排序。這些重排序會導致線程安全的問題，一個很經典的例子就是DCL問題。針對編譯器重排序，JMM的編譯器重排序規則會禁止一些特定類型的編譯器重排序；針對處理器重排序，編譯器在生成指令序列的時候會通過插入內存屏障指令來禁止某些特殊的處理器重排序。

那么什么情況下，不能進行重排序了？下面就來說說數據依賴性。有如下代碼：

double pi = 3.14 //A

double r = 1.0 //B

double area = pi * r * r //C

這是一個計算圓面積的代碼，由于A,B之間沒有任何關系，對最終結果也不會存在關系，它們之間執行順序可以重排序。因此可以執行順序可以是A->B->C或者B->A->C執行最終結果都是3.14，即A和B之間沒有數據依賴性。具體的定義為：如果兩個操作訪問同一個變量，且這兩個操作有一個為寫操作，此時這兩個操作就存在數據依賴性這里就存在三種情況：1. 讀后寫；2.寫后寫；3. 寫后讀，者三種操作都是存在數據依賴性的，如果重排序會對最終執行結果會存在影響。編譯器和處理器在重排序時，會遵守數據依賴性，編譯器和處理器不會改變存在數據依賴性關系的兩個操作的執行順序。

4、重排序對多線程的影響。

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線程執行 writer 方法，B線程執行 reader 方法，線程B在執行4操作的時候，能否看到線程A對a的寫入操作？

答案是: 不一定！

由于操作1和操作2沒有數據依賴關系，編譯器和處理器可以對這兩個操作重排序。

如果操作1和操作2做了重排序，程序執行時，線程A首先寫標記變量 flag，隨后線程 B 讀這個變量。由于條件判斷為真，線程 B 將讀取變量a。此時，變量 a 還根本沒有被線程 A 寫入，在這里多線程程序的語義被重排序破壞了！

二、數據依賴性。

如果兩個操作訪問同一個變量，且這兩個操作中有一個為寫操作，此時這兩個操作之間就存在數據依賴性。數據依賴分下列三種類型：

名稱	代碼示例	說明
寫后讀	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規則。

具體的一共有六項規則：

1、程序順序規則。（可見性）

一個線程中的每個操作，happens-before于該線程中的任意后續操作。程序順序規則中所說的每個操作happens-before于該線程中的任意后續操作并不是說前一個操作必須要在后一個操作之前執行，而是指前一個操作的執行結果必須對后一個操作可見，如果不滿足這個要求那就不允許這兩個操作進行重排序。