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

From: Xunlei Pang
Date: Mon Apr 10 2017 - 05:24:36 EST


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