###### tags:`Notes`
# DeadLock

## 起因
如果系統中只有一個行程，當然不會產生死結。如果每個行程僅需求一種系統資源，也不會產生死結。不過這只是理想狀態，在現實中是可遇不可求的。
## 範例
假設兩人正好面對面碰上對方：

死結：兩人互不相讓，都在等對方先讓開。
活結：兩人互相禮讓，卻恰巧站到同一側，再次讓開，又站到同一側，同樣的情況不斷重複下去導致雙方都無法通過。

## 死結的四個條件：

死結只有在四個條件同時滿足時發生，預防死結必須至少破壞其中一項。
### 互斥（mutual exclusion）
資源只能同時分配給一個行程，無法多個行程共享。
### 持有和等待（hold and wait）
一個行程可以在等待時持有系統資源。
### 禁止搶占（no preemption）
系統資源不能被強制從一個行程中退出。
### 循環等待（circular waiting）
一系列行程互相持有其他行程所需要的資源。

## 死結的三個解法
### 預防
提供一組方法去確認==至少一個==必要的死結情況不會發生。這些方法靠著限制資源的需求來達成預防死結。
1. Mutual exclusion:
對不可共用的資源類型而言，互斥一定成立，而可共用的資源類型，因為可以同時讀取相同檔案，所以一定不會產生。
3. Hold and Wait:
process必須保證一個行程在要求一項資源時，不可以佔用任何其它的資源。
5. No preemption:
只要某個處理元要不到所要求的資源時，便把它已經擁有的資源釋放，然後再重新要求所要資源。
7. Circular Wait:
確保循環式等候的條件不成立，我們對所有的資源型式強迫安排一個線性的順序。

### 避免
要求作業系統給出額外的資訊，關於一個程序(process)在他的 生命期限(lifetime)裡會要求的資源(resource)。有了這些額外的資訊，作業系統可以決定是否 讓程序的要求繼續等候。為了決定現在的要求是否能滿足，作業系統必須考慮現在資源的存量、 資源的分配量、和未來資源的要求與釋放。

假設我們知道

1. 系統目前可用的資源數量(Available)
2. 各process對資源的最大需求量(max)
3. 各process目前持有的資源量(allocation)

- 各系統還需多少資源(need) = max - allocation

Safety演算法:
Resource_Allocation_Graph演算法結論:
Banker's演算法:

### 任其發生
系統可以提供一個演算法進入一個狀態來判斷死結是否產生，並且加以恢復。

**偵測**
Deadlock detection algorithm

**恢復**

一旦檢測出死結，則就要採取一些策略使系統從死結中恢復，常有以下方法來從死結中恢復:
- 結束所有死結進程。即強制性地從系統中撤銷死結進程，並剝奪它們的資源給剩下的進程使用。（使前面的工作全部損失）

- 將死結進程退回到前一個檢查點，並重新從該檢查點啓動這些進程（前提是系統必須提供檢

查點和重新啓動的機制）。

- 相繼的逐個結束死結進程直至死結不再存在。在每個進程結束後，都要使用死結檢測算法以

確定死結是否依然存在。

- 相繼的逐個搶佔死結進程的資源，直至死結不再存在。但搶佔資源的方法是否可行，往往與資源特性有關。有時搶佔資源還需要人工干預，例如搶佔激光印表機時就需將原來影印的紙張先放到一邊去，並使被搶佔進程回到當初獲得資源時的斷點。

由於所有使死結進程相繼結束和強佔資源策略均涉及損失了這些進程已完成工作的開銷。因此要基於成本的基礎上選擇結束進程的次序。首先要優先選擇以下死結進程：
1. 選擇使用最少處理器時間的進程。
2. 選擇使用最少輸出工作量的進程。
3. 選擇具有最多剩餘時間的進程。
4. 選擇分的最少資源進程。
5. 具有最小優先級的進程。