本人免費(fèi)整理了Java高級(jí)資料，涵蓋了Java、Redis、MongoDB、MySQL、Zookeeper、Spring Cloud、Dubbo高并發(fā)分布式等教程，一共30G，需要自己領(lǐng)取。
傳送門：https://mp.weixin.qq.com/s/JzddfH-7yNudmkjT0IRL8Q

1.ConcurrentLinkedQueue簡介

在單線程編程中我們會(huì)經(jīng)常用到一些集合類，比如ArrayList,HashMap等，但是這些類都不是線程安全的類。在面試中也經(jīng)常會(huì)有一些考點(diǎn)，比如ArrayList不是線程安全的，Vector是線程安全。而保障Vector線程安全的方式，是非常粗暴的在方法上用synchronized獨(dú)占鎖，將多線程執(zhí)行變成串行化。要想將ArrayList變成線程安全的也可以使用Collections.synchronizedList(List<T> list)方法ArrayList轉(zhuǎn)換成線程安全的，但這種轉(zhuǎn)換方式依然是通過synchronized修飾方法實(shí)現(xiàn)的，很顯然這不是一種高效的方式，同時(shí)，隊(duì)列也是我們常用的一種數(shù)據(jù)結(jié)構(gòu)，為了解決線程安全的問題，Doug Lea大師為我們準(zhǔn)備了ConcurrentLinkedQueue這個(gè)線程安全的隊(duì)列。從類名就可以看的出來實(shí)現(xiàn)隊(duì)列的數(shù)據(jù)結(jié)構(gòu)是鏈?zhǔn)健?/p>創(chuàng)新互聯(lián)是一家專業(yè)提供裕安企業(yè)網(wǎng)站建設(shè),專注與成都網(wǎng)站建設(shè)、成都網(wǎng)站設(shè)計(jì)、H5高端網(wǎng)站建設(shè)、小程序制作等業(yè)務(wù)。10年已為裕安眾多企業(yè)、政府機(jī)構(gòu)等服務(wù)。創(chuàng)新互聯(lián)專業(yè)的建站公司優(yōu)惠進(jìn)行中。

1.1 Node

要想先學(xué)習(xí)ConcurrentLinkedQueue自然而然得先從它的節(jié)點(diǎn)類看起，明白它的底層數(shù)據(jù)結(jié)構(gòu)。Node類的源碼為：

private?static?class?Node<E>?{
????????volatile?E?item;
????????volatile?Node<E>?next;
????????.......}

Node節(jié)點(diǎn)主要包含了兩個(gè)域：一個(gè)是數(shù)據(jù)域item，另一個(gè)是next指針，用于指向下一個(gè)節(jié)點(diǎn)從而構(gòu)成鏈?zhǔn)疥?duì)列。并且都是用volatile進(jìn)行修飾的，以保證內(nèi)存可見性。另外ConcurrentLinkedQueue含有這樣兩個(gè)成員變量：

private?transient?volatile?Node<E>?head;private?transient?volatile?Node<E>?tail;

說明ConcurrentLinkedQueue通過持有頭尾指針進(jìn)行管理隊(duì)列。當(dāng)我們調(diào)用無參構(gòu)造器時(shí)，其源碼為：

public?ConcurrentLinkedQueue()?{
????head?=?tail?=?new?Node<E>(null);}

head和tail指針會(huì)指向一個(gè)item域?yàn)閚ull的節(jié)點(diǎn),此時(shí)ConcurrentLinkedQueue狀態(tài)如下圖所示：

如圖，head和tail指向同一個(gè)節(jié)點(diǎn)Node0，該節(jié)點(diǎn)item域?yàn)閚ull,next域?yàn)閚ull。

1.2 操作Node的幾個(gè)CAS操作

在隊(duì)列進(jìn)行出隊(duì)入隊(duì)的時(shí)候免不了對(duì)節(jié)點(diǎn)需要進(jìn)行操作，在多線程就很容易出現(xiàn)線程安全的問題。可以看出在處理器指令集能夠支持CMPXCHG指令后，在java源碼中涉及到并發(fā)處理都會(huì)使用CAS操作，那么在ConcurrentLinkedQueue對(duì)Node的CAS操作有這樣幾個(gè)：

