[RFC v2 0/7] CPU reclaiming for SCHED_DEADLINE

Luca Abeni
2016-04-01T15:18:24Z

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