Skip to contentSkip to conversation

sched/deadline: Throttle a constrained task activated if overflow

PATCH In review Xunlei Pang 5 participants 15 messages Apr 10, 2017 – Apr 13, 2017 Scheduler

lore
Share & tools
lore
#0 lore raw

PATCH 1/1 sched/deadline: Throttle a constrained task activated if overflow

I was testing Daniel's changes with his test case in the commit df8eac8cafce ("sched/deadline: Throttle a constrained deadline task activated after the deadline"), and tweaked it a little.

Instead of having the runtime equal to the deadline, I tweaked runtime, deadline and sleep value to ensure every time it calls dl_check_constrained_dl() with "dl_se->deadline > rq_clock(rq)" as well as true dl_entity_overflow(), so it does replenishing every wake up in update_dl_entity(), and break its bandwidth.

Daniel's test case had:
attr.sched_runtime = 2 * 1000 * 1000; /* 2 ms */ attr.sched_deadline = 2 * 1000 * 1000; /* 2 ms*/ attr.sched_period = 2 * 1000 * 1000 * 1000; /* 2 s */ ts.tv_sec = 0;
ts.tv_nsec = 2000 * 1000; /* 2 ms */

I changed it to:
attr.sched_runtime = 5 * 1000 * 1000; /* 5 ms */ attr.sched_deadline = 7 * 1000 * 1000; /* 7 ms */ attr.sched_period = 1 * 1000 * 1000 * 1000; /* 1 s */ ts.tv_sec = 0;
ts.tv_nsec = 1000 * 1000; /* 1 ms */

The change above can result in over 25% of the CPU on my machine.

In order to avoid the beakage, we improve dl_check_constrained_dl() to prevent dl tasks from being activated until the next period if it runs out of bandwidth of the current period.

Cc Daniel Bristot de Oliveira <[email protected]>
Cc Steven Rostedt <[email protected]>
---
 kernel/sched/deadline.c | 47 +++++++++++++++++++++++++++--------------------
 1 file changed, 27 insertions(+), 20 deletions(-)
kernel/sched/deadline.c +27 -20
index a2ce590..e7be3b4 100644
@@ -702,28 +702,33 @@ void init_dl_task_timer(struct sched_dl_entity *dl_se)
  * works fine for implicit deadline tasks (deadline == period), and the
  * CBS was designed for implicit deadline tasks. However, a task with
  * constrained deadline (deadine < period) might be awakened after the
- * deadline, but before the next period. In this case, replenishing the
- * task would allow it to run for runtime / deadline. As in this case
- * deadline < period, CBS enables a task to run for more than the
- * runtime / period. In a very loaded system, this can cause a domino
- * effect, making other tasks miss their deadlines.
+ * deadline before the next period, or before the deadline but bandwidth
+ * of the current period was used up. In these cases, replenishing the
+ * task would allow it to run for more than runtime / period. In a very
+ * loaded system, this can cause a domino effect, making other tasks miss
+ * their deadlines.
  *
- * To avoid this problem, in the activation of a constrained deadline
- * task after the deadline but before the next period, throttle the
- * task and set the replenishing timer to the begin of the next period,
- * unless it is boosted.
+ * To avoid these problems, in the activation of a constrained deadline
+ * task, throttle the task as needed and set the replenishing timer to
+ * the begin of the next period.
  */
 static inline void dl_check_constrained_dl(struct sched_dl_entity *dl_se)
 {
 	struct task_struct *p = dl_task_of(dl_se);
 	struct rq *rq = rq_of_dl_rq(dl_rq_of_se(dl_se));
 
-	if (dl_time_before(dl_se->deadline, rq_clock(rq)) &&
-	    dl_time_before(rq_clock(rq), dl_next_period(dl_se))) {
-		if (unlikely(dl_se->dl_boosted || !start_dl_timer(p)))
-			return;
-		dl_se->dl_throttled = 1;
-	}
+	if (dl_time_before(dl_next_period(dl_se), rq_clock(rq)))
+		return;
+
+	/* Still have available bandwidth in the current period. */
+	if (dl_time_before(rq_clock(rq), dl_se->deadline) &&
+	    !dl_entity_overflow(dl_se, dl_se, rq_clock(rq)))
+		return;
+
+	if (!start_dl_timer(p))
+		return;
+
+	dl_se->dl_throttled = 1;
 }
 
 static
@@ -990,12 +995,14 @@ static void enqueue_task_dl(struct rq *rq, struct task_struct *p, int flags)
 	}
 
 	/*
-	 * Check if a constrained deadline task was activated
-	 * after the deadline but before the next period.
-	 * If that is the case, the task will be throttled and
-	 * the replenishment timer will be set to the next period.
+	 * Check if a constrained deadline task is allowed to be
+	 * activated in the current period. If not, the task will
+	 * be throttled and the replenishment timer will be set to
+	 * the next period. Skip boosted and throttled tasks.
 	 */
-	if (!p->dl.dl_throttled && dl_is_constrained(&p->dl))
+	if (!p->dl.dl_boosted &&
+	    !p->dl.dl_throttled &&
+	    dl_is_constrained(&p->dl))
 		dl_check_constrained_dl(&p->dl);
 
 	/*
Signature · 1 line
1.8.3.1
#1 lore raw
Quoted 24 lines · Xunlei Pang

I was testing Daniel's changes with his test case in the commit df8eac8cafce ("sched/deadline: Throttle a constrained deadline task activated after the deadline"), and tweaked it a little.

Instead of having the runtime equal to the deadline, I tweaked runtime, deadline and sleep value to ensure every time it calls dl_check_constrained_dl() with "dl_se->deadline > rq_clock(rq)" as well as true dl_entity_overflow(), so it does replenishing every wake up in update_dl_entity(), and break its bandwidth.

Daniel's test case had:
attr.sched_runtime = 2 * 1000 * 1000; /* 2 ms */ attr.sched_deadline = 2 * 1000 * 1000; /* 2 ms*/ attr.sched_period = 2 * 1000 * 1000 * 1000; /* 2 s */ ts.tv_sec = 0;
ts.tv_nsec = 2000 * 1000; /* 2 ms */

I changed it to:
attr.sched_runtime = 5 * 1000 * 1000; /* 5 ms */ attr.sched_deadline = 7 * 1000 * 1000; /* 7 ms */ attr.sched_period = 1 * 1000 * 1000 * 1000; /* 1 s */ ts.tv_sec = 0;
ts.tv_nsec = 1000 * 1000; /* 1 ms */

Quoted 5 lines

The change above can result in over 25% of the CPU on my machine.

In order to avoid the beakage, we improve dl_check_constrained_dl() to prevent dl tasks from being activated until the next period if it runs out of bandwidth of the current period.

The problem now is that, with your patch, we will throttle the task with some possible runtime. Moreover, the task did not brake any rule, like being awakened after the deadline - the user-space is not misbehaving.

That is +- what the reproducer is doing when using your patch, (I put some trace_printk when noticing the overflow in the wakeup).

          <idle>-0     [007] d.h.  1505.066439: enqueue_task_dl: my current runtime is 3657361 and the deadline is 4613027 from now 
          <idle>-0     [007] d.h.  1505.066439: enqueue_task_dl: 	my dl_runtime is 5000000

and so the task will be throttled with 3657361 ns runtime available.

As we can see, it is really breaking the density:

5ms / 7ms (.714285) < 3657361 / 4613027 (.792833)

Well, it is not breaking that much. Trying to be less pessimist, we can compute a new runtime with following equation:

runtime = (dl_runtime / dl_deadline) * (deadline - now)

That is, a runtime which fits in the task's density.

In code:

dl_se->runtime = (div64_u64(dl_se->dl_runtime << 20, dl_se->dl_deadline) * (dl_se->deadline - rq_clock(rq))) >> 20;

For example (a trace_printk) showing the adjusted runtime for the previous task:

          <idle>-0     [007] d.h.  1505.066440: enqueue_task_dl: 	I can still run for 3294208 (it is not that bad)

With the adjusted runtime, we have the following density:

3294208 / 4613027 = .714109

as .714109 < .714285

Voilà. We can still use 3.2 ms of runtime! Not bad at all.

However, even this result is, somehow, controversial. Because we are reducing the task's reservation (Q/P). But that is very close to the implicit deadline behavior: when it "overflows", the runtime is truncated (a replenishment...) and the deadline is postponed. In this case, we do not need to postpone the deadline, just to "truncate" the runtime to fit in the density... it is not that bad.

Another possibility is not to replenish a constrained deadline task twice in a period. In this case, the task would run further the deadline, potentially causing problems for implicit deadline tasks. But! even implicit deadline would do it in a overloaded system. The problem is that, by using the density the system easily becomes overloaded (too pessimistic).

Resuming (so far):

1) We can be pessimistic to the constrained deadline task, with Xunlei's patch;
2) Compute a new runtime to fit in the density - somehow pessimistic.
3) Avoid replenishing a constrained deadline before the next period. but the system will become overload very easily (density).

I think the option 2 is the mid-term.
I am showing a _proof of concept_ patch bellow. I is based in the Xunlei's changes in the verification. I need to polish it... but... you guys can read the idea in C.

I have the 3) too, but I am not sure if it is as good as 2.

We still need to think more about the solution.... test more... I will continue working on this tomorrow, discussing with luca and tommaso as well.

Thoughts? Am I missing something (probably, I am tired :-) )?

---
 kernel/sched/deadline.c | 53 ++++++++++++++++++++++++++++---------------------
 1 file changed, 30 insertions(+), 23 deletions(-)
