6.1
非同步並行 Process
- 共用資源
- 必須滿足互斥性
Race Condition
Process Concurrent 導致共用資源不正常的問題
循序執行
處理元依序執行為循序執行，並且有 n! 個循序次序
可循序化
Process 不是循序執行，由 CPU Scheduler 排程次序， 執行結果相同代表可循序化。
互斥
Process 使用資源時，其他 Process 不能同時使用該資源
臨界區間
Process 存取共用資源的程式碼
交易
最細小不可分割的單位，由一到數個指令組成邏輯功能
6.2
臨界區間要求
- Mutual Exclusion: 同一時間僅一個 Process 存取資源
- Progress: 公平原則，當 Process 進入並離開 Critical Section 時， 當前 Process 指向 Remainder code ，重新回到 Enter Statment 時， 相較之下尚未執行 Remainder code 的 Process 優先進入 Critical Section。 若其他 Process 不進入 C.S. 不會導致其他 Process 無法進入 C.S.
- Bounded Waiting: n 個 Process 最多等待 n - 1 次
方法
- 禁止中斷法: 多處理器下不可行，不滿足 Progress, Bounded Waiting
- 必須考量非同步並行的問題
- Peterson’s solution: 保證 M.E., Progress, B.W. ，任意位置 Context Switch 不影響運行，只能處理兩個 Process。
- Bakery: 滿足 M.E., Progress, B.W. ，不被 Context Switch 影響， 抽取號碼牌可能有相同的值，編號唯一使同時單一 Process， Progress 為 Totally Order， B.W. 也因此為 FCFS 因此進入 C.S. 次數有限。
6.3 硬體解決方法
透過硬體實現細小運算以免運算次序出錯。
test-and-set()與swap()都能解決互斥，但不滿足 Progress 與 B.W.- 採用 lock ，使只能單一 Process 運行，Progress 透過運行的 Process 解除等待， 使其他等待的 Process 進行，B.W. 由於循環並依序執行 Process ，因此最多只需要 n - 1 次等待。
6.4, 6.5 Semaphores
- Binary Semaphore: 0, 1, 負值
- Counting Semaphore: 任意正負
- 透過不可中斷的細小運算
P與V - 保護變數
S僅可被P與V同步 - Busy waiting: 為 Spin Lock CPU 不斷測試 S 是否符合條件
- Block/Wakeup: 透過佇列處理，符合三個要求，S 負數代表等待的 Process 數量。
實做
- 最細小運算不可 Context Switch
- 硬體實現最細小運算
- 軟體需要透過 M.E., Progress, B.W. 三者符合的演算法
問題與實用
- Time Dependent Error: 編寫誤用或 Deadlock 導致 Starvation
- 同步: 可以透過 Semaphore 進行 IPC ，同步兩 Process 的執行順序
- Producer-Consumer: 解決緩衝區共用，透過 Semaphore 紀錄數量
- 讀寫問題
- Dining Philosophers:
- Deadlock
- 奇左後右，偶右後左
- 同時取左右
- 單個放棄
- Starvation
- Wait queue
- 動態優先級
- 超時優先
- Deadlock 導致 Starvation
- Deadlock 導致 Starvation, 解決不一定能避免 Starvation
- Deadlock
6.6 Critical Region / Monitor
語言文法定義 Critical Region / Monitor 解決時間相依錯誤的問題。
- 宣告於 Monitor 的變數、 Procedure 管理同步。
- 透過 Queue 提供 Block, Waiting
- Monitor 保證 M.E.
- 透過 Monitor 管理與執行資料控制。
比較
- Critical Region 比 Semaphores 保護程式碼可讀性來的高
- Critical Region 比起 Monitor ， Monitor 可用範圍更大
- Critical Section 代表處理共用資源的程式碼，Critical Section 為程式語言文法， 代表需要被保護的範圍。
6.7
- Locking Protocol:
- SLock: Shared Read
- XLock: Exclusive Write
- Two Phase Locking: 兩個步驟，個別只能 Lock 或只能 Unlock
- Growing phase: 只能 Lock 不可 Unlock
- Shrinking phase: 只能 Unlock 不可 Lock
- 保證 Conflict Serializable, 不保證 Deadlock 不發生
- Time stamp則可以保證 C.S. 與無 Deadlock
Operating System