Java中的ConcurrentLinkedQueue松散隊(duì)列解析
一、為什么叫松散隊(duì)列？
唯一一個(gè)使用cas實(shí)現(xiàn)的線程安全并發(fā)效率高的集合。
鏈表是松散的，鏈表節(jié)點(diǎn)并不都是有效的，允許存在無效節(jié)點(diǎn)val=null，但是只有最后一個(gè)節(jié)點(diǎn)才能next=null 為什么線程安全需要把鏈表做成松散的。就是因?yàn)槿腙?duì)分為兩步，cas設(shè)置最后一個(gè)節(jié)點(diǎn)的next，和cas設(shè)置tail，兩個(gè)操作之間并無原子性，所以可能并發(fā)操作了多個(gè)cas設(shè)置next，才設(shè)置tail。tail滯后很多。 出隊(duì)的時(shí)候，也需要分為兩步，cas將值設(shè)置成null。cas移動(dòng)head。head也會(huì)滯后很多。所以會(huì)有很多節(jié)點(diǎn)已經(jīng)出隊(duì)為null，但是依然可以遍歷到。因此叫做松散隊(duì)列。
二、如何實(shí)現(xiàn)線程安全？
add入隊(duì)操作
tail節(jié)點(diǎn)并不是最后一個(gè)節(jié)點(diǎn)
1、從 tail 節(jié)點(diǎn)開始遍歷到尾節(jié)點(diǎn)，若定位到尾節(jié)點(diǎn)（p.next == null），則入隊(duì)。
2、遍歷過程中，如果遍歷到無效節(jié)點(diǎn)（p.next == p）說明p已經(jīng)并發(fā)出隊(duì)，需要重新從有效節(jié)點(diǎn)（tail 或 head）開始遍歷。
3、遍歷過程中，時(shí)刻關(guān)注 tail 節(jié)點(diǎn)是否無效。若無效了需要重新從最新的 tail（如果tail失效，從head） 開始遍歷，否則繼續(xù)遍歷當(dāng)前的下一個(gè)節(jié)點(diǎn)。
4、找到最后一個(gè)節(jié)點(diǎn)后，進(jìn)行入隊(duì)操作，使用cas將next修改為新節(jié)點(diǎn)，如果tail->next!=null，需要使用cas將tail設(shè)置為新節(jié)點(diǎn)。
cas設(shè)置next，和cas設(shè)置tail，兩個(gè)操作之間并無原子性，所以可能并發(fā)操作了多個(gè)cas設(shè)置next，才設(shè)置tail。tail滯后很多。
如下圖B節(jié)點(diǎn)已經(jīng)被poll了，tail還在B節(jié)點(diǎn)前面。tail失效了，從tail無法遍歷到最后一個(gè)節(jié)點(diǎn)。
poll出隊(duì)操作
1、從 head 節(jié)點(diǎn)開始遍歷找出首個(gè)有效節(jié)點(diǎn)（p.item != null），返回該節(jié)點(diǎn)的數(shù)據(jù)（p.item）。
2、遍歷過程中，如果遍歷到尾節(jié)點(diǎn)（p.next == null），則返回空。
3、遍歷過程中，如果遍歷到無效節(jié)點(diǎn)（p.next == p），說明其他線程修改了 head，需要重新從有效節(jié)點(diǎn)（新的 head）開始遍歷。
4、cas將值設(shè)置成null。cas移動(dòng)head。
5、更新head，需要注意的是，并不是每次出隊(duì)時(shí)都執(zhí)行 updateHead() 更新 head 節(jié)點(diǎn)： 當(dāng) head 節(jié)點(diǎn)里有元素時(shí)，直接彈出 head 節(jié)點(diǎn)里的元素，設(shè)置為null，而不會(huì)更新 head 節(jié)點(diǎn)。
只有當(dāng) head 節(jié)點(diǎn)里沒有元素時(shí)，出隊(duì)操作才會(huì)更新 head 節(jié)點(diǎn)。
三、優(yōu)缺點(diǎn)
從它的入隊(duì)出隊(duì)機(jī)制就可以看出，優(yōu)缺點(diǎn)非常明顯。
優(yōu)點(diǎn)： 1、并發(fā)效率高，入隊(duì)出隊(duì)不需要加鎖進(jìn)行線程同步，全程使用cas操作
缺點(diǎn)： 1、入隊(duì)出隊(duì)都分為兩步cas，cas之間是控制不了的，所以會(huì)產(chǎn)生tail滯后，tail失效，鏈表節(jié)點(diǎn)poll了，還可以繼續(xù)訪問沒有釋放，內(nèi)存是松散的，無效節(jié)點(diǎn)占用內(nèi)存，內(nèi)存開銷大。
2、由于head和tail都不是嚴(yán)格指向頭尾，每次poll，add都需要遍歷，浪費(fèi)時(shí)間效率。concurrentLinkedQueue存的元素越多，效率越低。因此只適合高并發(fā)小容量的場(chǎng)景使用。
3、size獲取大小也要遍歷所有節(jié)點(diǎn)才行
到此這篇關(guān)于Java中的ConcurrentLinkedQueue松散隊(duì)列解析的文章就介紹到這了,更多相關(guān)ConcurrentLinkedQueue松散隊(duì)列內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
通過自動(dòng)掃描，Spring?會(huì)自動(dòng)從掃描指定的包及其子包下的所有類，并根據(jù)類上的特定注解將該類裝配到容器中，而無需在?XML?配置文件或?Java?配置類中逐一聲明每一個(gè)?Bean，這篇文章主要介紹了Spring?IOC中的組件掃描,需要的朋友可以參考下2022-05-05
8個(gè)簡(jiǎn)單部分開啟Java語言學(xué)習(xí)之路 附j(luò)ava學(xué)習(xí)書單
8個(gè)簡(jiǎn)單部分開啟Java語言學(xué)習(xí)之路，附j(luò)ava學(xué)習(xí)書單，這篇文章主要向大家介紹了學(xué)習(xí)java語言的方向，感興趣的小伙伴們可以參考一下2016-09-09
eclipse啟動(dòng)出現(xiàn)“failed to load the jni shared library”問題解決
這篇文章主要介紹了eclipse啟動(dòng)出現(xiàn)“failed to load the jni shared library”問題解決,文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2019-11-11
這篇文章主要介紹了java中的AWT事件處理問題，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2022-11-11
這篇文章主要介紹了springBoot整合rabbitMQ的方法詳解,本文通過實(shí)例代碼給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2021-04-04
這篇文章主要介紹了java中的空指針異常情況以及解決方案，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2021-10-10
在本篇文章里小編給各位整理了關(guān)于微服務(wù)和分布式的區(qū)別以及相關(guān)知識(shí)點(diǎn)總結(jié)，有興趣的朋友們學(xué)習(xí)下。2019-07-07
這篇文章主要介紹了Spring集成Swagger常見錯(cuò)誤及解決辦法，幫助大家更好的理解和學(xué)習(xí)使用Spring，感興趣的朋友可以了解下2021-05-05
這篇文章主要介紹了深入解讀MVC模式和三層架構(gòu),三層架構(gòu)就是為了符合“高內(nèi)聚,低耦合”思想,把各個(gè)功能模塊劃分為表示層(UI)、業(yè)務(wù)邏輯層(BLL)和數(shù)據(jù)訪問層(DAL)的三層架構(gòu),各層之間采用接口相互訪問,需要的朋友可以參考下2023-04-04
大家好，本篇文章主要講的是關(guān)于java中多個(gè)JDK和切換版本介紹，感興趣的同學(xué)趕快來看一看吧，對(duì)你有幫助的話記得收藏一下，方便下次瀏覽2022-01-01