[OS] Deadlock

7.1

• Deadlock: 由於 Process 正在 Block 等待資源， 但資源也被另外一個 Block 的 Process 佔用。
• 所有需要 Process 等待 Event，但沒有 Process 可以發出 Event 導致所有 Process 餓死。
• 兩個以上的 Process (或 Thread) 有可能發生 Deadlock
• 透過**資源配置圖(Resource Allocation Graph)**檢查 Process 與 資源的相依關係，並且為有向圖。

Deadlock 產生的條件

1. Mutual Exclusion
2. Hold and Wait: Process 已擁有獨占資源， 並且等待其他 Process 的獨占資源。
3. Non-Preemtion: 其他 Process 不能搶奪被佔有的資源
4. Circuler Wait: 循環等待鍊

繪畫出資源配置圖，以便檢查是否有循環圈存在，並且循環圈資源內的資源不足才有可能形成死結。

參見WillyWangkaa: Operating System - Deadlock

解決 Deadlock

• 預防 Deadlock: 系統使用協議並免死結
• 偵測 Deadlock: 偵測到死結產生後，對死結進行復原

7.2 預防 Deadlock

使 Deadlock 的四個條件不成立。

1. Mutual Exclusion:
   • 讓資源共用
   • 不可行: 因為有些資源是無法共用的，必須維持互斥性
2. Hold and Wait:
   • Process 必須獲得所有資源才能運算
   • 可行低效: 要不到資源先釋放自身所有資源，效率低落
   • 可能導致 Stravation
3. Non-Preemtion: 不可行
   • 釋放自身資源: 低效
   • 奪取資源:
     • 如印表機等專屬設備是不可奪取的資源
     • 共用設備則可以奪取，如 CPU 、 RAM.. 等可奪取的資源 ** (Premptible Resource) **
   • 可能導致 Stravation
4. Circuler Wait: 可能但實務不可行
   • 必須依資源編號順序請求資源
   • 資源編號都是唯一的
   • 反證法: 循環圈產生之後， 最小編號的資源不可能小於自己的編號因此產生矛盾。 因此循環等待是不可能產生的。
   • 難以對資源編號

7.3 避免 Deadlock

透過資源配置圖檢查是否處於 Deadlock 或 Safe State 或 Unsafe State。

• Safe State: 系統透過一些次序分配資源給每 Process ，能夠 避免 Deadlock
• Unsafe State: 不一定有 Deadlock ， 但是 Deadlock 一定發生在 Unsafe State

分配資源時，盡可能給予最少需求的 Process ，以便這些 Process 能夠釋放更多資源，保持在 Safe State。

配置圖與配置狀態

• Resource Allocation Graph: 使用一個資源，判斷分配資源後是否會產生迴圈，會則不分配。
• Resource Allocation State: 紀錄使用多個資源，以保持 Safe State

Banker’s algorithm

系統有 n 個 Process 與 m 種資料

• Allocation: 目前 Process 以使用的資源，m * n 個元素
• Max: 最多需要多少資源
• Need: 還需要多少資源 Max - Allocation = Need
• Available: 系統還有多少可用資源，m 個元素

資源請求演算法

1. 檢查請求是否合理，比方說需要的資源小於請求的資源。
2. 計算請求的資源是否在可用的範圍
3. 計算資源配置狀態

安全演算法

1. 讓 Work 與 Finish 向量長度各為 m 與 n，並初始化
2. while (找到一個未完成，並且可以完全提供的)
   • 取回資源
3. finish 所有代表系統安全。

Deadlock Detection

• 允許 Deadlock 出現，透過演算法偵測並且消除。
• 作業系統必須有解 Deadlock 的方法，透過選擇犧牲者進行回復
• 如果 Abort 一個不行，多 Abort 幾個
• Abort 之後必須 Rollback ，並且回到開始執行前的狀態

偵測方法

• 資源單個: 循環圖，循環圈
• 數個資源: Banker’s algorithm

演算法

與 Safe Algorithm 的差異

1. 第一步驟如果 Aloocation != 0 的時候， Finish 會被設定為 false，否則設為 true
2. 第二步驟差異，在於檢查請求而非所需的資源數量
3. 第三步驟相同
4. Finish[i] == false 代表 Thread_i 發生 Deadlock

偵測時機

• 無法立即得到資源
• 排程時間
• CPU 使用率降低

Recovery

為一種不預期的結束，並且回復所作的行為

處理的部份為 Transaction Failure， 其他如 System failure, Media failure.

Transaction Log

用於解決 Transaction Failure，並且把過程紀錄到 Transaction Log 當中

• Commit: 代表 Transaction 成功結束
• Abort: 代表不成功結束，並且進行Rollback，還原操作

紀錄檔需求

關於 Write, Ahead, Logging 等行為的資訊， 其資訊可以用來檢查哪些資料需要回溯。

• Command
• Before Image
• After Image

檢查 Transaction 是否正常結束，如果沒有正常結束(缺乏 Commit)， 就必須 Rollback。

Redo and Undo

• Undo: start whitout commit
• Redo: start with commit，用於確保資料有成功寫入

Checkpoint

節省 Transaction Log 所花費的時間，固定時間排程檢查點， 並且在 Crash 之後回到 Check Point 即可。

1. 輸出 log Records 寫入 Stable Storage
2. 將 Modified 寫入 Stable Storage
3. 輸出 Checkpoint 到 Stable Storage 代表已記憶體內容寫入。

如果次序錯誤，比方說先做第二步，在做第一步驟，可能會導致已修改但是沒有紀錄的情形發生。

Time Stamp

適用於分散式系統，網路延遲可能導致問題。

• W-timestamp: 資料最後被寫入的時間
• R-timestamp: 最後被讀取的時間

何時 Rollback

• 讀取時: 如果發出請求的時間之後(含)被寫入就做 Rollback
• 寫入時: 如果發出請求的時間之後(含)被寫入或讀取就做 Rollback，

特性

• Serializable
• No Deadlock

---

Operating System