AbstractQueuedSynchronizer

??提供一個(gè)框架，用于實(shí)現(xiàn)依賴先進(jìn)先出(FIFO)等待隊(duì)列的阻塞鎖和相關(guān)同步器(信號(hào)量、事件等)。該類被設(shè)計(jì)為大多數(shù)依賴于單個(gè)原子int值來(lái)表示狀態(tài)的同步器的有用基礎(chǔ)。子類必須定義改變?cè)摖顟B(tài)的受保護(hù)方法，以及這些方法定義了該狀態(tài)在獲取或釋放該對(duì)象方面的含義?？紤]到這些，該類中的其他方法執(zhí)行所有隊(duì)列和阻塞機(jī)制。子類可以維護(hù)其他狀態(tài)字段，但是只有使用方法getState、setState和compareAndSetState對(duì)原子更新的int值進(jìn)行同步跟蹤。

??子類應(yīng)該被定義為非公共的內(nèi)部幫助類，用于實(shí)現(xiàn)其封閉類的同步屬性。類AbstractQueuedSynchronizer不實(shí)現(xiàn)任何同步接口。相反，它定義了諸如acquireInterruptibly這樣的方法，具體鎖和相關(guān)同步器可以根據(jù)需要調(diào)用這些方法來(lái)實(shí)現(xiàn)它們的公共方法。

??這個(gè)類支持默認(rèn)的模式和模式。在獨(dú)占模式下獲取時(shí)，其他線程試圖獲取的操作無(wú)法成功。多個(gè)線程獲取的共享模式可能(但不需要)成功。這個(gè)類不“明白”除了機(jī)械意義上的差異之外，這些差異還包括:當(dāng)共享模式獲取成功時(shí)，下一個(gè)等待的線程(如果存在的話)也必須確定它是否能夠獲取。在不同模式下等待的線程共享同一個(gè)FIFO隊(duì)列。通常，實(shí)現(xiàn)子類只支持其中一種模式，但這兩種模式都可以發(fā)揮作用，例如在ReadWriteLock中。只支持獨(dú)占模式或僅支持共享模式的子類不需要定義支持未使用模式的方法。

??這個(gè)類定義了一個(gè)嵌套的ConditionObject類,可以用作Condition由子類實(shí)現(xiàn)支持獨(dú)占模式的方法isHeldExclusively報(bào)告同步是否只對(duì)當(dāng)前線程持有,release方法調(diào)用與getState獲取當(dāng)前的值和acquire方法完全釋放這個(gè)對(duì)象,鑒于這個(gè)保存的狀態(tài)值,最終將該對(duì)象恢復(fù)到以前獲取的狀態(tài)。AbstractQueuedSynchronizer沒(méi)有方法會(huì)創(chuàng)建這樣的條件，所以如果不能滿足這個(gè)約束，就不要使用它。ConditionObject的行為當(dāng)然依賴于它的同步器實(shí)現(xiàn)的語(yǔ)義。

??該類為內(nèi)部隊(duì)列提供了檢查、檢測(cè)和監(jiān)視方法，跟Condition對(duì)象的方法很相似。可以使用AbstractQueuedSynchronizer將這些同步機(jī)制按照需要導(dǎo)出到類中。

??該類的序列化只存儲(chǔ)底層原子整數(shù)維護(hù)狀態(tài)，因此反序列化的對(duì)象具有空線程隊(duì)列。需要序列化的典型子類將定義一個(gè)readObject方法，該方法在反序列化時(shí)將其恢復(fù)到已知的初始狀態(tài)。

使用

??如果要使用這個(gè)類作為同步器的基礎(chǔ)，可以使用getState、setState和/或compareAndSetState檢查和/或修改同步狀態(tài)，根據(jù)需要重新定義以下方法:
?--tryAcquire
?--tryRelease
?--tryAcquireShared
?--tryReleaseShared
?--isHeldExclusively

