多個(gè)線程為了同個(gè)資源打起架來(lái)了，該如何讓他們安分？

前言

先來(lái)看看虛構(gòu)的小故事

已經(jīng)晚上 11 點(diǎn)了，程序員小明的雙手還在鍵盤(pán)上飛舞著，眼神依然注視著的電腦屏幕。

沒(méi)辦法這段時(shí)間公司業(yè)績(jī)?cè)鲩L(zhǎng)中，需求自然也多了起來(lái)，加班自然也少不了。

天氣變化莫測(cè)，這時(shí)窗外下起了蓬勃大雨，同時(shí)閃電轟鳴。

但這一絲都沒(méi)有影響到小明，始料未及，突然一道巨大的雷一閃而過(guò)，辦公樓就這么停電了，隨后整棟樓都在回蕩著的小明那一聲撕心裂肺的「臥槽」。

此時(shí)，求小明的心里面積有多大？

等小明心里平復(fù)后，突然肚子非常的痛，想上廁所，小明心想肯定是晚上吃的某堡王有問(wèn)題。

整棟樓都停了電，小明兩眼一抹黑，啥都看不見(jiàn)，只能靠摸墻的方法，一步一步的來(lái)到了廁所門(mén)口。

到了廁所（共享資源），由于實(shí)在太急，小明直接沖入了廁所里，用手摸索著剛好第一個(gè)門(mén)沒(méi)鎖門(mén)，便奪門(mén)而入。

這就荒唐了，這個(gè)門(mén)里面正好小紅在上著廁所，正好這個(gè)廁所門(mén)是壞了的，沒(méi)辦法鎖門(mén)。

黑暗中，小紅雖然看不見(jiàn)，但靠著聲音，發(fā)現(xiàn)自己面前的這扇門(mén)有動(dòng)靜，覺(jué)得不對(duì)勁，于是鉚足了力氣，用她穿著高跟鞋腳，用力地一腳踢了過(guò)去。

小明很幸運(yùn)，被踢中了「命根子」，撕心裂肺地喊出了一個(gè)字「痛」！

故事說(shuō)完了，扯了那么多，實(shí)際上是為了說(shuō)明，對(duì)于共享資源，如果沒(méi)有上鎖，在多線程的環(huán)境里，那么就可能會(huì)發(fā)生翻車現(xiàn)場(chǎng)。

接下來(lái)，用30+張圖，帶大家走進(jìn)操作系統(tǒng)中避免多線程資源競(jìng)爭(zhēng)的互斥、同步的方法。

正文

競(jìng)爭(zhēng)與協(xié)作

在單核 CPU 系統(tǒng)里，為了實(shí)現(xiàn)多個(gè)程序同時(shí)運(yùn)行的假象，操作系統(tǒng)通常以時(shí)間片調(diào)度的方式，讓每個(gè)進(jìn)程執(zhí)行每次執(zhí)行一個(gè)時(shí)間片，時(shí)間片用完了，就切換下一個(gè)進(jìn)程運(yùn)行，由于這個(gè)時(shí)間片的時(shí)間很短，于是就造成了「并發(fā)」的現(xiàn)象。

并發(fā)

另外，操作系統(tǒng)也為每個(gè)進(jìn)程創(chuàng)建巨大、私有的虛擬內(nèi)存的假象，這種地址空間的抽象讓每個(gè)程序好像擁有自己的內(nèi)存，而實(shí)際上操作系統(tǒng)在背后秘密地讓多個(gè)地址空間「復(fù)用」物理內(nèi)存或者磁盤(pán)。

虛擬內(nèi)存管理-換入換出

如果一個(gè)程序只有一個(gè)執(zhí)行流程，也代表它是單線程的。當(dāng)然一個(gè)程序可以有多個(gè)執(zhí)行流程，也就是所謂的多線程程序，線程是調(diào)度的基本單位，進(jìn)程則是資源分配的基本單位。

所以，線程之間是可以共享進(jìn)程的資源，比如代碼段、堆空間、數(shù)據(jù)段、打開(kāi)的文件等資源，但每個(gè)線程都有自己獨(dú)立的?？臻g。

多線程

那么問(wèn)題就來(lái)了，多個(gè)線程如果競(jìng)爭(zhēng)共享資源，如果不采取有效的措施，則會(huì)造成共享數(shù)據(jù)的混亂。

我們做個(gè)小實(shí)驗(yàn)，創(chuàng)建兩個(gè)線程，它們分別對(duì)共享變量i自增1執(zhí)行10000次，如下代碼（雖然說(shuō)是 C++ 代碼，但是沒(méi)學(xué)過(guò) C++ 的同學(xué)也是看到懂的）：

按理來(lái)說(shuō)，i變量最后的值應(yīng)該是20000，但很不幸，并不是如此。我們對(duì)上面的程序執(zhí)行一下：

