成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

非阻塞隊(duì)列ConcurrentLinkedQueue與CAS算法應(yīng)用分析

Ali_ / 902人閱讀

摘要：是無(wú)阻塞隊(duì)列的一種實(shí)現(xiàn)，依賴與算法實(shí)現(xiàn)。這樣比從往后找更有效率出隊(duì)規(guī)則定義補(bǔ)充一項(xiàng)，也表示節(jié)點(diǎn)已經(jīng)被刪除參考方法。

ConcurrentLinkedQueue是無(wú)阻塞隊(duì)列的一種實(shí)現(xiàn)， 依賴與CAS算法實(shí)現(xiàn)。

入隊(duì)offer

if(q==null)當(dāng)前是尾節(jié)點(diǎn) -> CAS賦值tail.next = newNode， 成功就跳出循環(huán)

elseif(p == q)尾節(jié)點(diǎn)被移除 -> 從tail或head重新往后找

else不是尾節(jié)點(diǎn) -> 往next找

規(guī)則定義:

當(dāng)一個(gè)節(jié)點(diǎn)的next指向自身時(shí)， 表示節(jié)點(diǎn)已經(jīng)被移除, 注釋中還會(huì)強(qiáng)調(diào)這一點(diǎn)。

完整代碼(JDK8): 
/**
 * Inserts the specified element at the tail of this queue.
 * As the queue is unbounded, this method will never return {@code false}.
 *
 * @return {@code true} (as specified by {@link Queue#offer})
 * @throws NullPointerException if the specified element is null
 */
/*
* 變量說(shuō)明：
*   成員變量: 
*       head: 首節(jié)點(diǎn)
*       tail: 尾節(jié)點(diǎn), 不一定指向末尾， 兩次入隊(duì)才更新一次
*   局部變量
*         t= tail; //保存循環(huán)開(kāi)始時(shí), 當(dāng)時(shí)的tail值
*         p= t; // 每次查找的起始位置， 可能指向首節(jié)點(diǎn)head或者臨時(shí)尾節(jié)點(diǎn)t
*         q= p.next; // 每次循環(huán)下一個(gè)節(jié)點(diǎn)
*        newNode= new Node; // 新節(jié)點(diǎn)
*
*
* 重要概念:
*     當(dāng)p = p.next時(shí)， 表示節(jié)點(diǎn)已經(jīng)被移除
*/
public boolean offer(E e) {
    checkNotNull(e);
    final Node newNode = new Node(e);

    for (Node t = tail, p = t;;) {
        Node q = p.next;
        if (q == null) {    // 情況1：  p是尾節(jié)點(diǎn)
            // p is last node
            // p是尾節(jié)點(diǎn)就直接將新節(jié)點(diǎn)放入末尾
            if (p.casNext(null, newNode)) {
                // 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 // 一次跳兩個(gè)節(jié)點(diǎn)， 即插入兩次， tail更新一次
                    casTail(t, newNode);  // Failure is OK. // 失敗也無(wú)妨， 說(shuō)明被別的線程更新了
                return true;  // 退出循環(huán)
            }
            // Lost CAS race to another thread; re-read next
        }
        else if (p == q)  // 情況2：  p節(jié)點(diǎn)被刪除了
            // 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.
            // 保存的節(jié)點(diǎn)p、t都已經(jīng)失效了，這時(shí)需要重新檢索，重新檢索的起始位置有兩種情況
            //     1.1. 如果tail==t,表示tail也是失效的, 那么從head開(kāi)始找
            //     1.2. 否則tail就是被其他線程更新了， 可以又試著從tail找
            p = (t != (t = tail)) ? t : head;
        else             // 情況3：   沿著p往下找
            // Check for tail updates after two hops.
            // 這段簡(jiǎn)單看作p = q就好理解了,  這么寫(xiě)是為了提高效率：
            //     1. 情況二中p可能指向了head(由于tail節(jié)點(diǎn)失效導(dǎo)致的)
            //     2. 現(xiàn)在tail可能被其他線程更新，也許重新指向了隊(duì)尾
            //     3. 如果是， 嘗試則從隊(duì)尾開(kāi)始找， 以減少迭代次數(shù)
            p = (p != t && t != (t = tail)) ? t : q;
    }
}
這兩段代碼看了很久， 特別記錄下：

