Q: 如何實現進程間的通信？

A:

兩個進程或者線程間如果要進行通信，可能涉及到以下三個問題：

1. 如何傳遞信息？
2. 如何防止「競爭」？
3. 如何保證進/線程間執行的順序？

Q: 如何防止「競爭」？

A:

我們首先來看下如何在進程間通信過程中避免「競爭」的問題。「競爭」通常出現在兩個進程或者線程同時要訪問/修改一個共享資源的時候，除了同時讀取可能還不會有問題之外，比如一讀一寫，兩個都是寫這種組合是肯定會引起資源的「競爭」的。這種「同時操作共享資源」的結果，完全取決於兩個競爭者之間執行的時序。但是我們都清楚，在編程的世界中，是不能夠對「時序」做任何假設的，因為它的隨機性較大，很多「競爭」問題之所以難以 track，就是因為它出現的幾率不固定，很難定位。

那現在問題就變成了：如何在使用共享資源的時候，同一時間只允許一個進程對其操作。這種行為有一個比較統一和抽象的稱呼：「互斥」。而產生「競爭」問題的地方或者說要進行「互斥」改造的地方，我們統一把它成為「臨界區」。「臨界區」是一段操作共享資源的代碼，如果能保證同一時間只有一個進程進入「臨界區」，那麼「競爭」的問題也就隨之解決了。

第一種可實現互斥機制的技術是：屏蔽中斷。這應該是最暴力的一種方式了，而且更多的是對於進程間「競爭」問題的解決方案。當一個進程進入臨界區後，可以屏蔽所有的中斷。此時， CPU 不會再切換進程，已經處在臨界區的進程也不會受到影響，它可以放心的操作「共享資源」。但是這種方案的缺點也很明顯：1. 進程一旦運行異常很可能從臨界區中退不出來，一直不能切換其他進程 2. 在多 CPU 的情形下，除非把所有 CPU 都 disable 掉，否則還是有其他的 CPU 可以調度運行與其「競爭」的進程。

第二種是在軟體層面的方案： 鎖變數。進臨界區之前查看是否可以獲得鎖，離開臨界區之後釋放鎖。「獲得」和「釋放」的操作通過修改某一個變數實現。但是，這其實並沒有什麼卵用，在 CPU 可以對進程進行任意切換的前提下，鎖變數就變成了另外一個「共享資源」。如：在 A 進程進入臨界區獲得鎖之後想更改鎖狀態時發生了進程間切換，那麼 B 進程此時仍然可以獲得鎖進入臨界區，最終的結果就是，A 和 B 都認為自己拿到了這個鎖，都進入了臨界區。究其原因，還是因為沒有保證進程之間對於共享資源操作的順序性。

第三種是利用「忙等待」的原理：利用一個全局變數實現兩個進程間的同步，保證執行順序。如，設置一個共享變數 turn，初始值為0。A 進程將通過一個 while 循環檢查turn，當其值為0的時候進入臨界區，出臨界區的時候將其改為1。B 進程將通過一個 while 循環檢查 turn，當其值為1的時候進入臨界區，出臨界區的時候將其改為0。利用這種機制就實現了兩個進程嚴格的「同步」，輪換進入臨界區。但是，這種實現有一個Edege Case 沒有考慮到，如果兩個進程執行的速度相差過大，就會導致速度較快的進程在離開臨界區之後，一直在等待速度較慢的進程先進入臨界區。此時，速度較快的進程在 CPU 時間片內執行一個死循環，浪費了 CPU 資源，而且最終執行的效率看起來已經完全取決於速度較慢的進程到底有多慢。

第四種則是在「忙等待」的基礎上進行了一些改進，由原來的不斷訪問鎖變數，查看是否可以進入臨界區的方式變為：當訪問鎖變數不能進入臨界區的時候就進入睡眠狀態，將自身阻塞在臨界區外。直到從臨界區出來的進程喚醒它。這種方式的本質是實現了一對「同步原語」：Sleep/Wake。不過它的缺陷和使用鎖變數是類似的：使用同步原語之前還是需要去訪問一個共享變數來決定是否執行 Sleep or Wake。如果在「訪問共享變數」和「執行 Sleep 原語」之間發生了進程間的切換，那麼很有可能在另外一個進程從臨界區出來之後執行 Wake，但是之前被切換的進程因沒有執行 Sleep ，所以最終將導致這個信號丟失。等到下一次它重新獲得 CPU 時間片的時候，會將自己Sleep，最終它將無法進入臨界區。

討論到現在為止，其實有一部分問題都已經解決了，比如：如何實現互斥，如何避免忙等待給系統帶來的消耗。唯一一個還沒有辦法解決的其實就是對共享變數的「互斥訪問」問題。而互斥訪問這個東西，基本上在用戶態下是不太可能做到的，因為內核才是大 Boss，他想把你調離 CPU 那你就是沒機會再進行下去了。所以，借鑒上面第一種方案的思路，我們需要藉助「屏蔽中斷」這一特性來實現共享變數的「互斥訪問」。這就必須要提及「信號量」的概念了。

