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

[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 */

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 <bristot@xxxxxxxxxx>
Cc: Steven Rostedt <rostedt@xxxxxxxxxxx>
Signed-off-by: Xunlei Pang <xlpang@xxxxxxxxxx>
---
 kernel/sched/deadline.c | 47 +++++++++++++++++++++++++++--------------------
 1 file changed, 27 insertions(+), 20 deletions(-)

diff --git a/kernel/sched/deadline.c b/kernel/sched/deadline.c
index a2ce590..e7be3b4 100644
--- a/kernel/sched/deadline.c
+++ b/kernel/sched/deadline.c
@@ -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);
 
 	/*
-- 
1.8.3.1