什么是重排序

請先看這樣一段代碼1：

public class PossibleReordering {
static int x = 0, y = 0;
static int a = 0, b = 0;

public static void main(String[] args) throws InterruptedException {
    Thread one = new Thread(new Runnable() {
        public void run() {
            a = 1;
            x = b;
        }
    });
    
    Thread other = new Thread(new Runnable() {
        public void run() {
            b = 1;
            y = a;
        }
    });
    one.start();other.start();
    one.join();other.join();
    System.out.println(“(” + x + “,” + y + “)”);
}

很容易想到這段代碼的運行結果可能為(1,0)、(0,1)或(1,1)，因為線程one可以在線程two開始之前就執(zhí)行完了，也有可能反之，甚至有可能二者的指令是同時或交替執(zhí)行的。

然而，這段代碼的執(zhí)行結果也可能是(0,0). 因為，在實際運行時，代碼指令可能并不是嚴格按照代碼語句順序執(zhí)行的。得到(0,0)結果的語句執(zhí)行過程，如下圖所示。值得注意的是，a=1和x=b這兩個語句的賦值操作的順序被顛倒了，或者說，發(fā)生了指令“重排序”(reordering)。（事實上，輸出了這一結果，并不代表一定發(fā)生了指令重排序，內存可見性問題也會導致這樣的輸出，詳見后文）

重排序圖解

對重排序現(xiàn)象不太了解的開發(fā)者可能會對這種現(xiàn)象感到吃驚，但是，筆者開發(fā)環(huán)境下做的一個小實驗證實了這一結果2。

重排序實驗

實驗代碼是構造一個循環(huán)，反復執(zhí)行上面的實例代碼，直到出現(xiàn)a=0且b=0的輸出為止。實驗結果說明，循環(huán)執(zhí)行到第13830次時輸出了(0,0).

大多數現(xiàn)代微處理器都會采用將指令亂序執(zhí)行（out-of-order execution，簡稱OoOE或OOE）的方法，在條件允許的情況下，直接運行當前有能力立即執(zhí)行的后續(xù)指令，避開獲取下一條指令所需數據時造成的等待3。通過亂序執(zhí)行的技術，處理器可以大大提高執(zhí)行效率。

除了處理器，常見的Java運行時環(huán)境的JIT編譯器也會做指令重排序操作4，即生成的機器指令與字節(jié)碼指令順序不一致。

as-if-serial語義

As-if-serial語義的意思是，所有的動作(Action)5都可以為了優(yōu)化而被重排序，但是必須保證它們重排序后的結果和程序代碼本身的應有結果是一致的。Java編譯器、運行時和處理器都會保證單線程下的as-if-serial語義。 比如，為了保證這一語義，重排序不會發(fā)生在有數據依賴的操作之中。

• int a = 1;
• int b = 2;
• int c = a + b;

將上面的代碼編譯成Java字節(jié)碼或生成機器指令，可視為展開成了以下幾步動作（實際可能會省略或添加某些步驟）。

1. 對a賦值1
2. 對b賦值2
3. 取a的值
4. 取b的值
5. 將取到兩個值相加后存入c

在上面5個動作中，動作1可能會和動作2、4重排序，動作2可能會和動作1、3重排序，動作3可能會和動作2、4重排序，動作4可能會和1、3重排序。但動作1和動作3、5不能重排序。動作2和動作4、5不能重排序。因為它們之間存在數據依賴關系，一旦重排，as-if-serial語義便無法保證。

為保證as-if-serial語義，Java異常處理機制也會為重排序做一些特殊處理。例如在下面的代碼中，y = 0 / 0可能會被重排序在x = 2之前執(zhí)行，為了保證最終不致于輸出x = 1的錯誤結果，JIT在重排序時會在catch語句中插入錯誤代償代碼，將x賦值為2，將程序恢復到發(fā)生異常時應有的狀態(tài)。這種做法的確將異常捕捉的邏輯變得復雜了，但是JIT的優(yōu)化的原則是，盡力優(yōu)化正常運行下的代碼邏輯，哪怕以catch塊邏輯變得復雜為代價，畢竟，進入catch塊內是一種“異常”情況的表現(xiàn)。6

public class Reordering {
    public static void main(String[] args) {
        int x, y;
        x = 1;
        try {
            x = 2;
            y = 0 / 0;    
        } catch (Exception e) {
        } finally {
            System.out.println("x = " + x);
        }
    }
}

內存訪問重排序與內存可見性

計算機系統(tǒng)中，為了盡可能地避免處理器訪問主內存的時間開銷，處理器大多會利用緩存(cache)以提高性能。

其模型如下圖所示：

處理器Cache模型

在這種模型下會存在一個現(xiàn)象，即緩存中的數據與主內存的數據并不是實時同步的，各CPU（或CPU核心）間緩存的數據也不是實時同步的。這導致在同一個時間點，各CPU所看到同一內存地址的數據的值可能是不一致的。從程序的視角來看，就是在同一個時間點，各個線程所看到的共享變量的值可能是不一致的。

有的觀點會將這種現(xiàn)象也視為重排序的一種，命名為“內存系統(tǒng)重排序”。因為這種內存可見性問題造成的結果就好像是內存訪問指令發(fā)生了重排序一樣。

這種內存可見性問題也會導致章節(jié)一中示例代碼即便在沒有發(fā)生指令重排序的情況下的執(zhí)行結果也還是(0, 0)。

內存訪問重排序與Java內存模型

Java的目標是成為一門平臺無關性的語言，即Write once, run anywhere. 但是不同硬件環(huán)境下指令重排序的規(guī)則不盡相同。例如，x86下運行正常的Java程序在IA64下就可能得到非預期的運行結果。為此，JSR-1337制定了Java內存模型(Java Memory Model, JMM)，旨在提供一個統(tǒng)一的可參考的規(guī)范，屏蔽平臺差異性。從Java 5開始，Java內存模型成為Java語言規(guī)范的一部分。

根據Java內存模型中的規(guī)定，可以總結出以下幾條happens-before規(guī)則8。

Happens-before的前后兩個操作不會被重排序且后者對前者的內存可見。

• 程序次序法則：線程中的每個動作A都happens-before于該線程中的每一個動作B，其中，在程序中，所有的動作B都能出現(xiàn)在A之后。
• 監(jiān)視器鎖法則：對一個監(jiān)視器鎖的解鎖 happens-before于每一個后續(xù)對同一監(jiān)視器鎖的加鎖。
• volatile變量法則：對volatile域的寫入操作happens-before于每一個后續(xù)對同一個域的讀寫操作。
• 線程啟動法則：在一個線程里，對Thread.start的調用會happens-before于每個啟動線程的動作。
• 線程終結法則：線程中的任何動作都happens-before于其他線程檢測到這個線程已經終結、或者從Thread.join調用中成功返回，或Thread.isAlive返回false。
• 中斷法則：一個線程調用另一個線程的interrupt happens-before于被中斷的線程發(fā)現(xiàn)中斷。
• 終結法則：一個對象的構造函數的結束happens-before于這個對象finalizer的開始。
• 傳遞性：如果A happens-before于B，且B happens-before于C，則A happens-before于C

Happens-before關系只是對Java內存模型的一種近似性的描述，它并不夠嚴謹，但便于日常程序開發(fā)參考使用，關于更嚴謹的Java內存模型的定義和描述，請閱讀JSR-133原文或Java語言規(guī)范章節(jié)17.4。

除此之外，Java內存模型對volatile和final的語義做了擴展。對volatile語義的擴展保證了volatile變量在一些情況下不會重排序，volatile的64位變量double和long的讀取和賦值操作都是原子的。對final語義的擴展保證一個對象的構建方法結束前，所有final成員變量都必須完成初始化（的前提是沒有this引用溢出）。

Java內存模型關于重排序的規(guī)定，總結后如下表所示：

重排序示意表

表中“第二項操作”的含義是指，第一項操作之后的所有指定操作。如，普通讀不能與其之后的所有volatile寫重排序。另外，JMM也規(guī)定了上述volatile和同步塊的規(guī)則盡適用于存在多線程訪問的情景。例如，若編譯器（這里的編譯器也包括JIT，下同）證明了一個volatile變量只能被單線程訪問，那么就可能會把它做為普通變量來處理。

留白的單元格代表允許在不違反Java基本語義的情況下重排序。例如，編譯器不會對對同一內存地址的讀和寫操作重排序，但是允許對不同地址的讀和寫操作重排序。

除此之外，為了保證final的新增語義。JSR-133對于final變量的重排序也做了限制。

• 構建方法內部的final成員變量的存儲，并且，假如final成員變量本身是一個引用的話，這個final成員變量可以引用到的一切存儲操作，都不能與構建方法外的將當期構建對象賦值于多線程共享變量的存儲操作重排序。例如對于如下語句：

x.finalField = v; … ;構建方法邊界sharedRef = x; v.afield = 1; x.finalField = v; … ; 構建方法邊界sharedRef = x;

這兩條語句中，構建方法邊界前后的指令都不能重排序。

• 初始讀取共享對象與初始讀取該共享對象的final成員變量之間不能重排序。例如對于如下語句：

x = sharedRef; … ; i = x.finalField;

前后兩句語句之間不會發(fā)生重排序。由于這兩句語句有數據依賴關系，編譯器本身就不會對它們重排序，但確實有一些處理器會對這種情況重排序，因此特別制定了這一規(guī)則。

內存屏障

內存屏障（Memory Barrier，或有時叫做內存柵欄，Memory Fence）是一種CPU指令，用于控制特定條件下的重排序和內存可見性問題。Java編譯器也會根據內存屏障的規(guī)則禁止重排序。

內存屏障可以被分為以下幾種類型：

• LoadLoad屏障：對于這樣的語句Load1; LoadLoad; Load2，在Load2及后續(xù)讀取操作要讀取的數據被訪問前，保證Load1要讀取的數據被讀取完畢。
• StoreStore屏障：對于這樣的語句Store1; StoreStore; Store2，在Store2及后續(xù)寫入操作執(zhí)行前，保證Store1的寫入操作對其它處理器可見。
• LoadStore屏障：對于這樣的語句Load1; LoadStore; Store2，在Store2及后續(xù)寫入操作被刷出前，保證Load1要讀取的數據被讀取完畢。
• StoreLoad屏障：對于這樣的語句Store1; StoreLoad; Load2，在Load2及后續(xù)所有讀取操作執(zhí)行前，保證Store1的寫入對所有處理器可見。它的開銷是四種屏障中最大的。在大多數處理器的實現(xiàn)中，這個屏障是個萬能屏障，兼具其它三種內存屏障的功能。

有的處理器的重排序規(guī)則較嚴，無需內存屏障也能很好的工作，Java編譯器會在這種情況下不放置內存屏障。

為了實現(xiàn)上一章中討論的JSR-133的規(guī)定，Java編譯器會這樣使用內存屏障。

內存屏障示意表

為了保證final字段的特殊語義，也會在下面的語句加入內存屏障。

x.finalField = v; StoreStore; sharedRef = x;

Intel 64/IA-32架構下的內存訪問重排序

Intel 64和IA-32是我們較常用的硬件環(huán)境，相對于其它處理器而言，它們擁有一種較嚴格的重排序規(guī)則。Pentium 4以后的Intel 64或IA-32處理的重排序規(guī)則如下。9

在單CPU系統(tǒng)中：

• 讀操作不與其它讀操作重排序。
• 寫操作不與其之前的寫操作重排序。
• 寫內存操作不與其它寫操作重排序，但有以下幾種例外
• CLFLUSH的寫操作
• 帶有non-temporal move指令(MOVNTI, MOVNTQ, MOVNTDQ, MOVNTPS, and MOVNTPD)的streaming寫入。
• 字符串操作
• 讀操作可能會與其之前的寫不同位置的寫操作重排序，但不與其之前的寫相同位置的寫操作重排序。
• 讀和寫操作不與I/O指令，帶鎖的指令或序列化指令重排序。
• 讀操作不能重排序到LFENCE和MFENCE之前。
• 寫操作不能重排序到LFENCE、SFENCE和MFENCE之前。
• LFENCE不能重排序到讀操作之前。
• SFENCE不能重排序到寫之前。
• MFENCE不能重排序到讀或寫操作之前。

在多處理器系統(tǒng)中：

• 各自處理器內部遵循單處理器的重排序規(guī)則。
• 單處理器的寫操作對所有處理器可見是同時的。
• 各自處理器的寫操作不會重排序。
• 內存重排序遵守因果性(causality)（內存重排序遵守傳遞可見性）。
• 任何寫操作對于執(zhí)行這些寫操作的處理器之外的處理器來看都是一致的。
• 帶鎖指令是順序執(zhí)行的。

值得注意的是，對于Java編譯器而言，Intel 64/IA-32架構下處理器不需要LoadLoad、LoadStore、StoreStore屏障，因為不會發(fā)生需要這三種屏障的重排序。

一例Intel 64/IA-32架構下的代碼性能優(yōu)化

現(xiàn)在有這樣一個場景，一個容器可以放一個東西，容器支持create方法來創(chuàng)建一個新的東西并放到容器里，支持get方法取到這個容器里的東西。我們可以較容易地寫出下面的代碼：

public class Container {
    public static class SomeThing {
        private int status;

