Re: [RFC 0/8] CPU reclaiming for SCHED_DEADLINE

[Luca Abeni]

On 01/19/2016 11:11 AM, Juri Lelli wrote:
> On 14/01/16 16:24, Luca Abeni wrote:
> > Hi all,
>
> Hi Luca,
>
> thanks a lot for posting these patches, it is something that we need to
> have at this point, IMHO.
>
> I'll try to do some more testing hopefully soon, but, if you already
> addressed Peter's comments and want to post a v2, please don't wait for
> me. I'll try to test and review the next version. Let me see if I'm able
> to setup that testing in the meantime :).
Thanks Juri; I'll work on Peter's comments in the next days, and I'll
post a v2 of the RFC, probably in the first days of February.


			Thanks,
				Luca

> Best,
>
> - Juri
>
> > 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