This is a sample chapter from the book Thinking in C#, by Larry O'Brien and Bruce Eckel. (c) 2002, 2003 Larry O'Brien, all rights reserved. Please do not repost without permission. For more information, or to gain access to the complete book, please visit /ticsharprc1.htm/
Objects divide the solution space into logical chunks of state and behavior. Often, you need groups of your objects to perform their behavior simultaneously, as independent subtasks that make up the whole.
Each of these independent subtasks is called a thread, and you program as if each thread runs by itself and has the CPU to itself. Some underlying mechanism is actually dividing up the CPU time for you, but in general, you don�t have to think about it, which makes programming with multiple threads a much easier task.
A process is a self-contained running program with its own address space. In C#, each application runs in its own process. A multitasking operating system is capable of running more than one process (program) at a time, while making it look like each one is chugging along on its own, by periodically providing CPU cycles to each thread within each process. A thread is a single sequential flow of control within a process (a �thread of execution�). A single process can thus have multiple concurrently executing threads.
There are many possible uses for multithreading, but in general, you�ll have some part of your program tied to a particular calculation or resource, and you don�t want to hang up the rest of your program because of that. So you create a thread associated with that calculation or resource and let it run independently of the main program. A good example is a �cancel� button to stop a lengthy calculation �you don�t want to be forced to poll the cancel button in every piece of code you write in your program and yet you want the cancel button to be responsive, as if you were checking it regularly. In fact, one of the most immediately compelling reasons for multithreading is to produce a responsive user interface.
As a starting point, consider a program that performs some CPU-intensive operation and thus ends up ignoring user input and being unresponsive. This one simply covers the display in a random patchwork of red spots:
At this point, the graphics code should be reasonably familiar from Chapters 14 and 15, except that instead of painting the display in OnPaint( ), we use Control.CreateGraphics( ) to stay busy: The method loops numberToCountTo times, picks a random spot on the form, and draws a 1-unit rectangle there.
Part of the loop inside startCounting( ) calls Thread.Sleep( ). Thread.Sleep( ) immediately pauses the currently executing thread for some amount of milliseconds. Regardless of whether you�re explicitly using threads, you can produce the current thread used by your program with Thread and the static Sleep( ) method.
When the Start button is pressed, startCounting( ) is invoked. On examining startCounting( ), you might think that it should allow multithreading because it goes to sleep. That is, while the method is asleep, it seems like the CPU could be busy monitoring other button presses. But it turns out that the real problem is that startCounting( ) doesn�t return until after it�s finished, and this means that stopCounting( ) is never called until it�s too late for its behavior to be meaningful. Since you�re stuck inside startCounting( ) for the first button press, the program can�t handle any other events. (To get out, you must either wait until startCounting( ) ends, or kill the process; the easiest way to do this is to press Control-C or to click a couple times to trigger Windows� �Program Not Responding� dialogue.)
The basic problem here is that startCounting( ) needs to continue performing its operations, and at the same time it needs to return so that stopCounting( ) can be activated and the user interface can continue responding to the user. But in a conventional method like startCounting( ) it cannot continue and at the same time return control to the rest of the program. This sounds like an impossible thing to accomplish, as if the CPU must be in two places at once, but this is precisely the illusion that threading provides.�
The thread model (and its programming support in C#) is a programming convenience to simplify juggling several operations at the same time within a single program. With threads, the CPU will pop around and give each thread some of its time. Each thread has the consciousness of constantly having the CPU to itself, but the CPU�s time is actually sliced between all the threads. The exception to this is if your program is running on multiple CPUs. But one of the great things about threading is that you are abstracted away from this layer, so your code does not need to know whether it is actually running on a single CPU or many. Thus, threads are a way to create transparently scalable programs.
Threading reduces computing efficiency somewhat, but the net improvement in program design, resource balancing, and user convenience is often quite valuable. Of course, if you have more than one CPU, then the operating system can dedicate each CPU to a set of threads or even a single thread and the whole program can run much faster. Multitasking and multithreading tend to be the most reasonable ways to utilize multiprocessor systems.
Like most modern operating systems, Windows differentiates between processes, which separate applications, and threads, which are the low-level unit of flow control inside a process; .NET introduces the concept of an Application Domain as an intermediate container between the two. An AppDomain, in addition to being responsible for loading and executing assemblies, is responsible for a managed process. In the same way that .NET has a managed heap that includes a Garbage Collector, managed processes are somewhat safer than unmanaged processes; specifically, a managed process can guarantee that finally clauses are executed, that IDisposable.Dispose( ) is called appropriately, and that garbage collection works properly with objects referenced by the managed process.
At any time, a given Thread is managed by some AppDomain. The controlling AppDomain may very well change over time, so Thread.GetDomain( ) is a method, not a property. The AppDomain may, conversely, be managing many threads but there is no easy way to determine this set given just an AppDomain reference. You do not usually need to interact with the AppDomain of a Thread, but it is important for remoting (not discussed in this book).
You must manage your Thread through five of its seven states of its life: Unstarted, Running, WaitSleepJoin, Suspended, and Stopped. The runtime will handle two intermediate states, SuspendRequested and AbortRequested. At any time, Thread.ThreadState will be one of these values.
Not all Threads need to enter all these states, as the state-transition diagram in Figure 16-1 illustrates. State-transition diagrams are UML diagrams that are especially handy to illustrate complex object lifecycles, such as is done here (they can also be used as the basis for a Finite-State-Machine architecture, popular with embedded programmers and developers of bad game AI).
: The lifecycle of a Thread
A .NET Thread must be constructed with a delegate of type ThreadStart. The ThreadStart delegate takes no arguments and returns nothing:
Once constructed, Thread.Start( ) will put the Thread in ThreadState.Running and the ThreadStart delegate will get called. If the Thread does not call the various methods shown in Figure #, and if no other Thread calls Thread.Suspend( ) on your Thread, when the ThreadStart( ) delegate returns, the Thread will call Thread.Abort( ) on itself and eventually change to ThreadState.Aborted.
This sample shows the bare minimum needed to get some behavior out of a Thread.
The threading classes are in the System.Threading namespace, so we need to bring in those references with using System.Threading. The Main( ) instantiates a ThreadStart delegate with the MyThreadedExecutionBlock� method. The delegate is passed to the Thread( ) constructor and we write myThread.ThreadState to the console.
If you run this program, sometimes you may see this output:
which is exactly what you�d expect if, as with a normal method call, the execution of Main( ) was suspended by the call to Start( ) that in turn called MyThreadedExecutionBlock( ). However, most times you run this program, you�ll see this:
Precisely because Main( ) is not suspended that long. Main( ) is suspended during the call to Start( ), but Thread.Start( ) simply triggers the start of the secondary thread, it does not wait for any behavior from it. The line that writes �After Start( )�� is written by the application thread; whether that line is written before myThread has begun processing or after its processing is a matter of a race between the main thread getting to the �After Start( )�� line before and the secondary thread getting to the �Executed from�� line.
It�s appropriate that our very first multithreaded program demonstrates a race condition defect. When programming with threads, you must never assume the order in which threads will reach certain blocks of code. If we wanted to ensure that the secondary thread had completed, we might try this:
Here, bool secondaryThreadFinished is a condition variable that is used to communicate between threads. After Main( ) calls myThread.Start( ), it spins in a tight loop, checking to see if the condition has been satisfied. This is what is called a busy-wait. The iSpins variable is not necessary for the logic of the program, but is used to illustrate why busy-waits are bad ideas. This program will have the desired behavior of delaying the writing of �After Start( )�� until after the secondary thread has completed, but you may be shocked at the value of iSpins. This value represents a lot of wasted CPU effort.
Instead of a busy-wait, changing the loop to:
will have a dramatic effect on the final value of iSpins (it will probably reduce it to 1).� The static method Thread.Sleep( ) takes an integer representing a time in milliseconds or a TimeSpan and places the current thread (that is, the Thread that is executing the line of code) into the WaitSleepJoin state for that amount of time. This suspension is done at the OS level and allows the CPU to be used efficiently.
If you pass a value of 0 to Thread.Sleep( ), you suspend the current thread so that other waiting threads may execute, but you are not requesting an actual pause in the current thread�s processing. If you pass a value of Timeout.Infinite, you are requesting that the Thread be put to sleep forever; we�ll cover how to get out of that situation with Thread.Interrupt( ) a little later.
The following example creates any number of threads that it keeps track of by assigning each thread a unique number, generated with a static variable. The delegated behavior is in the Run( ) method, which is overridden to count down each time it passes through its loop and finishes when the count is zero (at the point when the delegated method returns, the thread is terminated).
The ThreadStart delegate method (often called Run( )) virtually always has some kind of loop that continues until the thread is no longer necessary, so you must establish the condition on which to break out of this loop (or, in the case above, simply return from Run( )). Often, Run( ) is cast in the form of an infinite loop, which means that, barring some external factor that causes Run( ) to terminate, it will continue forever.
In Main( ) you can see a number of threads being created and run. The Start( ) method in the Thread class performs the initialization for the thread and then calls Run( ). So the steps are: The constructor is called to build the object that will do the work, the ThreadStart delegate is given the name of the working function, the ThreadStart is passed to a newly created Thread, then Start( ) configures the thread and calls the delegated function � Run( ). If you don�t call Start( ), the thread will never be started.
The output for one run of this program (it will be different from one run to another) is:
You�ll notice that nowhere in this example is Thread.Sleep( ) called, and yet the output indicates that each thread gets a portion of the CPU�s time in which to execute. This shows that Sleep( ), while it relies on the existence of a thread in order to execute, is not involved with either enabling or disabling threading. It�s simply another method.
You can also see that the threads are not run in the order that they�re created. In fact, the order that the CPU attends to an existing set of threads is indeterminate, unless you go in and adjust the Priority property of the thread.
When Main( ) creates the Thread objects it isn�t capturing the references for any of them. This is where the managed process capability of the AppDomain comes into play. An ordinary object with no references to it would be fair game for garbage collection, but not a Thread in a managed process. As long as the Thread has not entered ThreadState.Stopped, it will not be garbage collected.
Now it�s possible to solve the problem in Counter1.cs with a thread. The trick is to make the working method �that is, the loop that�s inside StopCounting( )�a delegate of a Thread. When the user presses the start button, the thread is started, but then the creation of the thread completes, so even though the thread is running, the main job of the program (watching for and responding to user-interface events) can continue. Here�s the solution:
Counter2 is a straightforward program, whose only job is to set up and maintain the user interface. But now, when the user presses the start button, the event-handling code does not do the time-consuming work. Instead a thread is created and started, and then the Counter2 interface can continue to respond to events.�
When you press the onOff button it toggles the runFlag condition variable inside the Counter2 object. Then, when the �worker� thread calls PaintScreen( ), it can look at that flag and decide whether to continue or stop. Pressing the onOff button produces an apparently instant response. Of course, the response isn�t really instant, not like that of a system that�s driven by interrupts. The painting stops only when the thread has the CPU and notices that the flag has changed.
If the thread painting the screen is running when the form is closed, the program will throw a fairly cryptic ExternalException with the explanation that �a generic error occurred in GDI+.� To get rid of this, we add another delegate StopCountingIfClosing and attach it to the Counter2 form�s Closing event. This also requires us to add using System.ComponentModel at the top of the program.
In Counter2, the loop within PaintScreen( ) calls Thread.Sleep( ) to sleep for 20 milliseconds. What if some crisis happened and even that was too long? Or, to return to something we discussed earlier, what if Thread.Sleep( ) was called with the value of Timeout.Infinite, would we be doomed to face another non-responsive interface? The answer is that in both situations, we can use Thread.Interrupt( ) to force the Thread to wake.
If you refer to Figure 16-1, you�ll see that to get out of ThreadState.WaitSleepJoin and back to ThreadState.Running requires someone to call Thread.Interrupt( ). When you call Thread.Sleep( ), the call is done by the runtime when the time�s up. But you can do it yourself if you want to interrupt a sleeping thread (the method name Thread.Interrupt( ) may be a little counter-intuitive at first, as stopping or pausing an active thread is also sometimes called �interrupting the thread.� If you just repeat �You can Interrupt a Sleeping Thread� enough times, you�ll get used to it.)
When you call Thread.Interrupt( ), a ThreadInterruptedException is thrown from the method you called that put the Thread in the WaitSleepJoin state (in this case, Thread.Sleep( )). If you do not catch this exception, it will propagate out of your ThreadStart delegate and your Thread will abort.
This example shows a Cat which has a CatNap( ) method that is used as a ThreadStart delegate. The Cat is interested in a Mouse that is not hiding in the walls. The Cat wakes up every 10 seconds for just long enough to determine if the mouse is in the room, if not, the Cat goes to sleep again. The Mouse class has a method SneakAbout( ) which is also to be used as an instance of� ThreadStart. The Mouse has a 20% chance of moving from hole to room and vice versa and, if in the room, it has a 10% chance of squeaking. If it squeaks, it will call Thread.Interrupt( ) on the theCat Thread.
This is a very good example, but I think it would be even more clear if the output was prepended with the name of the thread it�s coming from (i.e. �Jerry: In Room� or �Tom: Chasing mouse�)
When you run this, sometimes it will end when the mouse is quietly in the room and the cat happens to wake up. Other times, it will end because Thread.Interrupt( ) immediately wakes the cat, triggering the exception handler. If the ThreadInterruptedException was not handled in the cat�s ThreadStart method CatNap( ), the call to myCat.Interrupt( ) would just terminate the myCat thread silently.
If you thought Thread.Interrupt( ) was a counterintuitive name, Thread.Join( ) is downright inexplicable. Thread.Join( ) blocks the calling thread until the Thread on which Join( ) has been called terminates. Why this is called �joining� the other thread is a mystery.�
Strange name aside, Thread.Join( ) is very useful, as waiting for another thread to end is probably one of the most commonly desired behaviors. Going back to the SecondaryThread example, Thread.Join( ) allows us to eliminate both the condition variable and the loop.
The line myThread.Join( ) is executed by the main application thread. When executed, the main application thread changes to ThreadState.WaitSleepJoin until myThread changes to ThreadState.Stopped. (However, if someone had a reference to the main thread of execution and called Thread.Interrupt( ) on it, a ThreadInterruptedException would be thrown from inside the myThread.Join( ) call. See the preceding section for an explanation.)
If you do not trust that the other thread will end, you can pass an int millisecond value or TimeSpan to Join( ). If the other thread hasn�t ended before the timeout elapses, the current thread will restart.
If you comment out the line
the program will continue to run even after Main( ) has exited. Every Thread is either a background thread or a foreground thread; an application only exits when all foreground threads have stopped. For Java programmers, this is the equivalent of the Thread.isDaemon( ).
The state-transition diagram in Figure 16-1 shows one more method that can put a Thread in ThreadState.WaitSleepJoin: Monitor.Wait( ). Before we can discuss this method, though, we�ll have to introduce some more multithreading complexity.
You can think of a single-threaded program as one lonely entity moving around through your problem space and doing one thing at a time. Because there�s only one entity, you never have to think about the problem of two entities trying to use the same resource at the same time, like two people trying to park in the same space, walk through a door at the same time, or even talk at the same time.
With multithreading, things aren�t lonely anymore, but you now have the possibility of two or more threads trying to use the same limited resource at once. Colliding over a resource must be prevented or else you�ll have two threads trying to access the same bank account at the same time, print to the same printer, or adjust the same valve, etc.
Consider a variation on the counters that have been used so far in this chapter. In the following example, each thread contains two counters that are incremented and displayed inside Run( ). In addition, there�s another thread of class Watcher that is watching the counters to see if they�re always equivalent. This seems like a needless activity, since looking at the code it appears obvious that the counters will always be the same. But that�s where the surprise comes in. Here�s the first version of the program:
As before, each counter contains its own display components: two text fields and a label that initially indicates that the counts are equivalent. These components are added to the panel of the Sharing1 object in the Sharing1 constructor.�
Because a TwoCounter thread is started via a button press by the user, it�s possible that Start( ) could be called more than once. It�s illegal for Thread.Start( ) to be called more than once for a thread (an exception is thrown). You can see the machinery to prevent this in the started flag and the Start( ) method.
The accessCountBox in Sharing1 keeps track of how many total accesses have been made on all TwoCounter threads. One way to do this would have been to have a static property that each TwoCounter could have incremented during SynchTest( ). Instead, we declared an IncrementAccess( ) delegate within TwoCounter that Sharing1 provides as a parameter to the TwoCounter constructor.
In Run( ), count1 and count2 are incremented and displayed in a manner that would seem to keep them identical. Then Sleep( ) is called; without this call the UI becomes unresponsive because all the CPU time is being consumed within the loops.
The SynchTest( )� calls its IncrementAccess delegate and then performs the apparently superfluous activity of checking to see if count1 is equivalent to count2; if they are not equivalent it sets the label to �Unsynched� to indicate this.
The Watcher class is a thread whose job is to call SynchTest( ) for all of the TwoCounter objects that are active. It does this by stepping through the array of TwoCounters passed to it by the Sharing1 object. You can think of the Watcher as constantly peeking over the shoulders of the TwoCounter objects.
Sharing1 contains an array of TwoCounter objects that it initializes in its constructor and starts as threads when you press the �Start Threads� button. Later, when you press the �Begin Watching� button, one or more watchers are created and free to spy upon the unsuspecting TwoCounter threads.
By changing the numCounters and numWatchers values, which you can do at the command-line, you�ll change the behavior of the program.
Here�s the surprising part. In TwoCounter.Run( ), the infinite loop is just repeatedly passing over the adjacent lines:
(as well as sleeping, but that�s not important here). When you run the program, however, you�ll discover that count1 and count2 will be observed (by the Watchers) to be unequal at times! This is because of the nature of threads�they can be suspended at any time. So at times, the suspension occurs between the time count1 and count2 are incremented, and the Watcher thread happens to come along and perform the comparison at just this moment, thus finding the two counters to be different.
This example shows a fundamental problem with using threads. You never know when a thread might be run. Imagine sitting at a table with a fork, about to spear the last piece of food on your plate and as your fork reaches for it, the food suddenly vanishes (because your thread was suspended and another thread came in and stole the food). That�s the problem that you�re dealing with.
Any time you rely on the state of an object being consistent, and that state can be manipulated by a different thread, you are vulnerable to this type of problem. This is another manifestation of a race condition defect (because your program�s proper functioning is dependent on its thread winning the �race� to the resource). This type of bug (and all bugs relating to threading) is difficult to track down, as they will often slip under the radar of your unit testing code and appear and disappear depending on load, hardware and operating system differences, and the whimsy of the fates.
Preventing this kind of collision is simply a matter of putting a lock on a resource when one thread is relying on that resource. The first thread that accesses a resource locks it, and then the other threads cannot access that resource until it is unlocked, at which time another thread locks and uses it, etc. If the front seat of the car is the limited resource, the child who shouts �Dibs!� asserts the lock.
Real-world programs have to share many types of resources � network sockets, database connections, sound channels, etc. By far the most common collisions, though, occur when some threads are changing the states of objects and other threads are relying on the state being consistent. This is the case with our TwoCounter and Watcher objects, where a thread controlled by TwoCounter increments the count1 and count2 variables, while a thread controlled by Watcher checks these variables for consistency.
�The Monitor class helps prevent collisions over object state. Every reference type in C# has an associated �synchronization block� object which maintains a lock for that object and a queue of threads waiting to access the lock. The Monitor class is the public interface to the behind-the-scenes sync block implementation.
The method Monitor.Enter(object o) acts as gatekeeper � when a thread executes this line, the synchronization block for o is checked; if no one currently has the lock, the thread gets the lock and processing continues, but if another thread has already acquired the lock, the thread waits, or �blocks,� until the lock becomes available. When the critical section of code has been executed, the thread should call Monitor.Exit(object o) to release the lock. The next blocking thread will then be given a chance to obtain the lock.
Making value types, which are created on the stack or inline, Monitor-able would be hugely inefficient, so you can only use Monitor on reference types. If you incorrectly use a value type as an argument to Monitor.Enter( ), it will throw a SynchronizationLockException at runtime. The current version of the runtime diagnoses an attempt to lock a value type with this somewhat misleading message: �Object synchronization method was called from an unsynchronized block of code.�
Because you virtually always want to release the lock on a thread at the end of a critical section, even when throwing an Exception, calls to Monitor.Enter( ) and Monitor.Exit( ) are usually wrapped in a try block:
Armed with this technique it appears that the solution is at hand: We�ll use the Monitor class to synchronize access to the counters. The following example is the same as the previous one, with the addition of Monitor.Enter/Exit calls at the two critical sections:
You�ll notice that both TwoCounter.Run( ) and SynchTest( ) call Monitor.Enter( ) and Exit( ). If you use the Monitor only on Run( ), the Watcher threads calling SynchTest( ) will happily read the state of the TwoCounter even while the TwoCounter thread has entered the critical section and has placed the object in an inconsistent state by incrementing Counter1 but not yet changing Counter2.
There�s nothing magic about thread synchronization � it�s the manipulation of the TwoCounter instance�s sync block via the Monitor that does the work. All synchronization depends on programmer diligence: Every piece of code that can place an object in an inconsistent state or that relies on an object being in a consistent state must be wrapped in an appropriate block.�
In order to save you some time typing, C# provides the lock keyword, which creates a guarded code block exactly equivalent to the
idiom. Instead of all that typing, you use the lock(object) keyword and specify a code block to be protected:
Although lock( )�s form makes it appear to be a call to a base class method (implemented by object presumably), it�s really just syntactic sugar. The choice of lock as a keyword may be a little misleading, in that you may expect that a �locked� object would be automatically thread-safe. This is not so; lock says that the current thread will act appropriately. If all threads follow the rules, things will work out for the best, but if another piece of code has a reference to the �locked� object, it may mistakenly manipulate the object without ever using Monitor. It�s like taking a number for service at a bakery � a fine idea that breaks down as soon as someone misbehaves through laziness or ignorance. Java has a similar mechanism, but uses the keyword synchronized, which gives a better indication that success requires the cooperation of multiple objects and threads.
Another advantage of lock over Monitor.Enter( ) is that the compiler will refuse to compile code that attempts to lock a value type.
Monitor.Enter( ) and Exit( ) can be passed any object for synchronization. It is best to use this � an inability to use this for synchronization (perhaps because you have mutually exclusive types of inconsistency to guard against) is a �code smell� that indicates that your object may be trying to do too many things at once and may be best broken up into smaller classes. For instance, in the TwoCounter class, we could place counter1 and counter2 in an inner class, add thread-safe accessors and methods, and achieve our goal without ever locking the entire TwoPanel instance:
The Counter class, an inner class of TwoPanel is now �thread-safe,� by removing any chance that an external object can place it in an inconsistent state. Incrementing the counter integers is done inside the Increment method, with a locked critical section, and access to the integers is done via the Count1 and Count2 properties, which also synchronize against the Monitor to ensure that they cannot be read until the Increment critical section has exited (and,� undesirably, also ensure that Count1 and Count2 cannot be read simultaneously by two different threads � a small penalty typical of the design decisions made when developing multithreaded apps).
Sometimes, locking this doesn�t seem like the right idea. When an object contains some resource, and especially when that resource is a container of some sort, such as a Collection or a Stream or an Image, it is common to want to perform some operation across some subset of that resource without worrying about whether some other thread will change the resource halfway through your operation. In a situation like this, it�s common to lock the resource, not this. we�re of two minds on this: On the one hand, the principle of coupling leads to the thought that if the only thing that�s vulnerable to being placed in an inconsistent state is the resource, then lock the resource, as locking this unnecessarily couples this and the resource. On the other hand, the principle of cohesion leads us to think that if one portion of the methods and resources� in an instance are vulnerable to race conditions, but other methods and resources in the instance aren�t, then maybe we ought to refactor. This is what we did with our TwoPanel class, splitting the initial class into two, and we think Sharing3 is clearly a superior design to Sharing2.
At this point, you shouldn�t be surprised that this program quickly fails:
The Run( ) method, which is used by a bunch of threads, increments and then decrements refCount, while a thread running the static delegate method ValCheck( ) stops the program if the value of refCount is ever not 0. When you run this, it is not long before refCount becomes either 2 or -1. This is what happens:
To synchronize access to the static value-type refCount, you have to wrap all access to the refCount object inside lock blocks that use some dummy object to synchronize on. You cannot lock(refCount) because it�s a value type. And lock(this) is ineffective on static objects! So you have to create a static dummy object to serve as a guard for the critical sections:
And indeed, that�s the general solution to synchronizing static value types.
For the specific problem of reference counting, however, the Interlocked class allows you to increment, decrement, and assign to an int or long in a thread-safe and very, very fast manner. It can also compare two ints or two longs without requiring the overhead of the Monitor implementation.
Even aside from its synchronization capabilities, Interlocked should be used to generate serially increasing id values. Although
is fine for a single-threaded program, it�s not thread-safe, since the ++ operator reads and assigns the value in two separate operations. A thread can come along after the read but before the assignment and therefore, in a multithreaded program, Next( ) could return the same value twice.
You might expect this program to freeze:
The first time RecursiveCall( ) is called, it acquires the Monitor to this. Then, from within that locked block, it calls RecursiveCall( ). What happens when it comes to the lock block on this second call? You might think �Well, it�s a different call to the method, so it will block.� But the right to enter the block is owned by the calling Thread; since it owns the lock on this, it continues into the lock block and recurses MAX_CALLS times.
An object�s thread-safety is entirely a function of the object�s state. A class without any static or instance variables, consisting solely of methods that don�t call methods that put it into ThreadState.WaitSleepJoin, is inherently thread-safe. Any variables or resources that affect whether your object is in a consistent state should be private or protected and only available to outside objects by way of properties or methods. It�s just foolish to ever allow direct references to these critical resources from external objects. If instead you create properties and methods which consistently use the Monitor class (or the equivalent lock blocks), you�ll save yourself considerable headaches when it comes to locating and debugging threading problems.
The Mutex class is similar to the Monitor class, but is used to synchronize behavior across application domains. And instead of locking on an arbitrary object, the Mutex locks itself � owning the Mutex provides cross-process mutual exclusion.
You attempt to acquire the Mutex by calling one of the overloaded Mutex.WaitOne( ) methods. If you pass in no arguments, the calling thread goes into ThreadState.WaitSleepJoin until the Mutex is available. Or you can call Mutex.WaitOne( ) with a timeout value and a bool that interacts with the SynchronizedAttribute. If you do not use the [Synchronized( )] �attribute, the value you use for this is irrelevant.
This example allows only one copy of the application to run on the machine at a time. To run this, open two console windows and run the program in both simultaneously.
When run, the output of the second instance of the application will be:
(You may have one more or fewer �Another app has the Mutex� lines, depending on how fast you started the second application.)
The first line of MutexDemo.Main( ) instantiates a .NET Mutex that corresponds to an OS-level mutex that is identified at the OS-level by the string �MutexDemo.� The call to WaitOne(0, true ) returns true immediately the first time the application is called � the OS-level �MutexDemo� mutex is available. Since gotTheMutex is true, the first application reports that it has the mutex and blocks for ten seconds.
If one or more additional applications are run within that ten second period, their calls to WaitOne(0, true ) will immediately return false because the �MutexDemo� mutex is held by the first application. As long as gotTheMutex is false, the application reports it to the console and calls WaitOne( ), again, this time specifying a 3,000 millisecond timeout.
For the purposes of this book, the only thing that you can use a Mutex for is as the basis of cross-process blocking. If your work involves .NET Remoting, you�ll learn how methods and objects can be invoked and moved across process boundaries and the Mutex will become the basis of synchronizing such behaviors.
We�ve discussed race conditions as one of the challenges of multithreading programming. To fight race conditions, we introduced the various methods that put the current Thread into ThreadState.WaitSleepJoin. Unfortunately, this introduces a new type of problem: the deadlock.
A deadlock is a situation where Thread a requires a resource locked by Thread b, which Thread b will not release until it acquires a resource locked by Thread a. Both threads enter WaitSleepJoin and, at best, the program times out. Of course, if it�s just two threads you have a good chance of finding the problem and debugging it; the real joy of deadlocks comes when it�s Thread a depending on Thread b depending on Thread c � depending on Thread z that depends on Thread a.
The classic deadlock exemplar is the Dining Philosophers problem. Five philosophers, or in this case language designers, are seated around a table. Each coder has a chopstick to his (or her) left and right.
: Language designers are happy when they have access to food
The coders do nothing but pontificate and eat. To eat, they pick up the chopstick� on their left and then the chopstick on the right.
When you run this program, the diners� pontificate for a while and then start to eat. When a diner is in Pickup( ) and they attempt to pick up a chopstick that is being used by their neighbor, they must wait. A reference to the Diner that is going to wait is stored in the Chopstick�s waitingFor variable. The call to Diner.Wait( ) puts the diner�s thread into ThreadState.WaitSleepJoin. If that Thread is not interrupted before the timeout, the diner starves to death. If, on the other hand, the current diner holding that chopstick calls Putdown( ), it calls waitingFor.Interrupt( ) which in turn calls Interrupt( ) on the thread that has been put into WaitSleepJoin.
When you run this program, it may run for a few seconds or it may run for quite a while, but eventually what will happen is that every diner will pick up the chopstick to their left and be waiting for the diner on their right to release their chopstick. All of the diners will starve to death.
There are several different ways to keep the diners from starving to death (for instance, if one of the group picks up the chopstick to their right first, no deadlock will occur), but the issue isn�t really keeping dime-a-dozen language designers alive, it�s developing good practices for minimizing deadlock.
One way to avoid a deadlock is to never wait for one resource while holding a lock on another. If there�s no hold-and-wait, there can be no deadlock. However, theoretically this can trigger livelock, in which the threads release and then ask for the resources again with such perfect timing that they never resolve the issue. In Windows, this threat can be discounted; given the speed with which locks are acquired and the nature of the OS-level thread scheduler, livelock may not even be possible.
The most general way to beat deadlocks is to design the acquisition of locks such that there is no possibility of circular dependencies. Without a circular wait, deadlocks cannot occur. If you get into complex blocking code, use the overloads of Monitor.Wait( ) and Thread.Join( ) that take a maximum time before throwing TimeoutExceptions.
To minimize deadlock, you must work on the balance between properly controlling the critical regions in your code and the dependencies that arise from blocking. This is an area where commonly used programming language and the .NET Framework fall short of what could be done. Multithreading is where memory management was a decade ago: a detail-oriented source of bugs that is the programmer�s responsibility. Just as software and hardware advances made managed memory models practical on the desktop, so too can we hope that a more advanced parallel processing model will eventually be incorporated into the .NET Framework and into application programming languages.�
Creating a safe multithreaded library is considerably more difficult than creating a single multithreaded application. Not only do you have to try to avoid deadlock in all the scenarios in which your library is used logically, you must never expose a virtual method that is called within a critical section. The problem is that if you declare a method as virtual and call it within a critical section (that is, a section in which you�ve acquired a Monitor), it is possible that the client programmer will override it in a way that creates a new thread and attempts to acquire the same Monitor. For this deadlock scenario to play out, the client must create a new thread since, as discussed on page 753, a call to acquire the Monitor within the same thread�s call stack will succeed. This is a subtle-enough requirement that this object-oriented deadlock can sneak by a lot of unit tests and code reviews.
The injunction goes against all virtual calls: those marked virtual, interfaces, abstract classes, and delegate calls are all vulnerable to this object-oriented deadlocking. In the following program, a Library object executes the method Client.VirtualCall( ). This works alright for FineClient, but BadClient deadlocks:
The Library class contains a reference to a Client object, whose VirtualCall( ) method is called within a lock block inside of Library.ThreadCaller( ). The two methods Library.Run( ) and Library.Stop( ) use previously discussed techniques to begin and end the ThreadCaller( ) loop.
In addition to the abstract method VirtualCall( ), the abstract class Client specifies a method called LockAndTalk( ), which acquires a lock on the Library object, outputs something to the screen, waits a second, and then releases the lock. (This violates our preference to lock(this), but it�s the easiest code to demonstrate the danger of virtual method calls.)
FineClient just calls LockAndTalk( ). When LockAndTalk( ) is called in FineClient, it is being executed in the same thread that executed Library.ThreadCaller( ) and that owns the Library monitor. Therefore, FineClient( ) works just fine.
BadClient( ) implements VirtualCall( ) in a way that the Library author did not anticipate: it starts a new Thread whose ThreadStart( ) delegate, a method called ThreadedLockAndTalk( ), calls LockAndTalk( ) from within a new thread. Notice that there is no explicit attempt on the part of the BadClient programmer to lock anything; the BadClient programmer is not doing anything obviously prone to failure. However, when ThreadedLockAndTalk( ) calls LockAndTalk( ) and that method attempts to acquire the lock on the Library object, the lock attempt is being executed from a different thread than the original thread in Library.ThreadCaller( ), which of course already has the lock on the Library object. The result is that although the BadClient programmer has done nothing obviously wrong, the Library deadlocks.
Writing a multithreaded library that is reentrant, that is, can be safely invoked from multiple threads, concurrently, and in a nested manner, is difficult enough at the best of times, but it is much harder if your library makes a virtual method call while holding onto a lock. Critical sections must be as controlled as possible; a virtual method call cedes that control and makes disaster all too likely.
Referring back to Figure 16-1, you�ll see that in addition to the WaitSleepJoin that we�ve discussed extensively, a call to Thread.Suspend( ) will place a Thread into ThreadState.SuspendRequested and subsequently into ThreadState.Suspended( ). Unlike the static Thread.Join( ) and Thread.Sleep( ) methods, Thread.Suspend( ) is an instance method. Thus, Suspend is useful in situations where, for some reason, the current Thread doesn�t have sufficient knowledge to control its own scheduling.
If an inability to lock(this) is a �code smell� that suggests that a refactoring may be called for, a need to use Thread.Suspend( ) is a stench.� Why does the current thread not have enough knowledge to know what resources it needs to wait on or in what situations it should suspend processing? In a good object-oriented design, objects encapsulate both the state and behavior they need to fulfill their design contracts; in a good multithreaded design, the object that contains the ThreadStart delegate should take the responsibility to maintain the state and behavior necessary to properly control the Thread using the ThreadStart delegate.
Sometimes people try to use Suspend( ) and Resume( ) to prioritize the scheduling of their application�s calculations, but that is precisely what the Thread.Priority property should be used for.
The collection classes in .NET�s System.Collections namespace are not thread-safe and behavior is �undefined� when collisions occur.� This program illustrates the issue:
The Main( ) creates a SyncCol1 class with a parameter indicating how many threads to simultaneously write to a collection. A SortedList is created and passed to the TimedWrite method. This method sets the static variable ExceptionCount of the WriterThread class to 0 and creates an array of WriterThreads. The WriterThread constructor takes the list and a variable. Each WriterThread creates a new thread, whose processing is delegated to the WriterThread.WriteThread( ) method. The IsBackground property of the WriterThread�s thread is set to true. Being able to create background �daemon� threads is very convenient, especially in a GUI, where the user can request a program closure at any time.
After the WriterThread constructor returns, the next line of TimedWrite( ) calls the Start( ) method, which in turn starts the inner thread, which in turn delegates processing to WriteThread( ). WriteThread( ) loops 5,000 times, each time creating a new name (such as �Writer237�) and attempting to add that to theList. A SortedArray is backed by two stores � one to store the values and another to store a sorted list of keys (the keys may or may not be the same as the values).
The call to Add( ) an element to the list is wrapped in a catch block. Since we are ignoring the details of the exception and only recording how many exceptions were thrown, the catch statement does not specify a variable name for the caught exception. Once the loop is finished, we set the Finished property of the WriterThread, kill the Thread, and return. Back in the SyncCol1 class, the main application thread goes through the array, checking to see if it�s finished. If it�s not, the main thread goes to sleep for 1,000 milliseconds before checking again. When all the WriterThread�s are Finished, the WriteThread( ) writes some data on the experiment and returns.
After the initial call with a regular SortedList, we create a new SortedList and pass it to the static method SortedList.Synchronized( ). All the Collections have this static method, which creates a new, thread-safe Collection.� To be clear, the program creates a total of 3 SortedLists: the one for the initial run through WriteThread( ), a second anonymous one, which is used as the parameter to SortedList.Synchronize( ), which returns a third one. After Chapter 12�s description of the .NET I/O library, you should recognize the Decorator pattern in play.
When you run this program, you�ll see that the first run with a plain SortedList throws a large number of exceptions (if you have a sufficiently speedy computer, you may get no exceptions, but if you increase the number of threads, eventually you�ll run into trouble), while the list produced by Synchronized( ) adds all the data flawlessly. You�ll also see why Collections aren�t synchronized by default: the thread-safe list takes something like 5-8 times the duration to complete.�You can find out if a Collection is synchronized or not by examining its Synchronized property, as TimedWrite( ) does during its status-writing lines.
If, instead of using a list produced by SortedList.Synchronized( ), you put a lock(theList) block around the Add( ) call, you�ll get exception-less behavior on both runs as well. Curiously, if you do this, the synchronized list seems to always outperform the unsynchronized list by a small margin!
In general, though, the challenge of working with collections and threads is not the thread-safety of the underlying collection, but the inherent challenge of objects being added, deleted, or changed by threads while your current thread tries to deal with the collection as a single logical unit. For instance, in an object with an instance object called myCollection, whether the Collection is Synchronized or not, the lines
are inherently thread-unsafe because another thread might have removed element i before the second line is executed. If the class obeys the recommendation that the only references to a critical resource like myCollection are internal, any method that accesses myCollection can simply lock(this) and achieve thread-safety.
The foreach keyword uses the IEnumerator interface to traverse a collection. You can also get an IEnumerator directly by calling GetEnumerator( ) on any of the collection classes. The IEnumerator methods MoveNext( ) and Reset( ) will throw an InvalidOperationException if their originating collection is changed during the enumerator�s lifetime. This is true even if the collection is synchronized � traversing a non-locked data structure is inherently thread-unsafe.
It�s not always possible to design classes that don�t expose internal instance or static collections, but give it a hard try before giving up on the attempt. Can you Clone the collection? Use the Proxy pattern to return, not the collection itself, but an interface to your own thread-safe methods? If not, be prepared for some long debugging sessions, because it�s a good bet that any time you open the door to multithreading defects, someone will introduce them.
Multithreaded programming cannot be done casually. If you never lock anything, you will face race conditions. If you lock excessively, you will have deadlocks.
� To ensure state in a multithreaded environment, you must protect critical sections with lock blocks (or the equivalent calls to Monitor.Enter( ) and, within a finally block, Monitor.Exit( )). A critical section may be as short as a single use of the ++ operator, so you must be painstaking in your consideration of all operations involving the critical state of your class.
� If non-readonly non-value data is ever shared between threads, every thread that writes or reads the data must obtain a lock on the data before writing or reading the data. The synchronization mechanism is required for reliable interthread communication as well as for mutual exclusion.
� Hold locks for as short a time as possible. The longer you hold a lock, the greater the chance for a deadlock.
� Don�t call virtual methods from within a critical section. A virtual method can be implemented in any way and may cause a deadlock.
� Flaws in threading logic may very well escape all unit and acceptance testing, and are often difficult to recreate. Proper multithreading is the most demanding aspect of C#�s programming model.
�This is not a C# or .NET issue; this use of the word join is traditional in the world of multithreading. Perhaps you can think of �boards are Joined end-to-end� as a mnemonic.
�Cilk adds just 3 keywords to the C programming language, has a conceptually simple work-stealing scheduler, and yet is very efficient. Parallel processing can be made much more accessible to the average programmer; it just has not yet been a priority for language designers. Even without keywords, one can imagine using attributes�to declaratively identify parallelization opportunities and constraints.
�If you said �But it�s the same Big O!� give yourself a gold star. If you said, �But ignorant hacks would confuse library performance with language performance and compare thread-safe collections to non-thread-safe collections, and on the basis of simplistic benchmarks write that C# has a performance problem, just as they did with Java!� give yourself a platinum star.