“This is the 20th day of my participation in the November Gwen Challenge. See details of the event: The Last Gwen Challenge 2021”.

preface

Hello everyone, I’m Llami. Deadlock is a problem that often appears in interviews. Today’s “Interview God” series will talk about deadlock.

background

Thread synchronization is a good tool to overcome race conditions in multithreaded programs. But it also has a dark side: deadlocks, serious bugs that are hard to find, reproduce, and fix. The only sure way to prevent them is to design your code correctly, which is the subject of this article. We’ll look at the origins of deadlocks, find a way to find potential deadlocks in existing code, and suggest practical ways to design deadlock-free synchronization.

It is assumed that the reader is already familiar with multithreaded programming and has a good understanding of thread synchronization primitives in Java. In the following sections, we will not distinguish between synchronization statements and lock apis, using the term “lock” to refer to both types of reentrant locks.

Deadlock mechanism

Now there are two methods:

void increment(a) {
    synchronized(lock1) {
        synchronized(lock2) { variable++; }}}void decrement(a) {
    synchronized(lock2) {
        synchronized(lock11) { variable--; }}}Copy the code

These two methods are deliberately designed to generate deadlocks so that we can consider in detail how this happens.

Both Increment () and Decrement () essentially consist of five steps:

Step increment() decrement()
1 Acquire lock1 Acquire lock2
2 Acquire lock2 Acquire lock1
3 Perform increment Perform decrement
4 Release lock2 Release lock1
5 Release lock1 Release lock2

Obviously, steps 1 and 2 of these two methods can only pass if the corresponding lock is idle; otherwise, the thread of execution will have to wait for them to be released.

Assume that you have two parallel threads, one performing increment() and the other decrement(). The steps of each thread are executed in the normal order, but if we consider two threads together, the steps of one thread will be randomly interlaced with those of the other thread. Randomness comes from unpredictable delays imposed by the system’s thread scheduler. The possible interweaving patterns or scenarios are numerous and can be divided into two groups. The first group is where one of the threads is fast enough to acquire two locks.

For example, the following table:

No deadlock
Thread-1 Thread-2 Result
1: Acquire lock1   lock1 busy
2: Acquire lock2   lock2 busy
  1: Acquire lock2 wait for lock2 release
3: Perform increment Waiting at lock2  
4: Release lock2 Intercept    lock2 lock2 changed owner
  2: Acquire lock1 wait for lock1 release
5: Release lock1 Intercept lock1 lock1 changed owner
  3: Perform decrement  
  4: Release lock1 lock1 free
  5: Release lock2 lock2 free

All cases in this group completed successfully.

In the second group, both threads successfully acquired the lock. The results are shown in the following table:

Deadlock
Thread-1 Thread-2 Result
1: Acquire lock1   lock1 busy
  1: Acquire lock2 Lock2 busy
2: Acquire lock2   wait for lock2 release
  2: Acquire lock1 wait for lock1 release
Waiting at lock2 Waiting at lock1  
… …

All cases in this group cause the first thread to wait for a lock owned by the second thread, and the second thread to wait for a lock owned by the first thread, so neither thread can proceed further:

This is a classic deadlock situation. It satisfies at least three points:

  • There are at least two threads, and each thread occupies at least two locks.
  • Deadlocks occur only in certain thread timing combinations.
  • Deadlocks occur depending on the order in which they are locked.

The second property means that deadlocks cannot be recreated at will. In addition, their reproducibility depends on the operating system, CPU frequency, CPU load, and other factors. The latter means that the concept of software testing does not apply to deadlocks, because the same code may work perfectly on one system and fail on another.

Therefore, the only way to deliver the right application is to eliminate deadlocks by design. There are two basic approaches to this design. Now, let’s start with an easier approach.

Coarse-grained synchronization

If no thread in our application is allowed to hold more than one lock at a time, deadlocks will not occur. But how many locks should we use and where should we put them?

The simplest and most straightforward answer is to protect all transactions with a single lock. For example, to protect a complex data object, you can declare all its public methods synchronous. This method is used in java.util.hashtable. The cost of simplicity is a performance penalty due to lack of concurrency, because all methods block each other.

Fortunately, in many cases, coarse-grained synchronization can be performed in a less restrictive manner, allowing for some concurrency and better performance. To explain this, we should introduce the concept of a transaction connection variable. Suppose two variables are connected on a transaction if either of two conditions are met:

  1. There are transactions involving two variables.
  2. Both variables are connected to a third variable (transitivity).

Therefore, you first group variables in such a way that any two variables in the same group are transactionally joined and no two variables in different groups are. Each group is then protected with a separate dedicated lock:

This kind of coarse-grained synchronization. A good example is the reality of Java util. Concurrent. ConcurrentHashMap. Inside this object, there are many identical data structures (” buckets “), each protected by its own lock. Transactions are dispatched to buckets determined by the hash code of the key. Therefore, transactions with different keys will mostly go into different buckets, allowing them to execute concurrently without sacrificing thread safety, which is possible due to the transactional independence of buckets.

Deadlock analysis

Suppose you need to determine whether a given code contains a potential deadlock. We call this task “synchronous analysis” or “deadlock analysis.” How do we deal with this problem?

Most likely, we will try to sort through all possible scenarios for thread contention to try to figure out if there are bad scenarios. In the deadlock mechanism section, we took the simplest approach and found that there were too many scenarios. Even in the simplest case, there are 252 of them, so a thorough examination of them is impossible. In practice, you might end up considering only a few scenarios and hope you haven’t missed something important. In other words, fair deadlock analysis cannot be done in a rudimentary way; we need a specialized, more efficient approach.

