Immutability and synchronization in Java

Question

Since I've read the book Java Concurrency in Practice I was wondering how I could use immutability to simplify synchronization problems between threads.

I perfectly understand that an immutable object is thread-safe. Its state cannot change after initialization, so there cannot be "shared mutable states" at all. But immutable object have to be use properly to be considered useful in synchronization problems.

Take for example this piece of code, that describes a bank wich owns many accounts and that exposes a method through which we can transfer money among accounts.

public class Bank {

    public static final int NUMBER_OF_ACCOUNT = 100;

    private double[] accounts = new double[NUMBER_OF_ACCOUNT];

    private Lock lock;
    private Condition sufficientFunds;

    public Bank(double total) {
        double singleAmount = total / 100D;
        for (int i = 0; i < NUMBER_OF_ACCOUNT; i++) {
            accounts[i] = singleAmount;
        }
        lock = new ReentrantLock();
        sufficientFunds = lock.newCondition();
    }

    private double getAdditionalAmount(double amount) throws InterruptedException {
        Thread.sleep(1000);
        return amount * 0.04D;
    }

    public void transfer(int from, int to, double amount) {
        try {
            // Not synchronized operation
            double additionalAmount = getAdditionalAmount(amount);
            // Acquiring lock
            lock.lock();
            // Verifying condition
            while (amount + additionalAmount > accounts[from]) {
                sufficientFunds.await();
            }
            // Transferring funds
            accounts[from] -= amount + additionalAmount;
            accounts[to] += amount + additionalAmount;
            // Signaling that something has changed
            sufficientFunds.signalAll();
        } catch (InterruptedException e) {
            e.printStackTrace();
        } finally {
            lock.unlock();
        }
   }   

   public double getTotal() {
       double total = 0.0D;
       lock.lock();
       try {
           for (int i = 0; i < NUMBER_OF_ACCOUNT; i++) {
               total += accounts[i];
           }
       } finally {
           lock.unlock();
       } 
       return total;
    }

    public static void main(String[] args) {
        Bank bank = new Bank(100000D);

        for (int i = 0; i < 1000; i++) {
            new Thread(new TransferRunnable(bank)).start();
        }
    }
}

In the above example, that comes from the book Core Java Volume I, it is used synchronization through explicit locks. The code is clearly difficult to read and error prone.

How can we use immutability to simplify the above code? I've tried to create an immutable Accounts class to hold the accounts value, giving to the Bank class a volatile instance of Accounts. However I've not reach my goal.

Can anybody explain me if it is possible to simplify synchronization using immutability?

---EDIT---

Probably I did not explain myself well. I know that an immutable object cannot change its state once it was created. And I know that for the rules implemented in the Java Memory Model (JSR-133), immutable objects are guaranteed to be seen fully constructed after their initialization (with some distingua).

Then I've try to use these concepts to delete explicit synchronization from the Bank class. I developed this immutable Accounts class:

class Accounts {
    private final List<Double> accounts;

    public Accounts(List<Double> accounts) {
        this.accounts = new CopyOnWriteArrayList<>(accounts);
    }

    public Accounts(Accounts accounts, int from, int to, double amount) {
        this(accounts.getList());
        this.accounts.set(from, -amount);
        this.accounts.set(to, amount);
    }

    public double get(int account) {
        return this.accounts.get(account);
    }

    private List<Double> getList() {
        return this.accounts;
    }
}

The accounts attribute of the Bank class have to be published using a volatile variable:

private volatile Accounts accounts;

Clearly, the transfer method of the Bank class will be changed accordingly:

public void transfer(int from, int to, double amount) {
    this.accounts = new Accounts(this.accounts, from, to, amount);
}

Using an immutable object (Accounts) to store the state of a class (Bank) should be a publishing pattern, that is described at paragraph 3.4.2 of the book JCIP.

However, there is still a race condition somewhere and I can't figure out where (and why!!!).

Answer 1

Your Account values are inherently mutable (a bank account with an immutable balance isn't very useful), however you can reduce the complexity by encapsulating the mutable state using something like the Actor Model. Your Account class implements Runnable, and each Account object is responsible for updating its value.

public class Bank {
    // use a ConcurrentMap so that all threads will see updates to it
    private final ConcurrentMap<Integer, Account> accounts;
    private final ExecutorService executor = Executors.newCachedThreadPool();

    public void newAccount(int acctNumber) {
        Account newAcct = new Account();
        executor.execute(newAcct);
        accounts.put(acctNumber, newAcct);
    }

    public void transfer(int from, int to, double amount) {
        Account fromAcct = accounts.get(from);
        Account toAcct = accounts.get(to);
        if(fromAcct == null || toAcct == null) throw new IllegalArgumentException();
        fromAcct.transfer(amount, toAcct);
    }
}

public interface Message {
    public double getAmount();
}

public class Transfer implements Message {
    // initialize in constructor, implement getters
    private final double amount;
    private final Account toAcct;
}

public class Credit implements Message {
    // initialize in constructor, implement getters
    private final double amount;
}

public class Account implements Runnable {
    private volatile double value;
    private final BlockingQueue<Message> queue = new ArrayBlockingQueue<>(8);

    public void transfer(double amount, Account toAcct) {
        queue.put(new Transfer(amount, toAcct));
    }

    public void credit(double amount) {
        queue.put(new Credit(amount));
    }

    public void run() {
        try {
            while(true) {
                Message message = queue.take();
                if(message instanceof Transfer) {
                    Transfer transfer = (Transfer)message;
                    if(value >= transfer.getAmount()) {
                        value -= transfer.getAmount();
                        transfer.getToAcct().credit(transfer.getAmount());
                    } else { /* log failure */ }
                } else if(message instanceof Credit) {
                    value += message.getAmount();
                } else { /* log unrecognized message */ }
            }
        } catch(InterruptedException e) {
            return;
        }
    }
}

The Account#transfer and Account#credit methods can be safely called from any thread because the BlockingQueue is thread-safe. The value field is only modified from within the account's run method and so there's no risk of concurrent modification; the value needs to be volatile so that updates are visible to all threads (you're using a ThreadPoolExecutor to execute all of the Accounts so there's no guarantee that an Account's run method will execute on the same Thread every time).

You should also log the transfer in the Bank class before executing it so that you can recover from a system failure - if the server crashes after the from account is debited but before the to account is credited then you'll need a way to reestablish consistency after the server comes back up.