ConcurrentLinkedQueue原理剖析

前言

ConcurrentLinkedQueue是無界線程安全基於FIFO的非阻塞隊列，基於wait-free實現。

ConcurrentLinkedQueue由Node節點、head頭節點、tail尾節點組成，其中Node節點是一個單鏈表結構，由item和next組成。

ConcurrentLinkedQueue默認構造函數如下：

其中head、tail節點默認指向一個item為null的Node節點。

ConcurrentLinkedQueue的入隊過程

源碼如下：

注意：如果tail節點的next節點為空，則將入隊節點設置為tail節點的next節點（此時不用更新tail節點），如果tail節點的next節點不為空，則將入隊節點設置為tail節點，tail節點不總是尾節點

分析：

1. 入隊過程首先創建一個newNode。
2. 變量t指向tail節點，p作為迭代鏈表的迭代器，初始時也是指向tail節點。
3. 判斷p的next節點q是否為null,如果為null，則將入隊節點newNode通過CAS設置為尾節點，如果設置成功，則判斷p是否等於 t，當p != t 時，證明已經hop過了兩個節點，（每經過兩個節點，就要更新一次tail節點）則CAS更新tail節點為新的入隊節點。當p == t時，此時不用更新tail節點。（也就是這次需要更新tail節點，下次就不需要更新tail節點，這樣間隔地來。）當tail節點有next節點時，p會變化，則tail會不等於p，此時就需要CAS更新tail節點為入隊節點。
4. 如果第3步的CAS設置尾節點不成功，則說明有其它線程搶先更新了尾節點，那麼就需要重讀p的next節點。
5. 如果第三步的CAS更新tail節點失敗無所謂，這說明其它線程成功更新了尾節點（注意此時鏈表的節點是完整的）
6. p == q的情況,當隊列中有兩個元素時，tail和head都指向第一個元素，那麼當把head節點poll出來的時候，那麼這種情況下有如下關係tail == head == t == p, 又因為更新了head節點，同時有p.next = p，當把p.next賦值給q的時候，q和p就會相等。這種情況下p節點已經脫離鏈表（fallen off list），需要重讀得到更新後的head節點，從新從head節點開始。另一種情況是源碼中的(t != (t = tail))，tail節點發生變化時，即其它線程更新了tail節點，那麼就不需要從head節點從新來讀，直接從新的tail節點開始遍歷即可。
7. 最後一個else情況：(p != t && t != (t = tail))如果p在遍歷過程中發現tail節點已經變化（被其它線程更改）且p節點不等於新的tail節點，那麼需要將新的tail節點指向p，p重新從新的tail節點開始遍歷。

ConcurrentLinkedQueue的入隊過程，並沒有利用互斥鎖來實現，但卻通過巧妙的設計實現了多線程併發下隊列的線程安全。因為hop機制避免了每次的入隊操作都進行CAS tail節點的更新，如果每個入隊的節點都設置為tail節點，那麼這是最簡單的，但不好的是，這樣會導致頻繁的CAS原子更新tail節點，要知道CAS的寫性能消耗要比CAS讀性能大得多，hop很巧妙地避免了這一點，基本把CAS更新tail節點的頻率降低50%。但使用hop機制，會降低數據的檢索速度，因為要從tail節點開始遍歷，所以hop的跨度不應該過大。ConcurrentLinkedQueue默認的hop是2，也就是n次入隊，n為（1，3，5，7….）時才需要為更新tail節點。

ConcurrentLinkedQueue的出隊過程

源碼如下：

分析：

1. 出隊時，head == h == p，如果p節點的item不為null,則CAS更新p節點（也就是head節點）的item為null。如果還未經過hop， 即p == h時，直接返回item，不需要CAS更新頭節點。
2. 如果p節點的item為null，如果p.next不為空，則p開始遍歷，p跳到下一個元素，再次判斷item。當判斷到item不為空時，如果 p != h，則要更新head節點。新的head節點計算如下：((q = p.next) != null) ? q : p，如果p.next不為空，則將頭節點更新為p的next節點（因為p節點的item已經被CAS設置為null了），如果p.next為空，則將頭節點更新為p節點
3. 當判斷p.item為空時，p.next如果為空，則更新頭節點。

• 這時的頭節點有兩種情況1）隊列中只有一個的節點 （item有可能為null，也有可能casItem失敗，被其它線程更新成功了），這時候不需要更新頭節點，因為這兩節點是一樣的。
• 隊列中有多個節點。可能item為null也有可能casItem失敗（反正都不會進入第一個if判斷）這時將最後一個節點更新為頭節點

1. p == q和情況，當隊列中有大於等2個節點時，當線程1操作頭節點1期間，線程2已經將頭節點更新為節點2，也就是頭節點1已經是fallen off list。有這樣的關係p.next = p，如果將q = p.next，那麼p和q就會相等（引入著一個無效的之前的head節）這樣就需要從新從頭節點處開始遍歷。

注意：更新head節點也是利用了hop這一機制，並不是每次出隊都會更新head節點。當head節點的item不為null時，不需要更新頭節點當head節佔的item為null時，需要更新頭節點。

更新頭節點時，原頭節點的next引用會指向自身，也就是pre_head.next = pre_head，當滿足這種關係時，需要重新從新的head節點處操作。

相關說明如下：

h.lazySetNext(h)會將h的next引用關聯到自身，然後調用succ的時候，就會返回新的head節點。