CLR Threads Via C# Part 3 – Race Conditions, Atomic Instructions With Interlocked, and Monitors

Part 3 of the CLR multi-threading series where I discuss shared resources, critical sections, race conditions, atomic instructions, the interlocked class and monitors.

Advertisements

In the last post, we discussed the thread pool, and in the post prior to that, we discussed the System.Threading.Thread class. In both of these posts, we’ve look at pretty trivial examples while drilling into each of these topics, which for our purposes is fine, but in more realistic scenarios, multi-threaded code isn’t so straightforward, there are things you need to be aware of, and there are tools at your disposal for helping address issues that can arise in multi-threaded code. One such tool is a monitor, a type of locking mechanism. We’ll look at this, and several other topics in this post.

Shared resources

The first thing that we need to understand but haven’t quite covered simply because we’ve had no need for understanding it, is a shared resource. In the context of multi-threaded code, a shared resource is a piece of a data that multiple threads can touch at the same time. As an example, if you had a method that your thread was executing, and that method modified the value of an integer, that integer is considered a shared resource because multiple threads will be modifying it’s value at the same time.

Race conditions

Race conditions are very often problematic in multi-threaded programming…but what is a race condition? Even if you know nothing about multi-threaded code, you’ve probably heard this term, along with locking and dead locking before. Race conditions describe a scenario where the timing of something can affect the outcome of something…too vague? Let’s look at an example. Say that you have a line of code as follows:

x++;

To a newer programmer, that’s one instruction, one line of code, so if two threads hit that line, most likely one will finish incrementing it, then the next thread will increment it. In reality, this is not the case. As threads get time with the CPU, they tell the processor which instructions they want to carry out, and this single line of code can be a few assembly instructions, not just one instruction. Compound that with the fact that a thread can be slept halfway through executing these instructions, etc. and you can quickly see a problem forming.

Let’s say we have two threads running this line of code, thread one gets time with the cpu, it reads the value of x from memory, let’s say it’s 0, and the task scheduler decides it’s time for that thread to be slept while thread 2 comes in and works. Well as it so happens, thread 2 is running the same line of code, so it reads from memory x’s current value, 0, carries out the next instructions to increment the variable, and finishes up. The value of x is now 1 and thread 1 wakes up to finish up it’s task, which presently is adding 1 and storing the result in x. Since thread 1 already read x’s value from memory, it uses the value it had on hand, 0, and increments this to 1, and stores that value back into memory. Because these two threads were allowed uncontrolled access to a shared resource, a race condition has occurred causing the value of x to be 1 instead of 2. This is a small bug, but imagine that there were 8 threads working here, and thread 1 does the first increment, but gets slept and the next 7 threads carry out the increment without issue, leaving us with a value of 7, well when thread 1 wakes up, it still has 0 on hand, and so when it stores it’s incremented value of x, it’s going to overwrite the 7 and make it a 1, this is a much more dramatic bug, and one that isn’t so far fetched.

Thread safety

So we understand shared resources, and we hopefully understand race conditions (if I did a bad job explaining, Google is your friend), so now we can talk about thread safety. Thread safety refers to whether a piece of code would be stable and safe to have multiple threads work on. A piece of code that uses multiple threads is considered “thread safe” whenever shared resources being accessed by multiple threads have no race conditions present, if a race condition can occur, then the code is considered to not be thread safe. That said, there are certainly instances where you may not care about thread safety (though I can’t think of one off the top of my head), but for any cases I can think of, you’ll want thread safety.

Atomic Updates

I’m no assembly expert, so if I butcher any of this, please be gentle (but feel free to correct me). Nowadays, most processors support what’s know as atomic updates of word sized data. A word in terms of a processor is a piece of data that is the size of the processors register, ex: 64 bit processor = 64 bit word size, 32 bit = 32 bit word size. Atomic operations are a thing where whenever a thread is doing an atomic operation, other threads see it as happening simultaneously. This is great because it avoids the need for locks and they are a fair bit faster than locks, but the disadvantage is they only have limited functionality so not all problems can be solved with atomic updates.

Interlocked Increment

The CLR provides a suite of atomic update methods in the Interlocked class. I will demonstrate our increment issue I previously described to show you a race condition, and then how Interlocked.Increment can help address this issue. To setup the problem, I’ve written some code (albeit very stupid code) to demonstrate a race condition:

        // Member variable in the program class
        public static int runningCount = 0;

        // Methods for incrementing
        public static void NonInterlockedIncrement()
        {
            int temp = runningCount;
            temp++;
            Thread.Sleep(1);
            runningCount = temp;
            Console.WriteLine(runningCount);
        }

        public static void InterlockedIncrement()
        {
            Interlocked.Increment(ref runningCount);
            Console.WriteLine(runningCount);
        }

        /// INSIDE OF MAIN ///
        for(int i = 0; i < 10; i++)
        {
            Thread thread = new Thread(() => NonInterlockedIncrement());
            thread.Start();
        }

Note that though I’ll be showing thread safe code, it’s still running in random order, that’s because the threads will finish execution in random order because we’ve not implemented any synchronization mechanism, but that’s not what I want to demonstrate here so I didn’t take the time to worry about it. All I want to show is a race condition, so if you run this code, your output should be total garbage, mine is as follows:

