37,8 → 37,6 |
SMP-unsafe, the spinlock algorithm eliminates the possibility of race |
conditions and is suitable for mutual exclusion use.</para> |
|
<para></para> |
|
<para>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 |
56,8 → 54,6 |
The unlock operation, <emphasis>spinlock_unlock</emphasis>, is quite |
easy - it merely clears the spinlock variable.</para> |
|
<para></para> |
|
<para>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 |
79,8 → 75,6 |
different memory barriers, depending on what operations can bleed |
out.</para> |
|
<para></para> |
|
<para>Spinlocks have one significant drawback: when held for longer time |
periods, they harm both parallelism and concurrency. Processor executing |
<emphasis>spinlock_lock</emphasis> does not do any fruitful work and is |
91,8 → 85,6 |
problem avoidance. For the same reason, threads are strongly discouraged |
from sleeping when they hold a spinlock.</para> |
|
<para></para> |
|
<para>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, |
107,27 → 99,190 |
<title>Passive kernel synchronization</title> |
|
<section> |
<title>Mutexes</title> |
<title>Wait queues</title> |
|
<para>Mutex explanations</para> |
<para>A wait queue is the basic passive synchronization primitive on |
which all other passive synchronization primitives build. 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 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.</para> |
|
<para>The thread that wants to wait for a wait queue event uses the |
<emphasis>waitq_sleep_timeout</emphasis> 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 changed to <emphasis>Sleeping</emphasis>. It then sleeps until |
one of the following events happens:</para> |
|
<orderedlist> |
<listitem> |
<para>another thread calls <emphasis>waitq_wakeup</emphasis> and the |
thread is the first thread in the wait queue's list of sleeping |
threads</para> |
</listitem> |
|
<listitem> |
<para>another thread calls |
<emphasis>waitq_interrupt_sleep</emphasis> on the sleeping |
thread</para> |
</listitem> |
|
<listitem> |
<para>the sleep timeouts provided that none of the previous occurred |
within a specified time limit; the limit can be infinity</para> |
</listitem> |
</orderedlist> |
|
<para>All five possibilities (immediate return on success, immediate |
return on failure, wakeup after sleep, interruption and timeout) are |
distinguishable by the return value of |
<emphasis>waitq_sleep_timeout</emphasis>. The ability to interrupt a |
sleeping thread is essential for externally initiated thread termination |
and 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 seconds in <emphasis>thread_sleep</emphasis> function. Because 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 synchronization |
operation with a timeout or a conditional operation.</para> |
|
<para>From the description above, it should be apparent, that when a |
sleeping thread is woken by <emphasis>waitq_wakeup</emphasis> or when |
<emphasis>waitq_sleep_timeout</emphasis> succeeds immediatelly, the |
thread can be sure the event has come and 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 |
one exception described below.</para> |
</section> |
|
<section> |
<title>Semaphores</title> |
|
<para>Semaphore explanations</para> |
<para>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 |
<emphasis>watiq_sleep_timeout</emphasis> and would immediately succeed |
instead. On the other hand, semaphores are synchronization primitives |
that will let predefined amount of threads in its 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 |
simultaneously.</para> |
|
<para>In the semaphore language, the wait queue operation |
<emphasis>waitq_sleep_timeout</emphasis> corresponds to |
<emphasis><emphasis>semaphore</emphasis> down</emphasis> operation, |
represented by the function <emphasis>semaphore_down_timeout</emphasis> |
and by way of similitude the wait queue operation waitq_wakeup |
corresponds to semaphore <emphasis>up</emphasis> operation, represented |
by the function <emphasis>sempafore_up</emphasis>. The conditional down |
operation is called <emphasis>semaphore_trydown</emphasis>.</para> |
</section> |
|
<section> |
<title>Read/Write Locks</title> |
<title>Mutexes</title> |
|
<para>RWLocks explanation</para> |
<para>Mutexes are 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 atop 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 |
<emphasis>mutex_lock</emphasis>, the conditional locking operation is |
called <emphasis>mutex_trylock</emphasis> and the unlocking operation is |
called <emphasis>mutex_unlock</emphasis>.</para> |
</section> |
|
<section> |
<title>Wait queues</title> |
<title>Reader/writer locks</title> |
|
<para>Wait queue explanation</para> |
<para>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.</para> |
|
<para>During reader/writer locks 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 the first come, first |
served basis with the additional note that readers are granted the lock |
in biggest possible batches.</para> |
|
<para>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 at all. As another |
example, if a writer at the beginning of the rwlock's wait queue |
timeouts and the lock is held by at least one reader, the timeouting |
writer must first wake up all readers that follow him in the queue prior |
to signalling the timeout itself and giving up.</para> |
|
<para>Because of the issues mentioned in the previous paragraph, the |
reader/writer locks 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.</para> |
|
<para>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 <emphasis>exclusive</emphasis> |
and is used to synchronize writers. The writer's lock operation, |
<emphasis>rwlock_write_lock_timeout</emphasis>, simply tries to acquire |
the exclusive mutex. If it succeeds, the writer is granted the rwlock. |
However, if the operation fails, the writer must check for potential |
readers at the head of the list of sleeping threads associated with the |
mutex's wait queue and proceed according to the procedure outlined |
above.</para> |
|
<para>The exclusive mutex plays an important role in reader |
synchronization as well. However, a reader doing the reader's lock |
operation, <emphasis>rwlock_read_lock_timeout</emphasis>, may bypass |
this mutex when it detects that:</para> |
|
<orderedlist> |
<listitem> |
<para>there are other readers in the critical section</para> |
</listitem> |
|
<listitem> |
<para>there are no sleeping threads waiting for the exclusive |
mutex</para> |
</listitem> |
</orderedlist> |
|
<para>If both conditions are true, the reader will bypass the mutex, |
increment the number of readers in the critical section and enter the |
critical section. Note that if there are any sleeping threads at the |
beginning of the wait queue, the first of them must be a writer. If the |
conditions are not fulfilled, the reader normally waits until the |
exclusive mutex is granted to it.</para> |
</section> |
|
<section> |