Java并發(fā)編程之ConcurrentLinkedQueue解讀
一、簡介
工作中有時候需要使用線程安全的隊(duì)列。如果要實(shí)現(xiàn)一個線程安全的隊(duì)列有兩種方式:一種是使用阻塞算法,另一種是使用非阻塞算法。使用阻塞算法的隊(duì)列可以用一個鎖(入隊(duì)和出隊(duì)用同一把鎖)或兩個鎖(入隊(duì)和出隊(duì)用不同的鎖)等方式來實(shí)現(xiàn)。非阻塞的實(shí)現(xiàn)方式則可以使用循環(huán)CAS的方式來實(shí)現(xiàn)。而ConcurrentLinkedQueue就是juc包中自帶的經(jīng)典非堵塞方式實(shí)現(xiàn)的工具類
二、結(jié)構(gòu)
ConcurrentLinkedQueue由head節(jié)點(diǎn)和tail節(jié)點(diǎn)組成,每個節(jié)點(diǎn)(Node)由節(jié)點(diǎn)元素(item)和指向下一個節(jié)點(diǎn)(next)的引用組成,節(jié)點(diǎn)與節(jié)點(diǎn)之間就是通過這個next關(guān)聯(lián)起來,從而組成一張鏈表結(jié)構(gòu)的隊(duì)列。默認(rèn)情況下head節(jié)點(diǎn)存儲的元素為空,tail節(jié)點(diǎn)等于head節(jié)點(diǎn)。
private transient volatile Node<E> tail = head;
三、入隊(duì)
從源代碼角度來看,整個入隊(duì)過程主要做兩件事情:第一是定位出尾節(jié)點(diǎn);第二是使用CAS算法將入隊(duì)節(jié)點(diǎn)設(shè)置成尾節(jié)點(diǎn)的next節(jié)點(diǎn),如不成功則重試。
public boolean offer(E e) { checkNotNull(e); // 入隊(duì)前,創(chuàng)建一個入隊(duì)節(jié)點(diǎn) final Node<E> newNode = new Node<E>(e); for (Node<E> t = tail, p = t;;) { // 創(chuàng)建一個指向tail節(jié)點(diǎn)的引用 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; } }
tail節(jié)點(diǎn)并不總是尾節(jié)點(diǎn),所以每次入隊(duì)都必須先通過tail節(jié)點(diǎn)來找到尾節(jié)點(diǎn)。尾節(jié)點(diǎn)可能是tail節(jié)點(diǎn),也可能是tail節(jié)點(diǎn)的next節(jié)點(diǎn)。代碼中循環(huán)體中的第一個if就是判斷tail是否有next節(jié)點(diǎn),有則表示next節(jié)點(diǎn)可能是尾節(jié)點(diǎn)。獲取tail節(jié)點(diǎn)的next節(jié)點(diǎn)需要注意的是p節(jié)點(diǎn)等于p的next節(jié)點(diǎn)的情況,只有一種可能就是p節(jié)點(diǎn)和p的next節(jié)點(diǎn)都等于空,表示這個隊(duì)列剛初始化,正準(zhǔn)備添加節(jié)點(diǎn),所以需要返回head節(jié)點(diǎn)。
/** *返回 p 的后繼節(jié)點(diǎn),或者如果 p.next 已經(jīng)鏈接到 self 則返回頭節(jié)點(diǎn),這只有在使用現(xiàn)在不在列表*中的陳舊指針遍歷時才會為真。 **/ final Node<E> succ(Node<E> p) { Node<E> next = p.next; return (p == next) ? head : next; }
四、出列
public E poll() { restartFromHead: for (;;) { for (Node<E> h = head, p = h, q;;) { //入列折騰的tail,那出列折騰的就是head E item = p.item; //出列判斷依據(jù)是節(jié)點(diǎn)的item=null //item != null, 并且能將操作節(jié)點(diǎn)的item設(shè)置null, 表示出列成功 if (item != null && p.casItem(item, null)) { if (p != h) //一旦出列成功需要對head進(jìn)行移動 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) //第一輪操作失敗,下一輪繼續(xù),調(diào)回到循環(huán)前 continue restartFromHead; else //推動head節(jié)點(diǎn)移動 p = q; } } }
五、ConcurrentLinkedQueue使用特點(diǎn)
ConcurrentLinkedQueue使用約定:
1:不允許null入列
2:在入隊(duì)的最后一個元素的next為null
3:隊(duì)列中所有未刪除的節(jié)點(diǎn)的item都不能為null且都能從head節(jié)點(diǎn)遍歷到
4:刪除節(jié)點(diǎn)是將item設(shè)置為null, 隊(duì)列迭代時跳過item為null節(jié)點(diǎn)
5:head節(jié)點(diǎn)跟tail不一定指向頭節(jié)點(diǎn)或尾節(jié)點(diǎn),可能存在滯后性
到此這篇關(guān)于Java并發(fā)編程之ConcurrentLinkedQueue解讀的文章就介紹到這了,更多相關(guān)Java中的ConcurrentLinkedQueue內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
java isPalindrome方法在密碼驗(yàn)證中的應(yīng)用
這篇文章主要為大家介紹了java isPalindrome方法在密碼驗(yàn)證中的簡單應(yīng)用技巧,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪2023-12-12使用Java實(shí)現(xiàn)一個不同難度(高、中、低)的猜數(shù)字游戲
本文介紹了一個增強(qiáng)版的猜數(shù)字游戲,包括菜單打印、游戲維持、邏輯功能選擇和源代碼展示,游戲通過隨機(jī)數(shù)生成和邏輯判斷來維持游戲進(jìn)程,用戶可以選擇不同的難度,源代碼展示了如何實(shí)現(xiàn)這三種不同難度的猜數(shù)字游戲,為玩家?guī)砀嗵魬?zhàn)和樂趣,需要的朋友可以參考下2024-09-09java 數(shù)據(jù)結(jié)構(gòu)并查集詳解
并查集是一種用來管理元素分組情況的數(shù)據(jù)結(jié)構(gòu)。并查集可以高效地進(jìn)行如下操作。本文將通過Java實(shí)現(xiàn)并查集,感興趣的小伙伴可以了解一下2022-03-03java實(shí)現(xiàn)兩個線程交替打印的實(shí)例代碼
在本篇文章里小編給大家整理的是一篇關(guān)于java實(shí)現(xiàn)兩個線程交替打印的相關(guān)知識點(diǎn)內(nèi)容,有需要的朋友們參考下。2019-12-12Java網(wǎng)絡(luò)通信中ServerSocket的設(shè)計優(yōu)化方案
今天小編就為大家分享一篇關(guān)于Java網(wǎng)絡(luò)通信中ServerSocket的設(shè)計優(yōu)化方案,小編覺得內(nèi)容挺不錯的,現(xiàn)在分享給大家,具有很好的參考價值,需要的朋友一起跟隨小編來看看吧2019-04-04IntelliJ?IDEA2022.3?springboot?熱部署含靜態(tài)文件(最新推薦)
這篇文章主要介紹了IntelliJ?IDEA2022.3?springboot?熱部署含靜態(tài)文件,本文結(jié)合實(shí)例代碼給大家介紹的非常詳細(xì),對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值,需要的朋友可以參考下2023-01-01springBoot下實(shí)現(xiàn)java自動創(chuàng)建數(shù)據(jù)庫表
這篇文章主要介紹了springBoot下實(shí)現(xiàn)java自動創(chuàng)建數(shù)據(jù)庫表的操作,具有很好的參考價值,希望對大家有所幫助。如有錯誤或未考慮完全的地方,望不吝賜教2021-07-07Springboot實(shí)現(xiàn)Java阿里短信發(fā)送代碼實(shí)例
這篇文章主要介紹了springboot實(shí)現(xiàn)Java阿里短信發(fā)送代碼實(shí)例,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下2020-02-02