Since Linux 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) 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_.
Now there is a failing of that system, some task will be scheduled with the proper deadline parameters: _Runtime_, _Deadline_, and _Period_. Others will be pushed as standard FIFO(First In First Out) process.
Now if a deadline process, even with the normal priority, takes all the CPU, it will starve the other task and prevent FIFO process from ever running (Keep in mind this example assume 100% CPU usage). The solution they came up with is a Deadline Server that is called when starvation condition are detected. The Deadline server will allow FIFO process to run to ensure some fairness and allow for way better result. Here is an example of theses results :[2]