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

CAS的優(yōu)點

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

CAS的缺點

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

不變性

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

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

可變性

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

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

快照

snapshot是我自己的理解 因為對于多線程操作來說 當(dāng)前引用對象 如offer()中 t=tail中的t; p=t中的p; q=p.next中的q都是一個快照 他獲得一個對象的快照版本 然后在后續(xù)的操作中 使(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;;) {//獲取當(dāng)前尾節(jié)點 t=tail,p是真正的尾節(jié)點 p.next==null 
            Node q = p.next;
            if (q == null) {
                // p is last node 
                if (p.casNext(null, newNode)) {//方法1 CAS更新 自己想3個線程同時進(jìn)行這個操作
                    // 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 延遲更新尾節(jié)點 下面說為什么
                        casTail(t, newNode);  //方法3 成不成功無所謂 下面說
                    return true;
                }
                // Lost CAS race to another thread; re-read next
            }
            else if (p == q)// 方法4 學(xué)習(xí)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  //去找到真正的尾節(jié)點 此處和方法2 應(yīng)是相互輝映的存在
                // Check for tail updates after two hops.
                p = (p != t && t != (t = tail)) ? t : q; //方法5
        }
    }

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

多線程操作

第一種情況: 只有 offer()

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

同時執(zhí)行offer()(假設(shè)我們現(xiàn)在有3個線程)

不變性:永遠(yuǎn)只有一個線程CAS成功 并且總會成功一個

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

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

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

只有offer() 操作時

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

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

                              圖1                  

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

                 
                                 圖2                       

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

                                 圖3
                                 

Thread2 工作完成 退出循環(huán)

對于Thread3 因為執(zhí)行1方法失敗 進(jìn)入5方法 此時Thread3的tail快照t3

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

按圖3來翻譯

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

p=t2;//直接去當(dāng)前能獲取到的尾節(jié)點?。。?/p>

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

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

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

偶數(shù)次offer() 操作更新一次tail 單線程的環(huán)境下

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

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

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

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

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

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

當(dāng)?shù)?0個線程操作時 雖然它很可憐 一直排到最后 但是尾節(jié)點更新一下就越過了9階!!!(不太恰當(dāng)?shù)牡胤秸埓罄袀冎更c)?

ConcurrrntLinkedQueue 優(yōu)點

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

能抵達(dá)每一個相對于當(dāng)前快照來說最新的next節(jié)點

高并發(fā)時 tail 和 p 相互配合 盡力去離當(dāng)前尾節(jié)點 最近的地方

ConcurrentLinkedQueue 缺點

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

循環(huán)可能會帶來額外的資源開銷