并發編程與鎖的底層原理

背景：

并發編程，多核、多線程的情況下，線程安全性問題都是一個無法回避的難題。雖然我們可以用到CAS,互斥鎖，消息隊列，甚至分布式鎖來解決，但是對于鎖的底層實現，這次分享，我們想更深入的來分析和探討鎖的底層原理，以便更好地理解和掌握并發編程。

大綱：

1.并發編程與鎖

2.緩存和一致性協議MESI

3.CPU/緩存與鎖

4.常見鎖總結

1 并發編程與鎖

我們寫的各種應用系統，像網絡編程，基本上都是并發編程，不論是多進程還是多線程，亦或是協程、隊列的方式，也都是并發編程的范疇。并發編程中，在多核操作系統中，多線程的時候，就會出現 線程安全性 問題，有的也說 并發安全性 問題。這種問題，都是因為對共享變量的并發讀寫引起的數據不一致問題。所以，在并發編程中，就會經常用到鎖，當然也可能使用隊列或者單線程的方式來處理共享數據。

我們先來還原一下具體的問題，然后再用不同的方法來處理它們。

線程安全性問題1

代碼中共享變量num是一個簡單的計數器，main主線程啟動了兩個協程，分別循環一萬次對num進行遞增操作。正常情況下，預期的結果應該是1w+1w=2w，但是，在并發執行的情況下，最終的結果只有10891，離2w差的好多。

典型應用場景：

1 庫存數量扣減

2 投票數量遞增

并發安全性問題：

num+ +是三個操作（讀、改、寫），不滿足原子性

并發讀寫全局變量，線程不安全

線程安全性問題2

代碼中共享變量list作為一個數據集合，由兩個協程并發的循環append數據進去。同樣是每個協程執行一萬次，正常情況下，預期的list長度應該是2w，但是，在并發執行下，結果卻可能連1w都不到。

具體的原因，大家可以思考下，為什么并發執行的情況下，2個協程，竟然list長度還小于1w呢？

典型應用場景：

1 發放優惠券

2 在線用戶列表

并發安全性問題：

append(list, i) 內部是一個復雜的數組操作函數

并發讀寫全局變量，線程不安全

問題修復

方法一： 通過WaitGroup將兩個協程分開執行，第一個執行完成再執行第二個，避免并發執行，串行化兩個任務。

方法二： 通過互斥鎖，在數字遞增的前后加上鎖的處理，數值遞增操作時互斥。

方法三： 針對int64的數字指針遞增操作，可以利用atomic.AddInt64原子遞增方法來處理。

當然還會有更多的實現方法，但是內部的實現原理也都類似，原子操作，避免對共享數據的并發讀寫。

并發編程的幾個基礎概念

概念1：并發執行不一定是并行執行。

概念2：單核CPU可以并發執行，不能并行執行。

概念3：單進程、單線程，也可以并發執行。

并行是 同一時刻 的多任務處理，并發是一個 時間段 內（1秒、1毫秒）的多任務處理。

區別并發和并行，多核的并行處理涉及到多核同時讀寫一個緩存行，所以很容易出現數據的臟讀和臟寫；單核的并發處理中因為任務內部的中間變量，所以有可能存在臟寫的情況。

鎖的作用

• 避免并行運算中，共享數據讀寫的安全性問題。

• 并行執行中，在鎖的位置，同時只能有一個程序可以獲得鎖，其他程序不能獲得鎖。

• 鎖的出現，使得并行執行的程序在鎖的位置串行化執行。

• 多核、分布式運算、并發執行，才會需要鎖。

不用鎖，也可以實現同樣效果？

單線程串行化執行，隊列式，CAS。

——不要通過共享內存來通信，而應該通過通信來共享內存

鎖的底層實現類型

1 鎖內存總線 ，針對內存的讀寫操作，在總線上控制，限制程序的內存訪問

2 鎖緩存行 ，同一個緩存行的內容讀寫操作，CPU內部的高速緩存保證一致性

鎖 ，作用在一個對象或者變量上。現代CPU會優先在高速緩存查找，如果存在這個對象、變量的緩存行數據，會使用鎖緩存行的方式。否則，才使用鎖總線的方式。

