Re: Bug in AC?

[luca abeni]

Hi,

On Tue, 17 May 2016 09:46:46 -0400
Steven Rostedt <rostedt@xxxxxxxxxxx> wrote:

> [ Added LKML and Peter ]
> 
> On Tue, 17 May 2016 12:38:54 +0200
> luca abeni <luca.abeni@xxxxxxxx> wrote:
> 
> > Hi all,
> > 
> > On Tue, 17 May 2016 10:02:01 +0100
> > Juri Lelli <juri.lelli@xxxxxxx> wrote:
> > [...]  
> > > Luca, Steve pinged me yesterday on IRC wondering if SCHED_DEADLINE AC
> > > control was broken as we don't consider densities.
> > > 
> > > I sent Luca this fix a while ago thinking, like Steve, that AC was
> > > broken.  But he convinced me that what we have is good enough, as not
> > > much more can be said using densities (WCET_i / D_i) in the SMP case
> > > (we could change the UP/partitioned case, though).    
> > 
> > I think Juri's summary below is correct (in the sense that it
> > correctly reflects our previous discussion).
> > 
> > The main issue here is what the kernel admission control is supposed to
> > do: in my understanding (but I might be wrong: I was not involved in
> > the design), it does not want to be a schedulability check, but it just
> > wants to ensure that some fraction of execution time is left for
> > non-deadline tasks (so that they are not starved).
> > If this is the goal, then the admission control based on utilisation
> > is ok (at least, it looks ok to me).
> > 
> > Of course, if my understanding is wrong and the goal of the admission
> > control is different, some changes are needed.  
> 
> Hmm, I thought that the checks were to guarantee that we could still
> make the deadlines, not just not lock up the system. If that's the
> goal, we need to SCREAM that out in documentation. I was already
> confused by that. I don't want people placing in wrong parameters that
> are guaranteed not to succeed and then complain that the kernel allowed
> it.
I was under the impression that the documentation explained that the
kernel admission control implements only a necessary schedulability
condition (and not a sufficient one), but maybe the documentation is
not clear enough.

I'll have a look at it and try to prepare a patch to better explain what
the current admission control really does.



				Luca


> 
> And I still don't see how this is a SMP vs UP situation. As I mentioned
> on IRC, what about the case with two CPUs and this:
> 
> Two tasks with:       R:10us D: 15us P:100us
> and two tasks with:   R:6us  D: 14us P:14us
> 
> If the period of the first two tasks line up on two different CPUs then
> there's no way the other two tasks will make their deadlines.
> 
> 
> -- Steve
> 
> 
> > 
> > 
> > 
> > 				Luca
> >   
> > > 
> > > Highlights from his reply follow (translated :-)):
> > > 
> > >  - SCHED_DEADLINE, as the documentation says, does AC using
> > > utilization
> > >  - it is true that a sufficient (but not necessary) test on UP for D_i
> > >    != P_i cases is the one of my patch below
> > >  - we have agreed in the past that the kernel should only check that
> > > we don't cause "overload" in the system (which is still the case if we
> > >    consider utilizations), not "hard schedulability"
> > >  - also because on SMP systems "sum(WCET_i / min{D_i, P_i}) <= M"
> > >    doesn't guarantee much more than the test base on P_i only (there
> > > not seem to be many/any papers around considering the D_i != P_i case
> > > on SMP actually)
> > >  - basically the patch below would only matter for the UP/partitioned
> > >    cases
> > > 
> > >  Luca please correct me if I misunderstood something.
> > > 
> > >  Steve, does this better answer your question?
> > > 
> > > - Juri
> > > 
> > > From 6cd9b6f3c2b9f144828aa09ad2a355b00a153348 Mon Sep 17 00:00:00 2001
> > > From: Juri Lelli <juri.lelli@xxxxxxx>
> > > Date: Fri, 4 Sep 2015 15:41:42 +0100
> > > Subject: [PATCH] sched/core: fix SCHED_DEADLINE admission control
> > > 
> > > As Documentation/sched/sched-deadline.txt says, a new task can pass
> > > through admission control if sum(WCET_i / min{D_i, P_i}) <= 1.
> > > However, if the user specifies both sched_period and sched_deadline,
> > > we actually check that sum(WCET_i / P_i) <= 1; and this is a less
> > > restrictive check w.r.t. the former.
> > > 
> > > Fix this by always using sched_deadline parameter to compute new_bw,
> > > as we also impose that runtime <= deadline <= period (if period != 0)
> > > and deadline != 0.
> > > 
> > > Fixes: 4df1638cfaf9 ("sched/deadline: Fix overflow to handle
> > > period==0 and deadline!=0") Signed-off-by: Juri Lelli
> > > <juri.lelli@xxxxxxx> ---
> > >  kernel/sched/core.c | 4 ++--
> > >  1 file changed, 2 insertions(+), 2 deletions(-)
> > > 
> > > diff --git a/kernel/sched/core.c b/kernel/sched/core.c
> > > index 096b73b..56bc449 100644
> > > --- a/kernel/sched/core.c
> > > +++ b/kernel/sched/core.c
> > > @@ -2302,9 +2302,9 @@ static int dl_overflow(struct task_struct *p,
> > > int policy, {
> > >  
> > >  	struct dl_bw *dl_b = dl_bw_of(task_cpu(p));
> > > -	u64 period = attr->sched_period ?: attr->sched_deadline;
> > > +	u64 deadline = attr->sched_deadline;
> > >  	u64 runtime = attr->sched_runtime;
> > > -	u64 new_bw = dl_policy(policy) ? to_ratio(period, runtime) :
> > > 0;
> > > +	u64 new_bw = dl_policy(policy) ? to_ratio(deadline,
> > > runtime) : 0; int cpus, err = -1;
> > >  
> > >  	if (new_bw == p->dl.dl_bw)    
>