• Dario Faggioli's avatar
    sched/deadline: Add SCHED_DEADLINE structures & implementation · aab03e05
    Dario Faggioli authored
    
    
    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: default avatarDario Faggioli <raistlin@linux.it>
    Signed-off-by: default avatarMichael Trimarchi <michael@amarulasolutions.com>
    Signed-off-by: default avatarFabio Checconi <fchecconi@gmail.com>
    Signed-off-by: default avatarJuri Lelli <juri.lelli@gmail.com>
    Signed-off-by: default avatarPeter Zijlstra <peterz@infradead.org>
    Link: http://lkml.kernel.org/r/1383831828-15501-4-git-send-email-juri.lelli@gmail.com
    
    Signed-off-by: default avatarIngo Molnar <mingo@kernel.org>
    aab03e05
sched.h 82.1 KB