Solaris Turnstiles

Solaris, a once prominent operating system, was renowned for its exceptional symmetric multiprocessing (SMP) capabilities. This strength stemmed from Solaris' innovative design, yet the operating system is no longer in active use. Despite this, Solaris' impact endures, as its inventions, including turnstiles, are now widely utilized across various software systems.

Turnstiles, though lesser-known, have significantly influenced major operating systems, web browsers, and language runtimes. These concepts may already be familiar to you, as they play a role in your daily interactions with technology.

To understand the significance of turnstiles, it is essential to delve into the challenges Sun engineers aimed to resolve. Solaris heavily relied on blocking mutexes (or locks) to achieve high-performance, soft real-time behavior. While blocking mutexes provided better latency for high-priority tasks, they introduced complexities such as the need for additional kernel tracking and the potential for priority inversion.

Priority inversion occurs when a high-priority task is delayed due to a lower-priority task holding a lock, leading to unnecessary latency and potential delays.

To address these issues, Solaris introduced turnstiles as a mechanism to efficiently manage lock dependencies and propagate priority through the lock's owner chain. Turnstiles are data structures associated with contended locks, storing information about threads waiting on the lock and facilitating priority inheritance. Instead of embedding the turnstile within the lock itself, each thread is allocated its own turnstile upon creation, ready to contend on a blocking lock.

When a thread blocks, it donates its turnstile to the lock it is waiting on, allowing the kernel to maintain waiters and priority-inheritance state.

To locate a turnstile, the kernel employs a hash table that associates the lock's address with the corresponding turnstile. Although the diagram simplistically shows one turnstile per hash bucket, in practice, each bucket contains a chain of turnstiles, and finding the appropriate turnstile involves iterating over the chain. This efficient mechanism, used in Solaris and other UNIX-derived operating systems, has become a cornerstone in managing lock dependencies and maintaining system performance.