68 What Are the Four Conditions That Must Be Met for a Deadlock to Occur #

In this lesson, I will introduce the 4 conditions that must be met for a deadlock to occur.

The 4 necessary conditions for a deadlock to occur #

In order for a deadlock to occur, there are 4 indispensable conditions. Let’s take a look at them one by one:

• The first one is called mutual exclusion. It means that each resource can only be used by one thread (or process) at a time. Why can’t multiple threads or processes use the same resource simultaneously? That’s because if everyone can get the resource they want, there’s no need to wait, so deadlock is impossible.
• The second one is hold and wait condition. It means that when a thread is blocked due to requesting a resource, it must hold on to the resources it has already obtained. If it blocked while requesting a resource and automatically released the resources it held (e.g., a lock), then others would naturally be able to take the resource I just released, and deadlock would not occur.
• The third one is no preemption condition. It means that a thread’s acquired resources should not be forcibly taken away before they are used up. For example, in the database example we discussed in the previous lesson, it is possible to forcibly take away the resources held by a transaction, which would prevent deadlock. So in order for deadlock to occur, the no preemption condition must be met, which means that when a thread currently holds a resource, others cannot come and take it away. Only then can deadlock occur.
• The fourth one is circular wait condition. Only when several threads form a circular wait relationship, meaning that they mutually hold the resources they need from each other and wait for each other, can deadlock occur. In the case of two threads, this “circular wait” means that they hold the resources needed by the other thread and wait for each other. In the case of three or more threads, a cycle needs to be formed, for example, by requesting the next resource held by the next thread in a circular manner.

Case analysis #

Now let’s go back to the example we wrote in the previous lesson and see if it meets all 4 conditions. The example code is as follows:

/**
 * Description: A situation that will definitely result in deadlock
 */
public class MustDeadLock implements Runnable {
    public int flag;
    static Object o1 = new Object();
    static Object o2 = new Object();
    public void run() {
        System.out.println("Thread " + Thread.currentThread().getName() + " has flag " + flag);
        if (flag == 1) {
            synchronized (o1) {
                try {
                    Thread.sleep(500);
                } catch (Exception e) {
                    e.printStackTrace();
                }
                synchronized (o2) {
                    System.out.println("Thread 1 acquired both locks");
                }
            }
        }
        if (flag == 2) {
            synchronized (o2) {
                try {
                    Thread.sleep(500);
                } catch (Exception e) {
                    e.printStackTrace();
                }
                synchronized (o1) {
                    System.out.println("Thread 2 acquired both locks");
                }
            }
        }
    }
    public static void main(String[] argv) {
        MustDeadLock r1 = new MustDeadLock();
        MustDeadLock r2 = new MustDeadLock();
        r1.flag = 1;
        r2.flag = 2;
        Thread t1 = new Thread(r1, "t1");
        Thread t2 = new Thread(r2, "t2");
        t1.start();
        t2.start();
    }
}

We have already analyzed and executed this code in the previous lesson, so we won’t go over it again here. Instead, let’s focus on the analysis of the 4 necessary conditions.

First, let’s look at the first condition, mutual exclusion. It is obvious that we are using synchronized locks, and the lock objects, o1 and o2, can only be obtained by one thread at a time, so the mutual exclusion condition is met.

Secondly, the hold and wait condition is also met. For example, thread 1 obtains lock o1 and then tries to acquire lock o2. At this point, it is blocked, but it does not automatically release lock o1. It holds on to the resources it has already obtained.

Third, the no preemption condition is met. In our code, the JVM does not actively take away locks held by a thread, so the no preemption condition is met as well.

Lastly, the circular wait condition is met. In our example, both threads want to acquire the resources held by the other thread. Thread 1 holds o1 and waits for o2, while thread 2 holds o2 and waits for o1. This forms a cycle, resulting in a circular wait.

As we can see, in our example, all 4 necessary conditions are met. In the future, we can start from these 4 conditions that lead to deadlock and solve deadlock problems by breaking any one of these conditions. This will be the key consideration in the deadlock resolution strategies we will discuss later.

Summary #

To summarize, in this lesson I introduced the 4 conditions that must be met for a deadlock to occur, namely mutual exclusion, hold and wait, no preemption, and circular wait. We also analyzed the example of a unavoidable deadlock that we covered in the previous lesson, and we can see that it satisfies all 4 conditions.