Subversion Repositories HelenOS-doc

Compare Revisions

Ignore whitespace Rev 58 → Rev 59

/design/trunk/src/ch_ds.xml
1,82 → 1,86
<?xml version="1.0" encoding="UTF-8"?>
<chapter id="ds">
<?dbhtml filename="ds.html"?>
 
<chapter id="ds"><?dbhtml filename="ds.html"?>
<title>Data structures</title>
<para>
There is lots of data that either flows through various HelenOS subsystems
or is stored directly by them. Each subsystem uses its own data structures
to represent the data. These data structures need to be kept
somewhere. In order to work efficiently, HelenOS, and especially its
kernel, deploys several house keeping data types that are designed
to faciliate managing other data structures. They serve like generic
containers.
</para>
<section>
<title>Lists</title>
<para>
HelenOS uses circular doubly linked lists to bind related data
together. Lists are composed of an independent head and links that are always
part of the object that is to be put into the list. Adding items to a list
thus doesn't require any further memory allocations. Head and each link then
contains forward and backward pointer. An empty list is composed of a sole
head whose both pointers reference the head itself. The expense of two times
bigger memory consumption as compared to memory consumption of singly linked
lists is justified by constant insertion and removal times at random positions
within the list.
</para>
<para>
Lists are frequently used to implement FIFO behaviour (e.g. scheduler run queues
or synchronization wait queues). Contrary to the FIFO type, which is also supported
by HelenOS, they don't take up any unused space and are more general. On the
other hand, they are slower than in-array FIFOs and can be hardly used to implement
buffers.
</para>
</section>
<title>Data structures</title>
 
<section>
<title>FIFO queues</title>
<para>
FIFO queues are implemented as either statically or dynamically allocated
arrays<footnote><para>Depending on the array size.</para></footnote> of some generic type
with two indices. The first index points to the head of the FIFO queue and the other
points to the tail thereof. There can be as many items in the FIFO as is the number
of elements in the array and no more. The indices are taken modulo size of the queue
because as a consequence of insertions and deletions, the tail can have numericaly
lower index than the head.
</para>
<para>
FIFO queues are used, for example, in ASID management code to store inactive ASIDs or
in userspace keyboard driver to buffer read characters.
</para>
</section>
<para>There is lots of data that either flows through various HelenOS
subsystems or is stored directly by them. Each subsystem uses its own data
structures to represent the data. These data structures need to be kept
somewhere. In order to work efficiently, HelenOS, and especially its kernel,
deploys several house keeping data types that are designed to faciliate
managing other data structures. Most of them serve like generic
containers.</para>
 
<section>
<title>Hash tables</title>
<para>
The kernel, as well as userspace, makes use of the hash table implementation with
separate chaining. The implementation is very generic in that it forces the user
to supply methods for computing the hash index, comparing items against a set of keys
and the item removal callback function. Besides these virtual operations,
the hash table is composed of a dynamically allocated array of list heads that
represent each chain, number of chains and the maximal number of keys.
</para>
</section>
<section>
<title>Lists</title>
 
<section>
<title>B+trees</title>
<para>
HelenOS makes use of a variant of B-tree called B+tree. B+trees, in HelenOS implementation,
are 3-4-5 balanced trees. They are characteristic by the fact that values are kept only in
the leaf-level nodes and that these nodes are linked together in a list. This data structure
has logaritmic search, insertion and deletion times and, thanks to the leaf-level list,
provides fantastic means of walking the nodes containing data. Moreover, B+trees can be used
for easy storing, resizing and merging of disjunctive intervals.
</para>
</section>
<para>HelenOS uses doubly-circularly-linked lists to bind related data
together. Lists are composed of an independent sentinel node called head
and links that are always part of the object that is to be put into the
list. Adding items to a list thus doesn't require any further memory
allocations. Head and each link then contains forward and backward
pointer. An empty list is composed of a sole head whose both pointers
reference the head itself. The expense of two times bigger memory
consumption as compared to memory consumption of singly linked lists is
justified by constant insertion and removal times at random positions
within the list.</para>
 
</chapter>
<para>Lists are frequently used to implement FIFO behaviour (e.g.
scheduler run queues or synchronization wait queues). Contrary to the FIFO
type, which is also supported by HelenOS, they don't take up any unused
space and are more general. On the other hand, they are slower than
in-array FIFOs and can be hardly used to implement buffers.</para>
</section>
 
<section>
<title>FIFO queues</title>
 
<para>FIFO queues are implemented as either statically or dynamically
allocated arrays<footnote>
<para>Depending on the array size.</para>
</footnote> of some generic type with two indices. The first index
points to the head of the FIFO queue and the other points to the tail
thereof. There can be as many items in the FIFO as is the number of
elements in the array and no more. The indices are taken modulo size of
the queue because as a consequence of insertions and deletions, the tail
can have numericaly lower index than the head.</para>
 
<para>FIFO queues are used, for example, in ASID management code to store
inactive ASIDs or in userspace keyboard driver to buffer read
characters.</para>
</section>
 
