Question about sched_prio_to_weight values

[Francesco Poli]

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