Java中的阻塞隊列
ArrayBlockingQueeue，LinkedBlockingQueue,PriorityBlockingQueue,ConcurrentLinkedQueue,SynchronousQueue,DelayQueue 簡單對比
ArrayBlockingQueue
特性
- 數(shù)組存儲
- 有界
- 阻塞隊列
- FIFO
初始化參數(shù)
- capacity 隊列最大可用容量
- fair 阻塞用的鎖是否使用公平鎖, 默認為false
- collection 隊列初始化完成后，將collection中的元素放入隊列中
基本原理
- 使用ReentrantLock保證同一時刻只有一個線程對隊列進行讀或者寫
- 使用兩個Condition分別來控制生產者和消費者是否進行阻塞虏劲，以及是否取消阻塞
- 容量在創(chuàng)建時即初始化好，并分配空間吊履，不可改變
- 內部維護三個變量takeIndex(尾索引)肤晓，putIndex(頭索引), count(實際大小)爷贫，因為只有一把鎖认然，所以count不需要特殊修飾符修飾
LinkedBlockingQueue
特性
- 鏈表存儲
- 可設置邊界
- 阻塞隊列
- FIFO
初始化參數(shù)
- capacity 隊列的最大容量，默認為：Integer.MAX_VALUE
- collection 隊列初始化完成后漫萄，將collection中的元素放入隊列中
基本原理
- 使用ReentrantLock分別創(chuàng)建了兩把鎖卷员，讀鎖和寫鎖
- 通過讀鎖和寫鎖各自的信號量單獨控制生產者和消費者是否阻塞
- 只設置最大容量，不預先分配空間
- 內部維護head(頭指針)腾务，last(尾指針)毕骡，以及AtomicInteger類型的count(實際大小)，因為是兩把鎖窑睁，所以count需要在能夠在不同線程間通訊挺峡。
LinkedBlockingQueue與ArrayBlockingQueue對比
這兩個隊列的區(qū)別主要是因為存儲數(shù)據的結構不同引起的.
1. array和LinkedList數(shù)據結構不同導致Queue處理capacity參數(shù)的策略不同
- array初始化時，必須設置大小担钮，并且初始化橱赠，所以ArrayBlockingQueue必須初始化容量，并且當容量設置過大時, 在初始化時箫津，就有內存溢出的風險
- 而鏈表初始化時狭姨，僅僅初始化了一個頭尾指針，所以LinkedBlockingQueue的容量大小可以設置為Integer.MAX_VALUE苏遥。
2. array和LinkedList數(shù)據結構不同導致Queue內部設計鎖的策略不同
從array和linkedList都是可以分別設置讀寫鎖的饼拍，那為什么ArrayBlockingQueue公用一把鎖呢？
- ArrayBlockingQueue設置讀鎖和寫鎖田炭，就需要考慮count就需要使用AtomicInteger师抄，而array在操作元素的時候，只需要更新數(shù)組的指針指向教硫，讀寫速度相對一致叨吮，此時AtomicInter類型的count有可能成為性能瓶頸(樂觀鎖遇見同時修改數(shù)據的情況，性能較低)瞬矩，所以不如直接使用一把鎖茶鉴，性能基本相似，并且代碼復雜度降低
- 當Queue的容量為空的時候景用，此時讀鎖和寫鎖需要控制array的同一個位置涵叮，此時的性能和使用一把鎖是一樣的。而且從實際場景來看伞插，我們無法判斷這種情形的多少割粮，倒不如減少代碼復雜度，
- linkedList因為是使用的鏈表媚污，即使隊列為空時穆刻，其也是分別操作頭尾指針，所以采用讀鎖和寫鎖可以降低搶占鎖的性能
- linkedList 插入數(shù)據時杠步，需要先構建node,而取數(shù)據時氢伟，只需要分離指針即可，讀寫操作耗時不一致幽歼，相當于降低了同時修改cout值的概率朵锣，此時樂觀鎖效率較高
3. 為什么通常說 LinkedBlockingQueue比ArrayBlockingQueue速度快，但是LinkedBlockingQueue的性能卻是不可預測或者說不穩(wěn)定的呢甸私？
快是因為雙鎖比單鎖要快诚些，不穩(wěn)定是因為樂觀鎖，樂觀鎖在并發(fā)過高的時候性能不穩(wěn)定皇型。
PriorityBlockingQueue
特性
- 數(shù)組存儲
- 無界
- 阻塞隊列
- 根據執(zhí)行策略進行優(yōu)先級排序出列
初始化參數(shù)
- initialCapacity 初始容量诬烹，默認為11，設定初始容量可以在能夠預估容量的情況下弃鸦，避免因為多次擴容造成的性能浪費
- comparator 排序規(guī)則绞吁，默認采用自然排序
- collection 將collection中的元素放入隊列中
基本原理
- 使用二叉樹最小堆算法來維護內部數(shù)組
- 使用ReentrantLock保證同一時刻只有一個線程對隊列進行讀或者寫
- 使用一個Condition控制消費者是否進行阻塞，以及是否取消阻塞
- 容量可動態(tài)擴容
- 插入數(shù)據時唬格，根據預設排序規(guī)則家破，將元素插入指定位置，
- 取數(shù)據時购岗，從隊列頭部取汰聋，因為頭部的數(shù)據優(yōu)先級總是最高的
QA
- Q: 為什么不用沒有使用鏈表實現(xiàn)的優(yōu)先級隊列？
A: 因為優(yōu)先級隊列涉及集合的排序過程喊积，而大多數(shù)排序算法都需要隨機插入烹困，在隨機插入方面數(shù)組的效率是遠優(yōu)于鏈表的。所以使用數(shù)組而不是鏈表乾吻。 - Q: PriorityBlockingQueue最大容量為什么是Integer.MAX_VALUE - 8髓梅？
A: 作者的解釋是：有些jvm會在數(shù)組放一下頭信息，為了避免內存溢出溶弟，所以設置最大容量為Integer.MAX_VALUE - 8, 在Java中女淑，幾乎所有以數(shù)組作為存儲結構的工具類都是這么設計的。比如ArrayList辜御。那為什么要減8呢鸭你？因為jvm的header信息在32位的系統(tǒng)下是4字節(jié)，在64位系統(tǒng)下是8字節(jié)擒权。所以預留減8足夠了袱巨。
ConcurrentLinkedQueue
特性
- 鏈表存儲
- 無界
- 并發(fā)安全
- FIFO
基本原理
ConcurrentLinkedQueue是基于樂觀鎖(CAS)實現(xiàn)的并發(fā)安全的無界隊列。其使用樂觀鎖存取數(shù)據碳抄，避免了在等待鎖時愉老，因線程掛起導致上下文切換所耗費的性能。
在引入樂觀鎖的同時剖效， ConcurrentLinkedQueue引入惰性更新的邏輯嫉入，延遲更新tail節(jié)點的更新頻率焰盗。即，正常操作應該是每次存取數(shù)據都要更新tail節(jié)點咒林，但是ConcurrentLinkedQueue只有在tail的操作次數(shù)達到閾值后才會被更新熬拒，這樣就減少了鎖的次數(shù)。降低性能開銷垫竞。
LinkedTransferQueue
特性
- 鏈表存儲
- 無界
- 并發(fā)安全
- FIFO
- 阻塞
基本原理
LinkedTransferQueue擴展了內部存儲的數(shù)據類型澎粟，即 懶惰雙類型隊列（Dual Queues with Slack），一般的隊列欢瞪，內部只是緩存生產者產生的數(shù)據活烙，這種情況下，從生產者到消費者遣鼓，數(shù)據流轉必須經歷一個完整的入隊啸盏，出隊過程，即使此時消費者的能力是大于等于生產者的譬正。
而LinkedTransferQueue不僅可以緩存生產者產生的數(shù)據宫补，還可以緩存消費者線程。通過這種方式曾我，將數(shù)據交換變?yōu)椋翰迦霐?shù)據時粉怕，判斷有沒有消費者在等待，若有則直接將數(shù)據交給消費者抒巢，沒有這加入隊列緩存贫贝。而消費者在取數(shù)據時，若發(fā)現(xiàn)隊列為空蛉谜，此時是將自己緩存到隊列的尾節(jié)點中稚晚。通過這種設計，一方面減少了消費者能力大于等于生產者條件下的數(shù)據交換邏輯型诚，同時減少了鎖的開銷客燕。
LinkedTransferQueue在更新tail節(jié)點時，也引入惰性刪除的邏輯狰贯。
SynchronousQueue
特性
- 阻塞隊列
- 零容量
- 阻塞
- FIFO
初始化參數(shù)
- fail 是否使用公平鎖也搓，默認為false
基本原理
SynchronousQueue分公平模式和非公平模式。
公平模式內部實現(xiàn)了一個TransferQueue涵紊，該隊列的特點是不存儲數(shù)據傍妒，然后將提交數(shù)據的生產者和消費數(shù)據的消費者阻塞起來，當生產者線程和消費者線程同時出現(xiàn)時摸柄，即可直接交換數(shù)據颤练。 TransferQueue內部實現(xiàn)了一個鏈表，用于存儲生產者和消費者線程驱负。當沒有成對的生產者消費者出現(xiàn)時嗦玖，所有來存取數(shù)據的線程都會被阻塞在鏈表中患雇。直到有匹配線程出現(xiàn)，則按照入隊順序喚醒相應的線程踏揣，然后交換數(shù)據庆亡。
非公平模式內部實現(xiàn)了一個TransferStack, 即使用棧的先進后出特性實現(xiàn)非公平性。
DelayQueue
特性
- 延時
- 阻塞
- 無界
基本原理
DelayQueue內部使用PriorityQueue實現(xiàn)了一個針對數(shù)據緩存時間的優(yōu)先級隊列捞稿。所以其特性同PriorityBlockingQueue是相同的。
