在并發(fā)編程中我們有時候需要使用線程安全的隊列。如果我們要實現一個線程安全的隊列有兩種實現方式一種是使用阻塞算法，另一種是使用非阻塞算法。使用阻塞算法的隊列可以用一個鎖（入隊和出隊用同一把鎖）或兩個鎖（入隊和出隊用不同的鎖）等方式來實現，而非阻塞的實現方式則可以使用循環(huán)CAS的方式來實現，下面我們一起來研究下Doug Lea是如何使用非阻塞的方式來實現線程安全隊列ConcurrentLinkedQueue的。
ConcurrentLinkedQueue是一個基于鏈接節(jié)點的無界線程安全隊列，它采用先進先出的規(guī)則對節(jié)點進行排序，當我們添加一個元素的時候，它會添加到隊列的尾部，當我們獲取一個元素時，它會返回隊列頭部的元素。它采用了“wait－free”算法來實現，該算法在Michael & Scott算法上進行了一些修改。
入隊
上圖所示的元素添加過程如下：
- 添加元素1：隊列更新head節(jié)點的next節(jié)點為元素1節(jié)點。又因為tail節(jié)點默認情況下等于head節(jié)點，所以它們的next節(jié)點都指向元素1節(jié)點。
- 添加元素2：隊列首先設置元素1節(jié)點的next節(jié)點為元素2節(jié)點，然后更新tail節(jié)點指向元素2節(jié)點。
- 添加元素3：設置tail節(jié)點的next節(jié)點為元素3節(jié)點。
- 添加元素4：設置元素3的next節(jié)點為元素4節(jié)點，然后將tail節(jié)點指向元素4節(jié)點。
入隊操作主要做兩件事情，第一是將入隊節(jié)點設置成當前隊列尾節(jié)點的下一個節(jié)點。第二是更新tail節(jié)點，如果tail節(jié)點的next節(jié)點不為空，則將入隊節(jié)點設置成tail節(jié)點，如果tail節(jié)點的next節(jié)點為空，則將入隊節(jié)點設置成tail的next節(jié)點，所以tail節(jié)點不總是尾節(jié)點，理解這一點很重要。
上面的分析讓我們從單線程入隊的角度來理解入隊過程，但是多個線程同時進行入隊情況就變得更加復雜，因為可能會出現其他線程插隊的情況。如果有一個線程正在入隊，那么它必須先獲取尾節(jié)點，然后設置尾節(jié)點的下一個節(jié)點為入隊節(jié)點，但這時可能有另外一個線程插隊了，那么隊列的尾節(jié)點就會發(fā)生變化，這時當前線程要暫停入隊操作，然后重新獲取尾節(jié)點。
從源代碼角度來看整個入隊過程主要做兩件事情：
- 第一是定位出尾節(jié)點
- 第二是使用CAS算法能將入隊節(jié)點設置成尾節(jié)點的next節(jié)點，
如不成功則重試。
ConcurrentLinkedQueue的入隊操作整體邏輯如下圖所示：
非阻塞卻線程安全的原因
觀察入隊和出隊的源碼可以發(fā)現，無論入隊還是出隊，都是在死循環(huán)中進行的，也就是說，當一個線程調用了入隊、出隊操作時，會嘗試獲取鏈表的tail、head結點進行插入和刪除操作，而插入和刪除是通過CAS操作實現的，而CAS具有原子性。故此，如果有其他任何一個線程成功執(zhí)行了插入、刪除都會改變tail/head結點，那么當前線程的插入和刪除操作就會失敗，則通過循環(huán)再次定位tail、head結點位置進行插入、刪除，直到成功為止。也就是說，ConcurrentLinkedQueue的線程安全是通過其插入、刪除時采取CAS操作來保證的。不會出現同一個tail結點的next指針被多個同時插入的結點所搶奪的情況出現。
