Java中的队列
阻塞隊(duì)列與普通隊(duì)列的區(qū)別在于，當(dāng)隊(duì)列是空的時(shí)，從隊(duì)列中獲取元素的操作將會(huì)被阻塞，或者當(dāng)隊(duì)列是滿(mǎn)時(shí)，往隊(duì)列里添加元素的操作會(huì)被阻塞。
?
試圖從空的阻塞隊(duì)列中獲取元素的線(xiàn)程將會(huì)被阻塞，直到其他的線(xiàn)程往空的隊(duì)列插入新的元素。
?
同樣，試圖往已滿(mǎn)的阻塞隊(duì)列中添加新元素的線(xiàn)程同樣也會(huì)被阻塞，直到其他的線(xiàn)程使隊(duì)列重新變得空閑起來(lái)，如從隊(duì)列中移除一個(gè)或者多個(gè)元素，或者完全清空隊(duì)列。
?
?Java中的隊(duì)列都有哪些，有什么區(qū)別？
1）ArrayDeque, （數(shù)組雙端隊(duì)列）?
2）PriorityQueue, （優(yōu)先級(jí)隊(duì)列）?
3）ConcurrentLinkedQueue, （基于鏈表的并發(fā)隊(duì)列）?
4）DelayQueue, （延期阻塞隊(duì)列）（阻塞隊(duì)列實(shí)現(xiàn)了BlockingQueue接口）?
5）ArrayBlockingQueue, （基于數(shù)組的并發(fā)阻塞隊(duì)列）?
6）LinkedBlockingQueue, （基于鏈表的FIFO阻塞隊(duì)列）?
7）LinkedBlockingDeque, （基于鏈表的FIFO雙端阻塞隊(duì)列）?
8）PriorityBlockingQueue, （帶優(yōu)先級(jí)的無(wú)界阻塞隊(duì)列）?
9）SynchronousQueue,?（并發(fā)同步阻塞隊(duì)列）
?
阻塞隊(duì)列和生產(chǎn)者-消費(fèi)者模式
阻塞隊(duì)列（Blocking queue）提供了可阻塞的put和take方法，它們與可定時(shí)的offer和poll是等價(jià)的。如果Queue已經(jīng)滿(mǎn)了，put方法會(huì)被阻塞直到有空間可用；如果Queue是空的，那么take方法會(huì)被阻塞，直到有元素可用。Queue的長(zhǎng)度可以有限，也可以無(wú)限；無(wú)限的Queue永遠(yuǎn)不會(huì)充滿(mǎn)，所以它的put方法永遠(yuǎn)不會(huì)阻塞。
?
阻塞隊(duì)列支持生產(chǎn)者-消費(fèi)者設(shè)計(jì)模式。一個(gè)生產(chǎn)者-消費(fèi)者設(shè)計(jì)分離了“生產(chǎn)產(chǎn)品”和“消費(fèi)產(chǎn)品”。該模式不會(huì)發(fā)現(xiàn)一個(gè)工作便立即處理，而是把工作置于一個(gè)任務(wù)（“to do”）清單中，以備后期處理。
?
生產(chǎn)者-消費(fèi)者模式簡(jiǎn)化了開(kāi)發(fā)，因?yàn)樗獬松a(chǎn)者和消費(fèi)者之間相互依賴(lài)的代碼。生產(chǎn)者和消費(fèi)者以不同的或者變化的速度生產(chǎn)和消費(fèi)數(shù)據(jù)，生產(chǎn)者-消費(fèi)者模式將這些活動(dòng)解耦，因而簡(jiǎn)化了工作負(fù)荷的管理。
?
生產(chǎn)者-消費(fèi)者設(shè)計(jì)是圍繞阻塞隊(duì)列展開(kāi)的，生產(chǎn)者把數(shù)據(jù)放入隊(duì)列，并使數(shù)據(jù)可用，當(dāng)消費(fèi)者為適當(dāng)?shù)男袨樽鰷?zhǔn)備時(shí)會(huì)從隊(duì)列中獲取數(shù)據(jù)。
?
生產(chǎn)者不需要知道消費(fèi)者的省份或者數(shù)量，甚至根本沒(méi)有消費(fèi)者—它們只負(fù)責(zé)把數(shù)據(jù)放入隊(duì)列。類(lèi)似地，消費(fèi)者也不需要知道生產(chǎn)者是誰(shuí)，以及是誰(shuí)給它們安排的工作。
?
BlockingQueue可以使用任意數(shù)量的生產(chǎn)者和消費(fèi)者，從而簡(jiǎn)化了生產(chǎn)者-消費(fèi)者設(shè)計(jì)的實(shí)現(xiàn)。最常見(jiàn)的生產(chǎn)者-消費(fèi)者設(shè)計(jì)是將線(xiàn)程池與工作隊(duì)列相結(jié)合。
?
阻塞隊(duì)列簡(jiǎn)化了消費(fèi)者的編碼，因?yàn)?strong>take會(huì)保持阻塞直到可用數(shù)據(jù)出現(xiàn)。如果生產(chǎn)者不能足夠快地產(chǎn)生工作，讓消費(fèi)者忙碌起來(lái)，那么消費(fèi)者只能一直等待，直到有工作可做。
?
同時(shí)，put方法的阻塞特性也大大地簡(jiǎn)化了生產(chǎn)者的編碼；如果使用一個(gè)有界隊(duì)列，那么當(dāng)隊(duì)列充滿(mǎn)的時(shí)候，生產(chǎn)者就會(huì)阻塞，暫不能生成更多的工作，從而給消費(fèi)者時(shí)間來(lái)趕進(jìn)進(jìn)度。
?
有界隊(duì)列是強(qiáng)大的資源管理工具，用來(lái)建立可靠的應(yīng)用程序：它們遏制那些可以產(chǎn)生過(guò)多工作量、具有威脅的活動(dòng)，從而讓你的程序在面對(duì)超負(fù)荷工作時(shí)更加健壯。
?
雖然生產(chǎn)者-消費(fèi)者模式可以把生產(chǎn)者和消費(fèi)者的代碼相互解耦合，但是它們的行為還是間接地通過(guò)共享隊(duì)列耦合在一起了。
?
類(lèi)庫(kù)中包含一些BlockingQueue的實(shí)現(xiàn)，其中LinkedBlockingQueue和ArrayBlockingQueue是FIFO隊(duì)列，與 LinkedList和ArrayList相似，但是卻擁有比同步List更好的并發(fā)性能。
?
PriorityBlockingQueue是一個(gè)按優(yōu)先級(jí)順序排序的隊(duì)列，當(dāng)你不希望按照FIFO的屬性處理元素時(shí)，這個(gè)PriorityBolckingQueue是非常有用的。
?
正如其他排序的容器一樣，PriorityBlockingQueue可以比較元素本身的自然順序（如果它們實(shí)現(xiàn)了Comparable），也可以使用一個(gè)?Comparator進(jìn)行排序。
?
最后一個(gè)BlockingQueue的實(shí)現(xiàn)是SynchronousQueue，它根本上不是一個(gè)真正的隊(duì)列，因?yàn)樗粫?huì)為隊(duì)列元素維護(hù)任何存儲(chǔ)空間。不過(guò)，它維護(hù)一個(gè)排隊(duì)的線(xiàn)程清單，這些線(xiàn)程等待把元素加入（enqueue）隊(duì)列或者移出（dequeue）隊(duì)列。
?
因?yàn)?strong>SynchronousQueue沒(méi)有存儲(chǔ)能力，所以除非另一個(gè)線(xiàn)程已經(jīng)準(zhǔn)備好參與移交工作，否則put和take會(huì)一直阻止。SynchronousQueue這類(lèi)隊(duì)列只有在消費(fèi)者充足的時(shí)候比較合適，它們總能為下一個(gè)任務(wù)作好準(zhǔn)備。
?
非阻塞算法
基于鎖的算法會(huì)帶來(lái)一些活躍度失敗的風(fēng)險(xiǎn)。如果線(xiàn)程在持有鎖的時(shí)候因?yàn)樽枞鸌/O，頁(yè)面錯(cuò)誤，或其他原因發(fā)生延遲，很可能所有的線(xiàn)程都不能前進(jìn)了。?
?
一個(gè)線(xiàn)程的失敗或掛起不應(yīng)該影響其他線(xiàn)程的失敗或掛起，這樣的算法成為非阻塞（nonblocking）算法；如果算法的每一個(gè)步驟中都有一些線(xiàn)程能夠繼續(xù)執(zhí)行，那么這樣的算法稱(chēng)為鎖自由（lock-free）算法。在線(xiàn)程間使用CAS進(jìn)行協(xié)調(diào)，這樣的算法如果能構(gòu)建正確的話(huà)，它既是非阻塞的，又是鎖自由的。
?
非競(jìng)爭(zhēng)的CAS總是能夠成功，如果多個(gè)線(xiàn)程以一個(gè)CAS競(jìng)爭(zhēng)，總會(huì)有一個(gè)勝出并前進(jìn)。非阻塞算法堆死鎖和優(yōu)先級(jí)倒置有“免疫性”（但它們可能會(huì)出現(xiàn)饑餓和活鎖，因?yàn)樗鼈冊(cè)试S重進(jìn)入）。
?
非阻塞算法通過(guò)使用低層次的并發(fā)原語(yǔ)，比如比較交換，取代了鎖。原子變量類(lèi)向用戶(hù)提供了這些底層級(jí)原語(yǔ)，也能夠當(dāng)做“更佳的volatile變量”使用，同時(shí)提供了整數(shù)類(lèi)和對(duì)象引用的原子化更新操作。
總結(jié)
- 上一篇： FreeRTOS应用——消息队列
- 下一篇： 机器学习.周志华《6 支持向量机》