1,34 → 1,119 |
<?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. Concept.</title> |
<title>Introduction</title> |
|
<para>Couple of words about global conception of sychronization</para> |
<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>Active kernel synchronization. Spinlock.</title> |
<para>Spinlocks explanation. Arch specific notes.</para> |
</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>Mutex</title> |
<title>Mutexes</title> |
|
<para>Mutex explanations</para> |
</section> |
|
<section> |
<title>Semaphore</title> |
<title>Semaphores</title> |
|
<para>Semaphore explanations</para> |
</section> |
45,20 → 130,20 |
<para>Wait queue explanation</para> |
</section> |
|
|
<section> |
<title>Conditional variables</title> |
<title>Condition variables</title> |
|
<para>Condvars explanation</para> |
</section> |
</section> |
|
<section> |
<title>Userspace synchronization</title> |
|
<section> |
<title>Userspace synchronization. Futex.</title> |
<title>Futexes</title> |
|
<para>Idea. Futex explanation.</para> |
<para></para> |
</section> |
|
</chapter> |
|
</section> |
</chapter> |