Re: [Xen-devel] [RFC PATCH 1/4] Implement cbs algorithm, remove extra queues, latency scaling, and weight support from sedf

[Dario Faggioli <dario.faggioli@xxxxxxxxxx>]

On gio, 2014-06-26 at 16:18 -0400, Joshua Whitehead wrote:
> On 6/17/2014 12:06 PM, Dario Faggioli wrote:
> >> +
> >> +            /* Make up for the overage by pushing the deadline
> >> +               into the future */
> >> +            inf->deadl_abs += ((inf->cputime / inf->slice)
> >> +                               * inf->period) * 2;
> >> +            inf->cputime -= (inf->cputime / inf->slice) * inf->slice;
> >> +        }
> >>
> > Can you enlighten me a bit about the math here? I see what you're up to,
> > but I'm not sure I understand the '*2'...
> > 
> Ah, the '*2' is not necessary, it may be a leftover from an experiment we were
> doing at one point.  This was something we caught as well but apparently it 
> got
> overlooked before we submitted the series.  I will make sure to update this 
> for
> the V2 patch.
> 
Ok. When I'll see v2, I'll tell more, as I can't right now. My
impression still is that what you're up to is sensible, but I think it
should be done differently. At least, I've always done it differently,
in all the EDF/CBS implementation I wrote, and I'm not sure I fully
understand this variant of yours.

But again, send v2, and I'll comment on it! :-)

> > You can shuffle this a bit more, and avoid the '/'.
> > 
> > The condition above can be rewritten as:
> > 
> >   c >= (d-r) * (inf->slide/inf->period)
> > 
> > i.e.:
> > 
> >   c * inf->period >= (d-r) * inf->slice
> > 
> > and this, the code can be rewritten as:
> > 
> >   if ((inf->slice - inf->cputime) * inf->period >=
> >       (inf->deadl_abs - now) * inf->slice)
> > 
> > which I think it's better. One may worry about the fact that the
> > multiplication can overflow, but that's really unlikely, since all the
> > involved time values are relative (i.e., remaining runtime, time to
> > deadline, etc).
> > 
> > Anyway, let's cross that bridge when we get to it.
> >
> This is a good point- because of the new nature of the scheduler we had not 
> made
> any attempts at simplification yet, but rather attempted to keep it as 
> apparent
> and straightforward as possible until we were positive everything was working
> correctly.  This would certainly be a good simplification and I agree the
> multiplication overflow is highly unlikely.  If you would like I can make this
> update in the V2, or we can leave it until we get any other bugs ironed out,
> whichever you think would be easiest.
>
It's rather basic math, IMO, and it does not really makes the condition,
and hence the whole algorithm, any harder to understand.

I'd say, do it right away, in v2. Do put a comment on top, with the
equation in the 'plain' form, and specify that you're shuffling for
avoiding a div, and that should do.

Regards,
Dario
-- 
<<This happens because I choose it to happen!>> (Raistlin Majere)
-----------------------------------------------------------------
Dario Faggioli, Ph.D, http://about.me/dario.faggioli
Senior Software Engineer, Citrix Systems R&D Ltd., Cambridge (UK)

Attachment: signature.asc
Description: This is a digitally signed message part

_______________________________________________
Xen-devel mailing list
Xen-devel@xxxxxxxxxxxxx
http://lists.xen.org/xen-devel