LinkedList怀樟、ConcurrentLinkedQueue功偿、LinkedBlockingQueue對(duì)比分析

寫這篇文章源于我經(jīng)歷過(guò)的一次生產(chǎn)事故盆佣,在某家公司的時(shí)候,有個(gè)服務(wù)會(huì)收集業(yè)務(wù)系統(tǒng)的日志械荷,此服務(wù)的開(kāi)發(fā)人員在給業(yè)務(wù)系統(tǒng)的sdk中就因?yàn)槭褂昧薒inkedList共耍,又沒(méi)有做并發(fā)控制,就造成了此服務(wù)經(jīng)常不能正常收集到業(yè)務(wù)系統(tǒng)的日志(丟日志以及日志上報(bào)的線程停止運(yùn)行)吨瞎”远担看一下add()方法的源碼,我們就可以知道原因了:

public boolean add(E e) {
    linkLast(e);//調(diào)用linkLast颤诀,在隊(duì)列尾部添加元素
    return true;
}
 
void linkLast(E e) {
    final Node<E> l = last;
    final Node<E> newNode = new Node<>(l, e, null);
    last = newNode;
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    size++;//多線程情況下字旭,如果業(yè)務(wù)系統(tǒng)沒(méi)做并發(fā)控制,size的數(shù)量會(huì)遠(yuǎn)遠(yuǎn)大于實(shí)際元素的數(shù)量
    modCount++;
}

demo  Lesson2LinkedListThreads 展示了在多線程且沒(méi)有做并發(fā)控制的環(huán)境下崖叫,size的值遠(yuǎn)遠(yuǎn)大于了隊(duì)列的實(shí)際值遗淳,100個(gè)線程,每個(gè)添加1000個(gè)元素心傀,最后實(shí)際只加進(jìn)去2030個(gè)元素:
List的變量size值為:88371
第2031個(gè)元素取出為null
解決方案屈暗,使用鎖或者使用ConcurrentLinkedQueue、LinkedBlockingQueue等支持添加元素為原子操作的隊(duì)列脂男。
上一節(jié)我們已經(jīng)分析過(guò)LinkedBlockingQueue的put等方法的源碼养叛,是使用ReentrantLock來(lái)實(shí)現(xiàn)的添加元素原子操作。我們?cè)俸?jiǎn)單看一下高并發(fā)queue的add和offer()方法宰翅,方法中使用了CAS來(lái)實(shí)現(xiàn)的無(wú)鎖的原子操作:

public boolean add(E e) {
     return offer(e);
   }

public boolean offer(E e) {
        checkNotNull(e);
        final Node<E> newNode = new Node<E>(e);
 
        for (Node<E> t = tail, p = t;;) {
            Node<E> q = p.next;
            if (q == null) {
                // p is last node
                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
                        casTail(t, newNode);  // Failure is OK.
                    return true;
                }
                // Lost CAS race to another thread; re-read next
            }
            else if (p == q)
                // 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
                // Check for tail updates after two hops.
                p = (p != t && t != (t = tail)) ? t : q;
        }
    }

接下來(lái)弃甥,我們?cè)倮酶卟l(fā)queue對(duì)上面的demo進(jìn)行改造,大家只要改變demo中的內(nèi)容汁讼,講下面兩行的注釋內(nèi)容顛倒淆攻,即可發(fā)現(xiàn)沒(méi)有丟失任何的元素:

  public static LinkedList list = new LinkedList();
  //public static ConcurrentLinkedQueue list = new ConcurrentLinkedQueue();

 再看一下高性能queue的poll()方法肮之,才覺(jué)得NB,取元素的方法也用CAS實(shí)現(xiàn)了原子操作卜录,因此在實(shí)際使用的過(guò)程中戈擒,當(dāng)我們?cè)诓荒敲丛谝庠靥幚眄樞虻那闆r下,隊(duì)列元素的消費(fèi)者艰毒,完全可以是多個(gè)筐高,不會(huì)丟任何數(shù)據(jù):
public E poll() {
        restartFromHead:
        for (;;) {
            for (Node<E> 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;
            }
        }
    }
關(guān)于ConcurrentLinkedQueue和LinkedBlockingQueue:
1.LinkedBlockingQueue是使用鎖機(jī)制,ConcurrentLinkedQueue是使用CAS算法丑瞧,雖然LinkedBlockingQueue的底層獲取鎖也是使用的CAS算法
2.關(guān)于取元素柑土,ConcurrentLinkedQueue不支持阻塞去取元素LinkedBlockingQueue支持阻塞的take()方法,如若大家需要 
  ConcurrentLinkedQueue的消費(fèi)者產(chǎn)生阻塞效果绊汹,需要自行實(shí)現(xiàn)
3.關(guān)于插入元素的性能稽屏,從字面上和代碼簡(jiǎn)單的分析來(lái)看ConcurrentLinkedQueue肯定是最快的,但是這個(gè)也要看具體的測(cè)試場(chǎng)景西乖,我做了兩個(gè)簡(jiǎn)單的demo做測(cè)試狐榔,測(cè)試的結(jié)果如下,兩個(gè)的性能差不多获雕,但在實(shí)際的使用過(guò)程中薄腻,尤其在多cpu的服務(wù)器上,有鎖和無(wú)鎖的差距便體現(xiàn)出來(lái)了届案,ConcurrentLinkedQueue會(huì)比LinkedBlockingQueue快很多:

