06.一文看懂並行程式設計中的鎖

大家好，我是王有志。關注王有志，一起聊技術，聊遊戲，從北漂生活談到國際風雲。

相信你經常會聽到讀鎖/寫鎖，公平鎖/非公平鎖，樂觀鎖/悲觀鎖等五花八門的鎖，那麼每種鎖有什麼用呢？它們又有什麼區別呢？今天我們就一起聊聊並行程式設計中的各種鎖。

關於鎖的理論，他們都問什麼？

問題其實不多，基本上都是圍繞著鎖的設計理論提問。常見的問題如下：

計算機中的鎖，它到底是什麼？

參照維基百科中鎖的解釋：

In computer science, a lock or mutex (from mutual exclusion) is a synchronization primitive: a mechanism that enforces limits on access to a resource when there are many threads of execution. A lock is designed to enforce a mutual exclusion concurrency control policy, and with a variety of possible methods there exists multiple unique implementations for different applications.

可以這麼理解：鎖用於保證並行環境中對共用資源存取的互斥，限制共用資源存取的同步機制。

Tips：

本文中存取操作既包含讀取變數，也包含修改變數；
不斷提到的共用資源在拓展內容中做了補充；
同步和互斥，可以回顧關於執行緒你必須知道的8個問題（下）；
mutex在電腦科學中被翻譯為互斥，互斥量，會大量出現。

畫一個鎖的簡易模型：

模型不難理解，獲取鎖的執行緒進入臨界區執行程式，存取共用資源，它描述了一種最簡單的互斥鎖模型。

Tips：臨界區源自於作業系統程序排程的概念，是存取共用資源的程式片段。

鎖的分類

我們把在並行程式設計中經常出現的鎖全部列出來：

讀鎖，S鎖，共用鎖，寫鎖，X鎖，獨佔鎖，排他鎖，讀寫鎖
公平鎖，非公平鎖
樂觀鎖，悲觀鎖
自旋鎖，阻塞鎖
可重入鎖，不可重入鎖

看到這麼多名字有沒有頭暈眼花？沒關係，我們透過現象給它們分類，或許能幫助你理解：

本質，指的是互斥與共用的本質；
- 互斥：寫鎖，X鎖，獨佔鎖，排他鎖；
- 共用：讀鎖，S鎖，共用鎖；
設計，指的是鎖的設計方式；
- 樂觀鎖，悲觀鎖；
- 讀寫鎖；
特性，指的是本質上新增的特性；
- 公平鎖，非公平鎖；
- 自旋鎖，阻塞鎖；
- 可重入鎖，不可重入鎖。

前面看到，鎖的基礎是提供執行緒間互斥的能力以保證存取共用資源的安全性，之後的發展中為了提升效能或適應不同場景而新增了各種各樣的特性。

除此之外，你還會聽過偏向鎖，輕量級鎖，重量級鎖，它們歸類到sychronized的狀態會比較合適，會在下一篇中詳細說明。至於分段鎖，我也將它歸類到鎖的設計中，具體的我們放到ConcurrentHashMap中討論。

Tips：

基於個人理解分類，只是為了更好的理解鎖的本質與特性，歡迎指正；
共用部分的劃分並不準確，因為共用鎖只與讀操作共用，與寫操作互斥；
特性是在本質的基礎上新增的，它們的關係像是車與改裝車的關係。

讀鎖，寫鎖和讀寫鎖

鎖是為了保證並行存取的互斥，但所有的場景都需要互斥嗎？

有時候，臨界區只有讀操作，使用互斥鎖的話就很呆。因此誕生了共用鎖，允許多個執行緒同時申請到共用鎖。不過共用鎖也限制了執行緒的操作範圍，持有共用鎖的執行緒只允許讀取資料。

讀寫鎖

實際上，單純使用共用鎖沒有太多意義，因為讀取操作不產生並行安全問題。但是對只有讀取操作的臨界區使用互斥鎖，有點「大材小用」，因此結合兩者產生了「共用-互斥鎖」，通常稱呼為讀寫鎖。

讀寫鎖的特點：

允許多個執行緒申請讀鎖；
如果讀鎖已經被申請，需要等待讀鎖釋放後才能申請寫鎖；
如果寫鎖已經被申請，需要等待寫鎖釋放後才能申請讀鎖。

總結一下：

換句話說，讀寫鎖中只有兩種情況多讀或一寫。

