Messages in this thread | | | Date | Wed, 11 Oct 2023 15:24:56 +0200 | From | Peter Zijlstra <> | Subject | Re: [PATCH 03/15] sched/fair: Add lag based placement |
| |
On Wed, Oct 11, 2023 at 08:00:22PM +0800, Abel Wu wrote: > On 5/31/23 7:58 PM, Peter Zijlstra Wrote: > > /* > > + * If we want to place a task and preserve lag, we have to > > + * consider the effect of the new entity on the weighted > > + * average and compensate for this, otherwise lag can quickly > > + * evaporate. > > + * > > + * Lag is defined as: > > + * > > + * lag_i = S - s_i = w_i * (V - v_i) > > + * > > + * To avoid the 'w_i' term all over the place, we only track > > + * the virtual lag: > > + * > > + * vl_i = V - v_i <=> v_i = V - vl_i > > + * > > + * And we take V to be the weighted average of all v: > > + * > > + * V = (\Sum w_j*v_j) / W > > + * > > + * Where W is: \Sum w_j > > + * > > + * Then, the weighted average after adding an entity with lag > > + * vl_i is given by: > > + * > > + * V' = (\Sum w_j*v_j + w_i*v_i) / (W + w_i) > > + * = (W*V + w_i*(V - vl_i)) / (W + w_i) > > + * = (W*V + w_i*V - w_i*vl_i) / (W + w_i) > > + * = (V*(W + w_i) - w_i*l) / (W + w_i) > > + * = V - w_i*vl_i / (W + w_i) > > + * > > + * And the actual lag after adding an entity with vl_i is: > > + * > > + * vl'_i = V' - v_i > > + * = V - w_i*vl_i / (W + w_i) - (V - vl_i) > > + * = vl_i - w_i*vl_i / (W + w_i) > > + * > > + * Which is strictly less than vl_i. So in order to preserve lag > > Maybe a stupid question, but why vl'_i < vl_i? Since vl_i can be negative.
So the below doesn't care about the sign, it simply inverts this relation to express vl_i in vl'_i:
> > + * we should inflate the lag before placement such that the > > + * effective lag after placement comes out right. > > + * > > + * As such, invert the above relation for vl'_i to get the vl_i > > + * we need to use such that the lag after placement is the lag > > + * we computed before dequeue. > > + * > > + * vl'_i = vl_i - w_i*vl_i / (W + w_i) > > + * = ((W + w_i)*vl_i - w_i*vl_i) / (W + w_i) > > + * > > + * (W + w_i)*vl'_i = (W + w_i)*vl_i - w_i*vl_i > > + * = W*vl_i > > + * > > + * vl_i = (W + w_i)*vl'_i / W
And then we obtain the scale factor: (W + w_i)/W, which is >1, right?
As such, that means that vl'_i must be smaller than vl_i in the absolute sense, irrespective of sign.
| |