運(yùn)行了兩次，發(fā)現(xiàn)出現(xiàn)了 i 值的結(jié)果是15173，也會(huì)出現(xiàn)20000的 i 值結(jié)果。

每次運(yùn)行不但會(huì)產(chǎn)生錯(cuò)誤，而且得到不同的結(jié)果。在計(jì)算機(jī)里是不能容忍的，雖然是小概率出現(xiàn)的錯(cuò)誤，但是小概率事件它一定是會(huì)發(fā)生的，「墨菲定律」大家都懂吧。

為什么會(huì)發(fā)生這種情況？

為了理解為什么會(huì)發(fā)生這種情況，我們必須了解編譯器為更新計(jì)數(shù)器i變量生成的代碼序列，也就是要了解匯編指令的執(zhí)行順序。

在這個(gè)例子中，我們只是想給i加上數(shù)字 1，那么它對(duì)應(yīng)的匯編指令執(zhí)行過(guò)程是這樣的：

可以發(fā)現(xiàn)，只是單純給i加上數(shù)字 1，在 CPU 運(yùn)行的時(shí)候，實(shí)際上要執(zhí)行3條指令。

設(shè)想我們的線程 1 進(jìn)入這個(gè)代碼區(qū)域，它將 i 的值（假設(shè)此時(shí)是 50 ）從內(nèi)存加載到它的寄存器中，然后它向寄存器加 1，此時(shí)在寄存器中的 i 值是 51。

現(xiàn)在，一件不幸的事情發(fā)生了：時(shí)鐘中斷發(fā)生。因此，操作系統(tǒng)將當(dāng)前正在運(yùn)行的線程的狀態(tài)保存到線程的線程控制塊 TCP。

現(xiàn)在更糟的事情發(fā)生了，線程 2 被調(diào)度運(yùn)行，并進(jìn)入同一段代碼。它也執(zhí)行了第一條指令，從內(nèi)存獲取 i 值并將其放入到寄存器中，此時(shí)內(nèi)存中 i 的值仍為 50，因此線程 2 寄存器中的 i 值也是 50。假設(shè)線程 2 執(zhí)行接下來(lái)的兩條指令，將寄存器中的 i 值 + 1，然后將寄存器中的 i 值保存到內(nèi)存中，于是此時(shí)全局變量 i 值是 51。

最后，又發(fā)生一次上下文切換，線程 1 恢復(fù)執(zhí)行。還記得它已經(jīng)執(zhí)行了兩條匯編指令，現(xiàn)在準(zhǔn)備執(zhí)行最后一條指令?；貞浺幌?， 線程 1 寄存器中的 i 值是51，因此，執(zhí)行最后一條指令后，將值保存到內(nèi)存，全局變量 i 的值再次被設(shè)置為 51。

簡(jiǎn)單來(lái)說(shuō)，增加 i （值為 50 ）的代碼被運(yùn)行兩次，按理來(lái)說(shuō)，最后的 i 值應(yīng)該是 52，但是由于不可控的調(diào)度，導(dǎo)致最后 i 值卻是 51。

針對(duì)上面線程 1 和線程 2 的執(zhí)行過(guò)程，我畫(huà)了一張流程圖，會(huì)更明確一些：

藍(lán)色表示線程 1 ，紅色表示線程 2

互斥的概念

上面展示的情況稱為競(jìng)爭(zhēng)條件（race condition），當(dāng)多線程相互競(jìng)爭(zhēng)操作共享變量時(shí)，由于運(yùn)氣不好，即在執(zhí)行過(guò)程中發(fā)生了上下文切換，我們得到了錯(cuò)誤的結(jié)果，事實(shí)上，每次運(yùn)行都可能得到不同的結(jié)果，因此輸出的結(jié)果存在不確定性（indeterminate）。

由于多線程執(zhí)行操作共享變量的這段代碼可能會(huì)導(dǎo)致競(jìng)爭(zhēng)狀態(tài)，因此我們將此段代碼稱為臨界區(qū)（critical section），它是訪問(wèn)共享資源的代碼片段，一定不能給多線程同時(shí)執(zhí)行。

我們希望這段代碼是互斥（mutualexclusion）的，也就說(shuō)保證一個(gè)線程在臨界區(qū)執(zhí)行時(shí)，其他線程應(yīng)該被阻止進(jìn)入臨界區(qū)，說(shuō)白了，就是這段代碼執(zhí)行過(guò)程中，最多只能出現(xiàn)一個(gè)線程。

互斥

另外，說(shuō)一下互斥也并不是只針對(duì)多線程。在多進(jìn)程競(jìng)爭(zhēng)共享資源的時(shí)候，也同樣是可以使用互斥的方式來(lái)避免資源競(jìng)爭(zhēng)造成的資源混亂。

同步的概念

