OS–進程間通信詳解(一)

文章目錄

• OS--進程間通信詳解(一)
• • 一、進程間通信
  • • 1.競態條件
    • 2.臨界區
    • 3.忙等互斥
    • • 屏蔽中斷
      • 鎖變量
      • 嚴格輪詢法
      • Peterson 解法
      • TSL指令
    • 4.睡眠與喚醒
    • • 生產者-消費者問題
    • 5.信號量

一、進程間通信

進程是需要頻繁的和其他進程進行交流的。

• 例如，在一個shell管道中，第一個進程的輸出必須傳遞給 第二個進程，這樣沿著管道進行下去。

因此，進程之間如果需要通信的話，必須要使用一種良好的數據 結構以至于不能被中斷。

下面我們會一起討論有關進程間通信(Inter Process Communication, IPC)的問題。

• 關于進程間的通信，這里有三個問題：

• ?上面提到了第一個問題，那就是一個進程如何傳遞消息給其他進程。

• ?第二個問題是如何確保兩個或多個線程之間不會相互干擾。

例如，兩個航空公司都試圖為不同的顧 客搶購飛機上的最后一個座位。

• ?第三個問題是數據的先后順序的問題，如果進程A產生數據并且進程B打印數據。則進程B打印 數據之前需要先等A產生數據后才能夠進行打印。

需要注意的是，這三個問題中的后面兩個問題同樣也適用于線程

• 第一個問題在線程間比較好解決，因為它們共享一個地址空間，它們具有相同的運行時環境

可以想象 你在用高級語言編寫多線程代碼的過程中，線程通信問題是不是比較容易解決？

另外兩個問題也同樣適用于線程，同樣的問題可用同樣的方法來解決。我們后面會慢慢討論

1.競態條件

• 在一些操作系統中，協作的進程可能共享一些彼此都能讀寫的公共資源。公共資源可能在內存中也可能 在一個共享文件。

• 為了講清楚進程間是如何通信的，這里我們舉一個例子：
• 一個后臺打印程序。
• 當一個進程需要打印某個文件時，它會將文件名放在一個特殊的后臺目錄(spooler directory)中。
• 另一個 進程打印后臺進程(printer daemon)會定期的檢查是否需要文件被打印，如果有的話，就打印并將 該文件名從目錄下刪除。
• 假設我們的后臺目錄有非常多的槽位(slot),編號依次為0, 1, 2,…，每個槽位存放一個文件名。
• 同時假設有兩個共享變量：out ,指向下一個需要打印的文件；in,指向目錄中下個空閑的槽位。
• 可以把這兩個文件保存在一個所有進程都能訪問的文件中，該文件的長度為兩個字。
  在某一時刻，0至3號槽位空，4號至6號槽位被占用。
• 在同一時刻，進程A和進程B都決定將一個文件排隊打印，情 況如下
  
• 墨菲法則(Murphy)中說過，任何可能出錯的地方終將出錯，這句話生效時，可能發生如下情況。
• 進程A讀到in的值為7,將7存在一個局部變量next_free_slot中。
• 此時發生一次時鐘中斷， CPU認為進程A已經運行了足夠長的時間，決定切換到進程B。
• 進程B也讀取in的值，發現是7, 然后進程B將7寫入到自己的局部變量next_free_slot中，在這一時刻兩個進程都認為下一個可 用槽位是7。
• 進程B現在繼續運行，它會將打印文件名寫入到slot 7中，然后把in的指針更改為8 ,然后進程B 離開去做其他的事情
• 現在進程A開始恢復運行，由于進程A通過檢查next_free_slot也發現slot 7的槽位是空的，于 是將打印文件名存入slot 7中，然后把in的值更新為8
• 由于slot 7這個槽位中已經有進程B寫入的 值，所以進程A的打印文件名會把進程B的文件覆蓋，由于打印機內部是無法發現是哪個進程更新 的，它的功能比較局限，所以這時候進程B永遠無法打印輸出

• 類似這種情況，即兩個或多個線程同 時對一共享數據進行修改，從而影響程序運行的正確性時，這種就被稱為競態條件(race condition).
• 調試競態條件是一種非常困難的工作，因為絕大多數情況下程序運行良好，但在極少數的情況下會發生 一些無法解釋的奇怪現象。

