競爭與協作

在單核 CPU 系統里，為了實現多個程序同時運行的假象，操作系統通常以時間片調度的方式，讓每個進程執行每次執行一個時間片，時間片用完了，就切換下一個進程運行，由于這個時間片的時間很短，于是就造成了「并發」的現象。

另外，操作系統也為每個進程創建巨大、私有的虛擬內存的假象，這種地址空間的抽象讓每個程序好像擁有自己的內存，而實際上操作系統在背后秘密地讓多個地址空間「復用」物理內存或者磁盤。

如果一個程序只有一個執行流程，也代表它是單線程的。當然一個程序可以有多個執行流程，也就是所謂的多線程程序，線程是調度的基本單位，進程則是資源分配的基本單位。

所以，線程之間是可以共享進程的資源，比如代碼段、堆空間、數據段、打開的文件等資源，但每個線程都有自己獨立的棧空間。

那么問題就來了，多個線程如果競爭共享資源，如果不采取有效的措施，則會造成共享數據的混亂。

假設現在創建了2個線程，要對i=i+1循環一千次，會出現什么結果？

假設 i == 100

1. 線程 A 讀取 i = 100

2. 線程 B 讀取 i = 100

3. A 執行 i + 1 得到 101，準備寫入

4. B 執行 i + 1 也得到 101，準備寫入

5. A 寫入 i = 101

6. B 也寫入 i = 101（把 A 的寫入覆蓋了）

本應 i = 102，但只加了 1，加1“丟失”了。

互斥的概念

上面展示的情況稱為競爭條件（race condition），當多線程相互競爭操作共享變量時，由于運氣不好，即在執行過程中發生了上下文切換，我們得到了錯誤的結果，事實上，每次運行都可能得到不同的結果，因此輸出的結果存在不確定性（indeterminate）。

由于多線程執行操作共享變量的這段代碼可能會導致競爭狀態，因此我們將此段代碼稱為臨界區（criticalsection），它是訪問共享資源的代碼片段，一定不能給多線程同時執行。

我們希望這段代碼是互斥（mutualexclusion）的，也就說保證一個線程在臨界區執行時，其他線程應該被阻止進入臨界區，說白了，就是這段代碼執行過程中，最多只能出現一個線程。

另外，說一下互斥也并不是只針對多線程。在多進程競爭共享資源的時候，也同樣是可以使用互斥的方式來避免資源競爭造成的資源混亂。

同步的概念

互斥解決了并發進程/線程對臨界區的使用問題。這種基于臨界區控制的交互作用是比較簡單的，只要一個進程/線程進入了臨界區，其他試圖想進入臨界區的進程/線程都會被阻塞著，直到第一個進程/線程離開了臨界區。

我們都知道在多線程里，每個線程并不一定是順序執行的，它們基本是以各自獨立的、不可預知的速度向前推進，但有時候我們又希望多個線程能密切合作，以實現一個共同的任務。

例子，線程 1 是負責讀入數據的，而線程 2 是負責處理數據的，這兩個線程是相互合作、相互依賴的。線程 2 在沒有收到線程 1 的喚醒通知時，就會一直阻塞等待，當線程 1 讀完數據需要把數據傳給線程 2時，線程 1 會喚醒線程 2，并把數據交給線程 2 處理。

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

互斥與同步的實現和使用

為了實現進程/線程間正確的協作，操作系統必須提供實現進程協作的措施和方法，主要的方法有兩種：

• 鎖：加鎖、解鎖操作；
• 信號量：P、V 操作；

這兩個都可以方便地實現進程/線程互斥，而信號量比鎖的功能更強一些，它還可以方便地實現進程/線程同步。

鎖

使用加鎖操作和解鎖操作可以解決并發線程/進程的互斥問題。

任何想進入臨界區的線程，必須先執行加鎖操作。若加鎖操作順利通過，則線程可進入臨界區；在完成對臨界資源的訪問后再執行解鎖操作，以釋放該臨界資源。

根據鎖的實現不同，可以分為「忙等待鎖」和「無忙等待鎖」。

忙等待鎖

在說明「忙等待鎖」的實現之前，先介紹現代 CPU 體系結構提供的特殊原子操作指令?—— 測試和置位（Test-and-Set）指令。

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

int TestAndSet(int *old_ptr,int new){int old=*old_ptr;*old_ptr=new;return old;
}

測試并設置指令做了下述事情:

• int *old_ptr：指向某個共享變量（通常是鎖變量）

• int new：你想設置的新值（例如 1，表示“加鎖”）

當然，關鍵是這些代碼是原子執行。因為既可以測試舊值，又可以設置新值，所以我們把這條指令叫作「測試并設置」。

那什么是原子操作呢？原子操作就是要么全部執行，要么都不執行，不能出現執行到一半的中間狀態我們可以運用 Test-and-Set 指令來實現「忙等待鎖」，代碼如下：

我們來確保理解為什么這個鎖能工作：

• 第一個場景是，首先假設一個線程在運行，調用?lock()，沒有其他線程持有鎖，所以?flag?是 0。沒有其他線程持有鎖，所以?flag?是 0。沒有其他線程持有鎖，所以?flag?是 0。同時也會原子的設置flag 為1，標志鎖已經被持有。當線程離開臨界區，調用?unlock()?將?flag?清理為 0。
• 第二種場景是，當某一個線程已經持有鎖（即?flag?為1）。本線程調用?lock()，然后調用TestAndSet(flag, 1)，這一次返回 1。只要另一個線程一直持有鎖，TestAndSet()?會重復返回 1，本線程會一直忙等。當?flag?終于被改為 0，本線程會調用?TestAndSet()，返回 0 并且原子地設置為 1，從而獲得鎖，進入臨界區。

很明顯，當獲取不到鎖時，線程就會一直 while 循環，不做任何事情，所以就被稱為「忙等待鎖」，也被稱為自旋鎖（spin lock）。

這是最簡單的一種鎖，一直自旋，利用 CPU 周期，直到鎖可用。在單處理器上，需要搶占式的調度器（即不斷通過時鐘中斷一個線程，運行其他線程）。否則，自旋鎖在單 CPU 上無法使用，因為一個自旋的線程永遠不會放棄 CPU。

無等待鎖

無等待鎖顧明思議就是獲取不到鎖的時候，不用自旋。

既然不想自旋，那當沒獲取到鎖的時候，就把當前線程放入到鎖的等待隊列，然后執行調度程序，把 CPU讓給其他線程執行。

信號量

信號量是操作系統提供的一種協調共享資源訪問的方法。

通常信號量表示資源的數量，對應的變量是一個整型（sem）變量。

另外，還有兩個原子操作的系統調用函數來控制信號量的，分別是：

• P 操作：將?sem?減?1，相減后，如果?sem < 0，則進程/線程進入阻塞等待，否則繼續，表明 P 操作可能會阻塞；
• V 操作：將?sem?加?1，相加后，如果?sem <= 0，喚醒一個等待中的進程/線程，表明 V 操作不會阻塞；

P 操作是用在進入臨界區之前，V 操作是用在離開臨界區之后，這兩個操作是必須成對出現的。

PV 操作的函數是由操作系統管理和實現的，所以操作系統已經使得執行 PV 函數時是具有原子性的。

PV 操作如何使用的呢

我們先來說說如何使用信號量實現臨界區的互斥訪問。

為每類共享資源設置一個信號量?s，其初值為?1，表示該臨界資源未被占用。

任何想進入臨界區的線程，必先在互斥信號量上執行 P 操作，在完成對臨界資源的訪問后再執行 V操作。由于互斥信號量的初始值為 1，故在第一個線程執行 P 操作后 s 值變為 0，表示臨界資源為空閑，可分配給該線程，使之進入臨界區。

若此時又有第二個線程想進入臨界區，也應先執行 P 操作，結果使 s 變為負值，這就意味著臨界資源已被占用，因此，第二個線程被阻塞。

并且，直到第一個線程執行 V 操作，釋放臨界資源而恢復 s 值為 0 后，才喚醒第二個線程，使之進入臨界區，待它完成臨界資源的訪問后，又執行 V 操作，使 s 恢復到初始值 1。

對于兩個并發線程，互斥信號量的值僅取 1、0 和 -1 三個值，分別表示：

• 如果互斥信號量為 1，表示沒有線程進入臨界區；
• 如果互斥信號量為 0，表示有一個線程進入臨界區；
• 如果互斥信號量為 -1，表示一個線程進入臨界區，另一個線程等待進入。

通過互斥信號量的方式，就能保證臨界區任何時刻只有一個線程在執行，就達到了互斥的效果。

再來，我們說說如何使用信號量實現事件同步。

同步的方式是設置一個信號量，其初值為?0。

