面試必備之樂觀鎖與悲觀鎖

何謂悲觀鎖與樂觀鎖

    樂觀鎖對應于生活中樂觀的人總是想着事情往好的方向發展，悲觀鎖對應于生活中悲觀的人總是想着事情往壞的方向發展。這兩種人各有優缺點，不能不以場景而定說一種人好于另外一種人。

悲觀鎖

總是假設最壞的情況，每次去拿資料的時候都認為别人會修改，是以每次在拿資料的時候都會上鎖，這樣别人想拿這個資料就會阻塞直到它拿到鎖（共享資源每次隻給一個線程使用，其它線程阻塞，用完後再把資源轉讓給其它線程）。傳統的關系型資料庫裡邊就用到了很多這種鎖機制，比如行鎖，表鎖等，讀鎖，寫鎖等，都是在做操作之前先上鎖。Java中synchronized和ReentrantLock等獨占鎖就是悲觀鎖思想的實作。

樂觀鎖

總是假設最好的情況，每次去拿資料的時候都認為别人不會修改，是以不會上鎖，但是在更新的時候會判斷一下在此期間别人有沒有去更新這個資料，可以使用版本号機制和CAS算法實作。樂觀鎖适用于多讀的應用類型，這樣可以提高吞吐量，像資料庫提供的類似于write_condition機制，其實都是提供的樂觀鎖。在Java中java.util.concurrent.atomic包下面的原子變量類就是使用了樂觀鎖的一種實作方式CAS實作的。

兩種鎖的使用場景

從上面對兩種鎖的介紹，我們知道兩種鎖各有優缺點，不可認為一種好于另一種，像樂觀鎖适用于寫比較少的情況下（多讀場景），即沖突真的很少發生的時候，這樣可以省去了鎖的開銷，加大了系統的整個吞吐量。但如果是多寫的情況，一般會經常産生沖突，這就會導緻上層應用會不斷的進行retry，這樣反倒是降低了性能，是以一般多寫的場景下用悲觀鎖就比較合适。

樂觀鎖常見的兩種實作方式

    樂觀鎖一般會使用版本号機制或CAS算法實作。

1. 版本号機制

一般是在資料表中加上一個資料版本号version字段，表示資料被修改的次數，當資料被修改時，version值會加一。當線程A要更新資料值時，在讀取資料的同時也會讀取version值，在送出更新時，若剛才讀取到的version值為目前資料庫中的version值相等時才更新，否則重試更新操作，直到更新成功。

舉一個簡單的例子：

假設資料庫中帳戶資訊表中有一個 version 字段，目前值為 1 ；而目前帳戶餘額字段（ balance ）為 $100 。當需要對賬戶資訊表進行更新的時候，需要首先讀取version字段。

    操作員 A 此時将其讀出（ version=1 ），并從其帳戶餘額中扣除 $50（ $100-$50 ）。

    在操作員 A 操作的過程中，操作員B 也讀入此使用者資訊（ version=1 ），并從其帳戶餘額中扣除 $20 （ $100-$20 ）。

    操作員 A 完成了修改工作，送出更新之前會先看資料庫的版本和自己讀取到的版本是否一緻，一緻的話，就會将資料版本号加1（ version=2 ），連同帳戶扣除後餘額（ balance=$50 ），送出至資料庫更新，此時由于送出資料版本大于資料庫記錄目前版本，資料被更新，資料庫記錄 version 更新為 2 。

    操作員 B 完成了操作，送出更新之前會先看資料庫的版本和自己讀取到的版本是否一緻，但此時比對資料庫記錄版本時發現，操作員 B 送出的資料版本号為 2 ，而自己讀取到的版本号為1 ，不滿足 “ 目前最後更新的version與操作員第一次讀取的版本号相等 “ 的樂觀鎖政策，是以，操作員 B 的送出被駁回。

這樣，就避免了操作員 B 用基于 version=1 的舊資料修改的結果覆寫操作員A 的操作結果的可能。

