• Juri Lelli's avatar
    sched/deadline: Add SCHED_DEADLINE SMP-related data structures & logic · 1baca4ce
    Juri Lelli authored
    Introduces data structures relevant for implementing dynamic
    migration of -deadline tasks and the logic for checking if
    runqueues are overloaded with -deadline tasks and for choosing
    where a task should migrate, when it is the case.
    
    Adds also dynamic migrations to SCHED_DEADLINE, so that tasks can
    be moved among CPUs when necessary. It is also possible to bind a
    task to a (set of) CPU(s), thus restricting its capability of
    migrating, or forbidding migrations at all.
    
    The very same approach used in sched_rt is utilised:
     - -deadline tasks are kept into CPU-specific runqueues,
     - -deadline tasks are migrated among runqueues to achieve the
       following:
        * on an M-CPU system the M earliest deadline ready tasks
          are always running;
        * affinity/cpusets settings of all the -deadline tasks is
          always respected.
    
    Therefore, this very special form of "load balancing" is done with
    an active method, i.e., the scheduler pushes or pulls tasks between
    runqueues when they are woken up and/or (de)scheduled.
    IOW, every time a preemption occurs, the descheduled task might be sent
    to some other CPU (depending on its deadline) to continue executing
    (push). On the other hand, every time a CPU becomes idle, it might pull
    the second earliest deadline ready task from some other CPU.
    
    To enforce this, a pull operation is always attempted before taking any
    scheduling decision (pre_schedule()), as well as a push one after each
    scheduling decision (post_schedule()). In addition, when a task arrives
    or wakes up, the best CPU where to resume it is selected taking into
    account its affinity mask, the system topology, but also its deadline.
    E.g., from the scheduling point of view, the best CPU where to wake
    up (and also where to push) a task is the one which is running the task
    with the latest deadline among the M executing ones.
    
    In order to facilitate these decisions, per-runqueue "caching" of the
    deadlines of the currently running and of the first ready task is used.
    Queued but not running tasks are also parked in another rb-tree to
    speed-up pushes.
    Signed-off-by: default avatarJuri Lelli <juri.lelli@gmail.com>
    Signed-off-by: default avatarDario Faggioli <raistlin@linux.it>
    Signed-off-by: default avatarPeter Zijlstra <peterz@infradead.org>
    Link: http://lkml.kernel.org/r/1383831828-15501-5-git-send-email-juri.lelli@gmail.comSigned-off-by: default avatarIngo Molnar <mingo@kernel.org>
    1baca4ce
rt.c 45.7 KB