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

原文轉自：http://www.anti-gravitydesign.com