What are the four conditions for deadlock?

• Mutual exclusion – the resource (lock) can be held by only one thread at a time. This is inherent to locks.
• Hold-and-wait – a thread holds at least one lock while waiting to acquire another. It does not release its current lock.
• No preemption – a lock cannot be forcibly taken from a thread. Only the holding thread can release it voluntarily.
• Circular wait – a chain of threads exists where Thread-1 waits for Thread-2, Thread-2 waits for Thread-3, and Thread-N waits for Thread-1, forming a cycle.
• Breaking conditions – if any one condition is false, the entire conjunction is false and deadlock is impossible. The most practical condition to break is circular wait through lock ordering.

What are the four Coffman conditions?

Edward Coffman identified in 1971 that four conditions must all hold simultaneously for a deadlock to occur. If any single condition is broken, deadlock is impossible.

How do you break mutual exclusion?

Mutual exclusion is inherent to locks: only one thread can hold a lock at a time. You can partially break it with ReadWriteLock (shared reads) or fully break it with lock-free structures.

package com.bank.core;

import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.atomic.AtomicInteger;

public class LockFreeExample {
    // No locks at all: CAS-based thread safety
    private final AtomicInteger transactionCount = new AtomicInteger(0);
    private final ConcurrentHashMap<String, String> cache = new ConcurrentHashMap<>();

    public void recordTransaction(String id) {
        cache.put(id, "PROCESSED");
        transactionCount.incrementAndGet();
    }
}

How do you break hold-and-wait?

Acquire all locks at once, or release the current lock before requesting another. tryLock enables this pattern.

package com.bank.core;

import java.util.concurrent.locks.ReentrantLock;

public class BreakHoldAndWait {
    public boolean transferSafely(ReentrantLock lockA, ReentrantLock lockB) {
        if (lockA.tryLock()) {
            try {
                if (lockB.tryLock()) {
                    try {
                        return true; // got both: perform transfer
                    } finally { lockB.unlock(); }
                }
            } finally { lockA.unlock(); }
        }
        return false; // could not get both: no hold-and-wait
    }
}

How do you break no preemption?

tryLock(timeout) simulates preemption: the thread gives up voluntarily after a deadline.

package com.bank.core;

import java.util.concurrent.TimeUnit;
import java.util.concurrent.locks.ReentrantLock;

public class BreakNoPreemption {
    public boolean acquireWithTimeout(ReentrantLock lock) throws InterruptedException {
        if (!lock.tryLock(5, TimeUnit.SECONDS)) {
            // Could not acquire in 5 seconds: back off voluntarily
            return false;
        }
        return true;
    }
}

How do you break circular wait?

Assign a global order to all locks and require every thread to acquire them in that order.

package com.bank.service;

import java.math.BigDecimal;

public class OrderedTransfer {
    public void transfer(com.bank.model.Account from,
                         com.bank.model.Account to,
                         BigDecimal amount) {
        // Order by account ID: always lock the lower ID first
        com.bank.model.Account first =
            from.getAccountId().compareTo(to.getAccountId()) < 0 ? from : to;
        com.bank.model.Account second = (first == from) ? to : from;

        synchronized (first.getLock()) {
            synchronized (second.getLock()) {
                from.debit(amount);
                to.credit(amount);
            }
        }
    }
}

Which condition is easiest to break?

| Condition | How to break | Difficulty | Common? |
|---|---|---|---|
| Circular wait | Lock ordering | Easy | Yes (most common) |
| Hold-and-wait | tryLock (all-or-none) | Medium | Yes (with retry logic) |
| No preemption | tryLock(timeout) | Medium | Yes (safety net) |
| Mutual exclusion | Lock-free structures | Hard | Sometimes |

Why is breaking one condition enough?

Deadlock requires all four conditions to be true simultaneously. The logical expression is: deadlock = C1 AND C2 AND C3 AND C4. If any condition is false, the entire expression is false. Breaking even one condition makes deadlock impossible.

What should a senior engineer know?

• Lock ordering at scale: in systems with hundreds of lock types, maintain a documented lock hierarchy. If Lock-A is higher in the hierarchy than Lock-B, always acquire A before B.
• Database deadlock prevention: SELECT ... FOR UPDATE ORDER BY primary_key applies the same lock-ordering principle at the database level.
• Formal verification: tools like Java Pathfinder can systematically explore all thread interleavings to prove the absence of deadlocks in critical code.