互斥解決了并發(fā)進(jìn)程/線程對(duì)臨界區(qū)的使用問(wèn)題。這種基于臨界區(qū)控制的交互作用是比較簡(jiǎn)單的，只要一個(gè)進(jìn)程/線程進(jìn)入了臨界區(qū)，其他試圖想進(jìn)入臨界區(qū)的進(jìn)程/線程都會(huì)被阻塞著，直到第一個(gè)進(jìn)程/線程離開(kāi)了臨界區(qū)。

我們都知道在多線程里，每個(gè)線程并一定是順序執(zhí)行的，它們基本是以各自獨(dú)立的、不可預(yù)知的速度向前推進(jìn)，但有時(shí)候我們又希望多個(gè)線程能密切合作，以實(shí)現(xiàn)一個(gè)共同的任務(wù)。

例子，線程 1 是負(fù)責(zé)讀入數(shù)據(jù)的，而線程 2 是負(fù)責(zé)處理數(shù)據(jù)的，這兩個(gè)線程是相互合作、相互依賴的。線程 2 在沒(méi)有收到線程 1 的喚醒通知時(shí)，就會(huì)一直阻塞等待，當(dāng)線程 1 讀完數(shù)據(jù)需要把數(shù)據(jù)傳給線程 2 時(shí)，線程 1 會(huì)喚醒線程 2，并把數(shù)據(jù)交給線程 2 處理。

所謂同步，就是并發(fā)進(jìn)程/線程在一些關(guān)鍵點(diǎn)上可能需要互相等待與互通消息，這種相互制約的等待與互通信息稱為進(jìn)程/線程同步。

舉個(gè)生活的同步例子，你肚子餓了想要吃飯，你叫媽媽早點(diǎn)做菜，媽媽聽(tīng)到后就開(kāi)始做菜，但是在媽媽沒(méi)有做完飯之前，你必須阻塞等待，等媽媽做完飯后，自然會(huì)通知你，接著你吃飯的事情就可以進(jìn)行了。

吃飯與做菜的同步關(guān)系

注意，同步與互斥是兩種不同的概念：

同步就好比：「操作 A 應(yīng)在操作 B 之前執(zhí)行」，「操作 C 必須在操作 A 和操作 B 都完成之后才能執(zhí)行」等；

互斥就好比：「操作 A 和操作 B 不能在同一時(shí)刻執(zhí)行」；

互斥與同步的實(shí)現(xiàn)和使用

在進(jìn)程/線程并發(fā)執(zhí)行的過(guò)程中，進(jìn)程/線程之間存在協(xié)作的關(guān)系，例如有互斥、同步的關(guān)系。

為了實(shí)現(xiàn)進(jìn)程/線程間正確的協(xié)作，操作系統(tǒng)必須提供實(shí)現(xiàn)進(jìn)程協(xié)作的措施和方法，主要的方法有兩種：

鎖：加鎖、解鎖操作；

信號(hào)量：P、V 操作；

這兩個(gè)都可以方便地實(shí)現(xiàn)進(jìn)程/線程互斥，而信號(hào)量比鎖的功能更強(qiáng)一些，它還可以方便地實(shí)現(xiàn)進(jìn)程/線程同步。

鎖

使用加鎖操作和解鎖操作可以解決并發(fā)線程/進(jìn)程的互斥問(wèn)題。

任何想進(jìn)入臨界區(qū)的線程，必須先執(zhí)行加鎖操作。若加鎖操作順利通過(guò)，則線程可進(jìn)入臨界區(qū)；在完成對(duì)臨界資源的訪問(wèn)后再執(zhí)行解鎖操作，以釋放該臨界資源。

加鎖-解鎖

根據(jù)鎖的實(shí)現(xiàn)不同，可以分為「忙等待鎖」和「無(wú)忙等待鎖」。

我們先來(lái)看看「忙等待鎖」的實(shí)現(xiàn)

在說(shuō)明「忙等待鎖」的實(shí)現(xiàn)之前，先介紹現(xiàn)代 CPU 體系結(jié)構(gòu)提供的特殊原子操作指令 —— 測(cè)試和置位（Test-and-Set）指令。

如果用 C 代碼表示 Test-and-Set 指令，形式如下：

測(cè)試并設(shè)置指令做了下述事情:

把old_ptr更新為new的新值

返回old_ptr的舊值；

當(dāng)然，關(guān)鍵是這些代碼是原子執(zhí)行。因?yàn)榧瓤梢詼y(cè)試舊值，又可以設(shè)置新值，所以我們把這條指令叫作「測(cè)試并設(shè)置」。

那什么是原子操作呢？原子操作就是要么全部執(zhí)行，要么都不執(zhí)行，不能出現(xiàn)執(zhí)行到一半的中間狀態(tài)

我們可以運(yùn)用 Test-and-Set 指令來(lái)實(shí)現(xiàn)「忙等待鎖」，代碼如下：

忙等待鎖的實(shí)現(xiàn)

我們來(lái)確保理解為什么這個(gè)鎖能工作：

