Fundamentals Of Concurrent Programming For .net

Charteris White Paper

Fundamentals of Concurrent Programming for .NET Greg Beech ([email protected]) 18 March 2005

2005 Charteris plc

CONTENTS CONTENTS

2

1.

3

INTRODUCTION

2. 2.1 2.2 2.3 2.4 2.5

THREADING IN .NET Operating system threads Fibers Managed threads The managed thread pool Asynchronous method invocation 2.5.1 Predefined asynchronous operations 2.5.2 User-defined asynchronous operations 2.6 Events and multicast delegates 2.7 Summary

4 4 4 4 5 6 6 7 7 8

3. 3.1 3.2

THREAD SYNCHRONIZATION Overview The .NET memory model 3.2.1 Volatile reads and writes 3.3 Monitor and the C# lock statement 3.4 MethodImplOptions.Synchronized 3.5 ReaderWriterLock 3.6 Wait handles 3.6.1 Mutex 3.6.2 ManualResetEvent and AutoResetEvent 3.6.3 Semaphore 3.7 Interlocked 3.7.1 Increment and Decrement 3.7.2 Exchange and CompareExchange 3.8 Summary

9 9 9 9 9 11 12 13 14 15 16 16 16 17 17

4. 4.1 4.2 4.3 4.4 4.5 4.6 4.7

DESIGN CONSIDERATIONS Nondeterministic execution Deadlocks Suspending, resuming and aborting threads Placement of critical sections The double-lock initialization pattern Raising events Summary

18 18 18 20 21 23 24 25

5.

CONCLUSIONS

26

APPENDIX A REFERENCE S

27

APPENDIX B SEMAPHORE CODE LISTING

29

18 March 2005

Fundamentals of Concurrent Programming for .NET Charteris White Paper

Page 2 of 30

1.

INTRODUCTION

Many developers will have read Herb Sutter’s article “The Free Lunch is Over” which talks about the future speed increases of CPUs. The good news is that they will get significantly faster, but the bad news is that you won’t see all of the possible performance gains unless you write your application to take advantage of them. Over the last few years the increase in clock speeds has slowed down, and chip manufacturers are focussing more and more on concurrent execution of code. Hyperthreading was the first step, which allows a single processor core to execute two threads in parallel, but the future is multi-core chips which will allow many threads to execute truly independently. Intel is already talking about chips with over a hundred cores, so if your code is single-threaded you may only be using one hundredth of the available processing power! This Charteris White Paper introduces the fundamentals that will allow you to begin writing concurrent applications, and is intended to be easier to read than much of the material on this subject. It is targeted at developers who have some experience of developing on the .NET Framework, and ideally in C# as this is my language of choice for the code samples. No prior knowledge of concurrent programming or multi-threading is needed, though even experienced developers in this area may find some new and surprising information. The first section of this paper provides background information about threads, fibers, the thread pool asynchronous methods and events particularly with respect to the .NET Framework. In the second section the .NET memory model is briefly examined and the most important synchronization mechanisms such as Monitor, ReaderWriterLock and Interlocked are described. The final section discusses some of the key design patterns and considerations when writing concurrent applications. Please note that this paper does not to provide all the information needed to become a proficient developer of concurrent applications, however it should confer a basic understanding of multithreading and some of the choices available when writing concurrent applications. The references section is extensive as there is a lot of information available about this topic, and if this paper sparks your interest I would thoroughly recommend that you read and understand the majority of these referenced articles which will elaborate on the concepts introduced here and introduce many more advanced ones.

18 March 2005

Fundamentals of Concurrent Programming for .NET Charteris White Paper

Page 3 of 30

2.

THREADING IN .NET

2.1

Operating system threads

An operating system (OS) thread is a system resource that executes code in sequence. Each process running on the operating system has one or more threads. A computer with one single core processor that is not hyperthreaded can execute exactly one thread at any given time, so the operating system has to schedule the threads to let one run for a period of time (known as its quantum or time slice) before allowing another thread to run.

When the currently running thread is paused and another thread is allowed to run, it is known as a context switch. Although context switches are required to allow multiple threads to run on a single processor they do have some performance cost such as saving and restoring registers. As such it is not a good idea to have too many threads as otherwise the system will spend more time context switching and less time actually executing the threads. As a rough guideline, under normal conditions there may be a few thousand context switches per second – this can be monitored with the performance counter Thread\Context Switches/sec using a tool such as Microsoft System Monitor. On a hyperthreaded CPU two threads can be executed simultaneously which can help to reduce the number of context switches, however there are certain compromises as it still uses the same core, so the speed increase is not as much as you might expect with a typical increase being up to around 25%. A multi-processor system or multi-core processor can execute multiple threads truly in parallel and independently of each other so the performance can theoretically increase in proportion to the number of processors/cores. In reality this is not quite true because of the requirement for synchronization between the processors in both hardware and software – and the fact that it is hard to write systems that effectively use this many threads simultaneously! Many server applications see negligible increases in speed past eight or even four processors.

2.2

Fibers

A fiber can be thought of as a lightweight thread that it is not scheduled by Windows, but must be manually scheduled by an application to run against a real OS thread. The Common Language Runtime (CLR) hosting API in versions 1.0 and 1.1 had basic support for fiber scheduling, and in version 2.0 and later these have been comprehensively overhauled, essentially to allow the CLR to be hosted in SQL Server 2005 in fiber mode. Sophisticated hosts such as SQL Server can use fibers to improve performance, but unless the scheduling algorithm is extremely well tuned the performance will probably be lower than not using fibers. Unless you really need the last 10% of performance from a system, and you have a lot of time available, fibers are not something that you should be overly concerned with other than just to be aware of their existence.

2.3

Managed threads

A managed thread is represented by the System.Threading.Thread class. In the .NET Framework 1.0 and 1.1 managed threads map directly onto an OS thread, however this is not guaranteed to be the case in the future, particularly when hosted in an environment such as SQL Server 2005 in fiber mode. Note that the .NET Framework also has the System.Diagnostics.ProcessThread class which represents an OS thread although this is not particularly useful for multi-threaded programming. There is no relationship between the Thread and ProcessThread classes and you cannot get an instance of one from the other. Every one of the main .NET languages can create and control managed threads explicitly, for example:

18 March 2005

Fundamentals of Concurrent Programming for .NET Charteris White Paper

Page 4 of 30

