Re: [PATCH RFC] sched/deadline: Use the revised wakeup rule for suspending constrained dl tasks

[Steven Rostedt]

On Mon, 24 Apr 2017 17:18:35 +0200
Daniel Bristot de Oliveira <bristot@xxxxxxxxxx> wrote:

> 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 ) * 4
>   runtime = 2.85 ms

Nice.

> 
> 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:
> 
>   edf5835 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.
> 
> Reported-by: Xunlei Pang <xpang@xxxxxxxxxx>
> Signed-off-by: Daniel Bristot de Oliveira <bristot@xxxxxxxxxx>
> Cc: Xunlei Pang <xpang@xxxxxxxxxx>
> Cc: Ingo Molnar <mingo@xxxxxxxxxx>
> Cc: Peter Zijlstra <peterz@xxxxxxxxxxxxx>
> Cc: Juri Lelli <juri.lelli@xxxxxxx>
> Cc: Steven Rostedt <rostedt@xxxxxxxxxxx>
> Cc: Luca Abeni <luca.abeni@xxxxxxxxxxxxxxx>
> Cc: Tommaso Cucinotta <tommaso.cucinotta@xxxxxxxx>
> Cc: Romulo Silva de Oliveira <romulo.deoliveira@xxxxxxx>
> Cc: linux-kernel@xxxxxxxxxxxxxxx
> ---
>  kernel/sched/deadline.c | 67 +++++++++++++++++++++++++++++++++++++++++++------
>  1 file changed, 60 insertions(+), 7 deletions(-)
> 
> diff --git a/kernel/sched/deadline.c b/kernel/sched/deadline.c
> index a2ce590..71e5bcf 100644
> --- a/kernel/sched/deadline.c
> +++ b/kernel/sched/deadline.c
> @@ -484,13 +484,63 @@ static bool dl_entity_overflow(struct sched_dl_entity *dl_se,
>  }
>  
>  /*
> + * Revised wakeup rule [1]: For self-suspending tasks, rather then
> + * re-initializing task's runtime and deadline, the revised wakeup
> + * rule adjusts the task's runtime to avoid the task to overrun its
> + * density.
> + *
> + * Reasoning: a task may overrun the density if:
> + *    runtime / (deadline - t) > dl_runtime / dl_deadline
> + *
> + * Therefore, runtime can be adjusted to:
> + *     runtime = (dl_runtime / dl_deadline) * (deadline - t)
> + *
> + * In such way that runtime will be equals to the maximum density
> + * the task can use without breaking any rule.
> + *
> + * [1] Luca Abeni, Giuseppe Lipari, and Juri Lelli. 2015. Constant
> + * bandwidth server revisited. SIGBED Rev. 11, 4 (January 2015), 19-24.
> + */
> +static void
> +update_dl_revised_wakeup(struct sched_dl_entity *dl_se, struct rq *rq)
> +{
> +	u64 density = div64_u64(dl_se->dl_runtime << 20, dl_se->dl_deadline);

Hmm, dl_runtime and dl_deadline don't get updated that often. Can't we
simply keep a static dl_se->dl_density, and update it when dl_runtime
or dl_deadline get updated? That would get rid of the divide in the
middle of a wake up call.

-- Steve

> +	u64 laxity = dl_se->deadline - rq_clock(rq);
> +
> +	BUG_ON(laxity < 0);
> +
> +	dl_se->runtime = density * laxity >> 20;
> +}
> +
> +static inline bool dl_is_constrained(struct sched_dl_entity *dl_se)
> +{
> +	return dl_se->dl_deadline < dl_se->dl_period;
> +}
> +