WebSVN – HelenOS-doc – Diff – /design/trunk/src/ch_synchronization.xml

     highly concurrent environment needs safe and efficient ways to handle
     mutual exclusion and synchronization of many execution flows.</para>
   </section>
   <section>
-    <title>Active kernel primitives</title>
+    <title>Active Kernel Primitives</title>
     <section>
       <indexterm>
         <primary>synchronization</primary>
       critical section and those that implement locking and unlocking of the
       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
+      <code>spinlock_trylock()</code> and <code>spinlock_unlock()</code>
-      to prevent the instructions inside the critical section from permeating
+      functions to prevent the instructions inside the critical section from
-      out. On some architectures, these hooks can be void because the
+      permeating out. On some architectures, these hooks can be void because
-      dependencies are implicitly there because of the special properties of
+      the dependencies are implicitly there because of the special properties
-      locking and unlocking instructions. However, other architectures need to
+      of locking and unlocking instructions. However, other architectures need
-      instrument these hooks with different memory barriers, depending on what
+      to instrument these hooks with different memory barriers, depending on
-      operations could permeate out.</para>
+      what operations could permeate out.</para>
       <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
       is effectively halted until it can grab the lock and proceed.
       synchronization primitives.</para>
     </section>
   </section>
   <section>
-    <title>Passive kernel synchronization</title>
+    <title>Passive Kernel Synchronization</title>
     <section>
       <indexterm>
         <primary>synchronization</primary>
         <secondary>- wait queue</secondary>
       </indexterm>
-      <title>Wait queues</title>
+      <title>Wait Queues</title>
       <para>A wait queue is the basic passive synchronization primitive on
       which all other passive synchronization primitives are built. Simply
       put, it allows a thread to sleep until an event associated with the
       particular wait queue occurs. Multiple threads are notified about
       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 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
-      wait queue's counter of missed wakeups and if there are any missed
+      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 <constant>Sleeping</constant>. It then sleeps until one of
       the following events happens:</para>
       <orderedlist>
         <listitem>
-          <para>another thread calls <code>waitq_wakeup()</code> and the thread
+          <para>another thread calls <code>waitq_wakeup()</code> and the
-          is the first thread in the wait queue's list of sleeping
+          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
-          sleeping thread;</para>
+          the sleeping thread;</para>
         </listitem>
         <listitem>
           <para>the sleep times out provided that none of the previous
           occurred within a specified time limit; the limit can be
         </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 <code>waitq_sleep_timeout()</code>.
+      distinguishable by the return value of
-      Being able to interrupt a sleeping thread is essential for externally
+      <code>waitq_sleep_timeout()</code>. Being able to interrupt a sleeping
-      initiated thread termination. The ability to wait only for a certain
+      thread is essential for externally initiated thread termination. The
-      amount of time is used, for instance, to passively delay thread
+      ability to wait only for a certain amount of time is used, for instance,
-      execution by several microseconds or even seconds in
+      to passively delay thread execution by several microseconds or even
-      <code>thread_sleep()</code> function. Due to the fact that all other
+      seconds in <code>thread_sleep()</code> function. Due to the fact that
-      passive kernel synchronization primitives are based on wait queues, they
+      all other passive kernel synchronization primitives are based on wait
-      also have the option of being interrutped and, more importantly, can
+      queues, they also have the option of being interrutped and, more
-      timeout. All of them also implement the conditional operation.
+      importantly, can timeout. All of them also implement the conditional
-      Furthemore, this very fundamental interface reaches up to the
+      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 a 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 <code>waitq_wakeup()</code> or when
-      <code>waitq_sleep_timeout()</code> succeeds immediately, the thread can be
+      <code>waitq_sleep_timeout()</code> succeeds immediately, the thread can
-      sure that the event has occurred. The thread need not and should not
+      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
       the exception as described below.</para>
     </section>
       <title>Semaphores</title>
       <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
-      On the other hand, semaphores are synchronization primitives that will
+      instead. On the other hand, semaphores are synchronization primitives
-      let predefined amount of threads into their critical section and block
+      that will let predefined amount of threads into their critical section
-      any other threads above this count. However, these two cases are exactly
+      and block any other threads above this count. However, these two cases
-      the same. Semaphores in HelenOS are therefore implemented as wait queues
+      are exactly the same. Semaphores in HelenOS are therefore implemented as
-      with a single semantic change: their wait queue is initialized to have
+      wait queues with a single semantic change: their wait queue is
-      so many missed wakeups as is the number of threads that the semphore
+      initialized to have so many missed wakeups as is the number of threads
-      intends to let into its critical section simultaneously.</para>
+      that the semphore 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>down</code> operation, represented by the function
       <code>semaphore_down_timeout()</code> and by way of similitude the wait
       <code>mutex_trylock()</code> and the unlocking operation is called
       <code>mutex_unlock()</code>.</para>
     </section>
     <section>