情況2中的p = (t != (t = tail)) ? t : head;
(t != (t = tail))可以分三步來(lái)看

  1.1. 首先取出t
  1.2. 將tail賦值給t
  1.3. 將先前取出的t與更新后的t比較

情況3中p = (p != t && t != (t = tail)) ? t : q;

首先:  p != t： 這種情況只有可能發(fā)生在執(zhí)行了情況2后  
現(xiàn)狀： 這時(shí)p指向head或者中間的元素, t指向一個(gè)被刪除了的節(jié)點(diǎn)  
那么如果tail被其他線程更新了， 我們可以將t重新指向tail, p指向t, 就像剛進(jìn)循環(huán)一樣， 從尾節(jié)點(diǎn)開(kāi)始檢索。
這樣比從head往后找更有效率

出隊(duì)poll 規(guī)則定義:

補(bǔ)充一項(xiàng)， item==null,也表示節(jié)點(diǎn)已經(jīng)被刪除(參考remove方法)。

/**
* updateHead
*   
*/
public E poll() {
    restartFromHead:
    for (;;) {
        for (Node h = head, p = h, q;;) {
            E item = p.item;

            if (item != null && p.casItem(item, null)) {
                // Successful CAS is the linearization point
                // for item to be removed from this queue.
                if (p != h) // hop two nodes at a time
                    updateHead(h, ((q = p.next) != null) ? q : p);
                return item;
            }
            else if ((q = p.next) == null) {
                updateHead(h, p);
                return null;
            }
            else if (p == q)
                continue restartFromHead;
            else
                p = q;
        }
    }
}

/**
 * Tries to CAS head to p. If successful, repoint old head to itself
 * as sentinel for succ(), below.
 */
final void updateHead(Node h, Node p) {
    if (h != p && casHead(h, p))
        h.lazySetNext(h);
}
出隊(duì)設(shè)值操作：

先更新head, 再將舊head的next指向自己

Note: CAS算法實(shí)現(xiàn)依靠Unsafe.compareAndSwapObject實(shí)現(xiàn)

UNSAFE.compareAndSwapObject(對(duì)象, 字段偏移量, 當(dāng)前值, 新值)

可以為對(duì)象中的某個(gè)字段實(shí)現(xiàn)CAS操作
lazySet依賴UNSAFE.putOrderedObject實(shí)現(xiàn)

UNSAFE.putOrderedObject(對(duì)象, 字段偏移量, 新值)

這個(gè)只能用在volatile字段上  
個(gè)人理解： volatile的設(shè)值會(huì)導(dǎo)致本地緩存失效， 那么需要重新從主存讀取， 使用這個(gè)方法可以使寄存器緩存依舊有效， 不必急于從主存取值。   
使用目的： 移除節(jié)點(diǎn)時(shí)， 需要更新節(jié)點(diǎn)的next指向自身， 但現(xiàn)在next指向的數(shù)據(jù)實(shí)際是有效的； 高并發(fā)情況下，如果offser方法已經(jīng)緩存了這個(gè)next值， 直接設(shè)置next會(huì)導(dǎo)致緩存行失效, CPU需要重新讀取next;  而使用putOrderedObject可以讓offser從這個(gè)next繼續(xù)檢索

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/72604.html

