Threading: Locking and Deadlocks Introduced

Reading Time: 4 minutes

So in this article on thread safety I finally get to talk about locking. Why has it taken me until article 3 to talk about this? Well, it’s not quite as straightforward as it first appears. Firstly there’s more than one type of lock. Secondly, there are hazards and pitfalls. Picking the wrong locking strategy, or implementing it badly can cripple performance rather than improving it. Then there’s the deadlock, it’s positively evil twin the compound deadlock and I’ll not even mention deadlocks that also involve message passing.

But before I start complicating matters with tales of horror, let’s take it right back to basics. In the examples from article 1 (C#, VS2008), in the not thread safe project there’s a comment to the effect that, to make the program thread safe, all one has to do is uncomment a lock statement.

        public static void DoAddition(object obj)
        {
            int tempVal;
            Thread.Sleep(rand.Next(10));

            /*
             * All you have to do to make this thread safe is uncomment this lock statement
             * Try it!
             */
            //lock (threads)
            {
                tempVal = accumulator;

                //wastes some time simulating a complex calculation
                for (double f = double.MaxValue; f > double.Epsilon; f *= 0.5f) ;

                accumulator = tempVal + 1;
            }
        }

The C# lock statement is a great example of a simple mutual exclusion lock. What we’re saying with the lock statement is to take a named variable, in this case threads and apply a mutual exclusion lock to it. This lock is in place whilst the code in the block (between the curly braces) is running and ends when we leave that block. What is the effect of this? Well, it means that if another thread tries to place a lock on the same variable (e.g. threads) whilst we’re executing the code block, it will have to wait until the our code block has finished.

If we revisit our example from the first article where we managed to accidentally declare our love to Dave, but this time use a lock, we can see the effect. The first thread locks msg, the second thread attempts to jump in and use msg whilst the first is still working with it. But when it tries to “acquire the lock” it can’t and has to wait until the first thread has finished and “releases the lock”. It’s worth noting that if a third thread jumped in, it would also have to wait.

Diagram of a simple mutex operation — The lock statement saves the day

Remember though that there’s no psychic element to the lock statement, or mutexes in most languages. Let’s look at a producer / consume example.

Queue<WorkItem> workQueue=new Queue<WorkItem>();

...

void processQueue()
{
    bool weNeedToProcess = true;
    do
    {
        WorkItem itemToProcess;
        lock(workQueue)
        {
            weNeedToProcess = workQueue.Any();
            if(weNeedToProcess)
                itemToProcess = workQueue.Dequeue();
            else
                itemToProcess = null;
        }
        if(null != itemToProcess)
        {
             do some things...
        }
    }while(weNeedToProcess);
}

...

void someMethod()
{
    //we need to queue a workItem
    WorkItem newWorkItem = new WorkItem(someTask);
    workQueue.Add(newWorkItem);
}

The processQueue method runs in a background thread processing items of work which are put on the queue by other threads. The problem though, is that in someMethod was have forgotten to lock workQueue which means that it’s not thread safe. When we add an item to the queue, processQueue could be in the middle of taking an item off the queue and all sorts of things could go wrong.

Fixing this is easy…

void someMethod()
{
    //we need to queue a workItem
    WorkItem newWorkItem = new WorkItem(someTask);
    lock(workQueue)
    {
        workQueue.Add(newWorkItem);
    }
}

So that’s one danger. Now let me introduce on the Great Satan of all multithreading, the deadlock. It’s really quite easy to explain a simple deadlock, thread a needs a lock that thread b has got at the same time as thread b needs a lock that thread a has got. Let’s go back to our savings account and current (or checking) account scenario.

BankAccount currentAccount;
BankAccount savingsaccount;

void moveFromSavingsToCurrent(int amount)
{
    //we need to work with savings, so lock it
    lock(savingsAccount)
    {
        if(savingsAccount.Total>amount)
        {
            //we can proceed, but we don't want any inconsistencies so we now need
            //to lock currentAccount
            lock(currentAccount)
            {
                savingsAccount -= amount;
                currentAccount += amount;
            }
        }
    }
}

void moveFromCurrentToSavings(int amount)
{
    //we need to work with current, so lock it
    lock(currentAccount)
    {
        if(currentAccount.Total>amount)
        {
            //we can proceed, but we don't want any inconsistencies so we now need
            //to lock savingsAccount
            lock(savingsAccount)
            {
                currentAccount -= amount;
                savingsAccount += amount;
            }
        }
    }
}

This will cause any experienced multithreaded programmer to scream in horror. Why?
Let’s say an instance of moveFromSavingsToCurrent and moveFromCurrentToSavings are run simultaneously and they interleave like this…

moveFromSavingsToCurrent acquires the lock on savingsAccount
Meanwhile, moveFromCurrentToSavings acquires the lock on currentAccount
moveFromSavingsToCurrent asks for the lock on currentAccount, but has to wait until the thread running moveFromCurrentToSavings has finished with it.
moveFromCurrentToSavings asks for the lock on savingsAccount, but has to wait until the thread running moveFromSavingsToCurrent has finished with it.

moveFromSavingsToCurrent can’t continue until moveFromCurrentToSavings releases the lock on currentAccount. The problem is that moveFromCurrentToSavings can’t progress and therefore can’t release its lock on currentAccount because it’s waiting for access to savingsAccount, which moveFromSavingsToCurrent has. These two threads will sit there doing nothing until they’re killed. That will probably be the end of your application, when the user finally gets irritated enough to forcibly close it.

Let’s have a go at diagramming that…