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

文章目錄

• OS--進程間通信詳解(二)
• • 一、進程間通信
  • • 1.互斥量
    • • Futexes
      • Pthreads中的互斥量
    • 2.管程
    • 3.消息傳遞
    • • 消息傳遞系統的設計要點
      • 用消息傳遞解決生產者?消費者問題
    • 4.屏障
    • 5.避免鎖：讀-復制-更新

一、進程間通信

1.互斥量

如果不需要信號量的計數能力時，可以使用信號量的一個簡單版本，稱為mutex(互斥量)。

• 互斥量的 優勢就在于在一些共享資源和一段代碼中保持互斥。由于互斥的實現既簡單又有效，這使得互斥量在實 現用戶空間線程包時非常有用。
• 互斥量是一個處于兩種狀態之一的共享變量：解鎖(unlocked)和加鎖(locked)。
• 這樣，只需要一 個二進制位來表示它，不過一般情況下，通常會用一個 整形(integer)來表示。0表示解鎖，其他所 有的值表示加鎖，比1大的值表示加鎖的次數。
• mutex使用兩個過程，當一個線程(或者進程)需要訪問關鍵區域時，會調用mutex_lock進行加 鎖。如果互斥鎖當前處于解鎖狀態(表示關鍵區域可用)，則調用成功，并且調用線程可以自由進入關 鍵區域。
• 另一方面，如果mutex互斥量已經鎖定的話，調用線程會阻塞直到關鍵區域內的線程執行完畢并且調 用了 mutex_unlock。如果多個線程在mutex互斥量上阻塞，將隨機選擇一個線程并允許它獲得 鎖。
  
• 由于mutex互斥量非常簡單，所以只要有TSL或者是XCHG指令，就可以很容易地在用戶空間實現它 們。
• 用于用戶級線程包的mutex_lock和mutex_unlock代碼如下，XCHG的本質也一樣。
  
  mutex_lock的代碼和上面enter_region的代碼很相似，我們可以對比著看一下:
  
• 上面代碼最大的區別你看出來了嗎？
• ?根據上面我們對TSL的分析，我們知道，如果TSL判斷沒有進入臨界區的進程會進行無限循環獲 取鎖，而在TSL的處理中，如果mutex正在使用，那么就調度其他線程進行處理。所以上面最大 的區別其實就是在判斷mutexTTSL之后的處理。
• ?在（用戶）線程中，情況有所不同，因為沒有時鐘來停止運行時間過長的線程。結果是通過忙等待 的方式來試圖獲得鎖的線程將永遠循環下去，決不會得到鎖，因為這個運行的線程不會讓其他線程運行從而釋放鎖，其他線程根本沒有獲得鎖的機會。在后者獲取鎖失敗時，它會調用 thread-yield將CPU放棄給另外一個線程。結果就不會進行忙等待。
• 在該線程下次運行時,它再一次對鎖進行測試。
• 上面就是enter_region和mutexjock的差別所在。由于thread_yield僅僅是一個用戶空間的線程調 度，所以它的運行非常快捷。
• 這樣，mutex_lock和mutex_unlock都不需要任何內核調用。通過 使用這些過程，用戶線程完全可以實現在用戶空間中的同步，這個過程僅僅需要少量的同步。
• 我們上面描述的互斥量其實是一套調用框架中的指令。從軟件角度來說，總是需要更多的特性和同步原 語。
• 例如，有時線程包提供一個調用mutex_trylock ,這個調用嘗試獲取鎖或者返回錯誤碼，但是 不會進行加鎖操作。這就給了調用線程一個靈活性，以決定下一步做什么，是使用替代方法還是等候下 去。

Futexes

隨著并行的增加，有效的同步(synchronization)和鎖定(locking)對于性能來說是非常重要的。

• 如果進程等待時間很短，那么自旋鎖(Spin lock)是非常有效；但是如果等待時間比較長，那么這會 浪費CPU周期。
• 如果進程很多，那么阻塞此進程，并僅當鎖被釋放的時候讓內核解除阻塞是更有效的 方式。
• 不幸的是，這種方式也會導致另外的問題：它可以在進程競爭頻繁的時候運行良好，但是在競爭 不是很激烈的情況下內核切換的消耗會非常大，而且更困難的是，預測鎖的競爭數量更不容易。