demo Lesson2ConcurrentLinkedQueuePerform:在使用ConcurrentLinkedQueue的情況下100個(gè)線程循環(huán)增加的元素?cái)?shù)為:33828193

demo Lesson2LinkedBlockingQueuePerform:在使用LinkedBlockingQueue的情況下100個(gè)線程循環(huán)增加的元素?cái)?shù)為:33827382

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末庵楷,一起剝皮案震驚了整個(gè)濱河市,隨后出現(xiàn)的幾起案子楣颠,更是在濱河造成了極大的恐慌尽纽,老刑警劉巖,帶你破解...
    沈念sama閱讀 222,946評(píng)論 6 518
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件童漩,死亡現(xiàn)場(chǎng)離奇詭異弄贿,居然都是意外死亡,警方通過(guò)查閱死者的電腦和手機(jī)睁冬,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,336評(píng)論 3 399
  • 文/潘曉璐 我一進(jìn)店門挎春,熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái),“玉大人豆拨,你說(shuō)我怎么就攤上這事直奋。” “怎么了施禾?”我有些...
    開(kāi)封第一講書人閱讀 169,716評(píng)論 0 364
  • 文/不壞的土叔 我叫張陵脚线,是天一觀的道長(zhǎng)。 經(jīng)常有香客問(wèn)我弥搞,道長(zhǎng)邮绿,這世上最難降的妖魔是什么渠旁? 我笑而不...
    開(kāi)封第一講書人閱讀 60,222評(píng)論 1 300
  • 正文 為了忘掉前任,我火速辦了婚禮船逮,結(jié)果婚禮上顾腊,老公的妹妹穿的比我還像新娘。我一直安慰自己挖胃,他們只是感情好杂靶,可當(dāng)我...
    茶點(diǎn)故事閱讀 69,223評(píng)論 6 398
  • 文/花漫 我一把揭開(kāi)白布。 她就那樣靜靜地躺著酱鸭,像睡著了一般吗垮。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上凹髓,一...
    開(kāi)封第一講書人閱讀 52,807評(píng)論 1 314
  • 那天烁登,我揣著相機(jī)與錄音,去河邊找鬼蔚舀。 笑死饵沧,一個(gè)胖子當(dāng)著我的面吹牛,可吹牛的內(nèi)容都是我干的蝗敢。 我是一名探鬼主播捷泞,決...
    沈念sama閱讀 41,235評(píng)論 3 424
  • 文/蒼蘭香墨 我猛地睜開(kāi)眼足删,長(zhǎng)吁一口氣:“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼寿谴!你這毒婦竟也來(lái)了?” 一聲冷哼從身側(cè)響起失受,我...
    開(kāi)封第一講書人閱讀 40,189評(píng)論 0 277
  • 序言:老撾萬(wàn)榮一對(duì)情侶失蹤讶泰,失蹤者是張志新(化名)和其女友劉穎,沒(méi)想到半個(gè)月后拂到,有當(dāng)?shù)厝嗽跇?shù)林里發(fā)現(xiàn)了一具尸體痪署,經(jīng)...
    沈念sama閱讀 46,712評(píng)論 1 320
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 38,775評(píng)論 3 343
  • 正文 我和宋清朗相戀三年兄旬,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了狼犯。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點(diǎn)故事閱讀 40,926評(píng)論 1 353
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡领铐,死狀恐怖悯森,靈堂內(nèi)的尸體忽然破棺而出,到底是詐尸還是另有隱情绪撵,我是刑警寧澤瓢姻,帶...
    沈念sama閱讀 36,580評(píng)論 5 351
  • 正文 年R本政府宣布,位于F島的核電站音诈,受9級(jí)特大地震影響幻碱,放射性物質(zhì)發(fā)生泄漏绎狭。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 42,259評(píng)論 3 336
  • 文/蒙蒙 一褥傍、第九天 我趴在偏房一處隱蔽的房頂上張望儡嘶。 院中可真熱鬧,春花似錦恍风、人聲如沸社付。這莊子的主人今日做“春日...
    開(kāi)封第一講書人閱讀 32,750評(píng)論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)鸥咖。三九已至,卻和暖如春兄世,著一層夾襖步出監(jiān)牢的瞬間啼辣,已是汗流浹背。 一陣腳步聲響...
    開(kāi)封第一講書人閱讀 33,867評(píng)論 1 274
  • 我被黑心中介騙來(lái)泰國(guó)打工御滩, 沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留鸥拧,地道東北人。 一個(gè)月前我還...
    沈念sama閱讀 49,368評(píng)論 3 379
  • 正文 我出身青樓削解,卻偏偏與公主長(zhǎng)得像富弦,于是被迫代替她去往敵國(guó)和親。 傳聞我的和親對(duì)象是個(gè)殘疾皇子氛驮,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,930評(píng)論 2 361