Subversion Repositories HelenOS-doc

Compare Revisions

Ignore whitespace Rev 85 → Rev 86

/design/trunk/src/ch_synchronization.xml
47,9 → 47,9
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 <code>spinlock_lock</code>. It
to acquire the spinlock and is called <code>spinlock_lock()</code>. It
simply loops until the test-and-set returns a zero value. The other
function, <code>spinlock_trylock</code>, is the conditional lock
function, <code>spinlock_trylock()</code>, 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
57,7 → 57,7
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, <code>spinlock_unlock</code>, is quite
next time. The unlock function, <code>spinlock_unlock()</code>, is quite
easy - it merely clears the spinlock variable.</para>
 
<para>Nevertheless, there is a special issue related to hardware
71,8 → 71,8
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 <code>spinlock_lock</code>,
<code>spinlock_trylock</code> and <code>spinlock_unlock</code> functions
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
82,7 → 82,7
 
<para>Spinlocks have one significant drawback: when held for longer time
periods, they harm both parallelism and concurrency. The processor
executing <code>spinlock_lock</code> does not do any fruitful work and
executing <code>spinlock_lock()</code> 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
124,7 → 124,7
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
<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
134,13 → 134,13
 
<orderedlist>
<listitem>
<para>another thread calls <code>waitq_wakeup</code> and the thread
<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
<para>another thread calls <code>waitq_interrupt_sleep()</code> on the
sleeping thread;</para>
</listitem>
 
153,12 → 153,12
 
<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>.
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
<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.
168,8 → 168,8
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 <code>waitq_wakeup</code> or when
<code>waitq_sleep_timeout</code> succeeds immediately, the thread can be
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
verify this fact. This approach is called direct hand-off and is
characteristic for all passive HelenOS synchronization primitives, with
187,7 → 187,7
 
<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.
<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
197,13 → 197,13
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
<code>waitq_sleep_timeout()</code> corresponds to semaphore
<code>down</code> operation, represented by the function
<code>semaphore_down_timeout</code> and by way of similitude the wait
<code>semaphore_down_timeout()</code> and by way of similitude the wait
queue operation waitq_wakeup corresponds to semaphore <code>up</code>
operation, represented by the function <code>sempafore_up</code>. The
operation, represented by the function <code>sempafore_up()</code>. The
conditional down operation is called
<code>semaphore_trydown</code>.</para>
<code>semaphore_trydown()</code>.</para>
</section>
 
<section>
222,9 → 222,9
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
<code>mutex_lock</code>, the conditional locking operation is called
<code>mutex_trylock</code> and the unlocking operation is called
<code>mutex_unlock</code>.</para>
<code>mutex_lock()</code>, the conditional locking operation is called
<code>mutex_trylock()</code> and the unlocking operation is called
<code>mutex_unlock()</code>.</para>
</section>
 
<section>
281,9 → 281,9
<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 <code>exclusive</code> and is
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
<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
for potential readers at the head of the list of sleeping threads
292,7 → 292,7
 
<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
operation, <code>rwlock_read_lock_timeout()</code>, may bypass this mutex
when it detects that:</para>
 
<orderedlist>
332,7 → 332,7
the condition becoming true does the following:</para>
 
<example>
<title>Use of <code>condvar_wait_timeout</code>.</title>
<title>Use of <code>condvar_wait_timeout()</code>.</title>
 
<programlisting language="C"><function>mutex_lock</function>(<varname>mtx</varname>);
while (!<varname>condition</varname>)
353,27 → 353,27
<function>mutex_unlock</function>(<varname>mtx</varname>);</programlisting>
</example>
 
<para>The wait operation, <code>condvar_wait_timeout</code>, always puts
<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>
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
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
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
variables are defined to forget events for which there is no waiting
thread and because <code>condvar_wait</code> must always go to sleep.
thread and because <code>condvar_wait()</code> must always go to sleep.
The operation with timeout is supported as usually.</para>
 
<para>In HelenOS, condition variables are based on wait queues. As it is
382,45 → 382,45
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 <code>waitq_sleep_timeout</code>. Therefore, if
picked up by a call to <code>waitq_sleep_timeout()</code>. 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 <code>while</code> loop in
<code>condvar_wait_timeout</code> would effectively do busy waiting
<code>condvar_wait_timeout()</code> would effectively do busy waiting
until all missed wakeups were discarded.</para>
 
<para>The requirement on the wait operation to atomically put the caller
to sleep and release the mutex poses an interesting problem on
<code>condvar_wait_timeout</code>. More precisely, the thread should
<code>condvar_wait_timeout()</code>. 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.</para>
 
<para>Problems described in the two previous paragraphs are addressed in
HelenOS by dividing the <code>waitq_sleep_timeout</code> function into
HelenOS by dividing the <code>waitq_sleep_timeout()</code> function into
three pieces:</para>
 
<orderedlist>
<listitem>
<para><code>waitq_sleep_prepare</code> prepares the thread to go to
<para><code>waitq_sleep_prepare()</code> prepares the thread to go to
sleep by, among other things, locking the wait queue;</para>
</listitem>
 
<listitem>
<para><code>waitq_sleep_timeout_unsafe</code> implements the core
<para><code>waitq_sleep_timeout_unsafe()</code> implements the core
blocking logic;</para>
</listitem>
 
<listitem>
<para><code>waitq_sleep_finish</code> performs cleanup after
<code>waitq_sleep_timeout_unsafe</code>; after this call, the wait
<para><code>waitq_sleep_finish()</code> performs cleanup after
<code>waitq_sleep_timeout_unsafe()</code>; after this call, the wait
queue spinlock is guaranteed to be unlocked by the caller</para>
</listitem>
</orderedlist>
 
<para>The stock <code>waitq_sleep_timeout</code> is then a mere wrapper
<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
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
following order:</para>
427,7 → 427,7
 
<orderedlist>
<listitem>
<para>calls <code>waitq_sleep_prepare</code> in order to lock the
<para>calls <code>waitq_sleep_prepare()</code> in order to lock the
condition variable's wait queue,</para>
</listitem>
 
440,7 → 440,7
</listitem>
 
<listitem>
<para>calls <code>waitq_sleep_timeout_unsafe</code>,</para>
<para>calls <code>waitq_sleep_timeout_unsafe()</code>,</para>
</listitem>
 
<listitem>
448,7 → 448,7
</listitem>
 
<listitem>
<para>calls <code>waitq_sleep_finish</code>.</para>
<para>calls <code>waitq_sleep_finish()</code>.</para>
</listitem>
</orderedlist>
</section>
510,7 → 510,7
 
<para>A futex should be initialized by setting its userspace counter to
one before it is used. When locking the futex via userspace library
function <code>futex_down_timeout</code>, the library code atomically
function <code>futex_down_timeout()</code>, 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
<constant>SYS_FUTEX_SLEEP</constant> syscall to put the thread asleep.
517,7 → 517,7
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
<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
532,8 → 532,8
 
<para>Both futex related syscalls, <constant>SYS_FUTEX_SLEEP</constant>
and <constant>SYS_FUTEX_WAKEUP</constant>, respectivelly, are mere
wrappers for <code>waitq_sleep_timeout</code> and
<code>waitq_sleep_wakeup</code>, respectively, with some housekeeping
wrappers for <code>waitq_sleep_timeout()</code> and
<code>waitq_sleep_wakeup()</code>, 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