進程間通信

09-22

進程間通信

現代操作系統，Chapter 2.3

競爭條件

兩個或多個線程讀寫某些共享數據，而最後的結果取決於進程運行的精確時序，稱為競爭條件。

競爭條件的癥結在於：在進程A對共享變數的使用未結束之前進程B就使用它。

臨界區

為了避免競爭條件，關鍵是找出某種途徑來組織多個進程同時讀寫共享變數或數據，換言之，我們需要的互斥(Mutual exclusion)。

為了解決競爭條件，也就是兩個進程不可能同時處於臨界區中。一個好的解決方案，需要滿足以下4個條件：

任何兩個進程不能同時處於臨界區
不應對CPU的速度和數量做出任何假設
臨界區外運行的進程不得阻塞其它進程
不得使得進程無限期等待進入臨界區

忙等待的互斥

屏蔽中斷

在單處理器系統中，最簡單的方法是使每個進程在剛剛進入臨界區後立即屏蔽所有中斷，並在就要離開時，打開中斷。

但這種方案不好，因為把屏蔽中斷的權利交給用戶進程是不明智的，如果進程忘記打開中斷，那麼就可能導致系統不會運行；另一方面，對於多核系統，屏蔽中斷只對當前核有用，其它核心還是能訪問共享內存。

鎖變數

作為第二種忙等待的互斥實現，是尋找一種軟體解決方案。

具體來說，可以建立一個共享(鎖)變數，其初始值為0，當一個進程想進入臨界區時，首先測試這把鎖，如果該鎖值為0，則該進程將其設置為1並進入臨界區；若這把鎖的值已為1，則該進程將忙等待直到其值變為0。於是，0就表示臨界區沒有進程，1表示已經有某個進程進入臨界區了。

這種方法本質上還是需要在讀取鎖變數的時候是正確的，這也就需要類似Atomic exchange的技術來實現了。

嚴格輪換法

嚴格輪換法就是根據進程的id，每次只執行一個進程。比如，當進程0執行完成後，更新可執行的進程號為1，則進程1開始執行，其它進程還是處於忙等待。

忙等待：連續測試一個變數直到某個值出現為止。用於忙等待的鎖，稱為自旋鎖。

Peterson解法

Peterson演算法由兩個用ANSI C編寫的過程(Enter_region, Leave_region)組成。

在使用共享變數之前(即進入臨界區)之前，各個進程使用其進程號id作為參數來調用enter_region。該調用在需要時將使進程等待，直到能安全進入臨界區。在完成對共享變數的操作之後，進程將調用leave_region，表示操作已完成，若其它的進程希望進入臨界區，則現在就能進入。

一種實現代碼如下：

#define FALSE 0#define TRUE 1#define N 2 // 線程數int true;int interested[N];void enter_region(int process){ int other; other = 1 - process; interested[process] = TRUE; turn = process; while(turn == process && interested[other] == TRUE);}void leave_region(int process){ interested[process] = FALSE;}

TSL指令

是一種硬體支持的一種方案。也就是測試並加鎖(Test and set lock)。它將一個內存字lock讀入到寄存器RX中，然後在該內存地址上存一個非零值。讀字和寫字是不可分割的，即該指令結束之前其它處理器均不允許訪問該內存字。執行TSL指令的CPU將鎖住內存匯流排，以禁止其它CPU在本指令結束之前訪問內存。

enter_region: TSL REGISTER, LOCK CMP REGISTER, #0 JNE enter_region ; 如果不空閑(=0)，那麼反覆執行，處於忙等待狀態 RETleave_region: MOVE LOCK, #0 RET

具體工作過程：第一條指令將lock原來的值複製到寄存器中並將lock設置為1，隨後這個原來的值與0相比較。如果原來的值非零，則說明以前已被加鎖，則程序將回到開始並再次測試。經過一段時間後，lock值變為0，於是過程返回，此時已加鎖。要清除這個鎖比較簡單，程序只需將0存入lock即可，不需要特殊的同步指令。

一個可替代TSL的指令是XCHG，它原子性地交換兩個位置的內容，例如，一個寄存器與一個存儲字。它本質上與TSL的解決辦法一樣。所有的Intel x86 CPU在底層同步中使用XCHG指令。

睡眠與喚醒

上述基於忙等待的互斥，不僅會浪費CPU時間，而且還可能引起預想不到的結果。例如，有兩個進程L和H，L的優先順序較低、H的優先順序較高。調度規則規定，只要H處於就緒態它就會運行。在某一時刻，L處於臨界區中，此時H變到就緒態，準備運行。現在H開始忙等待，待由於H就緒時，L就不會被調度，也就無法離開臨界區，所以H將永遠忙等待下去。這種情況有時被稱作優先順序反轉問題。

最簡單的進程間通信原語，它們在無法進入臨界區時將阻塞，而不是忙等待。兩條最簡單的通信原語是：sleep和wakeup。sleep是一個將引起調用進程阻塞的系統調用，即被掛起，直到另外一個進程將其喚醒。wakeup調用有一個參數，即要被喚醒的進程。

