Practical Concurrency Patterns: Spinlock

Previously in the series we have examined the performance differences between concurrency patterns based on kernel synchronization (critical sections, events, mutexes etc.) and concurrency patterns based on wait-free synchronization (such as the interlocked family of operations).  Kernel synchronization tends to be expensive if locks are frequently acquired and released because of the associated context switches, introducing anti-patterns such as lock convoys.  Wait-free synchronization tends to be expensive if locks are held for a long time because of the spinning which burns CPU without making progress.

Oftentimes neither approach is flexible enough to implement a practical scenario, and an intermediate mechanism is required.  Such an intermediate mechanism is available in the Win32 API in the form of a critical section with a spin count.

The InitializeCriticalSectionAndSpinCount API initializes a critical section and associates it with a spin count.  When a thread attempts to acquire the critical section and finds it locked, it will first spin the CPU for the specified number of iterations (i.e. the spin count) before transitioning to a kernel wait.  If the critical section is released while the thread is spinning, it will acquire the critical section without context switching and without a kernel wait, producing a significant performance boost.

Critical sections with spin counts are a specific example of the general spinlock pattern used in the Windows kernel and in user-mode frameworks such as the Parallel Extensions for .NET.

A typical kernel implementation of a spinlock is a single bit.  The spinlock has the following semantics:

• When the spinlock is taken, the bit is set to 1.
• When the spinlock is free, the bit is set to 0.
• When a thread attempts to acquire the spinlock, it will spin indefinitely until the bit is set to 0 (using an atomic operation such as the x86 BTS or InterlockedCompareExchange).

A refinement on the spinlock pattern that is better suited for multi-processor machines is the queued spinlock.  A queued spinlock is typically implemented using a set of bits (queue), one for each CPU waiting for the spinlock.  Each CPU is also associated with a bit that it uses to spin while waiting for the spinlock.  When a spinlock is released, the releasing CPU hands it over to the next waiting CPU by setting its private bit and removing it from the queue.

This pattern minimizes inter-processor contention for memory because each CPU spins on a private bit which serves as its spinlock indicator.  It also introduces first-in-first-out order for acquiring the spinlock to guarantee fairness.

Side note:  In the Windows kernel, queued spinlocks are used on multi-processor systems.  On single-processor systems, spinlocks are not needed because spinlock synchronization is required on high IRQLs only.  On high IRQLs (above dispatch IRQL) a context switch cannot occur, so instead of spinning the acquiring thread can simply request an interrupt on the relevant IRQL and return; the interrupt will be masked until the releasing thread lowers the IRQL below the requested IRQL.