sched/deadline: Add SCHED_DEADLINE structures & implementation
authorDario Faggioli <raistlin@linux.it>
Thu, 28 Nov 2013 10:14:43 +0000 (11:14 +0100)
committerIngo Molnar <mingo@kernel.org>
Mon, 13 Jan 2014 12:41:06 +0000 (13:41 +0100)
commitaab03e05e8f7e26f51dee792beddcb5cca9215a5
treebae7f6033c849e7ca77a98783c732caea412ae75
parentd50dde5a10f305253cbc3855307f608f8a3c5f73
sched/deadline: Add SCHED_DEADLINE structures & implementation

Introduces the data structures, constants and symbols needed for
SCHED_DEADLINE implementation.

Core data structure of SCHED_DEADLINE are defined, along with their
initializers. Hooks for checking if a task belong to the new policy
are also added where they are needed.

Adds a scheduling class, in sched/dl.c and a new policy called
SCHED_DEADLINE. It is an implementation of the Earliest Deadline
First (EDF) scheduling algorithm, augmented with a mechanism (called
Constant Bandwidth Server, CBS) that makes it possible to isolate
the behaviour of tasks between each other.

The typical -deadline task will be made up of a computation phase
(instance) which is activated on a periodic or sporadic fashion. The
expected (maximum) duration of such computation is called the task's
runtime; the time interval by which each instance need to be completed
is called the task's relative deadline. The task's absolute deadline
is dynamically calculated as the time instant a task (better, an
instance) activates plus the relative deadline.

The EDF algorithms selects the task with the smallest absolute
deadline as the one to be executed first, while the CBS ensures each
task to run for at most its runtime every (relative) deadline
length time interval, avoiding any interference between different
tasks (bandwidth isolation).
Thanks to this feature, also tasks that do not strictly comply with
the computational model sketched above can effectively use the new
policy.

To summarize, this patch:
 - introduces the data structures, constants and symbols needed;
 - implements the core logic of the scheduling algorithm in the new
   scheduling class file;
 - provides all the glue code between the new scheduling class and
   the core scheduler and refines the interactions between sched/dl
   and the other existing scheduling classes.

Signed-off-by: Dario Faggioli <raistlin@linux.it>
Signed-off-by: Michael Trimarchi <michael@amarulasolutions.com>
Signed-off-by: Fabio Checconi <fchecconi@gmail.com>
Signed-off-by: Juri Lelli <juri.lelli@gmail.com>
Signed-off-by: Peter Zijlstra <peterz@infradead.org>
Link: http://lkml.kernel.org/r/1383831828-15501-4-git-send-email-juri.lelli@gmail.com
Signed-off-by: Ingo Molnar <mingo@kernel.org>
include/linux/sched.h
include/linux/sched/deadline.h [new file with mode: 0644]
include/uapi/linux/sched.h
kernel/fork.c
kernel/hrtimer.c
kernel/sched/Makefile
kernel/sched/core.c
kernel/sched/deadline.c [new file with mode: 0644]
kernel/sched/sched.h
kernel/sched/stop_task.c