Subversion Repositories HelenOS-doc

  </section>

  <section>

    <title>Scheduler</title>

    <section>

      <title>Run queues</title>

      <para>There is an array of several run queues on each processor. The

      current version of HelenOS uses 16 run queues implemented by 16 doubly

      linked lists. Each of the run queues is associated with thread priority.

      The lower the run queue index in the array is, the higher is the

      priority of threads linked in that run queue and the shorter is the time

      in which those threads will execute. When kernel code wants to access

      the run queue, it must first acquire its lock.</para>

    </section>

    <section>

      <title>Scheduler operation</title>

      <para>The scheduler is invoked either explicitly when a thread calls the

      <code>scheduler</code> function (e.g. goes to sleep or merely wants to

      relinquish the processor for a while) or implicitly on a periodic basis

      when the generic clock interrupt preempts the current thread. After its

      invocation, the scheduler saves the synchronous register context of the

      current thread and switches to its private stack. Afterwards, a new

      thread is selected according to the scheduling policy. If there is no

      suitable thread, the processor is idle and no thread executes on it.

      Note that the act of switching to the private scheduler stack is

      essential. If the processor kept running using the stack of the

      preempted thread it could damage it because the old thread can be

      migrated to another processor and scheduled there. In the worst case

      scenario, two execution flows would be using the same stack. </para>

      <para>The scheduling policy is implemented in function

      <code>find_best_thread</code>. This function walks the processor run

      queues from lower towards higher indices and looks for a thread. If the

      visited run queue is empty, it simply searches the next run queue. If it

      is known in advance that there are no ready threads waiting for

      execution, <code>find_best_thread</code> interruptibly halts the

      processor or busy waits until some threads arrive. This process repeats

      until <code>find_best_thread</code> succeeds.</para>

      <para>After the best thread is chosen, the scheduler switches to the

      thread's task and memory management context. Finally, the saved

      synchronous register context is restored and the thread runs. Each

      scheduled thread is given a time slice depending on its priority (i.e.

      run queue). The higher priority, the shorter timeslice. To summarize,

      this policy schedules threads with high priorities more frequently but

      gives them smaller time slices. On the other hand, lower priority

      threads are scheduled less frequently, but run for longer periods of

      time.</para>

      <para>When a thread uses its entire time slice, it is preempted and put

      back into the run queue that immediately follows the previous run queue

      from which the thread ran. Threads that are woken up from a sleep are

      put into the biggest priority run queue. Low priority threads are

      therefore those that don't go to sleep so often and just occupy the

      processor.</para>

      <para>In order to avoid complete starvation of the low priority threads,

      from time to time, the scheduler will provide them with a bonus of one

      point priority increase. In other words, the scheduler will now and then

      move the entire run queues one level up.</para>

    </section>

    <section>

      <title>Processor load balancing</title>

      <para>Normally, for the sake of cache locality, threads are scheduled on

      one of the processors and don't leave it. Nevertheless, a situation in

      which one processor is heavily overloaded while others sit idle can

      occur. HelenOS deploys special kernel threads to help to mitigate this

      problem. Each processor is associated with one load balancing thread

      called <code>kcpulb</code> that wakes up regularily to see whether its

      processor is underbalanced or not. If yes, the thread attempts to

      migrate threads from other overloaded processors to its own processor's

      run queues. When the job is done or there is no need for load balancing,

      the thread goes to sleep.</para>

      <para>The balancing threads operate very gently and try to migrate low

      priority threads first; one <code>kcpulb</code> never takes from one

      processor twice in a row. The load balancing threads as well as threads

      that were just stolen cannot be migrated. The <code>kcpulb</code>

      threads are wired to their processors and cannot be migrated whatsoever.

      The ordinary threads are protected only until they are

    </section>