Java? 5.0 第一次讓使用 Java 語言開發(fā)非阻塞算法成為可能， java.util.concurrent 包充分地利用了這個(gè)功能。非阻塞算法屬于并發(fā)算法，它們可以安全地派生它們的線程，不通過鎖定派生，而是通過低級(jí)的原子性的硬件原生形式 —— 例如 比較和交換 。非阻塞算法的設(shè)計(jì)與實(shí)現(xiàn)極為困難，但是它們能夠提供更好的吞吐率，對(duì)生存問題（例如死鎖和優(yōu)先級(jí)反轉(zhuǎn)）也能提供更好的防御。在這期的 Java 理論與實(shí)踐 中，并發(fā)性大師 Brian Goetz 演示了幾種比較簡(jiǎn)單的非阻塞算法的工作方式。

在不只一個(gè)線程訪問一個(gè)互斥的變量時(shí)，所有線程都必須使用同步，否則就可能會(huì)發(fā)生一些非常糟糕的事情。Java 語言中主要的同步手段就是 synchronized 關(guān)鍵字（也稱為 內(nèi)在鎖 ），它強(qiáng)制實(shí)行互斥，確保執(zhí)行 synchronized 塊的線程的動(dòng)作，能夠被后來執(zhí)行受相同鎖保護(hù)的 synchronized 塊的其他線程看到。在使用得當(dāng)?shù)臅r(shí)候，內(nèi)在鎖可以讓程序做到線程安全，但是在使用鎖定保護(hù)短的代碼路徑，而且線程頻繁地爭(zhēng)用鎖的時(shí)候，鎖定可能成為相當(dāng)繁重的操作。

在 “流行的原子” 一文中，我們研究了 原子變量 ，原子變量提供了原子性的讀-寫-修改操作，可以在不使用鎖的情況下安全地更新共享變量。原子變量的內(nèi)存語義與 volatile 變量類似，但是因?yàn)樗鼈円部梢员辉有缘匦薷?，所以可以把它們用作不使用鎖的并發(fā)算法的基礎(chǔ)。

非阻塞的計(jì)數(shù)器

清單 1 中的 Counter 是線程安全的，但是使用鎖的需求帶來的性能成本困擾了一些開發(fā)人員。但是鎖是必需的，因?yàn)殡m然增加看起來是單一操作，但實(shí)際是三個(gè)獨(dú)立操作的簡(jiǎn)化：檢索值，給值加 1，再寫回值。（在 getValue 方法上也需要同步，以保證調(diào)用 getValue 的線程看到的是最新的值。雖然許多開發(fā)人員勉強(qiáng)地使自己相信忽略鎖定需求是可以接受的，但忽略鎖定需求并不是好策略。）

在多個(gè)線程同時(shí)請(qǐng)求同一個(gè)鎖時(shí)，會(huì)有一個(gè)線程獲勝并得到鎖，而其他線程被阻塞。JVM 實(shí)現(xiàn)阻塞的方式通常是掛起阻塞的線程，過一會(huì)兒再重新調(diào)度它。由此造成的上下文切換相對(duì)于鎖保護(hù)的少數(shù)幾條指令來說，會(huì)造成相當(dāng)大的延遲。

清單 1. 使用同步的線程安全的計(jì)數(shù)器

            public final class Counter {
    private long value = 0;
    public synchronized long getValue() {
        return value;
    }
    public synchronized long increment() {
        return ++value;
    }
}

          

?

清單 2 中的 NonblockingCounter 顯示了一種最簡(jiǎn)單的非阻塞算法：使用 AtomicInteger 的 compareAndSet() （CAS）方法的計(jì)數(shù)器。 compareAndSet() 方法規(guī)定 “將這個(gè)變量更新為新值，但是如果從我上次看到這個(gè)變量之后其他線程修改了它的值，那么更新就失敗”（請(qǐng)參閱 “流行的原子” 獲得關(guān)于原子變量以及 “比較和設(shè)置” 的更多解釋。）

清單 2. 使用 CAS 的非阻塞算法

            public class NonblockingCounter {
    private AtomicInteger value;
    public int getValue() {
        return value.get();
    }
    public int increment() {
        int v;
        do {
            v = value.get();
        while (!value.compareAndSet(v, v + 1));
        return v + 1;
    }
}

          

?

原子變量類之所以被稱為 原子的 ，是因?yàn)樗鼈兲峁┝藢?duì)數(shù)字和對(duì)象引用的細(xì)粒度的原子更新，但是在作為非阻塞算法的基本構(gòu)造塊的意義上，它們也是原子的。非阻塞算法作為科研的主題，已經(jīng)有 20 多年了，但是直到 Java 5.0 出現(xiàn)，在 Java 語言中才成為可能。

