java并發(fā)編程——容器

1. 同步容器

在早期的JDK中放航,同步容器有兩種現(xiàn)成的實(shí)現(xiàn)盗飒,Vector和Hashtable嚷量,可以直接new對象獲取逆趣;在JDK1.2中蝶溶,引入了同步封裝類,可以由Collections.synchronizedXxxx等方法創(chuàng)建宣渗;這兩種方式底層實(shí)現(xiàn)都是通過將狀態(tài)封裝起來抖所,并對每個公有方法進(jìn)行同步,使得每次只有一個線程能訪問容器的狀態(tài)痕囱。
以Hashtable為例查看jdk源碼實(shí)現(xiàn)如下所示:

public synchronized V remove(Object key) {}
public synchronized V put(K key, V value) {}
public synchronized V get(Object key) {}

可以看到Hashtable與普通HashMap的區(qū)別就是相應(yīng)方法都添加了synchronized進(jìn)行同步田轧,這個保證了容器操作的安全。但是鞍恢,所有對容器狀態(tài)的訪問都串行化傻粘,這種代價就是嚴(yán)重降低了并發(fā)性,多個線程競爭的時候帮掉,吞吐量嚴(yán)重降低弦悉。

2. 并發(fā)容器

前面敘述了同步容器使用的局限性,JDK5.0開始增加了ConcurrentHashMap等并發(fā)容器來代替同步容器提高多線程并發(fā)情況下的性能旭寿。下面就其中典型并發(fā)容器使用和實(shí)現(xiàn)進(jìn)行介紹:

2.1 ConcurrentHashMap

2.1.1ConcurrentHashMap設(shè)計(jì)

ConcurrentHashMap采用了分段鎖的設(shè)計(jì)警绩,只有在同一個分段內(nèi)才存在競態(tài)關(guān)系,不同的分段鎖之間沒有鎖競爭盅称。相比于對整個Map加鎖的設(shè)計(jì)肩祥,分段鎖大大的提高了高并發(fā)環(huán)境下的處理能力后室。
ConcurrentHashMap中主要實(shí)體類就是三個:ConcurrentHashMap(整個Hash表),Segment(桶),HashEntry(節(jié)點(diǎn))混狠,對應(yīng)下圖可以看出之間的關(guān)系:

ConcurrentHashMap內(nèi)部構(gòu)成

從上面的結(jié)構(gòu)我們可以了解到岸霹,ConcurrentHashMap定位一個元素的過程需要進(jìn)行兩次Hash操作,第一次Hash定位到Segment将饺,第二次Hash定位到元素所在的鏈表的頭部贡避。由于不同的Segment有各自的鎖,理想情況下ConcurrentHashMap可以最高同時支持Segment數(shù)量大小的寫操作予弧。

2.1.2ConcurrentHashMap常用方法分析
get操作

查看JDK源碼整個get操作過程不需要加鎖刮吧,主要分兩步第一步進(jìn)行再散列,并根據(jù)再散列值定位到Segment掖蛤;第二步找到對應(yīng)HashEntry并遍歷鏈表找到具體對應(yīng)值杀捻。


get操作
put操作

查看JDK源碼put操作,為了線程安全蚓庭,在操作共享變量時必須加鎖致讥。put方法首先定位到Segment,然后在Segment里面進(jìn)行插入操作器赞。插入操作需要進(jìn)行兩個步驟垢袱,第一步判斷是否需要對Segment里的HashEntry數(shù)組進(jìn)行擴(kuò)容,第二步定位添加元素的位置港柜,然后將其放在HashEntry數(shù)組里请契。


put操作
size操作

前面兩個操作都是在單個segment中進(jìn)行的,但是size操作是在多個segment中進(jìn)行夏醉。ConcurrentHashMap的size操作也采用了一種比較巧的方式姚糊,來盡量避免對所有的Segment都加鎖。ConcurrentHashMap的做法是先嘗試2次通過不鎖住Segment的方式來統(tǒng)計(jì)各個Segment大小授舟,如果統(tǒng)計(jì)過程中,容器count發(fā)生了變化贸辈,則采用加鎖的方式來統(tǒng)計(jì)所有Segment大小释树。這里ConcurrentHashMap通過判斷modCount是否變化來判斷容器在計(jì)算size過程中是否發(fā)生變化。

size操作

2.2 CopyOnWrite

CopyOnWrite即寫入時復(fù)制的容器擎淤,每次修改的時奢啥,都會創(chuàng)建并重新發(fā)布一個新的容器副本,然后新的容器副本里添加元素嘴拢,添加完元素之后桩盲,再將原容器的引用指向新的容器。
CopyOnWrite容器也是一種讀寫分離的思想席吴,讀和寫不同的容器赌结,由于當(dāng)前容器不會被修改所以支持無鎖并發(fā)讀取捞蛋。

