| 1,64 → 1,149 |
|---|
| <?xml version="1.0" encoding="UTF-8"?> |
| <chapter id="sync"> |
| <?dbhtml filename="sync.html"?> |
| |
| <title>Mutual exclusion and synchronization</title> |
| |
| <chapter id="sync"><?dbhtml filename="sync.html"?> |
| <title>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>Introduction. Concept.</title> |
| <title>Spinlocks</title> |
| |
| <para>Couple of words about global conception of sychronization</para> |
| </section> |
| <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> |
| |
| <section> |
| <title>Active kernel synchronization. Spinlock.</title> |
| <para>Spinlocks explanation. Arch specific notes.</para> |
| </section> |
| <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> |
| |
| <section> |
| <title>Passive kernel synchronization</title> |
| <para></para> |
| |
| <section> |
| <title>Mutex</title> |
| <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>Mutex explanations</para> |
| </section> |
| <para></para> |
| |
| <section> |
| <title>Semaphore</title> |
| <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> |
| |
| <para>Semaphore explanations</para> |
| </section> |
| <section> |
| <title>Passive kernel synchronization</title> |
| |
| <section> |
| <title>Read/Write Locks</title> |
| <section> |
| <title>Mutexes</title> |
| |
| <para>RWLocks explanation</para> |
| </section> |
| <para>Mutex explanations</para> |
| </section> |
| |
| <section> |
| <title>Wait queues</title> |
| <section> |
| <title>Semaphores</title> |
| |
| <para>Wait queue explanation</para> |
| </section> |
| <para>Semaphore explanations</para> |
| </section> |
| |
| <section> |
| <title>Read/Write Locks</title> |
| |
| <section> |
| <title>Conditional variables</title> |
| <para>RWLocks explanation</para> |
| </section> |
| |
| <para>Condvars explanation</para> |
| </section> |
| </section> |
| <section> |
| <title>Wait queues</title> |
| |
| <para>Wait queue explanation</para> |
| </section> |
| |
| <section> |
| <title>Userspace synchronization. Futex.</title> |
| <title>Condition variables</title> |
| |
| <para>Idea. Futex explanation.</para> |
| <para>Condvars explanation</para> |
| </section> |
| </section> |
| |
| </chapter> |
| <section> |
| <title>Userspace synchronization</title> |
| |
| <section> |
| <title>Futexes</title> |
| |
| <para></para> |
| </section> |
| </section> |
| </chapter> |