現(xiàn)代的處理器提供了特殊的指令，可以自動(dòng)更新共享數(shù)據(jù)，而且能夠檢測(cè)到其他線程的干擾，而 compareAndSet() 就用這些代替了鎖定。（如果要做的只是遞增計(jì)數(shù)器，那么 AtomicInteger 提供了進(jìn)行遞增的方法，但是這些方法基于 compareAndSet() ，例如 NonblockingCounter.increment() ）。

非阻塞版本相對(duì)于基于鎖的版本有幾個(gè)性能優(yōu)勢(shì)。首先，它用硬件的原生形態(tài)代替 JVM 的鎖定代碼路徑，從而在更細(xì)的粒度層次上（獨(dú)立的內(nèi)存位置）進(jìn)行同步，失敗的線程也可以立即重試，而不會(huì)被掛起后重新調(diào)度。更細(xì)的粒度降低了爭(zhēng)用的機(jī)會(huì)，不用重新調(diào)度就能重試的能力也降低了爭(zhēng)用的成本。即使有少量失敗的 CAS 操作，這種方法仍然會(huì)比由于鎖爭(zhēng)用造成的重新調(diào)度快得多。

NonblockingCounter 這個(gè)示例可能簡(jiǎn)單了些，但是它演示了所有非阻塞算法的一個(gè)基本特征 —— 有些算法步驟的執(zhí)行是要冒險(xiǎn)的，因?yàn)橹廊绻?CAS 不成功可能不得不重做。非阻塞算法通常叫作 樂觀算法 ，因?yàn)樗鼈兝^續(xù)操作的假設(shè)是不會(huì)有干擾。如果發(fā)現(xiàn)干擾，就會(huì)回退并重試。在計(jì)數(shù)器的示例中，冒險(xiǎn)的步驟是遞增 —— 它檢索舊值并在舊值上加一，希望在計(jì)算更新期間值不會(huì)變化。如果它的希望落空，就會(huì)再次檢索值，并重做遞增計(jì)算。

?

回頁首

非阻塞堆棧

非阻塞算法稍微復(fù)雜一些的示例是清單 3 中的 ConcurrentStack 。 ConcurrentStack 中的 push() 和 pop() 操作在結(jié)構(gòu)上與 NonblockingCounter 上相似，只是做的工作有些冒險(xiǎn)，希望在 “提交” 工作的時(shí)候，底層假設(shè)沒有失效。 push() 方法觀察當(dāng)前最頂?shù)墓?jié)點(diǎn)，構(gòu)建一個(gè)新節(jié)點(diǎn)放在堆棧上，然后，如果最頂端的節(jié)點(diǎn)在初始觀察之后沒有變化，那么就安裝新節(jié)點(diǎn)。如果 CAS 失敗，意味著另一個(gè)線程已經(jīng)修改了堆棧，那么過程就會(huì)重新開始。

清單 3. 使用 Treiber 算法的非阻塞堆棧

            public class ConcurrentStack<E> {
    AtomicReference<Node<E>> head = new AtomicReference<Node<E>>();
    public void push(E item) {
        Node<E> newHead = new Node<E>(item);
        Node<E> oldHead;
        do {
            oldHead = head.get();
            newHead.next = oldHead;
        } while (!head.compareAndSet(oldHead, newHead));
    }
    public E pop() {
        Node<E> oldHead;
        Node<E> newHead;
        do {
            oldHead = head.get();
            if (oldHead == null) 
                return null;
            newHead = oldHead.next;
        } while (!head.compareAndSet(oldHead,newHead));
        return oldHead.item;
    }
    static class Node<E> {
        final E item;
        Node<E> next;
        public Node(E item) { this.item = item; }
    }
}

          

?

性能考慮

在輕度到中度的爭(zhēng)用情況下，非阻塞算法的性能會(huì)超越阻塞算法，因?yàn)?CAS 的多數(shù)時(shí)間都在第一次嘗試時(shí)就成功，而發(fā)生爭(zhēng)用時(shí)的開銷也不涉及線程掛起和上下文切換，只多了幾個(gè)循環(huán)迭代。沒有爭(zhēng)用的 CAS 要比沒有爭(zhēng)用的鎖便宜得多（這句話肯定是真的，因?yàn)闆]有爭(zhēng)用的鎖涉及 CAS 加上額外的處理），而爭(zhēng)用的 CAS 比爭(zhēng)用的鎖獲取涉及更短的延遲。

