Deadlock Conditions (Coffman Conditions)

A deadlock can occur only when four conditions hold at the same time: mutual exclusion, hold and wait, no preemption, and circular wait. Breaking any one of these conditions prevents that form of deadlock.

Mutual exclusion means a resource can be held by only one thread at a time. For example, a lock protects a shared data structure so that only its owner can enter the protected section.

Hold and wait means a thread already holding at least one resource is waiting to acquire another resource. In Java, this can happen when a thread owns one monitor while trying to enter a second synchronized block.

No preemption means a resource cannot simply be taken away from the thread holding it; the holder must release it voluntarily. Java monitor locks generally follow this property: another thread cannot forcibly remove a monitor lock from its owner.

Circular wait means there is a cycle of threads waiting for resources held by one another. For example, thread A holds lock 1 and waits for lock 2, while thread B holds lock 2 and waits for lock 1. Because all four conditions occur together, neither thread can make progress.

Key points

• All four Coffman conditions must exist simultaneously for deadlock.
• Mutual exclusion makes some resources exclusive to one thread.
• Hold and wait means a thread keeps resources while requesting more.
• No preemption means resources cannot be forcibly reclaimed from their holders.
• Circular wait creates the cycle that prevents the waiting threads from progressing.

Interview questions

What are the four Coffman conditions for deadlock?

The four conditions are mutual exclusion, hold and wait, no preemption, and circular wait. Mutual exclusion means a resource can have only one owner at a time. Hold and wait means a thread keeps resources while requesting additional ones. No preemption means a held resource cannot be forcibly taken away, and circular wait means the waiting relationships form a cycle.

Can you give a Java example of deadlock?

A common example uses two locks and two threads. Thread A acquires lock A and then waits for lock B, while thread B acquires lock B and then waits for lock A. If the timing allows both first acquisitions to happen, each thread waits for the other indefinitely. This demonstrates hold and wait, no preemption, and circular wait in addition to exclusive locking.

How would you prevent deadlock in a Java application?

A common strategy is to impose a global ordering on locks and always acquire them in that order. This prevents circular wait because dependencies cannot form an inconsistent cycle. Other approaches include reducing lock scope, avoiding unnecessary nested locking, and using APIs such as `tryLock` with timeouts where appropriate. The exact strategy depends on the resources and consistency requirements of the application.

Why are all four Coffman conditions described as necessary rather than sufficient individually?

Each condition is required for the classic deadlock model, but any single condition by itself does not imply deadlock. For example, mutual exclusion can exist in a perfectly healthy concurrent program. A deadlock requires the complete combination, including a circular dependency among threads and resources. Therefore, preventing any one condition is sufficient to prevent that class of deadlock.