Deadlock Characterization

Necessary Conditions
• Mutual exclusion: At least one resource must be held in a non-sharable mode
• Hold and wait: a process holding at least one resource is waiting to acquire additional resources held by others
• No preemption: a resource can be released only voluntarily by the process holding it, after it has completed its task
• Circular wait: there exists a set {P0, P1, …, P0} of waiting processes such that P0 is waiting for a resource that is held by P1, P1 is waiting for a resource that is held by P2, …, Pn–1 is waiting for a resource that is held by Pn, and Pn is waiting for a resource that is held by P0.

Deadlock can arise if four conditions hold simultaneously.

Resource-Allocation Graph
• A set of vertices V and a set of edges E.
• V is partitioned into two types:
– P = {P1, P2, …, Pn} (All processes in the system)
– R = {R1, R2, …, Rm} (All resources in the system)
• Two kinds of edges
– Request edge – directed edge P1  Rj
– Assignment edge – directed edge Rj  Pi

continuation..
• Process

• Resource Type with 4 instances

• Pi requests instance of Rj

• Pi is holding an instance of Rj

Example of a Resource Allocation Graph


Resource Allocation Graph With A Cycle But No Deadlock


RAG And Deadlock
• If graph contains no cycles  no deadlock.
• If graph contains a cycle 
– If only one instance per resource type, then deadlock.
– If several instances per resource type, possibility of deadlock.