kernel/sched/deadline.c +30 -23
index 7508129..6fa4887 100644
@@ -696,34 +696,38 @@ void init_dl_task_timer(struct sched_dl_entity *dl_se)
 }
 
 /*
- * During the activation, CBS checks if it can reuse the current task's
- * runtime and period. If the deadline of the task is in the past, CBS
- * cannot use the runtime, and so it replenishes the task. This rule
- * works fine for implicit deadline tasks (deadline == period), and the
- * CBS was designed for implicit deadline tasks. However, a task with
- * constrained deadline (deadine < period) might be awakened after the
- * deadline, but before the next period. In this case, replenishing the
- * task would allow it to run for runtime / deadline. As in this case
- * deadline < period, CBS enables a task to run for more than the
- * runtime / period. In a very loaded system, this can cause a domino
- * effect, making other tasks miss their deadlines.
- *
- * To avoid this problem, in the activation of a constrained deadline
- * task after the deadline but before the next period, throttle the
- * task and set the replenishing timer to the begin of the next period,
- * unless it is boosted.
+ * XXX: Daniel will document it better in a clean patch, this is
+ * a proof of concept.
  */
 static inline void dl_check_constrained_dl(struct sched_dl_entity *dl_se)
 {
 	struct task_struct *p = dl_task_of(dl_se);
 	struct rq *rq = rq_of_dl_rq(dl_rq_of_se(dl_se));
+	u64 clock = rq_clock(rq);
 
-	if (dl_time_before(dl_se->deadline, rq_clock(rq)) &&
-	    dl_time_before(rq_clock(rq), dl_next_period(dl_se))) {
-		if (unlikely(dl_se->dl_boosted || !start_dl_timer(p)))
-			return;
-		dl_se->dl_throttled = 1;
+	/* we are in a new period */
+	if (dl_time_before(dl_next_period(dl_se), rq_clock(rq)))
+		return;
+
+	/* are we ok with the deadline and density? */
+	if (dl_time_before(rq_clock(rq), dl_se->deadline) &&
+	    !dl_entity_overflow(dl_se, dl_se, rq_clock(rq)))
+		return;
+
+	/* is the density the problem? */
+	if (dl_entity_overflow(dl_se, dl_se, clock)) {
+		/* reduces the runtime so it fits in the density */
+		dl_se->runtime =
+		  (div64_u64(dl_se->dl_runtime << 20, dl_se->dl_deadline) *
+		  (dl_se->deadline - clock)) >> 20;
+		WARN_ON(dl_se->runtime < 0);
+		return;
 	}
+
+	if (!start_dl_timer(p))
+		return;
+
+	dl_se->dl_throttled = 1;
 }
 
 static
@@ -996,8 +1000,11 @@ static void enqueue_task_dl(struct rq *rq, struct task_struct *p, int flags)
 	 * If that is the case, the task will be throttled and
 	 * the replenishment timer will be set to the next period.
 	 */
-	if (!dl_se->dl_throttled && dl_is_constrained(dl_se))
-		dl_check_constrained_dl(dl_se);
+	if (!p->dl.dl_boosted &&
+	    !p->dl.dl_throttled &&
+	    dl_is_constrained(&p->dl))
+		dl_check_constrained_dl(&p->dl);
+
 
 	/*
 	 * If p is throttled, we do nothing. In fact, if it exhausted
Signature · 1 line
2.5.0
#2 lore raw
Quoted 38 lines · Daniel Bristot de Oliveira
Quoted 24 lines · Xunlei Pang

I was testing Daniel's changes with his test case in the commit df8eac8cafce ("sched/deadline: Throttle a constrained deadline task activated after the deadline"), and tweaked it a little.

Instead of having the runtime equal to the deadline, I tweaked runtime, deadline and sleep value to ensure every time it calls dl_check_constrained_dl() with "dl_se->deadline > rq_clock(rq)" as well as true dl_entity_overflow(), so it does replenishing every wake up in update_dl_entity(), and break its bandwidth.

Daniel's test case had:
attr.sched_runtime = 2 * 1000 * 1000; /* 2 ms */ attr.sched_deadline = 2 * 1000 * 1000; /* 2 ms*/ attr.sched_period = 2 * 1000 * 1000 * 1000; /* 2 s */ ts.tv_sec = 0;
ts.tv_nsec = 2000 * 1000; /* 2 ms */

I changed it to:
attr.sched_runtime = 5 * 1000 * 1000; /* 5 ms */ attr.sched_deadline = 7 * 1000 * 1000; /* 7 ms */ attr.sched_period = 1 * 1000 * 1000 * 1000; /* 1 s */ ts.tv_sec = 0;
ts.tv_nsec = 1000 * 1000; /* 1 ms */

Quoted 5 lines

The change above can result in over 25% of the CPU on my machine.

In order to avoid the beakage, we improve dl_check_constrained_dl() to prevent dl tasks from being activated until the next period if it runs out of bandwidth of the current period.

The problem now is that, with your patch, we will throttle the task with some possible runtime. Moreover, the task did not brake any rule, like being awakened after the deadline - the user-space is not misbehaving.

That is +- what the reproducer is doing when using your patch, (I put some trace_printk when noticing the overflow in the wakeup).

Quoted 8 lines
          <idle>-0     [007] d.h.  1505.066439: enqueue_task_dl: my current runtime is 3657361 and the deadline is 4613027 from now 
          <idle>-0     [007] d.h.  1505.066439: enqueue_task_dl: 	my dl_runtime is 5000000

and so the task will be throttled with 3657361 ns runtime available.

As we can see, it is really breaking the density:

5ms / 7ms (.714285) < 3657361 / 4613027 (.792833)

For the runtime 5ms, deadline 7ms, 3657361 is the remaining runtime, so the actual runtime is (5000000 - 3657361) = 1342639, and the actual density is 1342639 / 7000000 (.191806), not break the limited density 5ms / 7ms (.714285).

"3657361 / 4613027 (.792833)" means available density greater than limited density(.714285), this means true dl_entity_overflow(), and can't meet the requirement in the current period any more, thus need to throttle it until next period.

Regards,
Xunlei

Quoted 141 lines

Well, it is not breaking that much. Trying to be less pessimist, we can compute a new runtime with following equation:

runtime = (dl_runtime / dl_deadline) * (deadline - now)

That is, a runtime which fits in the task's density.

In code:

dl_se->runtime = (div64_u64(dl_se->dl_runtime << 20, dl_se->dl_deadline) * (dl_se->deadline - rq_clock(rq))) >> 20;

For example (a trace_printk) showing the adjusted runtime for the previous task:

          <idle>-0     [007] d.h.  1505.066440: enqueue_task_dl: 	I can still run for 3294208 (it is not that bad)

With the adjusted runtime, we have the following density:

3294208 / 4613027 = .714109

as .714109 < .714285

Voilà. We can still use 3.2 ms of runtime! Not bad at all.

However, even this result is, somehow, controversial. Because we are reducing the task's reservation (Q/P). But that is very close to the implicit deadline behavior: when it "overflows", the runtime is truncated (a replenishment...) and the deadline is postponed. In this case, we do not need to postpone the deadline, just to "truncate" the runtime to fit in the density... it is not that bad.

Another possibility is not to replenish a constrained deadline task twice in a period. In this case, the task would run further the deadline, potentially causing problems for implicit deadline tasks. But! even implicit deadline would do it in a overloaded system. The problem is that, by using the density the system easily becomes overloaded (too pessimistic).

Resuming (so far):

1) We can be pessimistic to the constrained deadline task, with Xunlei's patch;
2) Compute a new runtime to fit in the density - somehow pessimistic.
3) Avoid replenishing a constrained deadline before the next period. but the system will become overload very easily (density).

I think the option 2 is the mid-term.
I am showing a _proof of concept_ patch bellow. I is based in the Xunlei's changes in the verification. I need to polish it... but... you guys can read the idea in C.

I have the 3) too, but I am not sure if it is as good as 2.

We still need to think more about the solution.... test more... I will continue working on this tomorrow, discussing with luca and tommaso as well.

Thoughts? Am I missing something (probably, I am tired :-) )?

---
 kernel/sched/deadline.c | 53 ++++++++++++++++++++++++++++---------------------
 1 file changed, 30 insertions(+), 23 deletions(-)