Q: 什麼是信號量？

A:

信號量是一個新的名字，它本質上其實就是我們之前所說的在睡眠和喚醒進程前訪問的共享變數。之所以改了一個新的名字，是因為信號量附加的相關操作是通過系統調用+屏蔽中斷來實現的，它可以保證將之前討論的一些可能發生「競爭」的操作實現為一個原子操作（要麼不執行，要麼就都執行完）。

信號量是一個整型的變數，它的取值範圍為[0, +無窮]，在當前的場景下，它的數值代表了還有多少進程處於睡眠狀態中並等待被喚醒。它以系統調用的方式實現了兩個操作：Up， Down。Up 操作為喚醒操作，Down 操作即為 Sleep 操作。它的工作機制大致是這樣的：

對於 Down 操作來說，它在操作一個信號量之前會檢查它是否大於0，如果大於0，則對信號量進行-1，然後進行剩餘的操作；如果等於0，那麼將進程睡眠。檢查，修改，以及後續的操作（睡眠 or 繼續）三者是作為一個原子性的操作來處理的。

對於 Up 操作來說，由於信號量的取值範圍是到正無窮的，所以它在對信號量進行+1操作之前是不需要檢查相應的值的。信號量一旦執行了Up 操作，就說明此時可以喚醒一個睡眠的進程執行了。而睡眠的進程在被喚醒的時候會使用 Down 操作對信號量-1，這樣一增一減也就平衡了。所以，增加信號量的值，喚醒一個進程，兩個步驟若被實現為一個原子操作，即可稱作是一個 Up 操作。

上面所說的，基本上是依靠信號量實現了「互斥」的功能，從而可以解決進程之間的「競爭」問題。實際上，由於信號量是一個整型變數，它的取值範圍比較大，所以可以利用它的計數功能實現進程間的「同步」，從而保證多進程的執行順序。所以，對於生產者和消費者模型來說，如何在保證互斥的同時又保證了兩者的執行順序，信號量的使用起到了至關重要的作用。

信號量的出現極大的豐富了我們處理「互斥」和「同步」問題的方式。若你想解決「競爭」，則可以使用一個僅有「解鎖，鎖住」兩種語義的信號量，我們通常稱他為「互斥量」。「互斥量」的作用僅限於避免「臨界區」同時多有個進程或者線程進入。若你想解決「同步問題」，則可以使用一個僅有「計數」語義的信號量。「計數量」的作用是在具有依賴關係的兩個進程或線程中傳遞「計數信號」，當「計數量」的值未達到某個進程運行條件時，該進程就會被阻塞，反之會順利的進行。

Q: 「互斥」+ 「條件」的另一種實現方式是什麼？

A:

了解到目前為止，我們大致可以歸納出操作系統在處理「互斥」和「同步」的問題上究竟依賴的是什麼思想了：

1. 互斥：通過某種實現，鎖住臨界區，防止臨界區內同一時間被多個進線程訪問。而且必須要藉助內核的力量，防止進程間切換導致的「競爭」
2. 同步：通過某種實現，在進線程間建立一種「通知」機制，可以按照一定的條件「睡眠」和「喚醒」某個進線程。「通知」機制的運行需要互斥的保護

其實，實現「同步」一種比較簡單的方式就是利用我們上面所說的信號量，而且這個信號量還有存儲信號的功能，不會怕信號丟失。同步和互斥一般都是在一起使用的：互斥用於鎖住臨界區，同步用於保證執行順序。但是在運用他們的時候，請一定要掌握好它們之間語義的差別：互斥作用於進程已經可以按照順序執行但是執行過程中受阻，同步作用於進程是否可以順序執行。這麼說可能比較迷惑，我們來看下面一個例子（利用信號量解決生產者、消費者問題）：

m_mux // 互斥信號量
m_num_empty // 緩衝區空閑位置個數
m_num_full // 緩衝區有數據的位置個數
buf // 緩衝區

void producer(){
down(m_num_empty) // 緩衝區是否已滿，可以生產消息
down(m_mux) // 是否可進入臨界區
buf.append(1) // 生產消息
up(m_mux) // 離開臨界區
up(m_num_full) // 增加有數據的位置個數
}

void comsumer(){
down(m_num_full) // 緩衝區是否還有數據，可以消費
down(m_mux) // 是否可進入臨界區
buf.append(1) // 生產消息
up(m_mux) // 離開臨界區
up(m_num_empty) // 增加空閑的位置個數
}

以目前的狀態，上面這個例子運行起來是沒有什麼問題的。但是如果我們把同步和互斥的語義搞錯，粗心一點將down 操作全部顛倒順序就可能會發生死鎖：當 m_mux 在減小 m_num_empty 信號前就被-1且緩衝區已經滿了的時候，生產者將會被阻塞，但是此時生產者已經沒有機會在釋放互斥量了。而消費者會因為被互斥量阻塞的原因無法進入臨界區消費，從而不能對m_num_empty信號量執行 up 操作釋放生產者。這是一個標準的死鎖的例子，它像我們說明了一個事實：在使用同步和互斥的時候要注意對信號量的操作順序，否則會引起災難。