//更改Node中的數(shù)據(jù)域item???
boolean?casItem(E?cmp,?E?val)?{
????return?UNSAFE.compareAndSwapObject(this,?itemOffset,?cmp,?val);}//更改Node中的指針域nextvoid?lazySetNext(Node<E>?val)?{
????UNSAFE.putOrderedObject(this,?nextOffset,?val);}//更改Node中的指針域nextboolean?casNext(Node<E>?cmp,?Node<E>?val)?{
????return?UNSAFE.compareAndSwapObject(this,?nextOffset,?cmp,?val);}

可以看出這些方法實(shí)際上是通過調(diào)用UNSAFE實(shí)例的方法，UNSAFE為sun.misc.Unsafe類，該類是hotspot底層方法，目前為止了解即可，知道CAS的操作歸根結(jié)底是由該類提供就好。

2.offer方法

對(duì)一個(gè)隊(duì)列來說，插入滿足FIFO特性，插入元素總是在隊(duì)列最末尾的地方進(jìn)行插入，而?。ㄒ瞥┰乜偸菑年?duì)列的隊(duì)頭。所有要想能夠徹底弄懂ConcurrentLinkedQueue自然而然是從offer方法和poll方法開始。那么為了能夠理解offer方法，采用debug的方式來一行一行的看代碼走。另外，在看多線程的代碼時(shí)，可采用這樣的思維方式：

單個(gè)線程offer?多個(gè)線程offer?部分線程offer，部分線程poll?----offer的速度快于poll --------隊(duì)列長度會(huì)越來越長，由于offer節(jié)點(diǎn)總是在對(duì)隊(duì)列隊(duì)尾，而poll節(jié)點(diǎn)總是在隊(duì)列對(duì)頭，也就是說offer線程和poll線程兩者并無“交集”，也就是說兩類線程間并不會(huì)相互影響，這種情況站在相對(duì)速率的角度來看，也就是一個(gè)"單線程offer" ----offer的速度慢于poll --------poll的相對(duì)速率快于offer，也就是隊(duì)頭刪的速度要快于隊(duì)尾添加節(jié)點(diǎn)的速度，導(dǎo)致的結(jié)果就是隊(duì)列長度會(huì)越來越短，而offer線程和poll線程就會(huì)出現(xiàn)“交集”，即那一時(shí)刻就可以稱之為offer線程和poll線程同時(shí)操作的節(jié)點(diǎn)為?臨界點(diǎn)?，且在該節(jié)點(diǎn)offer線程和poll線程必定相互影響。根據(jù)在臨界點(diǎn)時(shí)offer和poll發(fā)生的相對(duì)順序又可從兩個(gè)角度去思考：1. 執(zhí)行順序?yàn)閛ffer-->poll-->offer，即表現(xiàn)為當(dāng)offer線程在Node1后插入Node2時(shí)，此時(shí)poll線程已經(jīng)將Node1刪除，這種情況很顯然需要在offer方法中考慮；?2.執(zhí)行順序可能為：poll-->offer-->poll，即表現(xiàn)為當(dāng)poll線程準(zhǔn)備刪除的節(jié)點(diǎn)為null時(shí)（隊(duì)列為空隊(duì)列），此時(shí)offer線程插入一個(gè)節(jié)點(diǎn)使得隊(duì)列變?yōu)榉强贞?duì)列

先看這么一段代碼：

1\.?ConcurrentLinkedQueue<Integer>?queue?=?new?ConcurrentLinkedQueue<>();2\.?queue.offer(1);3\.?queue.offer(2);

創(chuàng)建一個(gè)ConcurrentLinkedQueue實(shí)例，先offer 1，然后再offer 2。offer的源碼為：

