Synchronization

I l @ ve RuBoard

Earlier, when we discussed a technique for passing parameters to threads using a property, you learned that problems can occur, mainly due to uncertainty about how threads are executed. You can never guarantee the order in which threads are run (unless they all have different priorities), so if one thread sets some shared data to a value that is read by another, the reading thread might run before the writing thread has actually written the data. In situations in which the running order matters, threads must be carefully synchronized.

As a simple example, consider the Stock and StockController classes shown in the StockControl.jsl file in the StockControl project. The Stock class models stock items held in a fictitious warehouse. The private variable numInStock holds the volume of the item currently in stock. You can use the property get_numberInStock to query the current stock level. The method addToNumInStock increases the volume of the item in the warehouse when it is restocked, and the reduceNumInStock is used when customers order that item. If the stock is insufficient to satisfy the order, reduceNumInStock throws an exception.

The StockController class is a test harness that creates two concurrent threads that manipulate the same Stock object, called widgets . The TakeOrders method actually performs the deed, ordering seven widgets and adjusting the stock level in the warehouse accordingly . The method displays messages indicating its progress ”you can use the Name property (available through the set_Name and get_Name methods in J#) to associate an identifying string with a thread. The main method populates the Stock object with 10 widgets and then creates and starts two threads that run the TakeOrders method.

When this program is built and executed, a number of scenarios are possible. One is that the main thread creates the sc1Runner and sc2Runner threads and executes their Start methods, setting their status to Running . In the ideal situation, once one of the threads starts, it executes the TakeOrders method to completion, deducting seven widgets from the available stock before the second thread runs and trips the exception in reduceNumInStock because there are no longer enough widgets available to fulfill the second order. The ideal output is shown in Figure 8-6.

Figure 8-6. The ideal output of the StockControl program

In alternative scenario, the TakeOrders method is interrupted partway through its execution and the sc2Runner thread starts executing before the sc1Runner completes. (This can even occur without sc1Runner being interrupted if you're using a multiprocessor machine.) Both threads might conceivably execute the reduceNumberInStock method simultaneously . If you examine this method closely, you'll see a looming problem:

 if(numInStock>=byHowMany) { numInStock-=byHowMany; returnnumInStock; } else { thrownewSystem.Exception ("Insufficientgoodsinstock-pleasereorder"); } 

There is a very real possibility that a race condition will occur. If sc1Runner performs the test in the if statement first, it will find that numInStock (10) is greater than byHowMany (7). Execution will then proceed to the next statement. If sc2Runner performs the same test at the same time but before sc1Runner has actually updated the stock level, it will get the same results. Both threads will deduct 7 from numInStock , resulting in the same goods being ordered twice and the numInStock variable becoming corrupted ”it will end up containing the value -4! Figure 8-7 shows the output.

Figure 8-7. A race condition in the StockControl program

Tip

We simulated this problem by adding the statement System.Threading.Thread.Sleep(1) inside the if statement in reduceNumInStock before deducting from numInStock . This might not always work (using Sleep to force the execution order of threads is not guaranteed ), but if you run the program a few times, you should get these results at least once.

The issue is really one of atomicity. In a multithreaded environment, it is vitally important that sequences of test and set operations form an indivisible unit. But when you write code in a high-level language such as Visual Basic .NET, C#, or J#, even single statements are not guaranteed to be atomic. For example, look at the addToNumInStock method in the Stock class. It contains the following statement:

 numInStock+=howMany; 

If you open StockControl.EXE using the Intermediate Language Disassembly tool (ILDASM) and examine the Microsoft Intermediate Language (MSIL) code for this method, you'll see this sequence of instructions:

 .methodpublichidebysigvirtualinstanceint32 addToNumInStock(int32howMany)cilmanaged { //Codesize25(0x19) .maxstack3 .localsinit([0]int32V_0) IL_0000:ldarg.0 IL_0001:ldarg.0 IL_0002:ldfldint32ReaderWriter.Stock::numInStock IL_0007:ldarg.1 IL_0008:add IL_0009:stfldint32ReaderWriter.Stock::numInStock IL_000e:ldarg.0 IL_000f:ldfldint32ReaderWriter.Stock::numInStock IL_0014:stloc.0 IL_0015:br.sIL_0017 IL_0017:ldloc.0 IL_0018:ret }//endofmethodStock::addToNumInStock 

1. Push the current value of the static field numInStock onto the stack.

2. Push the value of argument 1 (the howMany parameter) onto the stack.

3. Add the two items at the top of the stack together, pushing the result onto the stack

4. Pop the item at the top of the stack back into the static field numInStock .

The important instructions are from address IL_0002 to IL_0009 . The sequence of operations is as follows :

This sequence could be suspended partway through. Another thread running the same method at the same time might corrupt the numInStock variable in a manner similar to the corruption you saw caused by concurrent execution of the reduceNumInStock method. And these are not the only combinations of sequences that can lead to this state of affairs ”one thread running addToNumInStock while another is executing reduceNumInStock can be equally disastrous.

The key to writing thread-safe code (code that will operate in a correct and well-defined manner when executed by multiple concurrent threads) is to use an appropriate synchronization technique.

Manual Synchronization

There are many ways to synchronize access to data. Some are more expensive than others in terms of resources used and other overhead, and some are more appropriate than others for a given scenario. Writing thread-safe applications is a matter of appreciating the options available and then applying them effectively.

You should ask yourself, "What code should I make thread-safe?" If you're building class libraries, you never know exactly how the methods in your classes will be invoked ”they might be executed concurrently from multiple threads. So all code that you write should be thread-safe ”or carefully documented with a big red warning label if it is not.

However, this does not mean that you must always implement expensive synchronization techniques. You can achieve a high level of thread safety by designing your classes carefully or using algorithms that can tolerate race conditions. Classes that expose static methods or static data are always vulnerable in a multithreaded environment and require synchronization. Restricting classes to instance methods and data does not guarantee thread safety (the Stock class shown earlier is an example of this), but such classes are less prone to problems with multithreading, and weak points can be isolated and protected more easily.

Note

The ability to mark a method as thread-safe or otherwise would certainly be a useful feature ”possibly using a ThreadSafe attribute that takes a Boolean parameter indicating whether the author intended the method to be available to a multithreaded environment. Naturally, the default value of this attribute would be false . The common language runtime (which knows all about the threads being used) could examine this attribute before executing each method and take appropriate action ”throwing an exception if a non-thread-safe method is invoked from anything other than the primary thread running an application, or enforcing the serialization of all non-thread-safe methods. The cost would be a few extra instructions executed before each method call, but the benefits could be enormous .

.NET Class Library Thread Safety

For reasons of performance, Microsoft has adopted the "big red warning label" approach and many of the classes in the .NET Class Library are not thread-safe. For instance, Microsoft created a number of classes in the System.Collections namespace for handling collections of data ”hash tables, array lists, queues, and so on. However, you can make many classes thread-safe by creating a static thread-safe wrapper and accessing the class exclusively through this wrapper. Microsoft has implemented such a wrapper for most of the collection classes.

For example, the ArrayList class provides the Synchronized method. You pass this method an ArrayList , and it returns a thread-safe reference to the same object:

 importSystem.Collections.*; ArrayListal=newArrayList(); ArrayListsal=ArrayList.Synchronized(al); sal.Add(...);//UsesallikeanordinaryArrayList 

Note that the System.Array class does not have a Synchronized method, and arrays are not thread-safe by default. For classes such as this, you must implement your own wrappers. In a number of cases, the .NET Framework Class Library provides the SyncRoot property, which returns an object that can be used to provide synchronized access. You can use this property with some of the synchronization primitives described in this chapter to implement thread safety for those classes.

Sync Blocks

Behind the scenes, each object running using the common language runtime contains a data structure that you can use to synchronize access to that object. This data structure is referred to as the sync block . Object-level synchronization primitives, such as the Monitor class, use it.

The Monitor Class

You can use the System.Threading.Monitor class to control access to shared resources and critical sections of code (code that should be executed by only one thread at a time). A Monitor object can obtain an exclusive lock over the sync block of an object specified by the developer when the static Enter method is used. An attempt to execute Enter by another thread will result in that thread being blocked. You release the lock by executing Monitor.Exit over the same object. If any threads are blocked, one of them will be selected and granted the lock, and then it can continue processing. Any remaining threads will remain blocked and continue waiting.

Note

The Monitor object operates in a manner similar to that used by synchronized methods in Java. The implementation of a synchronized method in J# actually executes Monitor.Enter(this) when the method starts and Monitor.Exit(this) when the method completes.

For example, if you need to restrict concurrent access to a resource such as the numInStock variable shown in the StockControl sample discussed earlier, you can use the technique shown here (this version of the code is available in the ConcurrentStockControl project):

 privateintnumInStock=0; //Restockthewarehouse publicintaddToNumInStock(inthowMany) { try { Monitor.Enter(this); this.numInStock+=howMany; returnthis.numInStock; } finally { Monitor.Exit(this); } } //Removestockfromwarehouse publicintreduceNumInStock(intbyHowMany)throwsSystem.Exception { try { Monitor.Enter(this); if(this.numInStock>=byHowMany) { this.numInStock-=byHowMany; returnthis.numInStock; } else { thrownewSystem.Exception("Insufficientgoodsinstock-pleasereorder"); } } finally { Monitor.Exit(this); } } 

When a method calls Monitor.Enter , the common language runtime will attempt to lock the sync block for the specified object ( this in the example above). If the sync block is already locked by another thread, Monitor.Enter will be suspended until it is released. The method call Monitor.Exit over the same object releases the sync block. Invocations of Monitor.Enter and Monitor.Exit must be balanced ”if you call Monitor.Enter over the same object twice, you must call Monitor.Exit twice to release the sync block. Failure to do this can result in the sync block never being released, leading to some long waits by blocked threads!

You should consider your exception handling strategy carefully when you use a monitor. Unhandled exceptions in a thread will cause the thread to terminate, and all its locks will be released automatically. However, if you catch exceptions, you must be prepared to release locks manually as part of the exception handling process. The code shown above uses a try finally construct to guarantee that Monitor.Exit is executed before the methods finish.

Note

If Monitor.Enter blocks, the thread will enter the WaitSleepJoin state. The thread can be woken using the Interrupt method, or it can be aborted.

When you use a monitor, you should consider carefully the object whose sync block you're going to use. The same object must be available to all the threads you intend to coordinate; otherwise, they'll have nothing in common to synchronize on. But you should avoid using a wide- ranging global object as a generic locking object because this can lead to sync block contention . Ideally, when you use monitors for synchronization, each protected resource (or group of resources) should have its own associated lock object (probably the object itself).

You should also ensure that you avoid deadlock. Deadlock commonly happens when threads require several locks over the same resources but acquire those locks in a different sequence ”for example, when two threads that have obtained one lock each attempt to obtain the lock held by the other and end up waiting indefinitely for each other. To reduce the likelihood of deadlock, you should always lock resources in the same order.

Tip

You might find the Execute Around pattern (not one of the GoF patterns) useful in deadlock situations. This pattern involves creating a synchronizer wrapper object that performs all the locking and can take a delegate that refers to a method to be executed after the necessary locks have been acquired .

The Monitor class also has the TryEnter method, which will attempt to grab the sync block for the selected object but will terminate if the lock cannot be obtained. TryEnter returns a Boolean value indicating whether the lock was obtained successfully:

 if(Monitor.TryEnter(this)) { try { //lockobtaineddoprocessing } finally { Monitor.Exit(this); } } else { //failedtoobtainlock } 

The TryEnter method is overloaded, and you can optionally specify a timeout as a second parameter. The method will wait until the lock is obtained (returning true ) or until the timeout occurs (returning false ):

 TimeSpants= newTimeSpan(0,0,30);//0hours,0minutes,30seconds if(Monitor.TryEnter(this,ts)) { } 

The Interlocked Class

The Monitor class is general-purpose ”it allows you to implement a variety of short and long-lived locking strategies (although long-lived locks are not always recommended as they can adversely affect the concurrency and throughput of your applications). For example, you can perform Monitor.Enter in one method and execute the corresponding Monitor.Exit method in another ”as long as the same thread invokes both methods. A monitor can be too heavy and coarse-grained for some operations, however, so the .NET Framework Class Library provides some specialized alternatives in the Interlocked and ReaderWriterLock classes.

The Interlocked class provides synchronized access to variables shared by multiple threads. It implements the CompareExchange , Decrement , Exchange , and Increment methods. These methods comprise atomic operations ”for example, Increment will increment an int or a long variable and will not be preempted partway through its execution:

 inti=100; Interlocked.Increment(i);//atomic 

Similarly, the Interlocked.Decrement method will atomically decrement an int or long variable.

The Interlocked.Exchange method performs an atomic query and assignment operation. The value of the second argument overwrites the first, but the method returns the original value of the first argument before the assignment occurred. It will operate on int , float , and Object types

Tip

If you use Exchange over Object types, make sure you have overridden the Equals method to make comparisons meaningful.

 inti=100; intj=120; intoldValue=Interlocked.Exchange(i,j);//oldValue=i;i=j; 

The Interlocked.CompareExchange method is an atomic test and set operation that compares the first and third arguments. If they are equal, the variable specified by the first argument is set to the value specified by the second; otherwise, the first argument is left unchanged. The value returned is the original value of the first argument (whether or not it has been changed):

 inti=100; intj=120; intk=100; intoldValue= Interlocked.CompareExchange(i,j,k);//oldValue=i; //if(i==k) //i=j; 

Like Interlocked.Exchange , Interlocked.CompareExchange will operate on int , float , and Object types. (All three parameters must be of the same type.)

The ReaderWriterLock Class

Just as the Interlocked class is a highly specialized beast optimized for performing a defined set of operations, so the ReaderWriterLock class is aimed at a particular set of problems. The ReaderWriterLock class caters for the "single writer, multiple readers" scenario. In this situation, a resource can be read by many threads concurrently with impunity, but a thread writing to the resource needs exclusive access. You can contrast this with the more draconian monitor approach, which enforces mutual exclusion regardless of whether the protected resource is being read or written to.

The algorithm used by the ReaderWriterLock class is based on fairness. Under normal circumstances, concurrent read requests can overlap. However, if a writer requests access, all further read requests will be queued behind the writer. This prevents the writer from potentially being blocked indefinitely.

The ReaderWriterLock class exposes a variety of methods for acquiring reader and writer locks, for releasing locks held, and for determining whether the current thread is actually holding a lock. These are instance methods, so to use them you must create a ReaderWriterLock object. The following code fragment shows implementations of the get_numberInStock and reduceNumInStock methods, which employ a ReaderWriterLock called stockLock . (This code is available in the ReaderWriterStockControl project.)

You should note several important points. First, you obtain a lock by calling AcquireReaderLock or AcquireWriterLock as appropriate. An attempt to obtain a writer lock will block if reader locks currently exist over the same ReaderWriterLock object, as will attempts to acquire a reader lock if a writer lock is currently held or has been requested. Remember that even though reader locks can be obtained concurrently, they will be held in a queue once a writer lock has been requested . Both methods expect a timeout parameter. If the lock has not been gained when the timeout expires , the common language runtime will throw a System.ApplicationException containing the message "This operation returned because the timeout period expired ." You can specify a value of 0 for the timeout if you do not want to wait, or Timeout.Infinite if you're prepared to wait indefinitely. Here's the code:

 privateintnumInStock=0; privateReaderWriterLockstockLock=newReaderWriterLock(); //Howmanyinstock /**@property*/ publicintget_numberInStock()throwsSystem.Exception { try { stockLock.AcquireReaderLock(newTimeSpan(0,0,5)); returnthis.numInStock; } finally { if(stockLock.get_IsReaderLockHeld()) { stockLock.ReleaseReaderLock(); } } } //Removestockfromwarehouse publicintreduceNumInStock(intbyHowMany)throwsSystem.Exception { try { stockLock.AcquireWriterLock(newTimeSpan(0,0,5)); if(this.numInStock>=byHowMany) { this.numInStock-=byHowMany; returnthis.numInStock; } else { thrownewSystem.Exception("Insufficientgoodsinstock-pleasereorder"); } } finally { if(stockLock.get_IsWriterLockHeld()) { stockLock.ReleaseWriterLock(); } } } 

You release locks using the ReleaseReaderLock or ReleaseWriterLock method. If you're currently holding a writer lock as well as a reader lock, ReleaseReaderLock will actually release them both. ReleaseWriterLock will release only a writer lock, however (it will also throw an exception if the thread is holding a reader lock). An error will result if you release a lock that you don't hold, which is why the finally blocks in the sample code shown above execute the property accessor methods get_IsReaderLockHeld and get_IsWriterLockHeld . These methods return true if the thread currently holds a lock of the designated type, false otherwise.

What constitutes a read or write operation (requiring a reader or a writer lock) is up to the developer. It's normally taken for granted that a read operation reads some data value, and that a write operation modifies it in some way, but what you actually do is your decision. The ReaderWriterLock class provides the methods UpgradeToWriterLock and DowngradeFromWriterLock to allow you to convert a reader lock to a writer lock and back again if needed.

Warning

The common language runtime does not care whether you write when you hold a reader lock, or vice-versa. Reading with a writer lock is no big deal, but writing with only a reader lock can be dangerous if others have reader locks also.

Reader and writer locks implement nested semantics. If you acquire a reader lock using AcquireReaderLock five times, you should release it using ReleaseReaderLock five times. An alternative is to use the method ReleaseLock , which will release all the locks that a thread holds on a ReaderWriterLock object regardless of how many times it grabbed them.

Automatic Synchronization

The Java language provides a synchronized method modifier that can be used to perform automatic synchronization of method calls. Similarly, the .NET Framework Class Library contains a pair of attributes that you can use to synchronize access to methods and objects. The first of these is System.Runtime.CompilerServices.MethodImplAttribute .

Method Synchronization

The MethodImplAttribute class has many uses. It is commonly employed by compiler writers, which is why it is in the CompilerServices namespace. Its purpose is to supply metadata indicating how a method is actually implemented ”for example, whether it was developed using managed or unmanaged code. One option you can specify is Synchronized . This indicates to the common language runtime that the method should be accessed by only one thread at a time. The runtime will automatically serialize access to the method in a particular object, and will block a thread that attempts to execute the method if another thread is currently executing it.

The following code shows another version of the reduceNumInStock method, which uses MethodImplAttribute :

 importSystem.Runtime.CompilerServices.*; /**@attributeMethodImplAttribute(MethodImplOptions.Synchronized)*/ publicintreduceNumInStock(intbyHowMany)throwsSystem.Exception { if(numInStock>=byHowMany) { numInStock-=byHowMany; returnnumInStock; } else { thrownewSystem.Exception("Insufficientgoodsinstock-pleasereorder"); } } 

This synchronization approach makes access to the method itself thread-safe (two threads will not be able to execute reduceNumInStock in the same object concurrently), but it does not prevent other methods (such as addToNumInStock ) from running, so this technique is appropriate only for protecting data manipulated by a single method. You can apply MethodImplAttribute to static and instance methods.

Object Synchronization

Managed objects live in application domains. An application domain can be divided into contexts. A context groups objects that share the same features, or context attributes. Each application domain has a default context, which is created when the application domain is created, but additional contexts might be created automatically as new objects with specific requirements are instantiated .

Objects themselves can be marked as being context-bound or context-agile. A context-agile object can be accessed freely from any other context in the same application domain. Context-bound objects can be accessed directly by other objects in the same context, but objects in other contexts must use proxies to access a context-bound object. (You will learn more about context-bound and context-agile objects in Chapter 11.) Much of the time, you don't need to be concerned whether an object is context-agile or context-bound because proxy generation and marshaling of method calls across context boundaries occurs automatically. (Marshaling across a context boundary in the same application domain is not as expensive as it sounds because everything is performed in process.) The exception to this rule, however, is if you want to apply context attributes to a class. All objects that have the same set of context attribute values reside in the same context and must be explicitly marked as being context-bound. One such attribute is System.Runtime.Remoting.Contexts.SynchronizationAttribute , which is used for performing object-level synchronization.

The SynchronizationAttribute is applied to a class. The class must inherit from System.ContextBoundObject for this attribute to have any effect. You can specify one of four synchronization options (listed below). If you've ever designed COM+ classes, these options might have a familiar feel.

• REQUIRED

  The object must execute in a synchronized context. If necessary, a new context will be created. If the object is invoked by another object that is already in a synchronized context, the existing context will be used. All method calls to the object and any other objects sharing the same context will be serialized.

• REQUIRES_NEW

  A new synchronized context will be created for the object. All method calls to this instance of the object (and any other synchronized objects it creates) will be serialized. Other instances of the object will be created in their own contexts.

• SUPPORTED

  The object can execute in the current context, regardless of whether the context is synchronized. Method calls to the object are not serialized.

• NOT_SUPPORTED

  The object will not execute in a synchronized context. If necessary, a new nonsynchronized context will be created. Method calls are not serialized.

The implementation of the Stock class shown below, available in the SynchronizedStockControl project, uses the REQUIRES_NEW option to create a synchronized context that serializes all method calls to the same instance of each Stock object (different instances still operate independently and can be accessed concurrently). Notice that the methods themselves require no additional logic for handling multithreading:

 importSystem.*; importSystem.Runtime.Remoting.Contexts.*; //Stockclass-modelsstockitemsinawarehouse /**@attribute SynchronizationAttribute(SynchronizationAttribute.REQUIRES_NEW) */ publicclassStockextendsContextBoundObject { privateintnumInStock=0; //Howmanyinstock publicintget_numberInStock() { returnthis.numInStock; } //Restockthewarehouse publicintaddToNumInStock(inthowMany) { this.numInStock+=howMany; returnthis.numInStock; } //Removestockfromwarehouse publicintreduceNumInStock(intbyHowMany)throwsSystem.Exception { if(this.numInStock>=byHowMany) { this.numInStock-=byHowMany; returnthis.numInStock; } else { thrownewSystem.Exception("Insufficientgoodsinstock-pleasereorder"); } } } 

Object synchronization is a powerful concept and is relatively easy to apply, but it does come with a penalty. In particular, as with the use of monitors, it locks an object for exclusive access and makes no distinction between read and write operations. Also, object synchronization does not apply to static methods.

Static and Thread Data

Static fields usually belong to a class rather than individual objects or sets of objects. When you use multithreading, however, you can create different instances of a static variable in different threads by applying the ThreadStaticAttribute to the variable in question. These are known as thread-relative static fields:

 /**@attributeThreadStaticAttribute()*/ privatestaticintthreadVar=100;//initializationmaynotoccur 

In this example, each thread will receive its own copy of the variable threadVar . Each instance created by a thread will automatically be assigned the value 0 regardless of whether the variable declaration contains any initialization. (This does not apply if the main program thread instantiates the object containing the variable ”normal initialization will occur in this case.) You can apply this attribute only to static variables.

Under the covers, thread-relative static fields are implemented using managed thread local storage (TLS). The Thread class exposes the AllocateDataSlot , SetData , and GetData methods that allow you to interact with managed TLS directly, creating and releasing TLS data slots dynamically:

 privateLocalDataStoreSlotldss; publicvoiddoWork() { ldss=System.Threading.Thread.AllocateDataSlot(); System.Threading.Thread.SetData(ldss," "Somedata"); } publicvoiddoSomeMoreWork() { Stringmsg=(String)System.Threading.Thread.GetData(ldss); } 

The class System.LocalDataStoreSlot is the .NET abstraction for a piece of TLS. The static method AllocateDataSlot creates a new chunk of TLS and returns a reference to it. You can use the static SetData method to store information in a slot. The information stored can be almost anything ”the parameter is passed in as an Object . Later, the data can be read back using the GetData method, which passes a reference to the same slot. The result must be cast to the type of data held in that slot. Data slots are private to a thread, and no other thread can access them.

You can also create named data slots. This gives you increased flexibility ”the name of a slot can be a string variable, and you do not have to retain static references to slots allocated in one method for use by another:

 publicvoiddoWork() { LocalDataStoreSlotldss= System.Threading.Thread.AllocateNamedDataSlot("Slot1"); System.Threading.Thread.SetData(ldss," "Somedata"); } publicvoiddoSomeMoreWork() { LocalDataStoreSlotldss= System.Threading.Thread.GetNamedDataSlot("Slot1"); Stringmsg=(String)System.Threading.Thread.GetData(ldss); } 

If you call GetNamedDataSlot on a nonexistent slot, it will be created automatically and its contents will be initialized to null . (It would be nicer if the runtime threw an exception, but you can't have everything!) If you try to create two slots with the same name, the common language runtime will throw a System.ArgumentException with the message "Item has already been added." You can release named slots using the FreeNamedDataSlot method.

A final variation on the static variable theme is the context static variable. All threads executing in the same context share static variables marked with System.ContextStaticAttribute . Different contexts see different instances of static data marked in this way.

 /**@attributeContextStaticAttribute()*/ privatestaticintcontextData; 

I l @ ve RuBoard