Q: 什麼是管程？什麼是條件變數？

A:

管程是一種高級的同步原語，它是編程語言的組成部分。管程是「互斥」和「同步」的結合體。其中「互斥」部分仍然由「互斥量」實現，但是它由編譯器進行操作。使用管程的人只需要將臨界區的代碼注入到一個管程中，而不用關注它是怎麼實現的。至於「同步」的部分，則是通過一個叫做「條件變數」的東西來實現的。條件變數是一種功能單一的信號量。它只負責實現「同步」。條件變數通常還伴隨著一個過程的集合（Wait，Signal），其中它的 Wait 操作的實現是比較有意思的：Wait 操作在發現當前進程因某些條件不滿足不能繼續執行下去的時候，除了將當前的進程阻塞，還會將另外一個合適的進程調入到管程中來。並且在執行完 Wait 操作之前，不會被任何中斷打斷，從而引起競爭，因為管程幫我們做了「互斥」的保護。

其實筆者對於「條件變數」和「信號量」的區別也不是特別清楚，總覺得條件變數是信號量的一個 Special Case。因為條件變數能做的東西，信號量也一樣可以做。所以，在這篇文章中，我們姑且就按照這樣來理解。

Q: 通過信號量實現的「互斥」和「同步」在哪些場景下會有缺陷呢？

A:

使用信號量實現「互斥」和「同步」有一個比較大的限制：通過將共享變數放在共享內存，並且通過 TSL 等指令來保護這些變數的操作，以避免競爭。但是，當在一個由多個操作系統組成的分散式系統中，每個 CPU 都有自己的私有內存，且還可以通過網路互連，那麼信號量的保護機制就將失效了。看起來，信號量並不能解決處於不同機器之間的進程的通信問題。

所以，操作系統又實現了兩個新的原語：Send && Receive。 通過字面的意思就可以看出，這是一種通過消息傳遞的方式來實現「互斥」和「同步」的。共享變數在通信雙方的機器上都需要被「互斥」機制保護，這一點在單機上實現起來應該是比較簡單的。發送進程可以調用 Send 原語發送信息，而接受進程可以調用 Receive 源於來接受消息。至於「阻塞」和「喚醒」則可以通過網路在雙端傳輸共享變數來實現：如生產者進程在啟動時調用 Receive 等待消費者向他傳遞緩衝區的空閑情況，因為它還不知道現在的情況是否可以傳遞消息，所以會進入阻塞狀態。消費者在啟動後，先調用 Send 將緩衝區的空閑情況發送給生產者，然後再調用 Receive 等待接受消息。生產者收到消息後會查看緩衝區的情況，如果確認可以發送，則調用 Send 向消費者發送消息。 在執行了一個循環之後，整個通信流程就變成了以下幾個步驟重複執行：

1. 生產者發送完消息被阻塞
2. 消費者接受並消費消息
3. 消費者發送緩衝區空閑情況
4. 消費者等待消息被阻塞
5. 生產者接受到和緩衝區空閑情況有關的消息
6. 生產者生產消息

Q: 如果需要「同步」機制的不是一個進程而是一個進程組，我們需要怎麼辦呢？

A:

信號量，管程都是針對於兩個進程間通訊所遇到的問題的解決方案。但是，當同步機製作用於進程組的時候，問題似乎更加抽象了。如，現在一共有八個進程為一組。這裡的同步是指，無論執行的速率，只有等到進程組內所有的進程都執行完了某一階段邏輯，它們才能夠繼續向下運行。

所以，操作系統專門為進程組的同步創建了一個原語：屏障（barrier）。它也是通過一個系統調用來實現的，且最終操作的肯定還是一個進程組內多個進程共享的變數。以上面的進程組為例來描述一下屏障的工作機制：進程組中的每一個進程在執行完它自己的第一階段邏輯之後都會調用 barrier 原語，此時，如果該進程不是進程組中最後一個執行完畢的進程，那麼它會被掛起，直到最後一個進程執行完且調用了 barrier 原語之後，所有的進程才會被釋放去執行第二階段的邏輯。

Q: 什麼是進程？

A:

進程其實是一個比較抽象的概念，它是用來描述多道程序設計系統中的一個工作單元。單純的給進程下一個定義是沒有任何意義的。比如現在所謂的標準答案：進程是操作系統中運行的程序。對於進程，我們更多的要理解它是一個「複合體」，它是一系列活動的組合。它是一個邏輯上的概念，並不是一個現實世界中具體的事物。這一點和 k8s 中的 pod很像。所以，我更傾向於將進程理解為操作系統中的一個複雜且基本的工作單元。

Q: 子進程被創建之後和父進程是如何隔離的？

A:

