Shulou(Shulou.com)06/01 Report--

This article mainly introduces the relevant knowledge of "how to achieve deadlock-free synchronization in Java". The editor shows you the operation process through an actual case. The operation method is simple, fast and practical. I hope this article "how to achieve deadlock-free synchronization in Java" can help you solve the problem.

Thread synchronization is a good tool to overcome competitive conditions in multithreaded programs. But it also has a dark side. Deadlock: a serious error that is difficult to find, reproduce, and fix. The only reliable way to prevent them from happening is to design your code correctly, which is the subject of this article. We will look at the origin of deadlocks, consider a way to discover potential deadlocks in existing code, and propose a practical method for designing deadlock-free synchronization. These concepts will be illustrated by a simple demonstration project.

It is assumed that the reader is already familiar with multithreaded programming and has a good understanding of the thread synchronization primitive in Java. In the following sections, we will not distinguish between synchronous statements and lock API, using the term "lock" to refer to these two types of reentrant locks, preferring the former in the example.

I. deadlock mechanism

Let's review how deadlocks work. Consider the following two approaches:

Java:

Void increment ({synchronized (lock1) {synchronized (lock2) {variablel + +;} void decrement ({synchronized (lock2) {synchronized (lock1) {variable--;})

These methods are deliberately designed to generate deadlocks. Let's consider in detail how this happened.

Increment () and decrement () basically consist of the following five steps:

Form 1

Step

Increment ()

Decrement ()

one

Acquire lock1

Acquire lock2

two

Acquire lock2

Acquire lock1

three

Perform increment

Perform decrement

four

Release lock2

Release lock1

five

Release lock1

Release lock2

Suppose you have two parallel threads, one executing increment () and the other executing decrement (). The steps of each thread will be executed in normal order, but if we consider the two threads together, the steps of one thread will be randomly interlaced with the steps of the other thread. Randomness comes from unpredictable delays imposed by the system thread scheduler. There are many possible interleaving patterns or scenarios (252, to be exact) and can be divided into two groups. The first is that one of the threads is fast enough to acquire two locks (see Table 2). Obviously, steps 1 and 2 of these two methods can only be passed when the corresponding locks are idle, otherwise the execution thread will have to wait for them to be released.

Form 2

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

In the second group, both threads successfully acquired the lock. The results are shown in Table 3: all cases in this group have been completed successfully.

Form 3

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

...

...

Everything in this group causes the first thread to wait for the lock owned by the second thread, while the second thread waits for the lock owned by the first thread, so neither thread can proceed further.

This is a classic deadlock situation with all typical properties. Let's outline the important ones:

There are at least two threads, each occupying at least two locks.

Deadlocks occur only in specific thread timing combinations.

The occurrence of a deadlock depends on the locking order.

The second attribute means that deadlocks cannot be reproduced 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 run perfectly on one system and fail on another. Therefore, the only way to deliver the right application is to eliminate deadlocks through design. There are two basic approaches to this design, so let's start with a simpler one.

two。 Coarse-grained synchronization

As you can see from the first attribute in the list above, a deadlock does not occur if no thread in our application is allowed to hold multiple locks at the same time. OK, this sounds like a plan, but how many locks should we use and where should we put them?

The simplest and most direct 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 to be synchronous. This method is applied to java.util.Hashtable. The simple price is the performance loss due to lack of concurrency, because all methods are blocking each other.

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

There are transactions involving two variables.

Both variables are connected to the third variable (transitivity).

Therefore, you first group variables in such a way that any two variables in the same group have transactional joins and none of the two variables in different groups.

The above explanation is a bit short for the exact meaning of the terms "transaction" and "involves", but if you want to explain it accurately, the article is too long, so this article only leaves the reader with intuition and experience.

A good real-world example of this advanced coarse-grained synchronization is java.util.concurrent.ConcurrentHashMap. Inside this object, there are many identical data structures ("buckets"), each protected by its own lock. The transaction is dispatched to a bucket determined by the hash code of the key. Therefore, transactions with different keys mostly go into different buckets, which allows them to execute concurrently without sacrificing thread safety, which is possible because of the transaction independence of buckets.

However, some solutions require a higher level of concurrency than coarse-grained synchronization can achieve. Later, we will consider how to deal with this problem, but first, we need to introduce an effective way to analyze synchronization schemes.

3. Lock graph

Suppose you need to determine whether a given code contains a potential deadlock. Let's call this task "synchronous analysis" or "deadlock analysis". How will you deal with this problem?

Most likely, you will try to sort all possible scenarios of thread contention for locks in an attempt to find out if there are any bad scenarios. In Section 1, we took such a simple approach that we found that there were too many scenarios. Even in the simplest case, there are 252, so it is impossible to examine them thoroughly. In practice, you may end up thinking about only a few scenarios and hope you haven't missed something important. In other words, fair deadlock analysis cannot be done in a naive way, and we need a specialized and more effective method.

This method includes building a lock graph and checking it for circular dependencies. A lock graph is a graph that shows the interaction between locks and threads on these locks. Each closed loop in such a diagram indicates that there may be a deadlock, and the lack of a closed loop ensures the deadlock security of the code.

This is the secret of drawing lock diagrams. It takes the code in section 1 as an example:

For each lock in the code, place a corresponding node on the diagram; in this case, these are lock1 and lock2

Draw an arrow from node A to node B for all statements that threads attempt to acquire lock B if they already hold lock A; in this example, there will be "lock 1-> lock 2" decrement () in increment () and lock2-> lock1. If a thread uses multiple locks sequentially, an arrow is drawn for every two consecutive locks.

The final diagram of the example in Section 1 is as follows:

Figure 3

It has a closed loop: lock1-> lock2-> lock1, which immediately tells us that the code contains potential deadlocks.

Let's do one more exercise. Consider the following code:

Java:

Void transaction1 (int amount) {synchronized (lock1) {synchronized (lock2) {/ / do something}} void transaction2 (int amount) {synchronized (lock2) {synchronized (lock3) {/ / do something}} void transaction3 (int amount) {synchronized (lock3) {synchronized (lock1) {/ / do zomething}

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

Again, this figure immediately shows that our design contains potential deadlocks. But it's more than that. It also reminds us how to fix the design; we just need to break the cycle! For example, we can exchange the lock transaction3 () in the method. The corresponding arrowhead changes direction, and the diagram in figure 4 color B becomes loop-free, which ensures the deadlock security of the fixed code.

Now that we are familiar with the magic of diagrams, we are ready to continue to use more complex but efficient methods to design deadlock-free synchronization.

4. Fine-grained synchronization with locking sort

This time, we are taking the route of synchronization as fine-grained as possible, hoping to get 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 multiple transactions at the same 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:

Java:

Void transaction (Item i1 Magi item i2, Item i3 Magi double amount) {synchronized (i1.lock) {synchronized (i2.lock) {synchronized (i3.lock) {/ / do actual transaction on the items}

Once the lock is acquired, these variables cannot be accessed by other transactions, so they are not modified concurrently. 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, such a design immediately leads to the possibility of deadlocks, because now we are dealing with multiple threads and multiple locks for each thread.

Then the second design principle comes into play, indicating 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 locks in the order defined by their index. Applying this principle to the above code, we get a complete description of the fine-grained design:

Java:

Void transaction (Item i1 Magi item i2 Magi item i3 Magi double... Amounts) {/ / Our plan is to use item IDs as canonical indices for locksItem [] order = {i1, i2, i3}; Arrays.sort (order, (a, b)-> Long. Compare (a.idjournal b.id); synchronized (order [o] .lock) {synchronized (order [1] .lock) {synchronized (order [2] .lock) {/ / do actual transaction on the items}

But does determining canonical ordering really prevent deadlocks? Can we prove it? The answer is yes, we can use the lock graph to do this.

Suppose we have a system with N variables, so there are N associated locks, so there are N nodes in the graph. If there is no forced sort, the lock will be grabbed in random order

No matter how hard we try, we will not find a closed loop on this graph, because there can be a closed loop only if the arrows are in both directions, but this is not the case. Moreover, no closed loop means no deadlock. Proved to be complete.

Well, by using fine-grained locks and lock sorting, we can build a system with high concurrency, thread safety, and no deadlock. But is there a price to pay for improving concurrency? Let's think about it.

First of all, 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 fine-grained design assumes that lock capture is at least twice as large. However, as the number of concurrent requests increases, fine-grained design will soon get better due to the use of multiple CPU cores.

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

Last but not least is the complexity of the code. While coarse-grained design can be accomplished by declaring that some methods are synchronized, fine-grained methods require a considerable amount of code, and sometimes we may even need to mess up business logic. Such code needs to be carefully written and more difficult to maintain. Unfortunately, this difficulty cannot be solved, but the result is worth the trouble, which will be demonstrated below.

5. Demonstration project

To understand what the proposed design pattern looks like in real code, let's take a look at a simple demonstration project. The goal of the project is to build a library that simulates some basic functions of the bank. For brevity, it uses a fixed set of accounts and implements only four operations: inquiry of balances, deposits, withdrawals, and transfer of funds between accounts. To make the task more interesting, it is required that the account balance should not be negative or exceed a certain value. Transactions that violate these rules should be rejected. The library API is defined in the interface MockBank.

There are three implementations of this interface that use the different synchronization methods described above:

CoarseGrainedImpl uses coarse-grained synchronization.

FineGrainedImpl uses a basic version of fine-grained synchronization.

FineGrainedWithMappingImpl uses a memory-efficient version of fine-grained synchronization.

There is also a test of the performance and correctness of the implementation, MockBankCrashTest. Each source file contains a detailed description of the algorithm in the class comments. Multiple test runs do not show thread safety violations or deadlocks. On multi-core systems, fine-grained designs perform several times as much as coarse-grained designs, as expected.

All the project files are here.

6. Invisible lock

So far, the proposed design pattern seems to automatically solve any synchronization problem. While this is not entirely untrue, there are some issues that you should pay attention to.

Although the considerations in the above section are correct and effective in themselves, they do not take into account the environment. Often, this is an error because our code inevitably interacts with the operating system and libraries, and there may be hidden locks that can interfere with our synchronized code, resulting in unexpected deadlocks. Let's look at an example. Consider the following code:

Java:

Private Hashtable db = new Hashtable (); private long version;public void put (String key,long value) {updateversion (key); db. Put (key,value);} public long increment (String key) {db.computeIfPresent (key, (k, v)-> {updateversion (k); return vault 1;}):} private synchronized void updateversion (String key) {db.put (key+ ".version", versiontl++);}

From this point of view, this code should be deadlock-free, because updateVersion (). However, this impression is wrong because there is actually an additional hidden lock in the Hashtable instance. The call chain put ()-updateVersion () and increment ()-computeIfPresent ()-updateVersion () acquire the two locks in reverse order, which leads to potential deadlocks.

An experienced reader may correctly argue here that the above code is rather lame and is deliberately designed to cause deadlocks. Then, here is a more concise example, where we try to exchange two values atomically in the mapping:

Java:

Private final Map map = new ConcurrentHashMap (); map.put (1, "1"); map. Put (2, "2");} public void swapalues (Integer key1,Integer key2) {map.compute (key1, (K1Magne v1)-> {return map. Put (key2, v1); / / returns v2}):}

This time, there was no lock at all, and the code seemed perfectly legal, but we encountered a potential deadlock again. The reason is that the ConcurrentHashMap is designed internally, which is outlined in Section 2. Calling swapValues (1Magne2) and swapValues (2Phone1) in reverse order to acquire the lock of the corresponding bucket means that the code may be deadlocked. This is why the document ConcurrentHashMap.compute () strongly discourages attempts to change the map from the callback. Unfortunately, in many cases, such warnings are missing in the documentation.

As shown in the example above, interference with hidden locks is most likely to occur in callback methods. Therefore, it is recommended that you keep the callback short, simple, and do not call synchronization methods. If this is not possible, you should always keep in mind that the thread performing the callback may hold one or more hidden locks and plan synchronization accordingly.

This is the end of the introduction to "how to achieve deadlock-free synchronization in Java". Thank you for reading. If you want to know more about the industry, you can follow the industry information channel. The editor will update different knowledge points for you every day.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.