??默認(rèn)情況下,每個(gè)方法都會(huì)UnsupportedOperationException。這些方法的實(shí)現(xiàn)必須是內(nèi)部線程安全的，并且通常應(yīng)該是短的，而不是阻塞的。定義這些方法是使用這個(gè)類的only支持的方法。所有其他方法都聲明為final，因?yàn)樗鼈儾荒塥?dú)立更改。

??您還可能發(fā)現(xiàn)從AbstractOwnableSynchronizer繼承的方法對(duì)于跟蹤擁有獨(dú)占同步器的線程非常有用。我們鼓勵(lì)您使用它們——這使得監(jiān)視和診斷工具能夠幫助用戶確定哪些線程持有鎖。

??即使這個(gè)類基于內(nèi)部FIFO隊(duì)列，它也不會(huì)自動(dòng)執(zhí)行FIFO獲取策略。獨(dú)占同步的核心形式為:

Acquire:
    while (!tryAcquire(arg)) {
        //enqueue thread if it is not already queued;
        //possibly block current thread;
    }
Release:
    if (tryRelease(arg))
        //unblock the first queued thread;

(共享模式類似，但可能涉及級(jí)聯(lián)信號(hào)。)

??因?yàn)楹炄氆@取是在排隊(duì)之前調(diào)用的，所以一個(gè)新的獲取線程可能會(huì)“插入”在其他被阻塞和排隊(duì)的線程之前。但是，如果需要，您可以通過(guò)內(nèi)部調(diào)用一個(gè)或多個(gè)檢查方法來(lái)定義tryAcquire和/或tryAcquireShared來(lái)禁止插入，從而提供一個(gè)"公平" FIFO獲取順序。特別是，如果hasQueuedPredecessors(一個(gè)專門為公平同步器設(shè)計(jì)的方法)返回true，那么大多數(shù)公平同步器可以定義tryAcquire來(lái)返回false。其他變化是可能的。

??對(duì)于默認(rèn)的barging(也稱為"貪心")策略，吞吐量和可伸縮性通常是最高的。雖然不能保證這是公平的或無(wú)中斷的，但允許較早排隊(duì)的線程在較晚排隊(duì)的線程之前重新競(jìng)爭(zhēng)，而且每次重新競(jìng)爭(zhēng)都有公平的機(jī)會(huì)面對(duì)傳入成功的線程。而且，在獲得的同時(shí)不<轉(zhuǎn)動(dòng)>。通常情況下，在阻塞之前，它們可以執(zhí)行tryAcquire的多次調(diào)用，其間穿插著其他計(jì)算。當(dāng)獨(dú)占同步只被短暫地持有時(shí)，這就提供了自旋的大部分好處，而當(dāng)它不被持有時(shí)，就沒(méi)有了大部分的不利因素。如果需要，您可以通過(guò)前面的調(diào)用來(lái)增強(qiáng)這種能力，通過(guò)“fast-path”檢查來(lái)獲取方法，可能會(huì)預(yù)先檢查hasContended和/或hasQueuedThreads，只在同步器可能不存在競(jìng)爭(zhēng)的情況下才能這樣做。

??這個(gè)類為同步提供了一個(gè)高效且可伸縮的基礎(chǔ)，部分原因是它將同步器的使用范圍專門化為可以依賴于int狀態(tài)、獲取和釋放參數(shù)以及內(nèi)部FIFO等待隊(duì)列的同步器。當(dāng)這還不夠時(shí)，您可以使用java.util.concurrent.atomic類、自定義的java.util.Queue類和LockSupport阻塞支持，從較低的級(jí)別構(gòu)建同步器。

使用舉例

??這是一個(gè)不可重入互斥鎖類，它使用0表示未鎖狀態(tài)，1表示已鎖狀態(tài)。雖然不可重入鎖并不嚴(yán)格要求記錄當(dāng)前的持有線程，但是這個(gè)類還是這樣做了，以便更容易地監(jiān)視使用情況。它還支持conditions，并公開(kāi)了一種檢測(cè)方法:

class Mutex implements Lock, java.io.Serializable {
    // 我們的內(nèi)部幫助類
    private static class Sync extends AbstractQueuedSynchronizer {
        // 報(bào)告是否處于鎖定狀態(tài)
        protected boolean isHeldExclusively() {
            return getState() == 1;
        }

    // 如果狀態(tài)為0，則獲取鎖
    public boolean tryAcquire(int acquires) {
        assert acquires == 1; // Otherwise unused
        if (compareAndSetState(0, 1)) {
            setExclusiveOwnerThread(Thread.currentThread());
            return true;
        }
        return false;
    }

    // 通過(guò)把狀態(tài)設(shè)為0來(lái)釋放鎖
    protected boolean tryRelease(int releases) {
        assert releases == 1; // Otherwise unused
        if (getState() == 0) throw new IllegalMonitorStateException();
            setExclusiveOwnerThread(null);
            setState(0);
            return true;
        }
 
    // 提供一個(gè) Condition
    Condition newCondition() { return new ConditionObject(); }
 
    // 反序列化
    private void readObject(ObjectInputStream s) throws IOException, ClassNotFoundException {
        s.defaultReadObject();
        setState(0); // reset to unlocked state
    }

 
    // sync對(duì)象完成所有的工作。我們只需要用它轉(zhuǎn)發(fā)功能就行。
    private final Sync sync = new Sync();
 
    public void lock()                { sync.acquire(1); }
    public boolean tryLock()          { return sync.tryAcquire(1); }
    public void unlock()              { sync.release(1); }
    public Condition newCondition()   { return sync.newCondition(); }
    public boolean isLocked()         { return sync.isHeldExclusively(); }
    public boolean hasQueuedThreads() { return sync.hasQueuedThreads(); }
    public void lockInterruptibly() throws InterruptedException {
        sync.acquireInterruptibly(1);
    }
    public boolean tryLock(long timeout, TimeUnit unit)
        throws InterruptedException {
        return sync.tryAcquireNanos(1, unit.toNanos(timeout));
    }
}

??這是一個(gè)類似于java.util.concurrent.CountDownLatch的鎖存器類。區(qū)別是它只需要一個(gè)signal來(lái)觸發(fā)。因?yàn)殒i存器是非獨(dú)占的，它使用shared獲取和釋放方法。

class BooleanLatch {
    private static class Sync extends AbstractQueuedSynchronizer {
        boolean isSignalled() { return getState() != 0; }
        protected int tryAcquireShared(int ignore) {
            return isSignalled() ? 1 : -1;
        }
        protected boolean tryReleaseShared(int ignore) {
            setState(1);
            return true;
        }
    }
    private final Sync sync = new Sync();
    public boolean isSignalled() { return sync.isSignalled(); }
    public void signal()         { sync.releaseShared(1); }
    public void await() throws InterruptedException {
        sync.acquireSharedInterruptibly(1);
    }
}

AbstractQueuedSynchronizer.Node

??等待隊(duì)列節(jié)點(diǎn)類。

??等待隊(duì)列是CLH(Craig、Landin和Hagersten)鎖隊(duì)列的變體。CLH鎖通常用于自旋鎖。相反，我們使用它們來(lái)阻塞同步器，但使用相同的基本策略，即在其節(jié)點(diǎn)的前身中保存關(guān)于線程的一些控制信息。每個(gè)節(jié)點(diǎn)中的status字段跟蹤線程是否應(yīng)該阻塞。一個(gè)節(jié)點(diǎn)在其前驅(qū)節(jié)點(diǎn)釋放時(shí)發(fā)出信號(hào)。否則，隊(duì)列的每個(gè)節(jié)點(diǎn)都充當(dāng)持有單個(gè)等待線程的特定通知樣式的監(jiān)視器。狀態(tài)字段不控制線程是否被授予鎖等。如果線程是隊(duì)列中的第一個(gè)線程，它可以嘗試獲取。但第一個(gè)也并不能保證成功，它只給你競(jìng)爭(zhēng)的權(quán)利。因此，當(dāng)前發(fā)布的競(jìng)爭(zhēng)者線程可能需要重新等待。