第一個(gè)場(chǎng)景是，首先假設(shè)一個(gè)線程在運(yùn)行，調(diào)用lock()，沒(méi)有其他線程持有鎖，所以flag是 0。當(dāng)調(diào)用TestAndSet(flag, 1)方法，返回 0，線程會(huì)跳出 while 循環(huán)，獲取鎖。同時(shí)也會(huì)原子的設(shè)置 flag 為1，標(biāo)志鎖已經(jīng)被持有。當(dāng)線程離開(kāi)臨界區(qū)，調(diào)用unlock()將flag清理為 0。

第二種場(chǎng)景是，當(dāng)某一個(gè)線程已經(jīng)持有鎖（即flag為1）。本線程調(diào)用lock()，然后調(diào)用TestAndSet(flag, 1)，這一次返回 1。只要另一個(gè)線程一直持有鎖，TestAndSet()會(huì)重復(fù)返回 1，本線程會(huì)一直忙等。當(dāng)flag終于被改為 0，本線程會(huì)調(diào)用TestAndSet()，返回 0 并且原子地設(shè)置為 1，從而獲得鎖，進(jìn)入臨界區(qū)。

很明顯，當(dāng)獲取不到鎖時(shí)，線程就會(huì)一直 wile 循環(huán)，不做任何事情，所以就被稱為「忙等待鎖」，也被稱為自旋鎖（spin lock）。

這是最簡(jiǎn)單的一種鎖，一直自旋，利用 CPU 周期，直到鎖可用。在單處理器上，需要搶占式的調(diào)度器（即不斷通過(guò)時(shí)鐘中斷一個(gè)線程，運(yùn)行其他線程）。否則，自旋鎖在單 CPU 上無(wú)法使用，因?yàn)橐粋€(gè)自旋的線程永遠(yuǎn)不會(huì)放棄 CPU。

再來(lái)看看「無(wú)等待鎖」的實(shí)現(xiàn)

無(wú)等待鎖顧明思議就是獲取不到鎖的時(shí)候，不用自旋。

既然不想自旋，那當(dāng)沒(méi)獲取到鎖的時(shí)候，就把當(dāng)前線程放入到鎖的等待隊(duì)列，然后執(zhí)行調(diào)度程序，把 CPU 讓給其他線程執(zhí)行。

無(wú)等待鎖的實(shí)現(xiàn)

本次只是提出了兩種簡(jiǎn)單鎖的實(shí)現(xiàn)方式。當(dāng)然，在具體操作系統(tǒng)實(shí)現(xiàn)中，會(huì)更復(fù)雜，但也離不開(kāi)本例子兩個(gè)基本元素。

如果你想要對(duì)鎖的更進(jìn)一步理解，推薦大家可以看《操作系統(tǒng)導(dǎo)論》第 28 章鎖的內(nèi)容，這本書(shū)在「微信讀書(shū)」就可以免費(fèi)看。

信號(hào)量

信號(hào)量是操作系統(tǒng)提供的一種協(xié)調(diào)共享資源訪問(wèn)的方法。

通常信號(hào)量表示資源的數(shù)量，對(duì)應(yīng)的變量是一個(gè)整型（sem）變量。

另外，還有兩個(gè)原子操作的系統(tǒng)調(diào)用函數(shù)來(lái)控制信號(hào)量的，分別是：

P 操作：將sem減1，相減后，如果sem < 0，則進(jìn)程/線程進(jìn)入阻塞等待，否則繼續(xù)，表明 P 操作可能會(huì)阻塞；

V 操作：將sem加1，相加后，如果sem <= 0，喚醒一個(gè)等待中的進(jìn)程/線程，表明 V 操作不會(huì)阻塞；

P 操作是用在進(jìn)入臨界區(qū)之前，V 操作是用在離開(kāi)臨界區(qū)之后，這兩個(gè)操作是必須成對(duì)出現(xiàn)的。

舉個(gè)類比，2 個(gè)資源的信號(hào)量，相當(dāng)于 2 條火車軌道，PV 操作如下圖過(guò)程：

信號(hào)量與火車軌道

操作系統(tǒng)是如何實(shí)現(xiàn) PV 操作的呢？

信號(hào)量數(shù)據(jù)結(jié)構(gòu)與 PV 操作的算法描述如下圖：

PV 操作的算法描述

PV 操作的函數(shù)是由操作系統(tǒng)管理和實(shí)現(xiàn)的，所以操作系統(tǒng)已經(jīng)使得執(zhí)行 PV 函數(shù)時(shí)是具有原子性的。

PV 操作如何使用的呢？

信號(hào)量不僅可以實(shí)現(xiàn)臨界區(qū)的互斥訪問(wèn)控制，還可以線程間的事件同步。

我們先來(lái)說(shuō)說(shuō)如何使用信號(hào)量實(shí)現(xiàn)臨界區(qū)的互斥訪問(wèn)。

