ConcurrentLinkedQueue是一個lock-free的非阻塞式線程安全的同步隊列宾巍，其中freelock算法是值得讓人思考和深究的节槐；
Michael & Scott算法
因為ConcurrentLinkedQueue是在Michael & Scott算法(論文)的基礎(chǔ)上做了一些修改的，所以先可以了解下該算法的原理；
背景
并發(fā)FIFO隊列廣泛應(yīng)用于并行應(yīng)用程序和操作系統(tǒng)中。為了確保數(shù)據(jù)的正確性，必須同步對共享隊列的并發(fā)訪問撇叁。通常，并發(fā)數(shù)據(jù)結(jié)構(gòu)(包括FIFO隊列)的算法分為兩類：阻塞和非阻塞畦贸；
阻塞算法允許一個緩慢或延遲的進(jìn)程陨闹，以防止更快的進(jìn)程無限期地對共享數(shù)據(jù)結(jié)構(gòu)的進(jìn)行操作。
非阻塞算法保證薄坏，如果有一個或多個活動線程試圖在共享數(shù)據(jù)結(jié)構(gòu)上執(zhí)行操作趋厉，某些操作將在有限的時間和步長內(nèi)完成。
在異步(尤其是多進(jìn)程)多處理器系統(tǒng)上胶坠，當(dāng)進(jìn)程在不適當(dāng)?shù)臅r候停止或延遲時君账，阻塞算法會導(dǎo)致顯著的性能下降。延遲的可能來源包括處理器調(diào)度搶占沈善、頁面錯誤和緩存丟失乡数。面對這些事件，非阻塞算法更加健壯闻牡。
原理
該算法是一個FIFO的净赴、帶有一個head和tail節(jié)點單鏈表隊列結(jié)構(gòu)，Head總是指向一個虛擬節(jié)點罩润，它是列表中的第一個節(jié)點玖翅；Tail指向列表中的最后一個節(jié)點或倒數(shù)第二個節(jié)點；因為是lock-free，使用CAS代替原本的加鎖邏輯金度，同時采用修改程序計數(shù)器的方式來避免CAS造成的ABA問題（并不是CAS的語義造成的ABA問題应媚，而是伴隨著CAS操作的上下文可能會存在ABA問題）；
該算法可以保證安全性猜极，因為滿足以下一些性質(zhì)：
- 鏈表是連續(xù)的珍特；
- 新節(jié)點只在鏈表的最后一個節(jié)點之后插入，出隊時只在鏈表的頭節(jié)點開始移除魔吐；
- Head始終指向鏈表中的第一個節(jié)點，tail總是指向鏈表的某一個節(jié)點莱找；
有了上面幾個特性酬姆，就可以推導(dǎo)出以下幾個結(jié)論
鏈表總是連接的，因為一旦插入了一個節(jié)點奥溺，它的下一個指針在釋放之前不會被設(shè)置為NULL辞色，并且一直不會釋放該節(jié)點直到從隊頭刪除。
在無鎖定算法浮定，節(jié)點只會被插入到鏈表的末尾相满，因為他們是通過tail指針鏈接，tail總是指向鏈表中的某一個節(jié)點桦卒，一個新節(jié)點只會被添加到某個next域為null的節(jié)點立美，通常這個節(jié)點是鏈表的最后一個；
節(jié)點從列表的頭部被刪除方灾，因為它們只有在被Head指向時才會被刪除建蹄，Head總是指向列表中的第一個節(jié)點。
Head始終指向列表中的第一個節(jié)點裕偿，并且它會自動地將其值更改為下一個節(jié)點(使用Head鎖或使用cas)洞慎。當(dāng)這種情況發(fā)生時，它用來指向的節(jié)點被認(rèn)為已從列表中刪除嘿棘。Head的新值不能為空劲腿，因為如果鏈表中有一個節(jié)點，dequeue操作將返回但不會刪除任何節(jié)點鸟妙。
Tail總是指向鏈表中的一個節(jié)點焦人，并且它從不落后于Head，所以它永遠(yuǎn)不會指向被刪除的節(jié)點圆仔。另外垃瞧，當(dāng)Tail改變它的值時，它總是移動到列表中的最后一個節(jié)點坪郭，如果下一個指針為空个从，則它被移動。
initialize(Q: pointer to queue_t)
// 初始化一個虛擬節(jié)點并將head和tail指向它
node = new_node()
node->next.ptr = NULL
Q->Head.ptr = Q->Tail.ptr = node
enqueue(Q: pointer to queue_t, value: data type)
// 創(chuàng)建即將入隊的新節(jié)點
E1: node = new_node()
E2: node->value = value
E3: node->next.ptr = NULL
// 無限循環(huán)直到入隊成功
E4: loop
E5: tail = Q->Tail
E6: next = tail.ptr->next
E7: if tail == Q->Tail
E8: if next.ptr == NULL
// 將新節(jié)點入隊
E9: if CAS(&tail.ptr->next, next, <node, next.count+1>)
E10: break // 完成入隊，退出循環(huán)
E11: endif
E12: else // tail并沒有指向最后一個節(jié)點
// 重新將tail節(jié)點指向最后一個節(jié)點嗦锐，重新循環(huán)
E13: CAS(&Q->Tail, tail, <next.ptr, tail.count+1>)
E14: endif
E15: endif
E16: endloop
// 入隊成功嫌松，試著將tail指向到新的插入節(jié)點上，可以允許失敗
E17: CAS(&Q->Tail, tail, <node, tail.count+1>)
dequeue(Q: pointer to queue_t, pvalue: pointer to data type): boolean
D1: loop // 循環(huán)直到有節(jié)點出隊
D2: head = Q->Head
D3: tail = Q->Tail
D4: next = head.ptr->next
D5: if head == Q->Head
D6: if head.ptr == tail.ptr
// 隊列為空或者tail節(jié)點在head節(jié)點前面
D7: if next.ptr == NULL
D8: return FALSE // 隊列是空的奕污，返回
D9: endif
// head節(jié)點落后于tail節(jié)點萎羔，嘗試將tail移到最后的位置
D10: CAS(&Q->Tail, tail, <next.ptr, tail.count+1>)
D11: else // 出隊只需處理head節(jié)點，tail節(jié)點不管
// CAS之前讀取值碳默，因為其他線程可能會釋放該節(jié)點
D12: *pvalue = next.ptr->value
// 將head節(jié)點指向已經(jīng)出隊的節(jié)點贾陷，將其作為新的哨兵節(jié)點
D13: if CAS(&Q->Head, head, <next.ptr, head.count+1>)
D14: break // 出隊完成，退出循環(huán)
D15: endif
D16: endif
D17: endif
D18: endloop
D19: free(head.ptr) // 釋放head節(jié)點的ptr嘱根，置為null
D20: return TRUE
有了這些規(guī)則定義后髓废，可以來分析算法的源碼了；
入隊
只有當(dāng)E7该抒、E8中的條件失敗或E9中的CAS失敗時慌洪，隊列操作才會循環(huán)；
在執(zhí)行了E5之后凑保，如果當(dāng)前線程失去了CPU的執(zhí)行權(quán)（比如時間片到了）冈爹，其他線程修改了tail節(jié)點，那么E7行中的條件就會失敗欧引，因此如果E7行失敗不止一次频伤，那么一定存在另一個線程完成了入隊操作；
如果Tail節(jié)點指向鏈表中倒數(shù)第二個節(jié)點维咸，則E8行判斷將失敗剂买，在E13行進(jìn)行CAS后，tail必須指向列表中的最后一個節(jié)點癌蓖，除非某個線程成功的插入了一個新的節(jié)點瞬哼，因此第E8行的判斷失敗了不止一次，那么一定存在另一個線程完成了入隊操作租副；
只有當(dāng)另一個線程成功地將一個新節(jié)點加入隊列時坐慰，第E9行中的CAS操作才會失敗。出隊
只有當(dāng)D5行中的條件失敗用僧、D6行中的條件保持不變(且隊列不是空的)或D13行中的CAS失敗時结胀，dequeue操作才會循環(huán)。
D5行中的條件和D13行中的cas只有在另一個線程修改Head時才會失敗责循，只有當(dāng)一個線程成功地使一個Node退出隊列時糟港，才會修改Head。
只有當(dāng)Tail指向鏈表中倒數(shù)第二個節(jié)點時院仿，D6行的條件才會成功(且隊列不是空的)秸抚。
在D10行進(jìn)行CAS之后速和，Tail必須指向列表中的最后一個節(jié)點，除非另一個線程成功的將一個新節(jié)點入隊剥汤。因此颠放，如果D6行的條件成功了不止一次，那么一定存在另一個線程完成了一個入隊操作或者出隊操作吭敢；
了解Michael & Scott算法之后碰凶，就可以對比ConcurrentLinkedQueue的異同；
特性
ConcurrentLinkedQueue是在Michael&Scott算法的基礎(chǔ)上做了一個修改鹿驼，適用于GC的環(huán)境欲低，由于不存在ABA的問題（因為就算是兩個A，但是對于節(jié)點來說內(nèi)存地址不一樣畜晰，所以不存在ABA問題）伸头，所以去掉了引用計數(shù)；
基本不變的規(guī)則有以下幾點：
- 只有一個(最后一個)節(jié)點具有
null的next引用(即新節(jié)點永遠(yuǎn)都從最后一個next為null的節(jié)點上添加的)舷蟀，它在排隊時被cas。最后一個節(jié)點可以在O(1)時間內(nèi)從tail節(jié)點到達(dá)面哼，但這僅僅是一個優(yōu)化——它也總是可以在O(N)時間內(nèi)從head到達(dá)同一個節(jié)點野宜。 - 所有被隊列中包含的非空元素是可以通過head的訪問的，通過CAS自動地將item為null的節(jié)點從隊列中刪除魔策。head到所有item不為null的可達(dá)性必須為true匈子，即使在并發(fā)條件下的修改而導(dǎo)致head的移動的情況下也是如此；對于創(chuàng)建了一個迭代器闯袒，或者僅僅是一個丟失了時間片的poll()虎敦，離開隊列的節(jié)點可能會被無限期地繼續(xù)使用。
上面的規(guī)則可能暗示了從一個被刪除的節(jié)點開始所有的節(jié)點都是gc可達(dá)的政敢，這將導(dǎo)致兩個問題:
- 允許一個迭代器造成無限的內(nèi)存占用
- 如果一個節(jié)點是活的其徙，則會導(dǎo)致舊節(jié)點與新節(jié)點的跨代連接，而分代gc很難處理這一問題喷户，從而導(dǎo)致重復(fù)的集合問題
為了解決這個問題唾那，代碼中使用了一個技巧，將所有被移除的節(jié)點的next節(jié)點都指向了自己本身褪尝，這可以隱含的告訴GC節(jié)點已經(jīng)是非可達(dá)的了闹获，從而可以被GC回收；
同時Head和Tail節(jié)點都是允許滯后更新的河哑，這是一個很重要的優(yōu)化避诽，可以減少更新頭尾節(jié)點的競爭提高并發(fā)性，最多允許落后一個節(jié)點的步長璃谨，當(dāng)有兩個或以上的步長時會更新頭尾節(jié)點沙庐；
debug的時候用IDEA時遇到debugger打印邏輯的錯誤鲤妥，一開始被IDEA給誤導(dǎo)了半天，很多代碼解釋不通轨功，最后采用的辦法是將代碼copy出來放在一個新的類里面就可以輸出正確的debugger結(jié)果了旭斥；
// head節(jié)點可以在O(1)時間內(nèi)到達(dá)第一個未被刪除的節(jié)點(如果有的話)的節(jié)點
// 不變性：
// - 鏈表中所有的節(jié)點都可以從head中訪問到
// - head != null
// - (tmp = head).next != tmp || tmp != head；代表head的next指針不可能指向自己
// 可變性：
// - head.item可是null或非null
// - 允許tail落后于head古涧，也就是說從head不可達(dá)到tail
private transient volatile Node<E> head;
// 列表中最后一個節(jié)點（也就是node.next == null的那個）辆它，可以從tail指針
// 以O(shè)(1)的時間到達(dá)
// 不變性：
// - 最后一個節(jié)點永遠(yuǎn)可以通過succ()從tail訪問
// - tail != null
// 可變性：
// - tail.item可是null或非null
// - 允許tail落后于head，也就是說從head不可達(dá)到tail
// - tail.next 允許指向自己
private transient volatile Node<E> tail;
//
public ConcurrentLinkedQueue() {
head = tail = new Node<E>(null);
}
初始化的時候會創(chuàng)建一個哨兵節(jié)點捕透，head和tail指向哨兵節(jié)點唠梨；
public boolean offer(E e) {
checkNotNull(e);
final Node<E> newNode = new Node<E>(e);
for (Node<E> t = tail, p = t;;) { // loop
Node<E> q = p.next;
if (q == null) {
// p是隊列結(jié)尾
if (p.casNext(null, newNode)) { // CAS成功
// 完成入隊
if (p != t)
// 如果tail距離尾節(jié)點的步長為2，更新tail
casTail(t, newNode); // 失敗也是ok的柒昏，意味著有其他線程更新成功
return true;
}
}
else if (p == q)
p = (t != (t = tail)) ? t : head;
else
p = (p != t && t != (t = tail)) ? t : q;
}
}
先假設(shè)單線程環(huán)境下的入隊操作凳宙，當(dāng)tail節(jié)點指向隊尾節(jié)點時，只需要通過一次CAS就可以入隊成功职祷；
可以看到氏涩，對比Michael&Scott算法的入隊操作，在更新尾節(jié)點的頻率上是更低頻次的有梆；
最多允許tail節(jié)點落后一個節(jié)點的步長是尖；現(xiàn)在可以理解p = (p != t && t != (t = tail)) ? t : q;這句話了;
// 走到這里代表p.next != null且p != p.next
p = (p != t && t != (t = tail)) ? t : q;
// 可以翻譯成下面的代碼
if (p == t) {
// 1
// 意味著tail節(jié)點沒有被其他線程修改，同時tail節(jié)點指向的并不是隊列最后一個節(jié)點
p = q;
} else {
// 2
// 并發(fā)情況下就有可能走到這里
// p.next != null && p != p.next && p != t
Node<E> tmp = t;
t = tail;
if (tmp != t) {
p = t; // tail被其他線程修改了泥耀，重新將p指向tail
} else {
p = q; // 指向next所指的節(jié)點
}
}
在通常情況下（比如上面的圖2場景）饺汹，tail節(jié)點并不是指向最后一個節(jié)點的時候，就有可能進(jìn)入到1的場景中痰催，這個還是比較好理解的兜辞；
就是場景2里面，只有在并發(fā)入隊的條件下才會有可能走到2夸溶，比如第一次走到場景1中逸吵，將q賦值給p，這時候p就是指向了原本p.next節(jié)點缝裁，但是在下一個p.casNext(null, newNode)失敗的情況下（意味著有一個其他的線程成功入隊了）胁塞，那么還是會在下一次loop中重新回到p = (p != t && t != (t = tail)) ? t : q;，并且這一次就是重新走到場景2压语；
public E poll() {
restartFromHead:
for (;;) { // loop
for (Node<E> h = head, p = h, q;;) {
E item = p.item;
if (item != null && p.casItem(item, null)) {
// 如果p的item不為null且cas成功就算是成功出隊
if (p != h) // 和入隊一樣啸罢，出隊也是允許head不是即時更新的
updateHead(h, ((q = p.next) != null) ? q : p);
return item;
}
// 走到這里意味著head的item為null，或者說其他線程出隊成功
// 而導(dǎo)致的cas失敗
else if ((q = p.next) == null) {
// 隊列已經(jīng)為空的了胎食，更新head節(jié)點并返回null
updateHead(h, p);
return null;
}
else if (p == q)
// q = p.next && p == q
// 意味著p和q指向的節(jié)點被移出了隊列
continue restartFromHead;
else
// 下一個元素不為null && p并不等于p.next
// p指向下一個出隊的元素
p = q;
}
}
}
同樣出隊的時候也是滯后更新head節(jié)點扰才，它只需要保證head節(jié)點一定可以通過succ()訪問到后繼節(jié)點就行了；
final void updateHead(Node<E> h, Node<E> p) {
// 通過CAS將head節(jié)點的值設(shè)置為下一個不為null的節(jié)點
if (h != p && casHead(h, p))
// 同時將節(jié)點的next指向自己
h.lazySetNext(h);
}
void lazySetNext(Node<E> val) {
UNSAFE.putOrderedObject(this, nextOffset, val);
}
可以看到并不是每一次出隊都會更新head節(jié)點厕怜，只有在步長大于1的時候才會移動head指針衩匣，同時把之前head節(jié)點的next域指向自己蕾总，將節(jié)點和鏈表之間的連接斷開；
UNSAFE.putOrderedObject方法的作用是優(yōu)化對volatile寫的開銷琅捏，因為為了保證volatile的可見性語義生百，在每個volatile寫操作后插入StoreLoad屏障，通常來說該屏障是需要昂貴的開銷才能完成柄延，而putOrderedObject的是使用StoreStore屏障蚀浆，使用的結(jié)果就是寫入數(shù)據(jù)可能并不會被其他線程馬上看到，通常是幾納秒后被其他線程看到搜吧，所以是叫lazySetNext市俊；
最后再回到offer方法的這個判斷情況
// q != null， q = p.next
else if (p == q)
// 如果p == q滤奈，那么意味著p的next指向的是自己
p = (t != (t = tail)) ? t : head;
// 可以翻譯成下面的代碼
Node<E> tmp = t;
t = tail;
if (tmp != t) {
// t不等于tail摆昧，意味著有新的節(jié)點入隊，重新指向tail節(jié)點
p = t;
} else {
// 當(dāng)前p指向的節(jié)點已經(jīng)被其他線程移除隊列蜒程，所以不能訪問后續(xù)的節(jié)點
// 將p指向head節(jié)點重新回到隊列上面
p = head;
}
如果p == q這個判斷條件成立绅你，那么意味著p的next域指向的是自己，這種情況只會在上面的poll()方法中的updateHead把節(jié)點移出隊列時才會把next域指向自己昭躺；所以說當(dāng)前的p節(jié)點實際上已經(jīng)脫離了隊列勇吊，那么就需要將其重新指向隊列中的某個節(jié)點；
