# Operating System #7

## The Deadlock Problem

* 其實前面已經提過，所謂的死結就是一群processes以循環的方式等候彼此的資源。
* 一個簡單的例子：
* 
---
* 死結出現必須有以下四個條件同時符合：
1. Mutual exclusion
* 一次一個process執行。
2. Hold and wait
* process必須至少擁有一個資源，且正等候另一個資源。
3. No preemption
* 要得到資源時必須等候該資源的擁有者結束，不可強制取得並執行。
4. Circular wait
* 環狀結構的等待。

## Resource-Allocation Graph

* 圓形代表process，方框裡面的點代表資源。
* 
* 圓形指向方框代表正在要求資源，方框指向圓形代表process正在占用該資源。
* 基礎概念：
* 沒有環狀出現：一定沒有死結。
* 有環狀出現：可能有可能沒有。

## Methods for Handling Deadlocks

* 確保系統不會有死結出現，通常有兩種方法：
* Prevention: 確保上面說過的四種條件其中一種不會發生。
* Avoidance: OS透過各種資訊去判斷該請求是否造成死結，進而決定是否執行或是要延後。
* 其他方案：
* 允許系統進入死結，但是可以修正該狀態。
* 無視該問題，將死結的發生視為程式設計師的問題。EX: UNIX。

## Deadlock Avoidance

* 藉由processes給予的資訊去判斷狀態是否會進入unsafe，如果請求的process會進入unsafe就拒絕掉。
* unsafe不代表一定會發生死結，只是有可能。
* 
* 題目正常會給予**總資源數量**、**每個process的需求**和**每個process目前擁有的資源**，要求你判斷現在是否會發生死結。
* 以下範例，總資源為`12`：

|| Max needs | Current holding | Will need |
|---| -------- | -------- | -------- |
|A| 10 | 5 | 5 |
|B| 4 | 2 | 2 |
|C| 9 | 2 | 7 |

* 只要用B,A,C就不會產生死結。(正常只要由需求最少一路往上推即可)

## Banker’s Algorithm

* 上面那種問題的延伸，在資源也有多個的情況下的演算法。
* 演算法寫個很複雜，其實步驟就是：
1. Loop檢查每個未執行的process是否擁有資源執行
2. 如果有，執行process，回收它的資源，回到第一步
3. Loop結束，如果都執行完畢就沒有死結，反之亦然。

## Deadlock Detection

* 如果一個系統既沒有Deadlock Prevention也沒有Deadlock Avoidance，那它就需要：
* deadlock detection algorithm去檢查系統狀態是否發生死結。
* 使用Deadlock Avoidance的方法去偵測。
* recovery algorithm去修復它。
* 中斷process或是資源搶占

###### tags: `note`