public?boolean?offer(E?e)?{1\.????checkNotNull(e);2\.????final?Node<E>?newNode?=?new?Node<E>(e);3\.????for?(Node<E>?t?=?tail,?p?=?t;;)?{4\.????????Node<E>?q?=?p.next;5\.????????if?(q?==?null)?{6\.????????????//?p?is?last?node7\.????????????if?(p.casNext(null,?newNode))?{
????????????????//?Successful?CAS?is?the?linearization?point????????????????//?for?e?to?become?an?element?of?this?queue,???????????????//?and?for?newNode?to?become?"live".8\.????????????????if?(p?!=?t)?//?hop?two?nodes?at?a?time9\.????????????????????casTail(t,?newNode);??//?Failure?is?OK.10\.????????????????return?true;
????????????}
????????????//?Lost?CAS?race?to?another?thread;?re-read?next????????}11\.????????else?if?(p?==?q)
????????????//?We?have?fallen?off?list.??If?tail?is?unchanged,?it????????????//?will?also?be?off-list,?in?which?case?we?need?to????????????//?jump?to?head,?from?which?all?live?nodes?are?always????????????//?reachable.??Else?the?new?tail?is?a?better?bet.12\.????????????p?=?(t?!=?(t?=?tail))???t?:?head;
???????????else
????????????//?Check?for?tail?updates?after?two?hops.13\.????????????p?=?(p?!=?t?&&?t?!=?(t?=?tail))???t?:?q;
????}}

單線程執(zhí)行角度分析：

先從單線程執(zhí)行的角度看起，分析offer 1的過程。第1行代碼會(huì)對(duì)是否為null進(jìn)行判斷，為null的話就直接拋出空指針異常，第2行代碼將e包裝成一個(gè)Node類，第3行為for循環(huán)，只有初始化條件沒有循環(huán)結(jié)束條件，這很符合CAS的“套路”，在循環(huán)體CAS操作成功會(huì)直接return返回，如果CAS操作失敗的話就在for循環(huán)中不斷重試直至成功。

這里實(shí)例變量t被初始化為tail，p被初始化為t即tail。為了方便下面的理解，p被認(rèn)為隊(duì)列真正的尾節(jié)點(diǎn)，tail不一定指向?qū)ο笳嬲奈补?jié)點(diǎn)，因?yàn)樵贑oncurrentLinkedQueue中tail是被延遲更新的，具體原因我們慢慢來看。代碼走到第3行的時(shí)候，t和p都分別指向初始化時(shí)創(chuàng)建的item域?yàn)閚ull，next域?yàn)閚ull的Node0。

第4行變量q被賦值為null，第5行if判斷為true，在第7行使用casNext將插入的Node設(shè)置成當(dāng)前隊(duì)列尾節(jié)點(diǎn)p的next節(jié)點(diǎn)，如果CAS操作失敗，此次循環(huán)結(jié)束在下次循環(huán)中進(jìn)行重試。CAS操作成功走到第8行，此時(shí)p==t，if判斷為false,直接return true返回。如果成功插入1的話，此時(shí)ConcurrentLinkedQueue的狀態(tài)如下圖所示：

如圖，此時(shí)隊(duì)列的尾節(jié)點(diǎn)應(yīng)該為Node1,而tail指向的節(jié)點(diǎn)依然還是Node0,因此可以說明tail是延遲更新的。那么我們繼續(xù)來看offer 2的時(shí)候的情況，很顯然此時(shí)第4行q指向的節(jié)點(diǎn)不為null了，而是指向Node1,第5行if判斷為false,第11行if判斷為false,代碼會(huì)走到第13行。

好了，再插入節(jié)點(diǎn)的時(shí)候我們會(huì)問自己這樣一個(gè)問題？上面已經(jīng)解釋了tail并不是指向隊(duì)列真正的尾節(jié)點(diǎn)，那么在插入節(jié)點(diǎn)的時(shí)候，我們是不是應(yīng)該最開始做的就是找到隊(duì)列當(dāng)前的尾節(jié)點(diǎn)在哪里才能插入？那么第13行代碼就是找出隊(duì)列真正的尾節(jié)點(diǎn)。

