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

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

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

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

借用上文中兩種“?！钡拇a，構(gòu)建測試方法：

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;
        //分別運(yùn)行不同的進(jìn)程數(shù)1、2、、4、8、16、32、64...
        int threads =1;
        //分別運(yùn)行不同的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);
}

設(shè)置不同的threads的值并切換SynchronizedStack類或者TreiberStack類后運(yùn)行結(jié)果如下:

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

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

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

public class TreiberStack {
    private AtomicReference> headNode = new AtomicReference<>();
    //記錄實際執(zhí)行次數(shù)
    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;
        }
    }
}

運(yùn)行測試方法：

public static void main(String[] args) {
    int loops = 1000;
    //分別運(yùn)行不同的進(jìn)程數(shù)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("希望執(zhí)行次數(shù)："+ loops*threads +"；希望執(zhí)行次數(shù)："+ stack.adder.longValue());
}

執(zhí)行結(jié)果如下：

通過結(jié)果我們可以發(fā)現(xiàn)，隨著線程數(shù)增多，實際執(zhí)行結(jié)果數(shù)越來越多，說明沖突增多重試次數(shù)增多。

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