| 143,7 → 143,93 |
|---|
| goes to sleep.</para> |
| </listitem> |
| </itemizedlist> |
| </section> |
| |
| <para></para> |
| <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 |
| rescheduled.</para> |
| </section> |
| </section> |
| </chapter> |