Tips：Java中提供了讀寫鎖ReentrantReadWriteLock，我們後面慢慢聊。

讀寫鎖的優缺點

相較於單純的互斥鎖，讀寫鎖保證了讀取的並行量，提高了程式的效能。但它真的那麼好嗎？

陳碩老師在《Linux多執行緒伺服器端程式設計》中提到了慎用讀寫鎖，並說道：

讀寫鎖（Readers-Writer lock，簡寫為rwlock）是個看上去很美的抽象。

並給出了4點理由：

開發過程中容易犯在持有read lock時修改資料的錯誤；
讀寫鎖的實現比互斥鎖複雜，如果控制粒度極小，互斥鎖可能更快；
如果讀鎖不允許升級為寫鎖，會和non-recursive mutex一樣，造成死鎖；
讀寫鎖會引起寫飢餓。

Tips：

recursive mutex和non-recursive mutex是POSIX規範的稱呼，我們通常稱為ReentrantLok和NonreentrantLock；
《Linux多執行緒伺服器端程式設計》的Keyword：Linux多執行緒伺服器端程式設計。

第1點和第2點比較容易理解，不過多解釋，第3點在ReentrantReadWriteLock的部分和大家解釋，我們今天來看第4點，讀寫鎖引起的寫飢餓。

如下，由於不斷的獲取讀鎖，導致執行緒t2雖然很早申請寫鎖，但要等到所有讀執行緒都執行後才能獲取到寫鎖，這就是寫飢餓。

Tips：ReentrantReadWriteLock存在寫飢餓的情況，Java 8雖然進行了增強，但不是對ReentrantReadWriteLock增強。

公平鎖與非公平鎖

接下來是按照特性分類了，先來看最容易理解的功能--公平性。不知道咋回事，想起來張麻子了~~

並行環境中，大量執行緒是瞬間湧入的，當執行到臨界區時，開始嘗試獲取互斥鎖，雖然看似是同時請求，但實際上還是有一丟丟時間差距。

公平鎖維護等待佇列，當執行緒嘗試獲取鎖時，如果等待佇列為空，或當前執行緒位於隊首，那麼執行緒就持有鎖，否則新增到隊尾，按照FIFO的順序出隊。

非公平鎖，執行緒直接嘗試獲取鎖，失敗後再進入等待佇列。

Tips：

不熟悉佇列的可以看我寫的另一個系列：資料結構：棧和佇列；
Java中ReentrantLock的「公平模式」和「非公平模式」的都藉助了AQS。

公平鎖與非公平鎖的比較

公平鎖嚴格按照申請順序獲取鎖，每個執行緒都有機會獲取鎖；非公平鎖允許直接搶佔，無需判斷等待佇列是否有等待執行緒。

對於非公平鎖來說，如果就是那麼「寸」，等待佇列隊首的執行緒每次嘗試獲取鎖時，都被其它執行緒「截胡」了，那麼佇列中的執行緒就永遠無法獲取鎖，這就是執行緒飢餓。

那麼非公平鎖有優點嗎？

等待佇列為空

以Java中ReentrantLock的公平鎖FairSync和非公平鎖NonfairSync加鎖過程為例：

根據演演算法複雜度分析，以圖中的內容來估算，FairSync的加鎖時間是NonfairSync的兩倍，加鎖速度上非公平鎖加鎖速度更快。

Tips：如果不熟悉演演算法複雜度，可以看預備知識：演演算法的複雜度分析。

等待佇列非空

等待佇列非空時，嘗試獲取公平鎖的執行緒進入等待佇列，輪到時喚醒該執行緒；對於非公平鎖來說，如果搶佔成功，直接執行程式，無需進入等待佇列後等待喚醒，如果搶佔失敗，則進入等待佇列。

最後，做個總結：

| / | 優點 | 缺點 |
| : -------- : | : ---------------------------------- : | :------------------------------: |
| 公平鎖 | 每個執行緒都有執行的機會 | 加鎖慢，可能需要額外的喚醒操作 |
| 非公平鎖 | 加鎖快，搶佔成功無需額外的喚醒操作 | 執行緒飢餓 |

悲觀鎖與樂觀鎖

我把悲觀鎖和樂觀鎖分到了鎖的設計類別中，我們先來了解悲觀鎖和樂觀鎖，再來看我這麼分類的理由。

什麼是悲觀鎖？

