一、為什么叫松散隊列？

唯一一個使用cas實現(xiàn)的線程安全并發(fā)效率高的集合。

鏈表是松散的，鏈表節(jié)點并不都是有效的，允許存在無效節(jié)點val=null，但是只有最后一個節(jié)點才能next=null 為什么線程安全需要把鏈表做成松散的。就是因為入隊分為兩步，cas設置最后一個節(jié)點的next，和cas設置tail，兩個操作之間并無原子性，所以可能并發(fā)操作了多個cas設置next，才設置tail。tail滯后很多。 出隊的時候，也需要分為兩步，cas將值設置成null。cas移動head。head也會滯后很多。所以會有很多節(jié)點已經出隊為null，但是依然可以遍歷到。因此叫做松散隊列。

二、如何實現(xiàn)線程安全？

add入隊操作

tail節(jié)點并不是最后一個節(jié)點

1、從 tail 節(jié)點開始遍歷到尾節(jié)點，若定位到尾節(jié)點（p.next == null），則入隊。

2、遍歷過程中，如果遍歷到無效節(jié)點（p.next == p）說明p已經并發(fā)出隊，需要重新從有效節(jié)點（tail 或 head）開始遍歷。

3、遍歷過程中，時刻關注 tail 節(jié)點是否無效。若無效了需要重新從最新的 tail（如果tail失效，從head） 開始遍歷，否則繼續(xù)遍歷當前的下一個節(jié)點。

4、找到最后一個節(jié)點后，進行入隊操作，使用cas將next修改為新節(jié)點，如果tail->next!=null，需要使用cas將tail設置為新節(jié)點。

cas設置next，和cas設置tail，兩個操作之間并無原子性，所以可能并發(fā)操作了多個cas設置next，才設置tail。tail滯后很多。

如下圖B節(jié)點已經被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將值設置成null。cas移動head。

5、更新head，需要注意的是，并不是每次出隊時都執(zhí)行 updateHead() 更新 head 節(jié)點： 當 head 節(jié)點里有元素時，直接彈出 head 節(jié)點里的元素，設置為null，而不會更新 head 節(jié)點。

只有當 head 節(jié)點里沒有元素時，出隊操作才會更新 head 節(jié)點。

三、優(yōu)缺點

從它的入隊出隊機制就可以看出，優(yōu)缺點非常明顯。

優(yōu)點： 1、并發(fā)效率高，入隊出隊不需要加鎖進行線程同步，全程使用cas操作

缺點： 1、入隊出隊都分為兩步cas，cas之間是控制不了的，所以會產生tail滯后，tail失效，鏈表節(jié)點poll了，還可以繼續(xù)訪問沒有釋放，內存是松散的，無效節(jié)點占用內存，內存開銷大。

2、由于head和tail都不是嚴格指向頭尾，每次poll，add都需要遍歷，浪費時間效率。concurrentLinkedQueue存的元素越多，效率越低。因此只適合高并發(fā)小容量的場景使用。

3、size獲取大小也要遍歷所有節(jié)點才行

到此這篇關于Java中的ConcurrentLinkedQueue松散隊列解析的文章就介紹到這了,更多相關ConcurrentLinkedQueue松散隊列內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！

最新評論