Summary:Recently, when optimizing the locking method of the program, there was a deadlock! ! Why? ! After careful analysis, the reason was finally found.

This article is shared from the HUAWEI CLOUD community “[High Concurrency]Deadlocked when optimizing the locking method! ! “, Author: Glacier.

written in front

Recently, when optimizing the locking method of the program, there was a deadlock! ! Why? ! After careful analysis, the reason was finally found.

Why do we need to optimize the locking method?

We use the TransferAccount.class object in the transfer class TransferAccount to lock the program, as shown below.

public class TansferAccount{
 private Integer balance;
 public void transfer(TansferAccount target, Integer transferMoney){
 synchronized(TansferAccount.class){
 if(this.balance >= transferMoney){
 this.balance -= transferMoney;
 target.balance += transferMoney;
 } 
 }
 }
}

This method does solve the concurrency problem of transfer operations, but is this method really advisable in a high-concurrency environment? Just imagine, if we use the above code to process transfer operations in a high-concurrency environment, because the TransferAccount.class object is created by the JVM when loading the TransferAccount class, all TransferAccount instance objects will share a TransferAccount.class object. In other words, when all TransferAccount instance objects execute the transfer() method, they are mutually exclusive! ! in other words,All transfer operations are serial! !

If all transfer operations are performed serially, the consequence is that the transfer operation from account C to account D can only be performed after the transfer from account A to account B is completed. If Internet users all over the world perform transfer operations together, and these transfer operations are executed serially, then the performance of the program is completely unacceptable! ! !

actually,The operation of account A transferring money to account B and the operation of account C transferring money to account D can be executed in parallel. Therefore, we must optimize the locking method to improve the performance of the program! !

Preliminary optimization of locking methods

Since it is not advisable to directly lock the program with TransferAccount.class in a high-concurrency environment, what should we do? !

Carefully analyze the above code business. The transfer operation of the above code involves the transfer-out account this and the transfer-in account target. Therefore, we can lock the transfer-out account this and the transfer-in account target respectively. Only two accounts are locked. The transfer operation is only performed when the locks are all successful.so that it can be doneThe operation of account A transferring money to account B and the operation of account C transferring money to account D can be executed in parallel.

We can express the optimized logic in the figure below.

According to the above analysis, we can optimize the code of TransferAccount as shown below.

public class TansferAccount{
 //账户的余额
 private Integer balance;
 //转账操作
 public void transfer(TansferAccount target, Integer transferMoney){
 //对转出账户加锁
 synchronized(this){
 //对转入账户加锁
 synchronized(target){
 if(this.balance >= transferMoney){
 this.balance -= transferMoney;
 target.balance += transferMoney;
 } 
 }
 }
 }
}

At this point, the above code looks fine,But is that really the case? I also hope that the program is perfect, but it is often not what we think!Yes, the above program will appear deadlock, Why is there a deadlock? Next, we start to analyze a wave.

Deadlock problem analysis

The code in the TransferAccount class looks perfect, but the optimized locking method will lead to deadlock! ! ! This is the conclusion I came to from my own test! !

Regarding the deadlock, we can combine the improved TransferAccount class to give a simple scenario: Suppose there are two threads, thread A and thread B, running on two different CPUs at the same time. Thread A performs the operation of transferring account A to account B, and thread B Execute the operation of transferring money from account B to account A. When thread A and thread B execute the synchronized (this) code, thread A acquires the lock of account A, and thread B acquires the lock of account B. When the synchronized (target) code is executed, when thread A tries to acquire the lock of account B, it finds that account B has been locked by thread B. At this time, thread A starts to wait for thread B to release the lock of account B; while thread B tries to acquire account A When the lock is found, account A has been locked by thread A. At this time, thread B starts to wait for thread A to release the lock of account A.

In this way, thread A holds the lock of account A and waits for thread B to release the lock of account B, thread B holds the lock of account B and waits for thread A to release the lock of account A, deadlock occurs! !

Necessary conditions for deadlock

Before how to solve the deadlock, let’s first look at the necessary conditions for a deadlock to occur. If a deadlock is to occur, the following four necessary conditions must exist, none of which can be dispensed with.

mutually exclusive condition

A resource is only occupied by one thread during a period of time. At this time, if other threads request the resource, the requesting thread can only wait.

inalienable condition

The resources obtained by the thread cannot be forcibly taken away by other threads before they are used up, that is, they can only be released by the thread that obtained the resource (only actively released).

Request and Hold Conditions

The thread has kept at least one resource, but it puts forward a new resource request, and the resource has been occupied by other threads. At this time, the requesting thread is blocked, but it does not let go of the resource it has obtained.

loop wait condition

Since the above four conditions must exist for the occurrence of deadlock, can everyone think of how to prevent deadlock?

deadlock prevention

In concurrent programming, once a deadlock occurs, there is basically no particularly good solution. Generally, the only solution is to restart the application. therefore,The best way to solve deadlock is to prevent deadlock.

When a deadlock occurs, there must be four necessary conditions for a deadlock. In other words, if we only need to “destroy” one of the four necessary conditions for deadlock when writing a program, we can avoid the occurrence of deadlock. Next, let’s discuss together how to “destroy” these four necessary conditions.

