Subversion Repositories HelenOS-doc

Compare Revisions

Ignore whitespace Rev 47 → Rev 48

/design/trunk/src/ch_intro.xml
6,6 → 6,11
 
<para>This book describes the design and principles of the HelenOS operating
system from the perspective of its microkernel as well as from the
perspective of its userspace drivers and server tasks.</para>
</chapter>
 
perspective of its userspace drivers and server tasks. Its primary goal is
to present ideas behind each subsystem and highlight things that are
specific to HelenOS. Although this text contains references to source code
(e.g. function names), these are provided only to improve reader's
orientation when reading the code. This book does not attempt to be a
substitute for a reference manual and the reader is strongly encouraged to
look for interface details there.</para>
</chapter>
/design/trunk/src/ch_synchronization.xml
175,9 → 175,9
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 into 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
that will let predefined amount of threads into their 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
292,7 → 292,131
<section>
<title>Condition variables</title>
 
<para>Condvars explanation</para>
<para>Condition variables can be used for waiting until a condition
becomes true. In this respect, they are similar to wait queues. But
contrary to wait queues, condition variables have different semantics
that allows events to be lost when there is no thread waiting for them.
In order to support this, condition variables don't use direct hand-off
and operate in a way similar to the example below. A thread waiting for
the condition becoming true does the following:</para>
 
<para><programlisting language="C"><function>mutex_lock</function>(<varname>mtx</varname>);
while (!<varname>condition</varname>)
<function>condvar_wait_timeout</function>(<varname>cv</varname>, <varname>mtx</varname>);
/* <remark>the condition is true, do something</remark> */
<function>mutex_unlock</function>(<varname>mtx</varname>);</programlisting></para>
 
<para>A thread that causes the condition become true signals this event
like this:</para>
 
<para><programlisting><function>mutex_lock</function>(<varname>mtx</varname>);
<varname>condition</varname> = <constant>true</constant>;
<function>condvar_signal</function>(<varname>cv</varname>); /* <remark>condvar_broadcast(cv);</remark> */
<function>mutex_unlock</function>(<varname>mtx</varname>);</programlisting></para>
 
<para>The wait operation, <emphasis>condvar_wait_timeout</emphasis>,
always puts the calling thread to sleep. The thread then sleeps until
another thread invokes <emphasis>condvar_broadcast</emphasis> on the
same condition variable or until it is woken up by
<emphasis>condvar_signal</emphasis>. The
<emphasis>condvar_signal</emphasis> operation unblocks the first thread
blocking on the condition variable while the
<emphasis>condvar_broadcast</emphasis> operation unblocks all threads
blocking there. If there are no blocking threads, these two operations
have no efect.</para>
 
<para>Note that the threads must synchronize over a dedicated mutex. To
prevent race condition between <emphasis>condvar_wait_timeout</emphasis>
and <emphasis>condvar_signal</emphasis> or
<emphasis>condvar_broadcast</emphasis>, the mutex is passed to
<emphasis>condvar_wait_timeout</emphasis> which then atomically puts the
calling thread asleep and unlocks the mutex. When the thread eventually
wakes up, <emphasis>condvar_wait</emphasis> regains the mutex and
returns.</para>
 
<para>Also note, that there is no conditional operation for condition
variables. Such an operation would make no sence since condition
variables are defined to forget events for which there is no waiting
thread and because <emphasis>condvar_wait</emphasis> must always go to
sleep. The operation with timeout is supported as usually.</para>
 
<para>In HelenOS, condition variables are based on wait queues. As it is
already mentioned above, wait queues remember missed events while
condition variables must not do so. This is reasoned by the fact that
condition variables are designed for scenarios in which an event might
occur very many times without being picked up by any waiting thread. On
the other hand, wait queues would remember any event that had not been
picked up by a call to <emphasis>waitq_sleep_timeout</emphasis>.
Therefore, if wait queues were used directly and without any changes to
implement condition variables, the missed_wakeup counter would hurt
performance of the implementation: the <code>while</code> loop in
<emphasis>condvar_wait_timeout</emphasis> would effectively do busy
waiting until all missed wakeups were discarded.</para>
 
<para>The requirement on the wait operation to atomically put the caller
to sleep and release the mutex poses an interesting problem on
<emphasis>condvar_wait_timeout</emphasis>. More precisely, the thread
should sleep in the condvar's wait queue prior to releasing the mutex,
but it must not hold the mutex when it is sleeping.</para>
 
<para>Problems described in the two previous paragraphs are addressed in
HelenOS by dividing the <emphasis>waitq_sleep_timeout</emphasis>
function into three pieces:</para>
 
<orderedlist>
<listitem>
<para><emphasis>waitq_sleep_prepare</emphasis> prepares the thread
to go to sleep by, among other things, locking the wait
queue;</para>
</listitem>
 
<listitem>
<para><emphasis>waitq_sleep_timeout_unsafe</emphasis> implements the
core blocking logic;</para>
</listitem>
 
<listitem>
<para><emphasis>waitq_sleep_finish</emphasis> performs cleanup after
<emphasis>waitq_sleep_timeout_unsafe</emphasis>; after this call,
the wait queue spinlock is guaranteed to be unlocked by the
caller</para>
</listitem>
</orderedlist>
 