<section>
<title>Hash tables</title>
 
<para>The kernel, as well as userspace, provides hash table data type
which uses separate chaining. The hash table type is very generic in that
it forces the user to supply methods for computing the hash index,
comparing items against a set of keys and the item removal callback
function. Besides these virtual operations, the hash table is composed of
a dynamically allocated array of list heads that represent each chain,
number of chains and the maximal number of keys.</para>
</section>
 
<section>
<title>Bitmaps</title>
 
<para>Several bitmap operations such as clearing or setting consecutive
bit sequences as well as copying portions of one bitmap into another one
are supported.</para>
</section>
 
<section>
<title>B+trees</title>
 
<para>HelenOS makes use of a variant of B-tree called B+tree. B+trees, in
HelenOS implementation, are 3-4-5 balanced trees. They are characteristic
by the fact that values are kept only in the leaf-level nodes and that
these nodes are linked together in a list. This data structure has
logaritmic search, insertion and deletion times and, thanks to the
leaf-level list, provides fantastic means of walking the nodes containing
data. Moreover, B+trees can be used for easy storing, resizing and merging
of disjunctive intervals.</para>
</section>
</chapter>
/design/trunk/src/ch_scheduling.xml
143,7 → 143,93
goes to sleep.</para>
</listitem>
</itemizedlist>
</section>
 
<para></para>
<section>
<title>Scheduler</title>
 
<section>
<title>Run queues</title>
 
<para>There is an array of several run queues on each processor. The
current version of HelenOS uses 16 run queues implemented by 16 doubly
linked lists. Each of the run queues is associated with thread priority.
The lower the run queue index in the array is, the higher is the
priority of threads linked in that run queue and the shorter is the time
in which those threads will execute. When kernel code wants to access
the run queue, it must first acquire its lock.</para>
</section>
 
<section>
<title>Scheduler operation</title>
 
<para>The scheduler is invoked either explicitly when a thread calls the
<code>scheduler</code> function (e.g. goes to sleep or merely wants to
relinquish the processor for a while) or implicitly on a periodic basis
when the generic clock interrupt preempts the current thread. After its
invocation, the scheduler saves the synchronous register context of the
current thread and switches to its private stack. Afterwards, a new
thread is selected according to the scheduling policy. If there is no
suitable thread, the processor is idle and no thread executes on it.
Note that the act of switching to the private scheduler stack is
essential. If the processor kept running using the stack of the
preempted thread it could damage it because the old thread can be
migrated to another processor and scheduled there. In the worst case
scenario, two execution flows would be using the same stack. </para>
 
<para>The scheduling policy is implemented in function
<code>find_best_thread</code>. This function walks the processor run
queues from lower towards higher indices and looks for a thread. If the
visited run queue is empty, it simply searches the next run queue. If it
is known in advance that there are no ready threads waiting for
execution, <code>find_best_thread</code> interruptibly halts the
processor or busy waits until some threads arrive. This process repeats
until <code>find_best_thread</code> succeeds.</para>
 
<para>After the best thread is chosen, the scheduler switches to the
thread's task and memory management context. Finally, the saved
synchronous register context is restored and the thread runs. Each
scheduled thread is given a time slice depending on its priority (i.e.
run queue). The higher priority, the shorter timeslice. To summarize,
this policy schedules threads with high priorities more frequently but
gives them smaller time slices. On the other hand, lower priority
threads are scheduled less frequently, but run for longer periods of
time.</para>
 
<para>When a thread uses its entire time slice, it is preempted and put
back into the run queue that immediately follows the previous run queue
from which the thread ran. Threads that are woken up from a sleep are
put into the biggest priority run queue. Low priority threads are
therefore those that don't go to sleep so often and just occupy the
processor.</para>
 
<para>In order to avoid complete starvation of the low priority threads,
from time to time, the scheduler will provide them with a bonus of one
point priority increase. In other words, the scheduler will now and then
move the entire run queues one level up.</para>
</section>
 
<section>
<title>Processor load balancing</title>
 
<para>Normally, for the sake of cache locality, threads are scheduled on
one of the processors and don't leave it. Nevertheless, a situation in
which one processor is heavily overloaded while others sit idle can
occur. HelenOS deploys special kernel threads to help to mitigate this
problem. Each processor is associated with one load balancing thread
called <code>kcpulb</code> that wakes up regularily to see whether its
processor is underbalanced or not. If yes, the thread attempts to
migrate threads from other overloaded processors to its own processor's
run queues. When the job is done or there is no need for load balancing,
the thread goes to sleep.</para>
 
<para>The balancing threads operate very gently and try to migrate low
priority threads first; one <code>kcpulb</code> never takes from one
processor twice in a row. The load balancing threads as well as threads
that were just stolen cannot be migrated. The <code>kcpulb</code>
threads are wired to their processors and cannot be migrated whatsoever.
The ordinary threads are protected only until they are
rescheduled.</para>
</section>
</section>
</chapter>