# OS筆記-Chapter 6: Process Synchronization

###### tags: `OS`
---
#### 目錄
* 總論
[Chapter 1: Introduction](https://hackmd.io/NoZq3J7IQvOQpcbo_tctjA)
[Chapter 2: Operating-System Structures](https://hackmd.io/OKykRLBESI6v9a13HgS35A)
* 行程管理
[Chapter 3: Processes](https://hackmd.io/HOqN-iQ3RIKIC-NB9QjBIQ)
[Chapter 4: Threads](https://hackmd.io/qzAIHeSASmKuecdkqidmHw)
[Chapter 5: CPU Scheduling](https://hackmd.io/IT5g2wHzTdOtMSDXPVEpOw)
<font color="red">Chapter 6: Process Synchronization</font>
[Chapter 7: Deadlocks](https://hackmd.io/Uu0jDK-rSyKNKq690y146g)
* 記憶體管理
[Chapter 8: Main Memory](https://hackmd.io/4KS_yPkBQzGZfHDisPciog)
[Chapter 9: Virtual Memory](https://hackmd.io/yirxZFn8Rz2wT56AAR7Sxw)
* 儲存裝置
[Chapter 10: File-System Interface](https://hackmd.io/aNPWKsFhTlGc-WFgQ__KRg)
[Chapter 11: File System Implementation](https://hackmd.io/bFcrlmefQsGp6hZdbI1MHQ)
[Chapter 12: Mass-Storage Systems](https://hackmd.io/9Y7Qo0OERda6htK7OOI36Q)
[Chapter 13: I/O Systems](https://hackmd.io/VNwXrhJPSo-l_t9tUBhYIg)
* 保護和安全
[Chapter 14: Protection](https://hackmd.io/izkd4JwXRwub_ZmhSMTlNw)
[Chapter 15: Security](https://hackmd.io/ofyvDidvQf-PxLMMZYhtsg)
---

### 背景
* 競爭情況(race condition):多個行程並行處理資料
* counter++:
* counter--:
* 並行:
* 得到不正確的狀態，因次序不同得到counter=4或6

* 需要行程同步(Process Synchronization)和協調(coordination)

### 臨界區間問題(Critical Section Problem)
* 臨界區間:
* n個行程中每一個含有的一段程式碼
* 這段程式中，行程可改變共同的資料
* 當一個行程在臨界區間內執行，不允許其他行程在臨界區間內執行

* 解決臨界區間問題
* 互斥(Mutual Exclusion):當一個行程在臨界區間內執行，不允許其他行程在臨界區間內執行
* 進行(Progress):如果沒有行程在臨界區間內執行，然後有其他行程要求進入其臨界區間，不能無限期地延遲接下來將進入臨界區間的行程的選擇
* 限制性等待(Bounded Waiting):當一個行程已經要求進入其臨界區間，但尚未被答應之前，允許其他行程進入其臨界區間有次數限制

* 假設n個行程執行速度不為零
* 無法假定n個行程的相對速度(relative speed)

* 可搶先核心(preemptive kernel)
* 對稱多處理(SMP,Symmetric multiprocessing)結構設計困難
* 更容易回應
* 對即時程式設計是更適當的

* 不可搶先核心(nonpreemptive kernel)
* 可免於核心資料結構上的競爭情況

### Peterson Solution
* turn:表示輪到誰進入臨界區間
* flag:表示一個行程是否就緒來進入它的臨界區間，例如flag[i]，表示Pᵢ是否就緒

### 同步之硬體(Synchronization Hardware)
* 使用鎖(lcok)保護臨界區間

* 單一處理器:
* 共用變數更改時，不讓中斷發生
* 不可搶先
* 解決臨界區間問題

* 多處理器:
* 不讓中斷發生費時，必須將這項訊息傳給每一個處理器
* 單元(atomically):在不可中斷的單元內，測試修改
* test_and_lock:
* 指令定義:
* 製作互斥:
* compare_and_swap:
* 指令定義:
* 製作互斥:
* 滿足互斥和限制性等待:

### 互斥鎖(Mutex Locks)
* mutex = mutual exclusion

* 使用互斥鎖保護臨界區間
* 進入臨界區間:取得鎖，acquire()
* 離開臨界區間:釋放鎖，release()

* 忙碌等待(busy waiting):
* 任何試圖進入臨界區間的其他行程必須在呼叫acquire()的地方不斷地執行
* 這種型態的互斥鎖被稱為自旋鎖(spinlock)
* 不須內容轉換

### 號誌(semaphore)
* S為號誌的值，同時只能有一個行程修改此值

* 技術號誌(Counting semaphore):不受限制
* 二元號誌(Binary semaphore):0或1

* 號誌被設定為可用資源數字的初值

* 為了解決這種忙碌等待的需要
* 使等待的行程放入等候佇列
* block():暫停呼叫它的行程
* wakeup(P):回復被閉鎖行程P的執行

* 如果號誌的值為負的，其大小則為等待此號誌的行程數目

* 死結(deadlocked)
* 兩個或以上的行程一直等待一項僅能有由等待行程鎖引發事件的情形
* S=1、Q=1

* 無限期阻滯(– indefinite blocking)/飢餓(Starvation)
* 可能產生在號誌間作無限期等待的情況

* 優先權倒置(Priority Inversion)
* A、B、C三個行程，優先權A<B<C，C要求A存取的資料，但B行程變成可執行，導致B搶先A，因此C行程受到較低優先權的行程影響
* 優先權繼承協定(priority-inheritance protocol):
* 所有要存取資源的行程，必須繼承行程區中較高優先權，直到資源被使用完成
* A繼承C的優先權，才能阻止B搶先

### 典型的同步問題
* 有限緩衝區問題(Bounded-Buffer Problem)
* n個緩衝區，每個可保存一項
* 生產者:
* 消費者:

* 讀取者-寫入者問題(Readers-Writers Problem)
* 讀取者:讀取資料的行程
* 寫入者:更新資料的行程
* 同時讀取與寫入資料將會導致紛亂
* 要求寫入者在對共用資料寫入時有獨一無二的存取權(寫入者需等待其他寫入者結束)
* 讀取者不需等待其他讀取者結束
* 寫入者或讀取者都可能飢餓
* 寫入者:
* 讀取者:
* mutex:用來確保變數read_count改變時的互斥
* re_mutex:用來確保寫入與讀取的互斥

* 哲學家進餐問題(Dining-Philosophers Problem)
* 拿取一支筷子視為wait()，放下筷子視為signal()
* 當5位哲學家同時拿起他左邊的筷子時，將產生死結
* 解決方法:
* 至多允許4個哲學家
* 只有左右筷子皆可用時，才能拿起
* 奇數位置的哲學家先拿左手，偶數位置先拿右手
* 免於死結的方法，並不能免於飢餓

### 監督程式(Monitors)
* 一種抽象資料型態(ADT,abstract data type)，且監督程式內設有互斥

* 可以確保只有一個行程在監督程式內活動

* 可定義一個或多個條件變數
* condition x,y
* x.wait():等待，直到x.singal()
* 例如:行程P執行x.singal()，而暫停行程Q與x相關則
* 訊號和等候(Signal and wait):P等候Q，直到Q離開監督程式
* 訊號和繼續(Signal and continue):Q等候P，直到P離開監督程式

* 使用監督程式解決哲學家進餐問題
* 監督程式DiningPhilosophers控制筷子分配
* 當左右兩邊都不進餐，狀態才能為EATING

* 使用號誌製作監督程式
* 號誌mutex用來確保每一個行程的互斥
* 對每一個條件x而言，我們引用一個號誌x_sem
* x.wait():
* x.singal():

* 監督程式內的恢復行程
* 如果有多個行程在等候條件x，當x.singal運作執行時，哪一行程先被恢復
* 先到先服務
* 條件式等待(conditional-wait):
* x.wait(c)
* c的數值稱為優先級數(priority number)
* 優先級數最小的等候行程會被恢復
* 監督程式不能保證，存取的順序一定能被遵守，可能發生:
* 一個行程在沒有先取得某項資源的存取允許權就先使用該資源
* 一個行程獲取某資源存取權後，佔住不放
* 一個行程試圖釋放一項未取得的資源
* 一個行程對兩個相同的資源提出要求
* 為了確保每一個行程都能遵守正確的執行順序
* 使用者行程必須時時依照正確的順序來呼叫監督程式
* 不合作的行程，不會直接忽略監督程式提供的互斥控制

### 替代方法
* 交易記憶體(transactional memory):是一連串不可分割的記憶體讀取和寫入操作，如果一個交易中所有交易都被完成，則記憶體被交付，否則操作被終止並撤回
* 假設函數update():
* 加入交易記憶體的特性後:
* 不可能有死結

* 軟體交易記憶體(STM,software transactional memory):
* 完全使用軟體實作

* 硬體交易記憶體(HTM,hardware transactional memory)
* 不需要特殊的程式碼
* 要求現存的快取架構與快取一致性協定被修改

* 命令式(imperative)/程序(procedure)程式語言
* C、C++、JAVA、C#
* 被用來製作以狀態為基礎的演算法

* 功能性(functional)程式語言
* 不必維護狀態