Troubleshooting and fixing deadlock

Question

I came across this question recently where I am suppose to find the deadlock in the code present below. I have no experience with Java or multithreading, that's why I am here to understand the problem better.

public class BankAccount {
  private final int customerId;
  private int balance;

  public BankAccount(int customerId, int openingBalance) {
    this.customerId = customerId;
    this.balance = openingBalance;
  }

  public void withdraw(int amount) throws OverdrawnException {
    if (amount > balance) {
      throw new OverdrawnException();
    }
    balance -= amount;
  }

  public void deposit(int amount) {
    balance += amount;
  }

  public int getCustomerId() {
    return customerId;
  }



  public int getBalance() {
    return balance;
  }
}


class TransferOperation extends Thread {
    int threadNum;

    TransferOperation(int threadNum) {
        this.threadNum = threadNum;
    }

    private void transfer(BankAccount fromAccount, BankAccount toAccount, int transferAmount) throws OverdrawnException {
        synchronized (fromAccount) {                    
            synchronized (toAccount) {
                fromAccount.withdraw(transferAmount);
                toAccount.deposit(transferAmount);
            }
        }
    }

    // ...
}

I have this above piece of code. I want to find where a deadlock could occur in the above code. I think only place it could occur is in the two synchronized blocks. Am I right?

If yes, can someone help me understand why? I can guess that it is probably because withdraw and deposit keeps one thread waiting for another. But this is a total guess, that's why asking for help here.

Also if I would want to prevent the deadlock, how would I go about it in the code?

Any help appreciated.

Answer 1

You are synchronize on fromAccount then toAccount objects.

Imagine that first thread calls transfer method with X,Y, while at the same time the other thread calls the same method with Y,X arguments - this leads to the deadlock.

The first thread "locks" X, the second thread "locks" Y, then the first thread are trying to lock Y, which is already locked by the second thread.
But the second thread is trying to lock X which is already locked by the first thread.
This is a deadlock.

Answer 2

Following are the possible solutions I could think of.

Possible solutions:

1. Within transfer() always lock the account with smaller id first, then lock the account with the larger id.
   Check this to see why it would work: Would you explain lock ordering?

2. Mark the whole transfer method as synchronized.
   Which will make it single threaded, that solves the issue, but it's slow for large amount of accounts.

3. Encapsulate the request as an object, send it to FIFO queue, then a single thread processor could handle it, each request is processed in a transaction.

4. (Improved based on solution 2), maintain a set of account ids of requests that are in processing, in memory.

   • If a request's 2 ids are not in the id set, then process with an existing or new parallel thread.
   • Otherwise, move it to end of queue or delay its processing in another way.

   (This implementation might be complex, and not very easy to write it correctly, though)

5. Group the requests.
   In each group, any id only appear once, then process the groups one by one.
   At a time, only one group could be processed, but with multiple threads.
   (This is kinda similar as the 3-th solution, and not trivial to impl correctly).