17,7 → 17,7 |
</section> |
|
<section> |
<title>Active kernel primitives</title> |
<title>Active Kernel Primitives</title> |
|
<section> |
<indexterm> |
72,13 → 72,13 |
a result, the processor needs to be explicitly told about each |
occurrence of such a dependency. Therefore, HelenOS adds |
architecture-specific hooks to all <code>spinlock_lock()</code>, |
<code>spinlock_trylock()</code> and <code>spinlock_unlock()</code> 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.</para> |
<code>spinlock_trylock()</code> and <code>spinlock_unlock()</code> |
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.</para> |
|
<para>Spinlocks have one significant drawback: when held for longer time |
periods, they harm both parallelism and concurrency. The processor |
102,7 → 102,7 |
</section> |
|
<section> |
<title>Passive kernel synchronization</title> |
<title>Passive Kernel Synchronization</title> |
|
<section> |
<indexterm> |
111,7 → 111,7 |
<secondary>- wait queue</secondary> |
</indexterm> |
|
<title>Wait queues</title> |
<title>Wait Queues</title> |
|
<para>A wait queue is the basic passive synchronization primitive on |
which all other passive synchronization primitives are built. Simply |
124,8 → 124,8 |
queue are protected by a spinlock.</para> |
|
<para>The thread that wants to wait for a wait queue event uses the |
<code>waitq_sleep_timeout()</code> function. The algorithm then checks the |
wait queue's counter of missed wakeups and if there are any missed |
<code>waitq_sleep_timeout()</code> 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 |
134,14 → 134,14 |
|
<orderedlist> |
<listitem> |
<para>another thread calls <code>waitq_wakeup()</code> and the thread |
is the first thread in the wait queue's list of sleeping |
<para>another thread calls <code>waitq_wakeup()</code> and the |
thread is the first thread in the wait queue's list of sleeping |
threads;</para> |
</listitem> |
|
<listitem> |
<para>another thread calls <code>waitq_interrupt_sleep()</code> on the |
sleeping thread;</para> |
<para>another thread calls <code>waitq_interrupt_sleep()</code> on |
the sleeping thread;</para> |
</listitem> |
|
<listitem> |
153,16 → 153,16 |
|
<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 <code>waitq_sleep_timeout()</code>. |
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 seconds in |
<code>thread_sleep()</code> 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 |
distinguishable by the return value of |
<code>waitq_sleep_timeout()</code>. 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 |
seconds in <code>thread_sleep()</code> 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.</para> |
169,8 → 169,8 |
|
<para>From the description above, it should be apparent, that when a |
sleeping thread is woken by <code>waitq_wakeup()</code> or when |
<code>waitq_sleep_timeout()</code> succeeds immediately, the thread can be |
sure that the event has occurred. The thread need not and should not |
<code>waitq_sleep_timeout()</code> 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.</para> |
187,14 → 187,15 |
|
<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 |
<code>watiq_sleep_timeout()</code> 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 simultaneously.</para> |
<code>watiq_sleep_timeout()</code> 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 |
simultaneously.</para> |
|
<para>In the semaphore language, the wait queue operation |
<code>waitq_sleep_timeout()</code> corresponds to semaphore |
228,7 → 229,7 |
</section> |
|
<section> |
<title>Reader/writer locks</title> |
<title>Reader/Writer Locks</title> |
|
<indexterm> |
<primary>synchronization</primary> |
281,8 → 282,8 |
<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, |
a bare wait queue. This mutex is called <emphasis>exclusive</emphasis> |
and is used to synchronize writers. The writer's lock operation, |
<code>rwlock_write_lock_timeout()</code>, 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 |
292,8 → 293,8 |
|
<para>The exclusive mutex plays an important role in reader |
synchronization as well. However, a reader doing the reader's lock |
operation, <code>rwlock_read_lock_timeout()</code>, may bypass this mutex |
when it detects that:</para> |
operation, <code>rwlock_read_lock_timeout()</code>, may bypass this |
mutex when it detects that:</para> |
|
<orderedlist> |
<listitem> |
315,7 → 316,7 |
</section> |
|
<section> |
<title>Condition variables</title> |
<title>Condition Variables</title> |
|
<indexterm> |
<primary>synchronization</primary> |
352,22 → 353,23 |
<function>mutex_unlock</function>(<varname>mtx</varname>);</programlisting> |
</example> |
|
<para>The wait operation, <code>condvar_wait_timeout()</code>, always puts |
the calling thread to sleep. The thread then sleeps until another thread |
invokes <code>condvar_broadcast()</code> on the same condition variable or |
until it is woken up by <code>condvar_signal()</code>. The |
<code>condvar_signal()</code> operation unblocks the first thread blocking |
on the condition variable while the <code>condvar_broadcast()</code> |
operation unblocks all threads blocking there. If there are no blocking |
threads, these two operations have no efect.</para> |
<para>The wait operation, <code>condvar_wait_timeout()</code>, always |
puts the calling thread to sleep. The thread then sleeps until another |
thread invokes <code>condvar_broadcast()</code> on the same condition |
variable or until it is woken up by <code>condvar_signal()</code>. The |
<code>condvar_signal()</code> operation unblocks the first thread |
blocking on the condition variable while the |
<code>condvar_broadcast()</code> operation unblocks all threads blocking |
there. If there are no blocking threads, these two operations have no |
efect.</para> |
|
<para>Note that the threads must synchronize over a dedicated mutex. To |
prevent race condition between <code>condvar_wait_timeout()</code> and |
<code>condvar_signal()</code> or <code>condvar_broadcast()</code>, the mutex |
is passed to <code>condvar_wait_timeout()</code> which then atomically |
puts the calling thread asleep and unlocks the mutex. When the thread |
eventually wakes up, <code>condvar_wait()</code> regains the mutex and |
returns.</para> |
<code>condvar_signal()</code> or <code>condvar_broadcast()</code>, the |
mutex is passed to <code>condvar_wait_timeout()</code> which then |
atomically puts the calling thread asleep and unlocks the mutex. When |
the thread eventually wakes up, <code>condvar_wait()</code> regains the |
mutex and returns.</para> |
|
<para>Also note, that there is no conditional operation for condition |
variables. Such an operation would make no sence since condition |
400,8 → 402,8 |
|
<orderedlist> |
<listitem> |
<para><code>waitq_sleep_prepare()</code> prepares the thread to go to |
sleep by, among other things, locking the wait queue;</para> |
<para><code>waitq_sleep_prepare()</code> prepares the thread to go |
to sleep by, among other things, locking the wait queue;</para> |
</listitem> |
|
<listitem> |
416,9 → 418,9 |
</listitem> |
</orderedlist> |
|
<para>The stock <code>waitq_sleep_timeout()</code> 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. |
<para>The stock <code>waitq_sleep_timeout()</code> 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 <code>condvar_wait_timeout()</code> does |
need this finer-grained control because it has to interleave calls to |
these functions by other actions. It carries its operations out in the |
454,7 → 456,7 |
</section> |
|
<section> |
<title>Userspace synchronization</title> |
<title>Userspace Synchronization</title> |
|
<section> |
<title>Futexes</title> |
516,11 → 518,11 |
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 |
<code>futex_up()</code>, 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 |
<code>futex_up()</code>, 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 |
<constant>SYS_FUTEX_WAKEUP</constant> syscall to wake one sleeping |
thread.</para> |
|