Bug in AC?

Hi all,

On Tue, 17 May 2016 10:02:01 +0100
Juri Lelli <[email protected]> wrote:
[...]

Quoted 7 lines

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.

Luca

Quoted 61 lines

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 <[email protected]>
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 <[email protected]> ---

 kernel/sched/core.c | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

kernel/sched/core.c +2 -2

index 096b73b..56bc449 100644
@@ -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)

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

Quoted 66 lines

Luca

Quoted 61 lines

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 <[email protected]>
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 <[email protected]> ---

 kernel/sched/core.c | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

kernel/sched/core.c +2 -2

index 096b73b..56bc449 100644
@@ -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)

Quoted 8 lines

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.

[ Added LKML and Peter ]

Quoted 24 lines · On Tue, 17 May 2016 12:38:54 +0200 luca abeni <[email protected]> wrote:

Hi all,

On Tue, 17 May 2016 10:02:01 +0100
Juri Lelli <[email protected]> wrote:
[...]

Quoted 7 lines

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

Quoted 2 lines

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

Quoted 66 lines

Luca

Quoted 61 lines

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 <[email protected]>
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 <[email protected]> ---

 kernel/sched/core.c | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

kernel/sched/core.c +2 -2

index 096b73b..56bc449 100644
@@ -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)

Quoted 8 lines · On Tue, 17 May 2016 16:07:49 +0200 luca abeni <[email protected]> wrote:

Quoted 8 lines

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.

Quoted 3 lines

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