Java 理論與實踐: 非阻塞算法簡介 – JAVA編程語言程序開發技術文章

Java? 5.0 第一次讓使用 Java 語言開發非阻塞算法成為可能,java.util.concurrent 包充分地利用瞭這個功能。非阻塞算法屬於並發算法,它們可以安全地派生它們的線程,不通過鎖定派生,而是通過低級的原子性的硬件原生形式 ?? 例如比較和交換。非阻塞算法的設計與實現極為困難,但是它們能夠提供更好的吞吐率,對生存問題(例如死鎖和優先級反轉)也能提供更好的防禦。在這期的 Java 理論與實踐 中,並發性大師 Brian Goetz 演示瞭幾種比較簡單的非阻塞算法的工作方式。

在不隻一個線程訪問一個互斥的變量時,所有線程都必須使用同步,否則就可能會發生一些非常糟糕的事情。Java 語言中主要的同步手段就是 synchronized 關鍵字(也稱為內在鎖),它強制實行互斥,確保執行 synchronized 塊的線程的動作,能夠被後來執行受相同鎖保護的 synchronized 塊的其他線程看到。在使用得當的時候,內在鎖可以讓程序做到線程安全,但是在使用鎖定保護短的代碼路徑,而且線程頻繁地爭用鎖的時候,鎖定可能成為相當繁重的操作。

在 “流行的原子” 一文中,我們研究瞭原子變量,原子變量提供瞭原子性的讀-寫-修改操作,可以在不使用鎖的情況下安全地更新共享變量。原子變量的內存語義與 volatile 變量類似,但是因為它們也可以被原子性地修改,所以可以把它們用作不使用鎖的並發算法的基礎。

非阻塞的計數器

清單 1 中的 Counter 是線程安全的,但是使用鎖的需求帶來的性能成本困擾瞭一些開發人員。但是鎖是必需的,因為雖然增加看起來是單一操作,但實際是三個獨立操作的簡化:檢索值,給值加 1,再寫回值。(在 getValue 方法上也需要同步,以保證調用 getValue 的線程看到的是最新的值。雖然許多開發人員勉強地使自己相信忽略鎖定需求是可以接受的,但忽略鎖定需求並不是好策略。)

在多個線程同時請求同一個鎖時,會有一個線程獲勝並得到鎖,而其他線程被阻塞。JVM 實現阻塞的方式通常是掛起阻塞的線程,過一會兒再重新調度它。由此造成的上下文切換相對於鎖保護的少數幾條指令來說,會造成相當大的延遲。

清單 1. 使用同步的線程安全的計數器

public final class Counter {
    private long value = 0;

    public synchronized long getValue() {
        return value;
    }

    public synchronized long increment() {
        return ++value;
    }
}

清單 2 中的 NonblockingCounter 顯示瞭一種最簡單的非阻塞算法:使用 AtomicInteger 的 compareAndSet() (CAS)方法的計數器。compareAndSet() 方法規定 “將這個變量更新為新值,但是如果從我上次看到這個變量之後其他線程修改瞭它的值,那麼更新就失敗”(請參閱 “流行的原子” 獲得關於原子變量以及 “比較和設置” 的更多解釋。)

清單 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;
    }
}

原子變量類之所以被稱為原子的,是因為它們提供瞭對數字和對象引用的細粒度的原子更新,但是在作為非阻塞算法的基本構造塊的意義上,它們也是原子的。非阻塞算法作為科研的主題,已經有 20 多年瞭,但是直到 Java 5.0 出現,在 Java 語言中才成為可能。

現代的處理器提供瞭特殊的指令,可以自動更新共享數據,而且能夠檢測到其他線程的幹擾,而 compareAndSet() 就用這些代替瞭鎖定。(如果要做的隻是遞增計數器,那麼 AtomicInteger 提供瞭進行遞增的方法,但是這些方法基於 compareAndSet(),例如 NonblockingCounter.increment())。

非阻塞版本相對於基於鎖的版本有幾個性能優勢。首先,它用硬件的原生形態代替 JVM 的鎖定代碼路徑,從而在更細的粒度層次上(獨立的內存位置)進行同步,失敗的線程也可以立即重試,而不會被掛起後重新調度。更細的粒度降低瞭爭用的機會,不用重新調度就能重試的能力也降低瞭爭用的成本。即使有少量失敗的 CAS 操作,這種方法仍然會比由於鎖爭用造成的重新調度快得多。

NonblockingCounter 這個示例可能簡單瞭些,但是它演示瞭所有非阻塞算法的一個基本特征 ?? 有些算法步驟的執行是要冒險的,因為知道如果 CAS 不成功可能不得不重做。非阻塞算法通常叫作樂觀算法,因為它們繼續操作的假設是不會有幹擾。如果發現幹擾,就會回退並重試。在計數器的示例中,冒險的步驟是遞增 ?? 它檢索舊值並在舊值上加一,希望在計算更新期間值不會變化。如果它的希望落空,就會再次檢索值,並重做遞增計算。

非阻塞堆棧

非阻塞算法稍微復雜一些的示例是清單 3 中的 ConcurrentStack。ConcurrentStack 中的 push() 和 pop() 操作在結構上與 NonblockingCounter 上相似,隻是做的工作有些冒險,希望在 “提交” 工作的時候,底層假設沒有失效。push() 方法觀察當前最頂的節點,構建一個新節點放在堆棧上,然後,如果最頂端的節點在初始觀察之後沒有變化,那麼就安裝新節點。如果 CAS 失敗,意味著另一個線程已經修改瞭堆棧,那麼過程就會重新開始。

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

public class ConcurrentStack {
    AtomicReference<node> head = new AtomicReference<node>();

    public void push(E item) {
        Node newHead = new Node(item);
        Node oldHead;
        do {
            oldHead = head.get();
            newHead.next = oldHead;
        } while (!head.compareAndSet(oldHead, newHead));
    }

    public E pop() {
        Node oldHead;
        Node newHead;
        do {
            oldHead = head.get();
            if (oldHead == null) 
                return null;
            newHead = oldHead.next;
        } while (!head.compareAndSet(oldHead,newHead));
        return oldHead.item;
    }

    static class Node {
        final E item;
        Node next;

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

性能考慮

在輕度到中度的爭用情況下,非阻塞算法的性能會超越阻塞算法,因為 CAS 的多數時間都在第一次嘗試時就成功,而

You May Also Like