1,44 → 1,140 |
<?xml version="1.0" encoding="UTF-8"?> |
<chapter id="time"> |
<?dbhtml filename="time.html"?> |
|
<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 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 |
timeouting versions of synchronization primitives. |
</para> |
<title>Time management</title> |
|
<section> |
<para>Time is one of the dimensions in which kernel, as well as the whole |
system, operates. 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 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> |
|
<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> |
|
<para>The rest of this section will, for the sake of clarity, focus on the |
two-register scheme. The decrementer scheme is very similar.</para> |
|
<para>The kernel must reinitialize the counter registers after each clock |
interrupt in order to schedule next interrupt. However this step is tricky |
and must be done with caution. Imagine that the clock interrupt is masked |
either because the kernel is servicing another interrupt or because the |
processor locally disabled interrupts for a while. If the clock interrupt |
occurs during this period, it will be pending until interrupts are enabled |
again. In theory, that could happen arbitrary counter register ticks |
later. Which is worse, the ideal time period between two non-delayed clock |
interrupts can also elapse arbitrary number of times before the delayed |
interrupt gets serviced. The architecture-specific part of the clock |
interrupt driver must avoid time drifts caused by this by taking proactive |
counter-measures.</para> |
|
<para>Let us assume that the kernel wants each clock interrupt be |
generated every <constant>TICKCONST</constant> ticks. This value |
represents the ideal number of ticks between two non-delayed clock |
interrupts and has some known relation to real time. On each clock |
interrupt, the kernel computes and writes down the expected value of the |
counter register as it hopes to read it on the next clock interrupt. When |
that interrupt comes, the kernel reads the counter register again and |
compares it with the written down value. If the difference is smaller than |
or equal to <constant>TICKCONST</constant>, then the time drift is none or |
small and the next interrupt is scheduled earlier with a penalty of so |
many ticks as is the value of the difference. However, if the difference |
is bigger, then at least one clock signal was missed. In that case, the |
missed clock signal is remembered in the special counter. If there are |
more missed signals, each of them is recorded there. The next interrupt is |
scheduled with respect to the difference similarily to the former case. |
This time, the penalty is taken modulo <constant>TICKCONST</constant>. The |
effect of missed clock signals is remedied in the generic clock interrupt |
handler.</para> |
</section> |
|
<section> |
<title>Timeouts</title> |
|
<para>Kernel subsystems can register a callback function to be executed |
with a specified delay. Such a registration is represented by a kernel |
structure called <classname>timeout</classname>. Timeouts are registered |
via <code>timeout_register</code> function. This function takes a pointer |
to a timeout structure, a callback function, a parameter of the callback |
function and a delay in microseconds as parameters. After the structure is |
initialized with all these values, it is sorted into the processor's list |
of active timeouts.Timeouts are sorted in this list according to the |
number of clock interrupts remaining to their expiration and relative to |
each other. </para> |
|
<para>Timeouts can be unregistered via <code>timeout_unregister</code>. |
This function can, as opposed to <code>timeout_register</code>, fail when |
it is too late to remove the timeout from the list of active |
timeouts.</para> |
|
<para>Timeouts are nearing their expiration in the list of active timeouts |
which exists on every processor in the system. The expiration counters are |
decremented on each clock interrupt by the generic clock interrupt |
handler. Due to the relative ordering of timeouts in the list, it is |
sufficient to decrement expiration counter only of the first timeout in |
the list. Timeouts with expiration counter equal to zero are removed from |
the list and their callback function is called with respective |
parameter.</para> |
</section> |
|
<section> |
<title>Generic clock interrupt handler</title> |
|
<para>On each clock interrupt, the architecture specific part of the clock |
interrupt handler makes a call to the generic clock interrupt handler |
implemented by the <code>clock</code> function. The generic handler takes |
care of several mission critical goals:</para> |
|
<itemizedlist> |
<listitem> |
<para>expiration of timeouts,</para> |
</listitem> |
|
<listitem> |
<para>updating time of the day counters for userspace and</para> |
</listitem> |
|
<listitem> |
<para>preemption of threads.</para> |
</listitem> |
</itemizedlist> |
|
<para>The first two goals are performed exactly one more times than is the |
number of missed clock signals (i.e. at least once and possibly more |
times, depending on the missed clock signals counter). The remaining |
timeslice of the running thread is decremented also with respect to this |
counter. By considering its value, the kernel performs actions that would |
otherwise be lost due to an occasional excessive time drift described in |
previous paragraphs.</para> |
</section> |
</chapter> |