媽媽一開始詢問兒子要不要做飯時，執行的是?P(s1)?，相當于詢問兒子需不需要吃飯，由于?s1?初始值為 0，此時?s1?變成 -1，表明兒子不需要吃飯，所以媽媽線程就進入等待狀態。

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

接著，兒子線程執行了?P(s2)，相當于詢問媽媽飯做完了嗎，由于?s2?初始值是 0，則此時?s2?變成-1，說明媽媽還沒做完飯，兒子線程就等待狀態。最后，媽媽終于做完飯了，于是執行?V(s2)，s2?信號量從 -1 變回了 0，于是就喚醒等待中的兒子線程，喚醒后，兒子線程就可以進行吃飯了。

生產者-消費者問題

生產者-消費者問題描述：

• 生產者在生成數據后，放在一個緩沖區中；
• 消費者從緩沖區取出數據處理；
• 任何時刻，只能有一個生產者或消費者可以訪問緩沖區；

我們對問題分析可以得出：

• 任何時刻只能有一個線程操作緩沖區，說明操作緩沖區是臨界代碼，需要互斥；
• 緩沖區空時，消費者必須等待生產者生成數據；緩沖區滿時，生產者必須等待消費者取出數據。說明生產者和消費者需要同步。

那么我們需要三個信號量，分別是：

• 互斥信號量?mutex：用于互斥訪問緩沖區，初始化值為 1；
• 資源信號量?fullBuffers：用于消費者詢問緩沖區是否有數據，有數據則讀取數據，初始化值為 0（表明緩沖區一開始為空）；
• 資源信號量?emptyBuffers：用于生產者詢問緩沖區是否有空位，有空位則生成數據，初始化值為 n（緩沖區大小）；

如果消費者線程一開始執行?P(fullBuffers)，由于信號量?fullBuffers?初始值為 0，則此時fullBuffers?的值從 0 變為 -1，說明緩沖區里沒有數據，消費者只能等待。

接著，輪到生產者執行?P(emptyBuffers)，表示減少 1 個空槽，如果當前沒有其他生產者線程在臨界區執行代碼，那么該生產者線程就可以把數據放到緩沖區，放完后，執行?V(fullBuffers)?，信號量fullBuffers?從 -1 變成 0，表明有「消費者」線程正在阻塞等待數據，于是阻塞等待的消費者線程會被喚醒。

消費者線程被喚醒后，如果此時沒有其他消費者線程在讀數據，那么就可以直接進入臨界區，從緩沖區讀取數據。最后，離開臨界區后，把空槽的個數 + 1。

經典同步問題

先來看看哲學家就餐的問題描述：

• 5?個老大哥哲學家，閑著沒事做，圍繞著一張圓桌吃面；
• 巧就巧在，這個桌子只有?5?支叉子，每兩個哲學家之間放一支叉子；
• 哲學家圍在一起先思考，思考中途餓了就會想進餐；
• 奇葩的是，這些哲學家要兩支叉子才愿意吃面，也就是需要拿到左右兩邊的叉子才進餐；
• 吃完后，會把兩支叉子放回原處，繼續思考；

方案一

我們用信號量的方式，也就是 PV 操作來嘗試解決它，代碼如下：

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

不過，這種解法存在一個極端的問題：假設五位哲學家同時拿起左邊的叉子，桌面上就沒有叉子了， 這樣就沒有人能夠拿到他們右邊的叉子，也就說每一位哲學家都會在?P(fork[(i + 1) % N ])?這條語句阻塞了，很明顯這發生了死鎖的現象。

方案二

既然「方案一」會發生同時競爭左邊叉子導致死鎖的現象，那么我們就在拿叉子前，加個互斥信號量，代碼如下：

上面程序中的互斥信號量的作用就在于，只要有一個哲學家進入了「臨界區」，也就是準備要拿叉子時，其他哲學家都不能動，只有這位哲學家用完叉子了，才能輪到下一個哲學家進餐。

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

方案三

那既然方案二使用互斥信號量，會導致只能允許一個哲學家就餐，那么我們就不用它。

另外，方案一的問題在于，會出現所有哲學家同時拿左邊刀叉的可能性，那我們就避免哲學家可以同時拿左邊的刀叉，采用分支結構，根據哲學家的編號的不同，而采取不同的動作。

即讓偶數編號的哲學家「先拿左邊的叉子后拿右邊的叉子」，奇數編號的哲學家「先拿右邊的叉子后拿左邊的叉子」。

