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