Re: Bug in AC?

Re: Bug in AC?

[Steven Rostedt]

[ Added LKML and Peter ]

On Tue, 17 May 2016 12:38:54 +0200
luca abeni <luca.abeni@unitn.it> wrote:

> Hi all,
> 
> On Tue, 17 May 2016 10:02:01 +0100
> Juri Lelli <juri.lelli@arm.com> 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@arm.com>
> > 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@arm.com> ---
> >  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)  

Re: Bug in AC?

[luca abeni]

Hi all,

a quick reply because I am in hurry... I'll write a longer reply this
evening or tomorrow

On Tue, 17 May 2016 09:46:46 -0400
Steven Rostedt <rostedt@goodmis.org> wrote:
[...]
> And I still don't see how this is a SMP vs UP situation.
Well, on UP if the sum of the sum of the tasks' densities is <= 1 then
all the deadlines are guaranteed to be respected; on SMP, there is no
similar guarantee based on tasks' densities (or utilisations): due to
the Dhall's effect, you can respect all of the deadlines only if the
sum of the densities is <= 1 (as in the UP case), independently from
the number of CPUs.

In other words: on UP a density-based (or utilisation-based) admission
control can guarantee the respect of deadlines, on SMP it cannot (you
have to use more advanced and complex admission control techniques).

> 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.
I agree this taskset is not schedulable on 2 CPUs. The problem is that
it is possible to generate tasksets with sum of densities < 2 that are
not schedulable on 2 CPUs.


				Luca
> 
> -- 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@arm.com>
> > > 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@arm.com> ---
> > >  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)    
> 

Re: Bug in AC?

[Steven Rostedt]

On Tue, 17 May 2016 16:07:49 +0200
luca abeni <luca.abeni@unitn.it> wrote:

> > 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.  
> I agree this taskset is not schedulable on 2 CPUs. The problem is that
> it is possible to generate tasksets with sum of densities < 2 that are
> not schedulable on 2 CPUs.

Makes sense. Thus the case is that we can't guarantee it on SMP anyway,
so why put the extra effort to use deadline instead of period, where on
UP we can make those guarantees.

I was under the impression that it appeared everyone was saying that SMP
we can guarantee it and UP we could not, which is where I was confused.

-- Steve

Re: Bug in AC?

[luca abeni]

Hi,

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

> [ Added LKML and Peter ]
> 
> On Tue, 17 May 2016 12:38:54 +0200
> luca abeni <luca.abeni@unitn.it> wrote:
> 
> > Hi all,
> > 
> > On Tue, 17 May 2016 10:02:01 +0100
> > Juri Lelli <juri.lelli@arm.com> 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@arm.com>
> > > 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@arm.com> ---
> > >  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)    
> 

Re: Bug in AC?

[luca abeni]

On Tue, 17 May 2016 10:33:00 -0400
Steven Rostedt <rostedt@goodmis.org> wrote:

> On Tue, 17 May 2016 16:07:49 +0200
> luca abeni <luca.abeni@unitn.it> wrote:
> 
> > > 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.    
> > I agree this taskset is not schedulable on 2 CPUs. The problem is that
> > it is possible to generate tasksets with sum of densities < 2 that are
> > not schedulable on 2 CPUs.  
> 
> Makes sense. Thus the case is that we can't guarantee it on SMP anyway,
> so why put the extra effort to use deadline instead of period, where on
> UP we can make those guarantees.

My understanding (but, again, I might be wrong) is that periods are used
because the admission control based on periods (sum of utilisations
smaller than a given value) has a clear meaning (if the admission control
is passed, than I know that at least a specified percentage of CPU time is
left for non-deadline tasks).
On the other hand, the meaning on the admission control based on deadlines
is clear only on UP (on SMP, the fact that the admission control is passed
does not guarantee anything in particular - at least, it does not guarantee
anything more than the period-based admission control).



			Luca
> 
> I was under the impression that it appeared everyone was saying that SMP
> we can guarantee it and UP we could not, which is where I was confused.
> 
> -- Steve