Re: [PATCH 3/2] sched/deadline: Use deadline instead of period when calculating overflow

[Juri Lelli]

Hi,

On 15/02/17 08:40, Luca Abeni wrote:
> Hi Steven,
> 
> On Tue, 14 Feb 2017 19:14:17 -0500
> Steven Rostedt <rostedt@xxxxxxxxxxx> wrote:
> [...]
> > > I am not sure about the correct fix (wouldn't
> > > "runtime / (deadline - t) > dl_runtime / dl_deadline" allow the
> > > task to use a fraction of CPU time equal to dl_runtime /
> > > dl_deadline?)
> > > 
> > > The current code is clearly wrong (as shown by Daniel), but I do not
> > > understand how the current check can allow the task to consume more
> > > than dl_runtime / dl_period... I need some more time to think about
> > > this issue. 
> > >   
> > 
> > This is in dl_entity_overflow() which is called by update_dl_entity()
> > which has this:
> > 
> > 	if (dl_time_before(dl_se->deadline, rq_clock(rq)) ||
> > 	    dl_entity_overflow(dl_se, pi_se, rq_clock(rq))) {
> > 		dl_se->deadline = rq_clock(rq) + pi_se->dl_deadline;
> > 		dl_se->runtime = pi_se->dl_runtime;
> > 	}
> > 
> > 
> > The comments in this code state:
> > 
> >  * The policy here is that we update the deadline of the entity only
> > if:
> >  *  - the current deadline is in the past,
> >  *  - using the remaining runtime with the current deadline would make
> >  *    the entity exceed its bandwidth.
> > 
> > That second comment is saying that when this task woke up, if the
> > percentage left to run will exceed its bandwidth with the rest of the
> > system then reset its deadline and its runtime.
> 
> Right; this is the problem. When the relative deadline is different
> from the period, the term "bandwidth" is ambiguous... We can consider
> the utilisation (maximum runtime / period), or the density (maximum
> runtime / relative deadline). In some sense, the two approaches are
> both correct (if we use density, we are more pessimistic but we try to
> respect deadlines in a hard way; if we use utilisation, we allow more
> tasks to be admitted but we can only provide bounded tardiness).
> 
> What the current code is doing is to mix the two approaches (resulting
> in a wrong runtime/deadline assignment).
> 
> > What happens in the current logic, is that overflow() check says, when
> > the deadline is much smaller than the period, "yeah, we're going to
> > exceed our percentage!" so give us more, even though it wont exceed
> > its percentage if we compared runtime with deadline.
> > 
> > The relative-runtime / relative-period is a tiny percentage, which
> > does not reflect the percentage that the task is allowed to have
> > before the deadline is hit. The tasks bandwidth should be calculated
> > by the relative-runtime / relative-deadline, as runtime <= deadline
> > <= period, and the runtime should happen within the deadline.
> > 
> > When the task wakes up, it currently looks at how much time is left
> > absolute-deadline - t, and compares it to the amount of runtime left.
> > The percentage allowed should still be compared with the percentage
> > between relative-runtime and relative-deadline. The relative-period or
> > even absolute-period, should have no influence in this decision.
> 
> Ok, thanks; I think I can now see why this can result in a task
> consuming more than the reserved utilisation. I still need some time to
> convince me that "runtime / (deadline - t) > dl_runtime / dl_deadline"
> is the correct check to use (in this case, shouldn't we also change the
> admission test to use densities instead of utilisations?)
> 

Right, this is what I was wondering as well, as dl_overflow() currently
looks at the period. And I also have some recollection of this
discussion happening already in the past, unfortunately it was not on
the list.

That discussion started with the following patch

--->8---