Subversion Repositories HelenOS-doc

<?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 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>

    <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>