定位隊(duì)列真正的對(duì)尾節(jié)點(diǎn)

p?=?(p?!=?t?&&?t?!=?(t?=?tail))???t?:?q;

我們來分析一下這行代碼，如果這段代碼在單線程環(huán)境執(zhí)行時(shí)，很顯然由于p==t,此時(shí)p會(huì)被賦值為q,而q等于Node<E> q = p.next，即Node1。在第一次循環(huán)中指針p指向了隊(duì)列真正的隊(duì)尾節(jié)點(diǎn)Node1，那么在下一次循環(huán)中第4行q指向的節(jié)點(diǎn)為null，那么在第5行中if判斷為true,那么在第7行依然通過casNext方法設(shè)置p節(jié)點(diǎn)的next為當(dāng)前新增的Node,接下來走到第8行，這個(gè)時(shí)候p!=t，第8行if判斷為true,會(huì)通過casTail(t, newNode)將當(dāng)前節(jié)點(diǎn)Node設(shè)置為隊(duì)列的隊(duì)尾節(jié)點(diǎn),此時(shí)的隊(duì)列狀態(tài)示意圖如下圖所示：

tail指向的節(jié)點(diǎn)由Node0改變?yōu)镹ode2,這里的casTail失敗不需要重試的原因是，offer代碼中主要是通過p的next節(jié)點(diǎn)q(Node<E> q = p.next)決定后面的邏輯走向的，當(dāng)casTail失敗時(shí)狀態(tài)示意圖如下

如圖，如果這里casTail設(shè)置tail失敗即tail還是指向Node0節(jié)點(diǎn)的話，無非就是多循環(huán)幾次通過13行代碼定位到隊(duì)尾節(jié)點(diǎn)。

通過對(duì)單線程執(zhí)行角度進(jìn)行分析，我們可以了解到poll的執(zhí)行邏輯為：

1. 如果tail指向的節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)（next域）為null的話，說明tail指向的節(jié)點(diǎn)即為隊(duì)列真正的隊(duì)尾節(jié)點(diǎn)，因此可以通過casNext插入當(dāng)前待插入的節(jié)點(diǎn),但此時(shí)tail并未變化，如圖2;

2. 如果tail指向的節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)（next域）不為null的話，說明tail指向的節(jié)點(diǎn)不是隊(duì)列的真正隊(duì)尾節(jié)點(diǎn)。通過q（Node<E> q = p.next）指針往前遞進(jìn)去找到隊(duì)尾節(jié)點(diǎn)，然后通過casNext插入當(dāng)前待插入的節(jié)點(diǎn)，并通過casTail方式更改tail，如圖3。

我們回過頭再來看p = (p != t && t != (t = tail)) ? t : q;這行代碼在單線程中，這段代碼永遠(yuǎn)不會(huì)將p賦值為t,那么這么寫就不會(huì)有任何作用，那我們?cè)囍诙嗑€程的情況下進(jìn)行分析。

多線程執(zhí)行角度分析

多個(gè)線程offer

很顯然這么寫另有深意，其實(shí)在多線程環(huán)境下這行代碼很有意思的。?t != (t = tail)這個(gè)操作并非一個(gè)原子操作，有這樣一種情況：

如圖，假設(shè)線程A此時(shí)讀取了變量t，線程B剛好在這個(gè)時(shí)候offer一個(gè)Node后，此時(shí)會(huì)修改tail指針,那么這個(gè)時(shí)候線程A再次執(zhí)行t=tail時(shí)t會(huì)指向另外一個(gè)節(jié)點(diǎn)，很顯然線程A前后兩次讀取的變量t指向的節(jié)點(diǎn)不相同，即t != (t = tail)為true,并且由于t指向節(jié)點(diǎn)的變化p != t也為true，此時(shí)該行代碼的執(zhí)行結(jié)果為p和t最新的t指針指向了同一個(gè)節(jié)點(diǎn)，并且此時(shí)t也是隊(duì)列真正的對(duì)尾節(jié)點(diǎn)。那么，現(xiàn)在已經(jīng)定位到隊(duì)列真正的隊(duì)尾節(jié)點(diǎn)，就可以執(zhí)行offer操作了。