通常情況下，在 Linux 系統當中，一旦子進程被創建，那麼子進程和父進程就會分別佔有兩塊獨立的地址空間。相互之間是隔離的，並且可以通過一些方式來進行通信或者共享某些資源。但是，在之後操作系統發展的過程當中，對於父子進程的創建過程可能會有一些優化，而不僅僅是粗暴的將父進程地址空間中所有的東西都 copy 一份給子進程。這裡也是有一個比較重要的機制：COW（寫時複製機制）。

Q: Linux 中的進程和 Windows 中有哪些不同？

A:

Linux 系統中的進程是有嚴格的「父子關係」的，並且所有的進程會以樹形的層次結構組織起來。其中祖先進程可認為是 Init，它是進程樹中的根。而 Windows 中的進程，無論父子，都是靠一個叫做「句柄」的概念對一個進程進行標識的，並且這個句柄是可以傳遞的。所以在 Windows 中，進程間沒有嚴格的父子關係。

Q: 什麼是線程？

A:

線程是輕量級的進程。進程由操作系統來管理而線程由進程來管理。不同進程之間的地址空間是隔離的，但是不同線程之間的地址空間是共享的。一般來說，一個進程通常會有一個主線程，進程負責向內核申請線程運行所需要的資源和環境，而線程才是真正執行程序的單位。

Q: 有了進程為什麼還需要線程？

A:

從程序性能的角度來說，很多程序在一個進程中都會做很多任務。這些任務可以大致的被劃分為兩類，一類是 I_O, 一類是計算。I_O 通常消耗的時間會比較長，對於只有主線程的進程來說，它會一直處於等待狀態，內核分配給他的 CPU 時間片也會被白白的消耗。計算類的任務則會直接消耗 CPU 資源，最大限度的利用了已分配的時間片。所以，如果一個程序中同時包含這兩類任務的話，計算類的任務很可能被 I_O 類的任務阻塞，最終導致整個程序的效率下降。因為線程是存在於進程的地址空間中的，如果可以在進程地址空間中創建多個線程，並且讓這些線程重疊執行，分別去運行不同類型的任務，就可以在一定的 CPU 時間片內，將程序的效率儘可能的提高。通過上面的一些思考，我們甚至可以延伸出另外一個問題：多線程技術一定會對我們的程序產生積極的影響么？其實也不盡然。如果我們的程序中既包含大量的 I_O 操作，也包含大量的計算操作，那麼多線程技術是可以提升我們程序的效率的。因為此時由於多個線程重疊的進行，最大限度的利用了 CPU 的時間片。如果我們的程序基本都是計算類的任務，很少有 I/O 操作，那麼多線程的引入可能不會對提升程序的效率有太大的幫助。因為即使線程間的切換消耗再小，還是有 CPU 時間片上面的損耗的。同樣，這個問題的思考方式還可以延伸到：多進程技術一定會對我們的程序有積極的影響么？

從資源共享的角度來說，不同進程間的地址是不同的，所以它們在共享一些資源的時候就會比較麻煩，可能需要藉助第三方的東西，比如文件。然而對於同一個進程中的不同的線程來說，這種內存上的隔離是不存在的，它們可以很方便的去共享一些資源。看到這裡你可能會說，在地址空間不隔離的條件下，多個線程對同一個資源可能會出現競爭的想像。對於這個問題，我們要明確兩點：首先，線程間共享資源的初衷是讓多個線程合作，而不是讓它們競爭。其次，如果不可避免的發生了競爭，也可以通過一些互斥的機制來解決。

最後還要提及一點的就是，大多數操作系統對於多線程的實現都是在「用戶態」下，且線程中維護的必要信息會較進程少很多。這就造成了線程是比進程更輕量級的。如果不可避免的發生頻繁和切換操作，那麼很明顯線程在這種場景下會更具優勢。

Q: 進程和線程之間的關係是什麼？

A:

進程更傾向於從操作系統申請資源，並對這些資源進行統一的管理，提供一個良好的運行環境。線程則更注重利用已經分配好的資源運行程序。也就是說，實際上在 CPU 上調度執行的並不是進程而是線程。

Q: 如何實現線程？

A:

實現線程有兩種思路：在用戶態實現 or 在內核態實現。

當我們想在用戶態實現「線程」的時候，就意味著「線程」或者說是「多線程」對於內核來講應該是透明的。內核與具有單個控制線程的主進程還是按照原來的模式運行（進程模型）。所以，我們很自然的就能夠想到，在用戶態下需要一系列「過程」的集合來實現和線程有關的操作以及「多線程」技術。這個「過程」的集合可以被稱作為是一種 Runtime 系統。

