SCHED_DEADLINE: Sporadic task model deadline scheduling
Since version 3.14, Linux provides a deadline scheduling policy
(SCHED_DEADLINE). This policy is currently implemented using
GEDF (Global Earliest Deadline First) in conjunction with CBS
(Constant Bandwidth Server). To set and fetch this policy and
associated attributes, one must use the Linux-specific
sched_setattr(2) and sched_getattr(2) system calls.
A sporadic task is one that has a sequence of jobs, where each
job is activated at most once per period. Each job also has a
relative deadline, before which it should finish execution, and a
computation time, which is the CPU time necessary for executing
the job. The moment when a task wakes up because a new job has
to be executed is called the arrival time (also referred to as
the request time or release time). The start time is the time at
which a task starts its execution. The absolute deadline is thus
obtained by adding the relative deadline to the arrival time.
The following diagram clarifies these terms:
arrival/wakeup absolute deadline
| start time |
| | |
v v v
-----x--------xooooooooooooooooo--------x--------x---
|<- comp. time ->|
|<------- relative deadline ------>|
|<-------------- period ------------------->|
When setting a SCHED_DEADLINE policy for a thread using
sched_setattr(2), one can specify three parameters: Runtime,
Deadline, and Period. These parameters do not necessarily
correspond to the aforementioned terms: usual practice is to set
Runtime to something bigger than the average computation time (or
worst-case execution time for hard real-time tasks), Deadline to
the relative deadline, and Period to the period of the task.
Thus, for SCHED_DEADLINE scheduling, we have:
arrival/wakeup absolute deadline
| start time |
| | |
v v v
-----x--------xooooooooooooooooo--------x--------x---
|<-- Runtime ------->|
|<----------- Deadline ----------->|
|<-------------- Period ------------------->|
The three deadline-scheduling parameters correspond to the
sched_runtime, sched_deadline, and sched_period fields of the
sched_attr structure; see sched_setattr(2). These fields express
values in nanoseconds. If sched_period is specified as 0, then
it is made the same as sched_deadline.
The kernel requires that:
sched_runtime <= sched_deadline <= sched_period
In addition, under the current implementation, all of the
parameter values must be at least 1024 (i.e., just over one
microsecond, which is the resolution of the implementation), and
less than 2^63. If any of these checks fails, sched_setattr(2)
fails with the error EINVAL.
The CBS guarantees non-interference between tasks, by throttling
threads that attempt to over-run their specified Runtime.
To ensure deadline scheduling guarantees, the kernel must prevent
situations where the set of SCHED_DEADLINE threads is not
feasible (schedulable) within the given constraints. The kernel
thus performs an admittance test when setting or changing
SCHED_DEADLINE policy and attributes. This admission test
calculates whether the change is feasible; if it is not,
sched_setattr(2) fails with the error EBUSY.
For example, it is required (but not necessarily sufficient) for
the total utilization to be less than or equal to the total
number of CPUs available, where, since each thread can maximally
run for Runtime per Period, that thread's utilization is its
Runtime divided by its Period.
In order to fulfill the guarantees that are made when a thread is
admitted to the SCHED_DEADLINE policy, SCHED_DEADLINE threads are
the highest priority (user controllable) threads in the system;
if any SCHED_DEADLINE thread is runnable, it will preempt any
thread scheduled under one of the other policies.
A call to fork(2) by a thread scheduled under the SCHED_DEADLINE
policy fails with the error EAGAIN, unless the thread has its
reset-on-fork flag set (see below).
A SCHED_DEADLINE thread that calls sched_yield(2) will yield the
current job and wait for a new period to begin.