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)系:
從上面的結(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)值杀捻。
put操作
查看JDK源碼put操作,為了線程安全蚓庭,在操作共享變量時必須加鎖致讥。put方法首先定位到Segment,然后在Segment里面進(jìn)行插入操作器赞。插入操作需要進(jìn)行兩個步驟垢袱,第一步判斷是否需要對Segment里的HashEntry數(shù)組進(jìn)行擴(kuò)容,第二步定位添加元素的位置港柜,然后將其放在HashEntry數(shù)組里请契。
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ā)生變化。
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個副本出來量承。
同時搬设,讀取元素操作非常簡單不需要鎖如下圖所示:
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é)了這些方法:
- 拋出異常:是指當(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)行分析:
- ArrayBlockQueue:一個由數(shù)組支持的有界阻塞隊(duì)列忠蝗。此隊(duì)列按 FIFO(先進(jìn)先出)原則對元素進(jìn)行排序。創(chuàng)建其對象必須明確大小漓拾,像數(shù)組一樣阁最。默認(rèn)情況下不保證訪問者公平的訪問隊(duì)列戒祠,即不會根據(jù)阻塞的先后順序來提供給訪問者。
- LinkedBlockQueue:一個可改變大小的阻塞隊(duì)列速种。此隊(duì)列按 FIFO(先進(jìn)先出)原則對元素進(jìn)行排序姜盈。創(chuàng)建其對象如果沒有明確大小,默認(rèn)值是Integer.MAX_VALUE配阵。
- PriorityBlockingQueue:類似于LinkedBlockingQueue馏颂,但其所含對象的排序不是FIFO,而是依據(jù)對象的自然排序順序或者是構(gòu)造函數(shù)所帶的Comparator決定的順序棋傍。
- SynchronousQueue:同步隊(duì)列救拉。同步隊(duì)列沒有任何容量,每個插入必須等待另一個線程移除瘫拣,反之亦然亿絮。即每一個put操作必須等待一個take操作,否則不能繼續(xù)添加元素麸拄。SynchronousQueue可以看成是一個傳球手派昧,負(fù)責(zé)把生產(chǎn)者線程處理的數(shù)據(jù)直接傳遞給消費(fèi)者線程。
- 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ì)列可用。
生產(chǎn)者往滿的隊(duì)列里添加元素時會阻塞住生產(chǎn)者
消費(fèi)者消費(fèi)空隊(duì)列的時候會阻塞消費(fèi)者
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