上面的程序，在 P 操作時，根據哲學家的編號不同，拿起左右兩邊叉子的順序不同。另外，V 操作是不需要分支的，因為 V 操作是不會阻塞的。

方案四

在這里再提出另外一種可行的解決方案，我們用一個數組 state 來記錄每一位哲學家的三個狀態，分別是在進餐狀態、思考狀態、饑餓狀態（正在試圖拿叉子）。

那么，一個哲學家只有在兩個鄰居都沒有進餐時，才可以進入進餐狀態。

第?i?個哲學家的左鄰右舍，則由宏?LEFT?和?RIGHT?定義：

• LEFT?: ( i + 5 - 1 ) % 5
• RIGHT?: ( i + 1 ) % 5

具體代碼實現如下：

上面的程序使用了一個信號量數組，每個信號量對應一位哲學家，這樣在所需的叉子被占用時，想進餐的哲學家就被阻塞。

注意，每個進程/線程將?smart_person?函數作為主代碼運行，而其他?take_forks、put_forks?和test?只是普通的函數，而非單獨的進程/線程。

方案四同樣不會出現死鎖，也可以兩人同時進餐。

讀者-寫者問題

前面的「哲學家進餐問題」對于互斥訪問有限的競爭問題（如 I/O 設備）一類的建模過程十分有用。

另外，還有個著名的問題是「讀者-寫者」，它為數據庫訪問建立了一個模型。

讀者只會讀取數據，不會修改數據，而寫者即可以讀也可以修改數據。

讀者-寫者的問題描述：

• 「讀-讀」允許：同一時刻，允許多個讀者同時讀
• 「讀-寫」互斥：沒有寫者時讀者才能讀，沒有讀者時寫者才能寫
• 「寫-寫」互斥：沒有其他寫者時，寫者才能寫

方案一

使用信號量的方式來嘗試解決：

• 信號量?wMutex：控制寫操作的互斥信號量，初始值為 1 ；
• 讀者計數?rCount：正在進行讀操作的讀者個數，初始化為 0；
• 信號量?rCountMutex：控制對 rCount 讀者計數器的互斥修改，初始值為 1；

上面的這種實現，是讀者優先的策略，因為只要有讀者正在讀的狀態，后來的讀者都可以直接進入，如果讀者持續不斷進入，則寫者會處于饑餓狀態。

方案二

那既然有讀者優先策略，自然也有寫者優先策略：

• 只要有寫者準備要寫入，寫者應盡快執行寫操作，后來的讀者就必須阻塞；
• 如果有寫者持續不斷寫入，則讀者就處于饑餓；

在方案一的基礎上新增如下變量

• 信號量?rMutex：控制讀者進入的互斥信號量，初始值為 1；
• 信號量?wDataMutex：控制寫者寫操作的互斥信號量，初始值為 1；
• 寫者計數?wCount：記錄寫者數量，初始值為 0；
• 信號量?wCountMutex：控制 wCount 互斥修改，初始值為 1；

注意，這里?rMutex?的作用，開始有多個讀者讀數據，它們全部進入讀者隊列，此時來了一個寫者，執行了?P(rMutex)?之后，后續的讀者由于阻塞在?rMutex?上，都不能再進入讀者隊列，而寫者到來，則可以全部進入寫者隊列，因此保證了寫者優先。

同時，第一個寫者執行了?P(rMutex)?之后，也不能馬上開始寫，必須等到所有進入讀者隊列的讀者都執行完讀操作，通過?V(wDataMutex)?喚醒寫者的寫操作。

方案三

既然讀者優先策略和寫者優先策略都會造成饑餓的現象，那么我們就來實現一下公平策略。

公平策略：

• 優先級相同；
• 寫者、讀者互斥訪問；
• 只能一個寫者訪問臨界區；
• 可以有多個讀者同時訪問臨界資源；

開始來了一些讀者讀數據，它們全部進入讀者隊列，此時來了一個寫者，執行?P(falg)?操作，使得后續到來的讀者都阻塞在?flag?上，不能進入讀者隊列，這會使得讀者隊列逐漸為空，即?rCount?減為 0。這個寫者也不能立馬開始寫（因為此時讀者隊列不為空），會阻塞在信號量?wDataMutex?上，讀者隊列中的讀者全部讀取結束后，最后一個讀者進程執行?V(wDataMutex)，喚醒剛才的寫者，寫者則繼續開始進行寫操作。