2.臨界區

• 不僅共享資源會造成競態條件，事實上共享文件、共享內存也會造成競態條件、那么該如何避免呢？
• 或 許一句話可以概括說明：禁止一個或多個進程在同一時刻對共享資源(包括共享內存、共享文件等)進 行讀寫。
• 換句話說，我們需要一種互斥(mutual exclusion)條件，這也就是說，如果一個進程在 某種方式下使用共享變量和文件的話，除該進程之外的其他進程就禁止做這種事(訪問統一資源)。

上 面問題的糾結點在于，在進程A對共享變量的使用未結束之前進程B就使用它。

在任何操作系統中， 為了實現互斥操作而選用適當的原語是一個主要的設計問題，接下來我們會著重探討一下。

• 避免競爭問題的條件可以用一種抽象的方式去描述。大部分時間，進程都會忙于內部計算和其他不會導 致競爭條件的計算。

• 然而，有時候進程會訪問共享內存或文件，或者做一些能夠導致競態條件的操作。

• 我們把對共享內存進行訪問的程序片段稱作臨界區域(critical region)或臨界區(critical section)。

• 如果我們能夠正確的操作，使兩個不同進程不可能同時處于臨界區，就能避免競爭條件， 這也是從操作系統設計角度來進行的。

• 盡管上面這種設計避免了競爭條件，但是不能確保并發線程同時訪問共享數據的正確性和高效性。一個 好的解決方案，應該包含下面四種條件

• 1.任何時候兩個進程不能同時處于臨界區

• 2.不應對CPU的速度和數量做任何假設

• 3.位于臨界區外的進程不得阻塞其他進程

• 4.不能使任何進程無限等待進入臨界區
  

• 從抽象的角度來看，我們通常希望進程的行為如上圖所示，在t1時刻，進程A進入臨界區

• 在t2的時 刻，進程B嘗試進入臨界區，因為此時進程A正在處于臨界區中，所以進程B會阻塞直到t3時刻進 程A離開臨界區，此時進程B能夠允許進入臨界區。

• 最后，在t4時刻，進程B離開臨界區，系統恢 復到沒有進程的原始狀態。

3.忙等互斥

下面我們會繼續探討實現互斥的各種設計，在這些方案中，當一個進程正忙于更新其關鍵區域的共享內 存時，沒有其他進程會進入其關鍵區域，也不會造成影響。

屏蔽中斷

• 在單處理器系統上，最簡單的解決方案是讓每個進程在進入臨界區后立即屏蔽所有中斷，并在離開臨 界區之前重新啟用它們。
• 屏蔽中斷后，時鐘中斷也會被屏蔽。CPU只有發生時鐘中斷或其他中斷時才 會進行進程切換。這樣，在屏蔽中斷后CPU不會切換到其他進程。
• 所以，一旦某個進程屏蔽中斷之 后，它就可以檢查和修改共享內存，而不用擔心其他進程介入訪問共享數據。

這個方案可行嗎？進程進入臨界區域是由誰決定的呢？不是用戶進程嗎？

• 當進程進入臨界區域后，用戶 進程關閉中斷，如果經過一段較長時間后進程沒有離開，那么中斷不就一直啟用不了，結果會如何？
• 可 能會造成整個系統的終止。而且如果是多處理器的話，屏蔽中斷僅僅對執行disable指令的CPU有 效。其他CPU仍將繼續運行，并可以訪問共享內存。
• 另一方面，對內核來說，當它在執行更新變量或列表的幾條指令期間將中斷屏蔽是很方便的。

• 例如，如 果多個進程處理就緒列表中的時候發生中斷，則可能會發生競態條件的出現。
• 所以，屏蔽中斷對于操作系統本身來說是一項很有用的技術，但是對于用戶線程來說，屏蔽中斷卻不是一項通用的互斥機制。

鎖變量

作為第二種嘗試，可以尋找一種軟件層面解決方案。

