sched/deadline: Revised wakeup for suspending constrained dl tasks

Hi,

Here is the new version of the patch.

Changes from RFC:
- dl_runtime and dl_deadline don't get updated that often, so save the task's density in a new variable (dl_density) in the sched_dl_entity, avoiding a division in the wakeup path. (Steven Rostedt & Juri Lelli)

- Added a patch fixing the comment of the variable dl_bw in the sched_dl_entity.

- Comment fixes (Peter Zijlstra):
- Reference the correct dependency (s/edf5835/df8eac8cafce/).
- Better explanation of the problem and solution.

- Fixes the laxity check: Use WARN_ON and change the check to one that actually works :-) (Peter Zijlstra).

- Adjust the alignment in the unlikely() in the function (Peter Zijlstra).

Daniel Bristot de Oliveira (2):
sched/deadline: Comment fix - dl_bw = dl_runtime / dl_period sched/deadline: Use the revised wakeup rule for suspending constrained
dl tasks

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

2.5.5

The sched_dl_entity's dl_bw variable stores the utilization (dl_runtime / dl_period) of a task, not its density (dl_runtime / dl_deadline), as the comment says.

---
 include/linux/sched.h | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

index 2b69fc6..9778546 100644
@@ -421,7 +421,7 @@ 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		*/
 
 	/*
 	 * Actual scheduling parameters. Initialized with the values above,

2.5.5

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 resumed 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 worth 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   |  1 +
 kernel/sched/core.c     |  2 +
 kernel/sched/deadline.c | 98 +++++++++++++++++++++++++++++++++++++++++++------
 3 files changed, 90 insertions(+), 11 deletions(-)

index 9778546..f50af02 100644
@@ -422,6 +422,7 @@ struct sched_dl_entity {
 	u64				dl_deadline;	/* Relative deadline of each instance	*/
 	u64				dl_period;	/* Separation of two instances (period) */
 	u64				dl_bw;		/* dl_runtime / dl_period		*/
+	u64				dl_density;	/* dl_runtime / dl_deadline		*/
 
 	/*
 	 * Actual scheduling parameters. Initialized with the values above,

index 803c3bc..da3ffbc 100644
@@ -2159,6 +2159,7 @@ void __dl_clear_params(struct task_struct *p)
 	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;

@@ -4026,6 +4027,7 @@ __setparam_dl(struct task_struct *p, const struct sched_attr *attr)
 	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

2.5.5