---
# System prepended metadata

title: 死結 Deadlock

---

# 死結 Deadlock
一群task，彼此等待。

當印表機已經分配給行程P2了，等待磁碟機接受要求才能繼續，但此時磁碟機已分配給行程P1，P1必須等待印表機接受要求才能繼續。P2在等待P1佔有的磁碟機，P1在等待P2佔有的印表機，這樣互相等待的狀態為死結。
![](https://i.imgur.com/sQiUwKT.png)

## 死結特性
死結構成的必要條件
1. 至少有一項資源是不可分享且互斥的
2. 一個行程必定已持有至少一項資源，且還在等待另一些被其他行程持有的資源，產生持有和等待的現象>
3. 已被分配的資源無法被強行搶走
4. 行程循環式等待

圖一
此圖沒有產生迴圈(因為P2可以出迴圈到R3)

圖二
此圖有產生迴圈(P2->R3->P3->R2->P2)


![](https://i.imgur.com/uALoi1C.png)

## 死結防止
使必要條件至少有一項不會發生
### 互斥
一般無法改變互斥條件來防止死結，因為有些資訊先天就是不可分享的，像是印表機。
### 持有和等待
1. 不可分次要求
2. 持有後若要要求資源必須先釋放已持有的資源
缺點:資源使用率很低&產生飢餓的情況
很可能一個行程所需的資源之一總是分配給其他行程，導致持續等待
### 不可搶奪No preemption
1. 持有後若要要求資源，那它所有的資源必須全部被搶奪
2. 行程要求的時候系統會檢查此資源是否可用
基本上只適用在CPU和記憶體資源，不適合應用在印表機或磁碟機等資源。此方法也有可能會造成某個行程飢餓
### 循環式等待
1. 將所有資源強迫排序，行程要求資源的時候必須照順序來要求
## 死結避免
![](https://i.imgur.com/ztNWnmc.png)

## 死結偵測