相關(guān)文章

  • 非阻塞同步算法實(shí)戰(zhàn)（一）：ConcurrentLinkedQueue

    摘要：注意這里指的不是當(dāng)次而是之后，所以如果我們使用隊(duì)列的方法返回，就知道隊(duì)列是否為空，但是不知道之后是否為空，并且，當(dāng)關(guān)注的操作發(fā)生時(shí)，在插入或取出操作的返回值里告知此信息，來(lái)指導(dǎo)是否繼續(xù)注冊(cè)寫(xiě)操作。 前言 本文寫(xiě)給對(duì)ConcurrentLinkedQueue的實(shí)現(xiàn)和非阻塞同步算法的實(shí)現(xiàn)原理有一定了解，但缺少實(shí)踐經(jīng)驗(yàn)的朋友，文中包括了實(shí)戰(zhàn)中的嘗試、所走的彎路，經(jīng)驗(yàn)和教訓(xùn)。 背景介紹 ...

    EscapedDog 評(píng)論0 收藏0

  • 通俗易懂，JDK 并發(fā)容器總結(jié)

    摘要：線程安全的線程安全的，在讀多寫(xiě)少的場(chǎng)合性能非常好，遠(yuǎn)遠(yuǎn)好于高效的并發(fā)隊(duì)列，使用鏈表實(shí)現(xiàn)。這樣帶來(lái)的好處是在高并發(fā)的情況下，你會(huì)需要一個(gè)全局鎖來(lái)保證整個(gè)平衡樹(shù)的線程安全。 該文已加入開(kāi)源項(xiàng)目：JavaGuide（一份涵蓋大部分Java程序員所需要掌握的核心知識(shí)的文檔類項(xiàng)目，Star 數(shù)接近 14 k）。地址:https://github.com/Snailclimb... 一 JDK ...

    curlyCheng 評(píng)論0 收藏0

  • 非阻塞同步算法實(shí)戰(zhàn)（二）：BoundlessCyclicBarrier

    摘要：如果停止了版本更新，可使用方法來(lái)解除所有因而阻塞的線程，包括指定版本號(hào)的。如果自己維護(hù)版本號(hào)，則應(yīng)該保證遞增。 前言 相比上一篇而言，本文不需要太多的準(zhǔn)備知識(shí)，但技巧性更強(qiáng)一些。因?yàn)榉治?、設(shè)計(jì)的過(guò)程比較復(fù)雜繁瑣，也限于篇幅，所以，主要展示如何解決這些需求，和講解代碼。另外，所講的內(nèi)容也是后一篇實(shí)戰(zhàn)中需要用到的一個(gè)工具類。 需求介紹 我需要編寫(xiě)一個(gè)同步工具，它需要提供這樣幾個(gè)方法：...

    yintaolaowanzi 評(píng)論0 收藏0

  • Java并發(fā)

    摘要：對(duì)象改變條件對(duì)象當(dāng)前線程要等待線程終止之后才能從返回。如果線程在上的操作中被中斷，通道會(huì)被關(guān)閉，線程的中斷狀態(tài)會(huì)被設(shè)置，并得到一個(gè)。清除線程的中斷狀態(tài)。非公平性鎖雖然可能造成饑餓，但極少的線程切換，保證其更大的吞吐量。 聲明：Java并發(fā)的內(nèi)容是自己閱讀《Java并發(fā)編程實(shí)戰(zhàn)》和《Java并發(fā)編程的藝術(shù)》整理來(lái)的。 showImg(https://segmentfault.com/im...

    SKYZACK 評(píng)論0 收藏0

  • ConcurrentLinkedQueue使用實(shí)例

    摘要：序是一個(gè)基于鏈接節(jié)點(diǎn)的無(wú)界線程安全隊(duì)列，它采用先進(jìn)先出的規(guī)則對(duì)節(jié)點(diǎn)進(jìn)行排序，當(dāng)我們添加一個(gè)元素的時(shí)候，它會(huì)添加到隊(duì)列的尾部，當(dāng)我們獲取一個(gè)元素時(shí)，它會(huì)返回隊(duì)列頭部的元素。的模型，默認(rèn)的是用這個(gè)來(lái)實(shí)現(xiàn)的。 序 ConcurrentLinkedQueue是一個(gè)基于鏈接節(jié)點(diǎn)的無(wú)界線程安全隊(duì)列，它采用先進(jìn)先出的規(guī)則對(duì)節(jié)點(diǎn)進(jìn)行排序，當(dāng)我們添加一個(gè)元素的時(shí)候，它會(huì)添加到隊(duì)列的尾部，當(dāng)我們獲取一個(gè)元...

    Raaabbit 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<