kernel/sched/deadline.c +30 -23
index 7508129..6fa4887 100644
@@ -696,34 +696,38 @@ void init_dl_task_timer(struct sched_dl_entity *dl_se)
 }
 
 /*
- * During the activation, CBS checks if it can reuse the current task's
- * runtime and period. If the deadline of the task is in the past, CBS
- * cannot use the runtime, and so it replenishes the task. This rule
- * works fine for implicit deadline tasks (deadline == period), and the
- * CBS was designed for implicit deadline tasks. However, a task with
- * constrained deadline (deadine < period) might be awakened after the
- * deadline, but before the next period. In this case, replenishing the
- * task would allow it to run for runtime / deadline. As in this case
- * deadline < period, CBS enables a task to run for more than the
- * runtime / period. In a very loaded system, this can cause a domino
- * effect, making other tasks miss their deadlines.
- *
- * To avoid this problem, in the activation of a constrained deadline
- * task after the deadline but before the next period, throttle the
- * task and set the replenishing timer to the begin of the next period,
- * unless it is boosted.
+ * XXX: Daniel will document it better in a clean patch, this is
+ * a proof of concept.
  */
 static inline void dl_check_constrained_dl(struct sched_dl_entity *dl_se)
 {
 	struct task_struct *p = dl_task_of(dl_se);
 	struct rq *rq = rq_of_dl_rq(dl_rq_of_se(dl_se));
+	u64 clock = rq_clock(rq);
 
-	if (dl_time_before(dl_se->deadline, rq_clock(rq)) &&
-	    dl_time_before(rq_clock(rq), dl_next_period(dl_se))) {
-		if (unlikely(dl_se->dl_boosted || !start_dl_timer(p)))
-			return;
-		dl_se->dl_throttled = 1;
+	/* we are in a new period */
+	if (dl_time_before(dl_next_period(dl_se), rq_clock(rq)))
+		return;
+
+	/* are we ok with the deadline and density? */
+	if (dl_time_before(rq_clock(rq), dl_se->deadline) &&
+	    !dl_entity_overflow(dl_se, dl_se, rq_clock(rq)))
+		return;
+
+	/* is the density the problem? */
+	if (dl_entity_overflow(dl_se, dl_se, clock)) {
+		/* reduces the runtime so it fits in the density */
+		dl_se->runtime =
+		  (div64_u64(dl_se->dl_runtime << 20, dl_se->dl_deadline) *
+		  (dl_se->deadline - clock)) >> 20;
+		WARN_ON(dl_se->runtime < 0);
+		return;
 	}
+
+	if (!start_dl_timer(p))
+		return;
+
+	dl_se->dl_throttled = 1;
 }
 
 static
@@ -996,8 +1000,11 @@ static void enqueue_task_dl(struct rq *rq, struct task_struct *p, int flags)
 	 * If that is the case, the task will be throttled and
 	 * the replenishment timer will be set to the next period.
 	 */
-	if (!dl_se->dl_throttled && dl_is_constrained(dl_se))
-		dl_check_constrained_dl(dl_se);
+	if (!p->dl.dl_boosted &&
+	    !p->dl.dl_throttled &&
+	    dl_is_constrained(&p->dl))
+		dl_check_constrained_dl(&p->dl);
+
 
 	/*
 	 * If p is throttled, we do nothing. In fact, if it exhausted
#3 lore raw
Quoted 42 lines · Xunlei Pang
Quoted 41 lines · Daniel Bristot de Oliveira
Quoted 24 lines · Xunlei Pang

I was testing Daniel's changes with his test case in the commit df8eac8cafce ("sched/deadline: Throttle a constrained deadline task activated after the deadline"), and tweaked it a little.

Instead of having the runtime equal to the deadline, I tweaked runtime, deadline and sleep value to ensure every time it calls dl_check_constrained_dl() with "dl_se->deadline > rq_clock(rq)" as well as true dl_entity_overflow(), so it does replenishing every wake up in update_dl_entity(), and break its bandwidth.

Daniel's test case had:
attr.sched_runtime = 2 * 1000 * 1000; /* 2 ms */ attr.sched_deadline = 2 * 1000 * 1000; /* 2 ms*/ attr.sched_period = 2 * 1000 * 1000 * 1000; /* 2 s */ ts.tv_sec = 0;
ts.tv_nsec = 2000 * 1000; /* 2 ms */

I changed it to:
attr.sched_runtime = 5 * 1000 * 1000; /* 5 ms */ attr.sched_deadline = 7 * 1000 * 1000; /* 7 ms */ attr.sched_period = 1 * 1000 * 1000 * 1000; /* 1 s */ ts.tv_sec = 0;
ts.tv_nsec = 1000 * 1000; /* 1 ms */

Quoted 5 lines

The change above can result in over 25% of the CPU on my machine.

In order to avoid the beakage, we improve dl_check_constrained_dl() to prevent dl tasks from being activated until the next period if it runs out of bandwidth of the current period.

The problem now is that, with your patch, we will throttle the task with some possible runtime. Moreover, the task did not brake any rule, like being awakened after the deadline - the user-space is not misbehaving.

That is +- what the reproducer is doing when using your patch, (I put some trace_printk when noticing the overflow in the wakeup).

          <idle>-0     [007] d.h.  1505.066439: enqueue_task_dl: my current runtime is 3657361 and the deadline is 4613027 from now 
          <idle>-0     [007] d.h.  1505.066439: enqueue_task_dl: 	my dl_runtime is 5000000
Quoted 7 lines
Quoted 5 lines

and so the task will be throttled with 3657361 ns runtime available.

As we can see, it is really breaking the density:

5ms / 7ms (.714285) < 3657361 / 4613027 (.792833)

For the runtime 5ms, deadline 7ms, 3657361 is the remaining runtime, so the actual runtime is (5000000 - 3657361) = 1342639, and the actual density is 1342639 / 7000000 (.191806),

The past density... we are not looking back here.

Quoted 5 lines

not break the limited density 5ms / 7ms (.714285).

"3657361 / 4613027 (.792833)" means available density greater than limited density(.714285), this means true dl_entity_overflow(), and can't meet the requirement in the current period any more, thus need to throttle it until next period.

This means that it has potential to break the rules, but it did not brake yet. It will break if it runs longer than:

(dl_runtime / dl_deadline) * (deadline - now)

By throttling the task too early, you will punish user-space, even if the user-space is not breaking the rules. I pointed a less pessimistic solution, but there are more possible solutions.

Actually, from the theoretical standing point this is an open issue, that is, the perfect solution is unknown for self-suspending constrained deadline tasks.

-- Daniel

#4 lore raw
In reply to Daniel Bristot de Oliveira
Quoted 45 lines · Daniel Bristot de Oliveira
Quoted 24 lines · Xunlei Pang

I was testing Daniel's changes with his test case in the commit df8eac8cafce ("sched/deadline: Throttle a constrained deadline task activated after the deadline"), and tweaked it a little.

Instead of having the runtime equal to the deadline, I tweaked runtime, deadline and sleep value to ensure every time it calls dl_check_constrained_dl() with "dl_se->deadline > rq_clock(rq)" as well as true dl_entity_overflow(), so it does replenishing every wake up in update_dl_entity(), and break its bandwidth.

Daniel's test case had:
attr.sched_runtime = 2 * 1000 * 1000; /* 2 ms */ attr.sched_deadline = 2 * 1000 * 1000; /* 2 ms*/ attr.sched_period = 2 * 1000 * 1000 * 1000; /* 2 s */ ts.tv_sec = 0;
ts.tv_nsec = 2000 * 1000; /* 2 ms */

I changed it to:
attr.sched_runtime = 5 * 1000 * 1000; /* 5 ms */ attr.sched_deadline = 7 * 1000 * 1000; /* 7 ms */ attr.sched_period = 1 * 1000 * 1000 * 1000; /* 1 s */ ts.tv_sec = 0;
ts.tv_nsec = 1000 * 1000; /* 1 ms */

Quoted 5 lines

The change above can result in over 25% of the CPU on my machine.

In order to avoid the beakage, we improve dl_check_constrained_dl() to prevent dl tasks from being activated until the next period if it runs out of bandwidth of the current period.

The problem now is that, with your patch, we will throttle the task with some possible runtime. Moreover, the task did not brake any rule, like being awakened after the deadline - the user-space is not misbehaving.

That is +- what the reproducer is doing when using your patch, (I put some trace_printk when noticing the overflow in the wakeup).

          <idle>-0     [007] d.h.  1505.066439: enqueue_task_dl: my current runtime is 3657361 and the deadline is 4613027 from now 
          <idle>-0     [007] d.h.  1505.066439: enqueue_task_dl: 	my dl_runtime is 5000000

and so the task will be throttled with 3657361 ns runtime available.

As we can see, it is really breaking the density:

Quoted 8 lines

5ms / 7ms (.714285) < 3657361 / 4613027 (.792833)

Well, it is not breaking that much. Trying to be less pessimist, we can compute a new runtime with following equation:

runtime = (dl_runtime / dl_deadline) * (deadline - now)

That is, a runtime which fits in the task's density.

This is a good point, to make the best use of remaining deadline, let me think more.

Regards,
Xunlei

Quoted 134 lines

In code:

dl_se->runtime = (div64_u64(dl_se->dl_runtime << 20, dl_se->dl_deadline) * (dl_se->deadline - rq_clock(rq))) >> 20;

For example (a trace_printk) showing the adjusted runtime for the previous task:

          <idle>-0     [007] d.h.  1505.066440: enqueue_task_dl: 	I can still run for 3294208 (it is not that bad)

With the adjusted runtime, we have the following density:

3294208 / 4613027 = .714109

as .714109 < .714285

Voilà. We can still use 3.2 ms of runtime! Not bad at all.

However, even this result is, somehow, controversial. Because we are reducing the task's reservation (Q/P). But that is very close to the implicit deadline behavior: when it "overflows", the runtime is truncated (a replenishment...) and the deadline is postponed. In this case, we do not need to postpone the deadline, just to "truncate" the runtime to fit in the density... it is not that bad.

Another possibility is not to replenish a constrained deadline task twice in a period. In this case, the task would run further the deadline, potentially causing problems for implicit deadline tasks. But! even implicit deadline would do it in a overloaded system. The problem is that, by using the density the system easily becomes overloaded (too pessimistic).

Resuming (so far):

1) We can be pessimistic to the constrained deadline task, with Xunlei's patch;
2) Compute a new runtime to fit in the density - somehow pessimistic.
3) Avoid replenishing a constrained deadline before the next period. but the system will become overload very easily (density).

I think the option 2 is the mid-term.
I am showing a _proof of concept_ patch bellow. I is based in the Xunlei's changes in the verification. I need to polish it... but... you guys can read the idea in C.

I have the 3) too, but I am not sure if it is as good as 2.

We still need to think more about the solution.... test more... I will continue working on this tomorrow, discussing with luca and tommaso as well.

Thoughts? Am I missing something (probably, I am tired :-) )?

---
 kernel/sched/deadline.c | 53 ++++++++++++++++++++++++++++---------------------
 1 file changed, 30 insertions(+), 23 deletions(-)
kernel/sched/deadline.c +30 -23
index 7508129..6fa4887 100644
@@ -696,34 +696,38 @@ void init_dl_task_timer(struct sched_dl_entity *dl_se)
 }
 
 /*
- * During the activation, CBS checks if it can reuse the current task's
- * runtime and period. If the deadline of the task is in the past, CBS
- * cannot use the runtime, and so it replenishes the task. This rule
- * works fine for implicit deadline tasks (deadline == period), and the
- * CBS was designed for implicit deadline tasks. However, a task with
- * constrained deadline (deadine < period) might be awakened after the
- * deadline, but before the next period. In this case, replenishing the
- * task would allow it to run for runtime / deadline. As in this case
- * deadline < period, CBS enables a task to run for more than the
- * runtime / period. In a very loaded system, this can cause a domino
- * effect, making other tasks miss their deadlines.
- *
- * To avoid this problem, in the activation of a constrained deadline
- * task after the deadline but before the next period, throttle the
- * task and set the replenishing timer to the begin of the next period,
- * unless it is boosted.
+ * XXX: Daniel will document it better in a clean patch, this is
+ * a proof of concept.
  */
 static inline void dl_check_constrained_dl(struct sched_dl_entity *dl_se)
 {
 	struct task_struct *p = dl_task_of(dl_se);
 	struct rq *rq = rq_of_dl_rq(dl_rq_of_se(dl_se));
+	u64 clock = rq_clock(rq);
 
-	if (dl_time_before(dl_se->deadline, rq_clock(rq)) &&
-	    dl_time_before(rq_clock(rq), dl_next_period(dl_se))) {
-		if (unlikely(dl_se->dl_boosted || !start_dl_timer(p)))
-			return;
-		dl_se->dl_throttled = 1;
+	/* we are in a new period */
+	if (dl_time_before(dl_next_period(dl_se), rq_clock(rq)))
+		return;
+
+	/* are we ok with the deadline and density? */
+	if (dl_time_before(rq_clock(rq), dl_se->deadline) &&
+	    !dl_entity_overflow(dl_se, dl_se, rq_clock(rq)))
+		return;
+
+	/* is the density the problem? */
+	if (dl_entity_overflow(dl_se, dl_se, clock)) {
+		/* reduces the runtime so it fits in the density */
+		dl_se->runtime =
+		  (div64_u64(dl_se->dl_runtime << 20, dl_se->dl_deadline) *
+		  (dl_se->deadline - clock)) >> 20;
+		WARN_ON(dl_se->runtime < 0);
+		return;
 	}
+
+	if (!start_dl_timer(p))
+		return;
+
+	dl_se->dl_throttled = 1;
 }
 
 static
@@ -996,8 +1000,11 @@ static void enqueue_task_dl(struct rq *rq, struct task_struct *p, int flags)
 	 * If that is the case, the task will be throttled and
 	 * the replenishment timer will be set to the next period.
 	 */
-	if (!dl_se->dl_throttled && dl_is_constrained(dl_se))
-		dl_check_constrained_dl(dl_se);
+	if (!p->dl.dl_boosted &&
+	    !p->dl.dl_throttled &&
+	    dl_is_constrained(&p->dl))
+		dl_check_constrained_dl(&p->dl);
+
 
 	/*
 	 * If p is throttled, we do nothing. In fact, if it exhausted
#5 lore raw
Quoted 48 lines · Xunlei Pang
Quoted 47 lines · Daniel Bristot de Oliveira
Quoted 24 lines · Xunlei Pang

I was testing Daniel's changes with his test case in the commit df8eac8cafce ("sched/deadline: Throttle a constrained deadline task activated after the deadline"), and tweaked it a little.

Instead of having the runtime equal to the deadline, I tweaked runtime, deadline and sleep value to ensure every time it calls dl_check_constrained_dl() with "dl_se->deadline > rq_clock(rq)" as well as true dl_entity_overflow(), so it does replenishing every wake up in update_dl_entity(), and break its bandwidth.

Daniel's test case had:
attr.sched_runtime = 2 * 1000 * 1000; /* 2 ms */ attr.sched_deadline = 2 * 1000 * 1000; /* 2 ms*/ attr.sched_period = 2 * 1000 * 1000 * 1000; /* 2 s */ ts.tv_sec = 0;
ts.tv_nsec = 2000 * 1000; /* 2 ms */

I changed it to:
attr.sched_runtime = 5 * 1000 * 1000; /* 5 ms */ attr.sched_deadline = 7 * 1000 * 1000; /* 7 ms */ attr.sched_period = 1 * 1000 * 1000 * 1000; /* 1 s */ ts.tv_sec = 0;
ts.tv_nsec = 1000 * 1000; /* 1 ms */

Quoted 5 lines

The change above can result in over 25% of the CPU on my machine.

In order to avoid the beakage, we improve dl_check_constrained_dl() to prevent dl tasks from being activated until the next period if it runs out of bandwidth of the current period.

The problem now is that, with your patch, we will throttle the task with some possible runtime. Moreover, the task did not brake any rule, like being awakened after the deadline - the user-space is not misbehaving.

That is +- what the reproducer is doing when using your patch, (I put some trace_printk when noticing the overflow in the wakeup).

          <idle>-0     [007] d.h.  1505.066439: enqueue_task_dl: my current runtime is 3657361 and the deadline is 4613027 from now 
          <idle>-0     [007] d.h.  1505.066439: enqueue_task_dl: 	my dl_runtime is 5000000

and so the task will be throttled with 3657361 ns runtime available.

As we can see, it is really breaking the density:

5ms / 7ms (.714285) < 3657361 / 4613027 (.792833)

Quoted 7 lines
Quoted 6 lines

Well, it is not breaking that much. Trying to be less pessimist, we can compute a new runtime with following equation:

runtime = (dl_runtime / dl_deadline) * (deadline - now)

That is, a runtime which fits in the task's density.

This is a good point, to make the best use of remaining deadline, let me think more.

I don't know if this will make things more complicated, we can see in update_dl_entity():
if (dl_time_before(dl_se->deadline, rq_clock(rq)) ||

        dl_entity_overflow(dl_se, pi_se, rq_clock(rq))) {
        dl_se->deadline = rq_clock(rq) + pi_se->dl_deadline;
        dl_se->runtime = pi_se->dl_runtime;
    }

Looks like we have similar issue for non-constrained tasks in case of true dl_entity_overflow(), althought its deadline is promoted(BTW, I think when overflow it should be dl_se->deadline += pi_se->dl_deadline?), the previous runtime is discarded, we may need to apply the same runtime truncating logic on it as well if we want to truncate runtime.

Regards,
Xunlei

Quoted 133 lines
Quoted 133 lines

In code:

dl_se->runtime = (div64_u64(dl_se->dl_runtime << 20, dl_se->dl_deadline) * (dl_se->deadline - rq_clock(rq))) >> 20;

For example (a trace_printk) showing the adjusted runtime for the previous task:

          <idle>-0     [007] d.h.  1505.066440: enqueue_task_dl: 	I can still run for 3294208 (it is not that bad)

With the adjusted runtime, we have the following density:

3294208 / 4613027 = .714109

as .714109 < .714285

Voilà. We can still use 3.2 ms of runtime! Not bad at all.

However, even this result is, somehow, controversial. Because we are reducing the task's reservation (Q/P). But that is very close to the implicit deadline behavior: when it "overflows", the runtime is truncated (a replenishment...) and the deadline is postponed. In this case, we do not need to postpone the deadline, just to "truncate" the runtime to fit in the density... it is not that bad.

Another possibility is not to replenish a constrained deadline task twice in a period. In this case, the task would run further the deadline, potentially causing problems for implicit deadline tasks. But! even implicit deadline would do it in a overloaded system. The problem is that, by using the density the system easily becomes overloaded (too pessimistic).

Resuming (so far):

1) We can be pessimistic to the constrained deadline task, with Xunlei's patch;
2) Compute a new runtime to fit in the density - somehow pessimistic.
3) Avoid replenishing a constrained deadline before the next period. but the system will become overload very easily (density).

