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. EEVDF EVDF d = 6 d = 6 d = 2 d = 2 d = 18 d = 18 q = 2 q = 2 t=0 V=1 t=0 V=1 A |----< A |----< >B |< >B |< C |----------------< C |----------------< |*--------|---------|---------|---------|---- |*--------|---------|---------|---------|---- t=2 V=1 t=2 V=1 >A |----< A |----< B |< >B |< C |----------------< C |----------------< |*--------|---------|---------|---------|---- |*--------|---------|---------|---------|---- t=8 V=3 t=4 V=2 A |----< >A |----< >B |< B |< C |----------------< C |----------------< |--*------|---------|---------|---------|---- |-*-------|---------|---------|---------|---- t=10 V=4 t=10 V=4 A |----< A |----< B |< >B |< >C |----------------< C |----------------< |---*-----|---------|---------|---------|---- |---*-----|---------|---------|---------|---- t=28 V=10 t=12 V=5 A |----< A |----< >B |< >B |< C |----------------< C |----------------< |---------*---------|---------|---------|---- |----*----|---------|---------|---------|---- t=30 V=11 t=14 V=5 A |----< A |----< >B |< >B |< C |----------------< C |----------------< |---------|*--------|---------|---------|---- |----*----|---------|---------|---------|---- t=32 V=11 t=16 V=6 A |----< >A |----< >B |< B |< C |----------------< C |----------------< |---------|*--------|---------|---------|---- |-----*---|---------|---------|---------|---- t=34 V=12 t=22 V=8 >A |----< A |----< B |< >B |< C |----------------< C |----------------< |---------|-*-------|---------|---------|---- |-------*-|---------|---------|---------|---- t=40 V=14 t=24 V=9 A |----< A |----< >B |< >B |< C |----------------< C |----------------< |---------|---*-----|---------|---------|---- |--------*|---------|---------|---------|---- t=42 V=15 t=26 V=9 A |----< A |----< >B |< >B |< C |----------------< C |----------------< |---------|----*----|---------|---------|---- |--------*|---------|---------|---------|---- t=44 V=15 t=28 V=10 A |----< >A |----< >B |< B |< C |----------------< C |----------------< |---------|----*----|---------|---------|---- |---------*---------|---------|---------|---- t=46 V=16 t=34 V=12 >A |----< A |----< B |< >B |< C |----------------< C |----------------< |---------|-----*---|---------|---------|---- |---------|-*-------|---------|---------|---- t=52 V=18 t=36 V=13 A |----< A |----< >B |< B |< C |----------------< >C |----------------< |---------|-------*-|---------|---------|---- |---------|--*------|---------|---------|---- t=54 V=19 t=54 V=19 A |----< A |----< >B |< >B |< C |----------------< C |----------------< |---------|--------*|---------|---------|---- |---------|--------*|---------|---------|---- lags: -10, 6 lags: -7, 11 BAaaBCccccccccBBBAaaBBBAaaBB BBAaaBBBAaaBBBAaaBCccccccccB 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. 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.