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

[Joshua Whitehead <josh.whitehead@dornerworks.com>]

On 6/17/2014 12:06 PM, Dario Faggioli wrote:
> Although very hard, I tried to have a look at the CBS implementation
> (so, some of the '+' hunks):
> 
> On ven, 2014-06-13 at 15:58 -0400, Josh Whitehead wrote:
>> ---
> 
>> @@ -410,49 +301,59 @@ static void desched_edf_dom(s_time_t now, struct vcpu* d)
>>    
>>      __del_from_queue(d);
>>  
>> -    /*
>> -     * Manage bookkeeping (i.e. calculate next deadline, memorise
>> -     * overrun-time of slice) of finished domains.
>> -     */
>> +#ifdef SEDF_STATS
>> +    /* Manage deadline misses */
>> +    if ( unlikely(inf->deadl_abs < now) )
>> +    {
>> +        inf->miss_tot++;
>> +        inf->miss_time += inf->cputime;
>> +    }
>> +#endif
>> +
>> +    /* Manage overruns */
>>      if ( inf->cputime >= inf->slice )
>>      {
>>          inf->cputime -= inf->slice;
>> -  
>> -        if ( inf->period < inf->period_orig )
>> -        {
>> -            /* This domain runs in latency scaling or burst mode */
>> -            inf->period *= 2;
>> -            inf->slice  *= 2;
>> -            if ( (inf->period > inf->period_orig) ||
>> -                 (inf->slice > inf->slice_orig) )
>> -            {
>> -                /* Reset slice and period */
>> -                inf->period = inf->period_orig;
>> -                inf->slice = inf->slice_orig;
>> -            }
>> -        }
>>  
>>          /* Set next deadline */
>>          inf->deadl_abs += inf->period;
>> +
>> +        /* Ensure that the cputime is always less than slice */
>> +        if ( unlikely(inf->cputime > inf->slice) )
>> +        {
>> +#ifdef SEDF_STATS
>> +            inf->over_tot++;
>> +            inf->over_time += inf->cputime;
>> +#endif
>> +
>> +            /* 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.

>> +        /* Ensure that the start of the next period is in the future */
>> +        if ( unlikely(PERIOD_BEGIN(inf) < now) )
>> +            inf->deadl_abs += 
>> +                (DIV_UP(now - PERIOD_BEGIN(inf),
>> +                        inf->period)) * inf->period;
>>      }
> 
>> @@ -1100,62 +663,65 @@ static void sedf_wake(const struct scheduler *ops, struct vcpu *d)
>>      inf->block_tot++;
>>  #endif
>>  
>> -    if ( unlikely(now < PERIOD_BEGIN(inf)) )
>> -    {
>> -        /* Unblocking in extra-time! */
>> -        if ( inf->status & EXTRA_WANT_PEN_Q )
>> +    if ( sedf_soft(d) )
>> +    {
>> +        /* Apply CBS rule
>> +         * Where:
>> +         *      c == Remaining server slice == (inf->slice - cpu_time) 
>> +         *      d == Server (vcpu) deadline  == inf->deadl_abs
>> +         *      r == Wake-up time of vcpu    == now
>> +         *      U == Server (vcpu) bandwidth == (inf->slice / inf->period)
>> +         *
>> +         * if c>=(d-r)*U  --->  
>> +         *      (inf->slice - cputime) >= (inf->deadl_abs - now) * inf->period
>> +         *
> Well, I think it's rather:
> 
>   (inf->slice - cputime) >= (inf->deadl_abs - now) *
>                               (inf->slice / inf->period)
> 
> It's only the comment that is wrong, though, the code is ok.
> 
Yes, just a typo in the comments, we will correct that.

>> +         * If true, push deadline back by one period and refresh slice, else
>> +         * use current slice and deadline.
>> +         */
>> +        if((inf->slice - inf->cputime) >= 
>> +            ((inf->deadl_abs - now) * (inf->slice / inf->period)))
>>          {
>>
> 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.  Thanks!

- Josh Whitehead

> Regards,
> Dario
>