為每類共享資源設(shè)置一個(gè)信號(hào)量s，其初值為1，表示該臨界資源未被占用。

只要把進(jìn)入臨界區(qū)的操作置于P(s)和V(s)之間，即可實(shí)現(xiàn)進(jìn)程/線程互斥：

此時(shí)，任何想進(jìn)入臨界區(qū)的線程，必先在互斥信號(hào)量上執(zhí)行 P 操作，在完成對(duì)臨界資源的訪問(wèn)后再執(zhí)行 V 操作。由于互斥信號(hào)量的初始值為 1，故在第一個(gè)線程執(zhí)行 P 操作后 s 值變?yōu)?0，表示臨界資源為空閑，可分配給該線程，使之進(jìn)入臨界區(qū)。

若此時(shí)又有第二個(gè)線程想進(jìn)入臨界區(qū)，也應(yīng)先執(zhí)行 P 操作，結(jié)果使 s 變?yōu)樨?fù)值，這就意味著臨界資源已被占用，因此，第二個(gè)線程被阻塞。

并且，直到第一個(gè)線程執(zhí)行 V 操作，釋放臨界資源而恢復(fù) s 值為 0 后，才喚醒第二個(gè)線程，使之進(jìn)入臨界區(qū)，待它完成臨界資源的訪問(wèn)后，又執(zhí)行 V 操作，使 s 恢復(fù)到初始值 1。

對(duì)于兩個(gè)并發(fā)線程，互斥信號(hào)量的值僅取 1、0 和 -1 三個(gè)值，分別表示：

如果互斥信號(hào)量為 1，表示沒(méi)有線程進(jìn)入臨界區(qū)；

如果互斥信號(hào)量為 0，表示有一個(gè)線程進(jìn)入臨界區(qū)；

如果互斥信號(hào)量為 -1，表示一個(gè)線程進(jìn)入臨界區(qū)，另一個(gè)線程等待進(jìn)入。

通過(guò)互斥信號(hào)量的方式，就能保證臨界區(qū)任何時(shí)刻只有一個(gè)線程在執(zhí)行，就達(dá)到了互斥的效果。

再來(lái)，我們說(shuō)說(shuō)如何使用信號(hào)量實(shí)現(xiàn)事件同步。

同步的方式是設(shè)置一個(gè)信號(hào)量，其初值為0。

我們把前面的「吃飯-做飯」同步的例子，用代碼的方式實(shí)現(xiàn)一下：

媽媽一開(kāi)始詢問(wèn)兒子要不要做飯時(shí)，執(zhí)行的是P(s1)，相當(dāng)于詢問(wèn)兒子需不需要吃飯，由于s1初始值為 0，此時(shí)s1變成 -1，表明兒子不需要吃飯，所以媽媽線程就進(jìn)入等待狀態(tài)。

當(dāng)兒子肚子餓時(shí)，執(zhí)行了V(s1)，使得s1信號(hào)量從 -1 變成 0，表明此時(shí)兒子需要吃飯了，于是就喚醒了阻塞中的媽媽線程，媽媽線程就開(kāi)始做飯。

接著，兒子線程執(zhí)行了P(s2)，相當(dāng)于詢問(wèn)媽媽飯做完了嗎，由于s2初始值是 0，則此時(shí)s2變成 -1，說(shuō)明媽媽還沒(méi)做完飯，兒子線程就等待狀態(tài)。

最后，媽媽終于做完飯了，于是執(zhí)行V(s2)，s2信號(hào)量從 -1 變回了 0，于是就喚醒等待中的兒子線程，喚醒后，兒子線程就可以進(jìn)行吃飯了。

生產(chǎn)者-消費(fèi)者問(wèn)題

生產(chǎn)者-消費(fèi)者模型

生產(chǎn)者-消費(fèi)者問(wèn)題描述：

生產(chǎn)者在生成數(shù)據(jù)后，放在一個(gè)緩沖區(qū)中；

消費(fèi)者從緩沖區(qū)取出數(shù)據(jù)處理；

任何時(shí)刻，只能有一個(gè)生產(chǎn)者或消費(fèi)者可以訪問(wèn)緩沖區(qū)；

我們對(duì)問(wèn)題分析可以得出：

任何時(shí)刻只能有一個(gè)線程操作緩沖區(qū)，說(shuō)明操作緩沖區(qū)是臨界代碼，需要互斥；

緩沖區(qū)空時(shí)，消費(fèi)者必須等待生產(chǎn)者生成數(shù)據(jù)；緩沖區(qū)滿時(shí)，生產(chǎn)者必須等待消費(fèi)者取出數(shù)據(jù)。說(shuō)明生產(chǎn)者和消費(fèi)者需要同步。

那么我們需要三個(gè)信號(hào)量，分別是：

互斥信號(hào)量mutex：用于互斥訪問(wèn)緩沖區(qū)，初始化值為 1；

