并發(fā)集合9-LinkedTransferQueue

前言

  1. LinkedTransferQueue是JDK1.7才添加的阻塞隊列,基于鏈表實現(xiàn)的FIFO無界阻塞隊列么鹤,是ConcurrentLinkedQueue(循環(huán)CAS+volatile 實現(xiàn)的wait-free并發(fā)算法)拍屑、SynchronousQueue(公平模式下轉(zhuǎn)交元素)芹敌、LinkedBlockingQueue(阻塞Queue的基本方法)的超集颖侄。而且LinkedTransferQueue更好用窥浪,因為它不僅僅綜合了這幾個類的功能,同時也提供了更高效的實現(xiàn)

  2. BlockingQueue接口坎藐,它是指這樣的一個隊列:當生產(chǎn)者向隊列添加元素但隊列已滿時,生產(chǎn)者會被阻塞嗅榕;當消費者從隊列移除元素但隊列為空時顺饮,消費者會被阻塞

  3. 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é)點

  1. 數(shù)據(jù)節(jié)點,則匹配前item不為null且不為自身,匹配后設(shè)置為null惜论。
  2. 占位請求節(jié)點许赃,匹配前item為null,匹配后自連接来涨。

LinkedTransferQueue重要字段


head和tail節(jié)點初始化時都為null


構(gòu)造器


LinkedTransferQueue是無界隊列图焰,并沒有指定容量的構(gòu)造器

xfer核心方法

實現(xiàn)所有隊列的出隊入隊方法的通用方法

how 參數(shù)



xfer方法



簡單說一下xfer方法的流程

  1. 尋找和操作匹配的節(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)簇抵。
  1. 如果遍歷整個隊列都沒有匹配的節(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é)點被匹配或者取消或者超時钢猛。
  1. 阻塞或者自旋

插入的占位節(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é)點被匹配或被取消或者超時


用途與注意事項

  1. 使用LinkedTransferQueue來代替SynchronousQueue也會使得ThreadPoolExecutor得到相應(yīng)的性能提升蒙秒。

  2. 盡量避免使用how == SYNC的操作勃黍,因為LinkedTransferQueue是無界隊列當大量線程都阻塞税肪,則會占用大量的線程資源溉躲。

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末,一起剝皮案震驚了整個濱河市益兄,隨后出現(xiàn)的幾起案子锻梳,更是在濱河造成了極大的恐慌,老刑警劉巖净捅,帶你破解...
    沈念sama閱讀 211,042評論 6 490
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件疑枯,死亡現(xiàn)場離奇詭異,居然都是意外死亡蛔六,警方通過查閱死者的電腦和手機荆永,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 89,996評論 2 384
  • 文/潘曉璐 我一進店門,熙熙樓的掌柜王于貴愁眉苦臉地迎上來国章,“玉大人具钥,你說我怎么就攤上這事∫菏蓿” “怎么了骂删?”我有些...
    開封第一講書人閱讀 156,674評論 0 345
  • 文/不壞的土叔 我叫張陵,是天一觀的道長。 經(jīng)常有香客問我宁玫,道長粗恢,這世上最難降的妖魔是什么? 我笑而不...
    開封第一講書人閱讀 56,340評論 1 283
  • 正文 為了忘掉前任欧瘪,我火速辦了婚禮眷射,結(jié)果婚禮上,老公的妹妹穿的比我還像新娘佛掖。我一直安慰自己妖碉,他們只是感情好,可當我...
    茶點故事閱讀 65,404評論 5 384
  • 文/花漫 我一把揭開白布苦囱。 她就那樣靜靜地躺著嗅绸,像睡著了一般。 火紅的嫁衣襯著肌膚如雪撕彤。 梳的紋絲不亂的頭發(fā)上,一...
    開封第一講書人閱讀 49,749評論 1 289
  • 那天猛拴,我揣著相機與錄音羹铅,去河邊找鬼。 笑死愉昆,一個胖子當著我的面吹牛职员,可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播跛溉,決...
    沈念sama閱讀 38,902評論 3 405
  • 文/蒼蘭香墨 我猛地睜開眼焊切,長吁一口氣:“原來是場噩夢啊……” “哼!你這毒婦竟也來了芳室?” 一聲冷哼從身側(cè)響起专肪,我...
    開封第一講書人閱讀 37,662評論 0 266
  • 序言:老撾萬榮一對情侶失蹤,失蹤者是張志新(化名)和其女友劉穎堪侯,沒想到半個月后嚎尤,有當?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體,經(jīng)...
    沈念sama閱讀 44,110評論 1 303
  • 正文 獨居荒郊野嶺守林人離奇死亡伍宦,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 36,451評論 2 325
  • 正文 我和宋清朗相戀三年芽死,在試婚紗的時候發(fā)現(xiàn)自己被綠了。 大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片次洼。...
    茶點故事閱讀 38,577評論 1 340
  • 序言:一個原本活蹦亂跳的男人離奇死亡关贵,死狀恐怖,靈堂內(nèi)的尸體忽然破棺而出卖毁,到底是詐尸還是另有隱情揖曾,我是刑警寧澤,帶...
    沈念sama閱讀 34,258評論 4 328
  • 正文 年R本政府宣布,位于F島的核電站翩肌,受9級特大地震影響模暗,放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜念祭,卻給世界環(huán)境...
    茶點故事閱讀 39,848評論 3 312
  • 文/蒙蒙 一兑宇、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧粱坤,春花似錦隶糕、人聲如沸。這莊子的主人今日做“春日...
    開封第一講書人閱讀 30,726評論 0 21
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽。三九已至株旷,卻和暖如春再登,著一層夾襖步出監(jiān)牢的瞬間,已是汗流浹背晾剖。 一陣腳步聲響...
    開封第一講書人閱讀 31,952評論 1 264
  • 我被黑心中介騙來泰國打工锉矢, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留,地道東北人齿尽。 一個月前我還...
    沈念sama閱讀 46,271評論 2 360
  • 正文 我出身青樓沽损,卻偏偏與公主長得像,于是被迫代替她去往敵國和親循头。 傳聞我的和親對象是個殘疾皇子绵估,可洞房花燭夜當晚...
    茶點故事閱讀 43,452評論 2 348

推薦閱讀更多精彩內(nèi)容