Better solution instead of nested synchronized blocks in Java?

Question

I have a Bank class with a list of Account. The bank has a transfer() method to transfer a value from one account to another. The idea is to lock both the from and to accounts within a transfer.

To solve this issue I have the following code (please bear in mind that this is a very trivial example because it's just that, an example):

public class Account {
    private int mBalance;

    public Account() {
        mBalance = 0;
    }

    public void withdraw(int value) {
        mBalance -= value;
    }

    public void deposit(int value) {
        mBalance += value;
    }
}

public class Bank {
    private List<Account> mAccounts;
    private int mSlots;

    public Bank(int slots) {
        mAccounts = new ArrayList<Account>(Collections.nCopies(slots, new Account()));
        mSlots = slots;
    }

    public void transfer(int fromId, int toId, int value) {
        synchronized(mAccounts.get(fromId, toId)) {
            synchronized(mAccounts.get(toId)) {
                mAccounts.get(fromId).withdraw(value);
                mAccounts.get(toId).deposit(value);
            }
        }
    }
}

This works, but does not prevent deadlocks. To fix that, we need to change the synchronization to the following:

synchronized(mAccounts.get(Math.min(fromId, toId))) {
    synchronized(mAccounts.get(Math.max(fromId, toId))) {
        mAccounts.get(fromId).withdraw(value);
        mAccounts.get(toId).deposit(value);
    }
}

But the compiler warns me about nested synchronization blocks and I trust that that is a bad thing to do? Also, I'm not very fond of the max/min solution (I was not the one who came up with that idea) and I would like to avoid that if possible.

How would one fix those 2 problems above? If we could lock on more than one object, we would lock both the from and to account, but we can't do that (as far as I know). What's the solution then?

Thar

You definitely seem to know what you're doing. I would ignore the compiler. – Basketry

Lol, I'm just learning process concurrency... I wouldn't call it "knowing what I'm doing", I just understand how this basic example works. But thanks. – Thar

Not at all, you identified and solved the deadlock problem very well. – Basketry

I'm assuming the reason the method itself isn't synchronized is because the example over-simplifies? – Goldarn

Actually I didn't, I had help :P As I stated, the idea didn't come from me. – Thar

@Dave The transfer method? Never thought of that... Maybe the example over-simplifies, I need to think about it for a moment but I can't do that now. I need to leave. – Thar

Having said all that, in the real world all this would happen in a database so the problem is pretty moot. – Basketry

this link discusses a similar issue: download.oracle.com/javase/tutorial/essential/concurrency/… – Impatience

Answer 1

Lock ordering is indeed the solution, so you're right. The compiler warns you because it cannot make sure all your locking is ordered—it's not smart enough to check your code, and smart enough to know there may be more.

An alternative solution could be locking on an enclosing object, e.g. for transfers within one user's account you could lock on user. Not so with transfers between users.

Having said that, you are not probably going to rely on Java locking in order to make a transfer: you need some data storage, usually a database. In case of using a database, the locking moves to the storage. Still, the same principles apply: you order locks to avoid deadlocks; you escalate locks to make locking simpler.

Zechariah

Answer 2

I personally prefer to avoid any but the most trivial synchronization scenario. In a case like yours I would probably use a synchronized queue collection to funnel deposits and withdraws into a single-threaded process that manipulates your unprotected variable. The "Fun" thing about these queues is when you put all the code into the object that you drop into the queue so the code pulling the object from the queue is absolutely trivial and generic (commandQueue.getNext().execute();)--yet the code being executed can be arbitrarily flexible or complex because it has an entire "Command" object for it's implementation--this is the kind of pattern that OO-style programming excels at.

This is a great general-purpose solution and can solve quite a few threading problems without explicit synchronization (synchronization still exists inside your queue but is usually minimal and deadlock-free, often only the "put" method needs to be synchronized at all, and that's internal).

Another solution to some threading problems is to ensure that every shared variable you might possibly write to can only be "Written" to by a single process, then you can generally leave off synchronization altogether (although you may need to scatter a few transients around)

Bootee

they should probably teach this technique first - have a single total order whenever possible. life is much simpler in that world. – Whereabouts

While it's usually a good idea to split consumers/producers, etc., in practice to get good scaling you'd want several consumers of the commandQueue and there we are again with locking :-) – Vulturine

@Vulturine I've done this--what you can do is tag each task with something that indicates the unsharable/scarce resources it wants, when something has already "Consumed" (is operating on) an unsharable resource and the next one in the queue wants that same resource you skip it and grab the next one up from the queue. Then the only "Synchronization" is, once more, simple, quick and contained within the queue structure. – Bootee

Interesting idea. Assuming that we scarcely get contention, this doesn't add much overhead (well in theory we get O(N) for get() + the additional lookups, but in practice that should be negligible) and seems simple enough. I fear you just gave me a hammer and I'll have to find a nail to test that solution in practice ;-) – Vulturine

If it became a problem (if many tasks potentially contended) you could break it up into multiple queues, each for a different resource (which would only work when each task only required a single resource). Another possibility would be to optimize the queue from the inside--but that logic gets trickier--it would be fun to mess with though. – Bootee

seems like this solution would lock all accounts while dealing with only two of them – Inge

Answer 3

I would advise you to look into Lock Objects in java. Have a look at condition objects too. Each of your account object can expose a condition on which a thread waits. Once a transaction is complete, condition objects await or notify is called.

Cult

Answer 4

If you haven't already you may want to look at the more advanced locking packages in java.util.concurrent.

While you still have to take care to avoid with deadlock, the ReadWriteLocks in particular are useful to allow multi-thread read access while still locking for object modification.

Pejoration

Answer 5

Make this easy with Polyglot programming, use Software Transactional Memory with Clojure but in Java.

Software Transactional Memory (STM) is a concurrency control technique analogous to database transactions for controlling access to shared memory in concurrent computing. It is an alternative to lock based synchronization.

Example solution

Account.java

import clojure.lang.Ref;

public class Account {
    private Ref mBalance;

    public Account() {
        mBalance = new Ref(0);
    }

    public void withdraw(int value) {
        mBalance.set(getBalance() - value);
    }

    public void deposit(int value) {
        mBalance.set(getBalance() + value);
    }

    private int getBalance() {
        return (int) mBalance.deref();
    }
}

Bank.java

import clojure.lang.LockingTransaction;

import java.util.*
import java.util.concurrent.Callable;

public class Bank {
    private List<Account> mAccounts;
    private int mSlots;

    public Bank(int slots) {
        mAccounts = new ArrayList<>(Collections.nCopies(slots, new Account()));
        mSlots = slots;
    }

    public void transfer(int fromId, int toId, int value) {
        try {
            LockingTransaction.runInTransaction(
                    new Callable() {
                        @Override
                        public Object call() throws Exception {
                            mAccounts.get(fromId).withdraw(value);
                            mAccounts.get(toId).deposit(value);
                            return null;
                        }
                    });
        } catch (Exception e) {
            e.printStackTrace();
        }

    }
}

Dependencies

<dependency>
    <groupId>org.clojure</groupId>
    <artifactId>clojure</artifactId>
    <version>1.6.0</version>
</dependency>

Embowel