Scheduling¶
Introduction¶
The scheduler is the component responsible for determining which task should be executing in a given moment in a CPU, and is also responsible for allocating tasks to CPUs, taking into account their affinity.
The scheduler has a core component, which provides an API that the kernel code can use to enqueue and dequeue tasks from execution, to yield the CPU for another task, and is also responsible for the logic of selecting the next task that must be executed.
The specific way tasks are scheduled for execution and have the concept of task priorities assigned to them is provided by the scheduler implementations (or disciplines), which, at the time of writing, three are present in the kernel, and are ordered in the following way from highest to lowest priority:
RMS (Rate monotonic scheduling)
POSIX Real Time - FIFO (First in-first out) scheduler
POSIX Real Time - RR (Round-robin) scheduler
RMS (Rate monotonic scheduling)¶
Rate monotonic scheduling is a periodic scheduler, mostly found in hard real-time systems.
Under this scheduler, a task tau_i has two properties: a period (P_i), and a computation time (C_i). Such task is eligible for execution at each period, and the scheduler must guarantee it will receive its required computation time in the time from the start of the period to its end.
The priority of a task is determined by its period. The task with the highest priority is the one with the smallest period. It will be executed, until it exhausts its computation time, or another task with a highest priority is enqueued, either because it has been unblocked or because its period has started. If the computation time has been exhausted, it will be replenished in the next period, and if the task has been interrupted because it has been preempted by a higher priority task, it will use its remaining execution time.
For simplicity of implementation, only periods that are powers of two are allowed. This makes the data structures easier to implement, and the schedulability test is equivalent to EDF (Earliest Deadline First): a set of tasks will be schedulable under this algorithm in a CPU if and only if the sum of their loads (C_i / P_i) is <= 1.
A task yielding or blocking gives up its execution time. TODO: explore priority inheritance algorithms,
For an outline of other schedulability tests for RMS and the proof of the previous statement, as well for the specific details of the implementation in the kernel, see kernel/src/sched/rms.c.
POSIX Real Time - FIFO (First in-first out) scheduler¶
Tasks using this scheduler have a single parameter: priority.
The task with the highest priority is the one being executed at a given moment, until it blocks, yields, or a task with a higher priority is enqueued. In the first two cases, the task is enqueued to the tail of its priority list, while in the latter, it is kept at the head.
The implementation can be found at kernel/src/sched/posix_rt.c.
POSIX Real Time - RR (Round-robin) scheduler¶
Tasks using this scheduler have a single parameter: priority.
The task with the highest priority is the one being executed at a given moment, until it blocks, yields, its exhaust it timeslice which depends on the priority, or a task with a higher priority is enqueued. In the first three cases, the task is enqueued to the tail of its priority list, while in the latter, it is kept at the head.
The implementation can be found at kernel/src/sched/posix_rt_c.