1
1
1
1
1
1
2
2
3
4

So this is pretty obviously a serious bug, but to be fair I really wrote this code to fail, I purposely stored the result of the increment in a temporary variable and slept the thread before the temporary variable was assigned to the running count, that way other threads could work and modify the value of the running count before the thread woke up to finish it’s work, but this demonstrates a race condition. Now, let’s use the interlocked variation of our increment method to show how it addresses this problem:

            for(int i = 0; i < 10; i++)
            {
                Thread thread = new Thread(() => InterlockedIncrement());
                thread.Start();
            }

The output I get now is as follows:

1
2
3
5
4
6
8
7
9
10

This was the output from one run, but the output is sometimes out of order because we aren’t doing any locking to keep the order of execution synced, the point is that this addresses the race condition, if we look at the value of runningCount, even when the order of execution is out of order, the count is still 10, because interlocked uses atomic updates.

Monitors

Now let’s talk about monitors. Monitors in C# are a locking mechanism that allows you to synchronize threads wanting to work on a portion of code that needs to be kept in sync. Portions of code that need to be executed in sync are known oftentimes as critical sections. Monitors use objects as locks for a portion of code, so when using a monitor, you tell it an object that you wish to use as a key, a thread is given the key, and then when that thread finishes it relinquishes ownership of the key and the next thread is free to proceed.

Before we look at an example of a lock, let’s drill into the lock class and see what we find. First off, notice that the monitor class is implemented as a static class with static methods, so we need only use the class name to access the features of the monitor class. the entirety of the Monitor class is as follows:

public static void Enter(object obj);
public static void Enter(object obj, ref bool lockTaken);
public static void Exit(object obj);
public static bool IsEntered(object obj);
public static void Pulse(object obj);
public static void PulseAll(object obj);
public static bool TryEnter(object obj, TimeSpan timeout);
public static void TryEnter(object obj, int millisecondsTimeout, ref bool lockTaken);
public static void TryEnter(object obj, ref bool lockTaken);
public static bool TryEnter(object obj);
public static bool TryEnter(object obj, int millisecondsTimeout);
public static void TryEnter(object obj, TimeSpan timeout, ref bool lockTaken);
public static bool Wait(object obj, int millisecondsTimeout, bool exitContext);
public static bool Wait(object obj, TimeSpan timeout, bool exitContext);
public static bool Wait(object obj, int millisecondsTimeout);
public static bool Wait(object obj, TimeSpan timeout);
public static bool Wait(object obj);

This class is really pretty simple, it has an enter, exit, is entered, pulse, pulseall, tryenter, and wait method, that’s it, so we need only break apart what the key parts of this class art and what they do to understand monitors. First off, note that the Enter method takes an object, which represents the lock a thread carries. Next is the exit method, which again takes the lock object, which represents the lock to release. Next we’ve got IsEntered, which just tells you if a lock is owned by another thread or not, and then there’s Pulse and PulseAll, both of these notify threads that are waiting about changes to the lock objects state, one does it to a specific thread, one does it for all threads. After that there’s TryEnter which is basically a method that attempts to get the lock object, and if it fails it returns back false. Note that some variations take a reference to a boolean via ref, and some return a boolean value, as far as I know, whichever you use is purely preference. Wait is interesting, it pauses the thread with the lock and causes the thread to release ownership of the lock, and that thread will then sit in a wait state until it is able to reacquire the lock.

Okay, we’ve broken the class down, let’s actually put it to use:

            object myLock = new object();
            int runningCount = 0;
            int runningCountWithMonitor = 0;


            for (int i = 0; i < 20; i++)
            {
                Thread t = new Thread(() =>
                {
                    runningCount++;
                    Console.WriteLine(runningCount);
                });

                t.Start();
            }

            for (int i = 0; i < 20; i++)
            {
                Thread t = new Thread(() =>
                {
                    Monitor.Enter(myLock);
                    runningCountWithMonitor++;
                    Console.WriteLine(runningCountWithMonitor);
                    Monitor.Exit(myLock);
                });

                t.Start();
            }

This is really simple stuff, I’ve got two running counts, one for the non-synchronized increment of a running count, and then a running count for the monitor. The first for loop does basic multi-threaded incrementing via standard threads with no locking mechanism. The second for loop does the same thing, only it uses a monitor with a lock object. If you run this a few times, you’ll see that the first for loop will very often be in a slightly random order, and the second loop will always be in sequential order. This is because the second for loop uses a monitor, so whenever the thread starts, it takes ownership of the lock, and when the next thread goes to run, it requests ownership of the lock, but the lock is already owned by another thread so it just sits around and waits until the lock is relinquished, and it then takes the lock and the cycle repeats, allowing this code to run in order.

Wrap up

Alright, this post is getting a bit lengthy, so I’ll probably talk some more about monitors in future posts but for now let’s just call this good. If you have any questions or corrections, feel free to reach out to me. Thanks for taking the time to read this, and until next time.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s

Advertisements
Advertisements
%d bloggers like this: