2024-07-04：操作系統同步與互斥學習筆記

---

并發的進程或者程序在執行的時候會失去封閉性，也就是說如果有兩個程序分別地區使用一個共享的資源，可能會導致每一次運行的結果都不一樣

原因就是我們沒有保護程序a和程序b都要去訪問的這個共享資源x

---

9.1 同步互斥的基本概念

9.1.1 同步關系

相互制約的關系就是同步，同步通俗一點理解就是它們進程之間執行的時候要有一個次序

---

9.1.2 互斥關系

間接相互制約的關系就稱為互斥關系,eg.打印機

---

9.1.3 臨界資源

• 在一段時間內只允許一個進程訪問的資源，稱為臨界資源（或獨占資源）
• 對于臨界資源的共享，各進程之間應該采用互斥方式

“生產者和消費者模型”
counter+ +

首先把變量放到寄存器里面
register1 = counter;
接下來對寄存器進行一個自增
register1 = register1 + 1;
再把結果返回到counter里
counter = register1;

counter- -

首先把變量放到寄存器里面
register2 = counter;
接下來對寄存器進行一個自減
register2 = register2 - 1;
再把結果返回到counter里
counter = register2;

解決辦法：把counter當做臨界資源處理，令進程互斥地訪問變量counter（后面會學到同步機制）

---

9.1.4 臨界區

不管是硬件臨界資源還是軟件的臨界資源，多個進程必須互斥地訪問

這些區本質都是代碼

• 進入區
• 臨界區
• 退出區
• 剩余區

---

9.1.5 同步機制應遵循規則

• 空閑讓進

無進程處于臨界區時，表明臨界區資源空閑，應允許一個請求進入臨界區的進程立即進入自己的臨界區，有效利用資源。

• 忙則等待

已有進程進入臨界區時，表明臨界資源正在被訪問，因而其他試圖進入臨界區的進程必須等待，以保證對臨界資源的互斥訪問

• 有限等待

對要求訪問臨界資源的進程，應保證在有限時間內能進入自己的臨界區，避免陷入”等死“狀態

• 讓權等待

進程不能進入自己的臨界區時，應立即釋放處理機(CPU)，以免進程陷入”忙等“狀態

---

9.2 軟件同步機制

9.2.1 單標志法

• 設置一公用整型變量來標明是否有進程在臨界中，如果已有進程在臨界區，則在進入區通過循環檢查進行等待，進程離開臨界區后則在退出區修改標志
• 單標志法設置一個公用整型變量turn，指示允許進入臨界區的進程編號，turn=0時允許進程P0進入臨界區
• turn=1時允許進程P1進入臨界區，退出臨界區將臨界區使用權賦予另一個進程（Pi推出臨界區時，令turn=j）

兩個進程必須交替進入臨界區，若一個進程不再進入臨界區，則另一個進程也無法進入臨界區，違背了“空閑讓進”準則

---

9.2.2 雙標志先檢查法

雙標志先檢查法設置一個布爾型數組flag[2]，用來標記各個進程想進入臨界區的意愿，flag[i]=true，表示Pi想進入臨界區。

• Pi進入臨界區前，先檢查對方是否進入臨界區，若想，則等待
• 否則，將flag[i]設置為true后，再進入臨界區
• 當Pi退出臨界區時，將flag[i]設置為false

• while循環相當于紅綠燈機制
• 設置對方的flag相當于改對方的紅綠燈
• 但由于兩個進程都是先檢查flag[先看紅綠燈]，初始時均為false[均為綠燈]，所以可能兩個進程同時通過紅綠燈，一起進入臨界區

---

9.2.3 雙標志后檢查法

雙標志后檢查法會檢查對方的標志再設置自己的，這倆操作無法一氣呵成，于是兩個進程可能同時進入臨界區；所以想出了后檢查法，先設置自己的標志，再檢查對方的標志，若對方標志位true則等待；否則進入臨界區

---

9.2.4 peterson算法

peterson算法結合了單標志法和雙標志后檢查法的思想，利用flag[]解決互斥訪問問題，在利用turn解決饑餓問題。

若雙方都爭著進入臨界區，則可讓進程將進入臨界區的機會讓給對方。
每個進程進入臨界區之前，設置自己的flag標志，在設置允許進入turn標志，之后，再同時檢測對方的flag和turn，以保證雙方同時要求進?臨界區時，只允許?個進程進入

沒有做到讓權等待

---

9.3 硬件同步機制

軟件解決各個進程互斥進入臨界區的問題有難度，而且有很大的局限性，所以計算機提供一些特殊的硬件指令來解決問題

9.3.1 關中斷

(1) 關中斷的定義

• 關中斷在計算機組成原理里面接觸過，它指的是去修改CPU中PSW這個寄存器里面的一位，這一位會去控制現在CPU會不會去相應中斷，這個中斷只能擋住可屏蔽中斷，不可屏蔽中斷擋不住
• 操作系統里面進程的調度都是依賴中斷去實現的，比如時鐘中斷
• 有進程再臨界區執行期間，計算機系統關中斷，從而不會引發調度，也就不會有進程或線程切換

(2) 關中斷的缺點

• 濫用終端會導致嚴重后果
• 關中斷時間過長，會影響系統效率
• 關中斷方法不適用于多CPU系統，在一個處理器上關中斷不能防止進程在其他處理器上執行相同臨界代碼

---

9.3.2 Test-and-Set 指令(TS指令)

TS指令可以看作一個執行過程不可分割的函數過程（原語）

• lock有兩種狀態：
• • *lock=FALSE表示資源空閑
• • *lock=TRUE表示資源正被使用

使用TS管理臨界區，要為每個臨界資源設置一個lock

• 初值為FALSE，表示臨界資源空閑
• 進程進入臨界區之前，先用TS測試lock，如果是FALSE，則可以進入，并將TRUE值賦給lock，關閉了臨界資源

---

9.3.3 Swap指令

稱為對換指令，用于交換兩個字的內容

• 為每個臨界資源設置一個全局布爾變量lock，初值FALSE
• 利用上面的硬件指令完成進程互斥
• 但是這種方法也會造成訪問進程不斷進行測試，處于“忙等”狀態，不符合“讓權等待”原則

---

9.4 信號量機制

9.4.1 整型信號量

被定義為一個用于表示資源數目的整型量S，對于這個整型信號量的操作只有三種：初始化(賦初值)、wait(自減)、signal(自增)

• wait和signal均為原子操作，執行時不可中斷
• 當一個進程在修改某信號量時，沒有其他進程可以同時對該信號量進行修改

---

9.4.2 記錄型信號量

不存在“忙等”現象的進程同步機制

• 除了一個用于代表資源數目的整型變量value外
• 還需要增加一個進程鏈表L，用于鏈接所有等待該資源的進程

• wait操作等價于P操作
• signal操作等價于V操作
• 只是兩種不同的稱呼，功能完全一致
• wait(A) = P(A)
• signal(B) = V(A)

---

(1) 利用信號量實現進程互斥

設置一個互斥信號量mutex=1,然后把各進程訪問臨界資源的臨界區放在wait(mutex)和signal(mutex)之間

---

(2) 利用信號量實現進程同步

設置一個同步信號量S=0，讓需要先執行的語句signal(S)，后執行的wait(S)