Tuesday, March 10, 2009

Safe Thread Synchronization

http://msdn.microsoft.com/en-us/magazine/cc188793.aspx



Safe Thread Synchronization
Jeffrey Richter

By far, the most common use of thread synchronization is to ensure mutually exclusive access to a shared resource by multiple threads. In the Win32® API, the CRITICAL_SECTION structure and associated functions offers the fastest and most efficient way to synchronize threads for mutually exclusive access when the threads are all running in a single process. The Microsoft® .NET Framework doesn't expose a CRITICAL_SECTION structure, but it does offer a similar mechanism allowing mutually exclusive access among a set of threads running in the same process. This mechanism is made possible by way of SyncBlocks and the System.Threading.Monitor class.
In this column, I'm going to explain how this common use of thread synchronization is exposed via the .NET Framework. Specifically, I'm going to explain the motivation for why SyncBlocks and Monitors were designed the way they are and how they work. Then, at the end of this column, I'm going to explain why this design is horrible and show you how to use this mechanism in a good, safe fashion.

The Great Idea
The .NET Framework employs an object-oriented programming structure. This means that developers construct objects and then call the type's members in order to manipulate it. Occasionally, these objects are manipulated by multiple threads, and to ensure that the object's state doesn't become corrupted, thread synchronization must be performed. While designing the .NET Framework, the folks at Microsoft decided to create a new mechanism that would make it easy for developers to synchronize an object.
Here's the basic idea: every object in the heap has a data structure associated with it (very similar to a Win32 CRITICAL_SECTION structure) that can be used for thread synchronization. Then, the framework class library provides methods that, when you pass in a reference to an object, use that data structure for thread synchronization purposes.
In Win32, an unmanaged C++ class with this design would look like the one in Figure 1. In essence, the .NET Framework provides every object with its own CRITICAL_SECTION-like field and takes over the responsibility of initializing and deleting it. The only thing the developer has to do is write some code to enter and leave the field as necessary in each method that required thread synchronization.
Figure 1 A CRITICAL_SECTION for Every Object 
class SomeType {
private:
  // The private CRITICAL_SECTION field
  // associated with each object

  CRITICAL_SECTION m_csObject;

public:
  SomeType() {
     // The constructor initializes the
     // object's CRITICAL_SECTION field
     InitializeCriticalSection(&m_csObject);
  }


  ~SomeType() {
     // The destructor deletes the
     // object's CRITICAL_SECTION field
     DeleteCriticalSection(&m_csObject);
  }

  void SomeMethod() {
     // In the methods, we use the object's

     // CRITICAL_SECTION field to synchronize
     // access to the object by multiple threads.

     EnterCriticalSection(&m_csObject);
     // Execute thread-safe code here...
     LeaveCriticalSection(&m_csObject);

  }

  void AnotherMethod() {
     // In the methods, we use the object's
     // CRITICAL_SECTION field to synchronize
     // access to the object by multiple threads.

     EnterCriticalSection(&m_csObject);

     // Execute thread-safe code here...
     LeaveCriticalSection(&m_csObject);
  }
};

