Saturday, July 5, 2008

[2008.07.04] Coordinate Data Structures in System.Threading [Part I/III]

The Coordinate Data Structures introduced in Parallel Extensions are used in all aspects of the library as seen in Fig.1. I have made notes based on the June 2008 CTP help file as well as from interviews with the people working on PE.

Fig.1 Parallel Extensions Hierarchy

[1] System.Threading.SpinWait

  • spin waiting can be an effective low-level mechanism for avoiding unnecessary context switches and associated kernel transitions
  • most of the data structures in the CDS use SpinWait in some form or the other
  • is used in the Scheduler, Task Parallel Library and PLINQ
  • SpinWait is waiting for something to happen by spinning (waiting in a loop)
  • in an application there are several types of waiting such as:
    • wait by blocking a kernel primitive
    • polling (keep asking: are we there yet, are we there yet ...)
  • know something will eventually happen and you don't want to take the full cost of a context switch or accessing the kernel
  • the idea is that by spinning just a little bit, that by wasting a little work to do the spinning, you will save yourself from wasting a lot of work by doing a context switch or querying the kernel

[2] System.Threading.SpinLock

  • the SpinLock data structure is built on top of the SpinWait
  • idea behind SpinLock is not going into kernel at all – it is all user mode
  • a SpinLock is a mutual exclusion lock primitive where a thread trying to acquire the lock waits in a loop repeatedly checking until the lock becomes available (in other words, it “spins”) [keep asking: is the lock available yet, is the lock available yet, ...]
  • both SpinWait and SpinLock are designed for advanced scenarios as the thread remains active performing a non-useful task
  • can think of SpinLock as a kind of busy waiting which consumes CPU resources without performing real work
  • spin locks can be more efficient than other kinds of locks on multi-processor machines if threads are only likely to be blocked for a very short period of time as they avoid unnecessary context switches and associated kernel transitions, which might otherwise be more costly than just spinning
  • in addition, both SpinWait and SpinLock are structs and as such they are cheaper to implement because if you wanted to use a Monitor or a Mutex, you will need to allocate a garbage collected object as these locks are all classes

[3] System.Threading.ManualResetEventSlim

  • the ManualResetEvent in System.Threading of the mscorlib.dll assembly notifies one or more waiting threads that an event has occurred
  • if one wants to use the Windows kernel event objects, there is a high overhead:
    • the cost of allocating the kernel object,
    • the cost of a new finalizable object for the garbage collector to track, and
    • the costs of the associated kernel transitions any time one wishes to wait or set the event
  • ManualResetEventSlim type addresses many of these issues by trying to do everything in user mode if possible and only lazily instantiate the underlying kernel events if absolutely necessary
  • it provides an interface similar to the original ManualResetEvent but unlike ManualResetEvent it:
    • does not provide the ability to create named events and thus cannot be used for cross-process synchronization
    • does not derive from WaitHandle

No comments: