操作系統-王道老師

第二章02-進程同步和進程互斥

目錄：

1.進程同步、進程互斥
????1.1 進程同步
????1.2 進程互斥
2.進程互斥的軟件實現方法
????2.1 單標志法
????2.2 雙標志先檢查
????2.3 雙標志后檢查
????2.4 Peterson算法
3.進程互斥的硬件實現方法
????3.1 中斷屏蔽方法
????3.2 TestAndSet（TS指令和TSL指令）
????3.3 Swap指令
4.信號量機制
????4.1 整形信號量
????4.2 記錄性信號量
????4.3 信號量實現進程互斥
????4.4 信號量實現進程同步
????4.5 信號量實現進程的前驅關系
5.生產者、消費者問題
6.多生產者、多消費者問題
7.吸煙者問題
8.讀者、寫者問題
9.哲學家進餐問題

1.進程同步、進程互斥

1.1 進程同步

舉例： 進程通信–管道通信

讀進程和寫進程并發地運行，由于并發必然導致異步性，因此“寫數據”和“讀數據”兩個操作執行的先后順序是不確定的。而實際應用中，又必須按照 “寫數據一讀數據”的順序來執行的。如何解決這種異步問題，就是 “進程同步”所討論的內容。

基本概念： 同步亦稱直接制約關系，它只為完成某種任務而建立的兩個或多個進程，這些進程因為需要在某些位置上協調它們的工作次序而產生制約關系。進程之間的直接制約關系就是源于它們之間的相互合作。

1.2 進程互斥

1.進程的“并發”需要“共享”的支持。各個并發執行的進程不可避免的需要共享一些系統資源（比如內存，又比如打印機、攝像頭這樣的I/O設備）
2.我們把一個時間段內只允許一個個進程使用的資源稱為臨界資源。許多物理設備（比如攝像頭、打印機）都屬于臨界資源。此外還有許多變量、數據、內存緩沖區等都屬于臨界資源。
3.對臨界資源的訪問，必須互斥地進行,互斥，亦稱間接的約束關系。進程互斥指當一個進程訪問某臨界資源時，另一個想訪問該臨界資源的進程必須等。當前訪問臨界資源的進程結束，釋放該資源之后這個，另一個進程才能訪問臨界資源。

對臨界資源的訪問，從邏輯上分為以下幾個部分：

互斥訪問臨界資源，需要循序以下原則：

1.空閑等待。臨界區空閑時，可以允許一個請求進入臨界區的進程立即進入臨界區。
2.忙則等待。當已有進程進入臨界區時，其他視圖進入臨界區的進程必須等待。
3.有限等待。對請求訪問的進程，應保證能在有限時間內進入臨界區（保證不會餓死）。
4.讓權等待。當進程不能進入臨界區時，應立即釋放處理機，防止進程忙等待。

2.進程互斥的軟件實現方法

2.1 單標志法

算法思想：

兩個進程在訪問臨界區后會把使用臨界區的限權轉交給另一個進程，也就是說每個進程進入臨界區的權限只能被另一個進程賦予。

主要問題：

不遵循“空閑讓進原則”

2.2 雙標志先檢查

算法思想：

設置一個布爾型數組flag[]，數組中個元素用來標記個進程想進入臨界區的意愿，比如“flag[0] = true”意味著0號進程P0想要進入臨界區。每個進程在進入臨界區之前先檢查當前沒有別的進程想要進入臨界區，如果沒有，則把自身對應的flag[i]設為true,之后開始訪問臨界區。

主要問題：

若按照1、5、2、6、3、7…順序執行,P0和P1都進入了訪問臨界區，因此違反“忙則等待”原則。

2.3 雙標志后檢查

算法思想：

雙標志先檢查算法的改版。前一個算法的問題在于先“檢查”后上鎖，但是兩個操作沒辦法一氣呵成，因此導致了兩個進程同事進入臨界區的問題。因此人們想到了先“上鎖”后 “檢查”的方法。

主要問題:

若按照1、5、2、6的順序執行，P0和P1都不能訪問臨界區，雖然解決了“忙著等待”的問題，但是違背了“空閑讓進”和“有限等待”原則，會各進程都長期無法訪問臨界資源而產生“饑餓”現象。

2.4 Peterson算法

算法思想：

雙標志后檢查法中，兩個進程都爭著想要進入臨界區，但是誰都不讓誰，最后誰都無法進入臨界區。GrayL.Peterson想到了一個方法，如果雙方都想爭著進入臨界區，那可以讓進程嘗試“孔融讓梨”，主動的讓對方先進入臨界區。

主要問題：

不遵循“讓權等待”原則，會發生“盲等”。

3.進程互斥的硬件實現方法

3.1 中斷屏蔽方法

利用 “開/關中斷指令” 實現（與原語的實現思想相同，即在某進程開始訪問臨界區到結束訪問為止，都不允許被中斷，也就 不能發生進程切換，因此也不可能發生兩個同時訪問臨界區的情況）。

優點：

簡單、高效。

缺點：

