一、同步與互斥的概念

1.1 同步與異步

• 異步性是指，各并發執行的進程以各自獨立的、不可預知的速度向前推進。

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

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

1.2 進程互斥

進程的“并發”需要“共享”的支持。各個并發執行的進程不可避免的需要共享一些系統資源(比如內存，又比如打印機、攝像頭這樣的I/O設備)

我們把一個時間段內只允許一個進程使用的資源稱為臨界資源。許多物理設備(比如攝像頭、打印機)都屬于臨界資源。此外還有許多變量、數據、內存緩沖區等都屬于臨界資源。對臨界資源的訪問，必須互斥地進行。

互斥，亦稱間接制約關系。進程互斥指當一個進程訪問某臨界資源時，另一個想要訪問該臨界資源的進程必須等待。當前訪問臨界資源的進程訪問結束，釋放該資源之后，另一個進程才能去訪問臨界資源。

• 對臨界資源的互斥訪問，可以在邏輯上分為如下四個部分：
  

• 為了實現對臨界資源的互斥訪問，同時保證系統整體性能，需要遵循以下原則:

  1.空閑讓進。臨界區空閑時，可以允許一個請求進入臨界區的進程立即進入臨界區;

  2.忙則等待。當已有進程進入臨界區時，其他試圖進入臨界區的進程必須等待 （拒絕搶資源）；

  3.有限等待。對請求訪問的進程，應保證能在有限時間內進入臨界區 （保證不會饑餓）

  4.讓權等待。當進程不能進入臨界區時，應立即釋放處理機，防止進程忙等待（不讓“占茅坑”）。

二、進程互斥的實現

2.1 軟件實現

2.1.1 單標志法

• 算法思想：兩個進程在訪問完臨界區后會把使用臨界區的權限轉交給另一個進程。也就是說每個進程進入臨界區的權限只能被另一個進程賦予。
  
• 出現的問題：①⑤
  這個算法只能按 P0 →P1→P0 →P1→…這樣輪流訪問。這種必須“輪流訪問”帶來的問題是，如果此時允許進入臨界區的進程是 P0，而P0一直不訪問臨界區，那么雖然此時臨界區空閑，但是并不允許P1訪問。因此，單標志法存在的主要問題是:違背“空閑讓進”原則。

2.1.2 雙標志先檢查法

• 算法思想：設置一個布爾型數組flag[ ]，數組中各個元素用來標記各進程想進入臨界區的意愿。
  比如“flag[0]=ture”意味著0號進程P0現在想要進入臨界區。每個進程在進入臨界區之前先檢查當前有沒有別的進程想進入臨界區，如果沒有，則把自身對應的標志flag[ ]設為true，之后開始訪問臨界區。
  
• 出現的問題：①⑤②⑥③⑦
  P0和P1將會同時訪問臨界區。因此，雙標志先檢查法的主要問題是：違反“忙則等待”原則。原因在于，進入區的“檢查”和“上鎖”兩個處理不是一氣呵成的。“檢查”后，“上鎖”前可能發生進程切換。

2.1.3 雙標志后檢查法

• 算法思想：雙標志先檢查法的改版。前一個算法的問題是先“檢查”后“上鎖”，但是這兩個操作又無法一氣呵成，因此導致了兩個進程同時進入臨界區的問題。因此，人們又想到 先上鎖后檢查 的方法，來避免上述問題。
  
• 出現的問題：①⑤②⑥
  P0和P1將都無法進入臨界區。因此，雙標志后檢查法雖然解決了“忙則等待”的問題，但是又違背了“空閑讓進”和“有限等待”原則，會因各進程都長期無法訪問臨界資源而產生“饑餓”現象。兩個進程都爭著想進入臨界區，但是誰也不讓誰，最后誰都無法進入臨界區。

2.1.4 Peterson法

• 算法思想：結合雙標志法、單標志法的思想。如果雙方都爭著想進入臨界區，那可以讓進程嘗試“孔融讓梨”（謙讓）。做一個有禮貌的進程。
  

• 出現的問題：Peterson算法用軟件方法解決了進程互斥問題，遵循了空閑讓進、忙則等待、有限等待三個原則，但是依然未遵循讓權等待的原則。

2.2 硬件實現

2.2.1 中斷指令

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

• 優點：簡單，高效
• 缺點：不適用于多處理機（也就是另外一個用戶進程也要使用臨界資源，也使用這樣的方法，那么就會導致兩個進程同時訪問臨界資源的情況)；只適用于操作系統內核進程，不適用于用戶進程(因為開/關中斷指令只能運行在內核態，這組指令如果能讓用戶隨意使用會很危險)

2.2.2 TestAndSet指令

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

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

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

2.2.3 Swap指令

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

三、互斥鎖

• 互斥鎖的主要缺點是：忙等待，當有一個進程在臨界區中，任何其他進程在進入臨界區時必須連續循環調用acquireO。當多個進程共享同一CPU時，就浪費了CPU周期。因此，互斥鎖通常用于多處理器系統，一個線程可以在一個處理器上等待，不影響其他線程的執行。

四、信號量機制

• 信號量:其實就是一個變量，可以用一個信號量來表示系統中某種資源的數量，比如：系統中只有一臺打印機，就可以設置一個初值為1的信號量
• 一對原語：wait(S)原語和signal(S)原語，括號里的信號量S其實就是函數調用時傳入的一個參數。wait(S)、signal(S) 兩個操作分別寫為P(S)、V(S)
• 對信號量的操作只有三種：初始化、P操作、V操作

4.1 整型信號量

用一個整數型的變量作為信號量，用來表示系統中某種資源的數量。

4.2 記錄型信號量

• P(S)：申請一個資源S，如果資源不夠就阻塞等待。
• V(S)：釋放一個資源S，如果有進程在等待該資源，就喚醒一個進程。
• P、V操作必須成對出現。缺少P(mutex)就不能保證臨界資源的互斥訪問。缺少V(mutex)會導致資源永不被釋放，等待進程永不被喚醒。

4.3 信號量機制實現

4.3.1 實現進程互斥

4.3.2 實現進程同步

• 實現同步的過程：
  • 若先執行到V(S)操作，則S++后S=1,釋放一個資源S。之后當執行到P(S)操作時，由于S=1，表示有可用資源，會執行S--，S=0，P2進程不會執行block原語，而是繼續往下執行代碼4，5，6。
  • 若先執行到P(S)操作，由于S=0，S--后S=-1，表示此時沒有可用資源，因此P操作中會執行block原語，主動請求阻塞。之后當執行完代碼2，繼而執行V(S)操作，S++，使S變回0，由于此時有進程在該信號量對應的阻塞隊列中，因此會在V操作中執行wakeup原語，喚醒P2進程。這樣P2就可以繼續執行代碼4了

4.3.3 實現進程的前驅關系