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

CAS的優(yōu)點(diǎn)

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

CAS的缺點(diǎn)

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

不變性

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

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

可變性

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

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

快照

snapshot是我自己的理解 因?yàn)閷?duì)于多線程操作來說 當(dāng)前引用對(duì)象 如offer()中 t=tail中的t; p=t中的p; q=p.next中的q都是一個(gè)快照 他獲得一個(gè)對(duì)象的快照版本 然后在后續(xù)的操作中 使(t!=(t=tail))這樣操作有意義

offer()入隊(duì)

poll() 出隊(duì)

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

        for (Node t = tail, p = t;;) {//獲取當(dāng)前尾節(jié)點(diǎn) t=tail,p是真正的尾節(jié)點(diǎn) p.next==null 
            Node q = p.next;
            if (q == null) {
                // p is last node 
                if (p.casNext(null, newNode)) {//方法1 CAS更新 自己想3個(gè)線程同時(shí)進(jìn)行這個(gè)操作
                    // 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é)點(diǎn) 下面說為什么
                        casTail(t, newNode);  //方法3 成不成功無(wú)所謂 下面說
                    return true;
                }
                // Lost CAS race to another thread; re-read next
            }
            else if (p == q)// 方法4 學(xué)習(xí)offer方法時(shí) 可以暫時(shí)放棄這一步
                // 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é)點(diǎn) 此處和方法2 應(yīng)是相互輝映的存在
                // Check for tail updates after two hops.
                p = (p != t && t != (t = tail)) ? t : q; //方法5
        }
    }

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

多線程操作

第一種情況: 只有 offer()

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

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

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

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

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

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

只有offer() 操作時(shí)

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()

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

                              圖1                  

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

                 
                                 圖2                       

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

                                 圖3
                                 

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

對(duì)于Thread3 因?yàn)閳?zhí)行1方法失敗 進(jìn)入5方法 此時(shí)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é)點(diǎn)?。。?/p>

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

tail和head都是 延遲更新的 但是tail更新在head更新后面 因?yàn)榉椒?中 需要依賴head節(jié)點(diǎn) 去找每一個(gè)存活的節(jié)點(diǎn)

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

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

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

Doug Lead老神仙的CAS 我這個(gè)菜鳥猜測(cè) 能不用CAS 就盡量不用 因?yàn)镃AS存在競(jìng)爭(zhēng) 提供以最少次數(shù)的更新達(dá)到最終正確的效果

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

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

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

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

當(dāng)?shù)?0個(gè)線程操作時(shí) 雖然它很可憐 一直排到最后 但是尾節(jié)點(diǎn)更新一下就越過了9階!!!(不太恰當(dāng)?shù)牡胤秸?qǐng)大佬們指點(diǎn))?

ConcurrrntLinkedQueue 優(yōu)點(diǎn)

能躍過一整段因?yàn)槎嗑€程在極短時(shí)間內(nèi)offer()插入的節(jié)點(diǎn) 直接去尾節(jié)點(diǎn) 直接跨過去

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

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

ConcurrentLinkedQueue 缺點(diǎn)

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

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