国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

非阻塞隊列ConcurrentLinkedQueue與CAS算法應用分析

Ali_ / 894人閱讀

摘要:是無阻塞隊列的一種實現,依賴與算法實現。這樣比從往后找更有效率出隊規則定義補充一項,也表示節點已經被刪除參考方法。

ConcurrentLinkedQueue是無阻塞隊列的一種實現, 依賴與CAS算法實現。

入隊offer

if(q==null)當前是尾節點 -> CAS賦值tail.next = newNode, 成功就跳出循環

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

else不是尾節點 -> 往next找

規則定義:

當一個節點的next指向自身時, 表示節點已經被移除, 注釋中還會強調這一點。

完整代碼(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
 */
/*
* 變量說明:
*   成員變量: 
*       head: 首節點
*       tail: 尾節點, 不一定指向末尾, 兩次入隊才更新一次
*   局部變量
*         t= tail; //保存循環開始時, 當時的tail值
*         p= t; // 每次查找的起始位置, 可能指向首節點head或者臨時尾節點t
*         q= p.next; // 每次循環下一個節點
*        newNode= new Node; // 新節點
*
*
* 重要概念:
*     當p = p.next時, 表示節點已經被移除
*/
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是尾節點
            // p is last node
            // p是尾節點就直接將新節點放入末尾
            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 // 一次跳兩個節點, 即插入兩次, tail更新一次
                    casTail(t, newNode);  // Failure is OK. // 失敗也無妨, 說明被別的線程更新了
                return true;  // 退出循環
            }
            // Lost CAS race to another thread; re-read next
        }
        else if (p == q)  // 情況2:  p節點被刪除了
            // 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都已經失效了,這時需要重新檢索,重新檢索的起始位置有兩種情況
            //     1.1. 如果tail==t,表示tail也是失效的, 那么從head開始找
            //     1.2. 否則tail就是被其他線程更新了, 可以又試著從tail找
            p = (t != (t = tail)) ? t : head;
        else             // 情況3:   沿著p往下找
            // Check for tail updates after two hops.
            // 這段簡單看作p = q就好理解了,  這么寫是為了提高效率:
            //     1. 情況二中p可能指向了head(由于tail節點失效導致的)
            //     2. 現在tail可能被其他線程更新,也許重新指向了隊尾
            //     3. 如果是, 嘗試則從隊尾開始找, 以減少迭代次數
            p = (p != t && t != (t = tail)) ? t : q;
    }
}
這兩段代碼看了很久, 特別記錄下:

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

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

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

首先:  p != t: 這種情況只有可能發生在執行了情況2后  
現狀: 這時p指向head或者中間的元素, t指向一個被刪除了的節點
那么如果tail被其他線程更新了, 我們可以將t重新指向tail, p指向t, 就像剛進循環一樣, 從尾節點開始檢索。
這樣比從head往后找更有效率

出隊poll 規則定義:

補充一項, item==null,也表示節點已經被刪除(參考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);
}
出隊設值操作:

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

Note: CAS算法實現依靠Unsafe.compareAndSwapObject實現

UNSAFE.compareAndSwapObject(對象, 字段偏移量, 當前值, 新值)

可以為對象中的某個字段實現CAS操作
lazySet依賴UNSAFE.putOrderedObject實現

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

這個只能用在volatile字段上  
個人理解: volatile的設值會導致本地緩存失效, 那么需要重新從主存讀取, 使用這個方法可以使寄存器緩存依舊有效, 不必急于從主存取值。
使用目的: 移除節點時, 需要更新節點的next指向自身, 但現在next指向的數據實際是有效的; 高并發情況下,如果offser方法已經緩存了這個next值, 直接設置next會導致緩存行失效, CPU需要重新讀取next; 而使用putOrderedObject可以讓offser從這個next繼續檢索

文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。

轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/72604.html

相關文章

  • 阻塞同步算法實戰(一):ConcurrentLinkedQueue

    摘要:注意這里指的不是當次而是之后,所以如果我們使用隊列的方法返回,就知道隊列是否為空,但是不知道之后是否為空,并且,當關注的操作發生時,在插入或取出操作的返回值里告知此信息,來指導是否繼續注冊寫操作。 前言 本文寫給對ConcurrentLinkedQueue的實現和非阻塞同步算法的實現原理有一定了解,但缺少實踐經驗的朋友,文中包括了實戰中的嘗試、所走的彎路,經驗和教訓。 背景介紹 ...

    EscapedDog 評論0 收藏0
  • 通俗易懂,JDK 并發容器總結

    摘要:線程安全的線程安全的,在讀多寫少的場合性能非常好,遠遠好于高效的并發隊列,使用鏈表實現。這樣帶來的好處是在高并發的情況下,你會需要一個全局鎖來保證整個平衡樹的線程安全。 該文已加入開源項目:JavaGuide(一份涵蓋大部分Java程序員所需要掌握的核心知識的文檔類項目,Star 數接近 14 k)。地址:https://github.com/Snailclimb... 一 JDK ...

    curlyCheng 評論0 收藏0
  • 阻塞同步算法實戰(二):BoundlessCyclicBarrier

    摘要:如果停止了版本更新,可使用方法來解除所有因而阻塞的線程,包括指定版本號的。如果自己維護版本號,則應該保證遞增。 前言 相比上一篇而言,本文不需要太多的準備知識,但技巧性更強一些。因為分析、設計的過程比較復雜繁瑣,也限于篇幅,所以,主要展示如何解決這些需求,和講解代碼。另外,所講的內容也是后一篇實戰中需要用到的一個工具類。 需求介紹 我需要編寫一個同步工具,它需要提供這樣幾個方法:...

    yintaolaowanzi 評論0 收藏0
  • Java并發

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

    SKYZACK 評論0 收藏0
  • ConcurrentLinkedQueue使用實例

    摘要:序是一個基于鏈接節點的無界線程安全隊列,它采用先進先出的規則對節點進行排序,當我們添加一個元素的時候,它會添加到隊列的尾部,當我們獲取一個元素時,它會返回隊列頭部的元素。的模型,默認的是用這個來實現的。 序 ConcurrentLinkedQueue是一個基于鏈接節點的無界線程安全隊列,它采用先進先出的規則對節點進行排序,當我們添加一個元素的時候,它會添加到隊列的尾部,當我們獲取一個元...

    Raaabbit 評論0 收藏0

發表評論

0條評論

Ali_

|高級講師

TA的文章

閱讀更多
最新活動
閱讀需要支付1元查看
<