悲觀鎖（Pessimistic Locking）：認為並行存取共用資源總是會發生修改，因此在進入臨界區前進行加鎖操作，退出臨界區後進行解鎖。

根據上面的描述，幾乎所有的鎖都可以劃分到悲觀鎖的範疇。那麼共用鎖算不算悲觀鎖？

我認為共用鎖（讀鎖，S鎖，共用鎖）也是悲觀鎖，有2個理由：

共用鎖總是在存取臨界區前加鎖，退出後解鎖；
共用鎖只與讀操作共用，與寫操作互斥。

悲觀鎖是計算機領域最常見的同步機制，資料庫中的行鎖，表鎖，Java中的synchronized等都是悲觀鎖。

什麼是樂觀鎖？

樂觀鎖（Optimistic Locking）：認為並行存取共用資源不會發生修改，因此無需加鎖操作，真正發生修改準備提交資料前，會檢查該資料是否被修改。

與悲觀鎖相反，樂觀鎖認為並行存取不會發生修改，因此允許執行緒「長驅直入」，如果發生了修改要怎麼處理？

如何實現樂觀鎖？

樂觀鎖（樂觀並行控制，Optimistic Concurrency Control）由孔祥重教授（華裔，臺灣省出生的美國電腦科學家）提出，併為樂觀鎖設計了4個階段：

讀取，讀取資料，系統派發時間戳；
修改，修改資料，此時修改尚未提交；
校驗，校驗資料是否被其他讀取或寫入；
提交/回滾：未發生修改/寫入，提交資料，發生修改/寫入，即產生衝突時，回滾資料。

如果按照以上4個步驟實現樂觀鎖會有什麼問題麼？

如果在校驗和提交階段發生執行緒切換，會導致值的覆蓋。通常了為了保證校驗和提交操作的原子性，會藉助CPU提供的CAS並行原語來保證。

什麼是CAS？

CAS（Compare And Swap）指的是比較並替換，雖然是兩個操作，但卻是一條原子指令。

Tips：《Intel® 64 and IA-32 Architectures Software Developer’s Manual》2A中描述，Intel和IA-32架構使用的是CMPXCHG指令，即Compare and Exchange。

CAS操作3個數：

V，記憶體原值
A，預期原值
B，修改的值

其過程可以簡單描述為：

讀取需要修改的記憶體原值V；
比較記憶體原值V與預期原值A；
如果$V=A$，則修改V的值為B，否則不執行任何操作。

好了，目前解決了原子操作的問題，是不是可以愉快的實現樂觀鎖了？別急，我們再看另一種情況：

ABA問題

執行緒t1，t2和t3都讀取V的值，執行緒t2和t3先後修改V的值，V的變化軌跡：$A \rightarrow B \rightarrow A$。

雖然對於執行緒t1來說，修改的還是A，看起來好像沒有問題，但真正的ABA問題可比上面的複雜多了。我們舉個例子，假設有單向連表實現的棧$A \rightarrow B \rightarrow C \rightarrow D$：

解決ABA問題

最常用的手段是，為資料新增版本，比較資料的同時也要對版本號進行比較，修改資料時，同時更新版本號。

這裡舉個最常用的通過資料庫實現的樂觀鎖：

-- 查詢庫存資訊
select book_id, book_count, version from book where book_id = #{bookId};

-- 程式計算扣減庫存操作
......

-- 更新資料庫庫存
update book set book_count = #{bookCount}, version = version + 1 where book_id = #{bookId} and version = #{version}

Tips：Java提供了AtomicStampedReference來解決CAS帶來的ABA問題。

選擇樂觀鎖還是悲觀鎖？

通常，我們認為樂觀鎖的效能優於悲觀鎖，因為悲觀鎖的粒度會更粗，而樂觀鎖的競爭只發生在產生衝突時。

一般，會在讀多寫少的場景使用樂觀鎖，這樣減少加鎖/解鎖的次數，提高系統的吞吐量；而在寫多讀少的場景選擇悲觀鎖，如果經常產生衝突，樂觀鎖需要不斷的回滾（或其他方式），反而會降低效能。

另外，CAS指令只保證對一個共用變數的原子操作，當需要操作多個共用變數時，無法保證多個CAS操作的原子性。

最後，樂觀鎖需要自行實現，往往設計邏輯比較複雜，如果本身業務邏輯就已經很複雜了，那麼首要保證的是正確的業務邏輯，然後再考慮效能。