有一種有趣的解決方案是把兩者的優點結合起來，提出一種新的思想，稱為futex ,或者是快速用 戶空間互斥(fast user space mutex)

是不是聽起來很有意思？

• futex是Linux中的特性實現了基本的鎖定(很像是互斥鎖)而且避免了陷入內核中，因為內核的切換的開銷非常大，這樣做可以大大提高性能。

• futex由兩部分組成：內核服務和用戶庫。內核服務提供 了了一個 等待隊列(wait queue)允許多個進程在鎖上排隊等待。除非內核明確的對他們解除阻塞， 否則它們不會運行。
  

• 對于一個進程來說，把它放到等待隊列需要昂貴的系統調用，這種方式應該被避免。在沒有競爭的情況 下，futex可以直接在用戶空間中工作。這些進程共享一個32位整數(integer)作為公共鎖變量。

• 假設鎖的初始化為1,我們認為這時鎖已經被釋放了。線程通過執行原子性的操作減少并測試 (decrement and test)來搶占鎖。

• decrement and set是Linux中的原子功能，由包裹在C函數中的內聯匯編組成，并在頭文件中進行定義。

• 下一步，線程會檢查結果來查看鎖是否已經被釋放。如果鎖 現在不是鎖定狀態，那么剛好我們的線程可以成功搶占該鎖。
• 然而，如果鎖被其他線程持有，搶占鎖的 線程不得不等待。在這種情況下，futex庫不會自旋，但是會使用一個系統調用來把線程放在內核中的 等待隊列中。
• 這樣一來，切換到內核的開銷已經是合情合理的了，因為線程可以在任何時候阻塞。
• 當線 程完成了鎖的工作時，它會使用原子性的增加并測試(increment and test)釋放鎖，并檢查結果以 查看內核等待隊列上是否仍阻止任何進程。
• 如果有的話，它會通知內核可以對等待隊列中的一個或多個 進程解除阻塞。如果沒有鎖競爭，內核則不需要參與競爭。

Pthreads中的互斥量

• Pthreads提供了一些功能用來同步線程。最基本的機制是使用互斥量變量，可以鎖定和解鎖，用來保護 每個關鍵區域。
• 希望進入關鍵區域的線程首先要嘗試獲取mutex。如果mutex沒有加鎖，線程能夠馬 上進入并且互斥量能夠自動鎖定，從而阻止其他線程進入。
• 如果mutex已經加鎖，調用線程會阻塞， 直到mutex解鎖。如果多個線程在相同的互斥量上等待，當互斥量解鎖時，只有一個線程能夠進入并 且重新加鎖。

下面是與互斥量有關的函數調用

• 向我們想象中的一樣，mutex能夠被創建和銷毀，扮演這兩個角色的分別是Phread_mutex_init和 Pthread_mutex_destroy。
• mutex也可以通過Pthread_mutex_lock來進行加鎖，如果互斥量已 經加鎖，則會阻塞調用者。
• 還有一個調用Pthread_mutex_trylock用來嘗試對線程加鎖，當mutex 已經被加鎖時，會返回一個錯誤代碼而不是阻塞調用者。這個調用允許線程有效的進行忙等
• 最 后，Pthread_mutex_unlock會對mutex解鎖并且釋放一個正在等待的線程。

除了互斥量以外，Pthreads還提供了第二種同步機制：條件變量(condition variables)。

• mutex可以很好的允許或阻止對關鍵區域的訪問。條件變量允許線程由于未滿足某些條件而阻塞。絕大 多數情況下這兩種方法是一起使用的。
• 下面再來重新認識一下生產者和消費者問題：一個線程將東西放在一個緩沖區內，由另一個線程將它們 取出。
• 如果生產者發現緩沖區沒有空槽可以使用了，生產者線程會阻塞起來直到有一個線程可以使用。 生產者使用mutex來進行原子性檢查從而不受其他線程干擾。
• 但是當發現緩沖區已經滿了以后，生產 者需要一種方法來阻塞自己并在以后被喚醒。

這便是條件變量做的工作。

• 上表中給出了一些調用用來創建和銷毀條件變量。條件變量上的主要屬性是Pthread_cond_wait和 Pthread_cond_signal
• 前者阻塞調用線程，直到其他線程發出信號為止（使用后者調用）。阻塞 的線程通常需要等待喚醒的信號以此來釋放資源或者執行某些其他活動。只有這樣阻塞的線程才能繼續 工作。條件變量允許等待與阻塞原子性的進程
• Pthread_cond_broadcast用來喚醒多個阻塞的、 需要等待信號喚醒的線程。
• 需要注意的是，條件變量（不像是信號量）不會存在于內存中。如果將一個信號量傳遞給一個沒有線程等待的條件變量，那么這個信號就會丟失，這個需要注意