不適用于多處理機，只適用于操作系統內核進程，不適用于用戶進程（因為開/關中斷指令只能運行在內核態，這組指令如果能讓用戶隨意使用會很危險）。

3.2 TestAndSet（TS指令和TSL指令）

TSL 指令是用硬件實現的，執行的過程不允許被中斷，只能一氣呵成。以下是用C語言描述的邏輯

算法思想：

若剛開始lock是false，則TSL返回的old 值為false, while 循環條件不滿足，直接跳過循環，進入臨界區。若剛開始 lock是true，則執行TLS后old返回的值為true，while循環條件滿足，會一直循環，直到當前訪問臨界區的進程在退出區進行 “解鎖”。
相比軟件實現方法，TSL指令把“上鎖”和“檢查” 操作用硬件的方式變成了一氣呵成的原子操作。

優點：

實現簡單，無需軟件實現方法嚴格檢查是否會有裸機漏洞，適用于多處理機。

3.3 Swap指令

Swap 指令是用硬件實現的，執行的過程不允許被中斷，只能一氣呵成。以下是用C語言描述的邏輯

算法思想：

邏輯上來看 Swap 和TSL并無太大區別，都是先記錄下此時臨界區是否己經被上鎖（記錄在old變量上）,再將上鎖標記 lock設置為true，最后檢查old，如果old為false則說明之前沒有別的進程對臨界區上鎖，則可跳出循環，進入臨界區。

優點：

實現簡單，無需像軟件實現方法那樣嚴格檢查是否會有邏輯漏洞；適用于多處理機環境。

缺點：

不滿足 “讓權等待”原則，暫時無法進入臨界區的進程會占用CPU并循環執行TSL指令，從而導致“忙等”。

4.信號量機制

1.用戶進程可以通過使用操作系統提供的一對原語來對信號量進行操作，從而很方便的實現了進程互斥、進程同步。

2.信號量其實就是一個變量（可以是一個整數，也可以是更復雜的記錄型變量），可以用一個信號量來表示系統中某種資源的數量。，比如：系統中只有一臺打印機，就可以設置一個初值為1的信號量。

3.原語是一種特殊的程序段，其執行只能一氣呵成，不可被中斷。原語是由關中斷/開中斷指令實現的。軟件解決方案的主要問題是由 “進入區的各種操作無法一氣呵成”，因此如果能把進入區、退出區的操作用原語來實現，是這些操作能“一氣呵成”就能避免問題。

4.一對原語：wait(S) 原語和 signal(S) 原語，可以把原語理解為我們自己寫的函數，函數名分別為 wait 和 signal，括號里的信號量S其實就是函數調用時傳入的一個參數。

5.wait、signal 原語常簡稱為P、V操作（來自荷蘭語 proberen 和 verhogen）。因此，做題的時候常把wait(S)、signal(S) 兩個操作分別寫為 P(S)、V(S)。

4.1 整形信號量

基本概念：

用一個整形的變量作為信號量，用來表示系統中某種資源的數量，這種變量區別于普通變量，對信號量的操作只有出事、P操作、V操作。

4.2 記錄性信號量

基本概念：

整形信號量的缺陷是存在“忙等”問題，因此人們提出了“記錄型信號量”，即用記錄型數據結構表示的信號量。

注：下面的P(S)操作 V(S) 無特別說明，都是記錄性信號量。

4.3 信號量實現進程互斥

1.分析并發進程的關鍵活動，劃定臨界區（如：對臨界資源打印機的訪問就應放在臨界區）
2.設置互斥信號量mutex，初值為1
3.在臨界區之前執行 P(mutex)
4.在臨界區之后執行 V(mutex)

注意：

1.對不同的臨界資源需要設置不同的互斥信號變量。
2.P、V操作必須成對出現。缺少P(mutex) 就不能保證臨界資源的互斥訪問。缺少 v(mutex)會導致資源永不被釋放，等待進程永不被喚醒。

4.4 信號量實現進程同步

1.分析什么地方需要實現“同步關系”，即必須保證“一前一后”執行的兩個操作（或兩句代碼）
2.設置同步信號量S,初始為0。
3.在“前操作”之后執行 V(S)。
4.在“后操作”之前執行 P(S)。
舉例：下面要求在執行代碼2操作執行了，代碼4操作才能執行，所以只要在前操作之后執行一個V(S)，在后后操作之前執行一個P(S)。

4.5 信號量實現進程的前驅關系

1.分析問題畫出前驅圖，把每對前驅關系都看成一個同步問題。
2.下面的步驟與上面的信號量實現進程同步一致。

常見的PV解決互斥和同步問題(只貼上了圖片)

5.生產者、消費者問題

6.多生產者、多消費者問題

7.吸煙者問題

8.讀者、寫者問題

9.哲學家進餐問題

進程同步和進程互斥小結，歡迎大家交流學習！

總結

以上是生活随笔為你收集整理的操作系统-进程同步和进程互斥的全部內容，希望文章能夠幫你解決所遇到的問題。

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