Patch "sched/deadline: Use the revised wakeup rule for suspending constrained dl tasks" has been added to the 4.9-stable tree

This is a note to let you know that I've just added the patch titled

sched/deadline: Use the revised wakeup rule for suspending constrained dl tasks

to the 4.9-stable tree which can be found at:
http://www.kernel.org/git/?p=linux/kernel/git/stable/stable-queue.git;a=summary

The filename of the patch is:
sched-deadline-use-the-revised-wakeup-rule-for-suspending-constrained-dl-tasks.patch
and it can be found in the queue-4.9 subdirectory.

If you, or anyone else, feels it should not be added to the stable tree, please let <[email protected]> know about it.

From: Daniel Bristot de Oliveira <[email protected]>
Date: Mon, 29 May 2017 16:24:03 +0200
Subject: sched/deadline: Use the revised wakeup rule for suspending constrained dl tasks

From: Daniel Bristot de Oliveira <[email protected]>

commit 3effcb4247e74a51f5d8b775a1ee4abf87cc089a upstream.

We have been facing some problems with self-suspending constrained deadline tasks. The main reason is that the original CBS was not designed for such sort of tasks.

One problem reported by Xunlei Pang takes place when a task suspends, and then is awakened before the deadline, but so close to the deadline that its remaining runtime can cause the task to have an absolute density higher than allowed. In such situation, the original CBS assumes that the task is facing an early activation, and so it replenishes the task and set another deadline, one deadline in the future. This rule works fine for implicit deadline tasks. Moreover, it allows the system to adapt the period of a task in which the external event source suffered from a clock drift.

However, this opens the window for bandwidth leakage for constrained deadline tasks. For instance, a task with the following parameters:

runtime = 5 ms
deadline = 7 ms
[density] = 5 / 7 = 0.71
period = 1000 ms

If the task runs for 1 ms, and then suspends for another 1ms, it will be awakened with the following parameters:

remaining runtime = 4
laxity = 5

presenting a absolute density of 4 / 5 = 0.80.

In this case, the original CBS would assume the task had an early wakeup. Then, CBS will reset the runtime, and the absolute deadline will be postponed by one relative deadline, allowing the task to run.

The problem is that, if the task runs this pattern forever, it will keep receiving bandwidth, being able to run 1ms every 2ms. Following this behavior, the task would be able to run 500 ms in 1 sec. Thus running more than the 5 ms / 1 sec the admission control allowed it to run.

Trying to address the self-suspending case, Luca Abeni, Giuseppe Lipari, and Juri Lelli [1] revisited the CBS in order to deal with self-suspending tasks. In the new approach, rather than replenishing/postponing the absolute deadline, the revised wakeup rule adjusts the remaining runtime, reducing it to fit into the allowed density.

A revised version of the idea is:

At a given time t, the maximum absolute density of a task cannot be higher than its relative density, that is:

runtime / (deadline - t) <= dl_runtime / dl_deadline

Knowing the laxity of a task (deadline - t), it is possible to move it to the other side of the equality, thus enabling to define max remaining runtime a task can use within the absolute deadline, without over-running the allowed density:

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

For instance, in our previous example, the task could still run:

runtime = ( 5 / 7 ) * 5
runtime = 3.57 ms

Without causing damage for other deadline tasks. It is note worthy that the laxity cannot be negative because that would cause a negative runtime. Thus, this patch depends on the patch:

df8eac8cafce ("sched/deadline: Throttle a constrained deadline task activated after the deadline")

Which throttles a constrained deadline task activated after the deadline.

Finally, it is also possible to use the revised wakeup rule for all other tasks, but that would require some more discussions about pros and cons.

---
 include/linux/sched.h   |    3 -
 kernel/sched/core.c     |    2 
 kernel/sched/deadline.c |   98 ++++++++++++++++++++++++++++++++++++++++++------
 3 files changed, 90 insertions(+), 13 deletions(-)

@@ -1411,7 +1411,8 @@ struct sched_dl_entity {
 	u64 dl_runtime;		/* maximum runtime for each instance	*/
 	u64 dl_deadline;	/* relative deadline of each instance	*/
 	u64 dl_period;		/* separation of two instances (period) */
-	u64 dl_bw;		/* dl_runtime / dl_deadline		*/
+	u64 dl_bw;		/* dl_runtime / dl_period		*/
+	u64 dl_density;		/* dl_runtime / dl_deadline		*/
 
 	/*
 	 * Actual scheduling parameters. Initialized with the values above,

@@ -2183,6 +2183,7 @@ void __dl_clear_params(struct task_struc
 	dl_se->dl_period = 0;
 	dl_se->flags = 0;
 	dl_se->dl_bw = 0;
+	dl_se->dl_density = 0;
 
 	dl_se->dl_throttled = 0;
 	dl_se->dl_yielded = 0;

@@ -3911,6 +3912,7 @@ __setparam_dl(struct task_struct *p, con
 	dl_se->dl_period = attr->sched_period ?: dl_se->dl_deadline;
 	dl_se->flags = attr->sched_flags;
 	dl_se->dl_bw = to_ratio(dl_se->dl_period, dl_se->dl_runtime);
+	dl_se->dl_density = to_ratio(dl_se->dl_deadline, dl_se->dl_runtime);
 
 	/*
 	 * Changing the parameters of a task is 'tricky' and we're not doing

Patches currently in stable-queue which might be from [email protected] are

queue-4.9/sched-deadline-zero-out-positive-runtime-after-throttling-constrained-tasks.patch queue-4.9/sched-deadline-use-the-revised-wakeup-rule-for-suspending-constrained-dl-tasks.patch