資源信號(hào)量fullBuffers：用于消費(fèi)者詢問(wèn)緩沖區(qū)是否有數(shù)據(jù)，有數(shù)據(jù)則讀取數(shù)據(jù)，初始化值為 0（表明緩沖區(qū)一開(kāi)始為空）；

資源信號(hào)量emptyBuffers：用于生產(chǎn)者詢問(wèn)緩沖區(qū)是否有空位，有空位則生成數(shù)據(jù)，初始化值為 n （緩沖區(qū)大?。?/p>

具體的實(shí)現(xiàn)代碼：

如果消費(fèi)者線程一開(kāi)始執(zhí)行P(fullBuffers)，由于信號(hào)量fullBuffers初始值為 0，則此時(shí)fullBuffers的值從 0 變?yōu)?-1，說(shuō)明緩沖區(qū)里沒(méi)有數(shù)據(jù)，消費(fèi)者只能等待。

接著，輪到生產(chǎn)者執(zhí)行P(emptyBuffers)，表示減少 1 個(gè)空槽，如果當(dāng)前沒(méi)有其他生產(chǎn)者線程在臨界區(qū)執(zhí)行代碼，那么該生產(chǎn)者線程就可以把數(shù)據(jù)放到緩沖區(qū)，放完后，執(zhí)行V(fullBuffers)，信號(hào)量fullBuffers從 -1 變成 0，表明有「消費(fèi)者」線程正在阻塞等待數(shù)據(jù)，于是阻塞等待的消費(fèi)者線程會(huì)被喚醒。

消費(fèi)者線程被喚醒后，如果此時(shí)沒(méi)有其他消費(fèi)者線程在讀數(shù)據(jù)，那么就可以直接進(jìn)入臨界區(qū)，從緩沖區(qū)讀取數(shù)據(jù)。最后，離開(kāi)臨界區(qū)后，把空槽的個(gè)數(shù) + 1。

經(jīng)典同步問(wèn)題

哲學(xué)家就餐問(wèn)題

當(dāng)初我在校招的時(shí)候，面試官也問(wèn)過(guò)「哲學(xué)家就餐」這道題目，我當(dāng)時(shí)聽(tīng)的一臉懵逼，無(wú)論面試官怎么講述這個(gè)問(wèn)題，我也始終沒(méi)聽(tīng)懂，就莫名其妙的說(shuō)這個(gè)問(wèn)題會(huì)「死鎖」。

當(dāng)然，我這回答槽透了，所以當(dāng)場(chǎng) game over，殘酷又悲慘故事，就不多說(shuō)了，反正當(dāng)時(shí)菜就是菜。

時(shí)至今日，看我來(lái)圖解這道題。

哲學(xué)家就餐的問(wèn)題

先來(lái)看看哲學(xué)家就餐的問(wèn)題描述：

5個(gè)老大哥哲學(xué)家，閑著沒(méi)事做，圍繞著一張圓桌吃面；

巧就巧在，這個(gè)桌子只有5支叉子，每?jī)蓚€(gè)哲學(xué)家之間放一支叉子；

哲學(xué)家圍在一起先思考，思考中途餓了就會(huì)想進(jìn)餐；

奇葩的是，這些哲學(xué)家要兩支叉子才愿意吃面，也就是需要拿到左右兩邊的叉子才進(jìn)餐；

吃完后，會(huì)把兩支叉子放回原處，繼續(xù)思考；

那么問(wèn)題來(lái)了，如何保證哲學(xué)家們的動(dòng)作有序進(jìn)行，而不會(huì)出現(xiàn)有人永遠(yuǎn)拿不到叉子呢？

方案一

我們用信號(hào)量的方式，也就是 PV 操作來(lái)嘗試解決它，代碼如下：

上面的程序，好似很自然。拿起叉子用 P 操作，代表有叉子就直接用，沒(méi)有叉子時(shí)就等待其他哲學(xué)家放回叉子。

方案一的問(wèn)題

不過(guò)，這種解法存在一個(gè)極端的問(wèn)題：假設(shè)五位哲學(xué)家同時(shí)拿起左邊的叉子，桌面上就沒(méi)有叉子了， 這樣就沒(méi)有人能夠拿到他們右邊的叉子，也就說(shuō)每一位哲學(xué)家都會(huì)在P(fork[(i + 1) % N ])這條語(yǔ)句阻塞了，很明顯這發(fā)生了死鎖的現(xiàn)象。

方案二

既然「方案一」會(huì)發(fā)生同時(shí)競(jìng)爭(zhēng)左邊叉子導(dǎo)致死鎖的現(xiàn)象，那么我們就在拿叉子前，加個(gè)互斥信號(hào)量，代碼如下：