offer->poll->offer

那么還剩下第11行的代碼我們沒有分析，大致可以猜想到應(yīng)該就是回答一部分線程offer，一部分poll的這種情況。當(dāng)if (p == q)為true時(shí)，說明p指向的節(jié)點(diǎn)的next也指向它自己，這種節(jié)點(diǎn)稱之為哨兵節(jié)點(diǎn)，這種節(jié)點(diǎn)在隊(duì)列中存在的價(jià)值不大，一般表示為要?jiǎng)h除的節(jié)點(diǎn)或者是空節(jié)點(diǎn)。為了能夠很好的理解這種情況，我們先看看poll方法的執(zhí)行過程后，再回過頭來看，總之這是一個(gè)很有意思的事情 :)。

3.poll方法

poll方法源碼如下：

public?E?poll()?{????restartFromHead:
????1\.?for?(;;)?{
????2\.????for?(Node<E>?h?=?head,?p?=?h,?q;;)?{
????3\.????????E?item?=?p.item;

????4\.????????if?(item?!=?null?&&?p.casItem(item,?null))?{
????????????????//?Successful?CAS?is?the?linearization?point????????????????//?for?item?to?be?removed?from?this?queue.????5\.????????????if?(p?!=?h)?//?hop?two?nodes?at?a?time????6\.????????????????updateHead(h,?((q?=?p.next)?!=?null)???q?:?p);
????7\.????????????return?item;
????????????}
????8\.????????else?if?((q?=?p.next)?==?null)?{
????9\.????????????updateHead(h,?p);
????10\.????????????return?null;
????????????}
????11\.????????else?if?(p?==?q)
????12\.????????????continue?restartFromHead;
????????????else
????13\.????????????p?=?q;
????????}
????}}

我們還是先站在單線程的角度去理清該方法的基本邏輯。假設(shè)ConcurrentLinkedQueue初始狀態(tài)如下圖所示：

參數(shù)offer時(shí)的定義，我們還是先將變量p作為隊(duì)列要?jiǎng)h除真正的隊(duì)頭節(jié)點(diǎn)，h（head）指向的節(jié)點(diǎn)并不一定是隊(duì)列的隊(duì)頭節(jié)點(diǎn)。先來看poll出Node1時(shí)的情況，由于p=h=head，參照上圖，很顯然此時(shí)p指向的Node1的數(shù)據(jù)域不為null,在第4行代碼中item!=null判斷為true后接下來通過casItem將Node1的數(shù)據(jù)域設(shè)置為null。

如果CAS設(shè)置失敗則此次循環(huán)結(jié)束等待下一次循環(huán)進(jìn)行重試。若第4行執(zhí)行成功進(jìn)入到第5行代碼，此時(shí)p和h都指向Node1,第5行if判斷為false,然后直接到第7行return回Node1的數(shù)據(jù)域1，方法運(yùn)行結(jié)束，此時(shí)的隊(duì)列狀態(tài)如下圖。

下面繼續(xù)從隊(duì)列中poll，很顯然當(dāng)前h和p指向的Node1的數(shù)據(jù)域?yàn)閚ull，那么第一件事就是要定位準(zhǔn)備刪除的隊(duì)頭節(jié)點(diǎn)(找到數(shù)據(jù)域不為null的節(jié)點(diǎn))。

定位刪除的隊(duì)頭節(jié)點(diǎn)

繼續(xù)看，第三行代碼item為null,第4行代碼if判斷為false,走到第8行代碼（q = p.next）if也為false，由于q指向了Node2,在第11行的if判斷也為false，因此代碼走到了第13行，這個(gè)時(shí)候p和q共同指向了Node2,也就找到了要?jiǎng)h除的真正的隊(duì)頭節(jié)點(diǎn)。

