[PATCH] sched/fair.c: Fix the calculation method of 'lag' to ensure that the vlag of the task after placement is the same as before.

[PATCH] sched/fair.c: Fix the calculation method of 'lag' to ensure that the vlag of the task after placement is the same as before.

[hupu]

From: hupu <hupu@oppo.com>

I think the 'lag' calculation here is inaccurate.

Assume that delta needs to be subtracted from v_i to ensure that the
vlag of task i after placement is the same as before. At this time, the
vlag of task i after placement should be:
vl'_i = V' - (v_i - delta)

From the above formula, we know that vl'_i should be:
vl'_i = (vl_i * W)/(W + w_i)

That is to say:
V' - (v_i - delta) = (vl_i * W)/(W + w_i)

For a newly added entity, generally set v_i to V', and the above formula
can be converted into:
V' - (V' - delta) = (vl_i * W)/(W + w_i)

Therefore the value of delta should be as follows, where delta is the
'lag' in the code.
delta = (vl_i * W)/(W + w_i)

Signed-off-by: hupu <hupu@oppo.com>
---
 kernel/sched/fair.c | 5 ++++-
 1 file changed, 4 insertions(+), 1 deletion(-)

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index 03be0d1330a6..c5f74f753be8 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -5239,9 +5239,12 @@ place_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
 		if (curr && curr->on_rq)
 			load += scale_load_down(curr->load.weight);
 
-		lag *= load + scale_load_down(se->load.weight);
+		lag *= load;
+
+		load += scale_load_down(se->load.weight);
 		if (WARN_ON_ONCE(!load))
 			load = 1;
+
 		lag = div_s64(lag, load);
 	}
 
-- 
2.17.1

Re: [PATCH] sched/fair.c: Fix the calculation method of 'lag' to ensure that the vlag of the task after placement is the same as before.

[Peter Zijlstra]

On Tue, Apr 23, 2024 at 07:44:16PM +0800, hupu@oppo.com wrote:
> From: hupu <hupu@oppo.com>
> 
> I think the 'lag' calculation here is inaccurate.
> 
> Assume that delta needs to be subtracted from v_i to ensure that the
> vlag of task i after placement is the same as before.

Why ?!? v_i is the unkown, it makes no sense to complicate things by
adding extra unknowns.

> At this time, the
> vlag of task i after placement should be:
> vl'_i = V' - (v_i - delta)

But but but, you can't have V' without knowing v_i.

> From the above formula, we know that vl'_i should be:
> vl'_i = (vl_i * W)/(W + w_i)
> 
> That is to say:
> V' - (v_i - delta) = (vl_i * W)/(W + w_i)
> 
> For a newly added entity, generally set v_i to V', and the above formula
> can be converted into:
> V' - (V' - delta) = (vl_i * W)/(W + w_i)
> 
> Therefore the value of delta should be as follows, where delta is the
> 'lag' in the code.
> delta = (vl_i * W)/(W + w_i)
> 
> Signed-off-by: hupu <hupu@oppo.com>
> ---
>  kernel/sched/fair.c | 5 ++++-
>  1 file changed, 4 insertions(+), 1 deletion(-)
> 
> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
> index 03be0d1330a6..c5f74f753be8 100644
> --- a/kernel/sched/fair.c
> +++ b/kernel/sched/fair.c
> @@ -5239,9 +5239,12 @@ place_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
>  		if (curr && curr->on_rq)
>  			load += scale_load_down(curr->load.weight);
>  
> -		lag *= load + scale_load_down(se->load.weight);
> +		lag *= load;
> +
> +		load += scale_load_down(se->load.weight);
>  		if (WARN_ON_ONCE(!load))
>  			load = 1;
> +
>  		lag = div_s64(lag, load);

You're making it:

	v_i = V - (W * vl_i) / (W + w_i)

In direct contradiction to the giant comment right above this that
explains why the code is as it is.

>  	}
>  
> -- 
> 2.17.1
> 

Re: [PATCH] sched/fair.c: Fix the calculation method of 'lag'