用戶態 Runtime 系統的數和進程數成正比。每一個進程中都有一個 Runtime 去管理進程中的多個線程。它負責線程的創建，銷毀。同時也要負責維護一張「線程表」，用於保存進程內部線程的運行狀態。更重要的是，這個 Runtime 系統需要藉助「線程表」進行線程間的切換，因為同一時刻只有一個線程可以獲得 CPU 的時間片。其實，這樣看起來，Runtime 運行的方式很像一個有限狀態機。它將進程內的線程的狀態保存至「線程表」中，當一個線程被調度到 CPU 上執行的時候，Runtime 就需要在線程表中讀取和這個線程有關的信息；當一個線程要被調度離開 CPU 的時候，同樣需要 Runtime 將此時的狀態保存到線程表中，以便下一次復原運行的上下文環境。如果再類比一下進程和操作系統內核的關係就可以得知，用輕量級的進程來描述線程，真的是再合適不過了。

對於線程間的切換來說，它和進程間的切換的實現有所不同。進程間的切換，要不就是依靠中斷機制，強行將進程從 CPU 上拿下來；要不就是等到該進程的 CPU 時間片被消耗完，調度系統切換新的進程上來。由於我們現在是在用戶態實現線程，操作系統內核無法干預線程的相關操作。所以，我們需要在 Runtime 中實現一個過程，這個過程在調用之後可以主動的將 CPU 時間片讓給其他處於就緒態的線程。這也就是 POSIX 線程標準中定義的 Pthread_yield 所要實現的功能。

在用戶態實現 Runtime 的好處其實很明顯：1. 之前看起來比較複雜的操作，如線程間的切換，都是在用戶態下完成的，不需要內核的參與，所以肯定要比內核實現的版本效率要高 2. 由於這個 Runtime 是我們自己來實現的，所以它的可定製性是非常強的。我們甚至可以開發出自己的一套「線程調度策略」來保證我們的程序效率最大化。

在用戶態實現 Runtime 的壞處其實都可以歸結到一個問題上：阻塞，它既包括線程之間的阻塞也包括線程所在進程的阻塞。線程間的阻塞是指：當一個線程想要進行一些阻塞操作的時候，比如從鍵盤讀取輸入信息。如果讓這個阻塞操作進行了且它所需要的條件一直沒有被滿足，那麼該進程中其他可運行的線程在這一個 CPU 時間片上就沒有機會再被運行了。這其實是不符合「多線程」技術發明的初衷的。進程的阻塞是指：當一個線程執行了一些阻塞系統調用的時候，不僅僅是其他的線程沒有運行的機會了，整個進程都會因為進入阻塞態而被調離 CPU。這是一個非常嚴重的事情。而觸發這種問題的 Case 也很常見：缺頁中斷（線程所需要的數據或者代碼沒有在內存頁中找到而是在硬碟中）。此外，由於多線程間只能夠通過主動調用 Pthread_yield 過程來實現切換操作，如果你的代碼寫的有 bug 的話，其他的線程就會處於「飢餓」或者「餓死」的狀態。

內核態實現的 Runtime 系統的數量不再隨著進程數的變化而變化。事實上，如果真的把線程拿到內核態來實現的話，線程額進程基本就沒什麼區別了。線程會和進程一樣，在內核中有一個線程表，用來維護線程的運行情況。通過對比之前在用戶態實現線程的缺點可以知道，如果將所有阻塞線程的調用全都以系統調用的形式來實現的話，線程間的切換就統一由內核來進行管理，它會選取一個合適的線程繼續使用剩餘的 CPU 時間片。這種阻塞調用既包括線程之間的阻塞也包括阻塞的系統調用。

雖然說，內核態實現 Runtime 開銷比較大的問題是不可避免的。但是仍然可以做出一些優化，比如在線程的銷毀操作上，如果一個線程需要被銷毀，內核可以不進行真正的銷毀操作，而是打上一個空閑線程的標記，並且由它統一管理。這樣如果有線程創建需求的時候，有可以直接復用之前已經分配的資源。

很顯然，內核態實現 Runtime 也是有很多缺點的。其中最被大家詬病的就是「開銷」變大了。這個開銷不僅僅是指時間上面的，還包括空間上面的。如：線程的數量一般都是要比進程多的，所以線程表的規模的增長速度會遠遠大於進程表。當規模大起來之後如何保證一個高效的讀取和寫入操作呢？畢竟引入線程和多線程相關概念的初衷是在合適的場景下能夠提升程序的效率而不是拉低。

既然兩者各有優劣，那麼根據操作系統的一貫思想，就是最大化的將這兩個方案的優點結合起來，產出一個普適性更強的方案：調度程序激活機制。它藉助了用戶態 Runtime 系統的優勢：高效的進行線程間的切換。同時，在用戶態下模擬「內核」線程的功能，防止因線程使用阻塞的系統調用而發生進程的切換。

調度程序激活機制啟用後，內核會為每一個進程分配一個或多個的虛擬 CPU，用戶態 Runtime 系統可以將線程分配到這些虛擬的 CPU 上。虛擬 CPU 代表這個進程可以使用的 CPU 核心數。當一個線程被同進程的另外一個線程所阻塞，它會被用戶態 Runtime 系統處理，並調度新的進程運行。此時，不會發生用戶態和內核態的切換，對於內核來說，這些操作都是透明的。當一個線程被進程之外的因素阻塞住時（阻塞的系統調用，缺頁終端），內核會感知到這個問題，它會通知用戶態 Runtime 系統，需要重新調度一個就緒的線程運行。而當阻塞的事件被完成的時候，內核也會將這個事件通知給用戶態 Runtime 系統，讓它自己來決定，下一步應該調度哪個線程運行。

