The four necessary conditions for deadlock

The conditions are often named after Coffman.

Model answer. A deadlock is a set of processes in which each one waits for a resource held by another member of the set, so none can proceed. The four Coffman conditions must all hold at the same time:

1. Mutual exclusion — at least one resource can be used by only one process at a time.

Break it: make resources shareable where possible (read-only files, spooling a printer), though many resources such as locks are inherently exclusive.

1. Hold and wait — a process holds at least one resource while waiting to acquire more.

Break it: require a process to request all resources at once, or release everything it holds before requesting more. This hurts utilization and may cause starvation.

1. No preemption — a resource cannot be forcibly taken away; it is released only voluntarily.

Break it: if a request cannot be satisfied, take back the resources the requester already holds (works for CPU registers or memory, rarely for locks mid-update). trylock with back-off is a software version of this idea.

1. Circular wait — there is a cycle P1 → P2 → … → Pn → P1 where each waits on the next.

Break it: impose a global ordering on resources and always acquire them in increasing order. This is the most practical technique in real code (e.g. always lock account with smaller ID first in a money transfer).

Overall strategies: prevention (break a condition), avoidance (e.g. Banker's algorithm, which grants requests only if the system stays in a safe state), detection and recovery (find cycles in a wait-for graph, then abort or roll back a process), or simply ignoring the problem, which is what most general-purpose operating systems do for application-level locks.

Common mistake: confusing deadlock with starvation. In starvation a process waits indefinitely because others keep getting preference, but the system as a whole still makes progress; in deadlock the involved processes make no progress at all.