Tips：CAS是實現樂觀鎖的關鍵技術，但使用CAS並不等於使用樂觀鎖。例如ReentrantLock中使用了compareAndSet，但它是悲觀鎖。

自旋鎖和阻塞鎖

自旋鎖（Spin Lock）和阻塞鎖都是互斥鎖，我們所說的自旋和阻塞是對未搶佔到鎖的執行緒來說的：

自旋鎖中，執行緒未獲取鎖，不會進入休眠，而是不斷的嘗試獲取鎖；
阻塞鎖中，執行緒未獲取鎖，進入休眠狀態。

也就是說，阻塞鎖存在休眠到喚醒的過程，而自旋鎖只需要執行自旋邏輯。什麼場景該使用自旋鎖呢？

假設我們只有兩個執行緒t1和t2，t1進入臨界區，t2進入自旋，t2自旋的耗時應當與t1在臨界區的執行時間相近。

如果臨界區執行時間非常短，自旋耗時遠小於一次休眠與喚醒，此時使用自旋鎖的的代價會比阻塞鎖小很多。如果臨界區執行時間很長，與其讓自旋鎖耗盡CPU時間片，倒不如讓給其它執行緒使用。

我們實現一個簡單的自旋邏輯：

int  count = 0;
while(!lock.tryLock() && count < 10) {
	count ++;
}

Tips：單核伺服器就不要使用自旋鎖了。

可重入鎖和不可重入鎖

可重入鎖指的是同一執行緒可以對其多次加鎖，可重入鎖的特性和遞迴很相似，因此POSIX中稱這種鎖為遞迴鎖。

不可重入鎖會造成死鎖？

為什麼要實現鎖的可重入呢？假設有不可重入鎖lock，我們執行一段遞迴刪除資料夾下檔案的邏輯：

public void deleteFile(File directory) {
	if(lock.tryLock()) {
		File[] files = directory.listFiles();
		for (File subFile : files) {
			if(file.isDirectory()) {
				deleteFile(subFile);
			} else {
				file.delete();
			}
		}
	}
}

當遇到第一個子資料夾時，執行lock.tryLock會被阻塞，因為lock已經被持有了，這時候就產生了死鎖。

可重入鎖的實現一般要在內部維護計數器，每次進入可重入鎖時計數器加1，退出時計數器減1，進入和退出的次數要匹配。

結語

到這裡就把Java常用到的鎖的基礎知識和設計思想介紹完了，希望通過這篇文章，小夥伴對這些五花八門的鎖有更清晰的認知。

其實總結起來，鎖的基礎功能是保證並行的安全（可以理解為互斥），再此基礎上誕生的公平鎖/非公平鎖，悲觀鎖/樂觀鎖，自旋鎖/阻塞鎖的目的是為了提升鎖的效能，而可重入鎖的出現是為了解決重入帶來的死鎖問題（或許是為了方便開發者解決死鎖的問題）。

大部分的鎖都能在Java中找到它們的實現：

公平鎖：ReentrantLock#FairSync
非公平鎖：ReentrantLock#NonfairSync
悲觀鎖：synchronized，ReentrantLock
可重入鎖：synchronized，ReentrantLock
讀寫鎖：ReentrantReadWriteLock

我會在未來的文章中和大家分享對它們設計思想的理解。

拓展內容

補充一些計算機基礎的相關內容。

共用記憶體

並行程式設計領域存在兩種基本通訊模型模型：

共用記憶體（Shared Memory），指的是多線（進）程執行在不同核心上，任何核心快取上的資料修改後，重新整理到主記憶體後，其他核心更新自己的快取；
訊息傳遞（Message Passing）

傳統的物件導向程式語言採用的是共用記憶體的方式進行執行緒間通訊，如：Java，C++等，但Java可以通過Akka實現Actor模型的訊息傳遞。

近年來的「攪局者」（存疑）Go語言則是訊息傳遞的忠實擁躉，在《Go Proverbs》中第一句便是：

Don't communicate by sharing memory, share memory by communicating.

不要通過共用記憶體來通訊，要通過通訊來共用記憶體。

Tips：近年來「程式語言哲學」比較普遍，前有Python大名鼎鼎的《The Zen of Python》，後來者Go也搞了《Go Proverbs》。

好了，今天就到這裡了，Bye~~