Race Conditions and Deadlocks in Java

Race conditions

A race condition exists when the correctness of a program depends on the relative timing of threads. The same code can produce the right answer a thousand times and the wrong one on the next run.

Read modify write

private int count = 0;

public void increment() {
    count++;          // read, add, write: another thread can interleave
}

Check then act

// Both threads can pass the check before either acts
if (!users.containsKey(email)) {
    users.put(email, new User(email));
}

// Atomic alternatives
users.putIfAbsent(email, new User(email));
users.computeIfAbsent(email, User::new);

Lazy initialisation

private Connection connection;

public Connection get() {
    if (connection == null) {          // two threads can both see null
        connection = open();            // and both open a connection
    }
    return connection;
}

// A static holder is initialised once by the JVM, with no locking in your code
private static class Holder {
    static final Connection INSTANCE = open();
}

public Connection get() {
    return Holder.INSTANCE;
}

A thread safe collection does not make a sequence of calls thread safe. containsKey followed by put is two atomic operations with a gap between them, and the gap is where the bug lives.

Deadlock

A deadlock occurs when two or more threads each hold a lock the other needs, so none can proceed.

public class Account {

    private final Object lock = new Object();
    private long balance;

    public void transferTo(Account target, long amount) {
        synchronized (lock) {              // holds its own lock
            synchronized (target.lock) {   // wants the other one
                this.balance -= amount;
                target.balance += amount;
            }
        }
    }
}

Thread 1: a.transferTo(b, 100)   holds a, wants b
Thread 2: b.transferTo(a, 50)    holds b, wants a
Neither can continue.

The four conditions

A deadlock requires all four of these at once, so breaking any one prevents it:

• Mutual exclusion - a lock is held by one thread at a time.
• Hold and wait - a thread holds one lock while requesting another.
• No preemption - a lock cannot be taken away.
• Circular wait - a cycle of threads each waiting on the next.

Fix 1: a global lock ordering

public void transferTo(Account target, long amount) {
    Account first = this.id < target.id ? this : target;
    Account second = this.id < target.id ? target : this;

    synchronized (first.lock) {
        synchronized (second.lock) {
            this.balance -= amount;
            target.balance += amount;
        }
    }
}

Every thread acquires locks in the same order, so a cycle is impossible. This is the standard and most reliable fix.

Fix 2: try with a timeout

public boolean transferTo(Account target, long amount) throws InterruptedException {
    if (lock.tryLock(1, TimeUnit.SECONDS)) {
        try {
            if (target.lock.tryLock(1, TimeUnit.SECONDS)) {
                try {
                    balance -= amount;
                    target.balance += amount;
                    return true;
                } finally {
                    target.lock.unlock();
                }
            }
        } finally {
            lock.unlock();
        }
    }
    return false;      // back off and let the caller retry
}

Livelock and starvation

// Livelock: both back off politely, forever
while (!acquired) {
    if (tryLock()) { acquired = true; }
    else { releaseEverything(); Thread.sleep(10); }   // both retry in lock step
}

Adding a small random element to the back off breaks the symmetry.

Detecting a deadlock

Found one Java-level deadlock:
=============================
"worker-1":
  waiting to lock monitor 0x00007f... (a com.example.Account),
  which is held by "worker-2"
"worker-2":
  waiting to lock monitor 0x00007f... (a com.example.Account),
  which is held by "worker-1"

Take a thread dump with jstack or jcmd. The JVM detects monitor deadlocks and prints exactly this. Explicit Lock deadlocks are not always reported, which is one more reason to prefer a consistent lock order.

ThreadMXBean threads = ManagementFactory.getThreadMXBean();
long[] deadlocked = threads.findDeadlockedThreads();
if (deadlocked != null) {
    logger.severe("Deadlock involving " + deadlocked.length + " threads");
}

A checklist for shared state

1. Can this data be immutable? If so, the problem disappears.
2. Can it be confined to one thread?
3. Can a concurrent collection or an atomic class handle it?
4. If a lock is needed, what exactly does it protect, and for how long?
5. If more than one lock is needed, what is the global order?
6. Is any unknown code called while a lock is held?

Common mistakes

• Assuming a thread safe collection makes compound operations safe.
• Acquiring two locks in different orders in different methods.
• Calling a callback or listener while holding a lock, because it may lock something else.
• Testing concurrency on one machine and concluding the code is correct.
• Using Thread.sleep to make an intermittent bug go away.
• Synchronising on objects that other code can also lock.

Best practices

• Prefer immutability; a value that never changes needs no protection.
• Prefer confinement; state used by one thread needs no lock.
• Use the concurrent collections and atomic classes rather than hand written locking.
• Hold one lock at a time whenever possible.
• When two are unavoidable, define and document a global order.
• Never call unknown code while holding a lock.
• Use timeouts so a stuck system fails visibly rather than hanging.

Practice

1. Write a transfer method that deadlocks, reproduce it, then fix it with lock ordering.
2. Explain why containsKey followed by put is a race even on a concurrent map.
3. Which of the four deadlock conditions does tryLock break?
4. Describe the difference between deadlock, livelock and starvation.
5. Take a thread dump of a deadlocked program and identify both locks.

Conclusion

Race conditions come from unprotected compound operations; deadlocks come from locks taken in inconsistent orders. Remove shared mutable state where you can, and where you cannot, protect it with a single well defined lock order.