上面程序中的互斥信號(hào)量的作用就在于，只要有一個(gè)哲學(xué)家進(jìn)入了「臨界區(qū)」，也就是準(zhǔn)備要拿叉子時(shí)，其他哲學(xué)家都不能動(dòng)，只有這位哲學(xué)家用完叉子了，才能輪到下一個(gè)哲學(xué)家進(jìn)餐。

方案二的問(wèn)題

方案二雖然能讓哲學(xué)家們按順序吃飯，但是每次進(jìn)餐只能有一位哲學(xué)家，而桌面上是有 5 把叉子，按道理是能可以有兩個(gè)哲學(xué)家同時(shí)進(jìn)餐的，所以從效率角度上，這不是最好的解決方案。

方案三

那既然方案二使用互斥信號(hào)量，會(huì)導(dǎo)致只能允許一個(gè)哲學(xué)家就餐，那么我們就不用它。

另外，方案一的問(wèn)題在于，會(huì)出現(xiàn)所有哲學(xué)家同時(shí)拿左邊刀叉的可能性，那我們就避免哲學(xué)家可以同時(shí)拿左邊的刀叉，采用分支結(jié)構(gòu)，根據(jù)哲學(xué)家的編號(hào)的不同，而采取不同的動(dòng)作。

即讓偶數(shù)編號(hào)的哲學(xué)家「先拿左邊的叉子后拿右邊的叉子」，奇數(shù)編號(hào)的哲學(xué)家「先拿右邊的叉子后拿左邊的叉子」。

上面的程序，在 P 操作時(shí)，根據(jù)哲學(xué)家的編號(hào)不同，拿起左右兩邊叉子的順序不同。另外，V 操作是不需要分支的，因?yàn)?V 操作是不會(huì)阻塞的。

方案三可解決問(wèn)題

方案三即不會(huì)出現(xiàn)死鎖，也可以兩人同時(shí)進(jìn)餐。

方案四

在這里再提出另外一種可行的解決方案，我們用一個(gè)數(shù)組 state 來(lái)記錄每一位哲學(xué)家在進(jìn)程、思考還是饑餓狀態(tài)（正在試圖拿叉子）。

那么，一個(gè)哲學(xué)家只有在兩個(gè)鄰居都沒(méi)有進(jìn)餐時(shí)，才可以進(jìn)入進(jìn)餐狀態(tài)。

第i個(gè)哲學(xué)家的左鄰右舍，則由宏LEFT和RIGHT定義：

LEFT: ( i + 5 - 1 ) % 5

RIGHT: ( i + 1 ) % 5

比如 i 為 2，則LEFT為 1，RIGHT為 3。

具體代碼實(shí)現(xiàn)如下：

上面的程序使用了一個(gè)信號(hào)量數(shù)組，每個(gè)信號(hào)量對(duì)應(yīng)一位哲學(xué)家，這樣在所需的叉子被占用時(shí)，想進(jìn)餐的哲學(xué)家就被阻塞。

注意，每個(gè)進(jìn)程/線程將smart_person函數(shù)作為主代碼運(yùn)行，而其他take_forks、put_forks和test只是普通的函數(shù)，而非單獨(dú)的進(jìn)程/線程。

方案四也可解決問(wèn)題

方案四同樣不會(huì)出現(xiàn)死鎖，也可以兩人同時(shí)進(jìn)餐。

讀者-寫(xiě)者問(wèn)題

前面的「哲學(xué)家進(jìn)餐問(wèn)題」對(duì)于互斥訪問(wèn)有限的競(jìng)爭(zhēng)問(wèn)題（如 I/O 設(shè)備）一類的建模過(guò)程十分有用。

另外，還有個(gè)著名的問(wèn)題是「讀者-寫(xiě)者」，它為數(shù)據(jù)庫(kù)訪問(wèn)建立了一個(gè)模型。

讀者只會(huì)讀取數(shù)據(jù)，不會(huì)修改數(shù)據(jù)，而寫(xiě)者即可以讀也可以修改數(shù)據(jù)。

讀者-寫(xiě)者的問(wèn)題描述：

「讀-讀」允許：同一時(shí)刻，允許多個(gè)讀者同時(shí)讀

「讀-寫(xiě)」互斥：沒(méi)有寫(xiě)者時(shí)讀者才能讀，沒(méi)有讀者時(shí)寫(xiě)者才能寫(xiě)

「寫(xiě)-寫(xiě)」互斥：沒(méi)有其他寫(xiě)者時(shí)，寫(xiě)者才能寫(xiě)

接下來(lái)，提出幾個(gè)解決方案來(lái)分析分析。

方案一

使用信號(hào)量的方式來(lái)嘗試解決：

信號(hào)量wMutex：控制寫(xiě)操作的互斥信號(hào)量，初始值為 1 ；

讀者計(jì)數(shù)rCount：正在進(jìn)行讀操作的讀者個(gè)數(shù)，初始化為 0；

信號(hào)量rCountMutex：控制對(duì) rCount 讀者計(jì)數(shù)器的互斥修改，初始值為 1；

