Deadlock due to improper execution sequence

In order to ensure the safety of threads, we have introduced the locking mechanism, but if we use locking without restrictions, it may lead to lock ordering deadlock. In the previous article, we also mentioned the resource deadlock caused by insufficient resources in online terms.

This article will discuss the problem of sequential deadlock.

Let's discuss a common problem of account transfer. Account a is to be transferred to account B. In order to ensure that a and B are not accidentally operated by other threads in the process of transfer, we need to lock a and B before transfer. Let's look at the transfer code:

    public void transferMoneyDeadLock(Account from,Account to, int amount) throws InsufficientAmountException {
        synchronized (from){
            synchronized (to){
                transfer(from,to,amount);
            }
        }
    }

    private void transfer(Account from, int amount) throws InsufficientAmountException {
        if(from.getBalance() < amount){
            throw new InsufficientAmountException();
        }else{
            from.debit(amount);
            to.credit(amount);
        }
    }

It seems that there is no problem with the above program, because we lock both from and to, and the program should be executed perfectly according to our requirements.

So if we consider the following scenario:

A：transferMoneyDeadLock（accountA, accountB, 20）
B：transferMoneyDeadLock（accountB, accountA, 10）

If a and B execute at the same time, it may occur that a obtains the lock of AccountA and B obtains the lock of Accountb. As a result, the following code cannot continue to execute, resulting in a deadlock.

Is there any good way to deal with this situation?

No matter how the parameters are passed, we first lock AccountA and then lock Accountb. Will there be no deadlock?

Let's look at the code implementation:

    private void transfer(Account from, int amount) throws InsufficientAmountException {
        if(from.getBalance() < amount){
            throw new InsufficientAmountException();
        }else{
            from.debit(amount);
            to.credit(amount);
        }
    }

    public void transferMoney(Account from, int amount) throws InsufficientAmountException {

       int fromHash= System.identityHashCode(from);
       int toHash = System.identityHashCode(to);

       if(fromHash < toHash){
           synchronized (from){
               synchronized (to){
                   transfer(from, amount);
               }
           }
       }else if(fromHash < toHash){
            synchronized (to){
                synchronized (from){
                    transfer(from, amount);
                }
            }
        }else{
           synchronized (lock){
           synchronized (from) {
               synchronized (to) {
                   transfer(from, to, amount);
               }
             }
           }
       }
    }

In the above example, we use system Identityhashcode to obtain the hash values of the two accounts, and select the lock order by comparing the hash values.

If the hash values of two accounts are exactly equal, we introduce a new external lock to ensure that only one thread can run internal methods at the same time, so as to ensure the execution of tasks without deadlock.

Examples of this article can be referred to https://github.com/ddean2009/learn-java-concurrency/tree/master/accountTransferLock