Question about sched_prio_to_weight values

From: Francesco Poli
Date: Sun Oct 06 2019 - 18:41:24 EST


Hello,
I am trying to understand something about the internals of the
completely fair scheduler (CFS) used in the Linux kernel.

I have a question about the mapping between nice levels and weights,
I hope someone can shed some light on those numbers.
Please note that I am not subscribed to the LKML: could you please Cc
me on replies? Thanks for your understanding.


As far as I can see, the mapping is hard-coded in the
sched_prio_to_weight array, which is defined in kernel/sched/core.c
The [latest code] defines the following values:

const int sched_prio_to_weight[40] = {
/* -20 */ 88761, 71755, 56483, 46273, 36291,
/* -15 */ 29154, 23254, 18705, 14949, 11916,
/* -10 */ 9548, 7620, 6100, 4904, 3906,
/* -5 */ 3121, 2501, 1991, 1586, 1277,
/* 0 */ 1024, 820, 655, 526, 423,
/* 5 */ 335, 272, 215, 172, 137,
/* 10 */ 110, 87, 70, 56, 45,
/* 15 */ 36, 29, 23, 18, 15,
};

but I found the same values in much more ancient versions
(the values probably date back to the first patch that introduced
the CFS in the kernel).

[latest code]: <https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/kernel/sched/core.c?h=v5.4-rc1>

Now, the comments in the code suggest that each value is obtained by
dividing the previous one by 1.25: I found [some] [documentation] that
seems to confirm that the "weight is roughly equivalent to
1024/(1.25)^(nice)"

[some]: <https://blog.shichao.io/2015/07/22/relationships_among_nice_priority_and_weight_in_linux_kernel.html>
[documentation]: <www.iaiai.org/journals/index.php/IEE/article/download/9/19>

I tried to see whether I could re-obtain those numbers by rounding (to
integers) the values computed with that formula, but the result does not
look quite right.
By using calc(1), I get:

; for (nice = -20; nice < 20; ++nice) {
;; w = 1024/(1.25)^(nice);
;; printf('%3d %7d (%.2f)\n', nice, round(w), w);
;; }
-20 88818 (~88817.84)
-19 71054 (~71054.27)
-18 56843 (~56843.42)
-17 45475 (~45474.74)
-16 36380 (~36379.79)
-15 29104 (~29103.83)
-14 23283 (~23283.06)
-13 18626 (~18626.45)
-12 14901 (~14901.16)
-11 11921 (~11920.93)
-10 9537 (~9536.74)
-9 7629 (~7629.39)
-8 6104 (~6103.52)
-7 4883 (~4882.81)
-6 3906 (3906.25)
-5 3125 (3125)
-4 2500 (2500)
-3 2000 (2000)
-2 1600 (1600)
-1 1280 (1280)
0 1024 (1024)
1 819 (819.2)
2 655 (655.36)
3 524 (~524.29)
4 419 (~419.43)
5 336 (~335.54)
6 268 (~268.44)
7 215 (~214.75)
8 172 (~171.80)
9 137 (~137.44)
10 110 (~109.95)
11 88 (~87.96)
12 70 (~70.37)
13 56 (~56.29)
14 45 (~45.04)
15 36 (~36.03)
16 29 (~28.82)
17 23 (~23.06)
18 18 (~18.45)
19 15 (~14.76)

where some numbers correspond, while others differ from those found
in kernel/sched/core.c ...

I tried to tweak the 1.25 factor: 1.2499599 makes me get
weight == 88761 for nice == -20, but other numbers still differ.
A non-linear curve fitting with grace(1) leads to a factor of 1.25018,
which still produces values that fail to completely match those found
in kernel/sched/core.c ...

I searched the web and the mailing list archives, but I failed to find
an answer to this question. Could someone please explain me how those
numbers were picked?

Thanks for your time!


--
http://www.inventati.org/frx/
There's not a second to spare! To the laboratory!
..................................................... Francesco Poli .
GnuPG key fpr == CA01 1147 9CD2 EFDF FB82 3925 3E1C 27E1 1F69 BFFE

Attachment: pgpTbv3XYg2dZ.pgp
Description: PGP signature