The HelenOS operating system is designed to make use of parallelism offered by hardware and to exploit concurrency of both the kernel and userspace tasks. This is achieved through multiprocessor support and several levels of multiprogramming (i.e. multitasking, multithreading and through userspace pseudo threads). However, such a highly concurrent environment needs safe and efficient ways to handle mutual exclusion and synchronization of many execution flows.

The basic mutual exclusion primitive is the spinlock. Spinlock implements busy waiting for an availability of a memory lock (i.e. simple variable) in a multiprocessor-safe manner. This safety is achieved through the use of a specialized, architecture-dependent, atomic test-and-set operation which either locks the spinlock (i.e. sets the variable) or, provided that it is already locked, leaves it unaltered. In any case, the test-and-set operation returns a value, thus signalling either success (i.e. zero return value) or failure (i.e. non-zero value) in acquiring the lock. Note that this makes the fundamental difference between the naive algorithm that doesn't use the atomic operation and the spinlock algortihm. While the naive algorithm is prone to race conditions on SMP configuratinos and thus is completely SMP-unsafe, the spinlock algorithm eliminates the possibility of race conditions and is suitable for mutual exclusion use. The semantics of the test-and-set operation is that the spinlock remains unavailable until this operation called on the respective spinlock returns zero. HelenOS builds two functions on top of test-and-set operation. The first is the unconditional attempt to acquire the spinlock and is called spinlock_lock. It simply loops until test-and-set returns zero. The other operation, spinlock_trylock, is the conditional lock operation and calls the test-and-set only once to find out wheter it managed to acquire the spinlock or not. The conditional operation is useful in situations in which an algorithm cannot acquire more spinlocks in the proper order and a deadlock cannot be avoided. In such a case, the algorithm would detect the danger and instead of possibly deadlocking the system it would simply release some spinlocks it already holds and retry the whole operation with the hope that it will succeed next time. The unlock operation, spinlock_unlock, is quite easy - it merely clears the spinlock variable. Nevertheless, there is a special issue related to hardware optimizations that modern processors implement. Particularily problematic is the out-of-order execution of instructions within the critical section protected by a spinlock. The processors are always self-consistent so that they can carry out speculatively executed instructions in the right order with regard to dependencies among those instructions. However, the dependency between instructions inside the critical section and those that implement locking and unlocking of the respective spinlock is not implicit on some processor architectures and the processor needs to be explicitly told about each occurrence of such a dependency. Therefore, HelenOS adds architecture-specific hooks to all spinlock_lock, spinlock_trylock and spinlock_unlock to prevent the instructions inside the critical section from bleeding out. On some architectures, these hooks can be a no-op because the dependencies are implicitly there because of the special properties of locking and unlocking instructions. However, other architectures need to instrument these hooks with different memory barriers, depending on what operations can bleed out. Spinlocks have one significant drawback: when held for longer time periods, they harm both parallelism and concurrency. Processor executing spinlock_lock does not do any fruitful work and is effectively halted until it can grab the lock and proceed. Similarily, other threads cannot execute on the processor that holds the spinlock because the kernel disables preemption on that processor when a spinlock is held. The reason behind disabling preemption is priority inversion problem avoidance. For the same reason, threads are strongly discouraged from sleeping when they hold a spinlock. To summarize, spinlocks represent very simple and essential mutual exclusion primitive for SMP systems. On the other hand, spinlocks scale poorly because of the active loop they are based on. Therefore, spinlocks are used in HelenOS only for a short-time mutual exclusion and in cases where the mutual exclusion is required out of thread context. Lastly, spinlocks are used in the construction of passive synchronization primitives.

Mutex explanations

Semaphore explanations

RWLocks explanation

Wait queue explanation

Condvars explanation