Table of Contents
The HelenOS operating system is designed to make use of the parallelism offered by the hardware and to exploit concurrency of both the kernel and userspace tasks. This is achieved through multiprocessor support and several levels of multiprogramming such as multitasking, multithreading and also 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. The spinlock implements active waiting for the 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 a 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 configurations 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 the
test-and-set operation. The first function is the unconditional attempt
to acquire the spinlock and is called
simply loops until the test-and-set returns a zero value. The other
spinlock_trylock(), is the conditional lock
operation and calls the test-and-set only once to find out whether 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 function,
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. Particularly 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. As
a result, the processor needs to be explicitly told about each
occurrence of such a dependency. Therefore, HelenOS adds
architecture-specific hooks to all
functions to prevent the instructions inside the critical section from
permeating out. On some architectures, these hooks can be void 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 could permeate out.
Spinlocks have one significant drawback: when held for longer time
periods, they harm both parallelism and concurrency. The processor
spinlock_lock() does not do any fruitful work and
is effectively halted until it can grab the lock and proceed.
Similarily, other execution flows 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
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 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.
A wait queue is the basic passive synchronization primitive on which all other passive synchronization primitives are built. Simply put, it allows a thread to sleep until an event associated with the particular wait queue occurs. Multiple threads are notified about incoming events in a first come, first served fashion. Moreover, should the event come before any thread waits for it, it is recorded in the wait queue as a missed wakeup and later forwarded to the first thread that decides to wait in the queue. The inner structures of the wait queue are protected by a spinlock.
The thread that wants to wait for a wait queue event uses the
waitq_sleep_timeout() function. The algorithm then checks
the wait queue's counter of missed wakeups and if there are any missed
wakeups, the call returns immediately. The call also returns immediately
if only a conditional wait was requested. Otherwise the thread is
enqueued in the wait queue's list of sleeping threads and its state is
Sleeping. It then sleeps until one of
the following events happens:
another thread calls
waitq_wakeup() and the
thread is the first thread in the wait queue's list of sleeping
another thread calls
the sleeping thread;
the sleep times out provided that none of the previous occurred within a specified time limit; the limit can be infinity.
All five possibilities (immediate return on success, immediate
return on failure, wakeup after sleep, interruption and timeout) are
distinguishable by the return value of
waitq_sleep_timeout(). Being able to interrupt a sleeping
thread is essential for externally initiated thread termination. The
ability to wait only for a certain amount of time is used, for instance,
to passively delay thread execution by several microseconds or even
thread_sleep() function. Due to the fact that
all other passive kernel synchronization primitives are based on wait
queues, they also have the option of being interrutped and, more
importantly, can timeout. All of them also implement the conditional
operation. Furthemore, this very fundamental interface reaches up to the
implementation of futexes - userspace synchronization primitive, which
makes it possible for a userspace thread to request a synchronization
operation with a timeout or a conditional operation.
From the description above, it should be apparent, that when a
sleeping thread is woken by
waitq_wakeup() or when
waitq_sleep_timeout() succeeds immediately, the thread can
be sure that the event has occurred. The thread need not and should not
verify this fact. This approach is called direct hand-off and is
characteristic for all passive HelenOS synchronization primitives, with
the exception as described below.
The interesting point about wait queues is that the number of
missed wakeups is equal to the number of threads that will not block in
watiq_sleep_timeout() and would immediately succeed
instead. On the other hand, semaphores are synchronization primitives
that will let predefined amount of threads into their critical section
and block any other threads above this count. However, these two cases
are exactly the same. Semaphores in HelenOS are therefore implemented as
wait queues with a single semantic change: their wait queue is
initialized to have so many missed wakeups as is the number of threads
that the semphore intends to let into its critical section
In the semaphore language, the wait queue operation
waitq_sleep_timeout() corresponds to semaphore
down operation, represented by the function
semaphore_down_timeout() and by way of similitude the wait
queue operation waitq_wakeup corresponds to semaphore
operation, represented by the function
conditional down operation is called
Mutexes are sometimes referred to as binary sempahores. That means
that mutexes are like semaphores that allow only one thread in its
critical section. Indeed, mutexes in HelenOS are implemented exactly in
this way: they are built on top of semaphores. From another point of
view, they can be viewed as spinlocks without busy waiting. Their
semaphore heritage provides good basics for both conditional operation
and operation with timeout. The locking operation is called
mutex_lock(), the conditional locking operation is called
mutex_trylock() and the unlocking operation is called
Reader/writer locks, or rwlocks, are by far the most complicated synchronization primitive within the kernel. The goal of these locks is to improve concurrency of applications, in which threads need to synchronize access to a shared resource, and that access can be partitioned into a read-only mode and a write mode. Reader/writer locks should make it possible for several, possibly many, readers to enter the critical section, provided that no writer is currently in the critical section, or to be in the critical section contemporarily. Writers are allowed to enter the critical section only individually, provided that no reader is in the critical section already. Applications, in which the majority of operations can be done in the read-only mode, can benefit from increased concurrency created by reader/writer locks.
During reader/writer lock construction, a decision should be made whether readers will be prefered over writers or whether writers will be prefered over readers in cases when the lock is not currently held and both a reader and a writer want to gain the lock. Some operating systems prefer one group over the other, creating thus a possibility for starving the unprefered group. In the HelenOS operating system, none of the two groups is prefered. The lock is granted on a first come, first served basis with the additional note that readers are granted the lock in the biggest possible batch.
With this policy and the timeout modes of operation, the direct hand-off becomes much more complicated. For instance, a writer leaving the critical section must wake up all leading readers in the rwlock's wait queue or one leading writer or no-one if no thread is waiting. Similarily, the last reader leaving the critical section must wakeup the sleeping writer if there are any sleeping threads left at all. As another example, if a writer at the beginning of the rwlock's wait queue times out and the lock is held by at least one reader, the writer which has timed out must first wake up all readers that follow him in the queue prior to signalling the timeout itself and giving up.
Due to the issues mentioned in the previous paragraph, the reader/writer lock imlpementation needs to walk the rwlock wait queue's list of sleeping threads directly, in order to find out the type of access that the queueing threads demand. This makes the code difficult to understand and dependent on the internal implementation of the wait queue. Nevertheless, it remains unclear to the authors of HelenOS whether a simpler but equivalently fair solution exists.
The implementation of rwlocks as it has been already put, makes
use of one single wait queue for both readers and writers, thus avoiding
any possibility of starvation. In fact, rwlocks use a mutex rather than
a bare wait queue. This mutex is called exclusive
and is used to synchronize writers. The writer's lock operation,
rwlock_write_lock_timeout(), simply tries to acquire the
exclusive mutex. If it succeeds, the writer is granted the rwlock.
However, if the operation fails (e.g. times out), the writer must check
for potential readers at the head of the list of sleeping threads
associated with the mutex's wait queue and then proceed according to the
procedure outlined above.
The exclusive mutex plays an important role in reader
synchronization as well. However, a reader doing the reader's lock
rwlock_read_lock_timeout(), may bypass this
mutex when it detects that:
there are other readers in the critical section and
there are no sleeping threads waiting for the exclusive mutex.
If both conditions are true, the reader will bypass the mutex, increment the number of readers in the critical section and then enter the critical section. Note that if there are any sleeping threads at the beginning of the wait queue, the first must be a writer. If the conditions are not fulfilled, the reader normally waits until the exclusive mutex is granted to it.
Condition variables can be used for waiting until a condition becomes true. In this respect, they are similar to wait queues. But contrary to wait queues, condition variables have different semantics that allows events to be lost when there is no thread waiting for them. In order to support this, condition variables don't use direct hand-off and operate in a way similar to the example below. A thread waiting for the condition becoming true does the following:
Example 6.1. Use of
mtx); while (!
mtx); /* the condition is true, do something */
A thread that causes the condition become true signals this event like this:
Example 6.2. Use of
cv); /* condvar_broadcast(cv); */
The wait operation,
puts the calling thread to sleep. The thread then sleeps until another
condvar_broadcast() on the same condition
variable or until it is woken up by
condvar_signal() operation unblocks the first thread
blocking on the condition variable while the
condvar_broadcast() operation unblocks all threads blocking
there. If there are no blocking threads, these two operations have no
Note that the threads must synchronize over a dedicated mutex. To
prevent race condition between
mutex is passed to
condvar_wait_timeout() which then
atomically puts the calling thread asleep and unlocks the mutex. When
the thread eventually wakes up,
condvar_wait() regains the
mutex and returns.
Also note, that there is no conditional operation for condition
variables. Such an operation would make no sence since condition
variables are defined to forget events for which there is no waiting
thread and because
condvar_wait() must always go to sleep.
The operation with timeout is supported as usually.
In HelenOS, condition variables are based on wait queues. As it is
already mentioned above, wait queues remember missed events while
condition variables must not do so. This is reasoned by the fact that
condition variables are designed for scenarios in which an event might
occur very many times without being picked up by any waiting thread. On
the other hand, wait queues would remember any event that had not been
picked up by a call to
waitq_sleep_timeout(). Therefore, if
wait queues were used directly and without any changes to implement
condition variables, the missed_wakeup counter would hurt performance of
the implementation: the
while loop in
condvar_wait_timeout() would effectively do busy waiting
until all missed wakeups were discarded.
The requirement on the wait operation to atomically put the caller
to sleep and release the mutex poses an interesting problem on
condvar_wait_timeout(). More precisely, the thread should
sleep in the condvar's wait queue prior to releasing the mutex, but it
must not hold the mutex when it is sleeping.
Problems described in the two previous paragraphs are addressed in
HelenOS by dividing the
waitq_sleep_timeout() function into
waitq_sleep_prepare() prepares the thread to go
to sleep by, among other things, locking the wait queue;
waitq_sleep_timeout_unsafe() implements the core
waitq_sleep_finish() performs cleanup after
waitq_sleep_timeout_unsafe(); after this call, the wait
queue spinlock is guaranteed to be unlocked by the caller
waitq_sleep_timeout() is then a mere
wrapper that calls these three functions. It is provided for convenience
in cases where the caller doesn't require such a low level control.
However, the implementation of
need this finer-grained control because it has to interleave calls to
these functions by other actions. It carries its operations out in the
waitq_sleep_prepare() in order to lock the
condition variable's wait queue,
releases the mutex,
clears the counter of missed wakeups,
retakes the mutex,
In a multithreaded environment, userspace threads need an efficient way to synchronize. HelenOS borrows an idea from Linux[Franke et al.] to implement lightweight userspace synchronization and mutual exclusion primitive called futex. The key idea behind futexes is that non-contended synchronization is very fast and takes place only in userspace without kernel's intervention. When more threads contend for a futex, only one of them wins; other threads go to sleep via a dedicated syscall.
The userspace part of the futex is a mere integer variable, a counter, that can be atomically incremented or decremented. The kernel part is rather more complicated. For each userspace futex counter, there is a kernel structure describing the futex. This structure contains:
number of references,
physical address of the userspace futex counter,
hash table link and
a wait queue.
The reference count helps to find out when the futex is no longer needed and can be deallocated. The physical address is used as a key for the global futex hash table. Note that the kernel has to use physical address to identify the futex beacause one futex can be used for synchronization among different address spaces and can have different virtual addresses in each of them. Finally, the kernel futex structure includes a wait queue. The wait queue is used to put threads that didn't win the futex to sleep until the winner wakes one of them up.
A futex should be initialized by setting its userspace counter to
one before it is used. When locking the futex via userspace library
futex_down_timeout(), the library code atomically
decrements the futex counter and tests if it dropped below zero. If it
did, then the futex is locked by another thread and the library uses the
SYS_FUTEX_SLEEP syscall to put the thread asleep.
If the counter decreased to 0, then there was no contention and the
thread can enter the critical section protected by the futex. When the
thread later leaves that critical section, it, using library function
futex_up(), atomically increments the counter. If the
counter value increased to one, then there again was no contention and
no action needs to be done. However, if it increased to zero or even a
smaller number, then there are sleeping threads waiting for the futex to
become available. In that case, the library has to use the
SYS_FUTEX_WAKEUP syscall to wake one sleeping
So far, futexes are very elegant in that they don't interfere with the kernel when there is no contention for them. Another nice aspect of futexes is that they don't need to be registered anywhere prior to the first kernel intervention.
Both futex related syscalls,
SYS_FUTEX_WAKEUP, respectivelly, are mere
waitq_sleep_wakeup(), respectively, with some housekeeping
functionality added. Both syscalls need to translate the userspace
virtual address of the futex counter to physical address in order to
support synchronization accross shared memory. Once the physical address
is known, the kernel checks whether the futexes are already known to it
by searching the global futex hash table for an item with the physical
address of the futex counter as a key. When the search is successful, it
returns an address of the kernel futex structure associated with the
counter. If the hash table does not contain the key, the kernel creates
it and inserts it into the hash table. At the same time, the the current
task's B+tree of known futexes is searched in order to find out if the
task already uses the futex. If it does, no action is taken. Otherwise
the reference count of the futex is incremented, provided that the futex