Subversion Repositories HelenOS-doc

      <para>A wait queue is the basic passive synchronization primitive on

      which all other passive synchronization primitives build. Simply put, it

      allows a thread to sleep until an event associated with the particular

      wait queue occurs. Multiple threads are notified about incoming events

      in first come, first served fashion. Moreover, should the event come

      before any thread waits for it, it is recorded in the wait queue as a

      missed wakeup and later forwarded to the first thread that decides to

      wait in the queue. The inner structures of the wait queue are protected

      <para>The thread that wants to wait for a wait queue event uses the

      <emphasis>waitq_sleep_timeout</emphasis> 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 enqueued in the wait queue's list of sleeping threads and its

      state is changed to <emphasis>Sleeping</emphasis>. It then sleeps until

      one of the following events happens:</para>

      <orderedlist>

        <listitem>

          <para>another thread calls <emphasis>waitq_wakeup</emphasis> and the

          thread is the first thread in the wait queue's list of sleeping

          threads</para>

        </listitem>

        <listitem>

          <para>another thread calls

          <emphasis>waitq_interrupt_sleep</emphasis> on the sleeping

          thread</para>

        </listitem>

        <listitem>

          <para>the sleep timeouts provided that none of the previous occurred

          within a specified time limit; the limit can be infinity</para>

        </listitem>

      </orderedlist>

      <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

      <emphasis>waitq_sleep_timeout</emphasis>. The ability to interrupt a

      sleeping thread is essential for externally initiated thread termination

      and 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 <emphasis>thread_sleep</emphasis> function. Because 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. Furthemore, this very fundamental interface reaches up to the

      implementation of futexes - userspace synchronization primitive, which

      makes it possible for a userspace thread to request synchronization

      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 <emphasis>waitq_wakeup</emphasis> or when

      <emphasis>waitq_sleep_timeout</emphasis> succeeds immediatelly, the

      thread can be sure the event has come and 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

      one exception described below.</para>

      <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

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

      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

      simultaneously.</para>

      <emphasis>waitq_sleep_timeout</emphasis> corresponds to

      <emphasis><emphasis>semaphore</emphasis> down</emphasis> operation,

      represented by the function <emphasis>semaphore_down_timeout</emphasis>

      and by way of similitude the wait queue operation waitq_wakeup

      corresponds to semaphore <emphasis>up</emphasis> operation, represented

      by the function <emphasis>sempafore_up</emphasis>. The conditional down

      operation is called <emphasis>semaphore_trydown</emphasis>.</para>

      <para>Mutexes are are sometimes referred to as binary sempahores. That

      means that mutexes are like semaphores that allow only one thread in its

      critical section. Indeed, mutexes in HelenOS are implemented exactly in

      this way: they are built atop semaphores. From another point of 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

      <emphasis>mutex_lock</emphasis>, the conditional locking operation is

      called <emphasis>mutex_trylock</emphasis> and the unlocking operation is

      <para>Reader/writer locks, or rwlocks, are by far the most complicated

      synchronization primitive within the kernel. The goal of these locks is

      to improve concurrency of applications in which threads need to

      synchronize access to a shared resource and that access can be

      partitioned into a read-only mode and a write mode. Reader/writer locks

      should make it possible for several, possibly many, readers to enter the

      critical section, provided that no writer is currently in the critical

      section, or to be in the critical section contemporarily. Writers are

      allowed to enter the critical section only individually, provided that

      no reader is in the critical section already. Applications in which the

      majority of operations can be done in the read-only mode can benefit

      from increased concurrency created by reader/writer locks.</para>

      <para>During reader/writer locks construction, a decision should be made

      whether readers will be prefered over writers or whether writers will be

      prefered over readers in cases when the lock is not currently held and

      both a reader and a writer want to gain the lock. Some operating systems

      prefer one group over the other, creating thus a possibility for

      starving the unprefered group. In the HelenOS operating system, none of

      the two groups is prefered. The lock is granted on the first come, first

      served basis with the additional note that readers are granted the lock

      <para>With this policy and the timeout modes of operation, the direct

      hand-off becomes much more complicated. For instance, a writer leaving

      the critical section must wake up all leading readers in the rwlock's

      wait queue or one leading writer or no-one if no thread is waiting.

      Similarily, the last reader leaving the critical section must wakeup the

      sleeping writer, if there are any sleeping threads at all. As another

      example, if a writer at the beginning of the rwlock's wait queue

      timeouts and the lock is held by at least one reader, the timeouting

      writer must first wake up all readers that follow him in the queue prior

      to signalling the timeout itself and giving up.</para>

      <para>Because of the issues mentioned in the previous paragraph, the

      reader/writer locks imlpementation needs to walk the rwlock wait queue's

      list of sleeping threads directly in order to find out the type of

      access that the queueing threads demand. This makes the code difficult

      to understand and dependent on the internal implementation of the wait

      queue. Nevertheless, it remains unclear to the authors of HelenOS

      whether a simpler but equivalently fair solution exists.</para>

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

      and is used to synchronize writers. The writer's lock operation,

      <emphasis>rwlock_write_lock_timeout</emphasis>, simply tries to acquire

      the exclusive mutex. If it succeeds, the writer is granted the rwlock.

      However, if the operation fails, the writer must check for potential

      readers at the head of the list of sleeping threads associated with the

      mutex's wait queue and proceed according to the procedure outlined

      above.</para>

      <para>The exclusive mutex plays an important role in reader

      synchronization as well. However, a reader doing the reader's lock

      operation, <emphasis>rwlock_read_lock_timeout</emphasis>, may bypass

      this mutex when it detects that:</para>

      <orderedlist>

        <listitem>

          <para>there are other readers in the critical section</para>

        </listitem>

        <listitem>

          <para>there are no sleeping threads waiting for the exclusive

          mutex</para>

        </listitem>

      </orderedlist>

      <para>If both conditions are true, the reader will bypass the mutex,

      increment the number of readers in the critical section and enter the

      critical section. Note that if there are any sleeping threads at the

      beginning of the wait queue, the first of them must be a writer. If the

      conditions are not fulfilled, the reader normally waits until the

      exclusive mutex is granted to it.</para>