2.2.1 CopyOnWriteArrayList的實(shí)現(xiàn)原理

作為CopyOnWrite思想具體實(shí)現(xiàn)類CopyOnWriteArrayList,首先看下源碼如何實(shí)現(xiàn)元素添加修改柬姚∧馍迹可以發(fā)現(xiàn)在添加的時候是需要加鎖的,否則多線程寫的時候會Copy出N個副本出來量承。

CopyOnWriteArrayList添加元素

同時搬设,讀取元素操作非常簡單不需要鎖如下圖所示:

CopyOnWriteArrayList讀取元素.png
2.2.2使用場景和注意點(diǎn)

CopyOnWrite并發(fā)容器用于讀多寫少的并發(fā)場景。比如白名單撕捍,黑名單拿穴,商品類目的訪問和更新的場景。
使用注意點(diǎn):

  • 使用批量添加忧风。因?yàn)槊看翁砑幽萜髅看味紩M(jìn)行復(fù)制,所以減少添加次數(shù)阀蒂,可以減少容器的復(fù)制次數(shù)该窗。
  • 根據(jù)實(shí)際需求初始化容器大小,減少擴(kuò)容帶來的開銷蚤霞。
  • 該容器不適合存儲占據(jù)內(nèi)存大的大對象由于復(fù)制的原因容易引起FullGC
  • CopyOnWrite容器只能保證數(shù)據(jù)的最終一致性酗失,不能保證數(shù)據(jù)的實(shí)時一致性。所以如果你希望寫入的的數(shù)據(jù)昧绣,馬上能讀到规肴,請不要使用CopyOnWrite容器。

2.3 并發(fā)隊(duì)列ConcurrentLinkedQueue

在并發(fā)編程中需要使用線程安全的隊(duì)列有兩種實(shí)現(xiàn)方式一種是使用阻塞算法夜畴,另一種是使用非阻塞算法拖刃。使用阻塞算法的隊(duì)列可以用一個鎖(入隊(duì)和出隊(duì)用同一把鎖)或兩個鎖(入隊(duì)和出隊(duì)用不同的鎖)等方式來實(shí)現(xiàn),而非阻塞的實(shí)現(xiàn)方式則可以使用循環(huán)CAS的方式來實(shí)現(xiàn)贪绘。并發(fā)隊(duì)列ConcurrentLinkedQueue通過非阻塞方式實(shí)現(xiàn)兑牡。

2.3.1 ConcurrentLinkedQueue設(shè)計(jì)

ConcurrentLinkedQueue 的非阻塞算法實(shí)現(xiàn)主要可概括為下面幾點(diǎn):

  • 使用 CAS 原子指令來處理對數(shù)據(jù)的并發(fā)訪問,這是非阻塞算法得以實(shí)現(xiàn)的基礎(chǔ)税灌。
  • head/tail 并非總是指向隊(duì)列的頭 / 尾節(jié)點(diǎn)均函,也就是說允許隊(duì)列處于不一致狀態(tài)。 這個特性把入隊(duì) /出隊(duì)時菱涤,原本需要一起原子化執(zhí)行的兩個步驟分離開來苞也,從而縮小了入隊(duì) /出隊(duì)時需要原子化更新值的范圍到唯一變量。這是非阻塞算法得以實(shí)現(xiàn)的關(guān)鍵粘秆。
  • 以批處理方式來更新head/tail如迟,從整體上減少入隊(duì) / 出隊(duì)操作的開銷。

ConcurrentLinkedQueue由head節(jié)點(diǎn)和tail節(jié)點(diǎn)組成,每個節(jié)點(diǎn)(Node)由節(jié)點(diǎn)元素(item)和指向下一個節(jié)點(diǎn)的引用(next)組成殷勘,節(jié)點(diǎn)與節(jié)點(diǎn)之間就是通過這個next關(guān)聯(lián)起來此再,從而組成一張鏈表結(jié)構(gòu)的隊(duì)列。默認(rèn)情況下head節(jié)點(diǎn)存儲的元素為空劳吠,tail節(jié)點(diǎn)等于head節(jié)點(diǎn)引润。

3. 阻塞隊(duì)列

阻塞隊(duì)列(BlockingQueue)與普通隊(duì)列的區(qū)別在于添加了兩個附加操作:當(dāng)隊(duì)列是空的時,從隊(duì)列中獲取元素的操作將會被阻塞痒玩;當(dāng)隊(duì)列是滿時淳附,往隊(duì)列里添加元素的操作會被阻塞。
BlockingQueue最終會有四種狀況蠢古,拋出異常奴曙、返回特殊值、阻塞草讶、超時洽糟,下表總結(jié)了這些方法:

BlockingQueue方法總結(jié).png
  • 拋出異常:是指當(dāng)阻塞隊(duì)列滿時候,再往隊(duì)列里插入元素堕战,會拋出IllegalStateException("Queue full")異常坤溃。
  • 返回特殊值:插入方法會返回是否成功,成功則返回true嘱丢。移除方法薪介,則是從隊(duì)列里拿出一個元素,如果沒有則返回null越驻。
  • 一直阻塞:當(dāng)阻塞隊(duì)列滿時汁政,如果生產(chǎn)者線程往隊(duì)列里put元素,隊(duì)列會一直阻塞生產(chǎn)者線程缀旁,直到拿到數(shù)據(jù)记劈,或者響應(yīng)中斷退出。當(dāng)隊(duì)列空時并巍,消費(fèi)者線程試圖從隊(duì)列里take元素目木,隊(duì)列也會阻塞消費(fèi)者線程,直到隊(duì)列可用懊渡。
  • 超時退出:當(dāng)阻塞隊(duì)列滿時嘶窄,隊(duì)列會阻塞生產(chǎn)者線程一段時間,如果超過一定的時間距贷,生產(chǎn)者線程就會退出。

3.1 JDK提供阻塞隊(duì)列

JDK7提供了7個阻塞隊(duì)列實(shí)現(xiàn)類吻谋,下面就其中常用類進(jìn)行分析:

  1. ArrayBlockQueue:一個由數(shù)組支持的有界阻塞隊(duì)列忠蝗。此隊(duì)列按 FIFO(先進(jìn)先出)原則對元素進(jìn)行排序。創(chuàng)建其對象必須明確大小漓拾,像數(shù)組一樣阁最。默認(rèn)情況下不保證訪問者公平的訪問隊(duì)列戒祠,即不會根據(jù)阻塞的先后順序來提供給訪問者。
  2. LinkedBlockQueue:一個可改變大小的阻塞隊(duì)列速种。此隊(duì)列按 FIFO(先進(jìn)先出)原則對元素進(jìn)行排序姜盈。創(chuàng)建其對象如果沒有明確大小,默認(rèn)值是Integer.MAX_VALUE配阵。
  3. PriorityBlockingQueue:類似于LinkedBlockingQueue馏颂,但其所含對象的排序不是FIFO,而是依據(jù)對象的自然排序順序或者是構(gòu)造函數(shù)所帶的Comparator決定的順序棋傍。
  4. SynchronousQueue:同步隊(duì)列救拉。同步隊(duì)列沒有任何容量,每個插入必須等待另一個線程移除瘫拣,反之亦然亿絮。即每一個put操作必須等待一個take操作,否則不能繼續(xù)添加元素麸拄。SynchronousQueue可以看成是一個傳球手派昧,負(fù)責(zé)把生產(chǎn)者線程處理的數(shù)據(jù)直接傳遞給消費(fèi)者線程。
  5. DelayQueue:一個支持延時獲取元素的無界阻塞隊(duì)列拢切。隊(duì)列使用PriorityQueue來實(shí)現(xiàn)蒂萎。隊(duì)列中的元素必須實(shí)現(xiàn)Delayed接口,在創(chuàng)建元素時可以指定多久才能從隊(duì)列中獲取當(dāng)前元素失球。只有在延遲期滿時才能從隊(duì)列中提取元素岖是。

3.2 ArrayBlockQueue實(shí)現(xiàn)原理

以ArrayBlockingQueue為例我們查看下JDK源碼可以發(fā)現(xiàn)其主要使用Condition來實(shí)現(xiàn)通知模——當(dāng)生產(chǎn)者往滿的隊(duì)列里添加元素時會阻塞住生產(chǎn)者实苞,當(dāng)消費(fèi)者消費(fèi)了一個隊(duì)列中的元素后豺撑,會通知生產(chǎn)者當(dāng)前隊(duì)列可用。

ArrayBlockingQueue初始化

生產(chǎn)者往滿的隊(duì)列里添加元素時會阻塞住生產(chǎn)者


put操作

消費(fèi)者消費(fèi)空隊(duì)列的時候會阻塞消費(fèi)者

take操作

3.3 阻塞隊(duì)列的應(yīng)用

阻塞隊(duì)列支持生產(chǎn)者——消費(fèi)者這種設(shè)計(jì)模式黔牵,當(dāng)數(shù)據(jù)產(chǎn)生時候聪轿,生產(chǎn)者把數(shù)據(jù)放到隊(duì)列當(dāng)中,而當(dāng)消費(fèi)者準(zhǔn)備處理數(shù)據(jù)時猾浦,將從隊(duì)列中獲取數(shù)據(jù)陆错。生產(chǎn)者不需要知道消費(fèi)者的標(biāo)識或數(shù)量,只需要將數(shù)據(jù)放入隊(duì)列即可金赦。同樣音瓷,消費(fèi)者也不需要知道生產(chǎn)者是誰。 阻塞隊(duì)列簡化了生產(chǎn)者——消費(fèi)者設(shè)計(jì)的實(shí)現(xiàn)過程夹抗,支持任意數(shù)量的生產(chǎn)者和消費(fèi)者绳慎。