• 考慮有單個共享的（鎖）變量，初始為值為0。當 一個線程想要進入關鍵區域時，它首先會查看鎖的值是否為0 ,如果鎖的值是0,進程會把它設置為1 并讓進程進入關鍵區域。如果鎖的狀態是1,進程會等待直到鎖變量的值變為0(這里的說法有些不同，有的說初始值為1，代表鎖資源可用。不管怎么說都是一個道理)。

因此，鎖變量的值是 0則意味著沒有線程進入關鍵區域。如果是1則意味著有進程在關鍵區域內。

我們對上圖修改后，如下 所示

• 這種設計方式是否正確呢？是否存在批漏呢？
• 假設一個進程讀出鎖變量的值并發現它為0,而恰好在它 將其設置為1之前，另一個進程調度運行，讀出鎖的變量為0 ,并將鎖的變量設置為1。
• 然后第一個線 程運行，把鎖變量的值再次設置為1,此時，臨界區域就會有兩個進程在同時運行。
  
• 也許我們可以這么認為，在進入前檢查一次，在要離開的關鍵區域再檢查一次不就解決了嗎？
• 實際 上這種情況也是于事無補，因為在第二次檢查期間其他線程仍有可能修改鎖變量的值，
• 換句話說，這種 set-before-check不是一種原子性操作，所以同樣還會發生競爭條件。

嚴格輪詢法

第三種互斥的方式先拋出來一段代碼：

• 在上面代碼中，變量turn ,初始值為0 ,用于記錄輪到那個進程進入臨界區，并檢查或更新共享內 存。
• 開始時，進程0檢查turn,發現其值為0 ,于是進入臨界區。
• 進程1也發現其值為0 ,所以在一 個等待循環中不停的測試turn, 看其值何時變為1。
• 連續檢查一個變量直到某個值出現為止，這種方法 稱為 忙等待(busywaiting)。
• 由于這種方式浪費CPU時間，所以這種方式通常應該要避免。
• 只有在 有理由認為等待時間是非常短的情況下，才能夠使用忙等待。用于忙等待的鎖，稱為自旋鎖 (spinlock)。
• 進程0離開臨界區時，它將turn的值設置為1,以便允許進程1進入其臨界區。
• 假設進程1很快便離 開了臨界區，則此時兩個進程都處于臨界區之外，turn的值又被設置為0。
• 現在進程0很快就執行完 了整個循環，它退出臨界區，并將turn的值設置為1。此時，turn的值為1,兩個進程都在其臨界區外 執行。
• 突然，進程0結束了非臨界區的操作并返回到循環的開始。
• 但是，這時它不能進入臨界區，因為turn 的當前值為1,此時進程1還忙于非臨界區的操作，進程0只能繼續while循環，直到進程1把turn 的值改為0。
• 這說明，在一個進程比另一個進程執行速度慢了很多的情況下，輪流進入臨界區并不是一 個好的方法。
• 這種情況違反了前面的敘述3,即位于臨界區外的進程不得阻塞其他進程，進程0被一個臨界區外的 進程阻塞。由于違反了第三條，所以也不能作為一個好的方案。

Peterson 解法

• 荷蘭數學家T.Dekker通過將鎖變量與警告變量相結合，最早提出了一個不需要嚴格輪換的軟件互斥算 法，

• 后來，G.L.Peterson發現了一種簡單很多的互斥算法，它的算法如下：
  

• 那么上面討論的是順序進入的情況，現在來考慮一種兩個進程同時調用enter_region的情況。

• 它們 都將自己的進程存入turn,但只有最后保存進去的進程號才有效，前一個進程的進程號因為重寫而丟 失。

• 假如進程1是最后存入的，則turn為1。

• 當兩個進程都運行到while的時候，進程0將不會 循環并進入臨界區，而進程1將會無限循環且不會進入臨界區，直到進程0退出位置。

TSL指令

現在來看一種需要硬件幫助的方案。一些計算機，特別是那些設計為多處理器的計算機，都會有下面這 條指令

TSL RX,LOCK