在高度爭(zhēng)用的情況下（即有多個(gè)線程不斷爭(zhēng)用一個(gè)內(nèi)存位置的時(shí)候），基于鎖的算法開始提供比非阻塞算法更好的吞吐率，因?yàn)楫?dāng)線程阻塞時(shí)，它就會(huì)停止?fàn)幱茫托牡氐群蜉喌阶约?，從而避免了進(jìn)一步爭(zhēng)用。但是，這么高的爭(zhēng)用程度并不常見，因?yàn)槎鄶?shù)時(shí)候，線程會(huì)把線程本地的計(jì)算與爭(zhēng)用共享數(shù)據(jù)的操作分開，從而給其他線程使用共享數(shù)據(jù)的機(jī)會(huì)。（這么高的爭(zhēng)用程度也表明需要重新檢查算法，朝著更少共享數(shù)據(jù)的方向努力。） “流行的原子” 中的圖在這方面就有點(diǎn)兒讓人困惑，因?yàn)楸粶y(cè)量的程序中發(fā)生的爭(zhēng)用極其密集，看起來即使對(duì)數(shù)量很少的線程，鎖定也是更好的解決方案。

?

回頁首

非阻塞的鏈表

目前為止的示例（計(jì)數(shù)器和堆棧）都是非常簡(jiǎn)單的非阻塞算法，一旦掌握了在循環(huán)中使用 CAS，就可以容易地模仿它們。對(duì)于更復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，非阻塞算法要比這些簡(jiǎn)單示例復(fù)雜得多，因?yàn)樾薷逆湵?、樹或哈希表可能涉及?duì)多個(gè)指針的更新。CAS 支持對(duì)單一指針的原子性條件更新，但是不支持兩個(gè)以上的指針。所以，要構(gòu)建一個(gè)非阻塞的鏈表、樹或哈希表，需要找到一種方式，可以用 CAS 更新多個(gè)指針，同時(shí)不會(huì)讓數(shù)據(jù)結(jié)構(gòu)處于不一致的狀態(tài)。

在鏈表的尾部插入元素，通常涉及對(duì)兩個(gè)指針的更新：“尾” 指針總是指向列表中的最后一個(gè)元素，“下一個(gè)” 指針從過去的最后一個(gè)元素指向新插入的元素。因?yàn)樾枰聝蓚€(gè)指針，所以需要兩個(gè) CAS。在獨(dú)立的 CAS 中更新兩個(gè)指針帶來了兩個(gè)需要考慮的潛在問題：如果第一個(gè) CAS 成功，而第二個(gè) CAS 失敗，會(huì)發(fā)生什么？如果其他線程在第一個(gè)和第二個(gè) CAS 之間企圖訪問鏈表，會(huì)發(fā)生什么？

對(duì)于非復(fù)雜數(shù)據(jù)結(jié)構(gòu)，構(gòu)建非阻塞算法的 “技巧” 是確保數(shù)據(jù)結(jié)構(gòu)總處于一致的狀態(tài)（甚至包括在線程開始修改數(shù)據(jù)結(jié)構(gòu)和它完成修改之間），還要確保其他線程不僅能夠判斷出第一個(gè)線程已經(jīng)完成了更新還是處在更新的中途，還能夠判斷出如果第一個(gè)線程走向 AWOL，完成更新還需要什么操作。如果線程發(fā)現(xiàn)了處在更新中途的數(shù)據(jù)結(jié)構(gòu)，它就可以 “幫助” 正在執(zhí)行更新的線程完成更新，然后再進(jìn)行自己的操作。當(dāng)?shù)谝粋€(gè)線程回來試圖完成自己的更新時(shí)，會(huì)發(fā)現(xiàn)不再需要了，返回即可，因?yàn)?CAS 會(huì)檢測(cè)到幫助線程的干預(yù)（在這種情況下，是建設(shè)性的干預(yù)）。

這種 “幫助鄰居” 的要求，對(duì)于讓數(shù)據(jù)結(jié)構(gòu)免受單個(gè)線程失敗的影響，是必需的。如果線程發(fā)現(xiàn)數(shù)據(jù)結(jié)構(gòu)正處在被其他線程更新的中途，然后就等候其他線程完成更新，那么如果其他線程在操作中途失敗，這個(gè)線程就可能永遠(yuǎn)等候下去。即使不出現(xiàn)故障，這種方式也會(huì)提供糟糕的性能，因?yàn)樾碌竭_(dá)的線程必須放棄處理器，導(dǎo)致上下文切換，或者等到自己的時(shí)間片過期（而這更糟）。

