Re: Bug in AC?

[Steven Rostedt]

[ 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.

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)