接下來(lái)看看代碼的實(shí)現(xiàn)：

上面的這種實(shí)現(xiàn)，是讀者優(yōu)先的策略，因?yàn)橹灰凶x者正在讀的狀態(tài)，后來(lái)的讀者都可以直接進(jìn)入，如果讀者持續(xù)不斷進(jìn)入，則寫(xiě)者會(huì)處于饑餓狀態(tài)。

方案二

那既然有讀者優(yōu)先策略，自然也有寫(xiě)者優(yōu)先策略：

只要有寫(xiě)者準(zhǔn)備要寫(xiě)入，寫(xiě)者應(yīng)盡快執(zhí)行寫(xiě)操作，后來(lái)的讀者就必須阻塞；

如果有寫(xiě)者持續(xù)不斷寫(xiě)入，則讀者就處于饑餓；

在方案一的基礎(chǔ)上新增如下變量：

信號(hào)量rMutex：控制讀者進(jìn)入的互斥信號(hào)量，初始值為 1；

信號(hào)量wDataMutex：控制寫(xiě)者寫(xiě)操作的互斥信號(hào)量，初始值為 1；

寫(xiě)者計(jì)數(shù)wCount：記錄寫(xiě)者數(shù)量，初始值為 0；

信號(hào)量wCountMutex：控制 wCount 互斥修改，初始值為 1；

具體實(shí)現(xiàn)如下代碼：

注意，這里rMutex的作用，開(kāi)始有多個(gè)讀者讀數(shù)據(jù)，它們?nèi)窟M(jìn)入讀者隊(duì)列，此時(shí)來(lái)了一個(gè)寫(xiě)者，執(zhí)行了P(rMutex)之后，后續(xù)的讀者由于阻塞在rMutex上，都不能再進(jìn)入讀者隊(duì)列，而寫(xiě)者到來(lái)，則可以全部進(jìn)入寫(xiě)者隊(duì)列，因此保證了寫(xiě)者優(yōu)先。

同時(shí)，第一個(gè)寫(xiě)者執(zhí)行了P(rMutex)之后，也不能馬上開(kāi)始寫(xiě)，必須等到所有進(jìn)入讀者隊(duì)列的讀者都執(zhí)行完讀操作，通過(guò)V(wDataMutex)喚醒寫(xiě)者的寫(xiě)操作。

方案三

既然讀者優(yōu)先策略和寫(xiě)者優(yōu)先策略都會(huì)造成饑餓的現(xiàn)象，那么我們就來(lái)實(shí)現(xiàn)一下公平策略。

公平策略：

優(yōu)先級(jí)相同；

寫(xiě)者、讀者互斥訪問(wèn)；

只能一個(gè)寫(xiě)者訪問(wèn)臨界區(qū)；

可以有多個(gè)讀者同時(shí)訪問(wèn)臨街資源；

具體代碼實(shí)現(xiàn)：

看完代碼不知你是否有這樣的疑問(wèn)，為什么加了一個(gè)信號(hào)量flag，就實(shí)現(xiàn)了公平競(jìng)爭(zhēng)？

對(duì)比方案一的讀者優(yōu)先策略，可以發(fā)現(xiàn)，讀者優(yōu)先中只要后續(xù)有讀者到達(dá)，讀者就可以進(jìn)入讀者隊(duì)列， 而寫(xiě)者必須等待，直到?jīng)]有讀者到達(dá)。

沒(méi)有讀者到達(dá)會(huì)導(dǎo)致讀者隊(duì)列為空，即rCount==0，此時(shí)寫(xiě)者才可以進(jìn)入臨界區(qū)執(zhí)行寫(xiě)操作。

而這里flag的作用就是阻止讀者的這種特殊權(quán)限（特殊權(quán)限是只要讀者到達(dá)，就可以進(jìn)入讀者隊(duì)列）。

比如：開(kāi)始來(lái)了一些讀者讀數(shù)據(jù)，它們?nèi)窟M(jìn)入讀者隊(duì)列，此時(shí)來(lái)了一個(gè)寫(xiě)者，執(zhí)行P(falg)操作，使得后續(xù)到來(lái)的讀者都阻塞在flag上，不能進(jìn)入讀者隊(duì)列，這會(huì)使得讀者隊(duì)列逐漸為空，即rCount減為 0。

這個(gè)寫(xiě)者也不能立馬開(kāi)始寫(xiě)（因?yàn)榇藭r(shí)讀者隊(duì)列不為空），會(huì)阻塞在信號(hào)量wDataMutex上，讀者隊(duì)列中的讀者全部讀取結(jié)束后，最后一個(gè)讀者進(jìn)程執(zhí)行V(wDataMutex)，喚醒剛才的寫(xiě)者，寫(xiě)者則繼續(xù)開(kāi)始進(jìn)行寫(xiě)操作。