下面是一個使用互斥量和條件變量的例子:

2.管程

為了能夠編寫更加準確無誤的程序，Brinch Hansen和Hoare提出了一個更局級的同步原語叫做 管程 (monitor)

他們兩個人的提案略有不同，通過下面的描述你就可以知道。

• 管程是程序、變量和數據 結構等組成的一個集合，它們組成一個特殊的模塊或者包。進程可以在任何需要的時候調用管程中的程序，但是它們不能從管程外部訪問數據結構和程序。

下面展示了一種抽象的，類似Pascal語言展示的 簡潔的管程。不能用C語言進行描述，因為管程是語言概念而C語言并不支持管程。

• 管程有一個很重要的特性，即在任何時候管程中只能有一個活躍的進程，這一特性使管程能夠很方便的 實現互斥操作。
• 管程是編程語言的特性，所以編譯器知道它們的特殊性，因此可以采用與其他過程調用 不同的方法來處理對管程的調用。
• 通常情況下，當進程調用管程中的程序時，該程序的前幾條指令會檢 查管程中是否有其他活躍的進程。如果有的話，調用進程將被掛起，直到另一個進程離開管程才將其喚 醒。如果沒有活躍進程在使用管程，那么該調用進程才可以進入。
• 進入管程中的互斥由編譯器負責，但是一種通用做法是使用 互斥量(mutex)和 二進制信號量 (binary semaphore) ，由于編譯器而不是程序員在操作，因此出錯的幾率會大大降低。
• 在任何時 候，編寫管程的程序員都無需關心編譯器是如何處理的。他只需要知道將所有的臨界區轉換成為管程過 程即可。絕不會有兩個進程同時執行臨界區中的代碼。
• 即使管程提供了一種簡單的方式來實現互斥，但在我們看來，這還不夠。因為我們還需要一種在進程無 法執行被阻塞。

在生產者-消費者問題中，很容易將針對緩沖區滿和緩沖區空的測試放在管程程序中， 但是生產者在發現緩沖區滿的時候該如何阻塞呢？

• 解決的辦法是引入條件變量(condition variables)以及相關的兩個操作wait和signal

• 一個管程程序發現它不能運行時(例如，生產者發現緩沖區已滿)，它會在某個條件變量(如full)上執行wait操作。這個操作造成調用進程阻塞，并且還將另一個以前等在管程之外的進程調入管程。

• 在前面的pthread中我們已經探討過條件變量的實現細節了。另一個進程，比如消費者可以通過執行 signal來喚醒阻塞的調用進程。

• Brinch Hansen和Hoare在對進程喚醒上有所不同，Hoare建議讓新喚醒的進程繼續運行；而掛 起另外的進程。

• 而Brinch Hansen建議讓執行signal的進程必須退出管程，這里我們采用Brinch Hansen的建議，因為它在概念上更簡單，并且更容易實現。

• 如果在一個條件變量上有若干進程都在等待，則在對該條件執行signal操作后，系統調度程序只能選擇 其中一個進程恢復運行。

• 順便提一下，這里還有第三種方式，它的理論是讓執行signal的進程繼續運 行，等待這個進程退出管程時，其他進程才能進入管程。

• 條件變量不是計數器。條件變量也不能像信號量那樣積累信號以便以后使用。所以，如果向一個條件變 量發送信號，但是該條件變量上沒有等待進程，那么信號將會丟失。也就是說，wait操作必須在 signal之前執行。
  
  

• 我們可能覺得wait和signal操作看起來像是前面提到的sleep和wakeup ,而且后者存在嚴重的競爭 條件。

• 它們確實很像，但是有個關鍵的區別：sleep和wakeup之所以會失敗是因為當一個進程想睡眠 時，另一個進程試圖去喚醒它。

• 使用管程則不會發生這種情況。管程程序的自動互斥保證了這一點，如 果管程過程中的生產者發現緩沖區已滿，它將能夠完成wait操作而不用擔心調度程序可能會在wait完 成之前切換到消費者。甚至，在wait執行完成并且把生產者標志為不可運行之前，是不會允許消費者 進入管程的。

