[PATCH 00/10] CPU reclaiming for SCHED_DEADLINE

From: luca abeni
Date: Thu May 18 2017 - 16:14:30 EST

From: Luca Abeni <luca.abeni@xxxxxxxxxxxxxxx>

Hi all,

here is the next iteration of my patchset implementing CPU reclaiming
(using the GRUB algorithm[1]) for SCHED_DEADLINE (since I think the
patchset is now mature enough, I removed the "RFC" keyword from the
emails subjects).
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.

The implemented CPU reclaiming algorithm is based on tracking the
utilization U_act of active tasks (first 2 patches), and modifying the
runtime accounting rule (see patches 0004, 0008 and 0009).
The original GRUB algorithm is modified as described in [2,3] 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 (see patch 0005: the
original algorithm can consume 100% of the CPU time, starving all the
other tasks).
Patch 0003 uses the newly introduced "inactive timer" (introduced in
patch 0002) to fix dl_overflow() and __setparam_dl().
Patch 0006 allows to enable CPU reclaiming only on selected tasks.
Patches 0007, 0008 and 0009 fix an issue found by Daniel in a previous
submission, by basing the GRUB reclaiming algorithm on the inactive
utilization U_inact as shown in [3]. Here, U_inact is computed as
the difference between the "rq utilization" (see patch 0007) and
Patch 0010 adds some documentation contributed by Claudio.

The changes respect to v5 are mostly cosmetic and about comments or
- I rearranged some code to avoid eccessive indentation,
as requested by Peter
- I modified dl_non_contending() to avoid doubts about use-after-free
- I added a comment to migrate_task_rq_dl() explaining the locking
- I added some braces to be compliant with the coding rules
- I renamed some functions and structure fields according to the
feedback I received
- I added a big comment to document the GRUB states transition
- I changed grub_reclaim() (and the comments to that function) to
make it more understandable
- I added some documentation by Claudio

Finally, I updated the patches to apply on top of tip/master.

[1] Lipari, G., & Baruah, S. (2000). Greedy reclamation of unused bandwidth in constant-bandwidth servers. In Real-Time Systems, 2000. Euromicro RTS 2000. 12th Euromicro Conference on (pp. 193-200). IEEE.
[2] Abeni, L., Lelli, J., Scordino, C., & Palopoli, L. (2014, October). Greedy CPU reclaiming for SCHED DEADLINE. In Proceedings of the Real-Time Linux Workshop (RTLWS), Dusseldorf, Germany
[3] Abeni, L., Lipari, G., Parri, A., & Sun, Y. (2016, April). Multicore CPU reclaiming: parallel or sequential?. In Proceedings of the 31st Annual ACM Symposium on Applied Computing (pp. 1877-1884). ACM..

Claudio Scordino (1):
sched/deadline: documentation about GRUB reclaiming

Luca Abeni (9):
sched/deadline: track the active utilization
sched/deadline: improve the tracking of active utilization
sched/deadline: fix the update of the total -deadline utilization
sched/deadline: implement GRUB accounting
sched/deadline: do not reclaim the whole CPU bandwidth
sched/deadline: make GRUB a task's flag
sched/deadline: track the "total rq utilization" too
sched/deadline: base GRUB reclaiming on the inactive utilization
sched/deadline: also reclaim bandwidth not used by dl tasks

Documentation/scheduler/sched-deadline.txt | 168 +++++++++++
include/linux/sched.h | 17 ++
include/uapi/linux/sched.h | 1 +
kernel/sched/core.c | 74 ++---
kernel/sched/deadline.c | 448 +++++++++++++++++++++++++++--
kernel/sched/sched.h | 66 ++++-
6 files changed, 709 insertions(+), 65 deletions(-)