67 How to Write an Example of an Inevitable Deadlock #

In this lesson, we will first introduce what a deadlock is, the dangers and characteristics of deadlocks, and then analyze a “definite deadlock example” through code.

What is a Deadlock? What are the Dangers? #

What is a Deadlock #

Occurs in concurrent scenarios

Firstly, you need to know that a deadlock always occurs in concurrent scenarios. In order to ensure thread safety, we sometimes use various tools, especially locks, to guarantee concurrency safety in our programs. However, if they are not used properly, it may result in deadlocks.

Mutual non-release

Deadlock is a state where two (or more) threads (or processes) hold each other’s required resources but refuse to release their own held resources. As a result, no one can obtain the desired resources, and all related threads (or processes) cannot proceed. Before changing this state, they cannot move forward. We call this state a deadlock state, and we believe that deadlocks have occurred. In simple terms, a deadlock is a situation where two or more threads (or processes) are indefinitely blocked and waiting for each other’s resources.

Examples from daily life

Below, we will use diagrams to demonstrate a deadlock situation that can occur in daily life, as shown in the following figure:

You can see from this comic strip that it depicts a scene where two gentlemen are bowing to each other. In order to show politeness, after they bow, neither of them wants to stand up first and they both hope to stand up after the other person stands up. But in this way, no one can stand up first. The action of standing up cannot be executed, and the two are in a state of waiting for each other, so this is a typical deadlock!

Example of two threads

Next, let’s take a look at an animated illustration of a deadlock situation where two threads occur, as shown in the following figure:

At this time, we have two threads, thread A and thread B. Let’s assume that thread A currently holds lock A, and thread B holds lock B. Then thread A tries to acquire lock B, but it cannot because thread B has not released lock B yet. Then thread B tries to acquire lock A, but it also cannot because lock A has already been held by thread A. As a result, thread A and thread B experience a deadlock because they both hold the resources that the other wants and refuse to release their own resources, creating a state of mutual waiting which will continue indefinitely.

Multiple threads causing deadlock

Deadlocks not only occur in scenarios with two threads, but also exist in scenarios with multiple threads. If there is a circular dependency relationship among multiple threads, that is, a cyclical dependency relationship exists, then a deadlock can also occur, as shown in the following figure:

In this example, we can see that thread 1 first holds lock A, then thread 2 holds lock B, and thread 3 holds lock C. Now each thread holds one lock respectively. Next, thread 1 wants to hold lock B, but it cannot because lock B is currently in the hands of thread 2; then thread 2 tries to acquire lock C, but it also cannot because lock C is currently in the hands of thread 3; then thread 3 tries to acquire lock A, but of course it cannot because thread 1 currently holds lock A. In this way, thread 1, thread 2, and thread 3 form a cycle of mutual dependency, resulting in a deadlock situation in multi-threading. Therefore, not only two threads, but multiple threads can also experience deadlocks in some situations.

Effects of Deadlocks #

The impact of deadlocks varies in different systems, and the size of the impact depends in part on the system’s or environment’s ability to handle deadlocks.

In databases

For example, in the design of database system software, deadlocks and recovery from deadlocks are taken into account. When executing a transaction, you may need to acquire multiple locks and hold them until the transaction is completed. The locks held by a certain transaction may also be needed by other transactions, so it is possible for a deadlock to occur between two transactions. Once a deadlock occurs, if there is no external intervention, the two transactions will wait forever. However, the database system will not allow this situation to happen. When the database detects that a group of transactions has deadlocked, depending on the strategy, it may choose to abandon one transaction. The abandoned transaction will release the locks it holds, allowing other transactions to proceed smoothly. At this point, the program can re-execute the forcibly terminated transaction, which can now be executed smoothly because all the transactions competing for resources have just completed and released the resources. In JVM

In JVM, the ability to handle deadlocks is not as strong as in databases. If a deadlock occurs in JVM, it will not be automatically resolved, so once a deadlock occurs, it will be stuck in an endless wait.