2. CAS算法

即compare and swap（比較與交換），是一種有名的無鎖算法。無鎖程式設計，即不使用鎖的情況下實作多線程之間的變量同步，也就是在沒有線程被阻塞的情況下實作變量的同步，是以也叫非阻塞同步（Non-blocking Synchronization）。CAS算法涉及到三個操作數

    需要讀寫的記憶體值 V

    進行比較的值 A

    拟寫入的新值 B

當且僅當 V 的值等于 A時，CAS通過原子方式用新值B來更新V的值，否則不會執行任何操作（比較和替換是一個原子操作）。一般情況下是一個自旋操作，即不斷的重試。

樂觀鎖的缺點

    ABA 問題是樂觀鎖一個常見的問題

1 ABA 問題

如果一個變量V初次讀取的時候是A值，并且在準備指派的時候檢查到它仍然是A值，那我們就能說明它的值沒有被其他線程修改過了嗎？很明顯是不能的，因為在這段時間它的值可能被改為其他值，然後又改回A，那CAS操作就會誤認為它從來沒有被修改過。這個問題被稱為CAS操作的 "ABA"問題。

JDK 1.5 以後的 AtomicStampedReference 類就提供了此種能力，其中的 compareAndSet 方法就是首先檢查目前引用是否等于預期引用，并且目前标志是否等于預期标志，如果全部相等，則以原子方式将該引用和該标志的值設定為給定的更新值。

2 循環時間長開銷大

自旋CAS（也就是不成功就一直循環執行直到成功）如果長時間不成功，會給CPU帶來非常大的執行開銷。 如果JVM能支援處理器提供的pause指令那麼效率會有一定的提升，pause指令有兩個作用，第一它可以延遲流水線執行指令（de-pipeline）,使CPU不會消耗過多的執行資源，延遲的時間取決于具體實作的版本，在一些處理器上延遲時間是零。第二它可以避免在退出循環的時候因記憶體順序沖突（memory order violation）而引起CPU流水線被清空（CPU pipeline flush），進而提高CPU的執行效率。

3 隻能保證一個共享變量的原子操作

CAS 隻對單個共享變量有效，當操作涉及跨多個共享變量時 CAS 無效。但是從 JDK 1.5開始，提供了AtomicReference類來保證引用對象之間的原子性，你可以把多個變量放在一個對象裡來進行 CAS 操作.是以我們可以使用鎖或者利用AtomicReference類把多個共享變量合并成一個共享變量來操作。

CAS與synchronized的使用情景

    簡單的來說CAS适用于寫比較少的情況下（多讀場景，沖突一般較少），synchronized适用于寫比較多的情況下（多寫場景，沖突一般較多）

    對于資源競争較少（線程沖突較輕）的情況，使用synchronized同步鎖進行線程阻塞和喚醒切換以及使用者态核心态間的切換操作額外浪費消耗cpu資源；而CAS基于硬體實作，不需要進入核心，不需要切換線程，操作自旋幾率較少，是以可以獲得更高的性能。

    對于資源競争嚴重（線程沖突嚴重）的情況，CAS自旋的機率會比較大，進而浪費更多的CPU資源，效率低于synchronized。

補充： Java并發程式設計這個領域中synchronized關鍵字一直都是元老級的角色，很久之前很多人都會稱它為 “重量級鎖” 。但是，在JavaSE 1.6之後進行了主要包括為了減少獲得鎖和釋放鎖帶來的性能消耗而引入的 偏向鎖 和 輕量級鎖 以及其它各種優化之後變得在某些情況下并不是那麼重了。synchronized的底層實作主要依靠 Lock-Free 的隊列，基本思路是 自旋後阻塞，競争切換後繼續競争鎖，稍微犧牲了公平性，但獲得了高吞吐量。線上程沖突較少的情況下，可以獲得和CAS類似的性能；而線程沖突嚴重的情況下，性能遠高于CAS。

梅花香自古寒來