參考

http://www.cnblogs.com/dolphin0520/p/3932905.html
http://www.importnew.com/22007.html
http://ifeve.com/java-copy-on-write/
http://ifeve.com/java-blocking-queue/
http://blog.csdn.net/ghsau/article/details/8108292

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末,一起剝皮案震驚了整個濱河市,隨后出現(xiàn)的幾起案子杏愤,更是在濱河造成了極大的恐慌靡砌,老刑警劉巖,帶你破解...
    沈念sama閱讀 211,123評論 6 490
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件珊楼,死亡現(xiàn)場離奇詭異通殃,居然都是意外死亡,警方通過查閱死者的電腦和手機(jī)厕宗,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 90,031評論 2 384
  • 文/潘曉璐 我一進(jìn)店門画舌,熙熙樓的掌柜王于貴愁眉苦臉地迎上來,“玉大人媳瞪,你說我怎么就攤上這事骗炉。” “怎么了蛇受?”我有些...
    開封第一講書人閱讀 156,723評論 0 345
  • 文/不壞的土叔 我叫張陵突梦,是天一觀的道長呐籽。 經(jīng)常有香客問我踪旷,道長贩挣,這世上最難降的妖魔是什么? 我笑而不...
    開封第一講書人閱讀 56,357評論 1 283
  • 正文 為了忘掉前任把将,我火速辦了婚禮轻专,結(jié)果婚禮上,老公的妹妹穿的比我還像新娘察蹲。我一直安慰自己请垛,他們只是感情好,可當(dāng)我...
    茶點(diǎn)故事閱讀 65,412評論 5 384
  • 文/花漫 我一把揭開白布洽议。 她就那樣靜靜地躺著宗收,像睡著了一般。 火紅的嫁衣襯著肌膚如雪亚兄。 梳的紋絲不亂的頭發(fā)上混稽,一...
    開封第一講書人閱讀 49,760評論 1 289
  • 那天,我揣著相機(jī)與錄音审胚,去河邊找鬼匈勋。 笑死,一個胖子當(dāng)著我的面吹牛膳叨,可吹牛的內(nèi)容都是我干的洽洁。 我是一名探鬼主播,決...
    沈念sama閱讀 38,904評論 3 405
  • 文/蒼蘭香墨 我猛地睜開眼菲嘴,長吁一口氣:“原來是場噩夢啊……” “哼诡挂!你這毒婦竟也來了碎浇?” 一聲冷哼從身側(cè)響起,我...
    開封第一講書人閱讀 37,672評論 0 266
  • 序言:老撾萬榮一對情侶失蹤璃俗,失蹤者是張志新(化名)和其女友劉穎,沒想到半個月后悉默,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體城豁,經(jīng)...
    沈念sama閱讀 44,118評論 1 303
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 36,456評論 2 325
  • 正文 我和宋清朗相戀三年抄课,在試婚紗的時候發(fā)現(xiàn)自己被綠了唱星。 大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點(diǎn)故事閱讀 38,599評論 1 340
  • 序言:一個原本活蹦亂跳的男人離奇死亡跟磨,死狀恐怖间聊,靈堂內(nèi)的尸體忽然破棺而出,到底是詐尸還是另有隱情抵拘,我是刑警寧澤哎榴,帶...
    沈念sama閱讀 34,264評論 4 328
  • 正文 年R本政府宣布,位于F島的核電站僵蛛,受9級特大地震影響尚蝌,放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜充尉,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 39,857評論 3 312
  • 文/蒙蒙 一飘言、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧驼侠,春花似錦姿鸿、人聲如沸。這莊子的主人今日做“春日...
    開封第一講書人閱讀 30,731評論 0 21
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽。三九已至相速,卻和暖如春碟渺,著一層夾襖步出監(jiān)牢的瞬間,已是汗流浹背突诬。 一陣腳步聲響...
    開封第一講書人閱讀 31,956評論 1 264
  • 我被黑心中介騙來泰國打工苫拍, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留,地道東北人旺隙。 一個月前我還...
    沈念sama閱讀 46,286評論 2 360
  • 正文 我出身青樓绒极,卻偏偏與公主長得像,于是被迫代替她去往敵國和親蔬捷。 傳聞我的和親對象是個殘疾皇子垄提,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 43,465評論 2 348

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