速度 ，加鎖、解鎖的速度，理論上就是高速緩存、內存總線的讀寫速度，它的效率是非常高的。而出現效率問題，是在產生沖突時的串行化等待時間，再加上線程的上下文切換，讓多核的并發能力直線下降。

2 緩存和一致性協議MESI

英文首字母縮寫，也就是英文環境下的術語、俚語、成語，新人理解和學習有難度，但是，掌握好了既可以省事，又可以縮小文化差距。

另外就是對英文的異形化，也類似漢字的變形體，“表醬紫”，“藍瘦香菇”，老外是很難懂得，反之一樣。

MESI“生老病死”緩存行的四種狀態

• M: modify 被修改，數據有效，cache和內存不一致

• E: exclusive 獨享，數據有效，cache與內存一致

• S: shared 共享，數據有效，cache與內存一致，多核同時存在

• I: invalid 數據無效

• F: forward 向前(intel)，特殊的共享狀態，多個S狀態，只有一個F狀態，從F高速緩存接受副本

當內核需要某份數據時，而其它核有這份數據的備份時，本cache既可以從內存中導入數據，也可以從其它cache中導入數據(Forward狀態的cache)。

四種狀態的更新路線圖

高效的狀態： E, S

低效的狀態： I, M

這四種狀態，保證CPU內部的緩存數據是一致的，但是，并不能保證是強一致性。

每個cache的控制器不僅知道自己的讀寫操作，而且也要監聽其它cache的讀寫操作。

緩存的意義

1 時間局部性：如果某個數據被訪問，那么不久還會被訪問

2 空間局部性：如果某個數據被訪問，那么相鄰的數據也很快可能被訪問

局限性：空間、速度、成本

更大的緩存容量，需要更大的成本。更快的速度，需要更大的成本。均衡緩存的空間、速度、成本，才能更有市場競爭力，也是現在我們看到的情況。當然，隨著技術的升級，成本下降，空間、速度也就能繼續穩步提高了。

緩存行，64Byte的內容

緩存行的存儲空間是64Byte（字節），也就是可以放64個英文字母，或者8個int64變量。

注意偽共享的情況——56Byte共享數據不變化，但是8Byte的數據頻繁更新，導致56Byte的共享數據也會頻繁失效。

解決方法：緩存行的數據對齊，更新頻繁的變量獨占一個緩存行，只讀的變量共享一個緩存行。

3 CPU/緩存與鎖

鎖的底層實現原理，與CPU、高速緩存有著密切的關系，接下來一起看看CPU的內部結構。

CPU與計算機結構

內核獨享寄存器、L1/L2，共享L3。在早先時候只有單核CPU，那時只有L1和L2，后來有了多核CPU，為了效率和性能，就增加了共享的L3緩存。

多顆CPU通過QPI連接。再后來，同一個主板上面也可以支持多顆CPU，多顆CPU也需要有通信和控制，才有了QPI。

內存讀寫都要通過內存總線。CPU與內存、磁盤、網絡、外設等通信，都需要通過各種系統提供的系統總線。

CPU流水線

CPU流水線，里面還有異步的LoadBuffer,

Store Buffer, Invalidate Queue。這些緩沖隊列的出現，更多的異步處理數據，提高了CPU的數據讀寫性能。

CPU為了保證性能，默認是寬松的數據一致性。

編譯器、CPU優化

• 編譯器優化：重排代碼順序，優先讀操作（讀有更好的性能，因為cache中有共享數據，而寫操作，會讓共享數據失效）

• CPU優化：指令執行亂序（多核心協同處理，自動優化和重排指令順序）

編譯器、CPU屏蔽

• 優化屏蔽：禁止編譯器優化。按照代碼邏輯順序生成二進制代碼，volatile關鍵詞

• 內存屏蔽：禁止CPU優化。防止指令之間的重排序，保證數據的可見性，store barrier, load barrier, full barrier

• 寫屏障：阻塞直到把Store Buffer中的數據刷到Cache中

• 讀屏障：阻塞直到Invalid Queue中的消息執行完畢

• 全屏障：包括讀寫屏障，以保證各核的數據一致性