可以總結(jié)出，定位待刪除的隊(duì)頭節(jié)點(diǎn)的過程為：如果當(dāng)前節(jié)點(diǎn)的數(shù)據(jù)域?yàn)閚ull，很顯然該節(jié)點(diǎn)不是待刪除的節(jié)點(diǎn)，就用當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)去試探。在經(jīng)過第一次循環(huán)后，此時(shí)狀態(tài)圖為下圖：

進(jìn)行下一次循環(huán)，第4行的操作同上述，當(dāng)前假設(shè)第4行中casItem設(shè)置成功，由于p已經(jīng)指向了Node2,而h還依舊指向Node1,此時(shí)第5行的if判斷為true，然后執(zhí)行updateHead(h, ((q = p.next) != null) ? q : p)，此時(shí)q指向的Node3，所有傳入updateHead方法的分別是指向Node1的h引用和指向Node3的q引用。updateHead方法的源碼為：

final?void?updateHead(Node<E>?h,?Node<E>?p)?{
????if?(h?!=?p?&&?casHead(h,?p))
????????h.lazySetNext(h);
}

該方法主要是通過casHead將隊(duì)列的head指向Node3,并且通過?h.lazySetNext將Node1的next域指向它自己。最后在第7行代碼中返回Node2的值。此時(shí)隊(duì)列的狀態(tài)如下圖所示：

Node1的next域指向它自己，head指向了Node3。如果隊(duì)列為空隊(duì)列的話，就會(huì)執(zhí)行到代碼的第8行(q = p.next) == null，if判斷為true,因此在第10行中直接返回null。以上的分析是從單線程執(zhí)行的角度去看，也可以讓我們了解poll的整體思路，現(xiàn)在來做一個(gè)總結(jié)：

1. 如果當(dāng)前head,h和p指向的節(jié)點(diǎn)的Item不為null的話，說明該節(jié)點(diǎn)即為真正的隊(duì)頭節(jié)點(diǎn)（待刪除節(jié)點(diǎn)），只需要通過casItem方法將item域設(shè)置為null,然后將原來的item直接返回即可。

2. 如果當(dāng)前head,h和p指向的節(jié)點(diǎn)的item為null的話，則說明該節(jié)點(diǎn)不是真正的待刪除節(jié)點(diǎn)，那么應(yīng)該做的就是尋找item不為null的節(jié)點(diǎn)。通過讓q指向p的下一個(gè)節(jié)點(diǎn)（q = p.next）進(jìn)行試探，若找到則通過updateHead方法更新head指向的節(jié)點(diǎn)以及構(gòu)造哨兵節(jié)點(diǎn)（通過updateHead方法的h.lazySetNext(h)）。

接下來，按照上面分析offer的思維方式，下面來分析一下多線程的情況，第一種情況是；

多線程執(zhí)行情況分析：

多個(gè)線程poll

現(xiàn)在回過頭來看poll方法的源碼，有這樣一部分：

else?if?(p?==?q)
????continue?restartFromHead;

這一部分就是處理多個(gè)線程poll的情況，q = p.next也就是說q永遠(yuǎn)指向的是p的下一個(gè)節(jié)點(diǎn)，那么什么情況下會(huì)使得p,q指向同一個(gè)節(jié)點(diǎn)呢？根據(jù)上面我們的分析，只有p指向的節(jié)點(diǎn)在poll的時(shí)候轉(zhuǎn)變成了哨兵節(jié)點(diǎn)（通過updateHead方法中的h.lazySetNext）。

當(dāng)線程A在判斷p==q時(shí)，線程B已經(jīng)將執(zhí)行完poll方法將p指向的節(jié)點(diǎn)轉(zhuǎn)換為哨兵節(jié)點(diǎn)并且head指向的節(jié)點(diǎn)已經(jīng)發(fā)生了改變，所以就需要從restartFromHead處執(zhí)行，保證用到的是最新的head。

poll->offer->poll

