摘要：上集算法實現的優點當一個線程執行任務失敗不影響其他線程的進行最大限度的利用資源能提高程序的伸縮性伸縮性不修改任何代碼升級硬件就能帶來性能上的提高升級硬件帶來的性能提高明顯就是伸縮性良好的缺點代碼復雜影響閱讀性剛開始看的時候沒有正確的思路理解

CAS的優點

當一個線程執行任務失敗不影響其他線程的進行 最大限度的利用CPU資源 能提高程序的伸縮性 伸縮性:不修改任何代碼 升級硬件就能帶來性能上的提高 升級硬件帶來的性能提高明顯 就是伸縮性良好

CAS的缺點

代碼復雜 影響閱讀性 剛開始看ConcurrentLinkedQueue的時候 沒有正確的思路,理解起來會比較費勁 我推薦直接用多線程同時執行的方式去理解 這樣會比較好

不變性

所有item不為null的節點都能從head頭節點開始通過succ()方法訪問到

head!=null 只要隊列有值 保證真實的head永不為null head哪怕會自引用 遲早也會解除這種假狀態

可變性

heatd.item 可能為null也可能不為null 因為cas活鎖操作 每一行代碼執行都不影響其他線程的訪問相同的代碼塊

tail尾節點的更新是滯后于head的 個人理解 在offer中 尾節點掉隊后 通過head節點 (不變性1的保證) 成功訪問最后一個p.next=null的節點

快照

snapshot是我自己的理解 因為對于多線程操作來說 當前引用對象 如offer()中 t=tail中的t; p=t中的p; q=p.next中的q都是一個快照 他獲得一個對象的快照版本 然后在后續的操作中 使(t!=(t=tail))這樣操作有意義

offer()入隊

poll() 出隊

public boolean offer(E e) {
        checkNotNull(e); //NullPointException檢查   
        final Node newNode = new Node(e); //包裝成一個Node對象

        for (Node t = tail, p = t;;) {//獲取當前尾節點 t=tail,p是真正的尾節點 p.next==null 
            Node q = p.next;
            if (q == null) {
                // p is last node 
                if (p.casNext(null, newNode)) {//方法1 CAS更新 自己想3個線程同時進行這個操作
                    // Successful CAS is the linearization point
                    // for e to become an element of this queue,
                    // and for newNode to become "live".
                    if (p != t) // hop two nodes at a time //方法2 延遲更新尾節點 下面說為什么
                        casTail(t, newNode);  //方法3 成不成功無所謂 下面說
                    return true;
                }
                // Lost CAS race to another thread; re-read next
            }
            else if (p == q)// 方法4 學習offer方法時 可以暫時放棄這一步
                // 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.
                p = (t != (t = tail)) ? t : head;
            else  //去找到真正的尾節點 此處和方法2 應是相互輝映的存在
                // Check for tail updates after two hops.
                p = (p != t && t != (t = tail)) ? t : q; //方法5
        }
    }

自頂向下 思考CAS中可能出現的情況 CAS是活鎖 所謂活鎖即是每一行代碼運行時 允許其他線程訪問相同的代碼塊 成功與失敗并存 衍生了更多的條件判斷 本人覺得CAS方法都應該從這個方法去理解 再自己畫畫時序圖 (注意:理解offer()時,先把方法4排除，因為4方法出現自引用的情況 只有offer()和poll()交替執行時會出現 本文只介紹第一種情況)

多線程操作

第一種情況: 只有 offer()

第二種情況: offer()和 poll()方法交替執行

同時執行offer()(假設我們現在有3個線程)

不變性:永遠只有一個線程CAS成功 并且總會成功一個

循環次數分析:Thread1 成功 循環一次退出 Thread2失敗 再循環一次成功 Thread3失敗 再循環兩次成功 如果有n個線程同時執行 offer() 執行次數 最大為n次 最少為1次

方法5中三目表達式解析: p=condition?result1:result2 我先說一下這里的意義 滿足result1的場景為 :獲取尾節點tail的快照已經過時了(其他線程更新了新的尾節點tail) 直接跳轉到當前獲得的最新尾節點的地方 滿足result2的場景為:多線程同時操作offer() 執行1方法CAS成功后 未更新尾節點(未執行3方法:兩種原因 1是未滿足前置條件if判斷 2是CAS更新失敗) 直接找next節點

方法2與方法5 是整個offer() 操作的點睛之筆 下面解釋

只有offer() 操作時

Thread 1執行完1方法成功 還未執行2方法 Thread2和Thread3進入5方法 ,也就是說Thread2和Thread3執行5方法發生在Thread1執行2方法之前 Thread2 and Thread3 invoke method5() before Thread1 invoke method2()

此時 Thread2.p =q,Thread3.p=q, 因為p==t成立 時序圖如下,然后Thread1執行方法2 p==t 不執行tail尾節點的更新操作 由此可知 尾節點是延遲更新 一切為了更高效～～～

                              圖1                  

Thread 2 與 Thread3 此時再次執行 1 方法 見圖1 他們此時的q.next==null 我們規定Thread2 CAS成功 Thread3失敗了 成功后的時序圖如下 我們假設 Thread3 invoke method5() after Thread2 invoke method2() Thread2執行方法2 在 Thread3執行方法5之前

                 
                                 圖2                       

對于Thread2 進入2方法 p!=t 滿足 執行 casTail(t, newNode) 更新尾節點的快照 如下圖

                                 圖3
                                 

Thread2 工作完成 退出循環

對于Thread3 因為執行1方法失敗 進入5方法 此時Thread3的tail快照t3

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

按圖3來翻譯

p=(p!=t3&&t3!=(t3=t2))?t2:q;

p=t2;//直接去當前能獲取到的尾節點！！！

到這里 offer() 方法解決完成

tail和head都是 延遲更新的 但是tail更新在head更新后面 因為方法4中 需要依賴head節點 去找每一個存活的節點

前面的敘述中 可以看到 offer() 方法內 核心操作 就是 p=condition?result1:result2

偶數次offer() 操作更新一次tail 單線程的環境下

Michael-Scott隊列 每次操作 都需要判斷是否需要推動尾節點 采取CAS的操作 優點也是缺點

Doug Lead老神仙的CAS 我這個菜鳥猜測 能不用CAS 就盡量不用 因為CAS存在競爭 提供以最少次數的更新達到最終正確的效果

我們把offer()中的整個行為想象為跳臺階 result1的形式就像是 武俠小說中的越階戰斗！！！result2的形式就是一步一個腳印 每次平穩地去下一個臺階

我們想象一下 offer()最優的情況 10個線程同時offer()

每一個執行1方法成功的線程都沒有(執行2方法或則執行3方法失敗) 沒關系 尾節點的更新終會成功

每一個失敗的線程都是去當前節點的next節點 p.next進行插入操作 在第9個線程(相當于我們上文中的線程2)

當第10個線程操作時 雖然它很可憐 一直排到最后 但是尾節點更新一下就越過了9階!!!(不太恰當的地方請大佬們指點)?

ConcurrrntLinkedQueue 優點

能躍過一整段因為多線程在極短時間內offer()插入的節點 直接去尾節點 直接跨過去

能抵達每一個相對于當前快照來說最新的next節點

高并發時 tail 和 p 相互配合 盡力去離當前尾節點 最近的地方

ConcurrentLinkedQueue 缺點

CAS操作 雖然總會成功 但是競爭效率如果很低 不如用同步鎖 采用CAS編寫并發代碼 都是大佬級別 難度高 不接地氣(嘿嘿)

循環可能會帶來額外的資源開銷