• 盡管類Pascal是一種想象的語言，但還是有一些真正的編程語言支持，比如Java，Java是能夠支持管程的，它是一種 面向對象的語言，支持用戶級線程，還允許將方法劃分 為類。

• 只要將關鍵字synchronized關鍵字加到方法中即可。Java能夠保證一旦某個線程執行該方 法，就不允許其他線程執行該對象中的任何synchronized方法。沒有關鍵字synchronized ,就不能保證沒有交叉執行。

下面是Java使用管程解決的生產者-消費者問題：

• 上面的代碼中主要設計四個類，外部類(outer class) Producerconsumer創建并啟動兩個線程，p 和c
• 第二個類和第三個類Producer和Consumer分別包含生產者和消費者代碼。最
  后，Our_monitor是管程，它有兩個同步線程，用于在共享緩沖區中插入和取出數據。

在前面的所有例子中，生產者和消費者線程在功能上與它們是相同的。

• 生產者有一個無限循環，該無限 循環產生數據并將數據放入公共緩沖區中；消費者也有一個等價的無限循環，該無限循環用于從緩沖區 取出數據并完成一系列工作。
• 程序中比較耐人尋味的就是Our_monitor了，它包含緩沖區、管理變量以及兩個同步方法。
• 當生產 者在insert內活動時，它保證消費者不能在remove方法中運行，從而保證更新變量以及緩沖區的安全 性，并且不用擔心競爭條件。
• 變量count記錄在緩沖區中數據的數量。變量1。是緩沖區槽的序號， 指出將要取出的下一個數據項。
• 類似地，hi是緩沖區中下一個要放入的數據項序號。允許lo = hi,含義是在緩沖區中有0個或N個數據。
• Java中的同步方法與其他經典管程有本質差別：Java沒有內嵌的條件變量。然而，Java提供了 wait 和notify分別與sleep和wakeup等價。
• 通過臨界區自動的互斥，管程比信號量更容易保證并行編程的正確性。
• 但是管程也有缺點，我們前面說 到過 管程是一個編程語言的概念，編譯器必須要識別管程并用某種方式對其互斥作出保證。C、Pascal 以及大多數其他編程語言都沒有管程，所以不能依靠編譯器來遵守互斥規則。
• 與管程和信號量有關的另一個問題是，這些機制都是設計用來解決訪問共享內存的一個或多個CPU上 的互斥問題的。通過將信號量放在共享內存中并用TSL或XCHG指令來保護它們，可以避免競爭。
• 但是 如果是在分布式系統中，可能同時具有多個CPU的情況，并且每個CPU都有自己的私有內存 昵，它們通過網絡相連，那么這些原語將會失效。因為信號量太低級了，而管程在少數幾種編程語言之 外無法使用，所以還需要其他方法。

3.消息傳遞

上面提到的其他方法就是 消息傳遞(messaage passing)

• 這種進程間通信的方法使用兩個原語 send和receive ,它們像信號量而不像管程，是系統調用而不是語言級別。

示例如下

• send方法用于向一個給定的目標發送一條消息，receive從一個給定的源接受一條消息。如果沒有消 息，接受者可能被阻塞，直到接受一條消息或者帶著錯誤碼返回。

消息傳遞系統的設計要點

消息傳遞系統現在面臨著許多信號量和管程所未涉及的問題和設計難點，尤其對那些在網絡中不同機器 上的通信狀況。

• 例如，消息有可能被網絡丟失。為了防止消息丟失，發送方和接收方可以達成一致：
• 一旦接受到消息后，接收方馬上回送一條特殊的確認(acknowledgement)消息
• 如果發送方在一段時 間間隔內未收到確認，則重發消息。

現在考慮消息本身被正確接收，而返回給發送著的確認消息丟失的情況。發送者將重發消息，這樣接受 者將收到兩次相同的消息。

對于接收者來說，如何區分新的消息和一條重發的老消息是非常重要的。

• 通常采用在每條原始消息中嵌 入一個連續的序號來解決此問題。

• 如果接受者收到一條消息，它具有與前面某一條消息一樣的序號，就 知道這條消息是重復的，可以忽略。

• 消息系統還必須處理如何命名進程的問題，以便在發送或接收調用中清晰的指明進程。