Go語言中的Lock指令就是一個內存全屏障同時禁止了編譯器優化。

x86的架構在CPU優化方面做的相對少一些，只是針對“寫讀”的順序才可能調序。

加鎖，加了些什么？

• 禁止編譯器做優化（加了優化屏蔽）

• 禁止CPU對指令重排（加了內存屏蔽）

• 針對緩存行、內存總線上的控制

• 沖突時的任務等待隊列

4 常見鎖總結

最后，我們一起來看看常見的自旋鎖、互斥鎖、條件鎖、讀寫鎖的實現邏輯，以及在Go源碼中，是如何來實現的CAS/atomic.AddInt64和Mutext.Lock方法的。

自旋鎖

只要沒有鎖上，就不斷重試。

如果別的線程長期持有該鎖，那么你這個線程就一直在 while while while 地檢查是否能夠加鎖，浪費 CPU 做無用功。

優點：不切換上下文；

不足：燒CPU；

適用場景：沖突不多，等待時間不長的情況下，或者少次數的嘗試自旋。

互斥鎖

操作系統負責線程調度，為了實現「鎖的狀態發生改變時再喚醒」就需要把鎖也交給操作系統管理。

所以互斥器的加鎖操作通常都需要涉及到上下文切換，操作花銷也就會比自旋鎖要大。

優點：簡單高效；

不足：沖突等待時的上下文切換；

適用場景：絕大部分情況下都可以直接使用互斥鎖。

條件鎖

它解決的問題不是「互斥」，而是「等待」。

消息隊列的消費者程序，在隊列為空的時候休息，數據不為空的時候（條件改變）啟動消費任務。

條件鎖的業務針對性更強。

讀寫鎖

內部有兩個鎖，一個是讀的鎖，一個是寫的鎖。

如果只有一個讀者、一個寫者，那么等價于直接使用互斥鎖。

不過由于讀寫鎖需要額外記錄讀者數量，花銷要大一點。

也可以認為讀寫鎖是針對某種特定情景（讀多寫少）的「優化」。

但個人還是建議忘掉讀寫鎖，直接用互斥鎖。

適用場景：讀多寫少，而且讀的過程時間較長，可以通過讀寫鎖，減少讀沖突時的等待。

無鎖操作CAS

Compare And Swap 比較并交換，類似于將 num+ + 的三個指令合并成一個指令 CMPXCHG，保證了操作的原子性。

為了保證順序一致性和數據強一致性，還需要有一個LOCK指令。  

源碼，參見 runtime/internal/atomic/asm_amd64.s

LOCK指令的作用就是禁止編譯器優化，同時加上內存全屏障，可以保證 LOCK指令 之后的一個指令執行時的數據強一致性和可見性。

數字的原子遞增操作 atomic.AddInt64

在原始指針數字的基礎上，原子性遞增 delta 數值，并且返回遞增后的結果值。

源碼1，參見sync/atomic/asm.s

XADDQ 數據交換，數值相加，寫入目標數據

ADDQ 數值相加，寫入目標數據

在XADDQ之前加上LOCK指令，保證這個指令執行時的數據強一致性和可見性。

源碼2，參見runtime/internal/atomic/asm_amd64.s

互斥鎖操作 sync.Mutex.Lock

源碼，參見 sync/mutex.go

大概的源碼處理邏輯如下：

1 通過CAS操作來競爭鎖的狀態 &m.state；

2 沒有競爭到鎖，先主動自旋嘗試獲取鎖runtime_canSpin 和 runtime_doSpin (原地燒CPU)；

3 自旋嘗試失敗，再次CAS嘗試獲取鎖；

4 runtime_SemacquireMutex 鎖請求失敗,進入休眠狀態,等待信號喚醒后重新開始循環；

5 m.state等待隊列長度（復用的int32位數字，第一位是鎖的狀態，后31位是鎖的等待隊列長度計數器）。

以上便是這次分享的全部內容，有不足和紕漏的地方，還請指教，謝謝 ~

 

來自：https://mp.weixin.qq.com/s/DX_GsBq31-cemADrqQKfqw?utm_source=tuicool&utm_medium=referral