• 稱為測試并加鎖（test and set lock）,它將一個內存字lock讀到寄存器RX中，然后在該內存 地址上存儲一個非零值。
• 讀寫指令能保證是一體的，不可分割的，一同執行的。在這個指令結束之前其 他處理器均不允許訪問內存。執行TSL指令的CPU將會鎖住內存總線，用來禁止其他CPU在這個指 令結束之前訪問內存。
• 很重要的一點是鎖住內存總線和禁用中斷不一樣。禁用中斷并不能保證一個處理器在讀寫操作之間另一 個處理器對內存的讀寫。
• 也就是說，在處理器1上屏蔽中斷對處理器2沒有影響。讓處理器2遠離內 存直到處理器1完成讀寫的最好的方式就是鎖住總線。這需要一個特殊的硬件（基本上，一根總線就可 以確?？偩€由鎖住它的處理器使用，而其他的處理器不能使用）
• 為了使用TSL指令，要使用一個共享變量lock來協調對共享內存的訪問。當lock為0時，任何進程 都可以使用TSL指令將其設置為1,并讀寫共享內存。當操作結束時，進程使用move指令將lock 的值重新設置為0。

這條指令如何防止兩個進程同時進入臨界區呢？下面是解決方案

• 我們可以看到這個解決方案的思想和Peterson的思想很相似。
• 假設存在如下共4指令的匯編語言程 序。
• 第一條指令將lock原來的值復制到寄存器中并將lock設置為1 ,隨后這個原來的值和0做對 比。
• 如果它不是零，說明之前已經被加過鎖，則程序返回到開始并再次測試。
• 經過一段時間后（可長可 短），該值變為0 （當前處于臨界區中的進程退出臨界區時），于是過程返回，此時已加鎖。
• 要清除這 個鎖也比較簡單，程序只需要將0存入lock即可，不需要特殊的同步指令。
• 現在有了一種很明確的做法，那就是進程在進入臨界區之前會先調用enter_region ,判斷是否進行 循環，如果lock的值是1 ,進行無限循環，如果lock是0,不進入循環并進入臨界區。
• 在進程從臨界 區返回時它調用leave_region ,這會把lock設置為0。與基于臨界區問題的所有解法一樣，進程 必須在正確的時間調用enter_region和leave_region ,解法才能奏效。
• 還有一個可以替換TSL的指令是XCHG ,它原子性的交換了兩個位置的內容，

例如，一個寄存器與一 個內存字，代碼如下：

4.睡眠與喚醒

上面解法中的Peterson 、TSL和XCHG解法都是正確的，但是它們都有忙等待的缺點。

• 這些解法的本 質上都是一樣的，先檢查是否能夠進入臨界區，若不允許，則該進程將原地等待，直到允許為止。
• 這種方式不但浪費了 CPU時間，而且還可能引起意想不到的結果。

• 考慮一臺計算機上有兩個進程，這 兩個進程具有不同的優先級，H是屬于優先級比較高的進程，L是屬于優先級比較低的進程。
• 進程 調度的規則是不論何時只要H進程處于就緒態H就開始運行。
• 在某一時刻，L處于臨界區中，此時H變為就緒態，準備運行(例如，一條I/O操作結束)。
• 現在H要開始忙等，但由于當H就緒時L就不會被調度，L從來不會有機會離開關鍵區域，所以H會變成死循環，有時將這種情況稱為優先級反轉問題 (priority inversion
  problem)

• 現在讓我們看一下進程間的通信原語，這些原語在不允許它們進入關鍵區域之前會阻塞而不是浪費CPU時間，最簡單的是sleep和wakeup。
• Sleep是一個能夠造成調用者阻塞的系統調用，也就是 說，這個系統調用會暫停直到其他進程喚醒它。
• wakeup調用有一個參數，即要喚醒的進程。還有一種 方式是wake叩和sleep都有一個參數，即sleep和wakeup需要匹配的內存地址。

生產者-消費者問題

