Deep C# - avoiding race conditions

This article was originally published in VSJ, which is now part of Developer Fusion.

You are probably coming under pressure to make your applications more responsive and to make them multi-core aware. The solution is, of course, very simple – just use threads. The downside is that with the solution comes a problem. Most of the code you will encounter isn’t “threadsafe” and this includes most of the objects in the .NET class library and of course your own code.

We often use the term threadsafe without really bothering to define what it actually means – as if using it often enough would make its meaning obvious. Basically a block of code, or an object, is threadsafe if it works correctly and as desired if multiple threads make use of it at the same time. Now the important thing to realise is that most code isn’t threadsafe unless you take steps to make it so. What exactly is the problem? There is the obvious confusion caused by threads sharing the same data. For example, if a method has a counter then another thread starting the same method might well zero that counter and leave it in a state that is not as the first thread left it. For example, consider the following code:

public int count;
public void A()
{
    for (int i = 0; i < 9999999; i++)
    {
    	count++;
    }
}
public void B()
{
    count = 0;
}

count = 0;
Thread T1 = new Thread(A);
Thread T2 = new Thread(B);
T1.Start();
T2.Start();
T1.Join();
T2.Join();
textBox1.Text = count.ToString();

Function A adds one to count in a loop and function B zeros the same variable. These are run as two independent threads and the main thread waits until they have completed using the Thread.Join method. If you run this program then you will discover that the final value of count isn’t predictable because it all depends on when the two threads get access to count. Is this threadsafe coding? In a sense it might be if the idea is to keep a count since the last zeroing by function B. In a deeper sense it isn’t threadsafe because access to the global resource, i.e. count, isn’t controlled. This means that function A could be interrupted in the middle of incrementing count with the result that an erroneous value is stored back in count when its thread resumes. In this case the incrementation is such a fast operation that the chance of being interrupted is low but we can change this by stretching out the operation a little:

