Messages in this thread | | | Date | Tue, 17 May 2016 16:07:49 +0200 | From | luca abeni <> | Subject | Re: Bug in AC? |
| |
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) >
| |