Subversion Repositories HelenOS-doc

Compare Revisions

Ignore whitespace Rev 52 → Rev 53

/design/trunk/src/ch_ds.xml
60,7 → 60,7
<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
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.
70,7 → 70,12
<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>
 
/design/trunk/src/ch_time.xml
5,7 → 5,7
<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
It is of special importance to many 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
12,4 → 12,33
timeouting versions of synchronization primitives.
</para>
 
<section>
<title>System clock</title>
<para>
Every hardware architecture supported by HelenOS must support some kind of a device that can be
programmed to yield periodic time signals (i.e. clock interrupts). Some architectures have
external clock that is merely programmed by the kernel to interrupt the processor multiple
times in a second. This is the case of ia32 and amd64 architectures<footnote><para>When
running in uniprocessor mode.</para></footnote>, which use i8254 or a compatible chip to
achieve the goal.
</para>
<para>
Other architectures' processors typically contain two registers. The first
register is usually called a compare or a match register and can be set to an arbitrary value
by the operating system. The contents of the compare register then stays unaltered until it is
written by the kernel again. The second register, often called a counter register, can be also
written by the kernel, but the processor automatically increments it after every executed
instruction or in some fixed relation to processor speed. The point is that a clock interrupt is
generated whenever the values of the counter and the compare registers match. Sometimes, the scheme of
two registers is modified so that only one register is needed. Such a register, called a decrementer,
then counts towards zero and an interrupt is generated when zero is reached.
</para>
<para>
In any case, the initial value of the decrementer or the initial difference between the counter and
the compare registers, respectively, must be set accordingly to a known relation between the real time
and the speed of the decrementer or the counter register, respectively.
</para>
</section>
 
</chapter>