電腦作業系統-並發控制

2022 年 11 月 3 日
筆記
電腦系統

什麼是並發控制

作業系統中可能有多道程式同時運行的情況，需要對程式進行同步與互斥的控制，以實現並發控制。

並發控制的關鍵問題

死鎖
飢餓

互斥

多道程式系統中存在許多進程，它們共享各種資源，然而有很多資源一次只能供一個進程使用。一次僅允許一個進程使用的資源稱為臨界資源（如印表機等）。那麼我們的多個程式就需要保證不同時的去訪問臨界資源（我們稱這段訪問臨界資源的程式碼為臨界區）。這個保障不同時的機制就叫互斥，顧名思義：互相排斥。
互斥的要求（滿足以下程式進入臨界區的要求才能保證互斥正常執行）

空閑讓進（因為，當無進程處於臨界區時，表明臨界資源處於空閑狀態，應允許一個請求進入臨界區的進程立即進入自己的臨界區，以有效地利用臨界資源。）
忙則等待（如果當前已有程式進入臨界區，訪問臨界資源，則請求進入臨界區的進程應該等待）
有限等待（對等待規定時間或者次數限制，否則會陷入死等）
讓權等待（如果進程無法進入自己的臨界區要及時釋放，避免其他進程死等）

互斥的具體實現方法

軟體方法
主要是Dekker互斥演算法和Peterson互斥演算法，（由於只能用於兩個進程，這裡不再贅述）
硬體方法
1. 屏蔽中斷
由於一個程式執行的時候，有可能因為調度演算法的原因，被系統中斷，然後執行另一個程式，因此可以直接屏蔽中斷讓程式一直執行不被打斷。但是顯然，這樣的方法程式就會不受控制，不太完美。
2. Test and Set指令
屬於系統原語（執行過程不會被打斷）
Test and Set偽程式碼
```
  function testset(var i:integer):boolen;
    begin
    if i = 0 then       
      begin
        i := 1;
        testset := true;
      end
    else testset := false
    end.
```

上述程式碼就是Test and Set 最根本的思想就是驗證一個標識變數i，如果為0就是可以進入臨界區，然後重置為1表示已經有進程進去了，然後返回true。如果已經發現是1，就是有程式進去了，就得返回false。
使用偽程式碼

      program mutualexculusion;
      const n := ...;/*進程數*/
      var flag:integer; //標識整數
      procedure P(i:integer);
      begin
        repeat
      repeat {nothing} untill testset(flag);
        <臨界區>;
        flag := 0;
        <其餘位置>
       forever
      end;

上述程式碼就是先設置一個本地的flag標識標識是否有進程，然後不斷的去調用testset，得到true就進入臨界區訪問臨界資源，結束後重置flag，如果得到false就直接再次循環
顯然testset原語會不斷的循環存在忙則等待的問題
2. Exchange指令(也是原語）

    procedure exchange ( var r :register; var m :memory);
    var temp;
    begin 
      temp :=m;
      m:=r;
      r:= temp;
    end.

    program mutualexclusion;
    const n=...;/*進程數*
    var bolt:integer;
    procedure P(i:integer);
    varkey:integer;
      begin
       repeat
        key:=1;
        repeat exchange(key,bolt) until key=0;
        <臨界區>;
        bolt:=0;
        <其餘部分>
        forever
      end;

優點 1.適用於單處理器或者共享主存的多處理器中任意數量的進程2.簡單並且容易證明3.可以用於支援多臨界區
缺點 1.忙等待消耗處理器時間2.當進程離開臨界區並且多個進程在等待的時候可能導致飢餓3.死鎖：如果一個低優先順序的進程擁有臨界區並且一個高優先順序進程也需求,那麼高優先順序進程會獲得處理器並等待臨界區

訊號量（極其重要，其實不僅可以做互斥，也可以同步，其實也是在交換資訊，後面詳細說明）
訊號量就是一個整形變數，有一個隊列用來放正在排隊想要使用這一資源的進程

訊號量通過wait申請，signal釋放
偽程式碼

注意到，wait操作就是上來先將訊號量減去1，signal先加上1.因此，wait操作中如果count < 0則說明已經沒有資源了，在signal中如果 >= 0意味著存在資源（這就是一種進程間最簡單的通訊）。
同時也會自身阻塞和被阻塞喚醒這也是一種同步

訊號量類型
1.互斥訊號量（訊號量最大只能1，只允許一個程式拿到訊號量）
2.資源訊號量（大於1的整型，運行多個程式拿到訊號量，模擬出了資源的利用）

同步

同步：是指散布在不同進程之間的若干程式片段，它們的運行必須嚴格按照一定的先後次序來運行，這種次序依賴於要完成的任務。比如數據的收發，必須發送方發送了接收方才能收。

同步是一種更為複雜的互斥嗎，而互斥是一種特殊的同步。互斥是兩個進程或執行緒之間不可以同時運行，它們會互相排斥，必須等待其中的一個運行完，另一個才可以運行。而同步也是不可以同時運行，並且還需要按照某種順序來運行。
（互斥是指某一資源同時只允許一個訪問者對其進行訪問，具有唯一性和排它性。但互斥無法控制對資源的訪問順序，同步是指在互斥的基礎上實現對資源的有序訪問）

剛剛的訊號量其實就是一種同步方法（經典的消費生產者問題就使用這種方法來同步消費者和生產者）
管程機制（其實就是用面向對象方法，用程式語言實現的訊號量，方便開發者使用）詳細點擊此處
消息傳遞（通過消息傳遞通訊來控制同步，不再贅述）詳細點擊此處

需要解決的兩大問題（之後會開一篇詳細說）

死鎖
死鎖的產生
1、互斥條件每一資源或者被分配給一個進程，或者空閑。
2、佔有並請求條件已分配到了一些資源的進程可以申請新的資源
3、不可剝奪條件已分配給某些進程的資源不可被剝奪，只能有佔有它的進程使用完後主動釋放
4、循環等待條件系統必然存在一條有兩個或兩個以上的進程組成的循環，聯眾的每一個進程都在等待相鄰進程所佔用的資源
可以通過上面的條件來預防死鎖（都不太理想）
還有一種著名的銀行家演算法來避免死鎖
飢餓
由於分配的不公平產生，進程在訊號量內無限等待。

Tags: 電腦系統