        public SomeThing() {
            status = 1;
        }

        public int getStatus() {
            return status;
        }
    }

    private SomeThing object;

    public void create() {
        object = new SomeThing();
    }

    public SomeThing get() {
        while (object == null) {
            Thread.yield(); //不加這句話可能會在此出現(xiàn)無限循環(huán)
        }
        return object;
    }
}

在單線程場景下，這段代碼執(zhí)行起來是沒有問題的。但是在多線程并發(fā)場景下，由不同的線程create和get東西，這段代碼是有問題的。問題的原因與普通的雙重檢查鎖定單例模式(Double Checked Locking,DCL)10類似，即SomeThing的構建與將指向構建中的SomeThing引用賦值到object變量這兩者可能會發(fā)生重排序。導致get中返回一個正被構建中的不完整的SomeThing對象實例。為了解決這一問題，通常的辦法是使用volatile修飾object字段。這種方法避免了重排序，保證了內存可見性，摒棄比使用同步塊導致的性能損失更小。但是，假如使用場景對object的內存可見性并不敏感的話（不要求一個線程寫入了object，object的新值立即對下一個讀取的線程可見），在Intel 64/IA-32環(huán)境下，有更好的解決方案。

根據上一章的內容，我們知道Intel 64/IA-32下寫操作之間不會發(fā)生重排序，即在處理器中，構建SomeThing對象與賦值到object這兩個操作之間的順序性是可以保證的。這樣看起來，僅僅使用volatile來避免重排序是多此一舉的。但是，Java編譯器卻可能生成重排序后的指令。但令人高興的是，Oracle的JDK中提供了Unsafe. putOrderedObject，Unsafe. putOrderedInt，Unsafe. putOrderedLong這三個方法，JDK會在執(zhí)行這三個方法時插入StoreStore內存屏障，避免發(fā)生寫操作重排序。而在Intel 64/IA-32架構下，StoreStore屏障并不需要，Java編譯器會將StoreStore屏障去除。比起寫入volatile變量之后執(zhí)行StoreLoad屏障的巨大開銷，采用這種方法除了避免重排序而帶來的性能損失以外，不會帶來其它的性能開銷。

我們將做一個小實驗來比較二者的性能差異。一種是使用volatile修飾object成員變量。

public class Container {
    public static class SomeThing {
        private int status;

