[RFC v2 0/7] CPU reclaiming for SCHED_DEADLINE

[Luca Abeni <luca.abeni@unitn.it>]

Hi all,

this patchset implements CPU reclaiming (using the GRUB algorithm[1])
for SCHED_DEADLINE: basically, this feature allows SCHED_DEADLINE tasks
to consume more than their reserved runtime, up to a maximum fraction
of the CPU time (so that other tasks are left some spare CPU time to
execute), if this does not break the guarantees of other SCHED_DEADLINE
tasks.
The patchset applies on top of tip/master.

Respect to the first version of the RFC:
- I tried to address all the comments I received
- I removed some patches that were not really used in the patchset
- I rebased on tip/master
- I removed all the checkpatch warnings
- I added a new patch (patch 0004) to update the total -deadline
  utilization (dl_b->total_bw) at the correct time, addressing the
  large comment in __setparam_dl() (see both  dl_overflow() and
  __setparam_dl()). 


The implemented CPU reclaiming algorithm is based on tracking the
utilization U_act of active tasks (first 3 patches), and modifying the
runtime accounting rule (see patch 0005). The original GRUB algorithm is
modified as described in [2] to support multiple CPUs (the original
algorithm only considered one single CPU, this one tracks U_act per
runqueue) and to leave an "unreclaimable" fraction of CPU time to non
SCHED_DEADLINE tasks (the original algorithm can consume 100% of the CPU
time, starving all the other tasks).

I tried to split the patches so that the whole patchset can be better
understood; if they should be organized in a different way, let me know.
The first 3 patches (tracking of per-runqueue active utilization) can
be useful for frequency scaling too.
Patches 0005-0007 implement the reclaiming algorithm. and patch 0004
uses the newly introduced "inactive timer" (introduced in patch 0003)
to fix dl_overflow() and __setparam_dl().


Luca Abeni (7):
  Track the active utilisation
  Correctly track the active utilisation for migrating tasks
  Improve the tracking of active utilisation
  Fix the update of the total -deadline utilization
  GRUB accounting
  Make GRUB a task's flag
  Do not reclaim the whole CPU bandwidth

 include/linux/sched.h      |   1 +
 include/uapi/linux/sched.h |   1 +
 kernel/sched/core.c        |  44 ++++-----
 kernel/sched/deadline.c    | 225 +++++++++++++++++++++++++++++++++++++++++----
 kernel/sched/sched.h       |  13 +++
 5 files changed, 239 insertions(+), 45 deletions(-)

-- 
2.5.0