-      <title>Reader/writer locks</title>
+      <title>Reader/Writer Locks</title>
       <indexterm>
         <primary>synchronization</primary>
         <secondary>- read/write lock</secondary>
       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
+      a bare wait queue. This mutex is called <emphasis>exclusive</emphasis>
-      used to synchronize writers. The writer's lock operation,
+      and is used to synchronize writers. The writer's lock operation,
       <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
       associated with the mutex's wait queue and then 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, <code>rwlock_read_lock_timeout()</code>, may bypass this mutex
+      operation, <code>rwlock_read_lock_timeout()</code>, may bypass this
-      when it detects that:</para>
+      mutex when it detects that:</para>
       <orderedlist>
         <listitem>
           <para>there are other readers in the critical section and</para>
         </listitem>
       conditions are not fulfilled, the reader normally waits until the
       exclusive mutex is granted to it.</para>
     </section>
     <section>
-      <title>Condition variables</title>
+      <title>Condition Variables</title>
       <indexterm>
         <primary>synchronization</primary>
         <secondary>- condition variable</secondary>
 <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>
       </example>
-      <para>The wait operation, <code>condvar_wait_timeout()</code>, always puts
+      <para>The wait operation, <code>condvar_wait_timeout()</code>, always
-      the calling thread to sleep. The thread then sleeps until another thread
+      puts the calling thread to sleep. The thread then sleeps until another
-      invokes <code>condvar_broadcast()</code> on the same condition variable or
+      thread invokes <code>condvar_broadcast()</code> on the same condition
-      until it is woken up by <code>condvar_signal()</code>. The
+      variable or until it is woken up by <code>condvar_signal()</code>. The
-      <code>condvar_signal()</code> operation unblocks the first thread blocking
+      <code>condvar_signal()</code> operation unblocks the first thread
-      on the condition variable while the <code>condvar_broadcast()</code>
+      blocking on the condition variable while the
-      operation unblocks all threads blocking there. If there are no blocking
+      <code>condvar_broadcast()</code> operation unblocks all threads blocking
-      threads, these two operations have no efect.</para>
+      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
+      <code>condvar_signal()</code> or <code>condvar_broadcast()</code>, the
-      is passed to <code>condvar_wait_timeout()</code> which then atomically
+      mutex is passed to <code>condvar_wait_timeout()</code> which then
-      puts the calling thread asleep and unlocks the mutex. When the thread
+      atomically puts the calling thread asleep and unlocks the mutex. When
-      eventually wakes up, <code>condvar_wait()</code> regains the mutex and
+      the thread eventually wakes up, <code>condvar_wait()</code> regains the
-      returns.</para>
+      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.
       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
-          sleep by, among other things, locking the wait queue;</para>
+          to sleep by, among other things, locking the wait queue;</para>
         </listitem>
         <listitem>
           <para><code>waitq_sleep_timeout_unsafe()</code> implements the core
           blocking logic;</para>
           <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
-      that calls these three functions. It is provided for convenience in
+      wrapper that calls these three functions. It is provided for convenience
-      cases where the caller doesn't require such a low level control.
+      in cases where the caller doesn't require such a low level control.
       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>
       </orderedlist>
     </section>
   </section>
   <section>
-    <title>Userspace synchronization</title>
+    <title>Userspace Synchronization</title>
     <section>
       <title>Futexes</title>
       <indexterm>
       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.
       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
-      value increased to one, then there again was no contention and no action
+      counter value increased to one, then there again was no contention and
-      needs to be done. However, if it increased to zero or even a smaller
+      no action needs to be done. However, if it increased to zero or even a
-      number, then there are sleeping threads waiting for the futex to become
+      smaller number, then there are sleeping threads waiting for the futex to
-      available. In that case, the library has to use the
+      become available. In that case, the library has to use the
       <constant>SYS_FUTEX_WAKEUP</constant> syscall to wake one sleeping
       thread.</para>
       <para>So far, futexes are very elegant in that they don't interfere with
       the kernel when there is no contention for them. Another nice aspect of

Subversion Repositories HelenOS-doc

(root)/design/trunk/src/ch_synchronization.xml – Rev 102 → 131