On Mon, 27 Mar 2017 16:26:33 +0200
Peter Zijlstra <pet...@infradead.org> wrote:
> On Fri, Mar 24, 2017 at 04:53:01AM +0100, luca abeni wrote:
> > From: Luca Abeni <luca.ab...@santannapisa.it>
> >
> > Instead of decreasing the runtime as "dq = -Uact dt" (eventually
> > divided by the maximum utilization available for deadline tasks),
> > decrease it as "dq = -(1 - Uinact) dt", where Uinact is the
> > "inactive utilization".
>
> > In this way, the maximum fraction of CPU time that can be reclaimed
> > is given by the total utilization of deadline tasks.
> > This approach solves some fairness issues that have been noticed
> > with "traditional" global GRUB reclaiming.
>
> I think the Changelog could do with explicit enumeration of what
> "some" is.
Sorry, when writing the changelog I've been lazy; I'll add a link to
Daniel's email showing the problem in action.
> > Signed-off-by: Luca Abeni <luca.ab...@santannapisa.it>
> > Tested-by: Daniel Bristot de Oliveira <bris...@redhat.com>
> > ---
> > kernel/sched/deadline.c | 23 ++++++++++++++++-------
> > 1 file changed, 16 insertions(+), 7 deletions(-)
> >
> > diff --git a/kernel/sched/deadline.c b/kernel/sched/deadline.c
> > index d70a7b9..c393c3d 100644
> > --- a/kernel/sched/deadline.c
> > +++ b/kernel/sched/deadline.c
> > @@ -900,14 +900,23 @@ extern bool sched_rt_bandwidth_account(struct
> > rt_rq *rt_rq); /*
> > * This function implements the GRUB accounting rule:
> > * according to the GRUB reclaiming algorithm, the runtime is
> > + * not decreased as "dq = -dt", but as "dq = (1 - Uinact) dt",
> > where
>
> Changelog had it right I think: dq = -(1 - Uinact) dt
Sorry about the typo... I'll fix it
> > + * Uinact is the (per-runqueue) inactive utilization, computed as
> > the
> > + * difference between the "total runqueue utilization" and the
> > runqueue
> > + * active utilization.
> > + * Since rq->dl.running_bw and rq->dl.this_bw contain utilizations
> > + * multiplied by 2^20, the result has to be shifted right by 20.
> > */
> > -u64 grub_reclaim(u64 delta, struct rq *rq)
> > +u64 grub_reclaim(u64 delta, struct rq *rq, u64 u)
> > {
> > + u64 u_act;
> > +
> > + if (rq->dl.this_bw - rq->dl.running_bw > (1 << 20) - u)
> > + u_act = u;
> > + else
> > + u_act = (1 << 20) - rq->dl.this_bw +
> > rq->dl.running_bw; +
> > + return (delta * u_act) >> 20;
>
> But that's not what is done here I think, something like this instead:
>
> Uinact = Utot - Uact
>
> -t_u dt ; Uinact > (1 - t_u)
> dq = {
> -(1 - Uinact) dt
>
>
> And nowhere do we have an explanation for that.
Sorry about this confusion... The accounting should be
dq = -(1 - Uinact)dt
but if (1 - Uinact) is too large (larger than the task's utilization)
then we use the task's utilization instead (otherwise, we end up
reclaiming other runqueues' time). I realized that this check was
needed after writing the comments, and I forgot to update the comments
when I fixed the code :(
> Now, I suspect we can write that like: dq = -max{ t_u, (1 - Uinact) }
> dt, which would suggest this is a sanity check on Utot, which I
> suspect can be over 1. Is this what is happening?
Right... I'll fix the code and comments according to your suggestion.
Thanks,
Luca
> #define BW_SHIFT 20
> #define BW_UNIT (1 << BW_SHIFT)
>
> static inline
> u64 grub_reclaim(u64 delta, struct rq *rq, struct sched_dl_entity
> *dl_se) {
> u64 u_inact = rq->dl.this_bw - rq->dl.running_bw; /* Utot -
> Uact */ u64 u_act;
>
> /*
> * What we want to write is:
> *
> * max(BW_UNIT - u_inact, dl_se->dl_bw)
> *
> * but we cannot do that since Utot can be larger than 1,
> * which means u_inact can be larger than 1, which would
> * have the above result in negative values.
> */
> if (u_inact > (BW_UNIT - dl_se->dl_bw))
> u_act = dl_se->dl_bw;
> else
> u_act = BW_UNIT - u_inact;
>
> return (delta * u_act) >> BW_SHIFT;
> }
>
> Hmm?