試想，還有這樣一種情況，如果當(dāng)前隊(duì)列為空隊(duì)列，線程A進(jìn)行poll操作，同時(shí)線程B執(zhí)行offer，然后線程A在執(zhí)行poll，那么此時(shí)線程A返回的是null還是線程B剛插入的最新的那個(gè)節(jié)點(diǎn)呢？我們來寫一代demo：

public?static?void?main(String[]?args)?{
????Thread?thread1?=?new?Thread(()?->?{
????????Integer?value?=?queue.poll();
????????System.out.println(Thread.currentThread().getName()?+?"?poll?的值為："?+?value);
????????System.out.println("queue當(dāng)前是否為空隊(duì)列："?+?queue.isEmpty());
????});
????thread1.start();
????Thread?thread2?=?new?Thread(()?->?{
????????queue.offer(1);
????});
????thread2.start();
}

輸出結(jié)果為：

Thread-0 poll 的值為：null queue當(dāng)前是否為空隊(duì)列：false

通過debug控制線程thread1和線程thread2的執(zhí)行順序，thread1先執(zhí)行到第8行代碼if ((q = p.next) == null)，由于此時(shí)隊(duì)列為空隊(duì)列if判斷為true，進(jìn)入if塊，此時(shí)先讓thread1暫停，然后thread2進(jìn)行offer插入值為1的節(jié)點(diǎn)后，thread2執(zhí)行結(jié)束。再讓thread1執(zhí)行，這時(shí)thread1并沒有進(jìn)行重試，而是代碼繼續(xù)往下走，返回null，盡管此時(shí)隊(duì)列由于thread2已經(jīng)插入了值為1的新的節(jié)點(diǎn)。所以輸出結(jié)果為thread0 poll的為null,然隊(duì)列不為空隊(duì)列。因此，在判斷隊(duì)列是否為空隊(duì)列的時(shí)候是不能通過線程在poll的時(shí)候返回為null進(jìn)行判斷的，可以通過isEmpty方法進(jìn)行判斷。

4. offer方法中部分線程offer部分線程poll

在分析offer方法的時(shí)候我們還留下了一個(gè)問題，即對(duì)offer方法中第11行代碼的理解。

offer->poll->offer

在offer方法的第11行代碼if (p == q)，能夠讓if判斷為true的情況為p指向的節(jié)點(diǎn)為哨兵節(jié)點(diǎn)，而什么時(shí)候會(huì)構(gòu)造哨兵節(jié)點(diǎn)呢？在對(duì)poll方法的討論中，我們已經(jīng)找到了答案，即當(dāng)head指向的節(jié)點(diǎn)的item域?yàn)閚ull時(shí)會(huì)尋找真正的隊(duì)頭節(jié)點(diǎn)，等到待插入的節(jié)點(diǎn)插入之后，會(huì)更新head，并且將原來head指向的節(jié)點(diǎn)設(shè)置為哨兵節(jié)點(diǎn)。假設(shè)隊(duì)列初始狀態(tài)如下圖所示：

因此在線程A執(zhí)行offer時(shí)，線程B執(zhí)行poll就會(huì)存在如下一種情況：

如圖，線程A的tail節(jié)點(diǎn)存在next節(jié)點(diǎn)Node1,因此會(huì)通過引用q往前尋找隊(duì)列真正的隊(duì)尾節(jié)點(diǎn)，當(dāng)執(zhí)行到判斷if (p == q)時(shí)，此時(shí)線程B執(zhí)行poll操作，在對(duì)線程B來說，head和p指向Node0,由于Node0的item域?yàn)閚ull,同樣會(huì)往前遞進(jìn)找到隊(duì)列真正的隊(duì)頭節(jié)點(diǎn)Node1,在線程B執(zhí)行完poll之后，Node0就會(huì)轉(zhuǎn)換為哨兵節(jié)點(diǎn)，也就意味著隊(duì)列的head發(fā)生了改變，此時(shí)隊(duì)列狀態(tài)為下圖。

image.png