I think the option 2 is the mid-term.
I am showing a _proof of concept_ patch bellow. I is based in the Xunlei's changes in the verification. I need to polish it... but... you guys can read the idea in C.

I have the 3) too, but I am not sure if it is as good as 2.

We still need to think more about the solution.... test more... I will continue working on this tomorrow, discussing with luca and tommaso as well.

Thoughts? Am I missing something (probably, I am tired :-) )?

---
 kernel/sched/deadline.c | 53 ++++++++++++++++++++++++++++---------------------
 1 file changed, 30 insertions(+), 23 deletions(-)
kernel/sched/deadline.c +30 -23
index 7508129..6fa4887 100644
@@ -696,34 +696,38 @@ void init_dl_task_timer(struct sched_dl_entity *dl_se)
 }
 
 /*
- * During the activation, CBS checks if it can reuse the current task's
- * runtime and period. If the deadline of the task is in the past, CBS
- * cannot use the runtime, and so it replenishes the task. This rule
- * works fine for implicit deadline tasks (deadline == period), and the
- * CBS was designed for implicit deadline tasks. However, a task with
- * constrained deadline (deadine < period) might be awakened after the
- * deadline, but before the next period. In this case, replenishing the
- * task would allow it to run for runtime / deadline. As in this case
- * deadline < period, CBS enables a task to run for more than the
- * runtime / period. In a very loaded system, this can cause a domino
- * effect, making other tasks miss their deadlines.
- *
- * To avoid this problem, in the activation of a constrained deadline
- * task after the deadline but before the next period, throttle the
- * task and set the replenishing timer to the begin of the next period,
- * unless it is boosted.
+ * XXX: Daniel will document it better in a clean patch, this is
+ * a proof of concept.
  */
 static inline void dl_check_constrained_dl(struct sched_dl_entity *dl_se)
 {
 	struct task_struct *p = dl_task_of(dl_se);
 	struct rq *rq = rq_of_dl_rq(dl_rq_of_se(dl_se));
+	u64 clock = rq_clock(rq);
 
-	if (dl_time_before(dl_se->deadline, rq_clock(rq)) &&
-	    dl_time_before(rq_clock(rq), dl_next_period(dl_se))) {
-		if (unlikely(dl_se->dl_boosted || !start_dl_timer(p)))
-			return;
-		dl_se->dl_throttled = 1;
+	/* we are in a new period */
+	if (dl_time_before(dl_next_period(dl_se), rq_clock(rq)))
+		return;
+
+	/* are we ok with the deadline and density? */
+	if (dl_time_before(rq_clock(rq), dl_se->deadline) &&
+	    !dl_entity_overflow(dl_se, dl_se, rq_clock(rq)))
+		return;
+
+	/* is the density the problem? */
+	if (dl_entity_overflow(dl_se, dl_se, clock)) {
+		/* reduces the runtime so it fits in the density */
+		dl_se->runtime =
+		  (div64_u64(dl_se->dl_runtime << 20, dl_se->dl_deadline) *
+		  (dl_se->deadline - clock)) >> 20;
+		WARN_ON(dl_se->runtime < 0);
+		return;
 	}
+
+	if (!start_dl_timer(p))
+		return;
+
+	dl_se->dl_throttled = 1;
 }
 
 static
@@ -996,8 +1000,11 @@ static void enqueue_task_dl(struct rq *rq, struct task_struct *p, int flags)
 	 * If that is the case, the task will be throttled and
 	 * the replenishment timer will be set to the next period.
 	 */
-	if (!dl_se->dl_throttled && dl_is_constrained(dl_se))
-		dl_check_constrained_dl(dl_se);
+	if (!p->dl.dl_boosted &&
+	    !p->dl.dl_throttled &&
+	    dl_is_constrained(&p->dl))
+		dl_check_constrained_dl(&p->dl);
+
 
 	/*
 	 * If p is throttled, we do nothing. In fact, if it exhausted
#6 lore raw
Quoted 63 lines · Xunlei Pang
Quoted 48 lines · Xunlei Pang
Quoted 47 lines · Daniel Bristot de Oliveira
Quoted 24 lines · Xunlei Pang

I was testing Daniel's changes with his test case in the commit df8eac8cafce ("sched/deadline: Throttle a constrained deadline task activated after the deadline"), and tweaked it a little.

Instead of having the runtime equal to the deadline, I tweaked runtime, deadline and sleep value to ensure every time it calls dl_check_constrained_dl() with "dl_se->deadline > rq_clock(rq)" as well as true dl_entity_overflow(), so it does replenishing every wake up in update_dl_entity(), and break its bandwidth.

Daniel's test case had:
attr.sched_runtime = 2 * 1000 * 1000; /* 2 ms */ attr.sched_deadline = 2 * 1000 * 1000; /* 2 ms*/ attr.sched_period = 2 * 1000 * 1000 * 1000; /* 2 s */ ts.tv_sec = 0;
ts.tv_nsec = 2000 * 1000; /* 2 ms */

I changed it to:
attr.sched_runtime = 5 * 1000 * 1000; /* 5 ms */ attr.sched_deadline = 7 * 1000 * 1000; /* 7 ms */ attr.sched_period = 1 * 1000 * 1000 * 1000; /* 1 s */ ts.tv_sec = 0;
ts.tv_nsec = 1000 * 1000; /* 1 ms */

Quoted 5 lines

The change above can result in over 25% of the CPU on my machine.

In order to avoid the beakage, we improve dl_check_constrained_dl() to prevent dl tasks from being activated until the next period if it runs out of bandwidth of the current period.

The problem now is that, with your patch, we will throttle the task with some possible runtime. Moreover, the task did not brake any rule, like being awakened after the deadline - the user-space is not misbehaving.

That is +- what the reproducer is doing when using your patch, (I put some trace_printk when noticing the overflow in the wakeup).

          <idle>-0     [007] d.h.  1505.066439: enqueue_task_dl: my current runtime is 3657361 and the deadline is 4613027 from now 
          <idle>-0     [007] d.h.  1505.066439: enqueue_task_dl: 	my dl_runtime is 5000000

and so the task will be throttled with 3657361 ns runtime available.

As we can see, it is really breaking the density:

5ms / 7ms (.714285) < 3657361 / 4613027 (.792833)

Quoted 7 lines
Quoted 6 lines

Well, it is not breaking that much. Trying to be less pessimist, we can compute a new runtime with following equation:

runtime = (dl_runtime / dl_deadline) * (deadline - now)

That is, a runtime which fits in the task's density.

This is a good point, to make the best use of remaining deadline, let me think more.

I don't know if this will make things more complicated, we can see in update_dl_entity():

   if (dl_time_before(dl_se->deadline, rq_clock(rq)) ||
        dl_entity_overflow(dl_se, pi_se, rq_clock(rq))) {
        dl_se->deadline = rq_clock(rq) + pi_se->dl_deadline;
        dl_se->runtime = pi_se->dl_runtime;
    }
Quoted 4 lines

Looks like we have similar issue for non-constrained tasks in case of true dl_entity_overflow(), although its deadline is promoted(BTW, I think when overflow it should be dl_se->deadline += pi_se->dl_deadline?), the previous runtime is discarded, we may need to apply the same runtime truncating logic on it as well if we want to truncate runtime.

For implicit deadline, the density is equals to the utilization. So things here are less pessimistic, and we are using the same rule for overflow and admission.

If you push "dl_se->deadline += pi_se->dl_deadline", you will give

runtime / (deadline - now) + period.

runtime.

As the deadline is in the future, (the !dl_time_before(dl_se->deadline, rq_clock(rq)), then (deadline - now) + period > period. Therefore, the next period will receive less than runtime / period & the task will receive a lower priority - a farther deadline.

Well, we could not to truncate the runtime, but than we would carry things from the past. If the task self-suspended for a long period, the sum of the residual runtime + runtime could give a higher utilization than Q/P.

Moreover, the current rule provides a guarantee that Tommaso likes. The CBS self-adjusts the period in the case of a timing drift of the external "event" that activates the task, without breaking Q/P.

(He can explain more about it....)

The current rule guarantees Q/P, that is the well known CBS.

Am I missing something?

-- Daniel

#7 lore raw
Quoted 74 lines · Daniel Bristot de Oliveira
Quoted 63 lines · Xunlei Pang
Quoted 48 lines · Xunlei Pang
Quoted 47 lines · Daniel Bristot de Oliveira
Quoted 24 lines · Xunlei Pang

I was testing Daniel's changes with his test case in the commit df8eac8cafce ("sched/deadline: Throttle a constrained deadline task activated after the deadline"), and tweaked it a little.

Instead of having the runtime equal to the deadline, I tweaked runtime, deadline and sleep value to ensure every time it calls dl_check_constrained_dl() with "dl_se->deadline > rq_clock(rq)" as well as true dl_entity_overflow(), so it does replenishing every wake up in update_dl_entity(), and break its bandwidth.

Daniel's test case had:
attr.sched_runtime = 2 * 1000 * 1000; /* 2 ms */ attr.sched_deadline = 2 * 1000 * 1000; /* 2 ms*/ attr.sched_period = 2 * 1000 * 1000 * 1000; /* 2 s */ ts.tv_sec = 0;
ts.tv_nsec = 2000 * 1000; /* 2 ms */

I changed it to:
attr.sched_runtime = 5 * 1000 * 1000; /* 5 ms */ attr.sched_deadline = 7 * 1000 * 1000; /* 7 ms */ attr.sched_period = 1 * 1000 * 1000 * 1000; /* 1 s */ ts.tv_sec = 0;
ts.tv_nsec = 1000 * 1000; /* 1 ms */

Quoted 5 lines

The change above can result in over 25% of the CPU on my machine.

In order to avoid the beakage, we improve dl_check_constrained_dl() to prevent dl tasks from being activated until the next period if it runs out of bandwidth of the current period.

The problem now is that, with your patch, we will throttle the task with some possible runtime. Moreover, the task did not brake any rule, like being awakened after the deadline - the user-space is not misbehaving.

That is +- what the reproducer is doing when using your patch, (I put some trace_printk when noticing the overflow in the wakeup).

          <idle>-0     [007] d.h.  1505.066439: enqueue_task_dl: my current runtime is 3657361 and the deadline is 4613027 from now 
          <idle>-0     [007] d.h.  1505.066439: enqueue_task_dl: 	my dl_runtime is 5000000

and so the task will be throttled with 3657361 ns runtime available.

As we can see, it is really breaking the density:

5ms / 7ms (.714285) < 3657361 / 4613027 (.792833)

Quoted 7 lines
Quoted 6 lines

Well, it is not breaking that much. Trying to be less pessimist, we can compute a new runtime with following equation:

runtime = (dl_runtime / dl_deadline) * (deadline - now)

That is, a runtime which fits in the task's density.

This is a good point, to make the best use of remaining deadline, let me think more.

I don't know if this will make things more complicated, we can see in update_dl_entity():

   if (dl_time_before(dl_se->deadline, rq_clock(rq)) ||
        dl_entity_overflow(dl_se, pi_se, rq_clock(rq))) {
        dl_se->deadline = rq_clock(rq) + pi_se->dl_deadline;
        dl_se->runtime = pi_se->dl_runtime;
    }
Quoted 4 lines

Looks like we have similar issue for non-constrained tasks in case of true dl_entity_overflow(), although its deadline is promoted(BTW, I think when overflow it should be dl_se->deadline += pi_se->dl_deadline?), the previous runtime is discarded, we may need to apply the same runtime truncating logic on it as well if we want to truncate runtime.

For implicit deadline, the density is equals to the utilization. So things here are less pessimistic, and we are using the same rule for overflow and admission.

If you push "dl_se->deadline += pi_se->dl_deadline", you will give

Quoted 8 lines

runtime / (deadline - now) + period.

runtime.

As the deadline is in the future, (the !dl_time_before(dl_se->deadline, rq_clock(rq)), then (deadline - now) + period > period. Therefore, the next period will receive less than runtime / period & the task will receive a lower priority - a farther deadline.

Yes, I think I got your meaning, thanks for the detailed explanation. This is indeed an issue, that's why I suggested to do truncate here as well.

But in the current implementation, promote deadline to "clock + pi_se->dl_deadline", will cause overlapping between periods, kind of like
[ period n ]
[ period n+1 ]
the overlapped time window is (deadline -now), is this a problem?

Quoted 11 lines

Well, we could not to truncate the runtime, but than we would carry things from the past. If the task self-suspended for a long period, the sum of the residual runtime + runtime could give a higher utilization than Q/P.

Moreover, the current rule provides a guarantee that Tommaso likes. The CBS self-adjusts the period in the case of a timing drift of the external "event" that activates the task, without breaking Q/P.

(He can explain more about it....)

Anyway implicit deadline has the same issue, image in update_dl_entity() when "deadline > rq_clock" and true dl_entity_overflow(), it can run part of dl_se->runtime within (dl_se->deadline - rq_clock), no? what do you think we truncate runtime in the common update_dl_entity()? Like:

kernel/sched/deadline.c +13 -3
index a2ce590..e92aad6 100644
@@ -497,11 +497,21 @@ static void update_dl_entity(struct sched_dl_entity *dl_se,
 {
        struct dl_rq *dl_rq = dl_rq_of_se(dl_se);
        struct rq *rq = rq_of_dl_rq(dl_rq);
+       u64 clock = rq_clock(rq);
 
-       if (dl_time_before(dl_se->deadline, rq_clock(rq)) ||
-           dl_entity_overflow(dl_se, pi_se, rq_clock(rq))) {
-               dl_se->deadline = rq_clock(rq) + pi_se->dl_deadline;
+       if (!dl_time_before(clock, dl_se->deadline)) {
+               dl_se->deadline = clock + pi_se->dl_deadline;
                dl_se->runtime = pi_se->dl_runtime;
+               return;
+       }
+
+       /* Truncate the runtime to fit the density in the current period after overflow. */
+       if (dl_entity_overflow(dl_se, pi_se, clock)) {
+               unsigned long ratio;
+
+               /* TODO: save the quotient in a variable like dl_se->dl_bw */
+               ratio = to_ratio(pi_se->dl_deadline, pi_se->dl_runtime);
+               dl_se->runtime = (ratio * (dl_se->deadline - clock)) >> 20;
        }
 }
#8 lore raw
In reply to Daniel Bristot de Oliveira
Quoted 152 lines · Daniel Bristot de Oliveira
Quoted 24 lines · Xunlei Pang

I was testing Daniel's changes with his test case in the commit df8eac8cafce ("sched/deadline: Throttle a constrained deadline task activated after the deadline"), and tweaked it a little.

Instead of having the runtime equal to the deadline, I tweaked runtime, deadline and sleep value to ensure every time it calls dl_check_constrained_dl() with "dl_se->deadline > rq_clock(rq)" as well as true dl_entity_overflow(), so it does replenishing every wake up in update_dl_entity(), and break its bandwidth.

Daniel's test case had:
attr.sched_runtime = 2 * 1000 * 1000; /* 2 ms */ attr.sched_deadline = 2 * 1000 * 1000; /* 2 ms*/ attr.sched_period = 2 * 1000 * 1000 * 1000; /* 2 s */ ts.tv_sec = 0;
ts.tv_nsec = 2000 * 1000; /* 2 ms */

I changed it to:
attr.sched_runtime = 5 * 1000 * 1000; /* 5 ms */ attr.sched_deadline = 7 * 1000 * 1000; /* 7 ms */ attr.sched_period = 1 * 1000 * 1000 * 1000; /* 1 s */ ts.tv_sec = 0;
ts.tv_nsec = 1000 * 1000; /* 1 ms */

Quoted 5 lines

The change above can result in over 25% of the CPU on my machine.

In order to avoid the beakage, we improve dl_check_constrained_dl() to prevent dl tasks from being activated until the next period if it runs out of bandwidth of the current period.

The problem now is that, with your patch, we will throttle the task with some possible runtime. Moreover, the task did not brake any rule, like being awakened after the deadline - the user-space is not misbehaving.

That is +- what the reproducer is doing when using your patch, (I put some trace_printk when noticing the overflow in the wakeup).

          <idle>-0     [007] d.h.  1505.066439: enqueue_task_dl: my current runtime is 3657361 and the deadline is 4613027 from now 
          <idle>-0     [007] d.h.  1505.066439: enqueue_task_dl: 	my dl_runtime is 5000000

and so the task will be throttled with 3657361 ns runtime available.

As we can see, it is really breaking the density:

5ms / 7ms (.714285) < 3657361 / 4613027 (.792833)

Well, it is not breaking that much. Trying to be less pessimist, we can compute a new runtime with following equation:

runtime = (dl_runtime / dl_deadline) * (deadline - now)

That is, a runtime which fits in the task's density.

In code:

dl_se->runtime = (div64_u64(dl_se->dl_runtime << 20, dl_se->dl_deadline) * (dl_se->deadline - rq_clock(rq))) >> 20;

For example (a trace_printk) showing the adjusted runtime for the previous task:

          <idle>-0     [007] d.h.  1505.066440: enqueue_task_dl: 	I can still run for 3294208 (it is not that bad)

With the adjusted runtime, we have the following density:

3294208 / 4613027 = .714109

as .714109 < .714285

Voilà. We can still use 3.2 ms of runtime! Not bad at all.

However, even this result is, somehow, controversial. Because we are reducing the task's reservation (Q/P). But that is very close to the implicit deadline behavior: when it "overflows", the runtime is truncated (a replenishment...) and the deadline is postponed. In this case, we do not need to postpone the deadline, just to "truncate" the runtime to fit in the density... it is not that bad.

Another possibility is not to replenish a constrained deadline task twice in a period. In this case, the task would run further the deadline, potentially causing problems for implicit deadline tasks. But! even implicit deadline would do it in a overloaded system. The problem is that, by using the density the system easily becomes overloaded (too pessimistic).

Resuming (so far):

1) We can be pessimistic to the constrained deadline task, with Xunlei's patch;
2) Compute a new runtime to fit in the density - somehow pessimistic.
3) Avoid replenishing a constrained deadline before the next period. but the system will become overload very easily (density).

I think the option 2 is the mid-term.
I am showing a _proof of concept_ patch bellow. I is based in the Xunlei's changes in the verification. I need to polish it... but... you guys can read the idea in C.

I have the 3) too, but I am not sure if it is as good as 2.

We still need to think more about the solution.... test more... I will continue working on this tomorrow, discussing with luca and tommaso as well.

Thoughts? Am I missing something (probably, I am tired :-) )?