static void Main(string[] args) { //create and start the thread Thread t = new Thread(new ThreadStart(SayHello)); t.Start(); //wait for the thread to finish t.Join(); Console.WriteLine("Complete"); } static void SayHello() { Console.WriteLine("Hello World"); }

All programs have a main application thread and in .NET applications this is the thread that runs the Main method. When a thread reaches the end of the method it starts in, the thread exits – if the thread is the main application thread then normally the application will exit when it reaches the end of the Main method. In the above sample, the main application thread starts a new thread to run the SayHello method and then calls Join on it which is a blocking call that waits for the thread to exit. The thread t runs the SayHello method, reaches the end and then exits, so at this point the Join method returns and the execution of Main continues. You may have noticed that I said an application normally exits when the Main method ends – this is governed by whether other threads that were created are foreground or background. Foreground threads and background threads are identical, however it is when all foreground threads have stopped that the application exits, so if the main application thread created any foreground threads that are still running the process will not exit until they do; at this point any background threads will be terminated. The Thread class has an IsBackground property to set this (note that it can be set even once the thread has started) and you should be aware that it defaults to false. A final important point to consider with respect to starting new threads is security. When you create a new thread it is created with the same Code Access Security (CAS) state as the thread that created it – this is important as it means partially trusted code cannot create new threads with full trust, but it also means that the results of any assert, demand, deny etc. operations for privileges that have been made on the original thread are propagated to the new thread.

2.4

The managed thread pool

Each OS thread that is created has supporting resources such as registers and its own execution stack which consumes memory. Because of this threads are relatively expensive resources to create and run. To simplify the process of creating and managing your own threads, the .NET Framework provides the System.Threading.ThreadPool class which is a pool of threads on which work can be queued to be asynchronously executed. The ThreadPool class automatically tunes the number of threads it contains based on factors such as how much work is queued and CPU utilisation. The following code shows how to queue a method call to run in the managed thread pool. static void Main(string[] args) { //queue the item bool queued = ThreadPool.QueueUserWorkItem(new WaitCallback(SayHello)); Console.WriteLine("Queued? {0}", queued); //sleep to wait for it to complete Thread.Sleep(1000); Console.WriteLine("Complete"); } static void SayHello(object state) { Console.WriteLine("Hello World"); }

18 March 2005

Fundamentals of Concurrent Programming for .NET Charteris White Paper

Page 5 of 30

Here the work is queued in the thread pool using QueueUserWorkItem and it will execute at some point in the future. The static call Thread.Sleep always applies to the thread that is running the method it is called from, in this case the main application thread, and causes it to pause for the specified number of milliseconds – here 1000 is chosen as an arbitrary value that should give the thread pool item long enough to execute. Note that the actual number of milliseconds the thread pauses for may not be exactly the number specified as it depends on the OS thread scheduler but experience shows it will normally be within about ten or twenty milliseconds either way. The ThreadPool class also provides a method RegisterWaitForSingleObject which allows you to queue an item in the same way, but have it wait for a WaitHandle to be signalled or a timeout to elapse before the code executes; wait handles will be discussed later in this paper. In the same way as managed threads, the CAS state is propagated to the thread pool thread when you queue it using QueueUserWorkItem or RegisterWaitForSingleObject so these can be used safely from both fully and partially trusted code. The ThreadPool class also provides complimentary methods, UnsafeQueueUserWorkItem and UnsafeRegisterWaitForSingleObject, which can only be called from fully trusted code and do not propagate the CAS state – these provide superior performance but have a potential security hole in that partially trusted code could be queued up and run with full trust. Unless you find from performance testing that the safe methods are a bottleneck, I would suggest that you leave the unsafe versions alone.

2.5

Asynchronous method invocation

In addition to managed threads and the thread pool, the .NET Framework allows applications to execute concurrently by means of asynchronous method invocation. These may be predefined asynchronous operations provided by the objects being used, or may be created manually by users of any library. Note that some predefined operations and all user-defined asynchronous operations execute in the managed thread pool behind the scenes, so may be queued rather than executing immediately.

2.5.1

Predefined asynchronous operations

If you have ever created a web reference, you will see that the generated proxy has not only the methods defined by the web service (e.g. GetCustomerData) but also asynchronous versions of these which follow the naming convention BeginMethod and EndMethod (e.g. BeginGetCustomerData and EndGetCustomerData). Calling a web service synchronously to look up both customer and order details may look something like the following: void DisplaySummary(int customerId) { LookupService svc = new LookupService(); CustomerDetails cd = svc.GetCustomerData(customerId); OrderDetails od = svc.GetOrderData(customerId); Console.WriteLine("Name: {0}, Total Orders: {1}", cd.Name, od.TotalOrders); }

The problem here is that the method first waits for one web service to complete, and then calls the other one – each of these may take a couple of seconds to do the lookup and return the information. This method can be significantly enhanced by using the asynchronous versions to call the web services in parallel, e.g. void DisplaySummary(int customerId) { //start the lookups asynchronously LookupService svc = new LookupService(); IAsyncResult custResult = svc.BeginGetCustomerData(customerId, null, null); IAsyncResult orderResult = svc.BeginGetOrderData(customerId, null, null); //end the lookups and display the results CustomerDetails cd = svc.EndGetCustomerData(custResult); OrderDetails od = svc.EndGetOrderData(orderResult); Console.WriteLine("Name: {0}, Total Orders: {1}", cd.Name, od.TotalOrders); }

18 March 2005

Fundamentals of Concurrent Programming for .NET Charteris White Paper

Page 6 of 30

Here the lookups are started together and run in parallel. The EndMethod calls block until the method has completed and so this method will block until both the lookups are done, then display the information. If each lookup takes two seconds then this method could now run in a total of two seconds instead of four when the services are called in sequence.

2.5.2

User-defined asynchronous operations

User-defined asynchronous operations work in exactly the same way as the predefined ones, except that you need to create the infrastructure for the BeginMethod and EndMethod calls yourself. This is done using the System.MulticastDelegate class (implemented with the delegate keyword in C#) – a delegate is similar to a C++ function pointer, except that it is type safe and references not only the method but the instance of the object it will be called on. Say the lookup methods for customers and orders were not web service methods but were defined in an external library which does not contain asynchronous versions; you can create the same effect as follows: //declare delegates that match the method signatures being called delegate CustomerDetails CustomerLookup(int customerId); delegate OrderDetails OrderLookup(int customerId); void DisplaySummary(int customerId) { LookupClass lookup = new LookupClass(); //create the delegates CustomerLookup custLookup = new CustomerLookup(lookup.GetCustomerData); OrderLookup orderLookup = new OrderLookup(lookup.GetOrderData); //start the lookups asynchronously IAsyncResult custResult = custLookup.BeginInvoke(customerId, null, null); IAsyncResult orderResult = orderLookup.BeginInvoke(customerId, null, null); //end the lookups and display the results CustomerDetails cd = custLookup.EndInvoke(custResult); OrderDetails od = orderLookup.EndInvoke(orderResult); Console.WriteLine("Name: {0}, Total Orders: {1}", cd.Name, od.TotalOrders); }

The code is very similar to the web method invocation, except that here you are defining and creating instances of delegates which reference the methods, and then run those delegates asynchronously. The BeginInvoke and EndInvoke methods on the delegate instance are created by the compiler and as such have a method signature that matches the synchronous method, with additional parameters added for a callback and a state obect. Using this technique you can invoke any method asynchronously, though bear in mind that it is slower to execute a method asynchronously so it is only worth doing if the concurrency gains outweigh the overhead incurred.

2.6

Events and multicast delegates

One of the common misconceptions about events is that they give you concurrency and that the handlers run in the managed thread pool. Events run sequentially and on the same thread that raised the event. This is because underneath an event is really just a wrapper around an instance of the System.MulticastDelegate class and as such is subject to its behaviour. A multicast delegate is a delegate that allows multiple handlers to be registered. When the delegate is invoked, all of the handlers are executed in the order that they were registered. The EventArgs object that is passed to the handlers may be modified, and the modified version will be received by the next handler in the chain (for this reason it is a good idea to make your EventArgs classes immutable unless you want this to occur). The following code demonstrates the pattern of event execution when a number of handlers are registered to receive the event: 18 March 2005

Fundamentals of Concurrent Programming for .NET Charteris White Paper

Page 7 of 30

delegate void MyEventHandler(object sender, TestEventArgs e); class TestEventArgs : EventArgs { public int Count; } class EventClass { event MyEventHandler TestEvent; public void RaiseEvent(int handlers) { for (int i = 0; i < handlers; i++) { this.TestEvent += new MyEventHandler(this.IncrementCount); } TestEventArgs e = new TestEventArgs(); Console.WriteLine( "Method: thread {0}, count {1}", Thread.CurrentThread.GetHashCode(), e.Count); this.TestEvent(this, e); //raise the event Console.WriteLine( "Method: thread {0}, count {1}", Thread.CurrentThread.GetHashCode(), e.Count); } void IncrementCount(object sender, TestEventArgs e) { e.Count++; Console.WriteLine( "Handler: thread {0}, count {1}", Thread.CurrentThread.GetHashCode(), e.Count); } }

The print out from this when invoked with three handlers is shown below (note that the value for the thread may be different on your system, but the hash code of a thread is guaranteed to be unique for the lifetime of that thread). This shows beyond doubt that the handlers are executed sequentially before control is returned to the method raising the event. Method: thread 2, count 0 Handler: thread 2, count 1 Handler: thread 2, count 2 Handler: thread 2, count 3 Method: thread 2, count 3

The predictable behaviour of events is necessary for many scenarios such as closing a Windows Form where the Closing event is raised with a CancelEventArgs argument – this allows handlers to set the Cancel property of this to true, and then the method that raised the event can check this property and decide whether to continue closing the form.

2.7

Summary

The .NET Framework provides powerful mechanisms for writing concurrent applications. It allows you to create and manage your own threads, queue work packages into a self-tuning thread pool, and execute methods asynchronously using either pre-defined functions of by creating your own delegate wrappers around the functions. Events in the .NET Framework do not give you concurrency which is not what a lot of people expect as they are used to the asynchronous publisher/subscriber model from environments such as COM+.

18 March 2005

Fundamentals of Concurrent Programming for .NET Charteris White Paper

Page 8 of 30

3.

THREAD SYNCHRONIZATION

3.1

Overview

When writing multi-threaded applications there is an almost universal need to access shared data from different threads. Without some form of synchronization between the threads the data would certainly be corrupted as one thread may overwrite parts of the data that another thread is busy reading, or two threads may change the same value at the same time so one of the changes is lost – this is known as a race condition. The most common approach to synchronizing the threads is through the use of locks. In lock-based programming the general principle is that an object is used as a lock, and the thread must acquire this object before it can execute a particular region of code that reads or modifies shared data; this protected region is known as a critical section. There is another approach which is gathering momentum known as lock-free programming, which as the name suggests does not use locks at all, although it has little mainstream value at the moment and as such is not discussed in this paper (there are however a number of references in Appendix A if you would like to find out more).

3.2

The .NET memory model

Before discussing synchronization mechanisms it is necessary to take a brief look at the .NET memory model to understand how it affects them. In order to make applications run faster, instructions such as reads and writes may be re-ordered by either compilers or hardware according to a set of rules. The rules for the .NET Framework can be summarised as follows: ♦ Reads and writes from the same processor to the same location cannot cross one another. ♦ No memory read (volatile or regular to any memory location), can move before a lock acquire. ♦ No memory write (volatile or regular to any memory location), can move after a lock release. ♦ All other reads and writes can reorder arbitrarily such that within a single thread of execution all side effects and exceptions are visible in the order specified (note that volatile reads and writes are considered side effects). Be aware that in these rules the only lock that is considered is the System.Threading.Monitor class; any other type of locking mechanism does not provide any guarantees about instruction reordering.

3.2.1

Volatile reads and writes

A volatile field (declared as volatile in C#) is always read and written such that any changes are immediately visible to any thread on any processor. It also disables certain optimisations like restricting the way instructions around the fields may be re-ordered. Because of the restrictions around volatile fields, accessing them is orders of magnitude slower than non-volatile fields and therefore avoiding their use unless they are absolutely necessary is good for performance. In some cases, for example when a variable is initialised only once, it may be beneficial to use one of the static methods on the Thread class to mimic volatility. This class provides VolatileRead and VolatileWrite which perform volatile reads and writes respectively, and also MemoryBarrier which causes all data that has been written up to that point (both volatile and non-volatile fields) to be visible to all threads on all processors – the use of MemoryBarrier is illustrated throughout the remainder of this paper.

3.3

Monitor and the C# lock statement

The most basic and common type of synchronization uses the System.Threading.Monitor class; it is so commonly used that many languages have keywords to encapsulate the major functions Enter and Exit (lock in C#, SyncLock in Visual Basic .NET). An object is designated as the lock object; the monitor obtains a lock on this for the duration of the critical section and then releases it at the end. To illustrate the use of the lock statement, consider the process of adding an item to a collection. The following code sample illustrates a method for doing this that is not thread-safe (note that code relating 18 March 2005

Fundamentals of Concurrent Programming for .NET Charteris White Paper

Page 9 of 30

to error checking, resizing the collection etc. is not shown throughout this paper as the aim is to illustrate threading issues rather than how to implement fully functional code). public class MyCollection { private readonly object syncRoot = new object(); private int count = 0; private object[] items = new object[16]; public int Add(object item) { int index = this.count; this.items[index] = item; this.count++; return index; } }

To add the item there are two changes to the class state required: the object must be inserted into the array of items and the count must be incremented. If two threads could execute this code at the same time then a possible sequence of events might be as follows: 1. Thread “A” gets the index and stores the item. 2. A context switch occurs to let thread “B” run. 3. Thread “B” gets the index and stores the item. 4. Thread “B” increments the count and returns the index. 5. A context switch occurs to let thread “A” run. 6. Thread “A” increments the count and returns the index. In this case, both threads store their items at the same index in the array, so the item that was written by thread “A” is lost. In addition, both threads increment the count so now the count is actually one more than the number of items in the collection. To make this method thread-safe we could rewrite it as follows using the Monitor class: public int Add(object item) { int index; Monitor.Enter(this.syncRoot); try { index = this.count; this.items[index] = item; this.count++; } finally { Monitor.Exit(this.syncRoot); } return index; }

The code between Monitor.Enter and Monitor.Exit is a critical section, enclosed by a lock on the private object syncRoot. There are a couple of important points in this code: ♦ The lock is taken on a private object, not a publicly visible object such as the class itself. It is quite common to see statements such as lock(this) in code, which can lead to major problems if another (possibly totally unrelated) class decides also to lock on the class instance. Even worse is locking on types, e.g lock(typeof(MyCollection)), which is commonly used for static methods – types are app-domain agile so you may be inadvertently locking a type in another app-domain! ♦ The lock is released in a finally block to ensure that even under error conditions it is released. If the lock was not released then no other thread could ever enter this method. 18 March 2005

Fundamentals of Concurrent Programming for .NET Charteris White Paper

Page 10 of 30

Using the C# lock keyword this method can be simplified significantly. The following code will be expanded by the compiler to be exactly equivalent to the above method: public int Add(object item) { int index; lock (this.syncRoot) { index = this.count; this.items[index] = item; this.count++; } //lock is released here even under error conditions return index; }

It is important to note that it is not only the Add method that must be synchronized – the collection is also likely to have other operations such as a Count property, an indexer, and IndexOf and Remove methods, each of which need to be synchronized. When synchronizing each of these the same lock object must be used as otherwise although the Add method would be synchronized the Remove method could alter the state in parallel. Correctly synchronized IndexOf and Remove methods are shown below: public int IndexOf(object item) { int index = -1; lock (this.syncRoot) { for (int i = 0; i < this.count; i++) { if (object.Equals(item, this.items[i])) { index = i; break; } } } return index; } public void Remove(object item) { lock (this.syncRoot) { int index = this.IndexOf(item); if (index != -1) { this.RemoveAt(index); //implementation not shown } } }

These methods lead to a final interesting point about the Monitor class. Note that when Remove is called it takes a lock, and then calls IndexOf, which also takes a lock on the same object. This works because a thread is allowed to lock the same object multiple times; it is only other threads that cannot acquire the lock. Note though that the thread must release the lock as many times as it acquires it because the .NET Framework tracks the number of time a lock has been taken on an object, not just whether it is locked.

3.4

MethodImplOptions.Synchronized

The .NET Framework includes the System.Runtime.CompilerServices.MethodImplAttribute attribute, which can be used with the enumeration value MethodImplOptions.Synchronized to indicate to the compiler that access to the entire method should be synchronized. This is, in effect, a declarative way to use the Monitor class to synchronize access to the method without any need for imperative programming, e.g. 18 March 2005

Fundamentals of Concurrent Programming for .NET Charteris White Paper

Page 11 of 30

[MethodImpl(MethodImplOptions.Synchronized)] public int Add(object item) { int index = this.count; this.items[index] = item; this.count++; return index; }

The behaviour of applying the Synchronized option to a method is not adequately described in MSDN because it does not describe what it is synchronizing with respect to. The answer, which is defined in the ECMA specification, is that the lock object is either the this pointer for instance methods, or the Type of the class for static methods. As noted previously both of these are bad practice so I recommend you avoid this form of synchronization. The tricky thing about avoiding this synchronization method, however, is that you may not realise you are using it! If you use the short form of event declaration in C#, as shown below, then the compilergenerated methods to add and remove handlers are automatically synchronized using this method. public event EventHandler MyEvent;

//short form of event syntax

There is no requirement in the ECMA specification for this behaviour; my assumption is that it is done as a reasonable compromise for the concise syntax as it is better to lock on the class type or instance than nothing in a multi-threaded environment. The good news is that if you want to be really safe you can explicitly code your own methods to add and remove handlers (which will not automatically be made synchronized) and lock on a private object in those: private readonly object syncRoot = new object(); private EventHandler myEvent; public event EventHandler MyEvent //full form of event syntax { add { lock (this.syncRoot) { this.myEvent = (EventHandler)Delegate.Combine(this.myEvent, value); } } remove { lock (this.syncRoot) { this.myEvent = (EventHandler)Delegate.Remove(this.myEvent, value); } } }

3.5

ReaderWriterLock

For objects which store state that is retrieved more often that it is written to, such as a Hashtable mainly used for lookups, the Monitor class may not be the most efficient way of controlling access. The System.Threading.ReaderWriterLock class allows multiple threads to read state concurrently, or a single thread to write state. For example, the previously considered Add and IndexOf methods could be synchronized with a ReaderWriterLock as shown below: public class MyCollection { private readonly ReaderWriterLock rwlock = new ReaderWriterLock(); private int count = 0; private object[] items = new object[16]; public int Add(object item) { int index; this.rwlock.AcquireWriterLock(Timeout.Infinite);

18 March 2005

Fundamentals of Concurrent Programming for .NET Charteris White Paper

Page 12 of 30

try { index = this.count; this.items[index] = item; this.count++; Thread.MemoryBarrier(); } finally { this.rwlock.ReleaseWriterLock(); } return index; } public int IndexOf(object item) { int index = -1; this.rwlock.AcquireReaderLock(Timeout.Infinite); try { for (int i = 0; i < this.count; i++) { if (object.Equals(item, this.items[i])) { index = i; break; } } } finally { this.rwlock.ReleaseReaderLock(); } return index; } }

As when using the Monitor class, the lock is released in a finally block to ensure that even under error conditions it is always released. In this collection either multiple threads can retrieve the index of an item simultaneously, or exactly one thread can add an item. Note that I have used a memory barrier in the Add method to ensure that all writes occur before the writer lock is released as ReaderWriterLock does not provide the same guarantees about writes not crossing the lock boundary as Monitor. Note that reader and writer threads waiting for the lock are queued separately. When a writer lock is released, all queued reader threads at that instant are granted reader locks. When all of those reader locks have been released the next writer thread in the writer queue is granted a writer lock. This alternating behaviour between a collection of readers and a single writer ensures fairness in accessing the resource, and that neither reader nor writer threads are starved of access.

3.6

Wait handles

A wait handle is a synchronization object that uses signalling to control the progress of threads rather than a lock object. The .NET Framework 1.0 and 1.1 provide three types of wait handle in the System.Threading namespace – Mutex, ManualResetEvent and AutoResetEvent – all of which derive from the abstract base class System.Threading.WaitHandle. Version 2.0 also provides a Semaphore class; if you do not have access to this then I have provided a code listing for a semaphore in Appendix B which has a similar public interface and behaviour. All wait handles have a commonality in that you can call the instance method WaitOne to wait for that particular instance, or the WaitHandle class has static methods WaitAll and WaitAny to wait for all or any of a number of wait handles respectively – note that the wait handles may be different types. The different behaviours of the wait handles will be discussed in the context of the instance method WaitOne ; the behaviour of the static methods can be inferred from this. 18 March 2005

Fundamentals of Concurrent Programming for .NET Charteris White Paper

Page 13 of 30

When using any of the wait handles remember that they all implement the System.IDisposable interface so you must make any class that holds one as a member also implement the disposable design pattern and close the wait handle when the class is disposed.

3.6.1

Mutex

The System.Threading.Mutex class serves much the same purpose as the Monitor class, in that it is designed to allow only one thread to execute a piece of code at any one time, but Mutex can be passed between app-domains and even used between processes. Note, however, that Mutex does not provide the same guarantees of read and write ordering as Monitor so you need to use a memory barrier when changing shared resources. The following code shows how the Add method of a collection could be written using Mutex. public class MyCollection : IDisposable { private readonly Mutex mutex = new Mutex(); private int count = 0; private object[] items = new object[16]; public int Add(object item) { int index; this.mutex.WaitOne(); try { index = this.count; this.items[index] = item; this.count++; Thread.MemoryBarrier(); } finally { this.mutex.ReleaseMutex(); } return index; } }

The

WaitOne method is called on mutex which blocks until it is signalled by another thread calling ReleaseMutex ; when this call returns the thread that called it owns the mutex. Similarly to the other synchronization objects, always call the ReleaseMutex method in a finally block to ensure it is called even under error conditions. ReleaseMutex must be called by the same thread that was released by WaitOne otherwise a System.ApplicationException is thrown.

To use a mutex between processes it must be a named instance, not an anonymous one as shown above; the name may be specified in the constructor. A common use of named mutexes is to only allow one instance of a process to run at any one time, as shown below: class Program { private static readonly Mutex mutex; static void Main(string[] args) { bool createdMutex; mutex = new Mutex(false, "MyApplicationName", out createdMutex); if (!createdMutex) { Console.WriteLine("An instance of this app is already running."); return; } //run the program here } }

18 March 2005

Fundamentals of Concurrent Programming for .NET Charteris White Paper

Page 14 of 30

It is worth mentioning that this type of code is potentially open to denial-of-service attacks; if malicious code can guess the name of the mutex then it could create it beforehand and not allow any instances of your process to run.

3.6.2

ManualResetEvent and AutoResetEvent

and AutoResetEvent are used to allow threads to synchronize with each other by signaling; they still call WaitOne to enter the protected section, but unlike Mutex they do not own the lock when this method has returned – any thread can signal the event at any time. ManualResetEvent

A ManualResetEvent or AutoResetEvent has two possible states: signalled and non-signalled. When the event is in the signalled state the WaitOne method returns immediately and when it is in the nonsignalled state it blocks. To make the event signalled the Set method is called and to make the event non-signalled Reset is called. The difference between the two classes is that when WaitOne returns on AutoResetEvent it automatically resets itself into the non-signalled state, thus releasing only a single thread, whereas ManualResetEvent stays signalled until Reset is called. The following sample shows how a ManualResetEvent might be used to cancel a long running calculation which uses multiple independent threads to iteratively find the optimal solution to a problem. class StochasticSearch { private ManualResetEvent stopEvent = new ManualResetEvent(false); private Thread[] threads; public void Start(int threadCount) { this.stopEvent.Set(); this.threads = new Thread[threadCount]; for (int i = 0; i < this.threads.Length; i++) { this.threads[i] = new Thread(new ThreadStart(this.DoCalculation)); this.threads[i].Start(); } } public void Stop() { this.stopEvent.Reset(); for (int i = 0; i < this.threads.Length; i++) { this.threads[i].Join(); } } private void DoCalculation() { while (stopEvent.WaitOne()) { //one iteration of a really long running calculation } } }

Finally a word of warning – many articles I have read use these events to attempt to protect a critical section where different threads read and write a shared resource. The general pattern is that they call Reset on the writer thread and then start changing the shared resource believing that it is protected as the reader threads will no longer be using it. However, reader threads that called WaitOne just before the Reset may already be using the resource, and calling Reset on the event will have no effect on them, so there may still be threads still using the resource while you change it! If you are trying to protect a critical section do not use ManualResetEvent or AutoResetEvent, use one of the objects designed for that purpose such as Monitor, ReaderWriterLock or Mutex.

18 March 2005

Fundamentals of Concurrent Programming for .NET Charteris White Paper

Page 15 of 30

3.6.3

Semaphore

A Semaphore is used to limit the number of threads simultaneously accessing a resource; generally this will be when more than one thread can simultaneously access the resource as otherwise a Mutex would be more appropriate. As such, a semaphore is normally used to control access to read-only resources. A semaphore is created with an initial count and a maximum count. When the WaitOne method is called, if the count is greater than zero the count is decremented and the method returns, else if the count is zero then the method will block until it times out or Release is called on the semaphore by another thread (which increments the count by a specified number). The following class shows how an application might limit the number of users logged in at any one time. When the user logs in StartSession is called, and if the count is greater than zero then true is returned, else false is returned indicating that the maximum number of users are already logged in. When the user logs out FinishSession is called to increment the count on the semaphore. public class UserManager { private static Semaphore semaphore = new Semaphore(10, 10); public static bool StartSession(int timeout) { return semaphore.WaitOne(timeout, false); } public static void FinishSession() { semaphore.Release(); //releases a single count } }

It is important that the client code calling these methods does so in the same try/finally pattern as with other synchronization mechanisms to ensure that an acquired lock is always released, e.g. void RunSession() { if (UserManager.StartSession(1000)) { try { //run the session } finally { UserManager.FinishSession(); } } else { Console.WriteLine("Maximum number of users already logged on."); } }

3.7

Interlocked

The System.Threading.Interlocked class is not designed to protect critical sections, but is for simple atomic operations such as incrementing/decrementing values and exchanging the values of items. Note that the results of all methods on the Intelocked class are immediately visible on all threads on all processors, so no lock or memory barrier is needed.

3.7.1

Increment and Decrement

These are used simply to increment or decrement a value in an atomic and thread-safe manner; in addition it returns the previous value of the item before the increment or decrement occurred. The following code shows an example:

18 March 2005

Fundamentals of Concurrent Programming for .NET Charteris White Paper

Page 16 of 30

int counter = 0; int previous = Interlocked.Increment(ref counter); //do something with the original value

3.7.2

Exchange and CompareExchange

The Exchange method allows you to exchange one item for another, and also retrieve the previous value of the item, all as an atomic operation. object original = new object(); object replacement = new object(); object previous = Interlocked.Exchange(ref original, replacement); //do something with the previous value

Note that the usefulness of this method is somewhat limited by the fact that the original object is passed as a reference parameter and therefore must be exactly of type int, float or object (the three types allowed by overloads of the method in .NET 1.0 and 1.1), it cannot be a type derived from them. The following code will fail to compile with error CS1503 (cannot convert type ‘ref MyObject’ to ‘ref object’). MyObject original = new MyObject(); MyObject replacement = new MyObject(); MyObject previous = (MyObject)Interlocked.Exchange(ref original, replacement);

The CompareExchange method is very similar to Exchange, except it also allows you to compare the item to another to see if the exchange should occur, also as an atomic operation. If the value already stored does not match the comparand the exchange does not happen. The following code only changes the original value if it is equal to 1234: int original = 1234; int comparand = 1234; int replacement = 5432; int previous = Interlocked.CompareExchange(ref original, replacement, comparand); //do something with the previous value

Again the CompareExchange method is limited by the fact that the original object is passed as a reference parameter. It would seem logical to include generic versions of these methods in .NET 2.0 and later (i.e. Interlocked.Exchange and Interlocked.CompareExchange ) but they are not evident at the time of writing.

3.8

Summary

The .NET Framework provides many different ways to synchronize threads including basic locks, attributes, reader/writer locks, mutexes, signalled events, semaphores and interlocked operations. Each has its benefits, drawbacks and limitations so it is important to choose the correct mechanism to suit each place in your application. Concurrency in .NET is made more difficult by the weak memory model; one of the consequences of it is that only Monitor and Interlocked guarantee to make the results of any changes made to shared resource visible to all other threads, so with any other synchronization method you must use a memory barrier to manually achieve this effect before releasing the lock.

18 March 2005

Fundamentals of Concurrent Programming for .NET Charteris White Paper

Page 17 of 30

4.

DESIGN CONSIDERATIONS

4.1

Nondeterministic execution

One of the features of concurrent applications is that they have nondeterministic execution; that is the control flow of the application could be different each time the application is run. The code sample below illustrates nondeterministic execution as there is no way of knowing the order in which the files in the source directory will be copied to the destination directory, or by which thread. class MultiThreadedCopy { private string destination; private int index; private string[] files; public void CopyDir(string source, string destination, int threadCount) { this.destination = destination; this.index = 0; this.files = Directory.GetFiles(source); Thread.MemoryBarrier(); //ensure the values are set across all CPUs Thread[] threads = new Thread[threadCount]; for (int i = 0; i < threads.Length; i++) { threads[i] = new Thread(new ThreadStart(this.CopyThreadStart)); threads[i].Start(); } for (int i = 0; i < threads.Length; i++) { threads[i].Join(); } } void CopyThreadStart() { int i; while ((i = Interlocked.Increment(ref this.index)) < this.files.Length) { //copy the file at the index i in the array of files } } }

In some cases such as this sample it may not matter that the execution is nondeterministic however in other cases the output may have to be deterministic – for example if this application split each file into sections and used multiple threads per file then it would be important that the sections of the file were reassembled in the same order! The overall execution of any multi-threaded application will be nondeterministic because it depends on factors outside the control of the programmer such as thread scheduling and often user input or communication with external applications. Nonetheless, it is important to understand whether any portions of the application do require deterministic execution and use appropriate means to ensure this; the easiest way is to write that portion as single threaded but if it is in a performance critical area then more involved approaches may be required.

4.2

Deadlocks

A deadlock is a condition where two or more threads are blocked, each waiting for the other to take some action. Deadlocks arise primarily as a result of a single shared resource having two or more locks that protect it and where two threads have each acquired one of the locks and are waiting for the other thread to release the other lock so they can continue. The following code shows a class where this situation could arise.

18 March 2005

Fundamentals of Concurrent Programming for .NET Charteris White Paper

Page 18 of 30

class SymbolTable { private BinaryTree tree = new BinaryTree(); private Hashtable table = new Hashtable(); public int Add(Symbol symbol) { lock (this.tree) { lock (this.table) { //add the symbol } } } public void Remove(Symbol symbol) { lock (this.table) { lock (this.tree) { //remove the symbol } } } }

This class has two data structures, a binary tree and a hashtable, and provides methods to add and remove an item from them. The Add method first locks tree then table, whereas the Remove method locks table then tree. If two threads were to execute these methods simultaneously then Add could lock tree and Remove could lock table; at this point each thread would be waiting for the other to release the resource it is trying to lock on and neither thread can continue – this is a deadlock. In the above example it is quite easy to see how the deadlock can arise and the fix is also simple, just change both methods to always lock the objects in the same order and then no deadlock can arise. Unfortunately it isn’t always this simple to find the issue: sometimes locks are taken in different methods and held while other methods are called, for example: class Table { private readonly object syncRoot = new object(); private View view; public void Update() { lock (this.syncRoot) { this.view.Update(); } } } class View { private readonly object syncRoot = new object(); private Table table; public void Update() { lock (this.syncRoot) { this.table.Update(); } } }

18 March 2005

Fundamentals of Concurrent Programming for .NET Charteris White Paper

Page 19 of 30

Here either class may have the Update method called, but as each class is independently thread-safe and passes the call through to the Update method of the other class while still holding the lock a deadlock may arise. Although it is more disguised than above this problem still comes down to the fact that locks on resources are not obtained in the same order. To mitigate the risk of deadlocks it is important to consider not only what locks a single class is taking, but also what locks may be taken in the period those locks are held, particularly if any external methods are called. For any locks that have dependencies on each other, a strategy needs to be agreed on about the order in which the locks will be taken.

4.3

Suspending, resuming and aborting threads

The System.Threading.Thread class provides the methods Suspend, Resume and Abort which pause the thread, make it resume after a pause, and abort it respectively. In general you should not use these methods; they lead to all types of problems such as deadlocks and errors which cannot be recovered from. Consider a thread that is running a static constructor while it is suspended. Because a type, or any instances of it, cannot be used until the static constructor has completed running, any code that tries to use this type will block. In the best case a couple of other threads may block for a while, the thread running the static constructor is resumed, and all continues normally. In the worst case, the thread that was going to resume the one running the static constructor tries to access the type and it blocks – this is a deadlock condition as each thread is waiting on the other one before it can continue. In an even worse scenario, consider that the thread running the static constructor is aborted. Aborting a thread in .NET does not just stop it immediately as you might expect, it actually throws a System.Threading.ThreadAbortException onto the thread being aborted, and so the static constructor will throw an exception thus rendering the type unusable and ensure no instances of it can ever be created. Remember that types are app-domain agile so you may not be affecting just the appdomain that the thread is aborted in! There is an additional problem with calling Abort on a thread, which is concerned with clean-up. When a thread is aborted then as an exception is thrown on the thread, catch and finally blocks are executed as normal – except if it is already executing one in which case it will jump straight out of the block and quite possibly not finish your clean-up. Below is an example where this could cause an unrecoverable situation: public int Add(object item) { int index; Monitor.Enter(this.syncRoot); try { index = this.count; this.items[index] = item; this.count++; } finally { //thread aborted here: ThreadAbortException thrown onto the thread Monitor.Exit(this.syncRoot); } return index; }

If the thread is aborted and the exception is thrown where indicated, then the Monitor.Exit method will not execute and the lock will not be released. Unfortunately as the lock can only be released by the thread that acquired it, which has just been aborted, this lock will never be released and any thread that calls the Add method will block indefinitely. Fortunately there is generally no need to use the Suspend, Resume and Abort methods. Almost any thread synchronization that can be done with them can be done with wait handles, although it admittedly does need cooperation between the running threads rather than being controlled by just one 18 March 2005

Fundamentals of Concurrent Programming for .NET Charteris White Paper

Page 20 of 30

(for an example of using a wait handle to mimic Abort see section 3.6.2). One of the very few scenarios where using these methods is appropriate would be in a tool such as a unit test host where external code is run and the user may want to pause or abort the execution of it; as the tool has no control over the external code it could not use wait handles for this.

4.4

Placement of critical sections

Some of the sample code in this paper has been concerned with making a collection class safe for multi-threaded operation. One of the troubles with making a class thread-safe by default is that a lot of the time it may run in a single-threaded environment, and so by introducing code that ensures threadsafety you are adding overhead without adding any value. Because of this you should generally make all instance methods of your class not thread-safe by default. Note, however, that static methods should be thread-safe by default because this is the common design pattern in the .NET Framework and most people will expect them to be. Generally there is no extra work to make static methods thread-safe as usually they either do not access shared state or access read-only state and as such are intrinsically thread-safe. The desire to make classes fast and not thread-safe by default, but still allow them to be used easily in multi-threaded environments, led the .NET Framework designers to the pattern seen on many of the collections which have a static Synchronized method that returns a thread-safe copy of the collection. The design pattern is that the base method/property is virtual and the thread-safe wrapper class overrides it, adding synchronization code, as illustrated in the following sample: public class MyCollection { public virtual int Add(object item) { int index = this.count; this.items[index] = item; this.count++; return index; } public static MyCollection Synchronized(MyCollection collection) { return new MySyncCollection(collection); } private sealed class MySyncCollection : MyCollection { private readonly object syncRoot = new object(); private readonly MyCollection collection; public MySyncCollection(MyCollection collection) { this.collection = collection; } public override int Add(object item) { lock (this.syncRoot) { return this.collection.Add(item); } } } }

This initially seems like a great idea, until you realise that the collection isn’t actually thread-safe. Yes, each operation is, but the trouble is that the operations are often not used independently. Consider the following code, which uses a System.Collections.Queue to demonstrate.

18 March 2005

Fundamentals of Concurrent Programming for .NET Charteris White Paper

Page 21 of 30

Queue syncQueue = Queue.Synchronized(new Queue()); void ProcessNextItem() { if (syncQueue.Count > 0) { object item = syncQueue.Dequeue(); //do something with the item } }

If two threads call

ProcessNextItem

concurrently then the following sequence could occur:

1. Thread “A” checks the count, it is 1 and so it enters the if block. 2. A context switch occurs to let thread “B” run. 3. Thread “B” checks the count, it is 1 and so it enters the

if

block.

4. Thread “B” dequeues the item and processes it. 5. A context switch occurs to let thread “A” run. 6. Thread “A” tries to dequeue the item but throws an the queue is empty.

InvalidOperationException

because

This is a particularly nasty type of bug because it is very hard to reproduce, so may not be discovered until production. It is also conceptually hard to debug because the developer is operating under the impression that the queue is thread-safe, so how can it be subject to threading problems? As a point of interest, new collections such as generics introduced in .NET 2.0 do not have the design pattern to allow synchronized collections because this type of bug has been introduced so commonly as a result of it. There is also the additional drawback that the methods/properties on the collection have to be virtual and therefore suffer from slower calling due to v-table lookups, and the contents of the methods cannot be inlined by the JIT compiler. The queue example illustrates why placement of critical sections is so important if you are to avoid synchronization problems. They need to be localized enough in the code so that they are not held for excessive periods of time and are not synchronizing code that does not need it, but they also need to be at a high enough level that they have an awareness of the circumstances under which they are operating – putting a critical section in the Dequeue method is not high level enough as it is unaware that it is being called based on the value of the Count property. The code can be rewritten to be truly thread-safe by using manual locking as follows: Queue queue = new Queue(); void ProcessNextItem() { bool dequeued = false; object item = null; lock (queue) { if (queue.Count > 0) { item = queue.Dequeue(); dequeued = true; } } if (dequeued) { //do something with the item } }

Note that here the item variable is declared outside the lock statement so that the lock only needs to be held for the period of time it takes to check the count and dequeue the item; any processing on the item is not synchronized so concurrency will be increased. 18 March 2005

Fundamentals of Concurrent Programming for .NET Charteris White Paper

Page 22 of 30

4.5

The double-lock initialization pattern

The double-lock initialization pattern is probably the most commonly used design pattern in lockbased multi-threaded programming, and is used for the lazy initialization of singletons (a singleton is a class that can only ever have one instance of itself instantiated). Lazy initialization means that the class is not instantiated until the first time it is accessed, which amongst other things can help to improve start-up times for applications. The pattern attempts to improve concurrency by avoiding taking locks except for the single case where the singleton is initialized, as follows: public class MyObject { private static readonly object syncRoot = new object(); private static readonly MyObject singleton; private ConfigData config; private MyObject() { this.config = this.LoadConfiguration(); } public static MyObject Singleton { get { if (singleton == null) { lock (syncRoot) { if (singleton == null) { singleton = new MyObject(); } } } return singleton; } } }

It checks whether the singleton is null, then locks the lock object, checks that the singleton is not null again (as two threads could have simultaneously executed the first check but only one could have got the lock), and then initializes the object. While this seems like a good idea, and does in fact work on strongly ordered memory model processors like x86, it is not guaranteed to work by the .NET framework’s memory model so if your application runs on a processor with a similarly weak memory model such as Intel’s IA64 architecture then your application may break! The reason is that the assignment of the new object reference to singleton could occur before the constructor of MyObject has completed running, and because the next thread coming in does not take a lock before checking whether it is null it may see an un-constructed or partially-constructed object! Note that declaring the singleton as volatile will not help here because it is only the assignment of the reference that will be affected, the construction may still happen after: Expected Sequence:

Possible Sequence on IA64 or similar:

It is important to highlight here that the problem only arises because this pattern avoids taking locks – if you always take a lock before accessing a shared resource then your code is less likely to suffer from unexpected side effects. As such, the simplest way to fix this issue is to remove the outer null check; because reads and writes cannot pass a lock then this is guaranteed to work. A better way to fix it that keeps the ‘lock only on initialization’ semantics is to use a memory barrier (which reads and writes also cannot cross) to ensure that an instance of the object is fully constructed before it is assigned to the singleton, as shown below. 18 March 2005

Fundamentals of Concurrent Programming for .NET Charteris White Paper

Page 23 of 30

public class MyObject { private static object syncRoot = new object(); private static MyObject singleton; private ConfigData config; private MyObject() { this.config = this.LoadConfiguration(); } public static MyObject Singleton { get { if (singleton == null) { lock (syncRoot) { if (singleton == null) { MyObject temp = new MyObject(); Thread.MemoryBarrier(); singleton = temp; } } } return singleton; } } }

4.6

Raising events

The first section of this paper asserted that events in .NET do not provide concurrency, so it may be a surprise to see a section devoted to it in design considerations. The problem is that raising events in .NET is not thread-safe unless you use a specific pattern to do so. The common approach, which is not thread-safe, is as follows: delegate void MyEventHandler(object sender, MyEventArgs e); class MyConnection { event MyEventHandler Opened; public void Open() { //open the connection //ensure the event has subscribers if (this.Opened != null) { //raise the event this.Opened(this, new MyEventArgs()); } } }

The event raising syntax in C# requires that the event is compared to null to see if there are any handlers registered; if there are no handlers registered and you try to raise the event then a NullReferenceException is thrown. There is a subtle race condition here in that after the null check, all handlers for the event could be cleared before you raise it which would set it to null. Fortunately the fix is simple, you cache the event handler in a local scoped variable and then even if the actual event is cleared the local reference will not be set to null:

18 March 2005

Fundamentals of Concurrent Programming for .NET Charteris White Paper

Page 24 of 30

public void Open() { //open the connection MyEventHandler handler = this.Opened; if (handler != null) { handler(this, new MyEventArgs()); }

//cache the handler

}

4.7

Summary

This section has highlighted some of the key design considerations when writing concurrent applications. You must be aware that the overall execution of the application will be nondeterministic and that this could lead to deadlocks if the locking strategy is not well planned; in addition, it is important to ensure that any synchronization code is correctly placed. The reasons for not suspending or aborting threads has been highlighted, and a couple of common issues relating to the double-lock pattern and raising of events have been discussed – both of these are written incorrectly in the vast majority of code, but fortunately both have low-impact and prescriptive fixes.

18 March 2005

Fundamentals of Concurrent Programming for .NET Charteris White Paper

Page 25 of 30

5.

CONCLUSIONS

The .NET Framework provides powerful mechanisms for creating and controlling threads, and a number of classes which encapsulate common synchronization techniques are included in the base class library. In spite of this, it is not easy to write robust and performant concurrent applications and the difficulty is compounded by the relatively weak memory model specified for the .NET runtime. Problems in multi-threaded code can arise in many ways, from mistakes in code to unexpected side effects as a result of instruction reordering. Unfortunately due to the nondeterministic nature of multithreaded execution most of these problems will only arise sporadically when the application is under load, so if you have written an application that uses concurrency you need to undertake extensive load testing before the system goes live.

18 March 2005

Fundamentals of Concurrent Programming for .NET Charteris White Paper

Page 26 of 30

APPENDIX A REFERENCES To make the references easier to use I have divided them roughly into their main subjects. I can thoroughly recommend all books and articles referenced here; they are well worth reading if you really want to build robust, high performance and secure concurrent applications. General Reference MSDN Library, Various Contributors, 2005: http://msdn.microsoft.com MSDN Longhorn API Library, Various Contributors, 2005: http://longhorn.msdn.microsoft.com Common Language Infrastructure Partition I: Concepts and Architecture, Various Contributors, 2001: http://download.microsoft.com/download/f/9/a/f9a26c29-1640-4f85-8d0798c3c0683396/partition_i_architecture.zip Common Language Infrastructure Partition II: Metadata Definition and Semantics, Various Contributors, 2001: http://download.microsoft.com/download/3/f/b/3fb318cb -f60c-4128-ada8bbffb791046d/partition_ii_metadata.zip Processor Evolution The Free Lunch is Over: A Fundamental Turn toward Concurrency in Software, Herb Sutter, 2005: http://www.gotw.ca/publications/concurrency-ddj.htm Platform 2015: Intel Processor and Platform Evolution for the Next Decade, Various Contributors, 2005: ftp://download.intel.com/technology/computing/archinnov/platform2015/download/Platform_201 5.pdf Platform 2015 Software: Enabling Innovation in Parallelism for the Next Decade, David J. Kuck, 2005: ftp://download.intel.com/technology/computing/archinnov/platform2015/download/Parallelism.pd f Threading and Concurrency Hyper-Threading Technology, Intel Corporation, (undated): http://www.intel.com/business/bss/products/hyperthreading/overview.htm Introduction to Multithreading, Superthreading and Hyperthreading, (unnamed), 2002: http://arstechnica.com/articles/paedia/cpu/hyperthreading.ars Implementing Coroutines for .NET by Wrapping the Unmanaged Fiber API, Ajai Shankar, 2003: http://msdn.microsoft.com/msdnmag/issues/03/09/CoroutinesinNET/default.aspx Inside .NET Thread Pooling, Kumar Gaurav Khanna, 2002: http://www.wintoolzone.com/showpage.aspx?url=articles/dotnet_inside_threadpooling.aspx An Introduction to Programming with C# Threads, Andrew D. Birrell, 2003: http://research.microsoft.com/~birrell/papers/ThreadsCSharp.pdf Threads, fibers, stacks & address space, Chris Brumme, 2003: http://weblogs.asp.net/cbrumme/archive/2003/04/15/51351.aspx Asynchronous Operations, pinning, Chris Brumme, 2003: http://weblogs.asp.net/cbrumme/archive/2003/05/06/51385.aspx

18 March 2005

Fundamentals of Concurrent Programming for .NET Charteris White Paper

Page 27 of 30

Security & Asynchrony, Chris Brumme, 2003: http://weblogs.asp.net/cbrumme/archive/2003/05/08/51396.aspx Modern Concurrency Abstractions for C#, Nick Benton, Luca Cardelli, Cédric Fournet, 2004: http://research.microsoft.com/Users/luca/Papers/Polyphony%20(TOPLAS).pdf Questionable value of SyncRoot on Collections, Brad Abrams, 2003: http://blogs.msdn.com/brada/archive/2003/09/28/50391.aspx Events, Delegates and Multithreading, Brad Abrams, 2005: http://blogs.msdn.com/brada/archive/2005/01/14/353132.aspx Multi-Threaded applications and Abort, careful not to kill your statics…, Justin Rogers, 2004: http://weblogs.asp.net/justin_rogers/archive/2004/02/02/66537.aspx Asynchronous Command Execution in ADO.NET 2.0, Pablo Castro, 2004: http://msdn.microsoft.com/data/default.aspx?pull=/library/en-us/dnvs05/html/async2.asp .NET memory model Volatile and MemoryBarrier(), Brad Abrams, 2004: http://weblogs.asp.net/brada/archive/2004/05/12/130935.aspx The DOTNET Memory Model, Vance Morrison, 2002: http://discuss.develop.com/archives/wa.exe?A2=ind0203B&L=DOTNET&P=R375 Memory Model, Chris Brumme, 2003: http://blogs.msdn.com/cbrumme/archive/2003/05/17/51445.aspx Performance Improving .NET Application Performance and Scalability, Various Contributors, 2004: http://www.microsoft.com/downloads/details.aspx?FamilyId=8A2E454D-F30E-4E72-B53175384A0F1C47&displaylang=en Lock-free programming Concurrent Programming Without Locks, Keir Fraser, Tim Harris, 2004: http://www.cl.cam.ac.uk/Research/SRG/netos/papers/2004-cpwl-submission.pdf Lock-Free Parallel Algorithms: An Experimental Study, Guojing Cong, David Bader, 2004: http://www.eece.unm.edu/~dbader/papers/lockfree-HiPC2004.pdf Static Analysis of Atomicity for Programs with Lock-Free Synchronization, Liqiang Wang, Scott D. Stoller, 2005: http://www.cs.sunysb.edu/~liqiang/papers/lockfree_tr.pdf

18 March 2005

Fundamentals of Concurrent Programming for .NET Charteris White Paper

Page 28 of 30

APPENDIX B SEMAPHORE CODE LISTING This code listing shows how to write a semaphore if you need one for applications built on the .NET Framework versions 1.0 or 1.1. If you are using 2.0 or later then these already include a Semaphore class in the System.Threading namespace which I would recommend you use instead (the public interface is similar to this code listing to provide an easy migration path). Note that this code is a sample with no input checking or error handling, and is not intended as production quality code; as such you should review and test it thoroughly before using it. namespace { using using using using

Charteris.Samples.Threading System; System.Runtime.InteropServices; System.Security; System.Threading;

public sealed class Semaphore : WaitHandle { public Semaphore(int initialCount, int maximumCount) : this(initialCount, maximumCount, null) { } public Semaphore(int initialCount, int maximumCount, string name) { bool createdNew; this.Initialize(initialCount, maximumCount, name, out createdNew); } public Semaphore( int initialCount, int maximumCount, string name, out bool createdNew) { this.Initialize(initialCount, maximumCount, name, out createdNew); } private Semaphore(IntPtr handle) { base.Handle = handle; } public static Semaphore OpenExisting(string name) { IntPtr handle = NativeMethods.OpenSemaphore( NativeMethods.SYNCHRONIZE, true, name); if (handle == WaitHandle.InvalidHandle) { Marshal.ThrowExceptionForHR(Marshal.GetHRForLastWin32Error()); } return new Semaphore(handle); } public int Release() { return this.Release(1); } public int Release(int releaseCount) { int previousCount; NativeMethods.ReleaseSemaphore( base.Handle, releaseCount, out previousCount); return previousCount; } private void Initialize( int initialCount, int maximumCount, string name, out bool createdNew)

18 March 2005

Fundamentals of Concurrent Programming for .NET Charteris White Paper

Page 29 of 30

{ base.Handle = NativeMethods.CreateSemaphore( IntPtr.Zero, initialCount, maximumCount, name); if (base.Handle == WaitHandle.InvalidHandle) { Marshal.ThrowExceptionForHR(Marshal.GetHRForLastWin32Error()); } int errorCode = Marshal.GetLastWin32Error(); createdNew = (errorCode != NativeMethods.ERROR_ALREADY_EXISTS); } [SuppressUnmanagedCodeSecurity] private sealed class NativeMethods { internal const int ERROR_ALREADY_EXISTS = 183; internal const uint SYNCHRONIZE = 0x00100000; [DllImport("kernel32.dll", SetLastError = true)] internal static extern IntPtr CreateSemaphore( IntPtr lpSemaphoreAttributes, int lInitialCount, int lMaximumCount, string lpName); [DllImport("kernel32.dll", SetLastError = true)] internal static extern IntPtr OpenSemaphore( uint dwDesiredAccess, bool bInheritHandle, string lpName); [DllImport("kernel32.dll", SetLastError = true)] internal static extern bool ReleaseSemaphore( IntPtr hSemaphore, int lReleaseCount, out int lpPreviousCount); } } }

18 March 2005

Fundamentals of Concurrent Programming for .NET Charteris White Paper

Page 30 of 30