• 身份驗證 (authentication)也是一個問題，比如客戶端怎么知道它是在與一個真正的文件服務器通信，從發 送方到接收方的信息有可能被中間人所篡改。

用消息傳遞解決生產者?消費者問題

現在我們考慮如何使用消息傳遞來解決生產者-消費者問題，而不是共享緩存。

下面是一種解決方式

• 假設所有的消息都有相同的大小，并且在尚未接受到發出的消息時，由操作系統自動進行緩沖。
• 在該解 決方案中共使用N條消息，這就類似于一塊共享內存緩沖區的N個槽。消費者首先將N條空消息發送 給生產者。
• 當生產者向消費者傳遞一個數據項時，它取走一條空消息并返回一條填充了內容的消息。
• 通 過這種方式，系統中總的消息數量保持不變，所以消息都可以存放在事先確定數量的內存中。
• 如果生產者的速度要比消費者快，則所有的消息最終都將被填滿，等待消費者，生產者將被阻塞，等待 返回一條空消息。
• 如果消費者速度快，那么情況將正相反：所有的消息均為空，等待生產者來填充，消 費者將被阻塞，以等待一條填充過的消息。

消息傳遞的方式有許多變體，下面先介紹如何對消息進行編址：

• ?—種方法是為每個進程分配一個唯一的地址，讓消息按進程的地址編址。
• ?另一種方式是引入一個新的數據結構，稱為 信箱(mailbox)，信箱是一個用來對一定的數據進行 緩沖的數據結構，信箱中消息的設置方法也有多種，典型的方法是在信箱創建時確定消息的數量。

在使用信箱時，在send和receive調用的地址參數就是信箱的地址，而不是進程的地址。

當一個 進程試圖向一個滿的信箱發送消息時，它將被掛起，直到信箱中有消息被取走，從而為新的消息騰 出地址空間。

4.屏障

最后一個同步機制是準備用于進程組而不是進程間的生產者-消費者情況的。

• 在某些應用中劃分了若干 階段，并且規定，除非所有的進程都就緒準備著手下一個階段，否則任何進程都不能進入下一個階段, 可以通過在每個階段的結尾安裝一個屏障(barrier)來實現這種行為。
• 當一個進程到達屏障時，它 會被屏障所攔截，直到所有的屏障都到達為止。屏障可用于一組進程同步

如下圖所示

• 在上圖中我們可以看到，有四個進程接近屏障，這意味著每個進程都在進行運算，但是還沒有到達每個 階段的結尾。
• 過了一段時間后，A、B、D三個進程都到達了屏障，各自的進程被掛起，但此時還不能進 入下一個階段昵，因為進程B還沒有執行完畢。
• 結果，當最后一個C到達屏障后，這個進程組才能夠 進入下一個階段。

5.避免鎖：讀-復制-更新

最快的鎖是根本沒有鎖。

問題在于沒有鎖的情況下，我們是否允許對共享數據結構的并發讀寫進行訪 問。

• 答案當然是不可以。

• 假設進程A正在對一個數字數組進行排序，而進程B正在計算其平均值
• 而 此時你進行A的移動，會導致B會多次讀到重復值，而某些值根本沒有遇到過。

• 然而，在某些情況下，我們可以允許寫操作來更新數據結構，即便還有其他的進程正在使用。
• 竅門在于 確保每個讀操作要么讀取舊的版本，要么讀取新的版本

例如下面的樹

• 上面的樹中，讀操作從根部到葉子遍歷整個樹。
• 加入一個新節點X后，為了實現這一操作，我們要讓這 個節點在樹中可見之前使它”恰好正確”：我們對節點X中的所有值進行初始化，包括它的子節點指針。
• 然后通過原子寫操作，使X稱為A的子節點。所有的讀操作都不會讀到前后不一致的版本
  
• 在上面的圖中，我們接著移除B和D
• 首先，將A的左子節點指針指向C。所有原本在A中的讀操作 將會后續讀到節點C,而永遠不會讀到B和D
• 也就是說，它們將只會讀取到新版數據。同樣，所有 當前在B和D中的讀操作將繼續按照原始的數據結構指針并且讀取舊版數據。
• 所有操作均能正確運 行，我們不需要鎖住任何東西。而不需要鎖住數據就能夠移除B和D的主要原因就是 讀-復制-更新 (Ready-Copy-Update,RCU),將更新過程中的移除和再分配過程分離開。

總結

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

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