[RFC v5 0/9] CPU reclaiming for SCHED_DEADLINE

[luca abeni]

From: Luca Abeni <luca.abeni@xxxxxxxxxxxxxxx>

Hi all,

here is yet another version of the patchset implementing 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.


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 and 0008).
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 my last
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
U_act.

Changes since v4:
the most important change is the addition of patches 0007, 0008
and 0009 to solve the fairness problem highlighted by Daniel:
http://lkml.iu.edu/hypermail/linux/kernel/1701.0/01290.html
I added this fix in the last 3 patches for easier reviewing (up
to patch 0006, the patches are similar to the previous ones),
but I can merge / reorder patches if needed.

I also performed some additional testing, finding and fixing some
bugs in the first 6 patches. Daniel and Claudio also stress-tested
the patchset, finding some other bugs that have been fixed.

Other than this, I tried to address all the comments I received, and to
add comments requested in the previous reviews.

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..

Luca Abeni (9):
  sched/deadline: track the active utilization
  sched/deadline: improve the tracking of active 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: base GRUB reclaiming on the inactive utilization
  sched/deadline: also reclaim bandwidth not used by dl tasks
  sched/deadline: fix the update of the total -deadline utilization
  sched/deadline: track the "total rq utilization" too

 include/linux/sched.h      |  17 +++
 include/uapi/linux/sched.h |   1 +
 kernel/sched/core.c        |  65 ++++----
 kernel/sched/deadline.c    | 366 ++++++++++++++++++++++++++++++++++++++++++---
 kernel/sched/sched.h       |  62 +++++++-
 5 files changed, 454 insertions(+), 57 deletions(-)

-- 
2.7.4