• 作為這些私有原語的例子，讓我們考慮生產者-消費者(producer-consumer)問題，也稱作 有界緩沖區(bounded-buffer)問題。
• 兩個進程共享一個公共的固定大小的緩沖區。其中一個是生產者 (producer),將信息放入緩沖區，另一個是消費者(consumer),會從緩沖區中取出。
• 也可以把這 個問題一般化為m個生產者和n個消費者的問題，但是我們這里只討論一個生產者和一個消費者的情況，這樣可以簡化實現方案。
• 如果緩沖隊列已滿，那么當生產者仍想要將數據寫入緩沖區的時候，會出現問題。它的解決辦法是讓生 產者睡眠，也就是阻塞生產者。等到消費者從緩沖區中取出一個或多個數據項時再喚醒它。
• 同樣的，當 消費者試圖從緩沖區中取數據，但是發現緩沖區為空時，消費者也會睡眠，阻塞。直到生產者向其中放 入一個新的數據。
• 這個邏輯聽起來比較簡單，而且這種方式也需要一種稱作 監聽 的變量，這個變量用于監視緩沖區的 數據，我們暫定為count
• 如果緩沖區最多存放N個數據項，生產者會每次判斷count是否達到N, 否則生產者向緩沖區放入一個數據項并增量count的值。
• 消費者的邏輯也很相似：首先測試count的 值是否為0 ,如果為0則消費者睡眠、阻塞，否則會從緩沖區取出數據并使count數量遞減。
• 每個進 程也會檢查檢查是否其他線程是否應該被喚醒，如果應該被喚醒，那么就喚醒該線程。

下面是生產者消 費者的代碼：

• 為了在C語言中描述像是sleep和wakeup的系統調用，我們將以庫函數調用的形式來表示。
• 它 們不是C標準庫的一部分，但可以在實際具有這些系統調用的任何系統上使用。代碼中未實現的 insert_item和remove_item用來記錄將數據項放入緩沖區和從緩沖區取出數據等。
• 現在讓我們回到生產者-消費者問題上來，上面代碼中會產生競爭條件，因為count這個變量是暴露在 大眾視野下的。
• 有可能出現下面這種情況：緩沖區為空，此時消費者剛好讀取count的值發現它為0 。此時調度程序決定暫停消費者并啟動運行生產者。
• 生產者生產了一條數據并把它放在緩沖區中，然后 增加count的值，并注意到它的值是1。
• 由于count為0,消費者必須處于睡眠狀態，因此生產者調 用wakeup來喚醒消費者。但是，消費者此時在邏輯上并沒有睡眠，所以wakeup信號會丟失。
• 當消 費者下次啟動后，它會查看之前讀取的count值，發現它的值是0 ,然后在此進行睡眠。不久之后生 產者會填滿整個緩沖區，在這之后會阻塞，這樣一來兩個進程將永遠睡眠下去。
• 引起上面問題的 本質是喚醒尚未進行睡眠狀態的進程會導致喚醒丟失。
• 如果它沒有丟失，則一切都很 正常。一種快速 解決上面問題的方式是增加一個喚醒等待位(wakeup waiting bit) 。
• 當一個 wakeup信號發送給仍在清醒的進程后，該位置為1。之后，當進程嘗試睡眠的時候，如果喚醒等待位 為1 ,則該位清除，而進程仍然保持清醒。
• 然而，當進程數量有許多的時候，這時你可以說通過增加喚醒等待位的數量來喚醒等待位，于是就有了2、4、6、8個喚醒等待位，但是并沒有從根本上解決問題。

5.信號量

• 信號量是E.W.Dijkstra在1965年提出的一種方法，它使用一個整形變量來累計喚醒次數，以供之后使 用。
• 在他的觀點中，有一個新的變量類型稱作**信號量(semaphore) ，—個信號量的取值可以是0 ,或 任意正數。0表示的是不需要任何喚醒，任意的正數表示的就是喚醒次數。**
• Dijkstra提出了信號量有兩個操作，現在通常使用down和up (分別可以用sleep和wakeup來表 示)。
• down這個指令的操作會檢查值是否大于0。如果大于0 ,則將其值減1 ；若該值為0 ,則進 程將睡眠，而且此時down操作將會繼續執行。
• 檢查數值、修改變量值以及可能發生的睡眠操作均為一 個單一的、不可分割的原子操作(atomic action)完成。
• 這會保證一旦信號量操作開始，沒有其他 的進程能夠訪問信號量，直到操作完成或者阻塞。這種原子性對于解決同步問題和避免競爭絕對必不可 少。

