Subversion Repositories HelenOS-doc

Rev

Rev 11 | Rev 44 | Go to most recent revision | Blame | Compare with Previous | Last modification | View Log | Download | RSS feed

  1. <?xml version="1.0" encoding="UTF-8"?>
  2. <chapter id="sync">
  3.   <?dbhtml filename="sync.html"?>
  4.  
  5.   <title>Mutual exclusion and synchronization</title>
  6.  
  7.   <section>
  8.     <title>Introduction</title>
  9.  
  10.     <para>The HelenOS operating system is designed to make use of parallelism
  11.     offered by hardware and to exploit concurrency of both the kernel and
  12.     userspace tasks. This is achieved through multiprocessor support and
  13.     several levels of multiprogramming (i.e. multitasking, multithreading and
  14.     through userspace pseudo threads). However, such a highly concurrent
  15.     environment needs safe and efficient ways to handle mutual exclusion and
  16.     synchronization of many execution flows.</para>
  17.   </section>
  18.  
  19.   <section>
  20.     <title>Active kernel primitives</title>
  21.  
  22.     <section>
  23.       <title>Spinlocks</title>
  24.  
  25.       <para>The basic mutual exclusion primitive is the spinlock. Spinlock
  26.       implements busy waiting for an availability of a memory lock (i.e.
  27.       simple variable) in a multiprocessor-safe manner. This safety is
  28.       achieved through the use of a specialized, architecture-dependent,
  29.       atomic test-and-set operation which either locks the spinlock (i.e. sets
  30.       the variable) or, provided that it is already locked, leaves it
  31.       unaltered. In any case, the test-and-set operation returns a value, thus
  32.       signalling either success (i.e. zero return value) or failure (i.e.
  33.       non-zero value) in acquiring the lock. Note that this makes the
  34.       fundamental difference between the naive algorithm that doesn't use the
  35.      atomic operation and the spinlock algortihm. While the naive algorithm
  36.      is prone to race conditions on SMP configuratinos and thus is completely
  37.      SMP-unsafe, the spinlock algorithm eliminates the possibility of race
  38.      conditions and is suitable for mutual exclusion use.</para>
  39.  
  40.      <para></para>
  41.  
  42.      <para>The semantics of the test-and-set operation is that the spinlock
  43.      remains unavailable until this operation called on the respective
  44.      spinlock returns zero. HelenOS builds two functions on top of
  45.      test-and-set operation. The first is the unconditional attempt to
  46.      acquire the spinlock and is called <emphasis>spinlock_lock</emphasis>.
  47.      It simply loops until test-and-set returns zero. The other operation,
  48.      <emphasis>spinlock_trylock</emphasis>, is the conditional lock operation
  49.      and calls the test-and-set only once to find out wheter it managed to
  50.      acquire the spinlock or not. The conditional operation is useful in
  51.      situations in which an algorithm cannot acquire more spinlocks in the
  52.      proper order and a deadlock cannot be avoided. In such a case, the
  53.      algorithm would detect the danger and instead of possibly deadlocking
  54.      the system it would simply release some spinlocks it already holds and
  55.      retry the whole operation with the hope that it will succeed next time.
  56.      The unlock operation, <emphasis>spinlock_unlock</emphasis>, is quite
  57.      easy - it merely clears the spinlock variable.</para>
  58.  
  59.      <para></para>
  60.  
  61.      <para>Nevertheless, there is a special issue related to hardware
  62.      optimizations that modern processors implement. Particularily
  63.      problematic is the out-of-order execution of instructions within the
  64.      critical section protected by a spinlock. The processors are always
  65.      self-consistent so that they can carry out speculatively executed
  66.      instructions in the right order with regard to dependencies among those
  67.      instructions. However, the dependency between instructions inside the
  68.      critical section and those that implement locking and unlocking of the
  69.      respective spinlock is not implicit on some processor architectures and
  70.      the processor needs to be explicitly told about each occurrence of such
  71.      a dependency. Therefore, HelenOS adds architecture-specific hooks to all
  72.      <emphasis>spinlock_lock</emphasis>,
  73.      <emphasis>spinlock_trylock</emphasis> and
  74.      <emphasis>spinlock_unlock</emphasis> to prevent the instructions inside
  75.      the critical section from bleeding out. On some architectures, these
  76.      hooks can be a no-op because the dependencies are implicitly there
  77.      because of the special properties of locking and unlocking instructions.
  78.      However, other architectures need to instrument these hooks with
  79.      different memory barriers, depending on what operations can bleed
  80.      out.</para>
  81.  
  82.      <para></para>
  83.  
  84.      <para>Spinlocks have one significant drawback: when held for longer time
  85.      periods, they harm both parallelism and concurrency. Processor executing
  86.      <emphasis>spinlock_lock</emphasis> does not do any fruitful work and is
  87.      effectively halted until it can grab the lock and proceed. Similarily,
  88.      other threads cannot execute on the processor that holds the spinlock
  89.      because the kernel disables preemption on that processor when a spinlock
  90.      is held. The reason behind disabling preemption is priority inversion
  91.      problem avoidance. For the same reason, threads are strongly discouraged
  92.      from sleeping when they hold a spinlock.</para>
  93.  
  94.      <para></para>
  95.  
  96.      <para>To summarize, spinlocks represent very simple and essential mutual
  97.      exclusion primitive for SMP systems. On the other hand, spinlocks scale
  98.      poorly because of the active loop they are based on. Therefore,
  99.      spinlocks are used in HelenOS only for a short-time mutual exclusion and
  100.      in cases where the mutual exclusion is required out of thread context.
  101.      Lastly, spinlocks are used in the construction of passive
  102.      synchronization primitives.</para>
  103.    </section>
  104.  </section>
  105.  
  106.  <section>
  107.    <title>Passive kernel synchronization</title>
  108.  
  109.    <section>
  110.      <title>Mutexes</title>
  111.  
  112.      <para>Mutex explanations</para>
  113.    </section>
  114.  
  115.    <section>
  116.      <title>Semaphores</title>
  117.  
  118.      <para>Semaphore explanations</para>
  119.    </section>
  120.  
  121.    <section>
  122.      <title>Read/Write Locks</title>
  123.  
  124.      <para>RWLocks explanation</para>
  125.    </section>
  126.  
  127.    <section>
  128.      <title>Wait queues</title>
  129.  
  130.      <para>Wait queue explanation</para>
  131.    </section>
  132.  
  133.    <section>
  134.      <title>Condition variables</title>
  135.  
  136.      <para>Condvars explanation</para>
  137.    </section>
  138.  </section>
  139.  
  140.  <section>
  141.    <title>Userspace synchronization</title>
  142.  
  143.    <section>
  144.      <title>Futexes</title>
  145.  
  146.      <para></para>
  147.    </section>
  148.  </section>
  149. </chapter>