How to avoid deadlock in Java

Deadlock can be avoided in some cases. This article will demonstrate three techniques for avoiding deadlocks. Friends who are interested in knowledge about avoiding deadlocks in Java should learn from this article

In some cases, deadlocks can be avoided. This article will demonstrate three techniques for avoiding deadlock:

1. Locking sequence

2. Locking time limit

3. Deadlock detection

Lock order

When multiple threads require the same locks but lock them in different orders, deadlock can easily occur.

If we can ensure that all threads obtain locks in the same order, deadlock will not occur. Look at the following example:

Thread 1:
 lock A 
 lock B
Thread 2:
  wait for A
  lock C (when A locked)
Thread 3:
  wait for A
  wait for B
  wait for C

If a thread (such as thread 3) needs some locks, then it must acquire the locks in a determined order. It can only acquire subsequent locks after acquiring the lock in front of it in sequence.

For example, thread 2 and thread 3 can only try to acquire lock C after acquiring lock A (acquiring lock A is a necessary condition for acquiring lock C). Because thread 1 already owns lock A, threads 2 and 3 need to wait until lock A is released. Then they must successfully lock A before they try to lock B or C.

Locking in order is an effective deadlock prevention mechanism. However, this method requires you to know all the locks that may be used in advance (and properly sequence these locks), but sometimes it is unpredictable.

Lock time limit

Another way to avoid deadlock is to add a timeout when trying to acquire the lock. This means that if this time limit is exceeded during the process of trying to acquire the lock, the thread will give up the lock request. If a thread does not successfully acquire all required locks within a given time limit, it will roll back and release all acquired locks, then wait for a random period of time before trying again. This random waiting time gives other threads the opportunity to try to acquire the same locks, and allows the application to continue running without acquiring the lock (you can continue to run and do other things after the lock times out) , then go back and repeat the previous locking logic).
The following is an example showing a scenario where two threads try to acquire the same two locks in different orders, roll back and try again after a timeout occurs:

 Thread 1 locks A
Thread 2 locks B
Thread 1 attempts to lock B but is blocked
Thread 2 attempts to lock A but is blocked
Thread 1's lock attempt on B times out
Thread 1 backs up and releases A as well
Thread 1 waits randomly (e.g. 257 millis) before retrying.
Thread 2's lock attempt on A times out
Thread 2 backs up and releases B as well
Thread 2 waits randomly (e.g. 43 millis) before retrying.

In the above example, thread 2 retries the lock 200 milliseconds earlier than thread 1, so it can successfully acquire two locks first. At this time, thread 1 tries to acquire lock A and is in the waiting state. When thread 2 ends, thread 1 can also successfully acquire these two locks (unless thread 2 or other threads acquire some of the locks before thread 1 successfully acquires the two locks).

It should be noted that due to the lock timeout, we cannot think that this scenario must be a deadlock. It could also be that the thread that acquired the lock (causing other threads to timeout) takes a long time to complete its task.

In addition, if there are many threads competing for the same batch of resources at the same time, even if there is a timeout and rollback mechanism, it may still cause these threads to try repeatedly but never get the lock. If there are only two threads and the retry timeout is set between 0 and 500 milliseconds, this phenomenon may not happen, but if there are 10 or 20 threads, the situation is different. Because the probability that these threads will wait for equal retry times is much higher (or so close that it will cause problems). (The timeout and retry mechanism is to avoid competition that occurs at the same time. However, when there are many threads, there is a high possibility that the timeout time of two or more threads will be the same or close, so even if competition occurs and a timeout occurs, Later, because the timeout is the same, they will start to retry at the same time, resulting in a new round of competition and bringing new problems)

There is a problem with this mechanism, which cannot be done in Java. Set the timeout period for synchronized synchronized blocks. You need to create a custom lock, or use the tools in the java.util.concurrent package in Java 5. Writing a custom lock class is not complicated, but is beyond the scope of this article.

Deadlock detection

Deadlock detection is a better deadlock prevention mechanism. It is mainly aimed at those situations where it is impossible to achieve sequential Scenarios where locking and lock timeout are not feasible.

Whenever a thread acquires a lock, it will be recorded in the thread- and lock-related data structures (map, graph, etc.). In addition, whenever a thread requests a lock, it also needs to be recorded in this data structure.

When a thread fails to request a lock, the thread can traverse the lock graph to see if a deadlock occurs. For example, thread A requests lock 7, but lock 7 is held by thread B at this time. At this time, thread A can check whether thread B has requested the lock currently held by thread A. If thread B does have such a request, then a deadlock has occurred (thread A owns lock 1 and requests lock 7; thread B owns lock 7 and requests lock 1).

Of course, deadlock is generally much more complicated than the situation where two threads hold each other's locks. Thread A waits for thread B, thread B waits for thread C, thread C waits for thread D, and thread D waits for thread A. In order for thread A to detect deadlock, it needs to progressively detect all locks requested by B. Starting from the lock requested by thread B, thread A found thread C, then found thread D, and found that the lock requested by thread D was held by thread A itself. This is when it knows a deadlock has occurred.
So what should these threads do when a deadlock is detected?

A feasible approach is to release all locks, roll back, and wait for a random period of time before trying again. This is similar to a simple lock timeout. The difference is that the rollback occurs only when a deadlock has occurred, not because the lock request has timed out. Although there is backoff and waiting, if there are a large number of threads competing for the same batch of locks, they will still deadlock repeatedly.

A better solution is to set priority for these threads, let one (or several) threads roll back, and the remaining threads continue as if no deadlock has occurred. They need locks. If the priorities assigned to these threads are fixed, the same threads will always have higher priority. To avoid this problem, random priorities can be set when a deadlock occurs.

The above is the detailed content of How to avoid deadlock in Java. For more information, please follow other related articles on the PHP Chinese website!