前言
LinkedTransferQueue是JDK1.7才添加的阻塞隊列,基于鏈表實現(xiàn)的FIFO無界阻塞隊列么鹤,是ConcurrentLinkedQueue(循環(huán)CAS+volatile 實現(xiàn)的wait-free并發(fā)算法)拍屑、SynchronousQueue(公平模式下轉(zhuǎn)交元素)芹敌、LinkedBlockingQueue(阻塞Queue的基本方法)的超集颖侄。而且LinkedTransferQueue更好用窥浪,因為它不僅僅綜合了這幾個類的功能,同時也提供了更高效的實現(xiàn)。
BlockingQueue接口坎藐,它是指這樣的一個隊列:當生產(chǎn)者向隊列添加元素但隊列已滿時,生產(chǎn)者會被阻塞嗅榕;當消費者從隊列移除元素但隊列為空時顺饮,消費者會被阻塞。
LinkedTransferQueue采用的一種預(yù)占模式凌那。意思就是消費者線程取元素時兼雄,如果隊列為空,那就生成一個節(jié)點(節(jié)點元素為null)入隊帽蝶,然后消費者線程被等待在這個節(jié)點上赦肋,后面生產(chǎn)者線程入隊時發(fā)現(xiàn)有一個元素為null的節(jié)點,生產(chǎn)者線程就不入隊了励稳,直接就將元素填充到該節(jié)點佃乘,喚醒該節(jié)點等待的線程,被喚醒的消費者線程取走元素驹尼,從調(diào)用的方法返回趣避。即找到匹配的節(jié)點不入隊,找不到根據(jù)how參數(shù)入隊新翎。
TransferQueue接口
TransferQueue繼承自BlockingQueue接口
LinkedTransferQueue定義
實現(xiàn)了TransferQueue接口
LinkedTransferQueue鏈表節(jié)點Node
將沒有匹配的數(shù)據(jù)節(jié)點進行匹配程帕,匹配成功后設(shè)置item為null,隊列中占位地啰,然后阻塞等待在此節(jié)點上的消費者愁拭,等待被喚醒被喚醒則返回true。
匹配前后節(jié)點item的變化亏吝,其中node1為數(shù)據(jù)節(jié)點岭埠,node2是消費者請求的占位節(jié)點
- 數(shù)據(jù)節(jié)點,則匹配前item不為null且不為自身,匹配后設(shè)置為null惜论。
- 占位請求節(jié)點许赃,匹配前item為null,匹配后自連接来涨。
LinkedTransferQueue重要字段
head和tail節(jié)點初始化時都為null
構(gòu)造器
LinkedTransferQueue是無界隊列图焰,并沒有指定容量的構(gòu)造器
xfer核心方法
實現(xiàn)所有隊列的出隊入隊方法的通用方法
how 參數(shù)
xfer方法
簡單說一下xfer方法的流程
- 尋找和操作匹配的節(jié)點
- 從head開始向后遍歷尋找未被匹配的節(jié)點启盛,找到一個未被匹配的節(jié)點再判斷操作和節(jié)點類型是否匹配(put和占位請求節(jié)點匹配蹦掐,take和數(shù)據(jù)節(jié)點匹配),如果不匹配則跳出內(nèi)循環(huán)再從head開始尋找未匹配節(jié)點(重復(fù))僵闯,否則通過CAS設(shè)置匹配節(jié)點的item為e卧抗,設(shè)置成功后再CAS設(shè)置新的head節(jié)點為匹配節(jié)點的后繼節(jié)點,向后推進head鳖粟,將原來的head節(jié)點自連接社裆,等待被GC,然后喚醒阻塞在這個節(jié)點上的線程向图,并返回匹配節(jié)點的item元素泳秀,元素沒有入隊,而是直接從生產(chǎn)者轉(zhuǎn)交給消費者榄攀。
- 上面可分兩個步驟:找到未被匹配的節(jié)點嗜傅,然后對節(jié)點的類型進行判斷和設(shè)置head
- put和take的不同:put本身帶有data(e != null),put找到匹配的節(jié)點檩赢,如果節(jié)點類型也滿足(not isData)吕嘀,則將e設(shè)置為p的item元素,并向后推進head贞瞒,然后喚醒等待的線程偶房,并返回匹配節(jié)點原來的item(null);take本身不帶data(e == null)军浆,take找到匹配的節(jié)點棕洋,如果節(jié)點類型也滿足( isData),則將e設(shè)置為p的item元素(item變?yōu)閚ull)乒融,并向后推進head掰盘,然后喚醒等待的線程,并返回匹配節(jié)點原來的item(not null)簇抵。
- 如果遍歷整個隊列都沒有匹配的節(jié)點庆杜,則執(zhí)行相對應(yīng)的how操作處理
注意如果isData為false,則是將一個占位請求節(jié)點插入隊列尾部碟摆。
- NOW:立即返回晃财,也不會插入節(jié)點
- SYNC:插入一個item為e(isData = haveData)到隊列的尾部,然后自旋或阻塞當前線程直到節(jié)點被匹配或者取消。
- ASYNC:插入一個item為e(isData = haveData)到隊列的尾部断盛,不阻塞直接返回罗洗。
- TIMED:插入一個item為e(isData = haveData)到隊列的尾部,然后自旋或阻塞當前線程直到節(jié)點被匹配或者取消或者超時钢猛。
- 阻塞或者自旋
插入的占位節(jié)點自旋超過一個閥值時將阻塞線程伙菜,當頻繁寫操作時避免過度自旋消耗CPU
ASYNC操作(put、offer命迈、add)
how 參數(shù)為ASYNC贩绕,即找不到匹配節(jié)點,則入隊不等待直接返回
NOW操作(poll壶愤、tryTransfer)
how 參數(shù)為NOW淑倾,即找不到匹配節(jié)點,則將構(gòu)建新節(jié)點入隊并立即返回
SYNC操作(transfer征椒、take)
how 參數(shù)為SYNC娇哆,即找不到匹配節(jié)點,則將構(gòu)建新節(jié)點入隊并阻塞線程直到節(jié)點被匹配或被取消
TIMED操作(poll勃救、tryTransfer)
how 參數(shù)為TIMED碍讨,即找不到匹配節(jié)點,則將構(gòu)建新節(jié)點入隊并阻塞線程直到節(jié)點被匹配或被取消或者超時
用途與注意事項
使用LinkedTransferQueue來代替SynchronousQueue也會使得ThreadPoolExecutor得到相應(yīng)的性能提升蒙秒。
盡量避免使用how == SYNC的操作勃黍,因為LinkedTransferQueue是無界隊列,當大量線程都阻塞税肪,則會占用大量的線程資源溉躲。