Implementing the Great Idea
Now, obviously, associating a CRITICAL_SECTION field with every object in the heap is quite wasteful, especially since most objects never require thread-safe access. So, the .NET Framework team designed a more efficient way to offer the functionality just described. Here's how it works.
When the common language runtime (CLR) initializes, it allocates a cache of SyncBlocks. A SyncBlock is a chunk of memory that can be associated with any object as needed. This SyncBlock contains the same fields that you would find in a Win32 CRITICAL_SECTION structure.
Whenever an object is created in the heap, each object gets two additional overhead fields associated with it. The first overhead field, the MethodTablePointer, contains the memory address to the type's method table. Basically, this pointer makes it possible to obtain the type information about any object in the heap. In fact, when you call System.Object's GetType method internally, this method follows the object's MethodTablePointer field to determine what type the object is. The second overhead field, called the SyncBlockIndex, contains a 32-bit signed integer index into the cache of SyncBlocks.
When an object is constructed, the object's SyncBlockIndex is initialized to a negative value to indicate that it doesn't refer to any SyncBlock at all. Then, when a method is called to synchronize access to the object, the CLR finds a free SyncBlock in its cache and sets the object's SyncBlockIndex to refer to the SyncBlock. In other words, SyncBlocks are associated with an object on the fly when the object needs the synchronization fields. When no more threads are synchronizing access to the object, the object's SyncBlockIndex is reset to a negative number, and the SyncBlock is free to be associated with another object in the future.
Figure 2 Thread Synchronization in .NET
For a concrete representation of this idea, take a look at Figure 2. In the CLR Data Structures section of the figure you can see that there is one data structure for every type that the system knows about; you can also see the set of SyncBlock structures. In the managed heap section of the figure you can see that three objects, ObjectA, ObjectB, and ObjectC, were created. Each object's MethodTablePointer field refers to the type's method table. From the method table, you can tell each object's type. So, we can easily see that ObjectA and ObjectB are instances of the SomeType type while ObjectC is an instance of the AnotherType type.
You'll notice that ObjectA's SyncBlockIndex overhead field is set to 0. This indicates that SyncBlock #0 is currently being used by ObjectA. On the other hand, ObjectB's SyncBlockIndex field is set to -1 indicating that ObjectB doesn't have a SyncBlock associated with it for its use. Finally, ObjectC's SyncBlockIndex field is set to 2 indicating that it is using SyncBlock #2. In the example I've presented here, SyncBlock #1 is not in use and may be associated with some object in the future.
So, logically, you see that every object in the heap has a SyncBlock associated with it that can be used for fast, exclusive thread synchronization. Physically, however, the SyncBlock structures are only associated with the object when they are needed and are disassociated from an object when they are no longer needed. This means that the memory usage is efficient. By the way, the SyncBlock cache is able to create more SyncBlocks if necessary so you shouldn't worry about the system running out of them if many objects are being synchronized simultaneously.

Using Monitor to Manipulate a SyncBlock
Now that you understand the SyncBlock infrastructure, let's examine how to lock an object. To lock or unlock an object you use the System.Threading.Monitor class. All of this type's methods are static. Here is the method you call to lock an object: 
public static void Enter(object obj);
When you call the Enter method, it first checks to see if the specified object's SyncBlockIndex is negative and if it is, the method finds a free SyncBlock and records its index in the object's SyncBlockIndex. Once a SyncBlock is associated with the object, this method examines the specified object's SyncBlock to see if another thread currently owns the SyncBlock. If it is currently unowned, then the calling thread becomes the owner of the object. If, on the other hand, another thread owns the SyncBlock when Enter is called, then the calling thread is suspended until the currently owning thread gives up ownership of the SyncBlock.
If you want to code more defensively, then instead of calling Enter, you can call one of the following TryEnter methods: 
public static Boolean TryEnter(object obj);

public static Boolean TryEnter(object obj,
   int millisecondsTimeout);


public static Boolean TryEnter(object obj,
   TimeSpan timeout);
The first version simply checks whether the calling thread can gain ownership of the object's SyncBlock and returns true if it is successful. The other two methods allow you to specify a timeout value indicating how long you'll allow the calling thread to sit around idly and wait for ownership. All the methods will return false if ownership cannot be obtained.
Once ownership is obtained, the code can access the object's fields safely. When finished, the thread should release the SyncBlock by calling Exit: 
public static void Exit(object obj);
If the calling thread doesn't own the specified object's SyncBlock, then Exit will throw a SynchronizationLockException. Also note that a thread can own a SyncBlock recursively; every successful call to Enter/TryEnter must be matched by a corresponding call to Exit before the SyncBlock is considered unowned.

Synchronizing the Microsoft Way
Now let's look at Figure 3 for some sample code that shows how to use Monitor's Enter and Exit methods to lock and unlock an object. Note that the implementation of the property requires calls to Enter, Exit, and a temporary variable, dt. This is very important in order to prevent returning a corrupt value. This could happen if a thread calls PerformTransaction at the same time another thread has accessed the property.
Figure 3 Using Enter and Exit Methods 
class Transaction {

  // Private field holding the time of
  // the last transaction performed

