deadlock

1. Deadlock: System中存在一些processes互相等待彼此所擁有的resources，即形成circular waiting，造成所有processes皆無法繼續執行(infinite blocking)，使得CPU utilization與system throughput大幅降低。
2. Process使用resources的三個步驟
􀁺 Request: 可透過wait() semaphore實作
􀁺 Use
􀁺 Release: 可透過signal() semaphore實作
3. Deadlock v.s. Starvation
􀁺 Starvation只限於單一(或某些/少數) process因長期拿不到resource而形成自身停滯的現象，但其他processes仍可正常執行；且CPU utilization與system throughput未必會降低。
􀁺 兩者皆為不公平的resource allocation的結果
􀁺 兩者通常在preemptive環境下較顯著
4. 形成deadlock的四個必要條件(缺一不可) (deadlock ⇒ 4 conditions)
􀁺 Mutual Exclusion: 至少有一個resource是non-sharable的狀態
􀁺 Hold and Wait: 某個process必定hold住部份的resources、且等待其他processes所hold住的resources
􀁺 No Preemption: 某些resources是non-preemptible；processes不能搶奪其他processes的resources，必須等到其他processes自動release這些resources，才能使用這些resources。
􀁺 Circular Wait: 存在一組processes {P0, P1, ..., Pn}，其中P0在等P1、P1在等P2、…、Pn在等P0。
􀁺 “Circular Wait” implies “Hold and Wait”.
5. Resource Allocation Graph, G = (V, E)
􀁺 Vertex set V = {process P, resource types R}
􀁺 Edge set E = {request edge (Pi → Rj), assignment edge (Ri → Pj)}
􀁺 Graph中，若沒有存在cycle，則不會產生deadlock。
􀁺 Graph中有cycle，未必造成deadlock
􀂕 每個resource type為multiple instances，則未必有deadlock
􀂕 每個reosource type皆是signle instance，則cycle ⇔ deadlock1