加鎖還是不加鎖，這是一個問題
雖說鎖是個好東西， 但是我們線程日常使用的都是互斥鎖，互斥，就是同一時刻只有獲得鎖的那個線程才有資格去操作共享資源， 別的線程都阻塞住了，被放到了一個叫鎖池(Lock pool)的地方，什么事情都干不了。
1 .前言
上次我說過， 我們這個線程的世界是個弱肉強食的地方， 大家為了爭搶資源大打出手，時不時鬧出些內存數據互相被覆蓋的事故， 給人類帶了無窮的煩惱。
后來線程元老院強勢出手， 發明了一種鎖的機制， 這才制止了內亂。 從此以后我們要訪問共享的資源(共享變量， 文件...)都得想辦法先申請到一把鎖才可以。
2 .互斥鎖
雖說鎖是個好東西， 但是我們線程日常使用的都是互斥鎖， 所謂互斥，就是同一時刻只有獲得鎖的那個線程才有資格去操作共享資源， 別的線程都阻塞住了，被放到了一個叫鎖池(Lock pool)的地方，什么事情都干不了。
比如說這個簡單的Sequence類吧， 有100個線程拼命地擠破頭去進入next()方法， 但由于synchronized的存在， 大家必須得獲得一把鎖才可以， 隔壁的小明運氣不錯， 獲得了操作系統的垂青， 喜滋滋的得到了寶貴的鎖， 進入了next()方法去做事了。
而我們剩下的99個線程大眼瞪小眼， 除了嘆口氣，感慨下人生之不如意十之八九， 還能干嘛?
老老實實地進入鎖池里待著去吧!
等到隔壁小明做完了事情， 美滋滋的拿著最新的value值出來以后， 我們這99個在鎖池里吹牛的線程一躍而起，去競爭那個剛剛被釋放的鎖。
但是下一個幸運兒是誰呢? 不知道?
有時候人類為了公平，會搞個隊列讓我們排好隊，先進先出。 但是我已經活了4.998秒，人生快走到了盡頭， 在這么長的人生里， 我體會到的真理是： 公平實在是個稀缺貨，不公平才是常態!
所以年輕人不要老是抱怨這個社會， 沒用的， 還是老老實實的奮斗吧。
3 .不要加鎖?
平淡的日子就這么過著， 有一天線程世界來了一個年輕人，自稱為小李, 他看著我們這么努力地奮斗著去爭搶那把鎖， 不由地嘲笑道： 你們真傻啊， 難道不知道不加鎖也能做事嗎?
我們愣了一下，人群中立刻發出一陣爆笑：哈哈哈， 這小子瘋了，沒有鎖豈不又回到互相覆蓋數據的日子了!
小李不甘示弱：你們這幫土老帽，把元老院的那幫老家伙的話當做圣旨， 豈不知天外有天， 人外有人， 這世界大得很吶!
這句話把我們鎮住了， 我小心翼翼地問： 那你說說，不加鎖怎么才能保證正確性呢?
“就拿你們的那個Sequence類來說吧， 不就是并發的更新內存中的一個值嗎， 可以這么分為三步來做：
1. 從內存中讀取value 值，假設為10， 我們把這個值稱為A
2. B = A+1 得到 B = 11
3. 用A 和 內存的值相比， 如果相等(就是說在過去的一段時間，沒人修改內存的值)， 那就把B的值(11)寫入內存, 如果不相等(就是說過去的一段時間， 有人修改了內存value 的值)， 意味著A已經不是最新值了， 那就放棄這次修改， 跳回第1步去”
我們面面相覷， 就這么簡單? 真的沒有加鎖啊。
隔壁的小明反應最快： 小李子， 你這第三步有問題啊， 你看需要讀內存吧，需要比較吧，還得寫入內存吧， 這不是一個原子操作， 在我們多線程并發執行的時候， 肯定會出問題!
小李說： “唉， 說你們老土吧， 你們還不服氣， 聽說過comare and swap 這個硬件指令沒有? 那個第三步其實就是一條硬件指令，保證原子執行。 在單個CPU上就不用說了，如果是有多個CPU， 這個指令甚至會鎖住總線， 確保同一時刻只有一個CPU能訪問內存!
這樣吧， 干脆寫成個指令： compareAndSwap(內存的值, A , B) , 這下子明白了吧? 還不明白? 估計是人類的語言你們聽起來不太明白， 來吧，給你們來點熟悉的代碼：”
看到了我們熟悉的代碼， 我的腦海飛速盤算：
假定我和小明都同時進入了這段代碼， 都讀到了內存的值A = 10 , 然后小明的時間片到了，只好退出CPU, 我則愉快的繼續執行。
對于我來說 A = 10 , B = 11, 然后我運行compareAndSwap ,我發現我的A值和內存值是相等的，于是就把新的值B寫入內存， 并且返回，退出next 函數， 收工回家。
等到小明再次被運行的時候， 由于他的初始值A也是10 ， 他也得到B = 11， 當他運行compareAndSwap 就發現A的值和內存不相等了(因為我改成了11) ， 那小明只好再次循環，獲得A = 11, B = 12 , 再次調用compareAndSwap ， 如果還是被別人搶了先， 小明只好再次循環, 從內存獲得A = 12 , B =13 .... 直到成功為止。
想到小明一直循環下去，累得要死的樣子， 我”邪惡“地笑了。
我抬起頭，正好和小明的目光相遇， 看到他不懷好意的樣子， 估計也是把我置于無限循環的想象中了。
4 .Java中的CAS
小李說： “Compare And Swap 這個詞太長了， 以后簡稱CAS，希望你們聽得懂。”
小明問道： “我們是Java 語言， 你那個讀取內存的值該怎么辦， 還有那個compareAndSwap 函數，我們實現不了啊?”
小李說：“你們Java 不是有JNI(Java native interface)嗎? 可以用C語言來實現， 然后在Java中封裝一下不就得了?”
“看看這個AtomicInteger, 他就代表了那個內存的值， 那個count.compareAndSet方法只有兩個參數， 實際上內存的值隱藏在了AtomicInteger當中，你們Java 不是喜歡面向對象嘛!”
我們仔細地審視這段代碼， 它根本沒有加鎖， 每個人都可以進入next()方法， 讀取數據，操作數據， 最后使用CAS來決定這次操作是否有效， 如果內存值被別人改過，那就再次循環嘗試。
小李總結到： “你們之前的synchronized 叫做悲觀鎖， 元老院太悲觀了，總是怕你們把事情搞砸，你看現在樂觀一點兒， 不也玩的挺好嘛! 每個線程都不用阻塞，不用在那個無聊的鎖池里待著。 要知道，阻塞，激活是一筆不小的開銷啊。”
5. CAS的擴展
使用非阻塞算法的線程越來越多， 小李趁熱打鐵，提供了一系列所謂Atomic的類：
- AtomicBoolean
- AtomicInteger
- AtomicLong
- AtomicIntegerArray
- AtomicLongArray
這些工具類都很好用， 大家非常喜歡， 只是我們發現小李的這些工具類只支持簡單的類型，對于一些復雜的數據結構，就不好使用CAS了，因為使用CAS需要頻繁的讀寫內存數據，并且做數據的比較， 如果數據結構很復雜， 那讀寫內存是不可承受之重，還不如最早的悲觀鎖呢!
小李胸有成竹， 馬上給出了改進： 不要比較數據啊， 只比較引用不就得了， 這里有一個AtomicReference, 拿去用吧。
我們向元老院做了推薦， 那些老家伙們可真是有兩把刷子， 立刻提出了一個我做夢都沒有想到的問題：
假設有兩個線程， 線程1 讀到內存的數值為 A , 然后時間片到期，撤出CPU。 線程2運行，線程2 也讀到了A , 把它改成了B， 然后又把B改成原來的值A , 簡單點說，修改的次序是 A -> B ->A 。 然后線程1開始運行， 它發現內存的值還是A , 完全不知道內存中已經被操作過。
我想了一下， 好像沒什么啊，不就是把數字改成了原來的值嗎?也沒什么影響。
可是小李卻陷入了沉思， 看來這是一個挺難的問題， 他口中念念有詞： 如果只是簡單的數字，那沒什么， 可是如果使用AtomicReference， 并且操作的是復雜的數據結構，就可能會出問題了。對了， 我可以用一個版本號來處理啊， 給每個放入AtomicReference的對象都加入一個version, 這樣以來盡管值相同， 也能區分開了! 嗯， 我就叫他AtomicStampedReference 吧。
元老院很滿意， 但是還是發了一個公告：
鑒于最近使用AtomicXXXX的線程越來越多， 元老院有責任提醒各位， 用這些類實現非阻塞算法是非常容易出錯的，在你自己實現之前， 看看元老院有沒有提供現成的類，例如： ConcurrentLinkedQueue。 如果非要自己寫，也得提交給元老院審查通過才可以使用。
6 .后記： Doug Lea
如果說要從Java 世界中找一個并發編程的大牛， 我想這個人非Doug Lea莫屬， 從JDK 1.5開始， Java 引入了一個非常著名的線程并發庫java.util.concurrent ， 由于其良好的抽象， 這個庫極大的降低了并發編程的難度， 其作者就是并發編程的權威Doug Lea， 他是紐約州立大學Oswego分校計算機科學系教授， JCP(Java Community Process)執行委員會成員，JSR166(并發編程)的主席 ， 文中的小李就是向Doug Lea致敬。
【本文為51CTO專欄作者“劉欣”的原創稿件，轉載請通過作者微信公眾號coderising獲取授權】