Low Probability but High Impact #

The problem of deadlock, like other concurrency safety issues, is probabilistic. In other words, even if there is a possibility of deadlock, it does not necessarily mean that it will occur 100% of the time. If the duration of holding each lock is short, the probability of conflicts occurring is low, and therefore the probability of deadlock is also low. However, in online systems, there may be millions of “acquiring lock” and “releasing lock” operations every day. In the face of such a large number of operations, the probability of the entire system encountering problems is magnified. As long as there are a few risky operations, it can lead to deadlock.

Because deadlock “may not occur”, it has become a challenge to identify deadlocks in advance. Although stress testing can detect some situations where deadlocks may occur, it is not enough to fully simulate real and long-term running scenarios. Therefore, it is not possible to identify all the potentially deadlock-prone code.

Once a deadlock occurs, depending on the responsibilities of the threads involved, it may cause subsystem crashes, performance degradation, or even the entire system to crash. Moreover, deadlocks often occur under high-concurrency and high-load conditions, which can directly impact many users, causing a series of problems. The aforementioned characteristics of low probability but high impact are common in deadlocks.

Example of Deadlock #

Below is an example of a situation that will definitely lead to deadlock. The code is as follows:

/**
 * Description: A situation that will definitely lead to 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");
    
}

...

synchronized (o1) {
        
    System.out.println("Thread 2 acquired both locks");
    
}

In this code snippet, we can see that there is an int variable called flag that serves as a flag. We also create two objects, o1 and o2, to be used as the locks in the synchronized blocks.

Let’s take a look at the run method. In this method, it first prints the name of the current thread, followed by the value of the flag variable.

If flag is equal to 1, it tries to acquire lock o1, then sleeps for 500 milliseconds, and finally tries to acquire lock o2. It then prints “Thread 1 acquired both locks”.

If flag is equal to 2, the process is reversed. It first acquires lock o2, sleeps for 500 milliseconds, and then tries to acquire lock o1. Finally, it prints “Thread 2 acquired both locks”.

Finally, let’s take a look at the main method. In the main method, we create two instances of the MustDeadLock class, r1 and r2. We set the flag of r1 to 1 and the flag of r2 to 2. Then, we create two threads, t1 and t2, to execute these two Runnable objects. The threads are named t1 and t2. Finally, we start both threads.

One possible output of the program is:

Thread t1's flag is 1
Thread t2's flag is 2

The key point here is that the program continues execution and does not stop at this point. It never prints “Thread 1 acquired both locks” or “Thread 2 acquired both locks”. This is where deadlock occurs.

Analysis of the Deadlock Process #

Let’s analyze the process of deadlock that occurs in the code:

• When the first thread starts, it checks its flag and tries to acquire lock o1 and sleep for 500 milliseconds.
• While the first thread is sleeping, the second thread starts as well. Since the flag of the second thread is 2, it enters the if (flag == 2) code block and tries to acquire lock o2. This means that while the first thread is sleeping and holding lock o1, the second thread acquires lock o2 and starts sleeping for 500 milliseconds as well.
• When the sleep duration of the first thread ends, it tries to acquire lock o2, but it is already held by the second thread.
• Similarly, when the sleep duration of the second thread ends, it tries to acquire lock o1, but it is already held by the first thread.

At this point, the first thread is waiting to acquire lock o2 and the second thread is waiting to acquire lock o1, creating a situation where they are mutually waiting for each other’s resources. This forms a deadlock. In this example, if the second thread starts before the first thread, the situation would be the same, resulting in a deadlock. This is an example where deadlock occurs “necessarily”.

Conclusion #

In this lesson, we first explained what deadlocks are and then provided examples of deadlocks in daily life, with two threads, and with multiple threads. We then analyzed the impact of deadlocks, which can prevent parts or the entire program from continuing execution in the JVM. Therefore, deadlocks can have significant consequences and should be avoided as much as possible. Lastly, we provided a detailed analysis of a code example that demonstrates a deadlock that is guaranteed to occur.