??要入隊(duì)一個(gè)CLH鎖，您需要將其原子拼接為新尾部。 要出列，您只需設(shè)置head字段。

      +------+  prev +-----+       +-----+
 head |      | <---- |     | <---- |     |  tail
      +------+       +-----+       +-----+

??插入CLH隊(duì)列只需要對(duì)“尾部”進(jìn)行單個(gè)原子操作，因此存在從未排隊(duì)到排隊(duì)的簡(jiǎn)單原子點(diǎn)劃分。 同樣，出列只涉及更新“頭部”。 但是，節(jié)點(diǎn)需要更多的工作來(lái)確定他們的后驅(qū)是誰(shuí)，部分是為了處理由于超時(shí)和中斷而可能的取消。

??處理取消主要需要“prev”鏈接（未在原始CLH鎖中使用）。 如果節(jié)點(diǎn)被取消，則其后驅(qū)（通常）重新鏈接到未取消的前驅(qū)。 有關(guān)自旋鎖的類似機(jī)制的解釋，請(qǐng)參閱Scott和Scherer的論文
http://www.cs.rochester.edu/u/scott/synchronization/

??我們還使用next鏈接來(lái)實(shí)現(xiàn)阻塞機(jī)制。 每個(gè)節(jié)點(diǎn)保存了自己所在線程ID，因此前驅(qū)通過(guò)遍歷下一個(gè)鏈接來(lái)通知下一個(gè)節(jié)點(diǎn)以確定它是哪個(gè)線程。 后驅(qū)的確定必須避免使用新排隊(duì)節(jié)點(diǎn)的競(jìng)爭(zhēng)來(lái)設(shè)置其前驅(qū)的next字段。 必要時(shí)，當(dāng)節(jié)點(diǎn)的后驅(qū)看起來(lái)為空時(shí)，通過(guò)從原子更新的tail向后檢查來(lái)解決這個(gè)問(wèn)題。 （或者，換句話說(shuō)，下一個(gè)鏈接是一個(gè)優(yōu)化，因此我們通常不需要向后掃描。）

??消除為基本算法引入了一些保守性。 由于我們必須輪詢消除其他節(jié)點(diǎn)，我們可能會(huì)忽略已消除的節(jié)點(diǎn)是在我們前面還是在我們后面。 這一點(diǎn)通過(guò)消除時(shí)始終取消停車的繼承人來(lái)處理，允許他們穩(wěn)定在新的前驅(qū)，除非我們能夠確定一位將承擔(dān)此責(zé)任的未經(jīng)解除的前驅(qū)。

??CLH隊(duì)列需要一個(gè)虛擬標(biāo)頭節(jié)點(diǎn)才能開(kāi)始。 但是我們不會(huì)在構(gòu)造函數(shù)里創(chuàng)建它們，因?yàn)槿绻麤](méi)有調(diào)用就會(huì)浪費(fèi)資源。 相反，節(jié)點(diǎn)在第一次調(diào)用時(shí)被構(gòu)造，并且設(shè)置頭尾指針。

??Conditions等待的線程使用相同的節(jié)點(diǎn)，但使用不同鏈接。Conditions只需要鏈接簡(jiǎn)單（非并發(fā)）鏈接隊(duì)列中的節(jié)點(diǎn)，因?yàn)樗鼈儍H在完全持有時(shí)才被訪問(wèn)。 等待時(shí)，將節(jié)點(diǎn)插入條件隊(duì)列。 根據(jù)信號(hào)，節(jié)點(diǎn)被轉(zhuǎn)移到主隊(duì)列。 狀態(tài)字段的特殊值用于標(biāo)記節(jié)點(diǎn)所在的隊(duì)列。

??感謝Dave Dice，Mark Moir，Victor Luchangco，Bill Scherer和Michael Scott以及JSR-166專家組成員對(duì)本課程設(shè)計(jì)的有益想法，討論和批評(píng)。