diff for duplicates of <20240424085533.GS40213@noisy.programming.kicks-ass.net> diff --git a/a/1.txt b/N1/1.txt index d2852c0..4b4a806 100644 --- a/a/1.txt +++ b/N1/1.txt @@ -1,65 +1,106 @@ -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. +> > 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. +> -Why ?!? v_i is the unkown, it makes no sense to complicate things by -adding extra unknowns. +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. -> At this time, the -> vlag of task i after placement should be: -> vl'_i = V' - (v_i - delta) +(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.) -But but but, you can't have V' without knowing v_i. +The following formula is valid BEFORE placing task 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); +/* + * \Sum (w_j * v_j) + * V = ------------------ + * \Sum w_j + * + * + * W = \Sum w_j + * + * + * vl_i = V - v_i + */ -You're making it: - v_i = V - (W * vl_i) / (W + w_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' + */ -In direct contradiction to the giant comment right above this that -explains why the code is as it is. +We hope to preserve the vlag which was calculated during the last +dequeue operation. So the proof process should be as follows: -> } -> -> -- -> 2.17.1 -> +/* + * 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 diff --git a/a/content_digest b/N1/content_digest index 0a4dddd..1deb908 100644 --- a/a/content_digest +++ b/N1/content_digest @@ -1,85 +1,124 @@ - "ref\020240423114416.64308-1-hupu@oppo.com\0" - "From\0Peter Zijlstra <peterz@infradead.org>\0" - "Subject\0Re: [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.\0" - "Date\0Wed, 24 Apr 2024 10:55:33 +0200\0" - "To\0hupu@oppo.com\0" - "Cc\0mingo@redhat.com" - juri.lelli@redhat.com - vincent.guittot@linaro.org - dietmar.eggemann@arm.com - rostedt@goodmis.org - bsegall@google.com - mgorman@suse.de - bristot@redhat.com - vschneid@redhat.com - linux-kernel@vger.kernel.org - " wuyun.abel@bytedance.com\0" + "From\0<hupu@oppo.com>\0" + "Subject\0Re: [PATCH] sched/fair.c: Fix the calculation method of 'lag'\0" + "Date\0Thu, 25 Apr 2024 19:44:59 +0800\0" + "To\0<peterz@infradead.org>\0" + "Cc\0<mingo@redhat.com>" + <juri.lelli@redhat.com> + <vincent.guittot@linaro.org> + <dietmar.eggemann@arm.com> + <rostedt@goodmis.org> + <bsegall@google.com> + <mgorman@suse.de> + <bristot@redhat.com> + <vschneid@redhat.com> + " <linux-kernel@vger.kernel.org>\0" "\00:1\0" "b\0" - "On Tue, Apr 23, 2024 at 07:44:16PM +0800, hupu@oppo.com wrote:\n" - "> From: hupu <hupu@oppo.com>\n" - "> \n" - "> I think the 'lag' calculation here is inaccurate.\n" - "> \n" - "> Assume that delta needs to be subtracted from v_i to ensure that the\n" - "> vlag of task i after placement is the same as before.\n" + "> > From: hupu <hupu@oppo.com>\n" + "> >\n" + "> > I think the 'lag' calculation here is inaccurate.\n" + "> >\n" + "> > Assume that delta needs to be subtracted from v_i to ensure that the\n" + "> > vlag of task i after placement is the same as before.\n" + ">\n" + "> Why ?!? v_i is the unkown, it makes no sense to complicate things by\n" + "> adding extra unknowns.\n" + ">\n" + "> > At this time, the\n" + "> > vlag of task i after placement should be:\n" + "> > vl'_i = V' - (v_i - delta)\n" + ">\n" + "> But but but, you can't have V' without knowing v_i.\n" + ">\n" "\n" - "Why ?!? v_i is the unkown, it makes no sense to complicate things by\n" - "adding extra unknowns.\n" + "Thank you for your patient guidance. I overlooked a important fact that\n" + "v_i is unknown in the process of proof. Below is the complete proof\n" + "process, and it turns out that you are correct.\n" "\n" - "> At this time, the\n" - "> vlag of task i after placement should be:\n" - "> vl'_i = V' - (v_i - delta)\n" + "(I put the formula in a comment block to prevent the email system from\n" + "removing the spaces in the formula. This preserves the formatting of the\n" + "formula and makes it look more readable.)\n" "\n" - "But but but, you can't have V' without knowing v_i.\n" + "The following formula is valid BEFORE placing task i.\n" "\n" - "> From the above formula, we know that vl'_i should be:\n" - "> vl'_i = (vl_i * W)/(W + w_i)\n" - "> \n" - "> That is to say:\n" - "> V' - (v_i - delta) = (vl_i * W)/(W + w_i)\n" - "> \n" - "> For a newly added entity, generally set v_i to V', and the above formula\n" - "> can be converted into:\n" - "> V' - (V' - delta) = (vl_i * W)/(W + w_i)\n" - "> \n" - "> Therefore the value of delta should be as follows, where delta is the\n" - "> 'lag' in the code.\n" - "> delta = (vl_i * W)/(W + w_i)\n" - "> \n" - "> Signed-off-by: hupu <hupu@oppo.com>\n" - "> ---\n" - "> kernel/sched/fair.c | 5 ++++-\n" - "> 1 file changed, 4 insertions(+), 1 deletion(-)\n" - "> \n" - "> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c\n" - "> index 03be0d1330a6..c5f74f753be8 100644\n" - "> --- a/kernel/sched/fair.c\n" - "> +++ b/kernel/sched/fair.c\n" - "> @@ -5239,9 +5239,12 @@ place_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)\n" - "> \t\tif (curr && curr->on_rq)\n" - "> \t\t\tload += scale_load_down(curr->load.weight);\n" - "> \n" - "> -\t\tlag *= load + scale_load_down(se->load.weight);\n" - "> +\t\tlag *= load;\n" - "> +\n" - "> +\t\tload += scale_load_down(se->load.weight);\n" - "> \t\tif (WARN_ON_ONCE(!load))\n" - "> \t\t\tload = 1;\n" - "> +\n" - "> \t\tlag = div_s64(lag, load);\n" + "/*\n" + " * \\Sum (w_j * v_j)\n" + " * V = ------------------\n" + " * \\Sum w_j\n" + " *\n" + " * \n" + " * W = \\Sum w_j\n" + " * \n" + " * \n" + " * vl_i = V - v_i\n" + " */\n" "\n" - "You're making it:\n" "\n" - "\tv_i = V - (W * vl_i) / (W + w_i)\n" + "The following formula is valid AFTER placing task i.\n" + "/* \n" + " * \\Sum (w_j * v_j) + (w_i * v_i')\n" + " * V' = --------------------------------\n" + " * \\Sum w_j + w_i\n" + " * \n" + " * \n" + " * W' = \\Sum w_j + w_i\n" + " * \n" + " * \n" + " * vl_i' = V' - v_i'\n" + " */\n" "\n" - "In direct contradiction to the giant comment right above this that\n" - "explains why the code is as it is.\n" + "We hope to preserve the vlag which was calculated during the last\n" + "dequeue operation. So the proof process should be as follows:\n" "\n" - "> \t}\n" - "> \n" - "> -- \n" - "> 2.17.1\n" - > + "/*\n" + " * vl_i = vl_i'\n" + " * \n" + " * =>\n" + " * vl_i = V' - v_i'\n" + " * \n" + " * =>\n" + " * \\Sum (w_j * v_j) + (w_i * v_i')\n" + " * vl_i = -------------------------------- - v_i'\n" + " * \\Sum w_j + w_i\n" + " * \n" + " * \n" + " * \\Sum (w_j * v_j) + (w_i * v_i') - v_i' * (\\Sum w_j + w_i)\n" + " * = -------------------------------------------------------------\n" + " * \\Sum w_j + w_i\n" + " * \n" + " * \n" + " * \\Sum (w_j * v_j) + (w_i * v_i') - (v_i' * \\Sum w_j) - (v_i' *\n" + " * w_i)\n" + " * =\n" + " * ---------------------------------------------------------------------\n" + " * \\Sum w_j + w_i\n" + " * \n" + " * \n" + " * \\Sum (w_j * v_j) - v_i' * \\Sum w_j\n" + " * = --------------------------------------\n" + " * \\Sum w_j + w_i\n" + " * \n" + " * \n" + " * V * \\Sum w_j - v_i' * \\Sum w_j\n" + " * = ------------------------------------\n" + " * \\Sum w_j + w_i\n" + " * \n" + " * \n" + " * =>\n" + " * vl_i * (\\Sum w_j + w_i) = V * \\Sum w_j - v_i' * \\Sum w_j\n" + " * \n" + " * =>\n" + " * vl_i * (\\Sum w_j + w_i)\n" + " * v_i' = V - ---------------------------\n" + " * \\Sum w_j\n" + " * \n" + " * \n" + " * W + w_i\n" + " * = V - ----------- * vl_i\n" + " * W\n" + " */\n" + " \n" + "-- \n" + 2.17.1 -fa62292e8f4712de3e80982b8dc3d35a239f983c2c6c58d9e69a81e7d418becb +0ffcf9770406fbfc05725cfc52525fe36e3df31c5ed846d0de69a8ddfc9df174
This is an external index of several public inboxes, see mirroring instructions on how to clone and mirror all data and code used by this external index.