Deadlock

Deadlock and resource model

Definition. A deadlock is a state in which a set of processes is permanently blocked because each waits for an event that only another process in the set can cause. Resources may have one or multiple instances; a process requests, uses, and releases them.

Example. P1 holds printer A and requests scanner B while P2 holds B and requests A.

Exam point. A blocked process alone is not enough; the waiting dependency must form a cycle or equivalent circular dependency.

Solved examples

Example 1 — dependency cycle. P1 holds R1 and requests R2; P2 holds R2 and requests R1.

1. P1 cannot proceed until R2 is released by P2.
2. P2 cannot proceed until R1 is released by P1.
3. Neither can release its held resource before proceeding.
4. The two-process wait cycle is deadlocked.

Example 2 — no cycle. P1 holds R1 and waits for R2; P2 holds R2 but is not waiting and will release it.

1. P1 is blocked temporarily.
2. P2 can execute and release R2.
3. P1 can then proceed.
4. This is not a deadlock.

Four necessary conditions

Definition. Deadlock requires all four Coffman conditions: mutual exclusion, hold-and-wait, no preemption, and circular wait. Breaking any one condition prevents deadlock under the modeled resource assumptions.

Condition	Meaning	Possible strategy to break it
Mutual exclusion	resource has nonshareable use	make resource shareable where feasible
Hold-and-wait	hold resources while requesting more	request all at once or release before request
No preemption	resources cannot be forcibly taken	preempt eligible resources
Circular wait	cyclic chain of requests	impose a global resource order

Example. Requiring processes to request resources in increasing order prevents a cycle in that order.

Exam point. These are necessary conditions, not a sufficient test for every system state.

Solved examples

Example 1 — find the broken condition. System requires a process to request its complete resource set before it starts.

1. The process cannot hold a partial set and later request more.
2. Hold-and-wait is prevented.
3. Deadlock is prevented through that condition, though utilization may fall.

Example 2 — ordered resources. Resources are ordered R1<R2<R3; all requests must follow increasing order.

1. A cycle would require requests eventually to move back to a lower-ranked resource.
2. Every edge in a wait cycle would have to increase rank strictly.
3. A finite cycle cannot strictly increase and return to its start.
4. Circular wait is impossible.

Resource-allocation graphs

Definition. In a resource-allocation graph, process nodes and resource nodes are connected by request edges P→R and assignment edges R→P. With one instance per resource type, a cycle is equivalent to deadlock. With multiple instances, a cycle is necessary but not sufficient.

Example. P1→R2 and R1→P1 show P1 waits for R2 while holding R1.

Exam point. Read edge direction carefully: request points from process to resource; assignment points from resource to process.

Solved examples

Example 1 — single-instance cycle. Edges R1→P1, P1→R2, R2→P2, P2→R1.

1. P1 holds R1 and requests R2.
2. P2 holds R2 and requests R1.
3. The graph contains a cycle through both processes and resources.
4. With one instance of each resource, the cycle implies deadlock.

Example 2 — multiple instances caution. Resource R has two identical instances; P1 requests R, P2 holds one instance but is not blocked and will release it.

1. A graph cycle may include requests and assignments involving R.
2. The second instance or a releasable instance can satisfy a request.
3. A cycle alone does not prove all processes are stuck.
4. For multiple instances, use a safety or detection algorithm.

Deadlock prevention

Definition. Prevention designs the system so at least one necessary condition never holds. Methods include spooling/shareability, all-at-once requests, preemption, and total resource ordering. Prevention can reduce concurrency or cause resource underuse.

Example. A strict order on locks prevents threads from acquiring them in opposite orders.

Exam point. Prevention is a policy constraint; it does not inspect each request for future safety.

Solved examples

Example 1 — all-at-once request. P needs R1 and R2 for a task but requests R1 first, then waits for R2. Under prevention it must request both together.

1. If both are available, grant both atomically.
2. Otherwise grant neither and let P wait without holding one.
3. Hold-and-wait is removed.

Example 2 — preemption limitation. CPU register state can be saved, but a partially written tape operation cannot safely be interrupted.

1. CPU allocation is generally preemptable.
2. A nonrestartable I/O operation may not be safely preemptable.
3. Prevention by preemption applies only to resources whose state can be safely restored or restarted.

Deadlock avoidance and safe states

Definition. Avoidance examines each request and grants it only if the resulting state is safe. A state is safe if there exists an order in which each process can obtain its remaining maximum need from currently available resources plus resources released by earlier completed processes. Unsafe does not mean currently deadlocked.

Example. A request may be postponed even when resources are free if granting it removes every safe completion sequence.

Exam point. Need=Max−Allocation; Available is total free resources, not total system resources.

Banker's safety algorithm

Definition. For n processes and m resource types, set Work=Available, Finish[i]=false. Repeatedly find an unfinished i with Need[i]≤Work, then set Work=Work+Allocation[i] and Finish[i]=true. If all finish, the state is safe; otherwise it is unsafe.