AbstractQueuedSynchronizer既然是同步器實(shí)現(xiàn)框架蕊温，關(guān)鍵便在于處理好多線程運(yùn)行時(shí)的問(wèn)題搬设。通過(guò)Java AbstractQueuedSynchronizer源碼閱讀1-基于隊(duì)列的同步器框架，可以了解到addWaiter()的功能是將Node入隊(duì)排拷，那么addWaiter()是如何保證多線程運(yùn)行下入隊(duì)操作的正確性的呢？

addWaiter()使用了原子性方法compareAndSetTail()。為方便敘述倔幼，將addWater()的代碼粘貼如下：

private Node addWaiter(Node mode) {
        Node node = new Node(Thread.currentThread(), mode);//新建與一個(gè)當(dāng)前線程關(guān)聯(lián)的node
        // Try the fast path of enq; backup to full enq on failure
        Node pred = tail;
        if (pred != null) {//如果tail不為空
            node.prev = pred;//將新建的node加入到隊(duì)尾
            if (compareAndSetTail(pred, node)) {//調(diào)用CAS（CompareAndSet）重新設(shè)置tail
                pred.next = node;
                return node;
            }
        }
        //如果入隊(duì)失敗了，則調(diào)用enq()
        enq(node);
        return node爽待；
    }

compareAndSetTail(pred, node)會(huì)比較pred和tail是否指向同一個(gè)節(jié)點(diǎn)损同，如果是，才將tail更新為node鸟款。為何不是直接賦值膏燃，而要多做一步比較操作呢？那是因?yàn)殡m然當(dāng)前線程在聲明pred時(shí)何什，為pred賦值了tail组哩，但tail可能會(huì)被其他線程改變，而當(dāng)前線程的本地變量pred是不會(huì)感知到這個(gè)改變的处渣。

這里伶贰，通過(guò)模擬多線程執(zhí)行來(lái)加深這個(gè)理解。

假設(shè)隊(duì)列的初始狀態(tài)如下罐栈，只有一個(gè)Node（稱為Node0）黍衙，隊(duì)列的head和tail都指向Node0。

隊(duì)列的初始狀態(tài)

現(xiàn)在有線程A和線程B同時(shí)調(diào)用addWaiter()悠瞬，要向該隊(duì)列插入新的Node们豌。假設(shè)線程A和線程B的執(zhí)行流程如下圖所示（省略了部分代碼，并對(duì)代碼采取了簡(jiǎn)寫(xiě)）：

線程A和線程B的執(zhí)行流程

第1步：線程A新建了Node（稱為NodeA）浅妆，并開(kāi)始入隊(duì)望迎。但是，線程A僅來(lái)的及將NodeA的prev指針賦值為tail凌外，便被調(diào)度出處理器辩尊。此時(shí)隊(duì)列的狀態(tài)如下圖所示，NodeA的prev指向了Node0康辑。圖中還另外標(biāo)注了線程A的局部變量pred摄欲，也是指向Node0的。

第1步

第2步：緊接著疮薇，線程B開(kāi)始占用處理器胸墙，執(zhí)行第2步。線程2也新建了一個(gè)Node（稱為NodeB）按咒，并且線程B成功的執(zhí)行完addWaiter()迟隅，將NodeB入隊(duì)。此時(shí)隊(duì)列的狀態(tài)如下圖所示，NodeB的prev也指向了Node0智袭。此處關(guān)鍵要注意的是奔缠，tail此時(shí)已經(jīng)指向了NodeB，但是線程A的pred依然指向Node0吼野。

第2步

第3步：線程B在入隊(duì)完成后校哎，線程A又開(kāi)始占用處理器執(zhí)行。線程A調(diào)用compareAndSetTail(pred, tail)瞳步，發(fā)現(xiàn)pred和tail并不是指向同一個(gè)Node的闷哆，該方法會(huì)返回false，線程A嘗試快速入隊(duì)失敗谚攒。之后阳准，線程A會(huì)調(diào)用enq()，重新獲取tail馏臭，并不停嘗試入隊(duì)直到成功。這里不再展開(kāi)enq()方法讼稚。最終隊(duì)列的狀態(tài)會(huì)如下所示括儒，線程B因?yàn)橄扔诰€程A成功調(diào)用了compareAndSetTail()，而位于A的前面锐想。

隊(duì)列最終狀態(tài)