<para>The stock <emphasis>waitq_sleep_timeout</emphasis> is then a mere
wrapper that calls these three functions. It is provided for convenience
in cases where the caller doesn't require such a low level control.
However, the implementation of <emphasis>condvar_wait_timeout</emphasis>
does need this finer-grained control because it has to interleave calls
to these functions by other actions. It carries its operations out in
the following order:</para>
 
<orderedlist>
<listitem>
<para>calls <emphasis>waitq_sleep_prepare</emphasis> in order to
lock the condition variable's wait queue,</para>
</listitem>
 
<listitem>
<para>releases the mutex,</para>
</listitem>
 
<listitem>
<para>clears the counter of missed wakeups,</para>
</listitem>
 
<listitem>
<para>calls <emphasis>waitq_sleep_timeout_unsafe</emphasis>,</para>
</listitem>
 
<listitem>
<para>retakes the mutex,</para>
</listitem>
 
<listitem>
<para>calls <emphasis>waitq_sleep_finish</emphasis>.</para>
</listitem>
</orderedlist>
</section>
</section>
 
/design/trunk/src/ch_arch_overview.xml
4,40 → 4,62
 
<title>Architecture overview</title>
 
<section>
<para>
<mediaobject id="arch1">
<imageobject role="html">
<imagedata fileref="images/arch1.png" format="PNG" />
</imageobject>
<para>The HelenOS operating system is designed as a relatively small
microkernel assisted with a set of userspace drivers and server tasks.
HelenOS is not very radical in what subsystems should or should not be
implemented in the kernel - in some cases, both kernel and userspace drivers
exist. The reason for creating the system as a microkernel is prosaic. Even
though it is initially more difficult to get the same level of functionality
from a microkernel than it is in the case of a simple monolithic kernel, a
microkernel is much easier to maintain once the pieces have been put to work
together. Therefore, the kernel of HelenOS, as well as the essential
userspace libraries thereof can be maintained by only a few developers who
understand them completely. In addition, a microkernel based operating
system reaches completion sooner than monolithic kernels as the system can
be used even without some traditional subsystems (e.g. block devices,
filesystems and networking).</para>
 
<imageobject role="fop">
<imagedata fileref="images.vector/arch1.svg" format="SVG" />
</imageobject>
</mediaobject>
</para>
</section>
<para><mediaobject id="arch1" xreflabel="">
<imageobject role="html">
<imagedata fileref="images/arch1.png" format="PNG" />
</imageobject>
 
<imageobject role="fop">
<imagedata fileref="images.vector/arch1.svg" format="SVG" />
</imageobject>
 
<caption>HelenOS architecture overview</caption>
</mediaobject></para>
 
<para>HelenOS is comprised of the kernel and userspace server tasks. The
kernel provides scheduling, memory management and IPC. It also contains
essential device drivers that control the system clock and other devices
necessary to guarantee a safe environment. Userspace communicates with the
kernel through a small set of syscalls. The userspace layer consists of
tasks with different roles, capabilities and privileges. Some of the tasks
serve as device drivers, naming servers, managers of various kinds and some
are just ordinary user programs. All of them communicate with other threads
via kernel-provided IPC.</para>
 
<section>
<para>The HelenOS operating system is designed as a relatively small
microkernel assisted with a set of userspace drivers and server tasks.
HelenOS is not very radical in what subsystems should or should not be
implemented in the kernel - in some cases, both kernel and userspace
drivers exist. The reason for creating the system as a microkernel is
prosaic. Even though it is initially more difficult to get the same level
of functionality from a microkernel than it is in the case of a simple
monolithic kernel, a microkernel is much easier to maintain once the
pieces have been put to work together. Therefore, the kernel of HelenOS,
as well as the essential userspace libraries thereof can be maintained by
only a few developers who understand them completely. In addition, a
microkernel based operating system reaches completion sooner than
monolithic kernels as the system can be used even without some traditional
subsystems (e.g. block devices, filesystems and networking).</para>
<title>Scheduling</title>
 
<para>HelenOS is comprised of the kernel and userspace server tasks. The
kernel provides scheduling, memory management and IPC. It also contains
essential device drivers that control the system clock and other devices
necessary to guarantee a safe environment. Userspace communicates with the
kernel through </para>
<para>Kernel's unit of execution flow is a thread. A thread is an entity
that executes code and has a stack that takes up some space in memory. The
relation between kernel and userspace threads is 1:1:n, meaning that there
can be several pseudo threads running within one userspace thread that
maps to one kernel thread. Threads are grouped into tasks by functionality
they provide (i.e. several threads implement functionality of one task).
Tasks serve as containers of threads, they provide linkage to address
space and are communication endpoints for IPC.</para>
 
<para>The scheduler deploys several run queues on each processor. A thread
ready for execution is put into one of the run queues, depending on its
priority and its current processor, from where it is eventually picked up
by the scheduler. Special purpose kernel threads strive to keep processors
balanced by thread migration. Threads are scheduled by the round robing
scheduling policy with respect to multiple priority run queues.</para>
 
<para></para>
</section>
</chapter>