  private DateTime timeOfLastTransaction;

  public void PerformTransaction() {
     // Lock this object
     Monitor.Enter(this);

     // Perform the transaction...

     // Record time of the most recent transaction

     timeOfLastTransaction = DateTime.Now;

     // Unlock this object
     Monitor.Exit(this);
  }

  // Public read-only property returning
  // the time of the last transaction
  public DateTime LastTransaction {

     get {
        // Lock this object
        Monitor.Enter(this);

        // Save the time of the last transaction
        // in a temporary variable
        DateTime dt = timeOfLastTransaction;


        // Unlock this object
        Monitor.Exit(this);

        // Return the value in the temporary variable
        return(dt);
     }
  }
}

Simplifying the Code with the C# Lock Statement
Because this pattern of calling Enter, accessing the protected resource, and then calling Exit is so common, the C# language offers special syntax to simplify the code. The two C# code fragments in Figure 4 are identical in their function, but the second one is simpler. Using the C# lock statement, you can simplify the Transaction class substantially. In particular, take a look at the new, improved LastTransaction property that is shown in Figure 5; the temporary variable is no longer necessary.
Figure 5 Transaction Class 
class Transaction {

  // Private field holding the time of
  // the last transaction performed

  private DateTime timeOfLastTransaction;

  public void PerformTransaction() {
     lock (this) {
        // Perform the transaction...

        // Record time of the most recent transaction
        timeOfLastTransaction = DateTime.Now;

     }
  }

  // Public read-only property returning
  // the time of the last transaction
  public DateTime LastTransaction {
     get {
        lock (this) {
           // Return the time of the last transaction

           return timeOfLastTransaction;
        }
     }
  }
}
Figure 4 Regular and Simple Lock and Unlock 
// Regular function
public void SomeMethod() {
  // Lock the object
  Object oTemp = this;
  Monitor.Enter(oTemp);

  try {
         // Access the object
        ...
        // Unlock the object
  }
  finally {
    Monitor.Exit(oTemp);
  }
  // Return
}

// Simple function
public void SomeMethod() {

  // Lock the object
  lock (this) {

     // Access the object
     ...
    // Unlock the object
  }

  // Return
}
In addition to this simplification, the lock statement ensures that Monitor.Exit is called, releasing the SyncBlock even if an exception occurs inside the try block. You should always use exception handling with thread synchronization mechanisms to ensure that locks are released properly. If you use the C# lock statement, the compiler writes the proper code for you automatically. By the way, Visual Basic® .NET has a SyncLock statement that does the same things as the C# lock statement.

Synchronizing Static Members the Microsoft Way
The Transaction class demonstrates how to synchronize access to an object's instance fields. But, what if your type defines a number of static fields and static methods that access these fields? In this case, you don't have an instance of the type in the heap and, therefore, there is no SyncBlock to be used or object reference to pass to Monitor's Enter and Exit methods.
As it turns out, the block of memory that contains a type's type descriptor is an object in the heap. Figure 2 doesn't show it, but the SomeType Type Descriptor and AnotherType Type Descriptor memory blocks are actually objects themselves and, as such, each has a MethodTablePointer field and a SyncBlockIndex field. This means that a SyncBlock can be associated with a type and a reference to the type object can be passed to the Monitor's Enter and Exit methods. In the version of the Transaction class shown in Figure 6, all of the members have been changed to static and the PerformTransaction method and LastTransaction property have been modified to show how Microsoft expects developers to synchronize access to static members.
Figure 6 New Transaction Class 
class Transaction {

  // Private field holding the time of
  // the last transaction performed

  private static DateTime timeOfLastTransaction;

  public static void PerformTransaction() {
     lock (typeof(Transaction)) {
        // Perform the transaction...

        // Record time of the most recent transaction

        timeOfLastTransaction = DateTime.Now;
     }
  }

  // Public read-only property returning
  // the time of the last transaction
  public static DateTime LastTransaction {
     get {

        lock (typeof(Transaction)) {
           // Return the time of the last transaction
           return timeOfLastTransaction;
        }
     }
  }
}
In the code for the method and property, you no longer see the this keyword being used since it can't be referenced in static members. Instead, I'm passing a reference to the type's type descriptor object to the lock statement. This reference is obtained using the C# typeof operator—this operator returns a reference to the specified type's type descriptor. In Visual Basic .NET, the same functionality is exposed via the GetType operator.

