[<prev] [next>] [thread-next>] [day] [month] [year] [list]
Message-ID: <cb6c406e-1431-fcfd-ef82-87259760ead9@joelfernandes.org>
Date: Thu, 29 Sep 2022 16:38:44 -0400
From: Joel Fernandes <joel@...lfernandes.org>
To: Peter Zijlstra <peterz@...radead.org>
Cc: LKML <linux-kernel@...r.kernel.org>,
Steven Rostedt <rostedt@...dmis.org>, juri.lelli@...hat.com,
vincent.guittot@...aro.org,
Youssef Esmat <youssefesmat@...gle.com>,
Dietmar Eggemann <dietmar.eggemann@....com>,
Thomas Gleixner <tglx@...utronix.de>
Subject: Sum of weights idea for CFS PI
Hi Peter, all,
Just following-up about the idea Peter suggested at LPC22 about sum of weights
to solve the CFS priority inversion issues using priority inheritance. I am not
sure if a straight forward summation of the weights of dependencies in the
chain, is sufficient (or may cause too much unfairness).
I think it will work if all the tasks on CPU are 100% in utilization:
Say if you have 4 tasks (A, B, C, D) running and each one has equal
weight (W) except for A which has twice the weight (2W).
So the CPU bandwidth distribution is (assuming all are running):
A: 2 / 5
B, C. D: 1 / 5
Say out of the 4 tasks, 3 of them are a part of a classical priority
inversion scenario (A, B and C).
Say now A blocks on a lock and that lock's owner C is running, however now
because A has blocked, B gets 1/3 bandwidth, where as it should have been
limited to 1/5. To remedy this, say you give C a weight of 2W. B gets 1/4
bandwidth - still not fair since B is eating away CPU bandwidth causing the
priority inversion we want to remedy.
The correct bandwidth distribution should be (B and D should be unchanged):
B = 1/5
D = 1/5
C = 3/5
This means that C's weight should be 3W , and B and D should be W each
as before. So indeed, C's new weight is its original weight PLUS the
weight of the A - that's needed to keep the CPU usage of the other
tasks (B, D) in check so that C makes forward progress on behalf of A and the
other tasks don't eat into the CPU utilization.
However, I think this will kinda fall apart if A is asleep 50% of the time
(assume the sleep is because of I/O and unrelated to the PI chain).
Because now if all were running (and assume no PI dependencies), with A being
50%, the bandwidth of B, C and D each would be divided into 2 components:
a. when A is running, it would be as above.
b. but if A was sleeping, B, C, and D would get 1/3.
So on average, B, C and D get: (1/3 + 1/5) / 2 = 8/30. This gives A about 6/30
or 1/5 bandwidth.
But now say A happen to block on a lock that C is holding. You would boost C to
weight 3W which gives it 3/5 (or 18/30) as we saw above, which is more than what
C should actually get.
C should get (8/30 + 6/30 = 14/30) AFAICS.
Hopefully one can see that a straight summation of weights is not enough. It
needs to be something like:
C's new weight = C's original weight + (A's weight) * (A's utilization)
Or something, otherwise the inherited weight may be too much to properly solve it.
Any thoughts on this? You mentioned you had some notes on this and/or proxy
execution, could you share it?
Thanks,
- Joel
Powered by blists - more mailing lists