本文打算寫一些和鎖有關的東西，談一談我對鎖的原理和實現(xiàn)的理解，主要包含以下方面
- 信號量
- 互斥量
- 條件變量
同步與互斥
其實同步與互斥都是計算機科學里面概念性的東西，它們和什么編程語言、操作系統(tǒng)其實都沒什么關系。很多人會混淆這兩個概念，但是其實這兩個概念并不一樣(其實也不深奧，我們在寫代碼的時候肯定都用到過這兩種概念性的東西)
互斥
這個概念大家應該都清楚，就是說一個資源在任意一個時刻只能被一個進程/線程持有
同步
我們先來看下wikipedia上是怎么解釋同步的
同步（英語：Synchronization），指在一個系統(tǒng)中所發(fā)生的事件（event），之間進行協(xié)調(diào)，在時間上出現(xiàn)一致性與統(tǒng)一化的現(xiàn)象。在系統(tǒng)中進行同步，也被稱為及時（in time）、同步化的（synchronous、in sync）。
其實就是說，在多進程/多線程里面，所有的操作都是并行的，而且進程/線程的調(diào)度都是由操作系統(tǒng)完成的，那么假如在進程A中有操作a，進程B中有操作b，那a和b的執(zhí)行順序并不是確定的，同步的語義就是指保證一定的執(zhí)行順序，比如保證在b的執(zhí)行前a已經(jīng)執(zhí)行完。仔細考慮一下這種語義，想要實現(xiàn)同步，就必須要防止出現(xiàn)競態(tài)，所以必然使用互斥的特點，同時為了實現(xiàn)有序性，肯定會用到和條件變量性質(zhì)一樣的東西（注意，條件變量是Linux里面的一個概念，后面會講到，但是注意到它是和操作系統(tǒng)強相關的，是Linux內(nèi)核提供的一個接口，它和互斥量/信號量不是一個級別的東西)
信號量和互斥量
概要
信號量和互斥量經(jīng)常被人們混淆，但是其實信號量和互斥量是用來解決不一樣的問題的，也就是它們的設計思想是不一樣的
- 信號量是為了解決同步問題
- 互斥量是為了解決互斥問題
用代碼舉個例子(一些"形象"的例子往往具有迷惑性)：在這里我假設你已經(jīng)知道了信號量的機制，如果你確實忘了，那可以看下面我從別處搬過來的信號量的機制
這個例子是用來計算c = a + b的，但是get_a()、get_b()、calcalate_c()在不同的進程/線程中執(zhí)行，我們希望保證在計算c之前已經(jīng)執(zhí)行過calculate_a()和calculate_b()，以保證得到預期的結果，這也就是我們的同步需求
int a, b, c;
//may process in Application A
void get_a() {
a = calculate_a();
semaphore_increase();//函數(shù)封裝，內(nèi)部調(diào)用信號量的V操作
}
//may process in Application B
void get_b() {
b = calculate_b();
semaphore_increase();
}
//may process in Appication C
void calculate_c() {
semaphore_decrease();//函數(shù)封裝，內(nèi)部調(diào)用信號量的P操作
semaphore_decrease();
c = get_a() + get_b();
}
如果實在看不懂，可以稍后回來再看下這個例子，通過這樣的代碼我們可以保證得到預期的效果，達到最終邏輯上的順序
信號量
概念
信號量是一個整數(shù)，為了方便，我們把信號量計作S，信號量有兩個原語，即P操作和V操作，打死都要記住，一定要記住P操作和V操作都是原子操作，到底如何實現(xiàn)P、V操作，這是操作系統(tǒng)需要考慮的，同時需要硬件/CPU指令集支持，下文會詳細介紹有關內(nèi)容
P操作：
- S減1；
- 若S減1后仍大于或等于零，則進程繼續(xù)執(zhí)行；
- 若S減1后小于零，則該進程被阻塞后進入與該信號相對應的隊列中，然后轉進程調(diào)度
V操作：
- S加1；
- 若相加結果大于零，則進程繼續(xù)執(zhí)行；
- 若相加結果小于或等于零，則從該信號的等待隊列中喚醒一等待進程，然后再返回原進程繼續(xù)執(zhí)行或轉進程調(diào)度
有一點很重要，信號量的操作只應該由內(nèi)核去進行
例子：當信號量最大值為1
上面的PV操作可能很多同學都是似懂非懂，那讓我們看個例子，當信號量最大值為1時：
- 如果有三個線程/進程 A、B、C，都想要執(zhí)行P操作，又因為P操作是原子的，那么ABC都執(zhí)行了P(且沒有進程執(zhí)行了V操作)，那信號量S將會是-2，而且后執(zhí)行P操作的兩個現(xiàn)場全部都要被加入到sleep進程隊列中去
- 當成功執(zhí)行P操作而且沒有被掛起的進程執(zhí)行了V操作之后，S變成了-1，這時候V操作還需要去sleep隊列中去喚醒某個進程，至于到底喚醒哪一個，這取決于操作系統(tǒng)進程的調(diào)度方式了
- 然后重復上面的第二步直到S等于1
仔細看下上面的步驟，這不就是鎖嗎？
根據(jù)這個例子，你可能更容易理解這句話：
S大于等于零時代表可供并發(fā)進程使用的資源實體數(shù)，當S小于零時則表示正在等待使用臨界區(qū)的進程數(shù)。
不信的話各位同學可以比對上面的例子去理解一下這句話的含義
這個例子其實也就是很多人所說的，當信號量最大值為1(或者說不需要信號量的計數(shù)能力時)，這種簡化了功能的信號量就被稱為互斥量。因為沒有了技術能力，互斥量只有兩種狀態(tài)0/1。需要注意的是，這種信號量只是互斥量的一種實現(xiàn)方式，在概念上來講，二者并沒有直接的關系(或許從一開始互斥量是從信號量演化而來的，但是后來互斥量被單獨拉成一個概念)，互斥量有很多種實現(xiàn)方式(因為互斥量很簡單)。有關互斥量的東西下文還會詳細說一下
實現(xiàn)
很多同學會疑惑，信號量這么牛X，不就是在于PV操作是原子的嗎？那它到底怎么保證的原子的操作啊？
其實不管什么樣的功能/需求，到最后是一堆指令的集合，實現(xiàn)相應功能，PV操作的原子性也必然是這樣的。想要實現(xiàn)原子操作，就需要指令集的支持，比如在x86指令集上，lock指令前綴就能實現(xiàn)原子操作。在介紹lock指令前綴之前我們先仔細想一下原子性的本質(zhì)是什么
原子性
在這里我就不貼概念了，簡單且不嚴謹?shù)恼f，原子性就是在邏輯上一系列的指令都由CPU一次執(zhí)行完畢，中間不發(fā)生進程/線程切換，但是記住，這只是邏輯上的，仔細想一想，只要與這一坨指令相關的內(nèi)存數(shù)據(jù)在CPU執(zhí)行過程中不被其他進程/線程進行讀寫訪問，那你操作系統(tǒng)kernel再怎么切換，最終結果看起來依舊是原子的，也就是說只要相關數(shù)據(jù)的讀寫訪問是互斥的那么表現(xiàn)出來的特征就是原子的
舉個例子，如果我們希望i = i + 1是原子操作，那其實我們只需要讓i = i + 1的讀寫訪問是互斥的不就ok了？
lock指令前綴
根據(jù)上面的分析，我們很希望如果有某種指令可以鎖住某一特定的地址空間，那就太完美了?？墒窃谟布用鎭碚f，只針對某一個特定的內(nèi)存地址太難了，但是比較簡單的是鎖住內(nèi)存總線(聽起來太狠了，實際上確實代價比較大) — 這就是lock指令做的事情，不過在后來的處理器中，intel為了減少開銷，lock指令并不一定每次都會鎖住總線，而是通過緩存鎖和緩存一致性協(xié)議去完成這個一樣的功能
lock 指令前綴只可以修飾部分指令，還有一些其他的規(guī)則，本文不再詳細列舉，僅列舉一些可以修飾的指令：
ADD, ADC, AND, BTC, BTR, BTS, CMPXCHG, CMPXCH8B,CMPXCHG16B, DEC, INC, NEG, NOT, OR, SBB, SUB, XOR, XADD, XCHG
緩存鎖
剛才我們提到了，老一些的處理器上，lock指令前綴可以設置一個LOCK信號，鎖住內(nèi)存總線，讓共享內(nèi)存只被一個CPU獨占，這樣的話，會阻塞其他所有的CPU訪問共享內(nèi)存，效率很低，所以在后來的CPU版本上，lock指令前綴不再簡單粗暴的鎖住總線，而是采用緩存鎖，所謂的緩存鎖，其實就是當所訪問的數(shù)據(jù)在CPU的緩存(L1、L2)中時，即命中緩存時，如果命中的緩存行處于獨占的狀態(tài)(MESI里的E/M)且命中的緩存行只有一行，則可以直接執(zhí)行該指令，然后利用緩存一致性協(xié)議，去保證邏輯上的原子性，也就是說當不命中緩存(即訪問數(shù)據(jù)不在CPU緩存中)或者命中的緩存不在同一個緩存行中時，再或者CPU不支持緩存鎖時，lock指令前綴依舊會在總線上聲明LOCK信號，從而鎖住總線
注意，在我的理解里面，緩存鎖不是單純的依賴緩存一致性，因為簡單的MESI并不能保證原子性/互斥性，所以注意上面的表述：如果命中的緩存行處于獨占的狀態(tài)，則可以直接執(zhí)行，也就是是說不處于獨占的狀態(tài)，需要一些額外的操作，具體的在下面介紹了MESI協(xié)議之后我會說一下我的想法
緩存一致性
上面提及了緩存鎖主要依賴于緩存一致性協(xié)議，其實有關緩存一致性協(xié)議的東西可以寫很多很多，這里我試著盡量把這一部分講清楚
先來考慮一下為什么需要緩存一致性：在多核處理器中，每個CPU有自己的cache(L1和L2)，還有共享內(nèi)存(L3、主存)，因為CPU的處理速度遠遠高于IO速度，所以高速緩存對于提高CPU的利用率和吞吐量來說是必要的，這樣對于頻繁訪問的數(shù)據(jù)，CPU可以在自己的高速緩存(L1、L2)中進行讀寫，但是這樣就引入了一些問題：
- 兩個及以上個CPU同時訪問相同的內(nèi)存地址，就會出現(xiàn)難以預期的后果，比如兩個CPU同時執(zhí)行i++，其中i = 1，在兩個CPU執(zhí)行完之后，i可能等于2，這里可以多考慮一下指令執(zhí)行的五個周期(取指、譯碼、執(zhí)行、訪存、寫回)，不熟悉的同學自己去找下吧，這個如果在寫進來就要累死了
- 現(xiàn)代處理器一般都采用回寫的方式寫回臟數(shù)據(jù)：臟數(shù)據(jù)簡單來說就是緩存中被修改了的數(shù)據(jù)，之所以稱之為"臟"，是因為緩存中的數(shù)據(jù)和共享內(nèi)存中的數(shù)據(jù)不一致。而回寫是指當修改了緩存中的數(shù)據(jù)時，不立即寫回到共享內(nèi)存，而是在之后的某個時間點寫回到共享內(nèi)存?；貙懙姆绞郊哟罅司彺嬉恢滦缘膹碗s性。
注意，上述提到的共享內(nèi)存是指所有CPU所共享的內(nèi)存，按照目前的計算機結構，共享內(nèi)存一般是指L3和主存。
MESI協(xié)議是一個簡單的緩存一致性協(xié)議，根據(jù)MESI協(xié)議衍生出了其他一些緩存一致性協(xié)議，這里我們只討論一下MESI：MESI是代表了緩存數(shù)據(jù)的四種狀態(tài)的首字母，分別是Modified、Exclusive、Shared、Invalid，即MESI是一個很好的狀態(tài)機(以下來自[1])
- M(Modified)：被修改的。處于這一狀態(tài)的數(shù)據(jù)，只在本CPU中有緩存數(shù)據(jù)，而其他CPU中沒有。同時其狀態(tài)相對于內(nèi)存中的值來說，是已經(jīng)被修改的，且沒有更新到內(nèi)存中。
- E(Exclusive)：獨占的。處于這一狀態(tài)的數(shù)據(jù)，只有在本CPU中有緩存，且其數(shù)據(jù)沒有修改，即與內(nèi)存中一致。
- S(Shared)：共享的。處于這一狀態(tài)的數(shù)據(jù)在多個CPU中都有緩存，且與內(nèi)存一致。
- I(Invalid)：要么已經(jīng)不在緩存中，要么它的內(nèi)容已經(jīng)過時。為了達到緩存的目的，這種狀態(tài)的段將會被忽略。一旦緩存段被標記為失效，那效果就等同于它從來沒被加載到緩存中。
有了狀態(tài)機，其實更需要的是根據(jù)不同的狀態(tài)對緩存中的數(shù)據(jù)進行監(jiān)聽，這樣才能達到我們期望的緩存一致性(以下借鑒自[1])
- 一個處于M狀態(tài)的緩存行，必須時刻監(jiān)聽所有試圖讀取該緩存行對應的主存地址的操作，如果監(jiān)聽到，則必須在此操作執(zhí)行前把其緩存行中的數(shù)據(jù)寫回CPU。
- 一個處于S狀態(tài)的緩存行，必須時刻監(jiān)聽使該緩存行無效或者獨享該緩存行的請求，如果監(jiān)聽到，則必須把其緩存行狀態(tài)設置為I。
- 一個處于E狀態(tài)的緩存行，必須時刻監(jiān)聽其他試圖讀取該緩存行對應的主存地址的操作，如果監(jiān)聽到，則必須把其緩存行狀態(tài)設置為S。
- 只有E和M可以進行寫操作而且不需要額外操作，如果想對S狀態(tài)的緩存字段進行寫操作，那必須先發(fā)送一個RFO(Request-For-Ownership)廣播，該廣播可以讓其他CPU的緩存中的相同數(shù)據(jù)的字段實效，即變成Invalid狀態(tài)
問題回歸
我們現(xiàn)在回到我們一開始的問題 — 緩存鎖，也許有的同學會產(chǎn)生和我一樣的疑問，這種緩存一致性協(xié)議怎么能保證數(shù)據(jù)訪問的原子性呢？
網(wǎng)上一些博客描述的是直接通過緩存一致性就可以保證原子性，我認為這并不嚴謹，因為我理解的單單依賴緩存一致性協(xié)議無法達到原子性，比如兩個CPU同時執(zhí)行ADD [%eax], 1這個指令，而且二者訪存階段有交集(就是說CPU A還未執(zhí)行到寫回，CPU B也執(zhí)行到了訪存)，單單依靠MESI，A和B的緩存行狀態(tài)全都是S，依舊不是互斥的，這是多核并行引入的問題，因為指令的執(zhí)行必然是連續(xù)的，CPU只有執(zhí)行完一個指令才能完成上下文切換，但是在多核環(huán)境下，必須把一個指令拆分為多個步驟去分析。上述問題在單核環(huán)境下不存在。同時注意到我說的是ADD指令，不是i = i+1;
我覺得更準確的描述應該是上面提到的(這只是我自己的理解，因為我沒有去看intel的指令手冊): 如果執(zhí)行l(wèi)ock前綴指令前，相關的數(shù)據(jù)命中緩存且在一個緩存行中，那就鎖定這個數(shù)據(jù)，其他CPU無法訪問(讀/寫)，然后再利用緩存一致性協(xié)議，當發(fā)生寫操作之后，其他所有的緩存中全部變成Invalid，就解決了上述問題
有關MESI的實現(xiàn)
這是和硬件強相關的事情了，我就簡單提及一下：
MESI中有各種監(jiān)聽，這種監(jiān)聽的實現(xiàn)大部分是通過窺探的方式實現(xiàn)的，簡單來說就是，所有的CPU和共享內(nèi)存?zhèn)鬏敂?shù)據(jù)都使用一條總線，CPU的緩存不只在與共享內(nèi)存發(fā)生數(shù)據(jù)傳輸?shù)臅r候才訪問總線，而是實時監(jiān)聽總線上的數(shù)據(jù)情況，任何CPU的緩存與共享內(nèi)存發(fā)生的任何數(shù)據(jù)傳輸都可以被任意一個CPU監(jiān)聽到，所以可以實現(xiàn)上述MESI各種監(jiān)聽
注意，共用的總線是CPU及其緩存和共享內(nèi)存(L3、主存)之間的，CPU和CPU自己的高速緩存是不使用這個內(nèi)存總線的
互斥量
或許從一開始互斥量是從信號量演化而來的，但是后來互斥量被單獨拉成一個概念，因為互斥量足夠?qū)崿F(xiàn)互斥鎖，而且互斥量的概念也足夠簡單
概念
互斥量是一個二元的變量，0代表解鎖(可以獲取)，1代表加鎖(已經(jīng)被其他進程獲取)。如果一個進程試圖mutex_lock時mutex為1，那這個進程應該被阻塞，直到獲得了mutex的進程自己調(diào)用mutex_unlock，其他進程才有機會進入臨界區(qū)
注意
- mutex_unlock應該由獲取了mutex的進程自己去unlock，即釋放互斥量
- 互斥量的概念很簡單，甚至可以在用戶空間就可以實現(xiàn)互斥量的功能，但是信號量只能被內(nèi)核調(diào)度
互斥量的實現(xiàn)
互斥量因為只有兩種狀態(tài)，所以它有很多種實現(xiàn)方式，但無論什么樣的實現(xiàn)方式，都只要內(nèi)部封裝，然后對外暴露接口lock和unlock就可以了
- 通過最大值為1的信號量實現(xiàn)，很明顯，這種實現(xiàn)方式是在內(nèi)核空間
- 通過TSL指令實現(xiàn)
ENTER_REGION:
TSL REGISTER, MUTEX
CMP RESGITER, #0
JNE ENTER_REGION
RET
TSL A, B：把B復制到寄存器A并且把B設置為一個非零值，注意，這個命令會鎖住內(nèi)存總線，保證原子性
把MUTEX復制到REGISTER中后，把REGISTER和0做比較，如果不是0，則循環(huán)，也就是忙等，這就是自旋鎖，很明顯，這種實現(xiàn)方式完全可以在用戶空間就可以實現(xiàn)
- 通過XCHG指令實現(xiàn)：和TSL很相似，不再贅述
再次強調(diào)，上面都是不同的實現(xiàn)方式，到底操作系統(tǒng)底層怎么實現(xiàn)，請去參考各個操作系統(tǒng)的kernel
多說一些，忙等和休眠
當某個進程獲取不到互斥量/信號量時，該進程都應該以某種方式等待互斥量/信號量的釋放，上面我們看到有兩種
- 忙等(自旋)：不停的循環(huán)，直到資源ready。這樣的缺點就是如果資源的釋放需要一定的時間，那么就要占用大量的CPU時間；優(yōu)點就是在資源很快釋放的情況下，不用發(fā)生內(nèi)核態(tài)和用戶態(tài)的切換，也不用進行sleep和喚醒，節(jié)省了時間開銷。
- 休眠(阻塞)：進程/線程被阻塞，進入休眠(sleep)。基本原理也就是操作系統(tǒng)內(nèi)核維護一個休眠的集合，然后當資源被釋放之后，操作系統(tǒng)根據(jù)自己的調(diào)度策略，選擇其一進行喚醒。這樣的優(yōu)缺點和忙等(自旋)正好相反。
我們都知道，在絕大多數(shù)情況下，都是采用休眠的方式來等待的；但是在某些情況下也會采用自旋的方式等待，比如Java的Hotspot就引入了自旋鎖，在一定的情況下會采用自旋的方式等待，這是一種優(yōu)化方式，用來在執(zhí)行臨界區(qū)耗時不長的情況下避免內(nèi)核態(tài)的調(diào)度，關于Hotspot的自旋鎖在這里先不講了
條件變量
如果各位同學真的理解了以上內(nèi)容(我覺得各位同學也應該理解，哈哈)，條件變量其實很簡單，條件變量的級別本來就不夠和信號量和互斥量相提并論，但是網(wǎng)上很多人喜歡把它和互斥量和信號量放在一起說，其實這樣徒增了我們的理解難度
概念
其實沒有概念，條件變量就是linux提供的一個編程接口，又有一些人喜歡把條件變量叫做條件鎖，其實說的都是一種東西。條件變量其實就是解決了一個問題：一個進程等待某個變量成立，另外一個線程對這個變量進行修改，而這個問題必須避免發(fā)生競態(tài)，所以往往必須要使用一個mutex，從而使得等待和修改都在同一個互斥量的臨界區(qū)里。這樣說可能很多人理解還是有偏差的，我們直接列出來Linux提供的接口，我們只看最關鍵的兩個接口函數(shù)
- int pthread_cond_wait(pthread_cond_t *cond,pthread_mutex_t *mutex); 使當前進程休眠，并且會釋放這個mutex，并且在被喚醒時重新獲取mutex
- int pthread_cond_signal(pthread_cond_t *cond); 喚醒等待對應條件變量的進程
這只是其中兩個接口函數(shù)，怎么初始化條件變量各位同學自行查閱有關資料
想一下下面的例子(偽代碼+部分C)
int flag = 0;
//cond是一個條件變量 mutex是一個互斥量
//process in thread/application A
void process_a() {
mutex_lock(mutex);
while (!flag) {
pthread_cond_wait(&cond, &mutex);
}
mutex_unlock(mutex);
}
//process in thread/application B
void process_b() {
mutex_lock(mutex);
flag = 1;
pthread_cond_signal(&cond);
mutex_lock(mutex);
}
結合這個例子我們來看下為什么這個接口要這么設計
- 條件變量不是你要修改的那個變量：你要修改的，即要等待其他進程修改的變量在上述例子里是flag，而不是條件變量，其實上述例子表述起來就是進程A等待其他進程將flag設置1，然后執(zhí)行，條件變量提供的只是使當前進程進入休眠，看上述例子，除了初始化意外，在我們的代碼里，沒有地方對cond進行賦值
- cond條件變量是一種標識符：那你可能會說，那為什么函數(shù)簽名里還需要一個條件變量類型的參數(shù)，去掉不行嗎？假如去掉條件變量，那代碼多處調(diào)用了wait方法，那signal應該喚醒哪個呢？所以說條件變量提供的是一種標識符的能力
小結
條件變量就是為了處理一個進程等待某個變量成立，另外一個線程對這個變量進行修改這樣的需求，這種需求必須防止競態(tài)的發(fā)生(原因各位同學可以很容易分析出來)，所以往往和mutex一起使用來保證互斥，所以有時有人也把它叫做條件鎖
總結
當你理解了這些東西的原理，才能很容易的理解一些看起來高大上的東西是怎么實現(xiàn)，其實它們都沒那么難