---
 kernel/sched/deadline.c | 53 ++++++++++++++++++++++++++++---------------------
 1 file changed, 30 insertions(+), 23 deletions(-)
kernel/sched/deadline.c +8 -21
index 7508129..6fa4887 100644
@@ -696,34 +696,38 @@ void init_dl_task_timer(struct sched_dl_entity *dl_se)
 }
 
 /*
- * During the activation, CBS checks if it can reuse the current task's
- * runtime and period. If the deadline of the task is in the past, CBS
- * cannot use the runtime, and so it replenishes the task. This rule
- * works fine for implicit deadline tasks (deadline == period), and the
- * CBS was designed for implicit deadline tasks. However, a task with
- * constrained deadline (deadine < period) might be awakened after the
- * deadline, but before the next period. In this case, replenishing the
- * task would allow it to run for runtime / deadline. As in this case
- * deadline < period, CBS enables a task to run for more than the
- * runtime / period. In a very loaded system, this can cause a domino
- * effect, making other tasks miss their deadlines.
- *
- * To avoid this problem, in the activation of a constrained deadline
- * task after the deadline but before the next period, throttle the
- * task and set the replenishing timer to the begin of the next period,
- * unless it is boosted.
+ * XXX: Daniel will document it better in a clean patch, this is
+ * a proof of concept.
  */
 static inline void dl_check_constrained_dl(struct sched_dl_entity *dl_se)
 {
 	struct task_struct *p = dl_task_of(dl_se);
 	struct rq *rq = rq_of_dl_rq(dl_rq_of_se(dl_se));
+	u64 clock = rq_clock(rq);
 
-	if (dl_time_before(dl_se->deadline, rq_clock(rq)) &&
-	    dl_time_before(rq_clock(rq), dl_next_period(dl_se))) {
-		if (unlikely(dl_se->dl_boosted || !start_dl_timer(p)))
-			return;
-		dl_se->dl_throttled = 1;
+	/* we are in a new period */
+	if (dl_time_before(dl_next_period(dl_se), rq_clock(rq)))
+		return;
+
+	/* are we ok with the deadline and density? */

kernel/sched/deadline.c void init_dl_task_timer(struct sched_dl_entity *dl_se) · line 722

Quoted 10 lines
kernel/sched/deadline.c +10 -0
+	if (dl_time_before(rq_clock(rq), dl_se->deadline) &&
+	    !dl_entity_overflow(dl_se, dl_se, rq_clock(rq)))
+		return;
+
+	/* is the density the problem? */
+	if (dl_entity_overflow(dl_se, dl_se, clock)) {
+		/* reduces the runtime so it fits in the density */
+		dl_se->runtime =
+		  (div64_u64(dl_se->dl_runtime << 20, dl_se->dl_deadline) *
+		  (dl_se->deadline - clock)) >> 20;

The more I read the code, the more I am confused why dl_entity_overflow() is needed, if the task is before its deadline, just let it run. E.g. For (runtime 2ms, deadline 4ms, period 8ms), for some reason was preempted after running a very short time 0.1ms, after 0.9ms it was scheduled back and immediately sleep 1ms, when it is awakened, remaining runtime is 1.9ms, remaining deadline(deadline-now) within this period is 2ms, but dl_entity_overflow() is true. However, clearly it can be correctly run 1.9ms before deadline comes wthin this period.

We can add a condition in dl_runtime_exceeded(), if its deadline is passed, then zero its runtime if positive, and a new period begins.

I did some tests with the following patch, seems it works well, please correct me if I am wrong.

---
 kernel/sched/deadline.c | 16 ++++++++++++----
 1 file changed, 12 insertions(+), 4 deletions(-)
kernel/sched/deadline.c +12 -4
index a2ce590..600c530 100644
@@ -498,8 +498,7 @@ static void update_dl_entity(struct sched_dl_entity *dl_se,
     struct dl_rq *dl_rq = dl_rq_of_se(dl_se);
     struct rq *rq = rq_of_dl_rq(dl_rq);
 
-    if (dl_time_before(dl_se->deadline, rq_clock(rq)) ||
-        dl_entity_overflow(dl_se, pi_se, rq_clock(rq))) {
+    if (!dl_time_before(rq_clock(rq), dl_se->deadline)) {
         dl_se->deadline = rq_clock(rq) + pi_se->dl_deadline;
         dl_se->runtime = pi_se->dl_runtime;
     }
@@ -722,13 +721,22 @@ static inline void dl_check_constrained_dl(struct sched_dl_entity *dl_se)
         dl_time_before(rq_clock(rq), dl_next_period(dl_se))) {
         if (unlikely(dl_se->dl_boosted || !start_dl_timer(p)))
             return;
+
+        if (dl_se->runtime > 0)
+            dl_se->runtime = 0;
+
         dl_se->dl_throttled = 1;
     }
 }
 
 static
-int dl_runtime_exceeded(struct sched_dl_entity *dl_se)
+int dl_runtime_exceeded(struct rq *rq, struct sched_dl_entity *dl_se)
 {
+    if (!dl_time_before(rq_clock(rq), dl_se->deadline)) {
+        if (dl_se->runtime > 0)
+            dl_se->runtime = 0;
+    }
+
     return (dl_se->runtime <= 0);
 }
 
@@ -779,7 +787,7 @@ static void update_curr_dl(struct rq *rq)
     dl_se->runtime -= delta_exec;
 
 throttle:
-    if (dl_runtime_exceeded(dl_se) || dl_se->dl_yielded) {
+    if (dl_runtime_exceeded(rq, dl_se) || dl_se->dl_yielded) {
         dl_se->dl_throttled = 1;
         __dequeue_task_dl(rq, curr, 0);
         if (unlikely(dl_se->dl_boosted || !start_dl_timer(curr)))
Signature · 1 line
1.8.3.1
#9 lore raw

Hi,

On Wed, 12 Apr 2017 13:27:32 +0800
Xunlei Pang <[email protected]> wrote:
[...]

Quoted 3 lines

The more I read the code, the more I am confused why dl_entity_overflow() is needed, if the task is before its deadline, just let it run.

Sorry for jumping in this thread; I did not read all of the previous emails, but I think I can answer this question :)

dl_entity_overflow() is needed to check if a deadline task that is waking up can use its current runtime and scheduling deadline without breaking the guarantees for other deadline tasks.

If the relative deadline of the tasks is equal to their period, this check is mathematically correct (and its correctness has been formally proved in some papers - see for example
http://disi.unitn.it/~abeni/tr-98-01.pdf).

If the relative deadline is different from the period, then the check is an approximation (and this is the big issue here). I am still not sure about what is the best thing to do in this case.

Quoted 7 lines

E.g. For (runtime 2ms, deadline 4ms, period 8ms),
for some reason was preempted after running a very short time 0.1ms, after 0.9ms it was scheduled back and immediately sleep 1ms, when it is awakened, remaining runtime is 1.9ms, remaining deadline(deadline-now) within this period is 2ms, but dl_entity_overflow() is true. However, clearly it can be correctly run 1.9ms before deadline comes wthin this period.

Sure, in this case the task can run for 1.9ms before the deadline... But doing so, it might break the guarantees for other deadline tasks. This is what the check is trying to avoid.

Quoted 14 lines

We can add a condition in dl_runtime_exceeded(), if its deadline is passed, then zero its runtime if positive, and a new period begins.

I did some tests with the following patch, seems it works well, please correct me if I am wrong. ---

 kernel/sched/deadline.c | 16 ++++++++++++----
 1 file changed, 12 insertions(+), 4 deletions(-)
kernel/sched/deadline.c +0 -0
index a2ce590..600c530 100644

kernel/sched/deadline.c static void update_dl_entity(struct · line 504

Quoted 9 lines
kernel/sched/deadline.c +1 -2
@@ -498,8 +498,7 @@ static void update_dl_entity(struct
 sched_dl_entity *dl_se, struct dl_rq *dl_rq = dl_rq_of_se(dl_se);
     struct rq *rq = rq_of_dl_rq(dl_rq);
 
-    if (dl_time_before(dl_se->deadline, rq_clock(rq)) ||
-        dl_entity_overflow(dl_se, pi_se, rq_clock(rq))) {
+    if (!dl_time_before(rq_clock(rq), dl_se->deadline)) {
         dl_se->deadline = rq_clock(rq) + pi_se->dl_deadline;
         dl_se->runtime = pi_se->dl_runtime;
     }

I think this will break the guarantees for tasks with relative deadline equal to period (think about a task with runtime 5ms, period 10ms and relative deadline 10ms... What happens if the task executes for 4.9ms, then blocks and immediately wakes up?)

Luca

Quoted 33 lines
kernel/sched/deadline.c +0 -0
@@ -722,13 +721,22 @@ static inline void
 dl_check_constrained_dl(struct sched_dl_entity *dl_se)

dl_time_before(rq_clock(rq), dl_next_period(dl_se))) { if (unlikely(dl_se->dl_boosted || !start_dl_timer(p))) return;

kernel/sched/deadline.c +11 -2
+
+        if (dl_se->runtime > 0)
+            dl_se->runtime = 0;
+
         dl_se->dl_throttled = 1;
     }
 }
 
 static
-int dl_runtime_exceeded(struct sched_dl_entity *dl_se)
+int dl_runtime_exceeded(struct rq *rq, struct sched_dl_entity *dl_se)
 {
+    if (!dl_time_before(rq_clock(rq), dl_se->deadline)) {
+        if (dl_se->runtime > 0)
+            dl_se->runtime = 0;
+    }
+
     return (dl_se->runtime <= 0);
 }
@@ -779,7 +787,7 @@ static void update_curr_dl(struct rq *rq)
     dl_se->runtime -= delta_exec;
 
 throttle:
-    if (dl_runtime_exceeded(dl_se) || dl_se->dl_yielded) {
+    if (dl_runtime_exceeded(rq, dl_se) || dl_se->dl_yielded) {
         dl_se->dl_throttled = 1;
         __dequeue_task_dl(rq, curr, 0);
         if (unlikely(dl_se->dl_boosted || !start_dl_timer(curr)))
#10 lore raw
Quoted 11 lines · Luca Abeni

Hi,

On Wed, 12 Apr 2017 13:27:32 +0800
Xunlei Pang <[email protected]> wrote:
[...]

Quoted 3 lines

The more I read the code, the more I am confused why dl_entity_overflow() is needed, if the task is before its deadline, just let it run.

Sorry for jumping in this thread; I did not read all of the previous emails, but I think I can answer this question :)

Quoted 8 lines

dl_entity_overflow() is needed to check if a deadline task that is waking up can use its current runtime and scheduling deadline without breaking the guarantees for other deadline tasks.

If the relative deadline of the tasks is equal to their period, this check is mathematically correct (and its correctness has been formally proved in some papers - see for example
http://disi.unitn.it/~abeni/tr-98-01.pdf).

Will have a look, thanks for the pointer.

Quoted 11 lines

If the relative deadline is different from the period, then the check is an approximation (and this is the big issue here). I am still not sure about what is the best thing to do in this case.

Quoted 7 lines

E.g. For (runtime 2ms, deadline 4ms, period 8ms),
for some reason was preempted after running a very short time 0.1ms, after 0.9ms it was scheduled back and immediately sleep 1ms, when it is awakened, remaining runtime is 1.9ms, remaining deadline(deadline-now) within this period is 2ms, but dl_entity_overflow() is true. However, clearly it can be correctly run 1.9ms before deadline comes wthin this period.

Quoted 3 lines

Sure, in this case the task can run for 1.9ms before the deadline... But doing so, it might break the guarantees for other deadline tasks. This is what the check is trying to avoid.

Image this deadline task was preempted after running 0.1ms by another one with an earlier absolute deadline for 1.9ms, after scheduled back it will have the same status (1.9ms remaining runtime, 2ms remaining deadline) under the current implementation.

I can hardly figure out the difference, why is wake-up(will check dl_entity_overflow()) so special?

Quoted 17 lines
Quoted 17 lines

We can add a condition in dl_runtime_exceeded(), if its deadline is passed, then zero its runtime if positive, and a new period begins.

I did some tests with the following patch, seems it works well, please correct me if I am wrong. ---

 kernel/sched/deadline.c | 16 ++++++++++++----
 1 file changed, 12 insertions(+), 4 deletions(-)
kernel/sched/deadline.c +0 -0
index a2ce590..600c530 100644
@@ -498,8 +498,7 @@ static void update_dl_entity(struct
 sched_dl_entity *dl_se, struct dl_rq *dl_rq = dl_rq_of_se(dl_se);
     struct rq *rq = rq_of_dl_rq(dl_rq);
 
Quoted 10 lines

kernel/sched/deadline.c static void update_dl_entity(struct sched_dl_entity *dl_se, · line 504

Quoted 6 lines
kernel/sched/deadline.c +1 -2
-    if (dl_time_before(dl_se->deadline, rq_clock(rq)) ||
-        dl_entity_overflow(dl_se, pi_se, rq_clock(rq))) {
+    if (!dl_time_before(rq_clock(rq), dl_se->deadline)) {
         dl_se->deadline = rq_clock(rq) + pi_se->dl_deadline;
         dl_se->runtime = pi_se->dl_runtime;
     }

I think this will break the guarantees for tasks with relative deadline equal to period (think about a task with runtime 5ms, period 10ms and relative deadline 10ms... What happens if the task executes for 4.9ms, then blocks and immediately wakes up?)

For your example, dl_se->deadline is after now, the if condition is false, update_dl_entity() actually does nothing, that is, after wake-up, it will carry (5ms-4.9ms)=0.1ms remaining runtime and (10ms-4.9ms)=5.1ms remaining deadline/period, continue within the current period. After running further 0.1ms, will be throttled by the timer in update_curr_dl().

It's actually the original logic, I just removed dl_entity_overflow() condition.

Regards,
Xunlei

Quoted 37 lines

Luca

Quoted 33 lines
kernel/sched/deadline.c +0 -0
@@ -722,13 +721,22 @@ static inline void
 dl_check_constrained_dl(struct sched_dl_entity *dl_se)

dl_time_before(rq_clock(rq), dl_next_period(dl_se))) { if (unlikely(dl_se->dl_boosted || !start_dl_timer(p))) return;

kernel/sched/deadline.c +11 -2
+
+        if (dl_se->runtime > 0)
+            dl_se->runtime = 0;
+
         dl_se->dl_throttled = 1;
     }
 }
 
 static
-int dl_runtime_exceeded(struct sched_dl_entity *dl_se)
+int dl_runtime_exceeded(struct rq *rq, struct sched_dl_entity *dl_se)
 {
+    if (!dl_time_before(rq_clock(rq), dl_se->deadline)) {
+        if (dl_se->runtime > 0)
+            dl_se->runtime = 0;
+    }
+
     return (dl_se->runtime <= 0);
 }
@@ -779,7 +787,7 @@ static void update_curr_dl(struct rq *rq)
     dl_se->runtime -= delta_exec;
 
 throttle:
-    if (dl_runtime_exceeded(dl_se) || dl_se->dl_yielded) {
+    if (dl_runtime_exceeded(rq, dl_se) || dl_se->dl_yielded) {
         dl_se->dl_throttled = 1;
         __dequeue_task_dl(rq, curr, 0);
         if (unlikely(dl_se->dl_boosted || !start_dl_timer(curr)))
#11 lore raw
Quoted 6 lines · On Wed, 12 Apr 2017 20:30:04 +0800 Xunlei Pang <[email protected]> wrote:

Image this deadline task was preempted after running 0.1ms by another one with an earlier absolute deadline for 1.9ms, after scheduled back it will have the same status (1.9ms remaining runtime, 2ms remaining deadline) under the current implementation.

I can hardly figure out the difference, why is wake-up(will check dl_entity_overflow()) so special?

The difference between a wake-up and being preempted is that one is voluntarily done by the application, the other is done by the scheduler. The preemption done by the schedule must very well be in line with the algorithms of the scheduler. But for cases where the task voluntarily sleeps and then wakes up at some arbitrary time, the scheduler has no idea what its intent was. Not to mention, it must still guarantee the bandwidth for other tasks.

-- Steve

#12 lore raw
In reply to Xunlei Pang

On Wed, 12 Apr 2017 20:30:04 +0800
Xunlei Pang <[email protected]> wrote:
[...]

Quoted 11 lines
Quoted 11 lines

If the relative deadline is different from the period, then the check is an approximation (and this is the big issue here). I am still not sure about what is the best thing to do in this case.

Quoted 7 lines

E.g. For (runtime 2ms, deadline 4ms, period 8ms),
for some reason was preempted after running a very short time 0.1ms, after 0.9ms it was scheduled back and immediately sleep 1ms, when it is awakened, remaining runtime is 1.9ms, remaining deadline(deadline-now) within this period is 2ms, but dl_entity_overflow() is true. However, clearly it can be correctly run 1.9ms before deadline comes wthin this period.

Quoted 8 lines
Quoted 3 lines

Sure, in this case the task can run for 1.9ms before the deadline... But doing so, it might break the guarantees for other deadline tasks. This is what the check is trying to avoid.

Image this deadline task was preempted after running 0.1ms by another one with an earlier absolute deadline for 1.9ms, after scheduled back it will have the same status (1.9ms remaining runtime, 2ms remaining deadline) under the current implementation.

The big difference is that in your first example the task blocks for some time while being the earliest-deadline task (so, the scheduling algorithm would give some execution time to the task, but the task does not use it... So, when the task wakes up, it has to check if now it is too late for using its reserved execution time).
On the other hand, in this second example the task is preempted by an earlier-deadline (higher priority) task, so there is no risk to have execution time reserved to the task that the task does not use (if I understand well your examples).

Quoted 27 lines
Quoted 16 lines
Quoted 16 lines

We can add a condition in dl_runtime_exceeded(), if its deadline is passed, then zero its runtime if positive, and a new period begins.

I did some tests with the following patch, seems it works well, please correct me if I am wrong. ---

 kernel/sched/deadline.c | 16 ++++++++++++----
 1 file changed, 12 insertions(+), 4 deletions(-)
kernel/sched/deadline.c +0 -0
index a2ce590..600c530 100644
@@ -498,8 +498,7 @@ static void update_dl_entity(struct
 sched_dl_entity *dl_se, struct dl_rq *dl_rq = dl_rq_of_se(dl_se);
     struct rq *rq = rq_of_dl_rq(dl_rq);
 
Quoted 10 lines

kernel/sched/deadline.c static void update_dl_entity(struct sched_dl_entity *dl_se, · line 504

Quoted 6 lines
kernel/sched/deadline.c +1 -2
-    if (dl_time_before(dl_se->deadline, rq_clock(rq)) ||
-        dl_entity_overflow(dl_se, pi_se, rq_clock(rq))) {
+    if (!dl_time_before(rq_clock(rq), dl_se->deadline)) {
         dl_se->deadline = rq_clock(rq) + pi_se->dl_deadline;
         dl_se->runtime = pi_se->dl_runtime;
     }  

I think this will break the guarantees for tasks with relative deadline equal to period (think about a task with runtime 5ms, period 10ms and relative deadline 10ms... What happens if the task executes for 4.9ms, then blocks and immediately wakes up?)

Quoted 6 lines

For your example, dl_se->deadline is after now, the if condition is false, update_dl_entity() actually does nothing, that is, after wake-up, it will carry (5ms-4.9ms)=0.1ms remaining runtime and (10ms-4.9ms)=5.1ms remaining deadline/period, continue within the current period. After running further 0.1ms, will be throttled by the timer in update_curr_dl().

Ok, sorry; I saw you inverted rq_clock(rq) and dl_se->deadline), but I did not notice you added a "!". My fault.

In this case, with this change the task cannot consume more than runtime every period (which is good), but it still risks to cause unexpected missed deadlines.
(if relative deadline == period, on uni-processor the current algorithm guarantees that the runtime will always be consumed before the scheduling deadline; on multi-processor it guarantees that the runtime will be consumed before a maximum delay from the deadline; with this change, it is not possible to provide this guarantee anymore).

Luca

Quoted 47 lines

It's actually the original logic, I just removed dl_entity_overflow() condition.

Regards,
Xunlei

Quoted 38 lines

Luca

Quoted 34 lines
kernel/sched/deadline.c +0 -0
@@ -722,13 +721,22 @@ static inline void
 dl_check_constrained_dl(struct sched_dl_entity *dl_se)

dl_time_before(rq_clock(rq), dl_next_period(dl_se))) { if (unlikely(dl_se->dl_boosted || !start_dl_timer(p))) return;

kernel/sched/deadline.c +5 -1
+
+        if (dl_se->runtime > 0)
+            dl_se->runtime = 0;
+
         dl_se->dl_throttled = 1;
     }
 }
 
 static
-int dl_runtime_exceeded(struct sched_dl_entity *dl_se)
+int dl_runtime_exceeded(struct rq *rq, struct sched_dl_entity

*dl_se) {

kernel/sched/deadline.c +6 -1
+    if (!dl_time_before(rq_clock(rq), dl_se->deadline)) {
+        if (dl_se->runtime > 0)
+            dl_se->runtime = 0;
+    }
+
     return (dl_se->runtime <= 0);
 }
@@ -779,7 +787,7 @@ static void update_curr_dl(struct rq *rq)
     dl_se->runtime -= delta_exec;
 
 throttle:
-    if (dl_runtime_exceeded(dl_se) || dl_se->dl_yielded) {
+    if (dl_runtime_exceeded(rq, dl_se) || dl_se->dl_yielded) {
         dl_se->dl_throttled = 1;
         __dequeue_task_dl(rq, curr, 0);
         if (unlikely(dl_se->dl_boosted

|| !start_dl_timer(curr)))

#13 lore raw
Quoted 21 lines · luca abeni

On Wed, 12 Apr 2017 20:30:04 +0800
Xunlei Pang <[email protected]> wrote:
[...]

Quoted 11 lines
Quoted 11 lines

If the relative deadline is different from the period, then the check is an approximation (and this is the big issue here). I am still not sure about what is the best thing to do in this case.

Quoted 7 lines

E.g. For (runtime 2ms, deadline 4ms, period 8ms),
for some reason was preempted after running a very short time 0.1ms, after 0.9ms it was scheduled back and immediately sleep 1ms, when it is awakened, remaining runtime is 1.9ms, remaining deadline(deadline-now) within this period is 2ms, but dl_entity_overflow() is true. However, clearly it can be correctly run 1.9ms before deadline comes wthin this period.

Quoted 7 lines
Quoted 3 lines

Sure, in this case the task can run for 1.9ms before the deadline... But doing so, it might break the guarantees for other deadline tasks. This is what the check is trying to avoid.

Image this deadline task was preempted after running 0.1ms by another one with an earlier absolute deadline for 1.9ms, after scheduled back it will have the same status (1.9ms remaining runtime, 2ms remaining deadline) under the current implementation.

Quoted 9 lines

The big difference is that in your first example the task blocks for some time while being the earliest-deadline task (so, the scheduling algorithm would give some execution time to the task, but the task does not use it... So, when the task wakes up, it has to check if now it is too late for using its reserved execution time).
On the other hand, in this second example the task is preempted by an earlier-deadline (higher priority) task, so there is no risk to have execution time reserved to the task that the task does not use (if I understand well your examples).

Yes, make sense, thanks!

Quoted 93 lines
Quoted 28 lines
Quoted 18 lines
Quoted 18 lines

We can add a condition in dl_runtime_exceeded(), if its deadline is passed, then zero its runtime if positive, and a new period begins.

I did some tests with the following patch, seems it works well, please correct me if I am wrong. ---

 kernel/sched/deadline.c | 16 ++++++++++++----
 1 file changed, 12 insertions(+), 4 deletions(-)
kernel/sched/deadline.c +0 -0
index a2ce590..600c530 100644
@@ -498,8 +498,7 @@ static void update_dl_entity(struct
 sched_dl_entity *dl_se, struct dl_rq *dl_rq = dl_rq_of_se(dl_se);
     struct rq *rq = rq_of_dl_rq(dl_rq);
 
Quoted 10 lines

kernel/sched/deadline.c static void update_dl_entity(struct sched_dl_entity *dl_se, · line 504

Quoted 6 lines
kernel/sched/deadline.c +1 -2
-    if (dl_time_before(dl_se->deadline, rq_clock(rq)) ||
-        dl_entity_overflow(dl_se, pi_se, rq_clock(rq))) {
+    if (!dl_time_before(rq_clock(rq), dl_se->deadline)) {
         dl_se->deadline = rq_clock(rq) + pi_se->dl_deadline;
         dl_se->runtime = pi_se->dl_runtime;
     }  

I think this will break the guarantees for tasks with relative deadline equal to period (think about a task with runtime 5ms, period 10ms and relative deadline 10ms... What happens if the task executes for 4.9ms, then blocks and immediately wakes up?)

Quoted 6 lines

For your example, dl_se->deadline is after now, the if condition is false, update_dl_entity() actually does nothing, that is, after wake-up, it will carry (5ms-4.9ms)=0.1ms remaining runtime and (10ms-4.9ms)=5.1ms remaining deadline/period, continue within the current period. After running further 0.1ms, will be throttled by the timer in update_curr_dl().

Ok, sorry; I saw you inverted rq_clock(rq) and dl_se->deadline), but I did not notice you added a "!". My fault.

In this case, with this change the task cannot consume more than runtime every period (which is good), but it still risks to cause unexpected missed deadlines.
(if relative deadline == period, on uni-processor the current algorithm guarantees that the runtime will always be consumed before the scheduling deadline; on multi-processor it guarantees that the runtime will be consumed before a maximum delay from the deadline; with this change, it is not possible to provide this guarantee anymore).

Luca

Quoted 44 lines

It's actually the original logic, I just removed dl_entity_overflow() condition.

Regards,
Xunlei

Quoted 37 lines

Luca

Quoted 34 lines
kernel/sched/deadline.c +0 -0
@@ -722,13 +721,22 @@ static inline void
 dl_check_constrained_dl(struct sched_dl_entity *dl_se)

dl_time_before(rq_clock(rq), dl_next_period(dl_se))) { if (unlikely(dl_se->dl_boosted || !start_dl_timer(p))) return;

kernel/sched/deadline.c +5 -1
+
+        if (dl_se->runtime > 0)
+            dl_se->runtime = 0;
+
         dl_se->dl_throttled = 1;
     }
 }
 
 static
-int dl_runtime_exceeded(struct sched_dl_entity *dl_se)
+int dl_runtime_exceeded(struct rq *rq, struct sched_dl_entity

*dl_se) {

kernel/sched/deadline.c +6 -1
+    if (!dl_time_before(rq_clock(rq), dl_se->deadline)) {
+        if (dl_se->runtime > 0)
+            dl_se->runtime = 0;
+    }
+
     return (dl_se->runtime <= 0);
 }
@@ -779,7 +787,7 @@ static void update_curr_dl(struct rq *rq)
     dl_se->runtime -= delta_exec;
 
 throttle:
-    if (dl_runtime_exceeded(dl_se) || dl_se->dl_yielded) {
+    if (dl_runtime_exceeded(rq, dl_se) || dl_se->dl_yielded) {
         dl_se->dl_throttled = 1;
         __dequeue_task_dl(rq, curr, 0);
         if (unlikely(dl_se->dl_boosted

|| !start_dl_timer(curr)))

#14 lore raw
In reply to Daniel Bristot de Oliveira
Quoted 97 lines · Daniel Bristot de Oliveira
Quoted 24 lines · Xunlei Pang

I was testing Daniel's changes with his test case in the commit df8eac8cafce ("sched/deadline: Throttle a constrained deadline task activated after the deadline"), and tweaked it a little.

Instead of having the runtime equal to the deadline, I tweaked runtime, deadline and sleep value to ensure every time it calls dl_check_constrained_dl() with "dl_se->deadline > rq_clock(rq)" as well as true dl_entity_overflow(), so it does replenishing every wake up in update_dl_entity(), and break its bandwidth.

Daniel's test case had:
attr.sched_runtime = 2 * 1000 * 1000; /* 2 ms */ attr.sched_deadline = 2 * 1000 * 1000; /* 2 ms*/ attr.sched_period = 2 * 1000 * 1000 * 1000; /* 2 s */ ts.tv_sec = 0;
ts.tv_nsec = 2000 * 1000; /* 2 ms */

I changed it to:
attr.sched_runtime = 5 * 1000 * 1000; /* 5 ms */ attr.sched_deadline = 7 * 1000 * 1000; /* 7 ms */ attr.sched_period = 1 * 1000 * 1000 * 1000; /* 1 s */ ts.tv_sec = 0;
ts.tv_nsec = 1000 * 1000; /* 1 ms */

Quoted 5 lines

The change above can result in over 25% of the CPU on my machine.

In order to avoid the beakage, we improve dl_check_constrained_dl() to prevent dl tasks from being activated until the next period if it runs out of bandwidth of the current period.

The problem now is that, with your patch, we will throttle the task with some possible runtime. Moreover, the task did not brake any rule, like being awakened after the deadline - the user-space is not misbehaving.

That is +- what the reproducer is doing when using your patch, (I put some trace_printk when noticing the overflow in the wakeup).

          <idle>-0     [007] d.h.  1505.066439: enqueue_task_dl: my current runtime is 3657361 and the deadline is 4613027 from now 
          <idle>-0     [007] d.h.  1505.066439: enqueue_task_dl: 	my dl_runtime is 5000000

and so the task will be throttled with 3657361 ns runtime available.

As we can see, it is really breaking the density:

5ms / 7ms (.714285) < 3657361 / 4613027 (.792833)

Well, it is not breaking that much. Trying to be less pessimist, we can compute a new runtime with following equation:

runtime = (dl_runtime / dl_deadline) * (deadline - now)

That is, a runtime which fits in the task's density.

In code:

dl_se->runtime = (div64_u64(dl_se->dl_runtime << 20, dl_se->dl_deadline) * (dl_se->deadline - rq_clock(rq))) >> 20;

For example (a trace_printk) showing the adjusted runtime for the previous task:

          <idle>-0     [007] d.h.  1505.066440: enqueue_task_dl: 	I can still run for 3294208 (it is not that bad)

With the adjusted runtime, we have the following density:

3294208 / 4613027 = .714109

as .714109 < .714285

Voilà. We can still use 3.2 ms of runtime! Not bad at all.

However, even this result is, somehow, controversial. Because we are reducing the task's reservation (Q/P). But that is very close to the implicit deadline behavior: when it "overflows", the runtime is truncated (a replenishment...) and the deadline is postponed. In this case, we do not need to postpone the deadline, just to "truncate" the runtime to fit in the density... it is not that bad.

Another possibility is not to replenish a constrained deadline task twice in a period. In this case, the task would run further the deadline, potentially causing problems for implicit deadline tasks. But! even implicit deadline would do it in a overloaded system. The problem is that, by using the density the system easily becomes overloaded (too pessimistic).

Resuming (so far):

1) We can be pessimistic to the constrained deadline task, with Xunlei's patch;
2) Compute a new runtime to fit in the density - somehow pessimistic.
3) Avoid replenishing a constrained deadline before the next period. but the system will become overload very easily (density).

I think the option 2 is the mid-term.
I am showing a _proof of concept_ patch bellow. I is based in the Xunlei's changes in the verification. I need to polish it... but... you guys can read the idea in C.

Quoted 7 lines

I have the 3) too, but I am not sure if it is as good as 2.

We still need to think more about the solution.... test more... I will continue working on this tomorrow, discussing with luca and tommaso as well.

Thoughts? Am I missing something (probably, I am tired :-) )?

Hi Daniel,

I think you can send out a formal patch for review, thanks!

Regards,
Xunlei

Quoted 83 lines
---
 kernel/sched/deadline.c | 53 ++++++++++++++++++++++++++++---------------------
 1 file changed, 30 insertions(+), 23 deletions(-)
kernel/sched/deadline.c +30 -23
index 7508129..6fa4887 100644
@@ -696,34 +696,38 @@ void init_dl_task_timer(struct sched_dl_entity *dl_se)
 }
 
 /*
- * During the activation, CBS checks if it can reuse the current task's
- * runtime and period. If the deadline of the task is in the past, CBS
- * cannot use the runtime, and so it replenishes the task. This rule
- * works fine for implicit deadline tasks (deadline == period), and the
- * CBS was designed for implicit deadline tasks. However, a task with
- * constrained deadline (deadine < period) might be awakened after the
- * deadline, but before the next period. In this case, replenishing the
- * task would allow it to run for runtime / deadline. As in this case
- * deadline < period, CBS enables a task to run for more than the
- * runtime / period. In a very loaded system, this can cause a domino
- * effect, making other tasks miss their deadlines.
- *
- * To avoid this problem, in the activation of a constrained deadline
- * task after the deadline but before the next period, throttle the
- * task and set the replenishing timer to the begin of the next period,
- * unless it is boosted.
+ * XXX: Daniel will document it better in a clean patch, this is
+ * a proof of concept.
  */
 static inline void dl_check_constrained_dl(struct sched_dl_entity *dl_se)
 {
 	struct task_struct *p = dl_task_of(dl_se);
 	struct rq *rq = rq_of_dl_rq(dl_rq_of_se(dl_se));
+	u64 clock = rq_clock(rq);
 
-	if (dl_time_before(dl_se->deadline, rq_clock(rq)) &&
-	    dl_time_before(rq_clock(rq), dl_next_period(dl_se))) {
-		if (unlikely(dl_se->dl_boosted || !start_dl_timer(p)))
-			return;
-		dl_se->dl_throttled = 1;
+	/* we are in a new period */
+	if (dl_time_before(dl_next_period(dl_se), rq_clock(rq)))
+		return;
+
+	/* are we ok with the deadline and density? */
+	if (dl_time_before(rq_clock(rq), dl_se->deadline) &&
+	    !dl_entity_overflow(dl_se, dl_se, rq_clock(rq)))
+		return;
+
+	/* is the density the problem? */
+	if (dl_entity_overflow(dl_se, dl_se, clock)) {
+		/* reduces the runtime so it fits in the density */
+		dl_se->runtime =
+		  (div64_u64(dl_se->dl_runtime << 20, dl_se->dl_deadline) *
+		  (dl_se->deadline - clock)) >> 20;
+		WARN_ON(dl_se->runtime < 0);
+		return;
 	}
+
+	if (!start_dl_timer(p))
+		return;
+
+	dl_se->dl_throttled = 1;
 }
 
 static
@@ -996,8 +1000,11 @@ static void enqueue_task_dl(struct rq *rq, struct task_struct *p, int flags)
 	 * If that is the case, the task will be throttled and
 	 * the replenishment timer will be set to the next period.
 	 */
-	if (!dl_se->dl_throttled && dl_is_constrained(dl_se))
-		dl_check_constrained_dl(dl_se);
+	if (!p->dl.dl_boosted &&
+	    !p->dl.dl_throttled &&
+	    dl_is_constrained(&p->dl))
+		dl_check_constrained_dl(&p->dl);
+
 
 	/*
 	 * If p is throttled, we do nothing. In fact, if it exhausted