/design/trunk/src/ch_intro.xml |
---|
4,8 → 4,15 |
<title>Introduction</title> |
<graphic align="center" depth="" fileref="images/helenos.gif" format="GIF" |
width="197" /> |
<para> <mediaobject id="helenos"> |
<imageobject role="html"> |
<imagedata align="center" width="197" fileref="images/helenos.gif" format="GIF" /> |
</imageobject> |
<imageobject role="fop"> |
<imagedata style="antialiasing:true" align="center" fileref="images.vector/helenos.svg" format="SVG" /> |
</imageobject> |
</mediaobject></para> |
<para>The HelenOS project is an effort to develop an easily portable, light |
but durable operating system. HelenOS supports SMP, multitasking and |
/design/trunk/src/images.vector/helenos.svg |
---|
0,0 → 1,106 |
<?xml version="1.0" encoding="utf-8"?> |
<!-- Generator: Adobe Illustrator 12.0.0, SVG Export Plug-In . SVG Version: 6.00 Build 51448) --> |
<!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.1//EN" "http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd" [ |
<!ENTITY ns_svg "http://www.w3.org/2000/svg"> |
<!ENTITY ns_xlink "http://www.w3.org/1999/xlink"> |
]> |
<svg version="1.1" xmlns="&ns_svg;" xmlns:xlink="&ns_xlink;" width="207.379" height="185.525" viewBox="0 0 207.379 185.525" |
overflow="visible" enable-background="new 0 0 207.379 185.525" xml:space="preserve"> |
<g id="Layer_1"> |
<g> |
<path fill="#272827" d="M29.516,139.5h6.066v44.899h-6.066V163.45H6.065v20.949H0V139.5h6.065v18.572h23.451V139.5z"/> |
<path fill="#272827" d="M68.763,174.143c-0.188,1.188-0.75,2.627-1.688,4.44s-2.313,3.314-4.127,4.502 |
c-1.063,0.688-2.189,1.251-3.439,1.626c-1.251,0.438-3.064,0.626-5.44,0.626c-2.251,0-4.315-0.438-6.128-1.251 |
c-1.813-0.813-3.377-1.938-4.627-3.439c-1.313-1.501-2.251-3.252-2.877-5.19c-0.688-1.938-1-4.127-1-6.504 |
c0-3.439,0.563-6.565,1.751-9.317c1.126-2.751,2.876-4.94,5.19-6.504c2.376-1.563,5.315-2.376,8.755-2.376 |
c2.314,0,4.377,0.438,6.191,1.313c1.751,0.938,3.189,2.188,4.377,3.814c1.125,1.626,2.001,3.627,2.626,5.94 |
c0.563,2.314,0.875,5.003,0.875,8.005H45.313c0,3.439,0.813,6.065,2.439,7.941c1.563,1.876,3.939,2.814,7.066,2.814 |
c1.25,0,2.376-0.188,3.439-0.625c1.001-0.438,1.876-0.938,2.626-1.626c0.688-0.688,1.313-1.376,1.751-2.189 |
c0.375-0.75,0.563-1.438,0.625-2.001H68.763z M63.51,165.451c-0.188-2.876-0.938-5.253-2.376-7.066 |
c-1.376-1.813-3.627-2.688-6.754-2.688c-1.626,0-3.126,0.438-4.502,1.313c-1.438,0.938-2.564,2.126-3.377,3.689 |
s-1.188,3.126-1.188,4.752H63.51z"/> |
<path fill="#272827" d="M78.374,184.399h-5.503V139.5h5.503V184.399z"/> |
<path fill="#272827" d="M111.259,174.143c-0.188,1.188-0.75,2.627-1.688,4.44c-0.938,1.813-2.313,3.314-4.127,4.502 |
c-1.063,0.688-2.188,1.251-3.439,1.626c-1.251,0.438-3.064,0.626-5.441,0.626c-2.251,0-4.314-0.438-6.128-1.251 |
c-1.814-0.813-3.377-1.938-4.628-3.439c-1.313-1.501-2.251-3.252-2.876-5.19c-0.688-1.938-1-4.127-1-6.504 |
c0-3.439,0.563-6.565,1.751-9.317c1.125-2.751,2.876-4.94,5.19-6.504c2.376-1.563,5.315-2.376,8.755-2.376 |
c2.313,0,4.377,0.438,6.191,1.313c1.751,0.938,3.189,2.188,4.377,3.814c1.126,1.626,2.001,3.627,2.627,5.94 |
c0.563,2.314,0.875,5.003,0.875,8.005H87.809c0,3.439,0.813,6.065,2.438,7.941c1.563,1.876,3.94,2.814,7.066,2.814 |
c1.251,0,2.376-0.188,3.439-0.625c1-0.438,1.876-0.938,2.627-1.626c0.688-0.688,1.313-1.376,1.751-2.189 |
c0.375-0.75,0.563-1.438,0.625-2.001H111.259z M106.006,165.451c-0.188-2.876-0.938-5.253-2.376-7.066 |
c-1.376-1.813-3.627-2.688-6.754-2.688c-1.626,0-3.127,0.438-4.502,1.313c-1.438,0.938-2.564,2.126-3.377,3.689 |
s-1.188,3.126-1.188,4.752H106.006z"/> |
<path fill="#272827" d="M141.945,184.399h-5.504l-0.063-20.136c0-3.002-0.5-5.19-1.563-6.504 |
c-1.001-1.376-2.814-2.063-5.441-2.063c-1.25,0-2.563,0.313-3.877,1c-1.313,0.626-2.438,1.751-3.377,3.377 |
c-0.938,1.626-1.375,3.814-1.375,6.504v17.822h-5.503v-32.705h5.189v4.627h0.126c0.938-1.438,2.251-2.688,3.814-3.877 |
c1.563-1.126,3.627-1.688,6.065-1.688c1.938,0,3.814,0.313,5.503,1.001c1.688,0.625,3.127,1.813,4.315,3.502 |
c1.125,1.688,1.688,4.002,1.688,6.878V184.399z"/> |
<path fill="#272827" d="M175.256,169.454c0,2.751-0.251,5.127-0.751,7.066c-0.5,1.938-1.313,3.564-2.501,4.939 |
c-1.126,1.313-2.627,2.314-4.565,3.002c-1.876,0.688-4.189,1.063-7.004,1.063c-2.751,0-5.065-0.376-7.004-1.063 |
s-3.502-1.688-4.689-3.002c-1.188-1.375-2.001-3.063-2.502-5.002c-0.563-1.939-0.813-4.315-0.813-7.004V150.38 |
c0-4.503,1.313-7.942,3.939-10.381c2.563-2.438,6.254-3.627,11.068-3.627c4.815,0,8.505,1.188,11.069,3.627 |
c2.501,2.438,3.752,5.878,3.752,10.381V169.454z M164.25,151.13c0-1.938-0.25-3.439-0.75-4.564 |
c-0.5-1.188-1.563-1.751-3.127-1.751s-2.563,0.625-3.127,1.813c-0.563,1.188-0.813,2.688-0.813,4.502v19.261 |
c0,4.44,1.313,6.691,4.002,6.691c1.563,0,2.627-0.625,3.127-1.938c0.438-1.251,0.688-2.814,0.688-4.753V151.13z"/> |
<path fill="#272827" d="M189.12,168.703v3.314c0,1.563,0.313,2.752,1,3.689c0.626,0.938,1.751,1.376,3.377,1.376 |
c1.188,0,2.063-0.438,2.752-1.376c0.625-0.938,0.938-2.001,0.938-3.314c0-1.688-0.438-2.938-1.376-3.814 |
c-0.938-0.875-2.501-2.001-4.752-3.377c-3.939-2.251-6.754-4.314-8.317-6.128c-2.126-2.502-3.189-5.628-3.189-9.381 |
c0-2.188,0.313-4.127,1.001-5.815c0.625-1.688,1.501-3.064,2.688-4.189c1.188-1.063,2.627-1.938,4.315-2.502 |
c1.688-0.563,3.627-0.813,5.815-0.813c2.251,0,4.252,0.375,6.003,1.063c1.751,0.688,3.252,1.688,4.44,3.001 |
c1.188,1.313,2.063,2.939,2.626,4.815c0.563,1.876,0.876,4.002,0.876,6.316h-10.131c-0.063-2.189-0.313-3.815-0.688-4.94 |
c-0.375-1.063-1.376-1.688-2.939-1.813c-2.313,0-3.564,1.063-3.814,3.127c0,1.438,0.25,2.501,0.813,3.313 |
c0.563,0.813,1.375,1.626,2.501,2.439c1,0.625,2.313,1.438,4.002,2.438c1.688,0.938,2.939,1.751,3.814,2.313 |
c0.876,0.563,1.688,1.188,2.439,1.876c1.313,1.251,2.376,2.752,3.063,4.503c0.688,1.751,1.001,4.002,1.001,6.691 |
c0,2.938-0.563,5.503-1.626,7.629c-1.063,2.063-2.688,3.689-4.753,4.753c-2.126,1.063-4.689,1.626-7.754,1.626 |
c-2.376,0-4.502-0.313-6.316-0.938c-1.813-0.563-3.313-1.438-4.502-2.563c-1.188-1.126-2.063-2.377-2.627-3.814 |
c-0.563-1.438-0.875-2.939-0.875-4.503v-5.003H189.12z"/> |
</g> |
</g> |
<g id="Layer_2"> |
<path fill="#6B6B6B" d="M160.914,84.42c2.357,6.217-0.646,13.124-6.713,15.426l-72.997,27.702 |
c-6.068,2.303-12.896-0.871-15.257-7.088L37.554,45.643c-2.359-6.218,0.646-13.123,6.713-15.426l72.997-27.702 |
c6.065-2.303,12.896,0.872,15.256,7.088L160.914,84.42z"/> |
<path fill="#DEDDDD" d="M161.994,80.904c2.309,6.089-0.734,12.893-6.8,15.194l-72.991,27.699 |
c-6.067,2.303-12.856-0.768-15.168-6.857L39.224,43.659c-2.311-6.09,0.733-12.892,6.8-15.194l72.991-27.7 |
c6.064-2.302,12.855,0.769,15.167,6.858L161.994,80.904z"/> |
<path fill="#A4ADAF" d="M155.905,79.039c2.059,5.426-0.627,11.481-5.997,13.52l-64.655,24.536 |
c-5.374,2.039-11.398-0.709-13.459-6.139L47.008,45.645c-2.06-5.428,0.626-11.48,6-13.519L117.66,7.59 |
c5.374-2.039,11.4,0.709,13.458,6.136L155.905,79.039z"/> |
<path fill="#FFFFFF" d="M47.786,45.947c-2.016-5.315,0.626-11.251,5.901-13.253l63.514-24.103 |
c5.28-2.003,11.193,0.683,13.213,6.002l24.28,63.98c2.017,5.317-0.625,11.251-5.904,13.254L85.279,115.93 |
c-5.279,2.004-11.194-0.684-13.211-6L47.786,45.947z"/> |
<linearGradient id="XMLID_2_" gradientUnits="userSpaceOnUse" x1="70.8823" y1="179.5894" x2="155.9314" y2="139.9303" gradientTransform="matrix(-4.371139e-008 1 -1 -4.371139e-008 260.9996 -51.1469)"> |
<stop offset="0" style="stop-color:#FFFFFF"/> |
<stop offset="0.1147" style="stop-color:#E9E9E9"/> |
<stop offset="0.3539" style="stop-color:#B0B0B0"/> |
<stop offset="0.6936" style="stop-color:#575757"/> |
<stop offset="1" style="stop-color:#000000"/> |
</linearGradient> |
<path opacity="0.24" fill="url(#XMLID_2_)" d="M47.786,45.947c-2.016-5.315,0.626-11.251,5.901-13.253l63.514-24.103 |
c5.28-2.003,11.193,0.683,13.213,6.002l24.28,63.98c2.017,5.317-0.625,11.251-5.904,13.254L85.279,115.93 |
c-5.279,2.004-11.194-0.684-13.211-6L47.786,45.947z"/> |
</g> |
<g id="Layer_3"> |
<circle fill="#D4DBE0" stroke="#E5E5E4" cx="81.68" cy="109.059" r="2.375"/> |
<ellipse transform="matrix(0.819 -0.5738 0.5738 0.819 -47.5865 66.3171)" fill="#A4ADAF" cx="81.313" cy="108.579" rx="1.729" ry="1.247"/> |
<circle fill="#D4DBE0" stroke="#E5E5E4" cx="148.374" cy="83.394" r="2.375"/> |
<ellipse transform="matrix(0.819 -0.5738 0.5738 0.819 -20.7849 99.9422)" fill="#A4ADAF" cx="148.006" cy="82.913" rx="1.729" ry="1.247"/> |
</g> |
<g id="Layer_4"> |
<path fill="#444444" d="M124.11,78.229c-2.326,0.875-4.822-0.045-5.576-2.049l-14.853-39.55c-0.753-2.006,0.521-4.34,2.849-5.214 |
l0,0c2.327-0.875,4.823,0.044,5.577,2.05l14.853,39.55C127.712,75.021,126.437,77.356,124.11,78.229L124.11,78.229z"/> |
<path fill="#444444" d="M94.454,89.329c-2.328,0.875-4.823-0.043-5.577-2.051L74.024,47.73c-0.753-2.006,0.521-4.339,2.85-5.214 |
l0,0c2.325-0.874,4.823,0.044,5.576,2.05l14.853,39.548C98.055,86.122,96.78,88.456,94.454,89.329L94.454,89.329z"/> |
<path fill="#444444" d="M116.055,53.935c0.753,2.006,0.388,3.998-0.814,4.449l-23.729,8.911c-1.203,0.453-2.789-0.807-3.542-2.813 |
l0,0c-0.754-2.007-0.389-4,0.815-4.451l23.727-8.911C113.714,50.668,115.301,51.928,116.055,53.935L116.055,53.935z"/> |
<g id="Layer_5"> |
</g> |
</g> |
<g id="Layer_6"> |
<polygon opacity="0.78" fill="#272827" points="68.008,100.595 63.259,106.61 45.741,60.42 52.572,60.089 "/> |
<polygon fill="#848A8D" points="63.259,106.61 60.491,106.17 43.741,61.92 45.741,60.42 "/> |
</g> |
</svg> |
/design/trunk/src/ch_synchronization.xml |
---|
37,8 → 37,6 |
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 |
56,8 → 54,6 |
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 |
79,8 → 75,6 |
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 |
91,8 → 85,6 |
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, |
107,27 → 99,190 |
<title>Passive kernel synchronization</title> |
<section> |
<title>Mutexes</title> |
<title>Wait queues</title> |
<para>Mutex explanations</para> |
<para>A wait queue is the basic passive synchronization primitive on |
which all other passive synchronization primitives build. Simply put, it |
allows a thread to sleep until an event associated with the particular |
wait queue occurs. Multiple threads are notified about incoming events |
in first come, first served fashion. Moreover, should the event come |
before any thread waits for it, it is recorded in the wait queue as a |
missed wakeup and later forwarded to the first thread that decides to |
wait in the queue. The inner structures of the wait queue are protected |
by a spinlock.</para> |
<para>The thread that wants to wait for a wait queue event uses the |
<emphasis>waitq_sleep_timeout</emphasis> function. The algorithm then |
checks the wait queue's counter of missed wakeups and if there are any |
missed wakeups, the call returns immediately. The call also returns |
immediately if only a conditional wait was requested. Otherwise the |
thread is enqueued in the wait queue's list of sleeping threads and its |
state is changed to <emphasis>Sleeping</emphasis>. It then sleeps until |
one of the following events happens:</para> |
<orderedlist> |
<listitem> |
<para>another thread calls <emphasis>waitq_wakeup</emphasis> and the |
thread is the first thread in the wait queue's list of sleeping |
threads</para> |
</listitem> |
<listitem> |
<para>another thread calls |
<emphasis>waitq_interrupt_sleep</emphasis> on the sleeping |
thread</para> |
</listitem> |
<listitem> |
<para>the sleep timeouts provided that none of the previous occurred |
within a specified time limit; the limit can be infinity</para> |
</listitem> |
</orderedlist> |
<para>All five possibilities (immediate return on success, immediate |
return on failure, wakeup after sleep, interruption and timeout) are |
distinguishable by the return value of |
<emphasis>waitq_sleep_timeout</emphasis>. The ability to interrupt a |
sleeping thread is essential for externally initiated thread termination |
and the ability to wait only for a certain amount of time is used, for |
instance, to passively delay thread execution by several microseconds or |
even seconds in <emphasis>thread_sleep</emphasis> function. Because all |
other passive kernel synchronization primitives are based on wait |
queues, they also have the option of being interrutped and, more |
importantly, can timeout. All of them also implement the conditional |
operation. Furthemore, this very fundamental interface reaches up to the |
implementation of futexes - userspace synchronization primitive, which |
makes it possible for a userspace thread to request synchronization |
operation with a timeout or a conditional operation.</para> |
<para>From the description above, it should be apparent, that when a |
sleeping thread is woken by <emphasis>waitq_wakeup</emphasis> or when |
<emphasis>waitq_sleep_timeout</emphasis> succeeds immediatelly, the |
thread can be sure the event has come and the thread need not and should |
not verify this fact. This approach is called direct hand-off and is |
characteristic for all passive HelenOS synchronization primitives with |
one exception described below.</para> |
</section> |
<section> |
<title>Semaphores</title> |
<para>Semaphore explanations</para> |
<para>The interesting point about wait queues is that the number of |
missed wakeups is equal to the number of threads that will not block in |
<emphasis>watiq_sleep_timeout</emphasis> and would immediately succeed |
instead. On the other hand, semaphores are synchronization primitives |
that will let predefined amount of threads in its critical section and |
block any other threads above this count. However, these two cases are |
exactly the same. Semaphores in HelenOS are therefore implemented as |
wait queues with a single semantic change: their wait queue is |
initialized to have so many missed wakeups as is the number of threads |
that the semphore intends to let into its critical section |
simultaneously.</para> |
<para>In the semaphore language, the wait queue operation |
<emphasis>waitq_sleep_timeout</emphasis> corresponds to |
<emphasis><emphasis>semaphore</emphasis> down</emphasis> operation, |
represented by the function <emphasis>semaphore_down_timeout</emphasis> |
and by way of similitude the wait queue operation waitq_wakeup |
corresponds to semaphore <emphasis>up</emphasis> operation, represented |
by the function <emphasis>sempafore_up</emphasis>. The conditional down |
operation is called <emphasis>semaphore_trydown</emphasis>.</para> |
</section> |
<section> |
<title>Read/Write Locks</title> |
<title>Mutexes</title> |
<para>RWLocks explanation</para> |
<para>Mutexes are are sometimes referred to as binary sempahores. That |
means that mutexes are like semaphores that allow only one thread in its |
critical section. Indeed, mutexes in HelenOS are implemented exactly in |
this way: they are built atop semaphores. From another point of view, |
they can be viewed as spinlocks without busy waiting. Their semaphore |
heritage provides good basics for both conditional operation and |
operation with timeout. The locking operation is called |
<emphasis>mutex_lock</emphasis>, the conditional locking operation is |
called <emphasis>mutex_trylock</emphasis> and the unlocking operation is |
called <emphasis>mutex_unlock</emphasis>.</para> |
</section> |
<section> |
<title>Wait queues</title> |
<title>Reader/writer locks</title> |
<para>Wait queue explanation</para> |
<para>Reader/writer locks, or rwlocks, are by far the most complicated |
synchronization primitive within the kernel. The goal of these locks is |
to improve concurrency of applications in which threads need to |
synchronize access to a shared resource and that access can be |
partitioned into a read-only mode and a write mode. Reader/writer locks |
should make it possible for several, possibly many, readers to enter the |
critical section, provided that no writer is currently in the critical |
section, or to be in the critical section contemporarily. Writers are |
allowed to enter the critical section only individually, provided that |
no reader is in the critical section already. Applications in which the |
majority of operations can be done in the read-only mode can benefit |
from increased concurrency created by reader/writer locks.</para> |
<para>During reader/writer locks construction, a decision should be made |
whether readers will be prefered over writers or whether writers will be |
prefered over readers in cases when the lock is not currently held and |
both a reader and a writer want to gain the lock. Some operating systems |
prefer one group over the other, creating thus a possibility for |
starving the unprefered group. In the HelenOS operating system, none of |
the two groups is prefered. The lock is granted on the first come, first |
served basis with the additional note that readers are granted the lock |
in biggest possible batches.</para> |
<para>With this policy and the timeout modes of operation, the direct |
hand-off becomes much more complicated. For instance, a writer leaving |
the critical section must wake up all leading readers in the rwlock's |
wait queue or one leading writer or no-one if no thread is waiting. |
Similarily, the last reader leaving the critical section must wakeup the |
sleeping writer, if there are any sleeping threads at all. As another |
example, if a writer at the beginning of the rwlock's wait queue |
timeouts and the lock is held by at least one reader, the timeouting |
writer must first wake up all readers that follow him in the queue prior |
to signalling the timeout itself and giving up.</para> |
<para>Because of the issues mentioned in the previous paragraph, the |
reader/writer locks imlpementation needs to walk the rwlock wait queue's |
list of sleeping threads directly in order to find out the type of |
access that the queueing threads demand. This makes the code difficult |
to understand and dependent on the internal implementation of the wait |
queue. Nevertheless, it remains unclear to the authors of HelenOS |
whether a simpler but equivalently fair solution exists.</para> |
<para>The implementation of rwlocks as it has been already put, makes |
use of one single wait queue for both readers and writers, thus avoiding |
any possibility of starvation. In fact, rwlocks use a mutex rather than |
a bare wait queue. This mutex is called <emphasis>exclusive</emphasis> |
and is used to synchronize writers. The writer's lock operation, |
<emphasis>rwlock_write_lock_timeout</emphasis>, simply tries to acquire |
the exclusive mutex. If it succeeds, the writer is granted the rwlock. |
However, if the operation fails, the writer must check for potential |
readers at the head of the list of sleeping threads associated with the |
mutex's wait queue and proceed according to the procedure outlined |
above.</para> |
<para>The exclusive mutex plays an important role in reader |
synchronization as well. However, a reader doing the reader's lock |
operation, <emphasis>rwlock_read_lock_timeout</emphasis>, may bypass |
this mutex when it detects that:</para> |
<orderedlist> |
<listitem> |
<para>there are other readers in the critical section</para> |
</listitem> |
<listitem> |
<para>there are no sleeping threads waiting for the exclusive |
mutex</para> |
</listitem> |
</orderedlist> |
<para>If both conditions are true, the reader will bypass the mutex, |
increment the number of readers in the critical section and enter the |
critical section. Note that if there are any sleeping threads at the |
beginning of the wait queue, the first of them must be a writer. If the |
conditions are not fulfilled, the reader normally waits until the |
exclusive mutex is granted to it.</para> |
</section> |
<section> |