Why the Great Idea isn't So Great
As you can see, the idea of having a synchronization data structure logically associated with every object in the heap sounds like a great idea. But, in real life, this is actually a terrible idea. Let me explain why. Remember the unmanaged C++ code shown at the beginning of this column? If you were coding this yourself, would you ever mark the CRITICAL_SECTION field with public access? Of course not—that would be ridiculous! Making this field public allows any code in the application to manipulate the CRITICAL_SECTION structure. It would then become trivially simple for malicious code to deadlock any threads that used instances of this type.
Well, guess what—the SyncBlock is just like a public synchronization data structure associated with every object in the heap! A reference to any object at all can be passed to Monitor's Enter and Exit methods at any time by any piece of code. In fact, a reference to any type descriptor can be passed to Monitor's methods too.
The code in Figure 7 demonstrates how horrible this situation can be. Here, Main constructs an App object and then enters this object's lock. At some point, a garbage collection occurs (in this code, the garbage collection is forced), and when App's Finalize method gets called, it attempts to lock the object. But, the CLR's Finalize thread can't acquire the lock because the application's primary thread owns the lock. This causes the common language runtime's Finalizer thread to stop—no more objects (in the process which can include multiple AppDomains) can get finalized and no more finalizable objects will ever have their memory reclaimed from within the managed heap!
Figure 7 Threads Banging Heads 
using System;
using System.Threading;

class App {
  static void Main() {
     // Construct an instance of the App object
     App a = new App();

     // This malicious code enters a lock on
     // the object but never exits the lock
     Monitor.Enter(a);

     // For demonstration purposes, let's release the
     // root to this object and force a garbage collection
     a = null;
     GC.Collect();

     // For demonstration purposes, wait until all Finalize
     // methods have completed their execution - deadlock!
     GC.WaitForPendingFinalizers();

     // We never get to the line of code below!
     Console.WriteLine("Leaving Main");
  }

  // This is the App type's Finalize method
  ~App() {
     // For demonstration purposes, have the CLR's
     // Finalizer thread attempt to lock the object.
     // NOTE: Since the Main thread owns the lock,
     // the Finalizer thread is deadlocked!
     lock (this) {
        // Pretend to do something in here...
     }
  }
}
Fortunately, there is a solution to this problem. However, it means you must ignore the Microsoft design and recommendations. Instead, you must define a private System.Object field as a member of your type, construct the object, and then use the C# lock or Visual Basic .NET SyncLock statement passing in a reference to the private object. Figure 8 shows how to rewrite the Transaction class so that the object used for synchronization is private to the class object. Likewise, Figure 9 shows how to rewrite the Transaction class where all the members are static.
Figure 9 Transaction with Static Members 
class Transaction {

  // Private, static Object field
  // used purely for synchronization
  private static Object objLock = new Object();


  // Private field holding the time of
  // the last transaction performed
  private static DateTime timeOfLastTransaction;

  public static void PerformTransaction() {
     lock (objLock) {
        // Perform the transaction...


        // Record time of the most recent transaction
        timeOfLastTransaction = DateTime.Now;
     }
  }

  // Public read-only property returning
  // the time of the last transaction

  public static DateTime LastTransaction {
     get {
        lock (objLock) {
           // Return the time of the last transaction
           return timeOfLastTransaction;
        }
     }

  }
}
Figure 8 Transaction with Private Object 
class Transaction {

  // Private Object field used
  // purely for synchronization
  private Object objLock = new Object();


  // Private field holding the time of
  // the last transaction performed
  private DateTime timeOfLastTransaction;

  public void PerformTransaction() {
     lock (objLock) {
        // Perform the transaction...


        // Record time of the most recent transaction
        timeOfLastTransaction = DateTime.Now;
     }
  }

  // Public read-only property returning
  // the time of the last transaction

