All of lore.kernel.org
 help / color / mirror / Atom feed
* [RFC 0/8] CPU reclaiming for SCHED_DEADLINE
@ 2016-01-14 15:24 Luca Abeni
  2016-01-14 15:24 ` [RFC 1/8] Track the active utilisation Luca Abeni
                   ` (8 more replies)
  0 siblings, 9 replies; 58+ messages in thread
From: Luca Abeni @ 2016-01-14 15:24 UTC (permalink / raw)
  To: linux-kernel; +Cc: Peter Zijlstra, Ingo Molnar, Juri Lelli, Luca Abeni

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.

I send this RFC because I think the code still needs some work and/or
cleanups (or maybe the patches should be splitted or merged in a different
way), but I'd like to check if there is interest in merging this feature
and if the current implementation strategy is reasonable.

I added in cc the usual people interested in SCHED_DEADLINE patches; if
you think that I should have added someone else, let me know (or please
forward these patches to interested people).

The implemented CPU reclaiming algorithm is based on tracking the
utilization U_act of active tasks (first 5 patches), and modifying the
runtime accounting rule (see patch 0006). 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 5 patches (tracking of per-runqueue active utilization) can
be useful for frequency scaling too (the tracked "active utilization"
gives a clear hint about how much the core speed can be reduced without
compromising the SCHED_DEADLINE guarantees):
- patches 0001 and 0002 implement a simple tracking of the active
  utilization that is too optimistic from the theoretical point of
  view
- patch 0003 is mainly useful for debugging this patchset and can
  be removed without problems
- patch 0004 implements the "active utilization" tracking algorithm
  described in [1,2]. It uses a timer (named "inactive timer" here) to
  decrease U_act at the correct time (I called it the "0-lag time").
  I am working on an alternative implementation that does not use
  additional timers, but it is not ready yet; I'll post it when ready
  and tested
- patch 0005 tracks the utilization of the tasks that can execute on
  each runqueue. It is a pessimistic approximation of U_act (so, if
  used instead of U_act it allows to reclaim less CPU time, but does
  not break SCHED_DEADLINE guarantees)
- patches 0006-0008 implement the reclaiming algorithm.

[1] http://retis.sssup.it/~lipari/papers/lipariBaruah2000.pdf
[2] http://disi.unitn.it/~abeni/reclaiming/rtlws14-grub.pdf



Juri Lelli (1):
  sched/deadline: add some tracepoints

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

 include/linux/sched.h        |   1 +
 include/trace/events/sched.h |  69 ++++++++++++++
 include/uapi/linux/sched.h   |   1 +
 kernel/sched/core.c          |   3 +-
 kernel/sched/deadline.c      | 214 +++++++++++++++++++++++++++++++++++++++++--
 kernel/sched/sched.h         |  12 +++
 6 files changed, 292 insertions(+), 8 deletions(-)

-- 
1.9.1

^ permalink raw reply	[flat|nested] 58+ messages in thread

end of thread, other threads:[~2016-02-03 13:28 UTC | newest]

Thread overview: 58+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2016-01-14 15:24 [RFC 0/8] CPU reclaiming for SCHED_DEADLINE Luca Abeni
2016-01-14 15:24 ` [RFC 1/8] Track the active utilisation Luca Abeni
2016-01-14 16:49   ` Peter Zijlstra
2016-01-15  6:37     ` Luca Abeni
2016-01-14 19:13   ` Peter Zijlstra
2016-01-15  8:07     ` Luca Abeni
2016-01-14 15:24 ` [RFC 2/8] Correctly track the active utilisation for migrating tasks Luca Abeni
2016-01-14 15:24 ` [RFC 3/8] sched/deadline: add some tracepoints Luca Abeni
2016-01-14 15:24 ` [RFC 4/8] Improve the tracking of active utilisation Luca Abeni
2016-01-14 17:16   ` Peter Zijlstra
2016-01-15  6:48     ` Luca Abeni
2016-01-14 19:43   ` Peter Zijlstra
2016-01-15  9:27     ` Luca Abeni
2016-01-19 12:20     ` Luca Abeni
2016-01-19 13:47       ` Peter Zijlstra
2016-01-27 13:36         ` Luca Abeni
2016-01-27 14:39           ` Peter Zijlstra
2016-01-27 14:45             ` Luca Abeni
2016-01-28 13:08               ` Vincent Guittot
     [not found]               ` <CAKfTPtAt0gTwk9aAZN238NT1O-zJvxVQDTh2QN_KxAnE61xMww@mail.gmail.com>
2016-01-28 13:48                 ` luca abeni
2016-01-28 13:56                   ` Vincent Guittot
2016-01-28 11:14             ` luca abeni
2016-01-28 12:21               ` Peter Zijlstra
2016-01-28 13:41                 ` luca abeni
2016-01-28 14:00                   ` Peter Zijlstra
2016-01-28 21:15                     ` Luca Abeni
2016-01-14 19:47   ` Peter Zijlstra
2016-01-15  8:10     ` Luca Abeni
2016-01-15  8:32       ` Peter Zijlstra
2016-01-14 15:24 ` [RFC 5/8] Track the "total rq utilisation" too Luca Abeni
2016-01-14 19:12   ` Peter Zijlstra
2016-01-15  8:04     ` Luca Abeni
2016-01-14 19:48   ` Peter Zijlstra
2016-01-15  6:50     ` Luca Abeni
2016-01-15  8:34       ` Peter Zijlstra
2016-01-15  9:15         ` Luca Abeni
2016-01-29 15:06           ` Peter Zijlstra
2016-01-29 21:21             ` Luca Abeni
2016-01-14 15:24 ` [RFC 6/8] GRUB accounting Luca Abeni
2016-01-14 19:50   ` Peter Zijlstra
2016-01-15  8:05     ` Luca Abeni
2016-01-14 15:24 ` [RFC 7/8] Make GRUB a task's flag Luca Abeni
2016-01-14 19:56   ` Peter Zijlstra
2016-01-15  8:15     ` Luca Abeni
2016-01-15  8:41       ` Peter Zijlstra
2016-01-15  9:08         ` Luca Abeni
2016-01-14 15:24 ` [RFC 8/8] Do not reclaim the whole CPU bandwidth Luca Abeni
2016-01-14 19:59   ` Peter Zijlstra
2016-01-15  8:21     ` Luca Abeni
2016-01-15  8:50       ` Peter Zijlstra
2016-01-15  9:49         ` Luca Abeni
2016-01-26 12:52         ` luca abeni
2016-01-27 14:44           ` Peter Zijlstra
2016-02-02 20:53             ` Luca Abeni
2016-02-03 11:30               ` Juri Lelli
2016-02-03 13:28                 ` luca abeni
2016-01-19 10:11 ` [RFC 0/8] CPU reclaiming for SCHED_DEADLINE Juri Lelli
2016-01-19 11:50   ` Luca Abeni

This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.