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
沒有留言:
張貼留言