  public DateTime LastTransaction {
     get {
        lock (objLock) {
           // Return the time of the last transaction
           return timeOfLastTransaction;
        }
     }
  }

}
It seems odd to have to construct a System.Object object just for synchronization with the Monitor class. When you get right down to it, I feel that Microsoft designed the Monitor class improperly. It should have been designed so that you construct an instance of the Monitor type for each type that you intend to synchronize. Then, the static methods should have been instance methods that don't require the use of the System.Object parameter. This would have solved all these problems and would have substantially simplified the programming model for developers.
By the way, if you create complex types with many fields, your methods and properties may need to lock only a subset of the object's fields at any time. You can always lock specific fields by passing the specific field object to lock or pass to Monitor.Enter. Of course, I would only consider doing this if the fields are private (which I always recommend). If you have several fields that you want to lock together, you can either use one of the fields as the one you always pass to lock or Enter. Or, you can construct a System.Object object that you use for the sole purpose of locking a field set. The more finely grained your locking, the better performance and scalability your code will achieve.

Unboxed Instances of Value Types
Before I wrap up this column, I'd like to point out a synchronization bug that took me several hours to track down the first time I ran into it. This code snippet demonstrates the problem: 
class AnotherType {

  // An unboxed Boolean value type
  private Boolean flag = false;

  public Boolean Flag {

     set {
        Monitor.Enter(flag); // Boxes flag and locks the object
        flag = value;        // The actual value is unprotected
        Monitor.Exit(flag);  // Boxes flag, attempts to unlock
                             // the object

     }
  }
}
You might be surprised to learn that in this code, no thread synchronization occurs! The reason is that flag is an unboxed value type, not a reference type. Instances of unboxed value types do not have the two overhead fields, MethodTablePointer and SyncBlockIndex. This means that an unboxed value type instance can't have a SyncBlock associated with it.
Monitor's Enter and Exit methods require a reference to an object on the heap. When C#, Visual Basic .NET, and many other compilers see code that is trying to pass an unboxed value type instance to a method that requires an object reference, they automatically generate code to box the instance. The boxed instance will have a MethodTablePointer and a SyncBlockIndex so the boxed version can be used for thread synchronization. However, a new boxed instance is created each time a method is called and therefore different objects are being locked and unlocked.
For example, in the last code snippet, when the Flag property's set property accessor method is called, it calls Monitor's Enter method. Enter requires a reference type and so flag is boxed and the pointer to the boxed version is passed to Enter. This boxed object's SyncBlock is now owned by the calling thread. If another thread were to access this property now, then flag would be boxed again making a new object with its own SyncBlock. In addition, the calls to Exit also box the passed value type.
As I said, it took me several hours to discover this problem. If you want to synchronize access to an unboxed value type instance, then you must allocate a System.Object object and use it for synchronization. The code in Figure 10 is the corrected code.
Figure 10 Now There's Synchronization 
class AnotherType {

  // An unboxed Boolean value type
  private Boolean flag = false;

  // A private Object field used to

  // synchronize access to the flag field
  private Object flagLock = new Object();

  public Boolean Flag {
     set {
        Monitor.Enter(flagLock);
        flag = value;
        Monitor.Exit(flagLock);

     }
  }
}
By the way, if you use the C# lock statement instead of calling Monitor's Enter and Exit methods directly, then the C# compiler will protect you from accidentally trying to lock a value type. When you pass an unboxed value type instance to the lock statement, the C# compiler produces an error. For example, if you try to pass a Boolean (bool in C#) to the lock statement, the following error is produced: error CS0185: 'bool' is not a reference type as required by the lock statement. The Visual Basic .NET compiler also reports the following error if you attempt to use an unboxed value type instance with its SyncLock statement: error BC30582: 'SyncLock' operand cannot be of type 'Boolean' because 'Boolean' is not a reference type.

Send your questions and comments for Jeff to dot-net@microsoft.com.


Jeffrey Richteris a cofounder of Wintellect (http://www.Wintellect.com), a training, debugging, and consulting firm specializing in .NET and Windows Technologies. He is the author of Applied Microsoft .NET Framework Programming (Microsoft Press, 2002) and several programming books on Windows.
Posted by at

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)