        public SomeThing() {
            status = 1;
        }

        public int getStatus() {
            return status;
        }
    }

    private volatile  SomeThing object;

    public void create() {
        object = new SomeThing();
    }

    public SomeThing get() {
        while (object == null) {
            Thread.yield(); //不加這句話可能會在此出現(xiàn)無限循環(huán)
        }
        return object;
    }
}

一種是利用Unsafe. putOrderedObject在避免在適當的位置發(fā)生重排序。

public class Container {
    public static class SomeThing {
        private int status;

        public SomeThing() {
            status = 1;
        }

        public int getStatus() {
            return status;
        }
    }

    private SomeThing object;

    private Object value;
    private static final Unsafe unsafe = getUnsafe();
    private static final long valueOffset;
    static {
        try {
            valueOffset = unsafe.objectFieldOffset(Container.class.getDeclaredField("value"));
        } catch (Exception ex) { throw new Error(ex); }
    }

    public void create() {
        SomeThing temp = new SomeThing();
        unsafe.putOrderedObject(this, valueOffset, null);	//將value賦null值只是一項無用操作，實際利用的是這條語句的內存屏障
        object = temp;
    }

    public SomeThing get() {
        while (object == null) {
            Thread.yield();
        }
        return object;
    }


    public static Unsafe getUnsafe() {
        try {
            Field f = Unsafe.class.getDeclaredField("theUnsafe");
            f.setAccessible(true);
            return (Unsafe)f.get(null);
        } catch (Exception e) {
        }
        return null;
    }
}

由于直接調用Unsafe.getUnsafe()需要配置JRE獲取較高權限，我們利用反射獲取Unsafe中的theUnsafe來取得Unsafe的可用實例。

unsafe.putOrderedObject(this, valueOffset, null) 這句僅僅是為了借用這句話功能的防止寫重排序，除此之外無其它作用。

利用下面的代碼分別測試兩種方案的實際運行時間。在運行時開啟-server和 -XX:CompileThreshold=1以模擬生產環(huán)境下長時間運行后的JIT優(yōu)化效果。

public static void main(String[] args) throws InterruptedException {
    final int THREADS_COUNT = 20;
    final int LOOP_COUNT = 100000;

    long sum = 0;
    long min = Integer.MAX_VALUE;
    long max = 0;
    for(int n = 0;n <= 100;n++) {
        final Container basket = new Container();
        List<Thread> putThreads = new ArrayList<Thread>();
        List<Thread> takeThreads = new ArrayList<Thread>();
        for (int i = 0; i < THREADS_COUNT; i++) {
            putThreads.add(new Thread() {
                @Override
                public void run() {
                    for (int j = 0; j < LOOP_COUNT; j++) {
                        basket.create();
                    }
                }
            });
            takeThreads.add(new Thread() {
                @Override
                public void run() {
                    for (int j = 0; j < LOOP_COUNT; j++) {
                        basket.get().getStatus();
                    }
                }
            });
        }
        long start = System.nanoTime();
        for (int i = 0; i < THREADS_COUNT; i++) {
            takeThreads.get(i).start();
            putThreads.get(i).start();
        }
        for (int i = 0; i < THREADS_COUNT; i++) {
            takeThreads.get(i).join();
            putThreads.get(i).join();
        }
        long end = System.nanoTime();
        long period = end - start;
        if(n == 0) {
            continue;	//由于JIT的編譯，第一次執(zhí)行需要更多時間，將此時間不計入統(tǒng)計
        }
        sum += (period);
        System.out.println(period);
        if(period < min) {
            min = period;
        }
        if(period > max) {
            max = period;
        }
    }
    System.out.println("Average : " + sum / 100);
    System.out.println("Max : " + max);
    System.out.println("Min : " + min);
}

在筆者的計算機上運行測試，采用volatile方案的運行結果如下：

Average : 62535770

Max : 82515000

Min : 45161000

采用unsafe.putOrderedObject方案的運行結果如下：

Average : 50746230

Max : 68999000

Min : 38038000

從結果看出，unsafe.putOrderedObject方案比volatile方案平均耗時減少18.9%，最大耗時減少16.4%，最小耗時減少15.8%.另外，即使在其它會發(fā)生寫寫重排序的處理器中，由于StoreStore屏障的性能損耗小于StoreLoad屏障，采用這一方法也是一種可行的方案。但值得再次注意的是，這一方案不是對volatile語義的等價替換，而是在特定場景下做的特殊優(yōu)化，它僅避免了寫寫重排序，但不保證內存可見性。

總結

以上為個人經驗，希望能給大家一個參考，也希望大家多多支持腳本之家。