Java中的ConcurrentLinkedQueue松散隊列解析
一、為什么叫松散隊列?
唯一一個使用cas實現(xiàn)的線程安全并發(fā)效率高的集合。
鏈表是松散的,鏈表節(jié)點并不都是有效的,允許存在無效節(jié)點val=null,但是只有最后一個節(jié)點才能next=null 為什么線程安全需要把鏈表做成松散的。就是因為入隊分為兩步,cas設(shè)置最后一個節(jié)點的next,和cas設(shè)置tail,兩個操作之間并無原子性,所以可能并發(fā)操作了多個cas設(shè)置next,才設(shè)置tail。tail滯后很多。 出隊的時候,也需要分為兩步,cas將值設(shè)置成null。cas移動head。head也會滯后很多。所以會有很多節(jié)點已經(jīng)出隊為null,但是依然可以遍歷到。因此叫做松散隊列。
二、如何實現(xiàn)線程安全?
add入隊操作
tail節(jié)點并不是最后一個節(jié)點
1、從 tail 節(jié)點開始遍歷到尾節(jié)點,若定位到尾節(jié)點(p.next == null),則入隊。
2、遍歷過程中,如果遍歷到無效節(jié)點(p.next == p)說明p已經(jīng)并發(fā)出隊,需要重新從有效節(jié)點(tail 或 head)開始遍歷。
3、遍歷過程中,時刻關(guān)注 tail 節(jié)點是否無效。若無效了需要重新從最新的 tail(如果tail失效,從head) 開始遍歷,否則繼續(xù)遍歷當(dāng)前的下一個節(jié)點。
4、找到最后一個節(jié)點后,進(jìn)行入隊操作,使用cas將next修改為新節(jié)點,如果tail->next!=null,需要使用cas將tail設(shè)置為新節(jié)點。
cas設(shè)置next,和cas設(shè)置tail,兩個操作之間并無原子性,所以可能并發(fā)操作了多個cas設(shè)置next,才設(shè)置tail。tail滯后很多。
如下圖B節(jié)點已經(jīng)被poll了,tail還在B節(jié)點前面。tail失效了,從tail無法遍歷到最后一個節(jié)點。
poll出隊操作
1、從 head 節(jié)點開始遍歷找出首個有效節(jié)點(p.item != null),返回該節(jié)點的數(shù)據(jù)(p.item)。
2、遍歷過程中,如果遍歷到尾節(jié)點(p.next == null),則返回空。
3、遍歷過程中,如果遍歷到無效節(jié)點(p.next == p),說明其他線程修改了 head,需要重新從有效節(jié)點(新的 head)開始遍歷。
4、cas將值設(shè)置成null。cas移動head。
5、更新head,需要注意的是,并不是每次出隊時都執(zhí)行 updateHead() 更新 head 節(jié)點: 當(dāng) head 節(jié)點里有元素時,直接彈出 head 節(jié)點里的元素,設(shè)置為null,而不會更新 head 節(jié)點。
只有當(dāng) head 節(jié)點里沒有元素時,出隊操作才會更新 head 節(jié)點。
三、優(yōu)缺點
從它的入隊出隊機制就可以看出,優(yōu)缺點非常明顯。
優(yōu)點: 1、并發(fā)效率高,入隊出隊不需要加鎖進(jìn)行線程同步,全程使用cas操作
缺點: 1、入隊出隊都分為兩步cas,cas之間是控制不了的,所以會產(chǎn)生tail滯后,tail失效,鏈表節(jié)點poll了,還可以繼續(xù)訪問沒有釋放,內(nèi)存是松散的,無效節(jié)點占用內(nèi)存,內(nèi)存開銷大。
2、由于head和tail都不是嚴(yán)格指向頭尾,每次poll,add都需要遍歷,浪費時間效率。concurrentLinkedQueue存的元素越多,效率越低。因此只適合高并發(fā)小容量的場景使用。
3、size獲取大小也要遍歷所有節(jié)點才行
到此這篇關(guān)于Java中的ConcurrentLinkedQueue松散隊列解析的文章就介紹到這了,更多相關(guān)ConcurrentLinkedQueue松散隊列內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
RabbitMQ 的消息持久化與 Spring AMQP 的實現(xiàn)詳解
這篇文章主要介紹了RabbitMQ 的消息持久化與 Spring AMQP 的實現(xiàn)剖析詳解,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下2019-08-08jsp+dao+bean+servlet(MVC模式)實現(xiàn)簡單用戶登錄和注冊頁面
這篇文章主要介紹了jsp+dao+bean+servlet(MVC模式)實現(xiàn)簡單用戶登錄和注冊頁面,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-12-12反射機制:getDeclaredField和getField的區(qū)別說明
這篇文章主要介紹了反射機制:getDeclaredField和getField的區(qū)別說明,具有很好的參考價值,希望對大家有所幫助。如有錯誤或未考慮完全的地方,望不吝賜教2021-06-06Java 5個人坐在一起(有關(guān)第五個人歲數(shù)的問題)
利用遞歸的方法,遞歸分為回推和遞推兩個階段。要想知道第五個人歲數(shù),需知道第四人的歲數(shù),依次類推,推到第一人(10歲),再往回推,需要的朋友可以參考下2017-02-02IDEA使用JDBC安裝配置jar包連接MySQL數(shù)據(jù)庫
這篇文章介紹了IDEA使用JDBC安裝配置jar包連接MySQL數(shù)據(jù)庫的方法,對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2022-01-01