Subversion Repositories HelenOS-doc

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

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