break the mutex condition

Mutual exclusion conditions are something we cannot destroy, because we use locks for mutual exclusion between threads. This point needs special attention! ! ! !

breach of the inalienable condition

The core of breaking the inalienable condition is to let the current thread actively release the resources it owns. About this, synchronized cannot do it. We can use the Lock under the java.util.concurrent package to solve it. At this point, we need to modify the code of the TransferAccount class to look like the following.

public class TansferAccount{
 private Lock thisLock = new ReentrantLock();
 private Lock targetLock = new ReentrantLock();
 //账户的余额
 private Integer balance;
 //转账操作
 public void transfer(TansferAccount target, Integer transferMoney){
 boolean isThisLock = thisLock.tryLock();
 if(isThisLock){
 try{
 boolean isTargetLock = targetLock.tryLock();
 if(isTargetLock){
 try{
 if(this.balance >= transferMoney){
 this.balance -= transferMoney;
 target.balance += transferMoney;
 } 
 }finally{
 targetLock.unlock
 }
 }
 }finally{
 thisLock.unlock();
 }
 }
 }
}

Among them, there are two tryLock methods in Lock, as shown below.

The tryLock() method has a return value, which means that it is used to try to acquire the lock. If the acquisition is successful, it returns true. If the acquisition fails (that is, the lock has been acquired by other threads), it returns false, which means that this method is no matter what will return immediately. It will not wait there all the time when the lock cannot be obtained.

• tryLock(long time, TimeUnit unit) method

The tryLock(long time, TimeUnit unit) method is similar to the tryLock() method, but the difference is that this method will wait for a certain period of time when the lock cannot be obtained. If the lock is not obtained within the time limit, it will return false. Returns true if the lock was originally acquired or was acquired during the wait period.

Destruction request and hold condition

By destroying the request and hold conditions, we can apply for all the resources we need at one time. For example, in the process of completing the transfer operation, we apply for account A and account B at one time. After both accounts are successfully applied, we can perform the transfer operation . At this point, we need to create another class ResourcesRequester to apply for resources. The function of this class is to apply for resources and release resources. At the same time, the TransferAccount class needs to hold a singleton object of the ResourcesRequester class. When we need to perform a transfer operation, we first apply to the ResourcesRequester for both the transfer-out account and the transfer-in account. After the application is successful, the two resources are locked; When the transfer operation is completed, release the lock and release the transfer-out account and transfer-in account resources requested by the ResourcesRequester class.

The code for the ResourcesRequester class is shown below.

public class ResourcesRequester{
 //存放申请资源的集合
 private List<Object> resources = new ArrayList<Object>();
 //一次申请所有的资源
 public synchronized boolean applyResources(Object source, Object target){
 if(resources.contains(source) || resources.contains(target)){
 return false;
 }
 resources.add(source);
 resources.add(targer);
 return true;
 }
 //释放资源
 public synchronized void releaseResources(Object source, Object target){
 resources.remove(source);
 resources.remove(target);
 }
}

At this point, the code for the TransferAccount class is as follows.

public class TansferAccount{
 //账户的余额
 private Integer balance;
 //ResourcesRequester类的单例对象
 private ResourcesRequester requester;
 //转账操作
 public void transfer(TansferAccount target, Integer transferMoney){
 //自旋申请转出账户和转入账户，直到成功
 while(!requester.applyResources(this, target)){
 //循环体为空
 ;
 }
 try{
 //对转出账户加锁
 synchronized(this){
 //对转入账户加锁
 synchronized(target){
 if(this.balance >= transferMoney){
 this.balance -= transferMoney;
 target.balance += transferMoney;
 } 
 }
 }
 }finally{
 //最后释放账户资源
 requester.releaseResources(this, target);
 }
 }
}

break loop wait condition

To break the circular waiting condition, you can sort the resources, apply for resources in a certain order, and then lock the resources in order, which can effectively avoid deadlock.

For example, in our transfer operations, each account often has a unique id value. When we lock account resources, we can apply for account resources in the order of id values ​​from small to large, and according to the order of id from small to large To lock the account, at this time, the program will no longer wait in a loop.

The program code is shown below.

public class TansferAccount{
 //账户的id
 private Integer id;
 //账户的余额
 private Integer balance;
 //转账操作
 public void transfer(TansferAccount target, Integer transferMoney){
 TansferAccount beforeAccount = this;
 TansferAccount afterAccount = target;
 if(this.id > target.id){
 beforeAccount = target;
 afterAccount = this;
 }
 //对转出账户加锁
 synchronized(beforeAccount){
 //对转入账户加锁
 synchronized(afterAccount){
 if(this.balance >= transferMoney){
 this.balance -= transferMoney;
 target.balance += transferMoney;
 } 
 }
 }
 }
}

Summarize

In concurrent programming, when using fine-grained locks to lock multiple resources, always pay attention to the problem of deadlock. In addition, the easiest way to avoid deadlock is to prevent circular waiting conditions, set flags and sort all resources in the system, and stipulate that all threads applying for resources must operate in a certain order to avoid deadlock.

Click to follow and learn about Huawei Cloud’s fresh technologies for the first time~