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 |