[hupu]

> > From: hupu <hupu@oppo.com>
> >
> > I think the 'lag' calculation here is inaccurate.
> >
> > Assume that delta needs to be subtracted from v_i to ensure that the
> > vlag of task i after placement is the same as before.
>
> Why ?!? v_i is the unkown, it makes no sense to complicate things by
> adding extra unknowns.
>
> > At this time, the
> > vlag of task i after placement should be:
> > vl'_i = V' - (v_i - delta)
>
> But but but, you can't have V' without knowing v_i.
>

Thank you for your patient guidance. I overlooked a important fact that
v_i is unknown in the process of proof. Below is the complete proof
process, and it turns out that you are correct.

(I put the formula in a comment block to prevent the email system from
removing the spaces in the formula. This preserves the formatting of the
formula and makes it look more readable.)

The following formula is valid BEFORE placing task i.

/*
 *      \Sum (w_j * v_j)
 * V = ------------------
 *          \Sum w_j
 *
 * 
 * W = \Sum w_j
 * 
 * 
 * vl_i = V - v_i
 */


The following formula is valid AFTER placing task i.
/* 
 *        \Sum (w_j * v_j) + (w_i * v_i')
 * V' =  --------------------------------
 *              \Sum w_j + w_i
 * 
 * 
 * W' = \Sum w_j + w_i
 * 
 * 
 * vl_i' = V' - v_i'
 */

We hope to preserve the vlag which was calculated during the last
dequeue operation. So the proof process should be as follows:

/*
 * vl_i = vl_i'
 * 
 * =>
 * vl_i = V' - v_i'
 * 
 * =>
 *          \Sum (w_j * v_j) + (w_i * v_i')
 * vl_i = -------------------------------- - v_i'
 *                \Sum w_j + w_i
 * 
 * 
 *      \Sum (w_j * v_j) + (w_i * v_i') - v_i' * (\Sum w_j + w_i)
 *  = -------------------------------------------------------------
 *                           \Sum w_j + w_i
 * 
 * 
 *      \Sum (w_j * v_j) + (w_i * v_i') - (v_i' * \Sum w_j) - (v_i' *
 *      w_i)
 *  =
 *  ---------------------------------------------------------------------
 *                            \Sum w_j + w_i
 * 
 * 
 *      \Sum (w_j * v_j) - v_i' * \Sum w_j
 *  = --------------------------------------
 *              \Sum w_j + w_i
 * 
 * 
 *       V * \Sum w_j - v_i' * \Sum w_j
 *  = ------------------------------------
 *              \Sum w_j + w_i
 * 
 * 
 * =>
 * vl_i * (\Sum w_j + w_i) = V * \Sum w_j - v_i' * \Sum w_j
 * 
 * =>
 *              vl_i * (\Sum w_j + w_i)
 * v_i' = V - ---------------------------
 *                   \Sum w_j
 * 
 * 
 *              W + w_i
 *      = V - ----------- * vl_i
 *                 W
 */
 
-- 
2.17.1

Re: [PATCH] sched/fair.c: Fix the calculation method of 'lag'

[Peter Zijlstra]

On Thu, Apr 25, 2024 at 07:44:59PM +0800, hupu@oppo.com wrote:
> > > From: hupu <hupu@oppo.com>
> > >
> > > I think the 'lag' calculation here is inaccurate.
> > >
> > > Assume that delta needs to be subtracted from v_i to ensure that the
> > > vlag of task i after placement is the same as before.
> >
> > Why ?!? v_i is the unkown, it makes no sense to complicate things by
> > adding extra unknowns.
> >
> > > At this time, the
> > > vlag of task i after placement should be:
> > > vl'_i = V' - (v_i - delta)
> >
> > But but but, you can't have V' without knowing v_i.
> >
> 
> Thank you for your patient guidance. I overlooked a important fact that
> v_i is unknown in the process of proof. Below is the complete proof
> process, and it turns out that you are correct.

*phew*, thanks for checking!