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

From: Peter Zijlstra
Date: Thu Oct 05 2023 - 10:32:50 EST

Next message: John Ogness: "Re: [PATCH printk v2 04/11] printk: nbcon: Provide functions to mark atomic write sections"
Previous message: Simon Glass: "Re: [PATCH v2 1/3] dt-bindings: mtd: fixed-partitions: Add binman compatible"
In reply to: Peter Zijlstra: "Re: [PATCH 00/15] sched: EEVDF and latency-nice and/or slice-attr"
Next in thread: Peter Zijlstra: "Re: [PATCH 00/15] sched: EEVDF and latency-nice and/or slice-attr"
Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]

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=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 |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 |A |----< A |----<
B |< >B |<
C |----------------< C |----------------<
|---------|-----*---|---------|---------|---- |---------|-*-------|---------|---------|----

t=52 V=18 t=36 V=13
A |----< A |----<
>B |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 |----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.
/* GPL-2.0 */
#include <stdio.h>
#include <limits.h>
#include <unistd.h>
#include <stdlib.h>
#include <stdbool.h>
#include <sys/param.h>

bool eligible = true;
unsigned long V_lim = 20;

struct entity {
unsigned long vruntime;
unsigned long weight;
unsigned long request;
unsigned long vdeadline;
int idx;
};

unsigned int gcd(unsigned int a, unsigned int b)
{
int gcd, m = MIN(a, b);

for (int i = 1; i <= m; i++) {
if (a%i == 0 && b%i == 0)
gcd = i;
}

return gcd;
}

int init_entities(int nr, struct entity *es)
{
unsigned int q = 0;

for (int i = 0; i < nr; i++) {
unsigned long d = (1024 * es[i].request) / es[i].weight;
printf("d = %d\n", d);
if (!q)
q = d;
else
q = gcd(q, d);

es[i].vdeadline = es[i].vruntime + d;
es[i].idx = i;
}

printf("q = %d\n\n", q);

return q;
}

int run_entity(struct entity *e)
{
unsigned long d = e->vdeadline - e->vruntime;

d *= e->weight;
d /= 1024;

e->vruntime = e->vdeadline;
e->vdeadline += (1024 * e->request) / e->weight;

return d;
}

unsigned long avg_vruntime(int nr, struct entity *es)
{
unsigned long W = 0, V = 0;

for (int i = 0; i < nr; i++) {
V += es[i].weight * es[i].vruntime;
W += es[i].weight;
}

V /= W;

return V;
}

struct entity *pick_entity(int nr, struct entity *es)
{
unsigned long W = 0, V = 0;
struct entity *e = NULL;

for (int i = 0; i < nr; i++) {
V += es[i].weight * es[i].vruntime;
W += es[i].weight;
}

for (int i = 0; i < nr; i++) {
if (eligible && W*es[i].vruntime > V)
continue;

if (!e || es[i].vdeadline < e->vdeadline)
e = &es[i];
}

return e;
}

void __print_space(int n)
{
for (int i = 0; i < n; i++)
putchar(' ');
}

void __print_arrow(int n)
{
putchar('|');
for (int i = 1; i < (n-1); i++)
putchar('-');
putchar('<');
}

void print_entity(struct entity *e)
{
__print_space(e->vruntime);
__print_arrow(e->vdeadline - e->vruntime);
}

void print_entities(int nr, struct entity *es, struct entity *p)
{
for (int i = 0; i < nr; i++) {
if (&es[i] == p)
putchar('>');
else
putchar(' ');
putchar('A' + i);
putchar(' ');
print_entity(&es[i]);
putchar('\n');
}
}

void print_timeline(unsigned long V)
{
char timeline[] = "|---------|---------|---------|---------|----";

if (V > sizeof(timeline)-1) {
printf("Whoopsie! out of time\n");
exit(0);
}

timeline[V] = '*';
__print_space(3);
puts(timeline);
putchar('\n');
}

void update_lags(int nr, struct entity *es, unsigned long V, long *min, long *max)
{
for (int i = 0; i < nr; i++) {
long lag = V - es[i].vruntime;
if (lag < *min)
*min = lag;
if (lag > *max)
*max = lag;
}
}

int main(int argc, char *argv[])
{
unsigned int s = 0, t = 0, n = 0, q = 1;
long min_lag = 0, max_lag = 0;
struct entity *e, es[8];
unsigned long V;
char S[1024];
int opt;

const int N = sizeof(es) / sizeof(es[0]);

while ((opt = getopt(argc, argv, "nv:e:")) != -1) {
unsigned int v,w,r;

switch (opt) {
case 'n':
eligible = false;
break;

case 'v':
V_lim = atol(optarg);
break;

case 'e':
if (n >= N) {
printf("Whoopsie! too many entities\n");
exit(0);
}
if (sscanf(optarg, "%u,%u,%u", &v,&w,&r) == 3) {
es[n++] = (struct entity) {
.vruntime = v,
.weight = w,
.request = r,
};
}
break;

default:
printf("Whoopsie!, bad arguments\n");
exit(0);
}
}

if (!n) {
printf("Whoopsie!, no entities\n");
exit(0);
}

q = init_entities(n, es);

do {
int d;

V = avg_vruntime(n, es);
printf("t=%d V=%ld\n", t, V);

update_lags(n, es, V, &min_lag, &max_lag);

e = pick_entity(n, es);
if (!e) {
printf("Whoopsie, no pick\n");
exit(0);
}

print_entities(n, es, e);
print_timeline(V);

d = run_entity(e);
t += d;

for (int i = 0; i < d; i += q) {
char c = 'A' + e->idx;
if (i)
c = 'a' + e->idx;
S[s++] = c;
S[s] = '\0';
}

putchar('\n');
} while (V < V_lim);

printf("lags: %ld, %ld\n\n", min_lag, max_lag);

puts(S);
putchar('\n');

return 0;
}

Next message: John Ogness: "Re: [PATCH printk v2 04/11] printk: nbcon: Provide functions to mark atomic write sections"
Previous message: Simon Glass: "Re: [PATCH v2 1/3] dt-bindings: mtd: fixed-partitions: Add binman compatible"
In reply to: Peter Zijlstra: "Re: [PATCH 00/15] sched: EEVDF and latency-nice and/or slice-attr"
Next in thread: Peter Zijlstra: "Re: [PATCH 00/15] sched: EEVDF and latency-nice and/or slice-attr"
Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]