Subversion Repositories HelenOS-doc

<?xml version="1.0" encoding="UTF-8"?>

<chapter id="scheduling">

  <?dbhtml filename="scheduling.html"?>

  <title>Scheduling</title>

  <para>One of the key aims of the operating system is to create and support

  the impression that several activities are executing contemporarily. This is

  true for both uniprocessor as well as multiprocessor systems. In the case of

  multiprocessor systems, the activities are trully happening in parallel. The

  scheduler helps to materialize this impression by planning threads on as

  many processors as possible and, where this means reaches its limits, by

  quickly switching among threads executing on a single processor.</para>

  <section>

    <title>Contexts</title>

    <para>The term context refers to the set of processor resources that

    define the current state of the computation or the environment and the

    kernel understands it in several more or less narrow sences:</para>

    <itemizedlist>

      <listitem>

        <para>synchronous register context,</para>

      </listitem>

      <listitem>

        <para>asynchronous register context,</para>

      </listitem>

      <listitem>

        <para>FPU context and</para>

      </listitem>

      <listitem>

        <para>memory management context.</para>

      </listitem>

    </itemizedlist>

    <para>The most narrow sence refers to the the synchronous register

    context. It includes all the preserved registers as defined by the

    architecture. To highlight some, the program counter and stack pointer

    take part in the synchronous register context. These are the registers

    that must be preserved across a procedure call and during synchronous

    context switches.</para>

    <para>The next type of the context understood by the kernel is the

    asynchronous register context. On an interrupt, the interrupted execution

    flow's state must be guaranteed to be eventually completely restored.

    Therefore the interrupt context includes, among other things, the scratch

    registers as defined by the architecture. As a special optimization and if

    certain conditions are met, it need not include the architecture's

    preserved registers. The condition mentioned in the previous sentence is

    that the low-level assembly language interrupt routines don't modify the

    preserved registers. The handlers usually call a higher-level C routine.

    The preserved registers are then saved on the stack by the compiler

    generated code of the higher-level function. In HelenOS, several

    architectures can be compiled with this optimization.</para>

    <para>Although the kernel does not do any floating point

    arithmetics<footnote>

        <para>Some architectures (e.g. ia64) inevitably use a fixed set of

        floating point registers to carry out its normal operations.</para>

      </footnote>, it must protect FPU context of userspace threads against

    destruction by other threads. Moreover, only a fraction of userspace

    programs use the floating point unit. HelenOS contains a generic framework

    for switching FPU context only when the switch is forced.</para>

    <para>The last member of the context family is the memory management

    context. It includes memory management registers that identify address

    spaces on hardware level (i.e. ASIDs and page tables pointers).</para>

    <section>

      <title>Synchronous context switches</title>

      <para>The scheduler, but also other pieces of the kernel, make heavy use

      of synchronous context switches, because it is a natural vehicle not

      only for changes in control flow, but also for switching between two

      kernel stacks. Two functions figure in a synchronous context switch

      implementation: <code>context_save</code> and

      <code>context_restore</code>. Note that these two functions break the

      natural perception of the linear C code execution flow starting at

      function's entry point and ending on one of the function's exit

      points.</para>

      <para>When the <code>context_save</code> function is called, the

      synchronous context is saved in a memory structure passed to it. After

      executing <code>context_save</code>, the caller is returned 1 as a

      return value. The execution of instructions continues as normally until

      <code>context_restore</code> is called. For the caller, it seems like

      the call never returns<footnote>

          <para>Which might be a source of problems with variable liveliness

          after <code>context_restore</code>.</para>

        </footnote>. Nevertheless, a synchronous register context, which is

      saved in a memory structure passed to <code>context_restore,</code> is

      restored, thus transfering the control flow to the place of occurrence

      of the corresponding call to <code>context_save</code>. From the

      perspective of the caller of the corresponding

      <code>context_save</code>, it looks as though a return from

      <code>context_save</code>. However, this time a return value of 0 is

      returned.</para>

    </section>

  </section>

  <section>

    <title>Threads</title>

    <para>A thread is the basic executable entity with some code and stack.

    While the code, implemented by a C language function, can be shared by

    several threads, the stack is always private to each instance of the

    thread. Each thread belongs to exactly one task through which it shares

    address space with its sibling threads. Threads that execute purely in the

    kernel don't have any userspace memory allocated. However, when a thread

    has ambitions to run in userspace, it must be allocated a userspace stack.

    The distinction between the purely kernel threads and threads running also

    in userspace is made by refering to the former group as to kernel threads

    and to the latter group as to userspace threads. Both kernel and userspace

    threads are visible to the scheduler and can become a subject of kernel

    preemption and thread migration during times when preemption is

    possible.</para>

    <para>HelenOS userspace layer knows even smaller units of execution. Each

    userspace thread can make use of an arbitrary number of pseudo threads.

    These pseudo threads have their own synchronous register context,

    userspace code and stack. They live their own life within the userspace

    thread and the scheduler does not have any idea about them because they

    are completely implemented by the userspace library. This implies several

    things:</para>

    <itemizedlist>

      <listitem>

        <para>pseudothreads schedule themselves cooperatively within the time

        slice given to their userspace thread,</para>

      </listitem>

      <listitem>

        <para>pseudothreads share FPU context of their containing thread

        and</para>

      </listitem>

      <listitem>

        <para>all pseudothreads of one userspace thread block when one of them

        goes to sleep.</para>

      </listitem>

    </itemizedlist>

    <para></para>

  </section>

</chapter>