public void A()
{
    for (int i = 0; i < 9999999; i++)
    {
    	int temp=count+1;
    	if (temp != count + 1)
    	{
    		return;
    	}
    	count = temp;
}

In this case a temporary variable is used to store the increment and an if statement checks that logically the incremented value is one more than the old count value. If you run this code with a breakpoint on the return instruction then you should find that about one in six runs results in temp and count+1 being different. This is the sort of problem that threadsafe code is designed to avoid. Notice that as this sort of threading error can have a low probability of occurring it’s possible for it to go unnoticed for many, many runs of the program and look to all intents and purposes like some sort of random hardware failure. It is this that makes multi-threaded programs very difficult to debug.

Methods to make a thread safe

There are three general approaches to making code threadsafe:

1. Write re-entrant code

If you only use local variables stored on the stack then restarting the function with another thread automatically saves the state of any original invocation. Restricting storage to the stack isn’t always easy so .NET also provides thread-local storage which ensures that each thread has its own private copy of any variables it used. Re-entrant code is a good approach if you need a function that can be used by multiple threads to do a task, but it forbids any sharing of resources which would render the code non-re-entrant.

2. Access control

This is a very general approach and it works by allowing only one thread to access a resource at a time. There are lots of facilities provided within .NET to allow you to implement mutual exclusion and more complicated access methods. The big problem with access control is knowing when a resource is in use by a thread and when it is free. Access control also brings with it problems connected with what happens when a thread wants to use a resource which is locked.

3. Atomic operations

An atomic operation is one that cannot be interrupted by a change of thread. That is, once started an atomic operation will complete without yielding to another thread. In general which operations are atomic is defined by the hardware so this isn’t a particularly stable multiplatform solution. However it is one of the easiest of approaches to thread safety.

Atomic operations and volatility

Before moving onto more sophisticated ideas let’s consider some of the issues of low level data access. The .NET CLR guarantees that all native integer operations are atomic in the sense that these cannot be interrupted by a task swap in mid operation. This avoids the problem of a variable being changed by another thread in the middle of an operation so resulting in invalid or inconsistent data. The problem with this definition is that the native integer size varies according to machine type. So, is:

count++

…an atomic operation? It all depends on the machine it is run on. If you want to be sure an operation is atomic then use the operations provided by the Interlocked class. For example,

Interlocked.Increment(count);

…will add one to count without any risk that the process will be interrupted by another thread using a similar Interlocked operation. Notice that it can potentially be interrupted by standard non-interlocked operation. For this approach to work all of the threads have to use nothing but Interlocked operations to access shared resources. The advantage of Interlocked is simplicity; its disadvantage is that it is limited to the methods provided. In most cases it is much better to use a lock based on a Monitor, as described later.

There is another strange problem associated with the way a variable changes its state or not. During a non-atomic operation a variable might change its state due to another thread. However, it is possible that the compiler and or machine architecture may make the assumption that a variable can’t change if the current thread doesn’t change it. This allows variables to be cached in fast memory but the cached copy may not reflect the true value of the variable stored in main memory. In practice this problem doesn’t happen at all often but you can declare a variable as volatile if you need the compiler to check that it hasn’t been changed by another thread. In practice it usually isn’t necessary to use volatile as, once again, if you use a lock it performs a volatile read at the start and a volatile write at the end making sure everything is up-to-date.

Re-entrant code

Re-entrant code can be executed concurrently because each time it is run essentially a new copy of everything it uses is automatically created. Re-entrancy is the key idea in functional programming (see Why F#?) where it is the norm, but in most languages you have to put in some work to achieve it. In C# you can create a re-entrant function in a number of ways, but essentially you have to avoid using global non-constant data.

To convert our two example functions to be re-entrant all we have to do is remove the use of the global variable count. Once defined as local to each function the variables are allocated on the stack and hence local to each thread as each thread has its own stack. Of course this means that the two functions cannot interact with each other, but this is in the nature of re-entrant functions.

Consider now the possibility that a class wants to be re-entrant, i.e. have nothing but re-entrant methods. This is fine as long as it doesn’t make use of global or static variables. A static variable is just a special case of a global variable, i.e. it’s global to all instances of the class. If you still want your class to be re-entrant then you have no choice but to use thread-local storage. The simplest way of doing this is to use the [ThreadStatic] attribute. For example to make the public count variable in the previous example thread-local we simply have to change its declaration to:

[ThreadStatic] static public int count;

Notice that now it’s also a static variable shared by all instances of the class, but it isn’t shared by different threads executing methods in the same or different instances of the class. The [ThreadStatic] attribute is the most efficient way of creating thread-local storage. You can also do it the hard way using named or unnamed data slots but you need to keep in mind that there are less efficient and only slightly more useful. In this case you have to allocate the storage yourself and use special storage and retrieval functions. The details are straightforward and documented under Thread.AllocateDataSlot and associated methods. Now it’s time to move on to a much bigger and more important topic – exclusion.

Exclusion

In principle exclusion is simple to implement. All you need is a flag that a thread can test to see if the resource is in use. If it is then the thread should wait, forming a queue if needs be, until the resource is free as indicated by the flag. In practice implementing the flag so that nothing goes wrong is difficult in the extreme. If you simply use a Boolean as a flag, for example, consider what happens when two threads test it at more or less the same time to discover that it is set to false and both proceed to set it to true and use the resource it guards. Not only do you now have two threads using the resource, when one of them has finished it will set the flag back to false and allow other threads to use the resource.

.NET provides a great many different locking facilities – so many that it’s very confusing. Part of the reason for this excess is that the theory of locking has been developed by many different people who each invented their own favourite way of doing the job. Let’s start with the simplest and most useful locking mechanism – the monitor, invented by Per Brinch Hansen in 1972. Every object in .NET has a monitor associated with it. A thread can acquire or enter the monitor only if no other thread has already acquired it. If it can’t acquire the monitor it simply waits, in a queue of other threads trying to acquire the same monitor, until the monitor is available. When the thread that has the monitor is finished it has to explicitly exit or release the monitor. Of course the monitor is implemented in such a way that the sort of problems described with simple locking on a flag cannot happen – acquiring a monitor is an atomic operation – however there are other things that can go wrong as we will see.

The first big problem that confronts any programmer wanting to use a monitor is which object to use for locking. Remember every object has a monitor and so can provide a unique lock restricting access to a resource. At this point you need to focus on the fact that in many ways it is the code which accesses the resource which is locked and not the resource. That is, suppose we have a block of code that manipulates a global variable. We clearly don’t want this code to be active on more than one thread at a time so we acquire the lock at the start of the code and release it at the end of the block. If there are multiple different blocks of code that access the same resource then each of these blocks have to be written to acquire the lock at the start of the code and release it at the end. You can now see that whatever object you use to provide the lock it has to be accessible to all of the blocks of code that need to use it. The object that you lock on also has to be a fairly obvious one for the job and it shouldn’t be used, by accident, by another block of code to restrict access to another resource. There is a great deal of custom and practice in which objects should be used. For example, it is often said that you should lock on this for instance methods and a type object for static methods. The logic is that each instance method will only access resources that belong to that instance and so thread locking only has to be specific to that instance. However, a static method is common to all instances and hence likely to need locking so that one thread can only access it at a time irrespective of which instance it is called from. These conventions have some sense but an equally good, and some might argue better, approach is to create and use objects specifically to be used to lock a resource. Let’s see how this works.

First we need an object to use as a lock:

static readonly object
    MyCountLock=new object();

As we don’t want multiple copies of the lock it should be static and as we don’t want anyone to change it – readonly. To make use of it we have to modify the count method quoted earlier to read:

public void A()
{
    for (int i = 0; i < 99; i++)
    {
    	Monitor.Enter(MyCountLock);
    	int temp=count+1;
    	Thread.Sleep(2);
    	if (temp != count + 1)
    	{
    		return;
    	}
    	count = temp;
    	Monitor.Exit(MyCountLock);
    }
}

The calls to the static Monitor object acquire and release the lock using our object. To try this out we need a main program:

count = 0;
Thread T1 = new Thread(A);
Thread T2 = new Thread(A);

T1.Start();
T2.Start();
T1.Join();
T2.Join();
textBox1.Text += count.ToString();

If you place a breakpoint on the return you will see that the update is performed in an orderly fashion in the sense that neither thread interrupts the other during the update. If you comment out the calls to the monitor then you will immediately see that the two threads do interfere with one another.

If you don’t want to use a specially created object then you can use the more commonly encountered lock on this:

Monitor.Enter(this);
int temp=count+1;
Thread.Sleep(2);
if (temp != count + 1)
{
    return;
}
count = temp;
Monitor.Exit(this);

The lock using the current instance works equally well, but imagine what would happen if the monitor was protecting a resource shared by multiple instances of the class. The result would be messy to say the least as each instance would obey the lock but threads from different instances would access it at the same time. Similarly a lock on this isn’t very useful for controlling access from different objects. Another problem with locking on the current instance is that you might well forget that it is being used to protect a particular resource and accidentally use it to protect another completely unconnected resource. This would result in a thread accessing resource one, unnecessarily blocking all access to resource two.

In many ways it is better to create an object specifically to be used to lock a particular resource and include the name of the resource in the name of the lock. Don’t make the common mistake of using a string or a value “object” to lock because there are pitfalls in using both. The string might well end up being shared due to optimisation and the value “object” would be boxed and unboxed each time it was used -making the lock useless.

Another potential problem with using the Monitor in the way described is that if the code crashes while it has a lock then the lock never gets released. Similarly you could accidentally forget to release the lock or attempt to release the lock on the wrong object. You can avoid the problem of a crash by wrapping the code in a Try-Catch clause but it’s much easier to use the equivalent lock statement (synclock in VB). That is:

lock(object){list of instructions}
…is equivalent to:
try{
    Monitor.Enter(object);
    list of instructions
}
finally{Monitor.Exit(object);

In other words, lock will try to obtain a lock using the specified object before executing the list of instructions within a try. No matter what happens you can be sure that the lock will be released so that other threads can use the resource. For example, the previous code can be written in a more robust way as:

lock(this)
{
    int temp=count+1;
    Thread.Sleep(2);
    if (temp != count + 1)
    {
    	return;
    }
    count = temp;
};

Notice that while this is rather more foolproof than using the basic Monitor methods a thread that doesn’t play by the rules and simply accesses the resource will spoil everything. The point is that you can’t enforce locking, just hope that everyone remembers to use it.

There are other Monitor methods that are sometimes useful. For example the TryEnter method will attempt to acquire a lock, after waiting for a specified time, but will allow the thread to continue if the lock cannot be acquired. Clearly in this case you need to test the return value (a Boolean) to see if the lock has been acquired and do something different if it hasn’t. The Wait method will allow the thread that currently has the lock to free it and allow other threads to acquire it while it waits for it to be signalled by another thread attempting to acquire the lock again. Another thread, one that currently has the lock, can signal to the next waiting thread (or to all waiting threads) to try to acquire the lock by using the pulse or pulseall method.

To understand how this might be used consider a thread that processes a buffer that is filled by another thread. The processing thread can call wait when it has finished processing the buffer and allow the filling thread to access it. As soon as the filling thread has finished its work it can use pulse to tell the processing thread to try to acquire the lock and start work again. The clever part is that this mechanism generalises to multiple work-creating and work-consuming threads and they can all queue in an orderly fashion to access the resource using wait and pulse.

Deadlock

There are other problems with locking and the most celebrated is perhaps the deadlock condition. Put simply, if thread A locks resource one and thread B locks resource two everything is fine unless thread A also wants a lock on resource two before it can complete and if thread B needs a lock on resource one before it can complete. The result is that both threads spend forever waiting for the other to finish and release the resource. This is deadlock and it can occur in much more complicated ways than this simple “A waits for B which waits for A” situation. It is possible to create a deadlock ring of dependency by having A wait for B, which waits for C, which waits for D which is waiting for A. There isn’t much you can do about deadlock except to be aware of it and design your access strategies with a great deal of care. You can try to avoid locking threads on more than one lock at a time but this can slow things down to unacceptable levels as threads have to wait while another thread acquires an oversized lock on resources, some of which it isn’t actually using. A better strategy is to attempt to acquire all of the locks that a thread needs to complete at the start and release any that have been acquired if it isn’t possible to acquire them all. Again this can result in a loss of performance.

The bottom line is that multi-threading with locks isn’t easy and carries the seeds of disaster. Multithreading without locks is easy but is always guaranteed to be a disaster.

You can do most of what you need to with nothing but the Monitor, but .NET does provide other locking facilities. For example the Mutex provides locking across process boundaries and the Semaphore can be used to control the number of threads that can access a resource. All of these work in similar ways to the Monitor and you should have no problems in understanding how they work – but if the Monitor does the job then use it.

You might also like...

Comments

Contribute

Why not write for us? Or you could submit an event or a user group in your area. Alternatively just tell us what you think!

Our tools

We've got automatic conversion tools to convert C# to VB.NET, VB.NET to C#. Also you can compress javascript and compress css and generate sql connection strings.

“Debugging is twice as hard as writing the code in the first place. Therefore, if you write the code as cleverly as possible, you are, by definition, not smart enough to debug it.” - Brian Kernighan