License Public Domain
Keywords
Mutex (2) Semaphore (1) Synchronization (2) Thread (4)
Permissions
Group Owner: .Net
Viewable by Everyone
Editable by Spencer Ruport
Hide
Writing an article is easy - try our reStructured Text demo Join Siafoo Now or Learn More

An introduction to threads, critical sections, and synchronization Atom Feed 3

With the days of the single cored processor drawing to a close and users demanding more robust user interfaces by the day, knowledge of multi-threaded programming techniques is quickly becoming a requirement of any competitive application developer.

If you've never worked with a multi-threaded application before, you might not see a problem with the following code.

# 's
 1class crashtest
2{
3 private const int thread_count = 30;
4 private const int thread_items = 1000;
5
6 private List<string> shared_data = new List<string>();
7 private List<Thread> threads = new List<Thread>();
8 bool begin = false;
9
10 public crashtest()
11 {
12 for (int i = 0; i < thread_count; i++)
13 threads.Add(new Thread(Work));
14 for (int i = 0; i < thread_count; i++)
15 threads[i].Start(i.ToString());
16
17 begin = true;
18
19 for (int i = 0; i < thread_count; i++)
20 threads[i].Join();
21
22 for (int i = 0; i < shared_data.Count; i++)
23 Console.WriteLine(shared_data[i]);
24 Console.WriteLine("Finished.");
25 Console.ReadKey();
26 }
27
28 private void Work(object param)
29 {
30 Thread.CurrentThread.Priority = ThreadPriority.Lowest;
31 while (!begin) Thread.Sleep(1);
32
33 string id = (string)param;
34 string data = "abc - " + id;
35 for (int i = 0; i < thread_items; i++)
36 shared_data.Add(data);
37 }
38}

The code compiles just fine, and depending on how lucky you are it might even execute properly once or twice. But, keep pressing your luck and sooner or later you'll receive an error. Eventually a context switch will happen at just the wrong moment resulting in an undesired behavior in your, or particularly in this example, Microsofts code. A context switch refers to the moment when CPU switches from one task to another. Consider the example two threads created to execute the following function.

# 's
1void WriteSomeStuff()
2{
3 Console.WriteLine("This is the first line of a thread.")
4 Console.WriteLine("This is the second line of a thread.");
5 Console.WriteLine("This is the third line of a thread.");
6}

Say the first thread executes line 1 and outputs:

# 's
1This is the first line of a thread.

Just afterwards a context switch occurs and the CPU begins working on the second thread and it completes all three lines of code. Now the output is:

# 's
1This is the first line of a thread.
2This is the first line of a thread.
3This is the second line of a thread.
4This is the third line of a thread.

The second thread completed, the CPU returns to the first thread and the final output becomes

# 's
1This is the first line of a thread.
2This is the first line of a thread.
3This is the second line of a thread.
4This is the third line of a thread.
5This is the second line of a thread.
6This is the third line of a thread.

It's important to note, context switches are expensive so it would be very unusual for two threads to be split up this way but simply for the sake of this example we're going to pretend they do. The main thing to remember is that a context switch can occur anywhere and hence you should always account for the possibility if you're writing a multi-threaded application. Which brings up something interesting about the Console.WriteLine() method. Keep in mind that it is not an atomic operation. (Meaning it can be broken up into pieces.) It's a method like any other and that it has several lines of code to execute and some of those lines call further methods that contain several more lines of code. The point being a context switch could potentially occur inside the Console.WriteLine() method itself. Were it not for the fact that the method is thread safe theoretically the result could have been something like.

# 's
1This is the fThis is the first line of a thread.
2irst line oThis is thf a the second liread.
3ne of This is the secoa thread.
4Tnd line of ahis is th thread.e third line of a thread.
5
6This is the third line of a thread.

However, the method uses mutual exclusion to ensure that no two calls overlap one another in it's critical section. A critical section is any portion of code that cannot be accessed by multiple threads if it is to function properly. So lets say you wanted your two threads to produce their outputs sequentially like so.

# 's
1This is the first line of a thread.
2This is the second line of a thread.
3This is the third line of a thread.
4This is the first line of a thread.
5This is the second line of a thread.
6This is the third line of a thread.

If you're already working on a solution as you're reading this article you may have considered the following.

# 's
 1     bool busyFlag = false;
2
3 // ...
4
5 void SomeThreadSafeFunction()
6 {
7 while (busyFlag) ; // Wait for other threads to finish
8 busyFlag = true; // Keep other threads out.
9
10 // Critical section
11 Console.WriteLine("This is the first line of a thread.")
12 Console.WriteLine("This is the second line of a thread.");
13 Console.WriteLine("This is the third line of a thread.");
14 // End critical section
15
16 busyFlag = false; // Let other threads in.
17}

