Home/Learn/Operating Systems/Deadlock Prevention

Deadlock Prevention

Intermediate

Deadlocks

Deadlock prevention eliminates deadlock by ensuring at least one of the four Coffman conditions can never hold in the system.

Overview

Prevention is the most conservative approach — it imposes constraints on how processes request resources, guaranteeing deadlock is structurally impossible. Each strategy targets one condition: making resources shareable (mutual exclusion), requiring all-or-nothing resource requests (hold and wait), allowing the OS to preempt resources (no preemption), or enforcing a global lock ordering (circular wait). Prevention is simpler to reason about than avoidance or detection but can lead to poor resource utilisation or starvation. In Java, lock ordering and tryLock() with timeout are the two most practical prevention techniques.

Lock Ordering: Eliminating Circular Wait

Assign a globally consistent total order to all locks. Every thread must acquire locks in ascending order only. This makes a circular dependency structurally impossible — you can never have P1 waiting for P2 while P2 is waiting for P1 if both must follow the same ordering.

Java — Lock ordering to prevent circular wait

import java.util.concurrent.locks.ReentrantLock;

// Assign a numeric ID to each lock — always acquire lower ID first
ReentrantLock lockA = new ReentrantLock(); // id = 1
ReentrantLock lockB = new ReentrantLock(); // id = 2

// SAFE: both threads acquire in the same order (A before B)
Runnable safeTask = () -> {
    lockA.lock();
    try {
        System.out.println(Thread.currentThread().getName() + ": acquired A");
        lockB.lock();
        try {
            System.out.println(Thread.currentThread().getName() + ": acquired B");
            // critical section
        } finally {
            lockB.unlock();
        }
    } finally {
        lockA.unlock();
    }
};

Thread t1 = new Thread(safeTask, "T1");
Thread t2 = new Thread(safeTask, "T2");
t1.start();
t2.start();
// No deadlock: circular wait condition is broken
// T2 will block on lockA.lock() until T1 releases it

tryLock with Timeout: Breaking Hold-and-Wait

Using tryLock() with a timeout means a thread that cannot acquire a lock within the deadline gives up and releases any locks it already holds. This breaks hold-and-wait: the thread will not indefinitely hold resources while waiting for others.

Java — tryLock timeout to break hold-and-wait

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

ReentrantLock lock1 = new ReentrantLock();
ReentrantLock lock2 = new ReentrantLock();

// tryLock with timeout — breaks hold-and-wait
Runnable task = () -> {
    while (true) {
        boolean got1 = false;
        boolean got2 = false;
        try {
            got1 = lock1.tryLock(50, TimeUnit.MILLISECONDS);
            got2 = lock2.tryLock(50, TimeUnit.MILLISECONDS);

            if (got1 && got2) {
                System.out.println(Thread.currentThread().getName() + ": both locks acquired");
                // do work
                return;
            }
        } catch (InterruptedException e) {
            Thread.currentThread().interrupt();
            return;
        } finally {
            // Release BOTH locks if we didn't get both (no partial hold)
            if (got2) lock2.unlock();
            if (got1) lock1.unlock();
        }
        // Back-off before retry to avoid livelock
        try {
            Thread.sleep((long)(Math.random() * 10));
        } catch (InterruptedException e) {
            Thread.currentThread().interrupt();
            return;
        }
    }
};

Key Points to Remember

1Prevention targets one Coffman condition structurally, making deadlock impossible at design time.
2Lock ordering (enforcing total order on acquisition) is the most widely used prevention strategy in Java.
3tryLock() with timeout breaks hold-and-wait but requires careful retry logic to avoid livelock.
4Eliminating mutual exclusion is only possible for inherently shareable resources (e.g., read-only data, ReadWriteLock).
5Prevention is safer than detection but may underutilise resources (e.g., holding all locks upfront blocks other processes).
6Java's ReadWriteLock reduces mutual exclusion by allowing concurrent readers, preventing deadlocks on read-heavy data.

Interview Questions

How does enforcing a global lock order prevent deadlock? Give an example.

EasyMicrosoft

What is the difference between deadlock prevention and deadlock avoidance?

MediumAmazon

How does tryLock() differ from lock() in ReentrantLock, and why is it useful for deadlock prevention?

MediumAtlassian

In a distributed system, how would you implement lock ordering across services to prevent deadlock?

HardGoogle

Ask Aria about Deadlock Prevention

Your personal AI tutor — ask anything about this concept

Revision Status

Personal Notes

Discussion

Loading discussion…

Resource Allocation Graph

Deadlock Avoidance: Banker's Algorithm