如果使用的不是CAS方法帮寻，而是直接采用賦值的方式（即將compareAndSetTail(pred, node)換成tail=node），則在第3步時(shí)赠摇，會(huì)得到下面這個(gè)錯(cuò)誤的結(jié)果固逗。

錯(cuò)誤的入隊(duì)

所以說(shuō)，入隊(duì)的同步關(guān)鍵在于原子性的compareAndSetTail()方法藕帜。它保證了每個(gè)線程能夠完整的執(zhí)行下面兩個(gè)操作：

1. 設(shè)置prev烫罩，將自己鏈接到隊(duì)尾；
2. 將tail更新為自己洽故。

這使得隊(duì)列中的tail和prev指針總是可靠的贝攒，用戶在任何時(shí)候都可以使用tail和prev去訪問(wèn)隊(duì)列。

提出一些問(wèn)題

為何不將如下入隊(duì)的兩步關(guān)鍵性操作封裝為原子性操作

1. 設(shè)置prev时甚，將自己鏈接到隊(duì)尾隘弊；
2. 將tail更新為自己。

如果將這兩步封裝為原子性操作荒适，那么正確的入隊(duì)就可以一次性完成梨熙。而原本的實(shí)現(xiàn)中，CAS失敗后刀诬，還需要再重試咽扇。但是，AbstractQueuedSynchronizer本身是要實(shí)現(xiàn)原子性的操作，而其本身又依賴原子性的操作肌割，感覺(jué)有點(diǎn)像是先有雞還是先有蛋的問(wèn)題了卧蜓。
其實(shí)，CAS的原子性是依賴機(jī)器指令實(shí)現(xiàn)的把敞，但是機(jī)器指令無(wú)法支持以上兩步執(zhí)行的原子性弥奸。AbstractQueuedSynchronizer采取的方法是，依賴原子性的CAS以及循環(huán)奋早，來(lái)實(shí)現(xiàn)上述兩步的原子性盛霎。

為何addWaiter()實(shí)現(xiàn)時(shí)，是按照下面這個(gè)順序

1. 設(shè)置prev指針耽装；
2. compareAndSetTail()愤炸；
3. 設(shè)置next指針；

而不是3-2-1或是1-3-2這種順序呢掉奄？

對(duì)于3-2-1规个，我認(rèn)為，其實(shí)和1-2-3的本質(zhì)上是一樣的姓建，只是代碼實(shí)現(xiàn)時(shí)诞仓，選擇prev指針而已。1-2-3這種方式保證了prev的可靠性速兔，可以看到AbstractQueuedSynchronizer中一些需要遍歷隊(duì)列的方法墅拭，如getQueuedThreads()，都是使用的prev涣狗。

對(duì)于1-3-2谍婉，我們可以按照上面的圖"線程A和線程B的執(zhí)行流程“，再推演一遍镀钓，可以發(fā)現(xiàn)穗熬，線程A在快速入隊(duì)時(shí)，對(duì)NodeA的prev指針和next指針的設(shè)置都浪費(fèi)了掸宛。而1-2-3的順序下死陆，僅是浪費(fèi)了設(shè)置prev指針這一步。

總而言之唧瘾，addWaiter()的實(shí)現(xiàn)保證了prev指針的可靠性措译。

那么，next指針既然不可靠饰序，那為何還需要呢领虹？prev指針不是已經(jīng)保證了隊(duì)列的可訪問(wèn)性了么？引用源碼中對(duì)Node的注釋求豫。

We also use "next" links to implement blocking mechanics. The thread id for each node is kept in its own node, so a predecessor signals the next node to wake up by traversing next link to determine which thread it is. Determination of successor must avoid races with newly queued nodes to set the "next" fields of their predecessors. This is solved when necessary by checking backwards from the atomically updated "tail" when a node's successor appears to be null. (Or, said differently, the next-links are an optimization so that we don't usually need a backward scan.)

這段話的大意是說(shuō)某個(gè)節(jié)點(diǎn)在釋放鎖時(shí)塌衰，需要喚醒其后繼節(jié)點(diǎn)羔杨。如果沒(méi)有next指針幢尚，那么每次都需要從tail往前遍歷跳座，next指針則優(yōu)化了這一操作珍德。但是要注意的是，因?yàn)閚ext指針并不可靠努酸，所以有時(shí)候next指針會(huì)是null服爷，此時(shí)，依然需要依賴tail指針向前回溯获诈，以找到期望的節(jié)點(diǎn)仍源。