Subversion Repositories HelenOS-doc

      to acquire the spinlock and is called

      to acquire the spinlock and is called <code>spinlock_lock</code>. It

      test-and-set returns a zero value. The other function,

      simply loops until the test-and-set returns a zero value. The other

      <emphasis>spinlock_trylock</emphasis>, is the conditional lock operation

      function, <code>spinlock_trylock</code>, is the conditional lock

      and calls the test-and-set only once to find out whether it managed to

      operation and calls the test-and-set only once to find out whether it

      acquire the spinlock or not. The conditional operation is useful in

      managed to acquire the spinlock or not. The conditional operation is

      situations in which an algorithm cannot acquire more spinlocks in the

      useful in situations in which an algorithm cannot acquire more spinlocks

      proper order and a deadlock cannot be avoided. In such a case, the

      in the proper order and a deadlock cannot be avoided. In such a case,

      algorithm would detect the danger and instead of possibly deadlocking

      the algorithm would detect the danger and instead of possibly

      the system it would simply release some spinlocks it already holds and

      deadlocking the system it would simply release some spinlocks it already

      retry the whole operation with the hope that it will succeed next time.

      holds and retry the whole operation with the hope that it will succeed

      The unlock function, <emphasis>spinlock_unlock</emphasis>, is quite easy

      next time. The unlock function, <code>spinlock_unlock</code>, is quite

      - it merely clears the spinlock variable.</para>

      easy - it merely clears the spinlock variable.</para>

      architecture-specific hooks to all <emphasis>spinlock_lock</emphasis>,

      architecture-specific hooks to all <code>spinlock_lock</code>,

      <emphasis>spinlock_unlock</emphasis> functions to prevent the

      <code>spinlock_trylock</code> and <code>spinlock_unlock</code> functions

      instructions inside the critical section from permeating out. On some

      to prevent the instructions inside the critical section from permeating

      architectures, these hooks can be void because the dependencies are

      out. On some architectures, these hooks can be void because the

      implicitly there because of the special properties of locking and

      dependencies are implicitly there because of the special properties of

      unlocking instructions. However, other architectures need to instrument

      locking and unlocking instructions. However, other architectures need to

      these hooks with different memory barriers, depending on what operations

      instrument these hooks with different memory barriers, depending on what

      could permeate out.</para>

      operations could permeate out.</para>

      executing <emphasis>spinlock_lock</emphasis> does not do any fruitful

      executing <code>spinlock_lock</code> does not do any fruitful work and

      work and is effectively halted until it can grab the lock and proceed.

      is effectively halted until it can grab the lock and proceed.

      <emphasis>waitq_sleep_timeout</emphasis> function. The algorithm then

      <code>waitq_sleep_timeout</code> function. The algorithm then checks the

      checks the wait queue's counter of missed wakeups and if there are any

      wait queue's counter of missed wakeups and if there are any missed

      missed wakeups, the call returns immediately. The call also returns

      wakeups, the call returns immediately. The call also returns immediately

      immediately if only a conditional wait was requested. Otherwise the

      if only a conditional wait was requested. Otherwise the thread is

      thread is enqueued in the wait queue's list of sleeping threads and its

      enqueued in the wait queue's list of sleeping threads and its state is

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

      changed to <constant>Sleeping</constant>. It then sleeps until one of

      one of the following events happens:</para>

      the following events happens:</para>

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

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

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

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

          <emphasis>waitq_interrupt_sleep</emphasis> on the sleeping

          <para>another thread calls <code>waitq_interrupt_sleep</code> on the

          thread;</para>

          sleeping thread;</para>

      distinguishable by the return value of

      distinguishable by the return value of <code>waitq_sleep_timeout</code>.

      sleeping thread is essential for externally initiated thread

      Being able to interrupt a sleeping thread is essential for externally

      termination. The ability to wait only for a certain amount of time is

      initiated thread termination. The ability to wait only for a certain

      used, for instance, to passively delay thread execution by several

      amount of time is used, for instance, to passively delay thread

      microseconds or even seconds in <emphasis>thread_sleep</emphasis>

      execution by several microseconds or even seconds in

      function. Due to the fact that all other passive kernel synchronization

      <code>thread_sleep</code> function. Due to the fact that all other

      primitives are based on wait queues, they also have the option of being

      passive kernel synchronization primitives are based on wait queues, they

      interrutped and, more importantly, can timeout. All of them also

      also have the option of being interrutped and, more importantly, can

      implement the conditional operation. Furthemore, this very fundamental

      timeout. All of them also implement the conditional operation.

      interface reaches up to the implementation of futexes - userspace

      Furthemore, this very fundamental interface reaches up to the

      synchronization primitive, which makes it possible for a userspace

      implementation of futexes - userspace synchronization primitive, which

      thread to request a synchronization operation with a timeout or a

      makes it possible for a userspace thread to request a synchronization

      conditional operation.</para>

      operation with a timeout or a conditional operation.</para>

      sleeping thread is woken by <emphasis>waitq_wakeup</emphasis> or when

      sleeping thread is woken by <code>waitq_wakeup</code> or when

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

      <code>waitq_sleep_timeout</code> succeeds immediately, the thread can be

      thread can be sure that the event has occurred. The thread need not and

      sure that the event has occurred. The thread need not and should not

      should not verify this fact. This approach is called direct hand-off and

      verify this fact. This approach is called direct hand-off and is

      is characteristic for all passive HelenOS synchronization primitives,

      characteristic for all passive HelenOS synchronization primitives, with

      with the exception as described below.</para>

      the exception as described below.</para>

      <emphasis>watiq_sleep_timeout</emphasis> and would immediately succeed

      <code>watiq_sleep_timeout</code> and would immediately succeed instead.

      instead. On the other hand, semaphores are synchronization primitives

      On the other hand, semaphores are synchronization primitives that will

      that will let predefined amount of threads into their critical section

      let predefined amount of threads into their critical section and block

      and block any other threads above this count. However, these two cases

      any other threads above this count. However, these two cases are exactly

      are exactly the same. Semaphores in HelenOS are therefore implemented as

      the same. Semaphores in HelenOS are therefore implemented as wait queues

      wait queues with a single semantic change: their wait queue is

      with a single semantic change: their wait queue is initialized to have

      initialized to have so many missed wakeups as is the number of threads

      so many missed wakeups as is the number of threads that the semphore

      that the semphore intends to let into its critical section

      intends to let into its critical section simultaneously.</para>

      <emphasis>waitq_sleep_timeout</emphasis> corresponds to

      <code>waitq_sleep_timeout</code> corresponds to semaphore

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

      <code>down</code> operation, represented by the function

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

      <code>semaphore_down_timeout</code> and by way of similitude the wait

      and by way of similitude the wait queue operation waitq_wakeup

      queue operation waitq_wakeup corresponds to semaphore <code>up</code>

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

      operation, represented by the function <code>sempafore_up</code>. The

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

      conditional down operation is called

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

      <code>semaphore_trydown</code>.</para>

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

      <code>mutex_lock</code>, the conditional locking operation is called

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

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

      called <emphasis>mutex_unlock</emphasis>.</para>

      <code>mutex_unlock</code>.</para>

      a bare wait queue. This mutex is called <emphasis>exclusive</emphasis>

      a bare wait queue. This mutex is called <code>exclusive</code> and is

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

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

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

      <code>rwlock_write_lock_timeout</code>, simply tries to acquire the

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

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

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

      operation, <code>rwlock_read_lock_timeout</code>, may bypass this mutex

      this mutex when it detects that:</para>

      when it detects that:</para>

      <para>The wait operation, <emphasis>condvar_wait_timeout</emphasis>,

      <para>The wait operation, <code>condvar_wait_timeout</code>, always puts

      always puts the calling thread to sleep. The thread then sleeps until

      the calling thread to sleep. The thread then sleeps until another thread

      another thread invokes <emphasis>condvar_broadcast</emphasis> on the

      invokes <code>condvar_broadcast</code> on the same condition variable or

      <emphasis>condvar_signal</emphasis>. The

      until it is woken up by <code>condvar_signal</code>. The

      <emphasis>condvar_signal</emphasis> operation unblocks the first thread

      <code>condvar_signal</code> operation unblocks the first thread blocking

      blocking on the condition variable while the

      on the condition variable while the <code>condvar_broadcast</code>

      blocking there. If there are no blocking threads, these two operations

      operation unblocks all threads blocking there. If there are no blocking

      have no efect.</para>

      threads, these two operations have no efect.</para>

      prevent race condition between <emphasis>condvar_wait_timeout</emphasis>

      prevent race condition between <code>condvar_wait_timeout</code> and

      <emphasis>condvar_broadcast</emphasis>, the mutex is passed to

      <code>condvar_signal</code> or <code>condvar_broadcast</code>, the mutex

      <emphasis>condvar_wait_timeout</emphasis> which then atomically puts the

      is passed to <code>condvar_wait_timeout</code> which then atomically

      calling thread asleep and unlocks the mutex. When the thread eventually

      puts the calling thread asleep and unlocks the mutex. When the thread

      wakes up, <emphasis>condvar_wait</emphasis> regains the mutex and

      eventually wakes up, <code>condvar_wait</code> regains the mutex and

      thread and because <emphasis>condvar_wait</emphasis> must always go to

      thread and because <code>condvar_wait</code> must always go to sleep.

      sleep. The operation with timeout is supported as usually.</para>

      The operation with timeout is supported as usually.</para>

      picked up by a call to <emphasis>waitq_sleep_timeout</emphasis>.

      picked up by a call to <code>waitq_sleep_timeout</code>. Therefore, if

      Therefore, if wait queues were used directly and without any changes to

      wait queues were used directly and without any changes to implement

      implement condition variables, the missed_wakeup counter would hurt

      condition variables, the missed_wakeup counter would hurt performance of

      performance of the implementation: the <code>while</code> loop in

      the implementation: the <code>while</code> loop in

      <emphasis>condvar_wait_timeout</emphasis> would effectively do busy

      <code>condvar_wait_timeout</code> would effectively do busy waiting

      waiting until all missed wakeups were discarded.</para>

      until all missed wakeups were discarded.</para>

      <emphasis>condvar_wait_timeout</emphasis>. More precisely, the thread

      <code>condvar_wait_timeout</code>. More precisely, the thread should

      should sleep in the condvar's wait queue prior to releasing the mutex,

      sleep in the condvar's wait queue prior to releasing the mutex, but it

      but it must not hold the mutex when it is sleeping.</para>

      must not hold the mutex when it is sleeping.</para>

      HelenOS by dividing the <emphasis>waitq_sleep_timeout</emphasis>

      HelenOS by dividing the <code>waitq_sleep_timeout</code> function into

      function into three pieces:</para>

      three pieces:</para>

          <para><emphasis>waitq_sleep_prepare</emphasis> prepares the thread

          <para><code>waitq_sleep_prepare</code> prepares the thread to go to

          to go to sleep by, among other things, locking the wait

          sleep by, among other things, locking the wait queue;</para>

          <para><emphasis>waitq_sleep_timeout_unsafe</emphasis> implements the

          <para><code>waitq_sleep_timeout_unsafe</code> implements the core

          core blocking logic;</para>

          blocking logic;</para>

          <para><emphasis>waitq_sleep_finish</emphasis> performs cleanup after

          <para><code>waitq_sleep_finish</code> performs cleanup after

          <emphasis>waitq_sleep_timeout_unsafe</emphasis>; after this call,

          <code>waitq_sleep_timeout_unsafe</code>; after this call, the wait

          the wait queue spinlock is guaranteed to be unlocked by the

          queue spinlock is guaranteed to be unlocked by the caller</para>

      <para>The stock <emphasis>waitq_sleep_timeout</emphasis> is then a mere

      <para>The stock <code>waitq_sleep_timeout</code> is then a mere wrapper

      wrapper that calls these three functions. It is provided for convenience

      that calls these three functions. It is provided for convenience in

      in cases where the caller doesn't require such a low level control.

      cases where the caller doesn't require such a low level control.

      However, the implementation of <emphasis>condvar_wait_timeout</emphasis>

      However, the implementation of <code>condvar_wait_timeout</code> does

      does need this finer-grained control because it has to interleave calls

      need this finer-grained control because it has to interleave calls to

      to these functions by other actions. It carries its operations out in

      these functions by other actions. It carries its operations out in the

      the following order:</para>

      following order:</para>

          <para>calls <emphasis>waitq_sleep_prepare</emphasis> in order to

          <para>calls <code>waitq_sleep_prepare</code> in order to lock the

          lock the condition variable's wait queue,</para>

          condition variable's wait queue,</para>

          <para>calls <emphasis>waitq_sleep_timeout_unsafe</emphasis>,</para>

          <para>calls <code>waitq_sleep_timeout_unsafe</code>,</para>

          <para>calls <emphasis>waitq_sleep_finish</emphasis>.</para>

          <para>calls <code>waitq_sleep_finish</code>.</para>