此時(shí)線程A在執(zhí)行判斷if (p == q)時(shí)就為true,會(huì)繼續(xù)執(zhí)行p = (t != (t = tail)) ? t : head;，由于tail指針沒有發(fā)生改變所以p被賦值為head,重新從head開始完成插入操作。

5. HOPS的設(shè)計(jì)

通過上面對(duì)offer和poll方法的分析，我們發(fā)現(xiàn)tail和head是延遲更新的，兩者更新觸發(fā)時(shí)機(jī)為：

tail更新觸發(fā)時(shí)機(jī)：當(dāng)tail指向的節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)不為null的時(shí)候，會(huì)執(zhí)行定位隊(duì)列真正的隊(duì)尾節(jié)點(diǎn)的操作，找到隊(duì)尾節(jié)點(diǎn)后完成插入之后才會(huì)通過casTail進(jìn)行tail更新；當(dāng)tail指向的節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)為null的時(shí)候，只插入節(jié)點(diǎn)不更新tail。

head更新觸發(fā)時(shí)機(jī)：當(dāng)head指向的節(jié)點(diǎn)的item域?yàn)閚ull的時(shí)候，會(huì)執(zhí)行定位隊(duì)列真正的隊(duì)頭節(jié)點(diǎn)的操作，找到隊(duì)頭節(jié)點(diǎn)后完成刪除之后才會(huì)通過updateHead進(jìn)行head更新；當(dāng)head指向的節(jié)點(diǎn)的item域不為null的時(shí)候，只刪除節(jié)點(diǎn)不更新head。

并且在更新操作時(shí)，源碼中會(huì)有注釋為：hop two nodes at a time。所以這種延遲更新的策略就被叫做HOPS的大概原因是這個(gè)（猜的 :)），從上面更新時(shí)的狀態(tài)圖可以看出，head和tail的更新是“跳著的”即中間總是間隔了一個(gè)。那么這樣設(shè)計(jì)的意圖是什么呢？

如果讓tail永遠(yuǎn)作為隊(duì)列的隊(duì)尾節(jié)點(diǎn)，實(shí)現(xiàn)的代碼量會(huì)更少，而且邏輯更易懂。但是，這樣做有一個(gè)缺點(diǎn)，**如果大量的入隊(duì)操作，每次都要執(zhí)行CAS進(jìn)行tail的更新，匯總起來對(duì)性能也會(huì)是大大的損耗。如果能減少CAS更新的操作，無疑可以大大提升入隊(duì)的操作效率，所以doug lea大師每間隔1次（tail和隊(duì)尾節(jié)點(diǎn)的距離為1）進(jìn)行才利用CAS更新tail。

**對(duì)head的更新也是同樣的道理，雖然，這樣設(shè)計(jì)會(huì)多出在循環(huán)中定位隊(duì)尾節(jié)點(diǎn)，但總體來說讀的操作效率要遠(yuǎn)遠(yuǎn)高于寫的性能，因此，多出來的在循環(huán)中定位尾節(jié)點(diǎn)的操作的性能損耗相對(duì)而言是很小的。

創(chuàng)新互聯(lián)www.cdcxhl.cn，專業(yè)提供香港、美國云服務(wù)器，動(dòng)態(tài)BGP最優(yōu)骨干路由自動(dòng)選擇，持續(xù)穩(wěn)定高效的網(wǎng)絡(luò)助力業(yè)務(wù)部署。公司持有工信部辦法的idc、isp許可證， 機(jī)房獨(dú)有T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確進(jìn)行流量調(diào)度，確保服務(wù)器高可用性。佳節(jié)活動(dòng)現(xiàn)已開啟，新人活動(dòng)云服務(wù)器買多久送多久。

網(wǎng)站題目：并發(fā)容器之ConcurrentLinkedQueue-創(chuàng)新互聯(lián)
路徑分享：http://www.rwnh.cn/article42/cciphc.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供品牌網(wǎng)站建設(shè)、企業(yè)網(wǎng)站制作、營銷型網(wǎng)站建設(shè)、關(guān)鍵詞優(yōu)化、網(wǎng)站收錄、ChatGPT

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)