清單 4 的 LinkedQueue 顯示了 Michael-Scott 非阻塞隊(duì)列算法的插入操作，它是由 ConcurrentLinkedQueue 實(shí)現(xiàn)的：

清單 4. Michael-Scott 非阻塞隊(duì)列算法中的插入

            public class LinkedQueue <E> {
    private static class Node <E> {
        final E item;
        final AtomicReference<Node<E>> next;
        Node(E item, Node<E> next) {
            this.item = item;
            this.next = new AtomicReference<Node<E>>(next);
        }
    }
    private AtomicReference<Node<E>> head
        = new AtomicReference<Node<E>>(new Node<E>(null, null));
    private AtomicReference<Node<E>> tail = head;
    public boolean put(E item) {
        Node<E> newNode = new Node<E>(item, null);
        while (true) {
            Node<E> curTail = tail.get();
            Node<E> residue = curTail.next.get();
            if (curTail == tail.get()) {
                if (residue == null) /* A */ {
                    if (curTail.next.compareAndSet(null, newNode)) /* C */ {
                        tail.compareAndSet(curTail, newNode) /* D */ ;
                        return true;
                    }
                } else {
                    tail.compareAndSet(curTail, residue) /* B */;
                }
            }
        }
    }
}

          

?

像許多隊(duì)列算法一樣，空隊(duì)列只包含一個(gè)假節(jié)點(diǎn)。頭指針總是指向假節(jié)點(diǎn)；尾指針總指向最后一個(gè)節(jié)點(diǎn)或倒數(shù)第二個(gè)節(jié)點(diǎn)。圖 1 演示了正常情況下有兩個(gè)元素的隊(duì)列：

圖 1. 有兩個(gè)元素，處在靜止?fàn)顟B(tài)的隊(duì)列

如 清單 4 所示，插入一個(gè)元素涉及兩個(gè)指針更新，這兩個(gè)更新都是通過 CAS 進(jìn)行的：從隊(duì)列當(dāng)前的最后節(jié)點(diǎn)（C）鏈接到新節(jié)點(diǎn)，并把尾指針移動(dòng)到新的最后一個(gè)節(jié)點(diǎn)（D）。如果第一步失敗，那么隊(duì)列的狀態(tài)不變，插入線程會(huì)繼續(xù)重試，直到成功。一旦操作成功，插入被當(dāng)成生效，其他線程就可以看到修改。還需要把尾指針移動(dòng)到新節(jié)點(diǎn)的位置上，但是這項(xiàng)工作可以看成是 “清理工作”，因?yàn)槿魏翁幵谶@種情況下的線程都可以判斷出是否需要這種清理，也知道如何進(jìn)行清理。

隊(duì)列總是處于兩種狀態(tài)之一：正常狀態(tài)（或稱靜止?fàn)顟B(tài)， 圖 1 和 圖 3 ）或中間狀態(tài)（圖 2）。在插入操作之前和第二個(gè) CAS（D）成功之后，隊(duì)列處在靜止?fàn)顟B(tài)；在第一個(gè) CAS（C）成功之后，隊(duì)列處在中間狀態(tài)。在靜止?fàn)顟B(tài)時(shí)，尾指針指向的鏈接節(jié)點(diǎn)的 next 字段總為 null，而在中間狀態(tài)時(shí)，這個(gè)字段為非 null。任何線程通過比較 tail.next 是否為 null，就可以判斷出隊(duì)列的狀態(tài)，這是讓線程可以幫助其他線程 “完成” 操作的關(guān)鍵。

圖 2. 處在插入中間狀態(tài)的隊(duì)列，在新元素插入之后，尾指針更新之前

插入操作在插入新元素（A）之前，先檢查隊(duì)列是否處在中間狀態(tài)，如 清單 4 所示。如果是在中間狀態(tài)，那么肯定有其他線程已經(jīng)處在元素插入的中途，在步驟（C）和（D）之間。不必等候其他線程完成，當(dāng)前線程就可以 “幫助” 它完成操作，把尾指針向前移動(dòng)（B）。如果有必要，它還會(huì)繼續(xù)檢查尾指針并向前移動(dòng)指針，直到隊(duì)列處于靜止?fàn)顟B(tài)，這時(shí)它就可以開始自己的插入了。

