Subversion Repositories HelenOS-doc

Compare Revisions

Ignore whitespace Rev 51 → Rev 52

/design/trunk/src/ch_ds.xml
0,0 → 1,77
<?xml version="1.0" encoding="UTF-8"?>
 
<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>
 
<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, 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 with several 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>B+trees</title>
<para>
</para>
</section>
 
</chapter>
/design/trunk/src/index.xml
3,6 → 3,8
"http://www.oasis-open.org/docbook/xml/4.4/docbookx.dtd" [
<!ENTITY chintro SYSTEM "ch_intro.xml">
<!ENTITY charcho SYSTEM "ch_arch_overview.xml">
<!ENTITY chds SYSTEM "ch_ds.xml">
<!ENTITY chtime SYSTEM "ch_time.xml">
<!ENTITY chsched SYSTEM "ch_scheduling.xml">
<!ENTITY chsynch SYSTEM "ch_synchronization.xml">
<!ENTITY chmemmg SYSTEM "ch_memory_management.xml">
21,7 → 23,13
<!-- Arch overview -->
&charcho;
 
<!-- Data structures -->
&chds;
<!-- Time management -->
&chtime;
<!-- Scheduling -->
&chsched;
/design/trunk/src/ch_time.xml
0,0 → 1,15
<?xml version="1.0" encoding="UTF-8"?>
 
<chapter id="time"><?dbhtml filename="time.html"?>
<title>Time management</title>
<para>
Time is one of the dimensions in which kernel, as well as the whole system, operates.
It is of special importance to other kernel subsytems. Knowledge of time makes it possible
for the scheduler to preemptively plan threads for execution. Different parts of the kernel
can request execution of their callback function with some specified delay. A good example
of such kernel code is the synchronization subsystem which uses this functionality to implement
timeouting versions of synchronization primitives.
</para>
 
</chapter>
/design/trunk/src/ch_arch_overview.xml
109,4 → 109,6
tasks. Calls can be synchronous or asynchronous and can be forwarded from
one task to another.</para>
</section>
 
 
</chapter>
/design/trunk/src/ch_scheduling.xml
2,10 → 2,10
 
<chapter id="scheduling"><?dbhtml filename="scheduling.html"?>
<title>Scheduling</title>
<section>
<title>Basic terms</title>
<para>Explain Task, Thread etc</para>
</section>
<para>
One of the key tasks of the operating system is to create and support impression that several activities are running contemporarily in the system. This is true for both uniprocessor as well as multiprocessor systems. In the case of multiprocessor systems, the activities are trully running in parallel
</para>
 
<section>
<title>Context switching</title>
14,11 → 14,6
</section>
 
<section>
<title>Kernel clock</title>
<para>timer interrupt handling, slices, timeouts, delays</para>
</section>
 
<section>
<title>Scheduler</title>
<para>How scheduler designed and how it works.</para>
</section>