這種內核調用用戶態 Runtime 系統的機制被稱作為「上行調用」。在CPU中用戶空間為上層，內核為下層層，常規調用應該是上層調用下層，下層不應該調用上層，上行調用就是指內核調用用戶空間的 Runtime 系統。

Q: 如何實現進程間的通信？

A:

兩個進程或者線程間如果要進行通信，可能涉及到以下三個問題：

1. 如何傳遞信息？
2. 如何防止「競爭」？
3. 如何保證進/線程間執行的順序？

Q: 如何防止「競爭」？

A:

我們首先來看下如何在進程間通信過程中避免「競爭」的問題。「競爭」通常出現在兩個進程或者線程同時要訪問/修改一個共享資源的時候，除了同時讀取可能還不會有問題之外，比如一讀一寫，兩個都是寫這種組合是肯定會引起資源的「競爭」的。這種「同時操作共享資源」的結果，完全取決於兩個競爭者之間執行的時序。但是我們都清楚，在編程的世界中，是不能夠對「時序」做任何假設的，因為它的隨機性較大，很多「競爭」問題之所以難以 track，就是因為它出現的幾率不固定，很難定位。

那現在問題就變成了：如何在使用共享資源的時候，同一時間只允許一個進程對其操作。這種行為有一個比較統一和抽象的稱呼：「互斥」。而產生「競爭」問題的地方或者說要進行「互斥」改造的地方，我們統一把它成為「臨界區」。「臨界區」是一段操作共享資源的代碼，如果能保證同一時間只有一個進程進入「臨界區」，那麼「競爭」的問題也就隨之解決了。

第一種可實現互斥機制的技術是：屏蔽中斷。這應該是最暴力的一種方式了，而且更多的是對於進程間「競爭」問題的解決方案。當一個進程進入臨界區後，可以屏蔽所有的中斷。此時， CPU 不會再切換進程，已經處在臨界區的進程也不會受到影響，它可以放心的操作「共享資源」。但是這種方案的缺點也很明顯：1. 進程一旦運行異常很可能從臨界區中退不出來，一直不能切換其他進程 2. 在多 CPU 的情形下，除非把所有 CPU 都 disable 掉，否則還是有其他的 CPU 可以調度運行與其「競爭」的進程。

第二種是在軟體層面的方案： 鎖變數。進臨界區之前查看是否可以獲得鎖，離開臨界區之後釋放鎖。「獲得」和「釋放」的操作通過修改某一個變數實現。但是，這其實並沒有什麼卵用，在 CPU 可以對進程進行任意切換的前提下，鎖變數就變成了另外一個「共享資源」。如：在 A 進程進入臨界區獲得鎖之後想更改鎖狀態時發生了進程間切換，那麼 B 進程此時仍然可以獲得鎖進入臨界區，最終的結果就是，A 和 B 都認為自己拿到了這個鎖，都進入了臨界區。究其原因，還是因為沒有保證進程之間對於共享資源操作的順序性。

第三種是利用「忙等待」的原理：利用一個全局變數實現兩個進程間的同步，保證執行順序。如，設置一個共享變數 turn，初始值為0。A 進程將通過一個 while 循環檢查turn，當其值為0的時候進入臨界區，出臨界區的時候將其改為1。B 進程將通過一個 while 循環檢查 turn，當其值為1的時候進入臨界區，出臨界區的時候將其改為0。利用這種機制就實現了兩個進程嚴格的「同步」，輪換進入臨界區。但是，這種實現有一個Edege Case 沒有考慮到，如果兩個進程執行的速度相差過大，就會導致速度較快的進程在離開臨界區之後，一直在等待速度較慢的進程先進入臨界區。此時，速度較快的進程在 CPU 時間片內執行一個死循環，浪費了 CPU 資源，而且最終執行的效率看起來已經完全取決於速度較慢的進程到底有多慢。

第四種則是在「忙等待」的基礎上進行了一些改進，由原來的不斷訪問鎖變數，查看是否可以進入臨界區的方式變為：當訪問鎖變數不能進入臨界區的時候就進入睡眠狀態，將自身阻塞在臨界區外。直到從臨界區出來的進程喚醒它。這種方式的本質是實現了一對「同步原語」：Sleep/Wake。不過它的缺陷和使用鎖變數是類似的：使用同步原語之前還是需要去訪問一個共享變數來決定是否執行 Sleep or Wake。如果在「訪問共享變數」和「執行 Sleep 原語」之間發生了進程間的切換，那麼很有可能在另外一個進程從臨界區出來之後執行 Wake，但是之前被切換的進程因沒有執行 Sleep，並沒有收到這個信號，從而導致了 Wake 消息丟失的問題。等到下一次它重新獲得 CPU 時間片的時候，會將自己Sleep，最終它將無法進入臨界區。

