Subversion Repositories HelenOS-doc

<?xml version="1.0" encoding="UTF-8"?>

<chapter id="sync">

  <?dbhtml filename="sync.html"?>

  <title>Mutual exclusion and synchronization</title>

  <section>

    <title>Introduction</title>

    <para>The HelenOS operating system is designed to make use of parallelism

    offered by hardware and to exploit concurrency of both the kernel and

    userspace tasks. This is achieved through multiprocessor support and

    several levels of multiprogramming (i.e. multitasking, multithreading and

    through userspace pseudo threads). However, such a 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>

    <section>

      <title>Spinlocks</title>

      <para>The basic mutual exclusion primitive is the spinlock. Spinlock

      implements busy waiting for an availability of a memory lock (i.e.

      simple variable) in a multiprocessor-safe manner. This safety is

      achieved through the use of a specialized, architecture-dependent,

      atomic test-and-set operation which either locks the spinlock (i.e. sets

      the variable) or, provided that it is already locked, leaves it

      unaltered. In any case, the test-and-set operation returns a value, thus

      signalling either success (i.e. zero return value) or failure (i.e.

      non-zero value) in acquiring the lock. Note that this makes the

      fundamental difference between the naive algorithm that doesn't use the

      atomic operation and the spinlock algortihm. While the naive algorithm

      is prone to race conditions on SMP configuratinos and thus is completely

      SMP-unsafe, the spinlock algorithm eliminates the possibility of race

      conditions and is suitable for mutual exclusion use.</para>

      <para></para>

      <para>The semantics of the test-and-set operation is that the spinlock

      remains unavailable until this operation called on the respective

      spinlock returns zero. HelenOS builds two functions on top of

      test-and-set operation. The first is the unconditional attempt to

      acquire the spinlock and is called <emphasis>spinlock_lock</emphasis>.

      It simply loops until test-and-set returns zero. The other operation,

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

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

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

      situations in which an algorithm cannot acquire more spinlocks in the

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

      algorithm would detect the danger and instead of possibly deadlocking

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

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

      The unlock operation, <emphasis>spinlock_unlock</emphasis>, is quite

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

      <para></para>

      <para>Nevertheless, there is a special issue related to hardware

      optimizations that modern processors implement. Particularily

      problematic is the out-of-order execution of instructions within the

      critical section protected by a spinlock. The processors are always

      self-consistent so that they can carry out speculatively executed

      instructions in the right order with regard to dependencies among those

      instructions. However, the dependency between instructions inside the

      critical section and those that implement locking and unlocking of the

      respective spinlock is not implicit on some processor architectures and

      the processor needs to be explicitly told about each occurrence of such

      a dependency. Therefore, HelenOS adds architecture-specific hooks to all

      <emphasis>spinlock_lock</emphasis>,

      <emphasis>spinlock_trylock</emphasis> and

      <emphasis>spinlock_unlock</emphasis> to prevent the instructions inside

      the critical section from bleeding out. On some architectures, these

      hooks can be a no-op because the dependencies are implicitly there

      because of the special properties of locking and unlocking instructions.

      However, other architectures need to instrument these hooks with

      different memory barriers, depending on what operations can bleed

      out.</para>

      <para></para>

      <para>Spinlocks have one significant drawback: when held for longer time

      periods, they harm both parallelism and concurrency. Processor executing

      <emphasis>spinlock_lock</emphasis> does not do any fruitful work and is

      effectively halted until it can grab the lock and proceed. Similarily,

      other threads cannot execute on the processor that holds the spinlock

      because the kernel disables preemption on that processor when a spinlock

      is held. The reason behind disabling preemption is priority inversion

      problem avoidance. For the same reason, threads are strongly discouraged

      from sleeping when they hold a spinlock.</para>

      <para></para>

      <para>To summarize, spinlocks represent very simple and essential mutual

      exclusion primitive for SMP systems. On the other hand, spinlocks scale

      poorly because of the active loop they are based on. Therefore,

      spinlocks are used in HelenOS only for a short-time mutual exclusion and

      in cases where the mutual exclusion is required out of thread context.

      Lastly, spinlocks are used in the construction of passive

      synchronization primitives.</para>

    </section>

  </section>

  <section>

    <title>Passive kernel synchronization</title>

    <section>

      <title>Mutexes</title>

      <para>Mutex explanations</para>

    </section>

    <section>

      <title>Semaphores</title>

      <para>Semaphore explanations</para>

    </section>

    <section>

      <title>Read/Write Locks</title>

      <para>RWLocks explanation</para>

    </section>

    <section>

      <title>Wait queues</title>

      <para>Wait queue explanation</para>

    </section>

    <section>

      <title>Condition variables</title>

      <para>Condvars explanation</para>

    </section>

  </section>

  <section>

    <title>Userspace synchronization</title>

    <section>

      <title>Futexes</title>

      <para></para>

    </section>

  </section>

</chapter>