* Re: Bug in AC?
2016-05-17 13:46 ` Bug in AC? Steven Rostedt
@ 2016-05-17 14:07 ` luca abeni
2016-05-17 14:33 ` Steven Rostedt
2016-05-17 21:17 ` luca abeni
1 sibling, 1 reply; 5+ messages in thread
From: luca abeni @ 2016-05-17 14:07 UTC (permalink / raw)
To: Steven Rostedt; +Cc: Juri Lelli, LKML, Peter Zijlstra
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)
>
^ permalink raw reply [flat|nested] 5+ messages in thread* Re: Bug in AC?
2016-05-17 13:46 ` Bug in AC? Steven Rostedt
2016-05-17 14:07 ` luca abeni
@ 2016-05-17 21:17 ` luca abeni
1 sibling, 0 replies; 5+ messages in thread
From: luca abeni @ 2016-05-17 21:17 UTC (permalink / raw)
To: Steven Rostedt; +Cc: Juri Lelli, LKML, Peter Zijlstra
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)
>
^ permalink raw reply [flat|nested] 5+ messages in thread