討論到現在為止，其實有一部分問題都已經解決了，比如：如何實現互斥，如何避免忙等待給系統帶來的消耗。唯一一個還沒有辦法解決的其實就是對共享變數的「互斥訪問」問題。而互斥訪問這個東西，基本上在用戶態下是不太可能做到的，因為內核才是大 Boss，他想把你調離 CPU 那你就是沒機會再進行下去了。所以，借鑒上面第一種方案的思路，我們需要藉助「屏蔽中斷」這一特性來實現共享變數的「互斥訪問」。這就必須要提及「信號量」的概念了。

Q: 什麼是信號量？

A:

信號量是一個新的名字，它本質上其實就是我們之前所說的在睡眠和喚醒進程前訪問的共享變數。之所以改了一個新的名字，是因為信號量附加的相關操作是通過系統調用+屏蔽中斷來實現的，它可以保證將之前討論的一些可能發生「競爭」的操作實現為一個原子操作。

信號量是一個整型的變數，它的取值範圍為[0, +無窮]，在當前的場景下，它的數值代表了還有多少進程處於睡眠狀態中並等待被喚醒。它以系統調用的方式實現了兩個操作：Up， Down。Up 操作為喚醒操作，Down 操作即為 Sleep 操作。它的工作機制大致是這樣的：

對於 Down 操作來說，它在操作一個信號量之前會檢查它是否大於0，如果大於0，則對信號量進行-1，然後進行剩餘的操作；如果等於0，那麼將進程睡眠，但是此時 Down 操作還並沒有結束，因為它還沒有將被它阻塞的進程順利的送出去。檢查，修改，以及後續的操作（睡眠 or 繼續）三者是作為一個原子性的操作來處理的。

對於 Up 操作來說，由於信號量的取值範圍是到正無窮的，所以它在對信號量進行+1操作之前是不需要檢查相應的值的。信號量一旦執行了Up 操作，就說明此時可以喚醒一個睡眠的進程執行了，而睡眠的進程在被喚醒的時候會使用 Down 操作對信號量-1，這樣一增一減也就平衡了。所以，增加信號量的值，喚醒一個進程，兩個步驟若被實現為一個原子操作，即可稱作是一個 Up 操作。

上面所說的，基本上是依靠信號量實現了「互斥」的功能，從而可以解決進程之間的「競爭」問題。實際上，由於信號量是一個整型變數，它的取值範圍比較大，所以可以利用它的計數功能實現進程間的「同步」，從而保證多進程的執行順序。所以，對於生產者和消費者模型來說，如何在保證互斥的同時又保證了兩者的執行順序，信號量的使用起到了至關重要的作用。

信號量的出現極大的豐富了我們處理「互斥」和「同步」問題的方式。若你想解決「競爭」，則可以使用一個僅有「解鎖，鎖住」兩種語義的信號量，我們通常稱他為「互斥量」。「互斥量」的作用僅限於避免「臨界區」同時多有個進程或者線程進入。若你想解決「同步問題」，則可以使用一個僅有「計數」語義的信號量。「計數量」的作用是在具有依賴關係的兩個進程或線程中傳遞「計數信號」，當「計數量」的值未達到某個進程運行條件時，該進程就會被阻塞，反之會順利的進行。

Q: 「互斥」+ 「條件」的另一種實現方式是什麼？

A:

了解到目前為止，我們大致可以歸納出操作系統在處理「互斥」和「同步」的問題上究竟依賴的是什麼思想了：

1. 互斥：通過某種實現，鎖住臨界區，防止臨界區內同一時間被多個進線程訪問
2. 同步：通過某種實現，在進線程間建立一種「通知」機制，可以按照一定的條件「睡眠」和「喚醒」某個進線程。「通知」機制的運行需要互斥的保護

其實，實現「同步」一種比較簡單的方式就是利用我們上面所說的信號量，而且這個信號量還有存儲信號的功能，不會怕信號丟失。同步和互斥一般都是在一起使用的：互斥用於鎖住臨界區，同步用於保證執行順序。但是在運用他們的時候，請一定要掌握好它們之間語義的差別：互斥作用於進程已經可以執行但是執行過程中受阻，同步作用於進程是否可以執行。這麼說可能比較迷惑，我們來看下面一個例子（利用信號量解決生產者、消費者問題）：

m_mux // 互斥信號量
m_num_empty // 緩衝區空閑位置個數
m_num_full // 緩衝區有數據的位置個數
buf // 緩衝區

void producer(){
down(m_num_empty) // 緩衝區是否已滿，可以生產消息
down(m_mux) // 是否可進入臨界區
buf.append(1) // 生產消息
up(m_mux) // 離開臨界區
up(m_num_full) // 增加有數據的位置個數
}

