Deadlock Characterization

<aside> 📖 程式之間彼此等待，無法進行了

</aside>

• Example

Necessary Condition → 一定要全部的條件同時發生

• Mutual exclusion — 資源是沒有共享性的（暫時）

• Hold and Wait — 會 hold resource 然後 wait 別人

• No preemptive — 不能強制別人放開 resource

• Circular wait — 一定會有一個 circular 的 wait。

  $P_0 \rightarrow P_1 \rightarrow P_1 \rightarrow \dots\rightarrow P_n \rightarrow P_0$

System Model

• 要有某些資源 $R_1, R_2, \dots, R_m$

  • E.g. CPU, memory pages, I/O devices

• 每個資源 $R_i$ 可能會有複數的共 $W_i$ 個 instances

  • E.g. a computer has 2 CPUs

• 每一個 process 取得 resource 的方式：

  Request → use → release

Resource-Allocation Graph

圓形跟正方形不能改

• 3 processes, P1 ~ P3
• 4 resources, R1 ~ R4
  • R1 and R3 each has one instance
  • R2 has two instances
  • R4 has three instances
• Request edges:
  • P1 → R1: P1 requests R1 （一直存在因為 resource 正在被用）