Lock the figure

This approach involves building a locking graph and checking it for circular dependencies. Lock diagrams are graphics that show the interaction of locks and threads on these locks. Each closed loop in such a diagram represents the possibility of a deadlock, and the absence of a closed loop ensures that the code is deadlocked.

How to draw the lock diagram? Take the code in the deadlock mechanism section as an example:

  1. For each lock in the code, place a corresponding node on the diagram; In the example, these arelock1 和 lock2
  2. Draw an arrow from node A to node B for all threads trying to acquire lock B when they already hold lock A; In this case,increment()There arelock1 -> lock2.decrement()There arelock2 -> lock1. If a thread uses multiple locks sequentially, an arrow is drawn for each two consecutive locks.

Here a closed loop is formed: lock1 -> lock2 -> lock1, telling us that the code contains a potential deadlock.

A more complicated example

void transaction1(int amount) {
    synchronized(lock1) {
        synchronized(lock2) {
            // do something;}}}void transaction2(int amount) {
    synchronized(lock2) {
        synchronized(lock13) {
            // do something;}}}void transaction3(int amount) {
    synchronized(lock3) {
        synchronized(lock11) {
            // do something;}}}Copy the code

Let’s see if this code is deadlock-safe. There are 3 locks: lock1, lock2, lock3 and 3 lock paths: Lock1 -> lock2 in transaction1(), lock2 -> lock3 in transaction2(), lock3 -> lock1 in transaction3().

Draw the locking diagram as follows:

Again, Figure A shows that our design contains potential deadlocks. But that’s not all. It also suggests how to fix the design; We just need to break the cycle! For example, we can exchange locks in the method transaction3(). The corresponding arrow changes direction and the graph in Figure B becomes looping free, ensuring deadlock security in the fixed code.

Fine-grained synchronization with lock sort

Take as fine-grained a synchronization approach as possible in the hope of getting the maximum possible transaction concurrency in return. This design is based on two principles.

The first principle is to prohibit any variable from participating in more than one transaction at a time.

To achieve this, we associate each variable with a unique lock and start each transaction by acquiring all the locks associated with the related variable. The following code illustrates this:

void transaction(Item i1, Item i2, Item i3, double amount) {
    synchronized(i1.lock) {
        synchronized(i2.lock) {
            synchronized(i3.lock) {
                // do something;}}}}Copy the code

Once the lock is acquired, these variables cannot be accessed by other transactions, so they are not concurrently modified. This means that all transactions in the system are consistent. At the same time, transactions on disjoint sets of variables are allowed to run concurrently. As a result, we have a highly concurrent but thread-safe system.

However, this design immediately opens up the possibility of deadlocks, because now we’re dealing with multiple threads and multiple locks per thread. This is where the second design principle comes in.

The second design principle is that locks must be acquired in a canonical order to prevent deadlocks.

This means that we associate each lock with a unique constant index and always acquire the locks in the order defined by their index. Applying this principle to the code above, we get a complete description of fine-grained design:

void transaction(Item i1, Item i2, Item i3, double. amounts) {
    // Use the id attribute of item as the lock index
    Item[] order = {i1, i2, i3};
    Arrays.sort(order, (a,b) -> Long.compare(a.id, b.id));
    synchronized(order, [0].lock) {
        synchronized(order, [1].lock) {
            synchronized(order, [2].lock) {
                // do something;}}}}Copy the code

But does determining a canonical sort really prevent deadlocks? Can we prove it? The answer is yes, we can do this using locking diagrams.

Suppose we have a system with N variables, so there are N associated locks, so there are N nodes in the graph. Without forced sorting, locks are grabbed in random order, so in the diagram, there will be random arrows in both directions, and there will definitely be a closed loop representing deadlocks:

If we enforce lock sorting, the lock paths from high to low index will be excluded, so the only arrows left will be those from left to right:

We can’t find a closed loop in the figure above, because a closed loop is only possible if the arrow flows in both directions, and no closed loop means no deadlocks.

By using fine-grained locking and lock ordering, we can build a high-concurrency, thread-safe, deadlock-free system. But is there a price to pay for increased concurrency?

First, in the case of low concurrency, there is a certain speed loss compared with the coarse-grained method. Each lock capture is a fairly expensive operation, but the fine-grained design assumes that the lock capture is at least twice as large. However, as the number of concurrent requests increases, fine-grained design quickly becomes better due to the use of multiple CPU cores.

Second, there is a memory overhead due to the large number of lock objects. Fortunately, this is easy to fix. If the protected variable is an object, we can get rid of the individual lock object and use the variable itself as our own lock. Otherwise, for example, if the variable is a primitive array element, we might only need a limited number of additional objects. To do this, we define a mapping from variable ids to moderately sized lock arrays. In this case, locks must be sorted by their actual index, not by variable ID.

conclusion

In this article, we explore deadlocks in multithreaded programming. We found that deadlocks can be completely avoided if synchronization code is written with certain design patterns. We also looked at why and how such designs work, what are the limitations of their applicability, and how to effectively find and fix potential deadlocks in existing code. It is expected that the materials provided provide sufficient practical guidance for designing perfect deadlock-free synchronization.

The last

Creation is not easy, if you feel that this article is helpful to you, please pay more attention to, a lot of praise!! Thank you!!!!!