void comsumer(){
down(m_num_full) // 緩衝區是否還有數據，可以消費
down(m_mux) // 是否可進入臨界區
buf.append(1) // 生產消息
up(m_mux) // 離開臨界區
up(m_num_empty) // 增加空閑的位置個數
}

以目前的狀態，上面這個例子運行起來是沒有什麼問題的。但是如果我們把同步和互斥的語義搞錯，粗心一點將down 操作全部顛倒順序就可能會發生死鎖：當 m_mux 在減小 m_num_empty 信號前就被-1且緩衝區已經滿了的時候，生產者將會被阻塞，但是此時生產者已經沒有機會在釋放互斥量了。而消費者會因為被互斥量阻塞的原因無法進入臨界區消費，從而不能對m_num_empty信號量執行 up 操作環境生產者。這是一個標準的死鎖的例子，它像我們說明了一個事實：在使用同步和互斥的時候要注意對信號量的操作順序，否則會引起災難。

Q: 什麼是管程？什麼是條件變數？

A:

管程是一種高級的同步原語，它是編程語言的組成部分。管程是「互斥」和「同步」的結合體。其中「互斥」部分仍然由「互斥量」實現，但是它由編譯器進行操作。使用管程的人只需要將臨界區的代碼注入到一個管程中，而不用關注它是怎麼實現的。而「同步」的部分，則是通過一個叫做「條件變數」的東西來實現的。條件變數是一種功能單一的信號量。它只負責實現「同步」。條件變數通常還伴隨著一個過程的集合，其中它的 Wait 操作的實現是比較有意思的：Wait 操作在發現當前進程因某些條件不滿足不能繼續執行下去的時候，除了將當前的進程阻塞，還會將另外一個合適的進程調入到管程中來。並且在執行完 Wait 操作之前，不會被任何中斷打斷，從而引起競爭，因為管程幫我們做了「互斥」的保護。

其實筆者對於「條件變數」和「信號量」的區別也不是特別清楚，總覺得條件變數是信號量的一個 Special Case。因為條件變數能做的東西，信號量也一樣可以做。所以，在這篇文章中，我們姑且就按照這樣來理解。

Q: 通過信號量實現的「互斥」和「同步」在哪些場景下會有缺陷呢？

A:

使用信號量實現「互斥」和「同步」有一個比較大的限制：通過將共享變數放在共享內存，並且通過 TSL 等指令來保護這些變數的操作，以避免競爭。但是，當在一個由多個操作系統組成的分散式系統中，每個 CPU 都有自己的私有內存，且還可以通過網路互連，那麼信號量的保護機制就將失效了。看起來，信號量並不能解決處於不同機器之間的進程的通信問題。

所以，操作系統又實現了兩個新的原語：Send && Receive。 通過字面的意思就可以看出，這是一種通過消息傳遞的方式來實現「互斥」和「同步」的。共享變數在通信雙方的機器上都需要被「互斥」機制保護，這一點在單機上實現起來應該是比較簡單的。發送進程可以調用 Send 原語發送信息，而接受進程可以調用 Receive 源於來接受消息。至於「阻塞」和「喚醒」則可以通過網路在雙端傳輸共享變數來實現：如生產者進程在啟動時調用 Receive 等待消費者向他傳遞緩衝區的空閑情況，因為它還不知道現在的情況是否可以傳遞消息，所以會進入阻塞狀態。消費者在啟動後，先調用 Send 將緩衝區的空閑情況發送給生產者，然後再調用 Receive 等待接受消息。生產者收到消息後會查看緩衝區的情況，如果確認可以發送，則調用 Send 向消費者發送消息。 在執行了一個循環之後，整個通信流程就變成了以下幾個步驟重複執行：

1. 生產者發送完消息被阻塞
2. 消費者接受並消費消息
3. 消費者發送緩衝區空閑情況
4. 消費者等待消息被阻塞
5. 生產者接受到和緩衝區空閑情況有關的消息
6. 生產者生產消息

Q: 如果需要「同步」機制的不是一個進程而是一個進程組，我們需要怎麼辦呢？

A:

信號量，管程都是針對於兩個進程間通訊所遇到的問題的解決方案。但是，當同步機製作用於進程組的時候，問題似乎更加抽象了。如，現在一共有八個進程為一組。這裡的同步是指，無論執行的速率，只有等到進程組內所有的進程都執行完了某一階段邏輯，它們才能夠繼續向下運行。

所以，操作系統專門為進程組的同步創建了一個原語：屏障（barrier）。它也是通過一個系統調用來實現的，且最終操作的肯定還是一個進程組內多個進程共享的變數。以上面的進程組為例來描述一下屏障的工作機制：進程組中的每一個進程在執行完它自己的第一階段邏輯之後都會調用 barrier 原語，此時，如果該進程不是進程組中最後一個執行完畢的進程，那麼它會被掛起，直到最後一個進程執行完且調用了 barrier 原語之後，所有的進程才會被釋放去執行第二階段的邏輯。

推薦閱讀：