原子性操作指的是在計算機科學的許多其他領域中，一組相關操作全部執行而沒有中斷或根本不 執行。

• up操作會使信號量的值+ 1。如果一個或者多個進程在信號量上睡眠，無法完成一個先前的down操 作，則由系統選擇其中一個并允許該程完成down操作。
• 因此，對一個進程在其上睡眠的信號量執行一 次up操作之后，該信號量的值仍然是0 ,但在其上睡眠的進程卻少了一個。
• 信號量的值增1和喚醒一 個進程同樣也是不可分割的。不會有某個進程因執行up而阻塞，正如在前面的模型中不會有進程因執 行wakeup而阻塞是一樣的道理。

用信號量解決生產者消費者丟失的wakeup問題，代碼如下：

• 為了確保信號量能正確工作，最重要的是要采用一種不可分割的方式來實現它。通常是將up和down 作為系統調用來實現。

• 而且操作系統只需在執行以下操作時暫時屏蔽全部中斷：檢查信號量、更新、必 要時使進程睡眠。由于這些操作僅需要非常少的指令，因此中斷不會造成影響。

• 如果使用多個CPU, 那么信號量應該被鎖進行保護。使用TSL或者XCHG指令用來確保同一時刻只有一個CPU對信號量 進行操作。

• 使用TSL或者XCHG來防止幾個CPU同時訪問一個信號量，與生產者或消費者使用忙等待來等待其 他騰出或填充緩沖區是完全不一樣的。前者的操作僅需要幾個毫秒，而生產者或消費者可能需要任意長 的時間。

• 上面這個解決方案使用了三種信號量：一個稱為full,用來記錄充滿的緩沖槽數目；一個稱為empty, 記錄空的緩沖槽數目；一個稱為mutex,用來確保生產者和消費者不會同時進入緩沖區。

• Full被初 始化為0 , empty初始化為緩沖區中插槽數，mutex初始化為1。信號量初始化為1并且由兩個或多 個進程使用，以確保它們中同時只有一個可以進入關鍵區域的信號被稱為 二進制信號量(binary semaphores)

• 如果每個進程都在進入關鍵區域之前執行down操作，而在離開關鍵區域之后執行up 操作，則可以確保相互互斥。

• 現在我們有了一個好的進程間原語的保證。然后我們再來看一下中斷的順序保證：

• 1.硬件壓入堆棧程序計數器等

• 2.硬件從中斷向量裝入新的程序計數器

• 3.匯編語言過程保存寄存器的值

• 4.匯編語言過程設置新的堆棧

• 5.C中斷服務器運行(典型的讀和緩存寫入)

• 6.調度器決定下面哪個程序先運行

• 7.C過程返回至匯編代碼

• 8.匯編語言過程開始運行新的當前進程

在使用信號量的系統中，隱藏中斷的自然方法是讓每個I/O設備都配備一個信號量，該信號量最初設 置為0。

• 在I/O設備啟動后，中斷處理程序立刻對相關聯的信號執行一個down操作，于是進程立即被 阻塞。
• 當中斷進入時，中斷處理程序隨后對相關的信號量執行一個up操作，能夠使已經阻止的進程恢 復運行。
• 在上面的中斷處理步驟中，其中的第5步C中斷服務器運行 就是中斷處理程序在信號量上 執行的一個up操作，所以在第6步中，操作系統能夠執行設備驅動程序
• 當然，如果有幾個進程已經 處于就緒狀態，調度程序可能會選擇接下來運行一個更重要的進程，我們會在后面討論調度的算法。
• 上面的代碼實際上是通過兩種不同的方式來使用信號量的，而這兩種信號量之間的區別也是很重要 的。
• mutex信號量用于互斥。它用于確保任意時刻只有一個進程能夠對緩沖區和相關變量進行讀寫。互斥是用于避免進程混亂所必須的一種操作。
• 另外一個信號量是關于同步(synchronization)的。full和empty信號量用于確保事件的發生 或者不發生。在這個事例中，它們確保了緩沖區滿時生產者停止運行；緩沖區為空時消費者停止運行。 這兩個信號量的使用與mutex不同。

總結

以上是生活随笔為你收集整理的OS--进程间通信详解(一)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。