Threading with shared mutable state is hard

Earlier today I saw this post about implementing locks with a timeout which claimed to have a thread-safe implementation of a simple in-memory bank account object. There were a lot of errors in the post, and the reasoning is too complex to leave in a comment, so this blog post aims to point out some of the flaws and provide solutions.

For reference, here is the class with some minor superficial changes to remove the code unrelated to the threading issues (the comment is left in from the original blog post):

public class Account
{
    private double balance;

    public Account(double amount)
    {
        this.balance = amount;
    }

    public double Balance
    {
        get { return this.balance; }
        set { this.balance = value; }
    }

    public void Deposit(double amount)
    {
        Interlocked.Exchange(ref this.balance, this.balance + amount);
    }

    public void Withdraw(double amount)
    {
        Interlocked.Exchange(ref this.balance, this.balance - amount);
    }

    public static void Transfer(double amount, Account fromAccount, Account toAccount)
    {
        // Bad code here. Potential deadlock.
        lock (fromAccount)
        lock (toAccount)
        {
            fromAccount.Withdraw(amount);
            toAccount.Deposit(amount);
        }
    }
}

Leaving aside the glaring issue that you should use decimals for anything financial rather than double, let’s focus only on the threading problems, starting with the Deposit and Withdraw methods, of which the original blog post claims:

Deposit and Withdraw methods are thread safe. They both uses Interlocked class which is has low level methods to modify values.

Unfortunately these methods are not actually thread safe. The use of Interlocked makes it appear to the casual observer that they are, but there are two problems with these methods. Firstly they perform a non-volatile read of the balance so the value read here is not necessarily the current value due to potential caching optimisations. Secondly, the balance may be updated between when the value is read from memory and when the Interlocked.Exchange method operates on the value, so an update made at the same time on a different thread may be overwritten.

To fix these we need to perform a volatile read of the balance to ensure we are operating on the latest value, and use the Interlocked.CompareExchange method to ensure that we’re really updating the value of the balance we think we are (note here it would be nice to be able to declare the balance field as volatile, but this modifier cannot be used on doubles). A truly thread-safe lock-free implementation of Withdraw is as follows, which loops until it updates a balance that has the same value as it previously read:

public void Withdraw(double amount)
{
    double b;
    do
    {
        b = Thread.VolatileRead(ref this.balance);
    }
    while (Interlocked.CompareExchange(ref this.balance, b - amount, b) != b);
}

Now let’s move onto the Transfer method, of which the original post says (correctly):

Transfer is not thread safe even though it uses locks. There is a potential deadlock if two thread transfer funds using the same accounts at the same time.

The remainder of the post goes on to explain an implementation of locking using the Monitor.TryEnter method with a timeout to avoid (or at least work around) the potential deadlock. Which would be fine apart from one thing: putting locks on the accounts in the transfer method doesn’t actually achieve anything!

By adding the locks it ensures there is only one transfer happening at a time, but because nothing else uses the same locks it doesn’t prevent the balance being set directly, or the Deposit or Withdraw methods being called to change it. In addition, if the call to Deposit fails after the call to Withdraw has already been made, the balance of the source account is still decreased even though the money has not gone anywhere. Locks do not give you transactions!

This problem isn’t actually an easy one to solve in code with the current C# language and .NET platform – what we really need is software transactional memory which would allow both calls to be made as an atomic operation, and then if the second one failed the first one would be rolled back. Unfortunately I think this is still quite a long way off, but fortunately this type of operation is typically done against a database where somebody else has already done the hard work of implementing a transaction manager for us.

I hope this post doesn’t come across as me picking on the author of the original post – that certainly isn’t my intent – I just wanted to highlight the issues in it, and make the point that even when you’re really thinking about threading it’s very easy to get it wrong. Threading with mutable state is hard.