Messages in this thread | | | Date | Mon, 27 Mar 2017 16:56:51 +0200 | From | Luca Abeni <> | Subject | Re: [RFC v5 8/9] sched/deadline: base GRUB reclaiming on the inactive utilization |
| |
On Mon, 27 Mar 2017 16:26:33 +0200 Peter Zijlstra <peterz@infradead.org> wrote:
> On Fri, Mar 24, 2017 at 04:53:01AM +0100, luca abeni wrote: > > From: Luca Abeni <luca.abeni@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.abeni@santannapisa.it> > > Tested-by: Daniel Bristot de Oliveira <bristot@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?
| |