一個使用這些原語的例子：生產者-消費者問題。在這個例子中，一個主要的問題是，發給一個尚未睡眠的進程的wakeup信號會丟失。一種快速的彌補方法是修改規則，加上一個喚醒等待位。當一個wakeup發送給一個清醒的進程信號時，將該位置1。隨後，當該進程要睡眠時，如果喚醒等待位為1，則將該位清楚，該進程仍然保持清醒。喚醒等待位實際就是wakeup信號的一個小倉庫。

信號量

基於支持P、V操作的非負整數實現。

信號量的用處一：生產者-消費者問題

在使用信號量的系統中，隱藏中斷的最自然的方法就是為每一個I/O設備設置一個信號量，其初始值為0。在啟動一個I/O設備之後，管理進程就立即對相關聯的信號量執行一個Down操作，於是進程立即被阻塞。當終端到來時，終端處理程序隨即對相關信號量執行一個Up操作，從而將相關的進程設置為就緒狀態。

為了解決生產者-消費者問題，可以使用三個信號量：full，用於記錄充滿的緩衝槽數據；empty，用於記錄空的緩衝槽總數；mutex，用來確保生產者和消費者不會同時訪問緩衝區。

信號量的用處二：用於實現同步(Synchronization)

信號量full和empty用來保證某種時間的順序發生或不發生。例如，當緩衝區滿的時候生產者停止運行，而空的時候消費者停止運行。

互斥量

互斥量是一個可以處於兩態之一的變數：加鎖、解鎖。相比於信號量，它沒有計數功能。

由於互斥量非常簡單，所以如果有TSL或XCHG指令，就可以很容易地在用戶空間中實現它們。由於用戶級線程包的mutex_lock和mutex_unlock代碼如下圖(0表示解鎖)：

mutex_lock: TSL REGISTER, MUTEX CMP REGISTER, #0 JZE ok ; 如果互斥鎖空閑，那麼就直接返回繼續運行 CALL thread_yield ; 如果互斥鎖忙，那麼就調用其它進程，這是與忙等待的區別 JMP mutex_lock ; 稍後再試，也就是本代碼段的開頭ok: RETmutex_unlock: MOVE MUTEX, #0 RET

mutex_lock的代碼與enter_region的代碼很相似，但有一個關鍵的區別。當enter_region進入臨界區失敗後，它始終重複測試鎖(忙等待)。實際上，由於時鐘超時的作用，會調度其它進程運行，這樣遲早擁有鎖的進程會進入運行並釋放鎖。

在用戶線程中，情形有所不同，因為沒有時鐘停止運行時間長度的線程。結果就是通過忙等待的方式來試圖獲取鎖的線程將永遠循環下去，絕不會得到鎖，因為這個運行的線程不會讓其它線程運行從而釋放鎖。

這就是enter_region與mutex_lock的區別。

Pthread中的互斥

pthread中提供了基於互斥鎖的同步機制。提供的函數如下：

pthread_mutex_init(); // 創建互斥鎖pthread_mutex_destroy(); // 銷毀互斥鎖pthread_mutex_lock(); // 上鎖pthread_mutex_trylock(); // 嘗試上鎖，若上鎖不成功，會返回錯誤代碼而不是阻塞調用者pthread_mutex_unlock(); // 對互斥鎖解鎖

pthread中處理提供了互斥鎖，還提供了條件變數用於實現同步。互斥量在允許或阻塞對臨界區的訪問上是很有用的，條件變數則允許線程由於一些未達到的條件而阻塞。絕大多數情況下，這兩種方法是一起使用的。下面就是線程、互斥量、條件變數之間的關聯。

線程、互斥量、條件變數之間的關聯

以生產者-消費者為例。一個線程將產品放在緩衝區內，由另一個線程將他們取出。如果生產者發現緩衝區沒有空槽可用，那麼就將生產者線程阻塞直到一個空槽可以使用。生產者使用互斥量可以進行原子性檢查，而不受其它線程干擾。但是當發現緩衝區已經滿的時候，生產者需要一種方法來阻塞自己並在以後被喚醒。這邊是條件變數做的事情了。

總的來說，互斥量提供了對臨界區域的互斥訪問，而條件變數可以實現線程的阻塞。所以它倆通常一起使用，下面的這些函數也接受一個互斥量作為參數。

pthread提供了pthread_conv_init, pthread_conv_destory, pthread_cond_wait，pthread_conv_signal, pthread_conv_broadcast來操作條件變數。

管程

消息傳遞

屏障

作為最後一個同步機制，是用於進程組而不是用於雙進程的生產者-消費者類情形。除非所有的進程都就緒準備著手下一階段，否則任何進程都不能進入下一階段。可以通過在每個階段的結尾安置屏障(Barrier)來實現這種行為。