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.

How does that help? Sorry total newbie. Could you please provide a little more information? — Ravi, Jan 31 '19 at 18:51
No problem Ravi, my badness I've commented too quickly. Having a second reading leads me to see that the answer from krokodilko is far better than mine. You can get relevant information here: https://www.tutorialspoint.com/java/java_thread_deadlock.htm — Romano, Jan 31 '19 at 21:33

score 3 · Accepted Answer · answered Jan 31 '19 at 19:19

3

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.

answered Jan 31 '19 at 19:19

krokodilko

35,300
7
55
79

What is the right way to fix it? Separate the two withdraw/deposit synchronized blocks or call the transfer function twice once with withdraw and then with deposit? – Ravi Feb 01 '19 at 05:35

Eric · Answer 2 · 2019-02-04T07:15:06.337

Following are the possible solutions I could think of.

Possible solutions:

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?
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.
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.
(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)
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).

Troubleshooting and fixing deadlock

2 Answers2