Re: [PATCH 00/15] sched: EEVDF and latency-nice and/or slice-attr

[Youssef Esmat]

On Thu, Oct 5, 2023 at 1:23 PM Youssef Esmat <youssefesmat@xxxxxxxxxxxx> wrote:
>
> On Thu, Oct 5, 2023 at 7:06 AM Peter Zijlstra <peterz@xxxxxxxxxxxxx> wrote:
> >
> > On Mon, Oct 02, 2023 at 08:41:36PM +0200, Peter Zijlstra wrote:
> >
> > > When mixing request sizes things become a little more interesting.
> > >
> > > Let me ponder this a little bit more.
> >
> > Using the attached program (I got *REALLY* fed up trying to draw these
> > diagrams by hand), let us illustrate the difference between Earliest
> > *Eligible* Virtual Deadline First and the one with the Eligible test
> > taken out: EVDF.
> >
> > Specifically, the program was used with the following argument for
> > EEVDF:
> >
> >   ./eevdf -e "0,1024,6" -e "1,1024,2" -e "2,1024,18" -v 19
> >
> > and with an additional '-n' for the EVDF column.
> >

<snip diagrams>

> >
> >
> > As I wrote before; EVDF has worse lag bounds, but this is not
> > insurmountable. The biggest problem that I can see is that of wakeup
> > preemption. Currently we allow to preempt when 'current' has reached V
> > (RUN_TO_PARITY in pick_eevdf()).
> >
> > With these rules, when EEVDF schedules C (our large slice task) at t=10
> > above, it is only a little behind C and can be reaily preempted after
> > about 2 time units.
> >
> > However, EVDF will delay scheduling C until much later, see how A and B
> > walk far ahead of V until t=36. Only when will we pick C. But this means
> > that we're firmly stuck with C for at least 11 time units. A newly
> > placed task will be around V and will have no chance to preempt.
> >
>
> Thank you for the detailed analysis! I am still in the process of
> digesting everything.
> I do have a quick question, this will only be the case if we adjust
> C's runtime without adjusting nice value, correct? So it does not
> currently apply to the submitted code where the only way to change the
> deadline is to also change the nice value and thus how fast/slow
> vruntime accumulates. In other words without the sched_runtime
> patch[1] we should not run into this scenario, correct?
>
> [1] https://lore.kernel.org/lkml/20230915124354.416936110@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx/

Sorry, to clarify, by "this" I meant "that we're firmly stuck with C
for at least 11 time units".

>
> > That said, I do have me a patch to cure some of that:
> >
> >   https://git.kernel.org/pub/scm/linux/kernel/git/peterz/queue.git/commit/?h=sched/eevdf&id=d7edbe431f31762e516f2730196f41322edcc621
> >
> > That would allow a task with a shorter request time to preempt in spite
> > of RUN_TO_PARITY.
> >
> > However, in this example V is only 2/3 of the way to C's deadline, but
> > it we were to have many more tasks, you'll see V gets closer and closer
> > to C's deadline and it will become harder and harder to place such that
> > preemption becomes viable.
> >
> > Adding 4 more tasks:
> >
> >   ./eevdf -e "0,1024,6" -e "1,1024,2" -e "2,1024,18" -v 19 -n -e "3,1024,2" -e "4,1024,2" -e "5,1024,2" -e "6,1024,2"
> >
> > t=92 V=16
> >  A                   |----<
> >  B                    |<
> > >C   |----------------<
> >  D                    |<
> >  E                   |<
> >  F                    |<
> >  G                   |<
> >    |---------|-----*---|---------|---------|----
> >
> >
> > And I worry this will create very real latency spikes.
> >
> > That said; I do see not having the eligibility check can help. So I'm
> > not opposed to having a sched_feat for this, but I would not want to
> > default to EVDF.