Messages in this thread | | | Date | Thu, 12 Oct 2023 15:04:47 +0800 | Subject | Re: Re: [PATCH 03/15] sched/fair: Add lag based placement | From | Abel Wu <> |
| |
On 10/11/23 9:24 PM, Peter Zijlstra Wrote: > 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?
Yeah, I see. But the scale factor is only for the to-be-placed entity. Say there is an entity k on the tree:
vl_k = V - v_k
adding the to-be-placed entity i affects this by:
define delta := w_i*vl_i / (W + w_i)
vl'_k = V' - v_k = V - delta - (V - vl_k) = vl_k - delta
hence for any entity on the tree, its lag is offsetted by @delta. So I wonder if we should simply do offsetting rather than scaling.
> > As such, that means that vl'_i must be smaller than vl_i in the absolute > sense, irrespective of sign.
| |