Coordination Data Structures Overview

Emad Omara

The June 2008 CTP of Parallel Extensions provides the first look at its 3rd major piece, a set of coordination data structures we lovably refer to as CDS. It contains lightweight and scalable thread-safe data structures and synchronization primitives.  There are of course already many synchronization primitives present in the System.Threading namespace of the .Net Framework, such as ManualResetEvent, Monitor, Mutex, and Semaphore: these types are still very useful for developing multithreading applications, and in fact Parallel Extensions relies on many of them, but sometimes higher-level or lighter-weight primitives are required to facilitate communications between threads.  CDS augments the existing types in System.Threading to provide just such primitives. Here is a brief introduction for each CDS type included in the June 2008 CTP.

ConcurrentStack<T> / CocncurrentQueue<T>
Generic, thread-safe LIFO stack and FIFO queue data structures. They impalement IConcurrentCollection<T>, a new interface providing thread-safe Add and Remove methods for adding a data element to a collection and removing a data element from a collection, according to the semantics of the implementing type.
Cistina already posted the ConcurrentStack<T> post

Since context switches and kernel transitions are relatively expensive operations, sometimes it’s beneficial and actually costs less to busy wait rather than to wait on a kernel synchronization primitive. SpinWait provides simple, correct, and efficient busy waiting.

Provides a locking mechanism based on spinning rather than based on waiting on kernel events. This can be useful in advanced scenarios where the critical region being protected is tiny and where it would be more costly to use heavier synchronization primitives like Monitor.

System.Threading already contains a ManualResetEvent that allows threads to wait on the event until it’s set by another thread. In common “fork/join” operations, where multiple pieces of asynchronous work are generated and where additional work can’t proceed until all of those forks have joined, a typical pattern is to initial a ManualResetEvent that a thread blocks waiting on, and also initial a count that is decremented every time one of the forked operations completes: when the count reaches 0, the event is set. CountdownEvent encapsulates this pattern.  It is initialized with a count (this count can also be increased with its Increment method), and when work items complete they can call to its Decrement method.  When the internal count reaches 0, the CountdownEvent is set, and any threads waiting on the event unblock.

Like a ManualResetEvent, ManualResetEventSlim is an event that allows threads to wait on it until other threads have set it.  However, ManualResetEventSlim is optimized for short waiting times, as it utilizes spinning and lazy-initialization of any necessary synchronization primitives . It supports basic event functionalities, such as Set, Reset, and Wait.

SemaphoreSlim is a lightweight semaphore implementation, also optimized for short waiting times. It also provides a few features not present in the System.Threading.Semaphore class, such as its current count, which can be useful for debugging purposes.

A blocking queue is a popular data structure in concurrent programming, as it provides a useful primitive for producer/consumer scenarios (with producers writing data into the queue and with consumers reading data from the queue, blocking until data is available to consume). The BlockingCollection<T> type provides this same functionality. However, rather than being tied to a particular storage implementation (e.g. the queue in a blocking queue), it provides a blocking and bounding mechanism for any IConcurrentCollection<T> implementation, including but not limited to implementations included with CDS (e.g. ConcurrentQueue<T> and ConcurrentStack<T>). BlockingCollection<T> supports not only blocking on removals, but also optional bounding on additions if it has maximum capacity set.

Lazy initialization is a common need in many applications, deferring the cost of creating an object until the object is actually needed.  There are several common patterns for lazy-initialization, and all of them can be difficult to get right and efficient, especially in concurrent situations.  Our LazyInit<T> type provides support for several of these common patterns.

The readonly keyword in C# (ReadOnly in Visual Basic) supports single initialization for a type and only from the constructor; any other attempt to initialize a readonly variable outside the constructor produces compilation error. However, sometimes developers need to create a variable that can be initialized only once, but the initialization doesn’t have to be inside the constructor. WriteOnce<T> provides that behavior, such that the variable can be initialized only once, and any other attempted set operations will fail.


Discussion is closed.

Feedback usabilla icon