Subversion Repositories HelenOS-doc

      <para>In a multithreaded environment, userspace threads need an

      efficient way to synchronize. HelenOS borrows an idea from Linux<xref

      linkend="futex" /> to implement lightweight userspace synchronization

      and mutual exclusion primitive called futex. The key idea behind futexes

      is that non-contended synchronization is very fast and takes place only

      in userspace without kernel's intervention. When more threads contend

      for a futex, only one of them wins; other threads go to sleep via a

      dedicated syscall.</para>

      <para>The userspace part of the futex is a mere integer variable, a

      counter, that can be atomically incremented or decremented. The kernel

      part is rather more complicated. For each userspace futex counter, there

      is a kernel structure describing the futex. This structure

      contains:</para>

      <itemizedlist>

        <listitem>

          <para>number of references,</para>

        </listitem>

        <listitem>

          <para>physical address of the userspace futex counter,</para>

        </listitem>

        <listitem>

          <para>hash table link and</para>

        </listitem>

        <listitem>

          <para>a wait queue.</para>

        </listitem>

      </itemizedlist>

      <para>The reference count helps to find out when the futex is no longer

      needed and can be deallocated. The physical address is used as a key for

      the global futex hash table. Note that the kernel has to use physical

      address to identify the futex beacause one futex can be used for

      synchronization among different address spaces and can have different

      virtual addresses in each of them. Finally, the kernel futex structure

      includes a wait queue. The wait queue is used to put threads that didn't

      win the futex to sleep until the winner wakes one of them up.</para>

      <para>A futex should be initialized by setting its userspace counter to

      one before it is used. When locking the futex via userspace library

      function <code>futex_down_timeout</code>, the library code atomically

      decrements the futex counter and tests if it droped below zero. If it

      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

      value increased to one, then there again was no contention and no action

      needs to be done. However, if it increased to zero or even a smaller

      number, then there are sleeping threads waiting for the futex to become

      available. In that case, the library has to use the

      <constant>SYS_FUTEX_WAKEUP</constant> syscall to wake one sleeping

      <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

      futexes is that they don't need to be registered anywhere prior to the

      first kernel intervention.</para>

      <para>Both futex related syscalls, <constant>SYS_FUTEX_SLEEP</constant>

      and <constant>SYS_FUTEX_WAKEUP</constant>, respectivelly, are mere

      wrappers for <code>waitq_sleep_timeout</code> and

      <code>waitq_sleep_wakeup</code>, respectively, with some housekeeping

      functionality added. Both syscalls need to translate the userspace

      virtual address of the futex counter to physical address in order to

      support synchronization accross shared memory. Once the physical address

      is known, the kernel checks whether the futexes are already known to it

      by searching the global futex hash table for an item with the physical

      address of the futex counter as a key. When the search is successful, it

      returns an address of the kernel futex structure associated with the

      counter. If the hash table does not contain the key, the kernel creates

      it and inserts it into the hash table. At the same time, the the current

      task's B+tree of known futexes is searched in order to find out if the

      task already uses the futex. If it does, no action is taken. Otherwise

      the reference count of the futex is incremented, provided that the futex

      already existed.</para>