175,9 → 175,9 |
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 into 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 |
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 |
292,7 → 292,131 |
<section> |
<title>Condition variables</title> |
|
<para>Condvars explanation</para> |
<para>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:</para> |
|
<para><programlisting language="C"><function>mutex_lock</function>(<varname>mtx</varname>); |
while (!<varname>condition</varname>) |
<function>condvar_wait_timeout</function>(<varname>cv</varname>, <varname>mtx</varname>); |
/* <remark>the condition is true, do something</remark> */ |
<function>mutex_unlock</function>(<varname>mtx</varname>);</programlisting></para> |
|
<para>A thread that causes the condition become true signals this event |
like this:</para> |
|
<para><programlisting><function>mutex_lock</function>(<varname>mtx</varname>); |
<varname>condition</varname> = <constant>true</constant>; |
<function>condvar_signal</function>(<varname>cv</varname>); /* <remark>condvar_broadcast(cv);</remark> */ |
<function>mutex_unlock</function>(<varname>mtx</varname>);</programlisting></para> |
|
<para>The wait operation, <emphasis>condvar_wait_timeout</emphasis>, |
always puts the calling thread to sleep. The thread then sleeps until |
another thread invokes <emphasis>condvar_broadcast</emphasis> on the |
same condition variable or until it is woken up by |
<emphasis>condvar_signal</emphasis>. The |
<emphasis>condvar_signal</emphasis> operation unblocks the first thread |
blocking on the condition variable while the |
<emphasis>condvar_broadcast</emphasis> 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 <emphasis>condvar_wait_timeout</emphasis> |
and <emphasis>condvar_signal</emphasis> or |
<emphasis>condvar_broadcast</emphasis>, the mutex is passed to |
<emphasis>condvar_wait_timeout</emphasis> which then atomically puts the |
calling thread asleep and unlocks the mutex. When the thread eventually |
wakes up, <emphasis>condvar_wait</emphasis> 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 <emphasis>condvar_wait</emphasis> 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 |
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 <emphasis>waitq_sleep_timeout</emphasis>. |
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 |
<emphasis>condvar_wait_timeout</emphasis> 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 |
<emphasis>condvar_wait_timeout</emphasis>. 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 <emphasis>waitq_sleep_timeout</emphasis> |
function into three pieces:</para> |
|
<orderedlist> |
<listitem> |
<para><emphasis>waitq_sleep_prepare</emphasis> prepares the thread |
to go to sleep by, among other things, locking the wait |
queue;</para> |
</listitem> |
|
<listitem> |
<para><emphasis>waitq_sleep_timeout_unsafe</emphasis> implements the |
core blocking logic;</para> |
</listitem> |
|
<listitem> |
<para><emphasis>waitq_sleep_finish</emphasis> performs cleanup after |
<emphasis>waitq_sleep_timeout_unsafe</emphasis>; after this call, |
the wait queue spinlock is guaranteed to be unlocked by the |
caller</para> |
</listitem> |
</orderedlist> |
|
<para>The stock <emphasis>waitq_sleep_timeout</emphasis> 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 <emphasis>condvar_wait_timeout</emphasis> |
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> |
|
<orderedlist> |
<listitem> |
<para>calls <emphasis>waitq_sleep_prepare</emphasis> in order to |
lock the condition variable's wait queue,</para> |
</listitem> |
|
<listitem> |
<para>releases the mutex,</para> |
</listitem> |
|
<listitem> |
<para>clears the counter of missed wakeups,</para> |
</listitem> |
|
<listitem> |
<para>calls <emphasis>waitq_sleep_timeout_unsafe</emphasis>,</para> |
</listitem> |
|
<listitem> |
<para>retakes the mutex,</para> |
</listitem> |
|
<listitem> |
<para>calls <emphasis>waitq_sleep_finish</emphasis>.</para> |
</listitem> |
</orderedlist> |
</section> |
</section> |
|