While this method of mutual exclusion would work 99% of the time, it isn't a real solution. Consider the following possibility

Thread 1 Thread 2
Enters SomeThreadSafeFunction()
Checks busyFlag (false)
Exits while loop
Enters SomeThreadSafeFunction()
Checks busyFlag (false)
Exits while loop
Sets busyFlag to true
Writes first line
Sets busyFlag to true
Writes first line
Writes second line
Writes third line
Sets busyFlag to false
Writes second line
Writes third line
Sets busyFlag to false
Exits function
Exits function

Potentially resulting in the same output as before.

# 's
1This is the first line of a thread.
2This is the first line of a thread.
3This is the second line of a thread.
4This is the third line of a thread.
5This is the second line of a thread.
6This is the third line of a thread.

At this point it should be clear that what you need is a way to test a flag and then set it without the chance of being interrupted. This is more commonly known as an atomic test and set operation. Several forms of these operations exist (lock, monitor, semaphore, message queue) and they all perform thread synchronization in this manner. However in this article I will be using mutexes which are commonly found in languages which support multi-threaded programming. So, lets change our prior example to use a mutex.

# 's
 1     System.Threading.Mutex mut = new System.Threading.Mutex();
2
3 // ...
4
5 void SomeThreadSafeFunction()
6 {
7 mut.WaitOne(); // Wait for the mutex to become available and lock it.
8
9 // Critical section
10 Console.WriteLine("This is the first line of a thread.")
11 Console.WriteLine("This is the second line of a thread.");
12 Console.WriteLine("This is the third line of a thread.");
13 // End critical section
14
15 mut.ReleaseMutex(); // Unlock the mutex.
16}

The critical section is now mutually exclusive and thread safe. Meaning, it is safe to call with multiple threads because the shared resource (the console window in this case) is only accessed by one thread at a time. If you were to look at the inner code of the Console.WriteLine() method you would see a similar approach being used to ensure that an entire line is written uninterrupted by another thread. The problem with the code at the beginning of this article is that the List<>.Add() method is not thread safe. Adding a mutex to the class and using it to protect the critical section (in this case a single line of code) will solve the problem.

# 's
 1class crashtest
2{
3 private const int thread_count = 30;
4 private const int thread_items = 1000;
5
6 private System.Threading.Mutex mut = new System.Threading.Mutex();
7
8 private List<string> shared_data = new List<string>();
9 private List<Thread> threads = new List<Thread>();
10 bool begin = false;
11
12 public crashtest()
13 {
14 // ...
15 }
16
17 private void Work(object param)
18 {
19 // ...
20
21 for (int i = 0; i < thread_items; i++)
22 {
23 mut.WaitOne();
24 shared_data.Add(data);
25 mut.ReleaseMutex();
26 }
27 }
28}

That's it. This code will now function as expected each time it's run. If you've followed along so far congratulations! You now understand the basics of multi-threaded programming! There are just two more things I want to point out.

# 's
1Thread.CurrentThread.Priority = ThreadPriority.Lowest;

By setting the threads priority to lowest it increases the number of times that a context switch will occur. Since the example was meant to show that context switches can cause unexpected results in your code if not handled properly this setting helps ensure something bad happens. Typically speaking however, you don't need to (and usually shouldn't) mess with a threads priority level.

# 's
1bool begin = false;

You may have noticed that this shared boolean is accessed by multiple threads but never protected with a mutex. I don't want to get into why this is possible in this article but the point is that some shared access is thread safe by definition and so a mutex isn't always necessary.

Obviously there is a lot more to multi-threaded programming to be learned. Stay tuned as I'll continue to post on the subject. In the mean time, take a look at my thread safe byte buffer queue for a further example.

Comments

over 5 years ago (29 Sep 2008 at 11:42 PM) by Stou S.
Good article.

Random side note years ago when I switch to a dual processor machine I remember having multithreaded code, that worked perfectly on a single processor machine, deadlock like crazy on the dual machine. I can't remember the exact situation but something in Charles Petzold's book led me to believe that it was a bug that would only show up in dual processor machines... the point is, when writing multithreaded apps... test them on a dualcore system =)

Oh and I think you should mention that thread synchronization primitives require special hardware instructions (like test-and-set-lock), since someone might be wondering how semaphores/mutexes/critical-sections work under the hood. Although I guess the processor can just turn off interrupts in order to prevent task switches while setting locks.
over 5 years ago (30 Sep 2008 at 01:42 AM) by Spencer Ruport
Whoops. Wrong button. How about a delete comment feature? =D
over 5 years ago (30 Sep 2008 at 01:41 AM) by Spencer Ruport
Yeah I thought about getting into that a bit but I'm a little hazy on it myself. I believe atomic test and set operations used to be handled exclusively by the OS but now I'm not sure what role it plays. When I figure it out I'll be sure to write another article on it. ;)