Java基礎學習：java阻塞隊列

更新時間：2020-04-07 13:11:42 來源：動力節(jié)點瀏覽2446次

隊列是一種數(shù)據(jù)結(jié)構(gòu)，它有兩個基本操作：在隊列尾部加入元素和從隊列頭部移除元素。在我們?nèi)粘ｉ_發(fā)中，經(jīng)常用來并發(fā)操作數(shù)據(jù)。java包中有一些應用比較廣泛的特殊隊列：一種是以ConcurrentLinkedQueue為代表的非阻塞隊列；另一種是以BlockingQueue接口為代表的阻塞隊列。通過這兩種隊列，我們保證了多線程操作數(shù)據(jù)的安全性。

Java基礎學習：java阻塞隊列

java集合中的Queue繼承collection接口，Dueue、LinkedList、PriorityQueue、BlockingQueue等類都實現(xiàn)了它。

阻塞隊列

阻塞隊列是一個支持兩個附加操作的隊列：1)在隊列為空時，獲取元素的線程會等待隊列變?yōu)榉强眨?)當隊列滿時，存儲元素的線程會等待隊列可用。因此，當一個線程試圖對一個已經(jīng)滿了的隊列進行入隊列操作時，它將會被堵塞，除非有另一個線程做了出隊列的操作；同樣，當一個線程試圖對一個空隊列進行出隊列操作時，它將會被阻塞，除非有另外一個線程進行了入隊列的操作。

常見的阻塞隊列應用就是生產(chǎn)者消費者模式。生產(chǎn)者把數(shù)據(jù)放到隊列，如果隊列滿了，就會阻塞此操作，直到消費者消費，如果隊列中數(shù)據(jù)被消費完，那么消費者被阻塞，直到生產(chǎn)者生產(chǎn)。

在java包"java.util.concurrent"中，提供六個實現(xiàn)了"BlockingQueue"接口的阻塞隊列。分別是ArrayBlockingQueue、LinkedBlockingQueue、PriorityBlockingQueue、DelayQueue、SynchronousQueue和LinkedBlockingDeque。實質(zhì)上阻塞隊列是一種特殊的FIFO數(shù)據(jù)結(jié)構(gòu)，它不是立即從隊列中添加或刪除元素，而是等到有空間或者元素可用的時候才操作。下面分析下每種阻塞隊列的實現(xiàn)方式和應用場景。

ArrayBlockingQueue

用數(shù)組實現(xiàn)的有界阻塞隊列，默認情況下不保證線程公平的訪問隊列（按照阻塞的先后順序訪問隊列），隊列可用的時候，阻塞的線程都可以爭奪隊列的訪問資格,當然也可以使用以下的構(gòu)造方法創(chuàng)建一個公平的阻塞隊列。ArrayBlockingQueue<String>blockingQueue2=newArrayBlockingQueue<>(10,true)。(其實就是通過將ReentrantLock設置為true來達到這種公平性的：即等待時間最長的線程會先操作)。用ReentrantLockcondition實現(xiàn)阻塞。

有界就是隊列的長度有限制，例如數(shù)組隊列，在構(gòu)建的時候就指定了長度。無界就是可以無限的添加。

LinkedBlockingQueue

基于鏈表實現(xiàn)的有界阻塞隊列。此隊列的默認和最大長度為Integer.MAX_VALUE。此隊列按照先進先出的原則對元素進行排序。這個隊列的實現(xiàn)原理和ArrayBlockingQueue實現(xiàn)基本相同。也是采用ReentrantLock控制并發(fā)，不同的是它使用兩個獨占鎖來控制消費和生產(chǎn)。即用takeLock和putlock,這樣的好處是消費者和生產(chǎn)者可以并發(fā)執(zhí)行，對吞吐量有提升。

PriorityBlockingQueue

PriorityBlockingQueue是一個帶優(yōu)先級的隊列，而不是先進先出隊列。元素按優(yōu)先級順序被移除，該隊列也沒有上限（看了一下源碼，PriorityBlockingQueue是對PriorityQueue的再次包裝，是基于堆數(shù)據(jù)結(jié)構(gòu)的，而PriorityQueue是沒有容量限制的，與ArrayList一樣，所以在優(yōu)先阻塞隊列上put時是不會受阻的。雖然此隊列邏輯上是無界的，但是由于資源被耗盡，所以試圖執(zhí)行添加操作可能會導致OutOfMemoryError），但是如果隊列為空，那么取元素的操作take就會阻塞，所以它的檢索操作take是受阻的。也是用ReentrantLock控制并發(fā)。

DelayQueue

DelayQueue是在PriorityQueue基礎上實現(xiàn)的，底層也是數(shù)組構(gòu)造方法，是一個存放Delayed元素的無界阻塞隊列，只有在延遲期滿時才能從中提取元素。該隊列的頭部是延遲期滿后保存時間最長的Delayed元素。如果延遲都還沒有期滿，則隊列沒有頭部，并且poll將返回null。當一個元素的getDelay(TimeUnit.NANOSECONDS)方法返回一個小于或等于零的值時，則出現(xiàn)期滿，poll就移除這個元素了。此隊列不允許使用null元素。

SynchronousQueue

一個沒有容量的隊列，不會存儲數(shù)據(jù)，每執(zhí)行一次put就要執(zhí)行一次take，否則就會阻塞。未使用鎖。通過cas實現(xiàn)，吞吐量異常高。內(nèi)部采用的就是ArrayBlockingQueue的阻塞隊列，所以在功能上完全可以用ArrayBlockingQueue替換，但是SynchronousQueue是輕量級的，SynchronousQueue不具有任何內(nèi)部容量，我們可以用來在線程間安全的交換單一元素。所以功能比較單一，優(yōu)勢就在于輕量。

LinkedBlockingDeque

LinkedBlockingDeque是雙向鏈表實現(xiàn)的雙向并發(fā)阻塞隊列。該阻塞隊列同時支持FIFO和FILO兩種操作方式，即可以從隊列的頭和尾同時操作(插入/刪除)；并且，該阻塞隊列是支持線程安全，當多線程競爭同一個資源時，某線程獲取到該資源之后，其它線程需要阻塞等待。此外，LinkedBlockingDeque還是可選容量的(防止過度膨脹)，即可以指定隊列的容量。如果不指定，默認容量大小等于Integer.MAX_VALUE。

非阻塞隊列

基于鎖的算法會帶來一些活躍度失敗的風險。如果線程在持有鎖的時候因為阻塞I/O、頁面錯誤、或其他原因發(fā)生延遲，很可能所有的線程都不能工作了。一個線程的失敗或掛起不應該影響其他線程的失敗或掛起，這樣的算法稱為非阻塞算法；如果算法的每一個步驟中都有一些線程能夠繼續(xù)執(zhí)行，那么這樣的算法稱為鎖自由（lock-free）算法。在線程間使用CAS進行協(xié)調(diào)，這樣的算法如果能構(gòu)建正確的話，它既是非阻塞的，又是鎖自由的。java中提供了基于CAS非阻塞算法實現(xiàn)的隊列，比較有代表性的有ConcurrentLinkedQueue和LinkedTransferQueue，它們的性能一般比阻塞隊列的好。

ConcurrentLinkedQueue

ConcurrentLinkedQueue是一個基于鏈接節(jié)點的無界線程安全隊列，它采用先進先出的規(guī)則對節(jié)點進行排序，當我們添加一個元素的時候，它會添加到隊列的尾部；當我們獲取一個元素時，它會返回隊列頭部的元素。ConcurrentLinkedQueue的線程安全是通過其插入、刪除時采取CAS操作來保證的。由于使用CAS沒有使用鎖，所以獲取size的時候有可能進行offer，poll或者remove操作，導致獲取的元素個數(shù)不精確，所以在并發(fā)情況下size函數(shù)不是很有用。

LinkedTransferQueue

jdk7才提供這個類，這個類實現(xiàn)了TransferQueue接口，也是基于鏈表的，對于所有給定的生產(chǎn)者都是先入先出的。與其他阻塞隊列的區(qū)別是：其他阻塞隊列，生產(chǎn)者生產(chǎn)數(shù)據(jù)，如果隊列沒有滿，放下數(shù)據(jù)就走，消費者獲取數(shù)據(jù)，看到有數(shù)據(jù)獲取數(shù)據(jù)就走。而LinkedTransferQueue生產(chǎn)者放數(shù)據(jù)的時候，如果此時消費者沒有獲取，則需阻塞等待直到有消費者過來獲取數(shù)據(jù)。有點類似SynchronousQueue，但是LinkedTransferQueue是被設計有容量的。LinkedTransferQueue通過使用CAS來實現(xiàn)并發(fā)控制，是一個無界的安全隊列。其長度可以無限延伸，當然帶來的問題也是顯而易見的。

Java基礎學習：java阻塞隊列