摘要：前言在上一篇文章中多線程奇幻之旅算法實現線程安全，我們介紹了和方式實現線程安全類的方法，兩種方式一個是鎖定阻塞方式，一個是非阻塞方式。

在上一篇文章中《Java多線程奇幻之旅——CAS算法實現線程安全》，我們介紹了Synchronized和CAS方式實現線程安全類的方法，兩種方式一個是鎖定阻塞方式，一個是非阻塞方式。本文專注于兩種實現方式效率問題。本文是上篇文章的延續，會借用到上文中的代碼，如果沒有閱讀前文請先前往閱讀。

在設計試驗方法之前，針對Synchronized和CAS兩種方式的特點，我們先來思考一下兩種方式效率如何？
首先，我們在回顧一下兩種方式是如何保證線程安全的。Synchronized方式通過大家應該很熟悉，他的行為非常悲觀，只要有一個線程進入Synchronized臨界區域（確保不被多線程并發訪問的區域），其他線程均不能進入，直到早先進入的線程退出臨界區域。和Synchronized相比CAS算法則顯得樂觀多了，他不限制其他線程進入臨界區域，但是當一個線程退出臨界區域的時候，他必須檢查臨界區域內數據是否被其他線程修改，一旦被修改，此線程就要做重試操作。

我們舉一個生活化的例子加深理解：
我們把線程比作在馬路上行駛的汽車，臨界區比作道路交叉的十字路口。
如果所有馬路上只有一輛車（單線程情況），那么我們無需任何處理。如果馬路上不只一輛車要通過十字路口（多線程情況），并且我們不允許車輛在十字路口相撞（線程沖突情況），那么我們必須需要做出一些限制來避免同時通過十字路口的車輛相互碰撞（保證線程安全）。Synchronized方式相當于在路口設置紅綠燈，用“紅燈停，綠燈行”的基本原則限制兩側路口的汽車同時進入十字路口。而CAS方式就要評司機自覺了，一旦一輛汽車進入十字路口后發現已經有另一輛汽車進入十字路口，他需要退出十字路口重新進入。
我們用生活經驗想象一下兩種方式的車輛通行效率，我們經常看到在車流不高的路口汽車白白等待紅綠燈，顯然在車輛比較少的路口設置紅綠燈很有可能影響通行效率，所有晚上一旦車流下降，某些路口紅綠燈會關閉以調高通過效率。我們也看到在某個高峰時段由于路口紅綠燈損壞造成的車輛擁堵，這說明在車流量較多的情況下，紅綠燈的使用恰恰能避免擁堵發生。
通過紅綠燈的例子我們可以假設，當線程競爭比較少的情況下，CAS算法效率較高，反之，Synchronized方式效率較高。

借用上文中兩種“棧”的代碼，構建測試方法：

public static void main(String[] args) {
    long amount = 0;
    int max = 1000;
    for (int k = 0; k < max; k++) {
        long start =System.nanoTime();
        int loops = 1000;
        //分別運行不同的進程數1、2、、4、8、16、32、64...
        int threads =1;
        //分別運行不同的Stack類。
        //SynchronizedStack stack = new SynchronizedStack();
        TreiberStack  stack=new TreiberStack();
        ExecutorService pool = Executors.newCachedThreadPool();
        for (int j = 0; j < threads; j++) {
            pool.submit(new Runnable() {
                @Override
                public void run() {
                    for (int i = 0; i < loops; i++) {
                        stack.push("a");
                    }
                }
            });
        }
        pool.shutdown();
        try {
            pool.awaitTermination(1, TimeUnit.HOURS);
        } catch (InterruptedException e) {
        }
        long end = System.nanoTime();
        System.out.println("每次用時：" + (end - start));

        amount += end - start;
    }
    System.out.println("平均用時：" + amount / max);
}

設置不同的threads的值并切換SynchronizedStack類或者TreiberStack類后運行結果如下:

在線程數較少，競爭較少的情況下TreiberStack和SynchronizedStack運行結果差距很小，但是隨著線程數的增多，競爭加劇，TreiberStack較SynchronizedStack執行時間明顯延長。

為什么在線程數較少的情況下TreiberStack和SynchronizedStack沒有明顯差別？
在JDK1.6以后對synchronized關鍵字做了優化，導致加鎖的效率提升，所以和非阻塞方式相比效率也不會相差很多。

為什么在線程數較多的情況下TreiberStack和SynchronizedStack差別越來越大？
主要原因在于TreiberStack在高并發的情況下會產生大量的競爭，造成大量重試操作。
我們改造一下TreiberStack類，演示這種情況：

public class TreiberStack {
    private AtomicReference> headNode = new AtomicReference<>();
    //記錄實際執行次數
    public static final LongAdder adder=new LongAdder();
    public void push(E item) {
        Node newHead = new Node<>(item);
        Node oldHead;
        do {
            adder.increment();
            oldHead = headNode.get();
            newHead.next = oldHead;
        } while (!headNode.compareAndSet(oldHead, newHead));
    }
    public E pop() {
        Node oldHead;
        Node newHead;
        do {
            oldHead = headNode.get();
            if (oldHead == null)
                return null;
            newHead = oldHead.next;
        } while (!headNode.compareAndSet(oldHead, newHead));
        return oldHead.item;
    }
    private static class Node {
        public final E item;
        public Node next;

        public Node(E item) {
            this.item = item;
        }
    }
}

運行測試方法：

public static void main(String[] args) {
    int loops = 1000;
    //分別運行不同的進程數1、2、、4、8、16、32、64...
    int threads =1;
    TreiberStack  stack=new TreiberStack();
    ExecutorService pool = Executors.newCachedThreadPool();
    for (int j = 0; j < threads; j++) {
        pool.submit(new Runnable() {
            @Override
            public void run() {
                for (int i = 0; i < loops; i++) {
                    stack.push("a");
                }
            }
        });
    }
    pool.shutdown();
    try {
        pool.awaitTermination(1, TimeUnit.HOURS);
    } catch (InterruptedException e) {
    }
    System.out.println("希望執行次數："+ loops*threads +"；希望執行次數："+ stack.adder.longValue());
}

執行結果如下：

通過結果我們可以發現，隨著線程數增多，實際執行結果數越來越多，說明沖突增多重試次數增多。

通過“提出假設——驗證假設——證明假設”這一過程，我們確定Synchronized方式和CAS方式在競爭較少的時候性能相差不大，后者略優于前者，而隨著沖突加劇，后者性能較前者顯著下降。
如果你親自運行文中測試方法，你還會發現一個現象，無論是TreiberStack類的運行時間還是實際執行次數，在同一線程數下每次運行結果差別較大，而SynchronizedStack類的結果較穩定，可見CAS方式執行的隨機性比較大，而Synchronized方式相對穩定。