[PATCH 00/10] CPU reclaiming for SCHED_DEADLINE

[luca abeni]

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
U_act.
Patch 0010 adds some documentation contributed by Claudio.

The changes respect to v5 are mostly cosmetic and about comments or
documentation:
- I rearranged some code to avoid eccessive indentation,
  as requested by Peter
  (http://lkml.iu.edu/hypermail/linux/kernel/1703.3/00291.html)
- I modified dl_non_contending() to avoid doubts about use-after-free
  (http://lkml.iu.edu/hypermail/linux/kernel/1703.3/00291.html)
- I added a comment to migrate_task_rq_dl() explaining the locking
  (http://lkml.iu.edu/hypermail/linux/kernel/1703.3/00291.html)
- 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(-)

-- 
2.7.4