| 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> |
| |