第一個(gè) CAS（C）可能因?yàn)閮蓚€(gè)線程競(jìng)爭(zhēng)訪問隊(duì)列當(dāng)前的最后一個(gè)元素而失敗；在這種情況下，沒有發(fā)生修改，失去 CAS 的線程會(huì)重新裝入尾指針并再次嘗試。如果第二個(gè) CAS（D）失敗，插入線程不需要重試 —— 因?yàn)槠渌€程已經(jīng)在步驟（B）中替它完成了這個(gè)操作！

圖 3. 在尾指針更新后，隊(duì)列重新處在靜止?fàn)顟B(tài)

幕后的非阻塞算法

如果深入 JVM 和操作系統(tǒng)，會(huì)發(fā)現(xiàn)非阻塞算法無處不在。垃圾收集器使用非阻塞算法加快并發(fā)和平行的垃圾搜集；調(diào)度器使用非阻塞算法有效地調(diào)度線程和進(jìn)程，實(shí)現(xiàn)內(nèi)在鎖。在 Mustang（Java 6.0）中，基于鎖的 SynchronousQueue 算法被新的非阻塞版本代替。很少有開發(fā)人員會(huì)直接使用 SynchronousQueue ，但是通過 Executors.newCachedThreadPool() 工廠構(gòu)建的線程池用它作為工作隊(duì)列。比較緩存線程池性能的對(duì)比測(cè)試顯示，新的非阻塞同步隊(duì)列實(shí)現(xiàn)提供了幾乎是當(dāng)前實(shí)現(xiàn) 3 倍的速度。在 Mustang 的后續(xù)版本（代碼名稱為 Dolphin）中，已經(jīng)規(guī)劃了進(jìn)一步的改進(jìn)。

?

回頁首

結(jié)束語

非阻塞算法要比基于鎖的算法復(fù)雜得多。開發(fā)非阻塞算法是相當(dāng)專業(yè)的訓(xùn)練，而且要證明算法的正確也極為困難。但是在 Java 版本之間并發(fā)性能上的眾多改進(jìn)來自對(duì)非阻塞算法的采用，而且隨著并發(fā)性能變得越來越重要，可以預(yù)見在 Java 平臺(tái)的未來發(fā)行版中，會(huì)使用更多的非阻塞算法。

參考資料

學(xué)習(xí)

• 您可以參閱本文在 developerWorks 全球站點(diǎn)上的 英文原文 。
  
  
• “ 流行的原子 ” （developerWorks，Brian Goetz，2004 年 11 月）：描述了 Java 5.0 中加入的原子變量類，以及比較-交換操作。
  
  
• “ Scalable Synchronous Queues ”（ACM SIGPLAN 關(guān)于并行編程的原則與實(shí)踐的討論會(huì)，William N. Scherer III、Doug Lea 和 Michael L. Scott，2006 年 3 月）：描述了 Java 6 中新增的 SynchronousQueue 實(shí)現(xiàn)的構(gòu)建和性能優(yōu)勢(shì)。
  
  
• “ Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queues ”（Maged M. Michael 和 Michael L. Scott，關(guān)于分布式計(jì)算原則的討論會(huì)，1996）：詳細(xì)介紹了本文的 清單 4 中演示的非阻塞鏈接隊(duì)列的構(gòu)建。
  
  
• Java Concurrency in Practice （Addison-Wesley Professional，Brian Goetz、Tim Peierls、Joshua Bloch、Joseph Bowbeer、David Holmes 和 Doug Lea，2006 年 6 月）：一份用 Java 語言開發(fā)并發(fā)程序的 how-to 手冊(cè)，包括構(gòu)建和編輯線程安全的類和程序，避免生存風(fēng)險(xiǎn)，管理性能和測(cè)試并發(fā)應(yīng)用程序。
  
  
• Java 技術(shù)專區(qū) ：數(shù)百篇關(guān)于 Java 編程各方面的文章。
  
  

獲得產(chǎn)品和技術(shù)

• JDK 5.0 Update 6 ：得到 JDK 5.0 的最新更新。
  
  

討論

• 參與論壇討論 。
  
  
• developerWorks blog ：加入 developerWorks 社區(qū)。

關(guān)于作者

?		Brian Goetz 作為專業(yè)的軟件開發(fā)人員已經(jīng)超過 18 年了。他是 Quiotix 的首席顧問，這是家軟件開發(fā)和咨詢公司，位于加州 Los Altos，他還效力于多個(gè) JCP 專家組。Brian 的力作 Java Concurrency In Practice 將于 2006 年初由 Addison-Wesley 出版。請(qǐng)參閱 Brian 在流行的行業(yè)出版物上 已經(jīng)發(fā)表和即將發(fā)表的文章 。

Java 理論與實(shí)踐: 非阻塞算法簡(jiǎn)介