Messages in this thread | | | Date | Mon, 24 Apr 2017 13:00:43 -0400 | From | Steven Rostedt <> | Subject | Re: [PATCH RFC] sched/deadline: Use the revised wakeup rule for suspending constrained dl tasks |
| |
On Mon, 24 Apr 2017 17:18:35 +0200 Daniel Bristot de Oliveira <bristot@redhat.com> 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@redhat.com> > Signed-off-by: Daniel Bristot de Oliveira <bristot@redhat.com> > Cc: Xunlei Pang <xpang@redhat.com> > Cc: Ingo Molnar <mingo@redhat.com> > Cc: Peter Zijlstra <peterz@infradead.org> > Cc: Juri Lelli <juri.lelli@arm.com> > Cc: Steven Rostedt <rostedt@goodmis.org> > Cc: Luca Abeni <luca.abeni@santannapisa.it> > Cc: Tommaso Cucinotta <tommaso.cucinotta@sssup.it> > Cc: Romulo Silva de Oliveira <romulo.deoliveira@ufsc.br> > Cc: linux-kernel@vger.kernel.org > --- > 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; > +} > +
| |