Scott Craig and Justin Tanner

Scheduler

The scheduler is the part of the kernel that decides what task to run next. The kernel dispatches tasks based on the current running task and other tasks waiting on the kernel.

Dispatching

After some initialization, the kernel enters a loop:

  1. Select and dispatch a process to run
  2. Exit the kernel. (The loop is left and re-entered here.)
  3. Handle the request from the process that was running.
  4. Goto step one

So effectively, every time the kernel code is entered at its single point of entry, the request of the currently running task is responded to, and another task--or maybe the same one depending on the nature of the request and the state of the other tasks--is selected to run next.

The structure of the kernel function to handle request is simple; it is mostly one long switch statement that selects the correct action depending on the type of request. Depending on the request, the current task may be suspended from running, and placed in some queue or terminated. Other tasks may also be moved from one queue to another. A transition diagram for how the states of tasks change given a particular request is shown below.

State Diagram for a Task

Task state diagram

For example, if the current task requests to wait on an event, then it will be suspended and placed in a waiting queue for the event. In another example, if the current task signals on an event, it may or may not be suspended, depending on the level of the other tasks waiting on that event.

After the request is handled, and the queues are adjusted, another function chooses the next task to dispatch. For efficiency, the function handling the request looks ahead to see if the current task needs to be suspended. So if the current task is already running, then it is left running. Otherwise, a new task is selected based on priority--SYSTEM, PERIODIC, RR--and on the scheduling policy of the various levels: first-come-first-served for SYSTEM tasks, and round-robin for RR tasks. If the PERIODIC task for the current time slot has not yet run, and there are no SYSTEM tasks, then it will be chosen.