* Re: [PATCH] sched/fair: Distribute burst-woken tasks when rq depth reaches 3x average
2026-11-04 9:18 [PATCH] sched/fair: Distribute burst-woken tasks when rq depth reaches 3x average Li kunyu
@ 2026-11-04 9:34 ` Li kunyu
2026-11-04 18:10 ` Kayra Cizmeci
2026-11-05 3:44 ` K Prateek Nayak
2 siblings, 0 replies; 5+ messages in thread
From: Li kunyu @ 2026-11-04 9:34 UTC (permalink / raw)
To: mingo, peterz, juri.lelli, vincent.guittot, dietmar.eggemann,
rostedt, bsegall, mgorman, vschneid, kprateek.nayak
Cc: linux-kernel
On 2026/11/4 17:18, Li kunyu wrote:
> When a task burst-wakes a large number of tasks in a short period, tasks
> can pile up on a single CPU regardless of whether the system has idle
> CPUs or NO_HZ enabled.
>
> Track the average runqueue depth (scaled by SCHED_CAPACITY_SCALE to
> preserve fractional precision) in root_domain during the periodic
> load-balance pass.
>
> In select_task_rq_fair(), when the target runqueue depth reaches 3x the
> system-wide average, fall back to cpumask_any_and_distribute(p->cpus_ptr,
> cpu_active_mask) to rotate waking tasks across allowed CPUs and reset the
> periodic load balance intervals so regular load balancing can promptly
> smooth out the distribution.
>
> Suggested-by: Peter Zijlstra <peterz@infradead.org>
> Link: https://lore.kernel.org/all/20261021125419.GK2823843@noisy.programming.kicks-ass.net/
> Signed-off-by: Li kunyu <likunyu@open-hieco.net>
> ---
> kernel/sched/fair.c | 70 ++++++++++++++++++++++++++++++++++++++---
> kernel/sched/sched.h | 3 ++
> kernel/sched/topology.c | 2 ++
> 3 files changed, 71 insertions(+), 4 deletions(-)
>
> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
> index 6e005f1e8dc9..e4d278ac46c4 100644
> --- a/kernel/sched/fair.c
> +++ b/kernel/sched/fair.c
> @@ -9903,6 +9903,38 @@ static int find_energy_efficient_cpu(struct task_struct *p, int prev_cpu)
> return target;
> }
>
> +/*
> + * Check if a CPU's rq depth reaches 3x the system-wide average tracked
> + * in root_domain (scaled by SCHED_CAPACITY_SCALE, floored at 1 task).
> + */
> +static inline bool rq_burst_overloaded(int cpu)
> +{
> + struct rq *rq = cpu_rq(cpu);
> + unsigned long avg;
> +
> + if (unlikely(!rq->rd))
> + return false;
> +
> + avg = max_t(unsigned long, READ_ONCE(rq->rd->avg_nr_running),
> + SCHED_CAPACITY_SCALE);
> +
> + return (READ_ONCE(rq->nr_running) << SCHED_CAPACITY_SHIFT) >= avg * 3;
> +}
> +
> +static inline void reset_periodic_lb_interval(int cpu)
> +{
> + struct sched_domain *sd;
> +
> + /*
> + * Only the most basic values are updated here to avoid excessive
> + * cost.
> + */
> + for_each_domain(cpu, sd) {
> + if (READ_ONCE(sd->balance_interval) > sd->min_interval)
> + WRITE_ONCE(sd->balance_interval, sd->min_interval);
> + }
> +}
> +
> /*
> * select_task_rq_fair: Select target runqueue for the waking task in domains
> * that have the relevant SD flag set. In practice, this is SD_BALANCE_WAKE,
> @@ -9972,11 +10004,19 @@ select_task_rq_fair(struct task_struct *p, int prev_cpu, int wake_flags)
>
> /* Slow path */
> if (unlikely(sd))
> - return sched_balance_find_dst_cpu(sd, p, cpu, prev_cpu, sd_flag);
> -
> + new_cpu = sched_balance_find_dst_cpu(sd, p, cpu, prev_cpu, sd_flag);
> /* Fast path */
> - if (wake_flags & WF_TTWU)
> - return select_idle_sibling(p, prev_cpu, new_cpu);
> + else if (wake_flags & WF_TTWU)
> + new_cpu = select_idle_sibling(p, prev_cpu, new_cpu);
> +
> + if (unlikely(rq_burst_overloaded(new_cpu))) {
> + int dist_cpu = cpumask_any_and_distribute(p->cpus_ptr, cpu_active_mask);
> +
> + if (likely(dist_cpu < nr_cpumask_bits)) {
> + reset_periodic_lb_interval(new_cpu);
> + return dist_cpu;
> + }
> + }
>
> return new_cpu;
> }
> @@ -11685,6 +11725,7 @@ struct sg_lb_stats {
> struct sd_lb_stats {
> struct sched_group *busiest; /* Busiest group in this sd */
> struct sched_group *local; /* Local group in this sd */
> + unsigned long total_nr_running; /* Sum of nr_running in this sd */
> unsigned long total_load; /* Total load of all groups in sd */
> unsigned long total_capacity; /* Total capacity of all groups in sd */
> unsigned long avg_load; /* Average load across all groups in sd */
> @@ -12964,6 +13005,7 @@ static inline void update_sd_lb_stats(struct lb_env *env, struct sd_lb_stats *sd
> /* Now, start updating sd_lb_stats */
> sds->total_load += sgs->group_load;
> sds->total_capacity += sgs->group_capacity;
> + sds->total_nr_running += sgs->sum_nr_running;
>
> sum_util += sgs->group_util;
> sg = sg->next;
> @@ -12982,11 +13024,31 @@ static inline void update_sd_lb_stats(struct lb_env *env, struct sd_lb_stats *sd
> env->fbq_type = fbq_classify_group(&sds->busiest_stat);
>
> if (!env->sd->parent) {
> + unsigned int weight = env->sd->span_weight;
> +
> /* update overload indicator if we are at root domain */
> set_rd_overloaded(env->dst_rq->rd, sg_overloaded);
>
> /* Update over-utilization (tipping point, U >= 0) indicator */
> set_rd_overutilized(env->dst_rq->rd, sg_overutilized);
> +
> + /*
> + * We update the average task count at the top-level (root)
> + * domain, as this incurs the least overhead and comes
> + * closest to the ideal scenario. The trade-off is that we
> + * must accept some temporary data inaccuracy.
> + */
> + if (weight) {
> + unsigned long cur_avg;
> + unsigned long old_avg;
> +
> + cur_avg = (sds->total_nr_running << SCHED_CAPACITY_SHIFT) / weight;
> + old_avg = READ_ONCE(env->dst_rq->rd->avg_nr_running);
> + if (old_avg)
> + cur_avg = (old_avg * 7 + cur_avg) >> 3;
> +
> + WRITE_ONCE(env->dst_rq->rd->avg_nr_running, cur_avg);
> + }
> } else if (sg_overutilized) {
> set_rd_overutilized(env->dst_rq->rd, sg_overutilized);
> }
> diff --git a/kernel/sched/sched.h b/kernel/sched/sched.h
> index e656c7059bf8..4147e043407c 100644
> --- a/kernel/sched/sched.h
> +++ b/kernel/sched/sched.h
> @@ -1077,6 +1077,9 @@ struct root_domain {
> cpumask_var_t rto_mask;
> struct cpupri cpupri;
>
> + /* Scaled (SCHED_CAPACITY_SCALE) average per-CPU rq depth */
> + unsigned long avg_nr_running;
> +
> /*
> * NULL-terminated list of performance domains intersecting with the
> * CPUs of the rd. Protected by RCU.
> diff --git a/kernel/sched/topology.c b/kernel/sched/topology.c
> index 3dab0253976f..41c3b9e30d65 100644
> --- a/kernel/sched/topology.c
> +++ b/kernel/sched/topology.c
> @@ -558,6 +558,8 @@ static int init_rootdomain(struct root_domain *rd)
>
> if (cpupri_init(&rd->cpupri) != 0)
> goto free_cpudl;
> +
> + rd->avg_nr_running = SCHED_CAPACITY_SCALE;
> return 0;
>
> free_cpudl:
>
Based on the suggestions from RFC patch 5, I independently developed a patch.
Verification showed highly satisfactory results: performance improved in the
vast majority of tests. The test comparison is provided below:
type pct
hackbench +12.2%
tbench +7.9%
schbench 99th +2.6%
stream-10 +38.5%
stream-100 +52.0%
unixbench +2.1%
overall average +19.2%
hackbench:
group base patch pct
-g 1 0.262 0.232 +11.5%
-g 2 0.288 0.299 -4.0%
-g 4 0.407 0.353 +13.3%
-g 8 0.567 0.467 +17.8%
-g 16 0.836 0.667 +20.2%
-g 32 1.411 1.164 +17.5%
-g 64 2.473 2.250 +9.0%
tbench(throughput):
clients base patch pct
1 475.97 487.16 +2.4%
2 714.48 757.36 +6.0%
4 1349.73 1484.51 +10.0%
8 2059.00 2193.00 +6.5%
16 4364.25 4305.11 -1.4%
32 8325.17 8102.79 -2.7%
64 12614.20 15140.07 +20.0%
128 15845.07 21614.20 +36.4%
256 20837.93 23567.93 +13.1%
512 29820.67 28243.37 -5.3%
1024 25969.93 26559.50 +2.3%
schbench(99th):
threads base patch pct
1 14.2 12.0 +15.5%
2 16.6 16.8 −1.2%
4 21.0 20.6 +1.9%
8 33.4 33.4 0.0%
16 54.6 50.4 +7.7%
32 93.4 79.0 +15.4%
64 196.4 219.6 −11.8%
128 4753.6 4804.8 −1.1%
256 7900.8 7822.4 +1.0%
512 11177.6 11318.4 −1.3%
stream-10:
operation base patch pct
Copy 126408 188733 +49.3%
Scale 124057 184036 +48.4%
Add 160037 203560 +27.2%
Triad 156224 201937 +29.3%
stream-100:
operation base patch pct
Copy 172068 275389 +60.1%
Scale 156385 248252 +58.7%
Add 158850 231243 +45.6%
Triad 162271 232983 +43.6%
unixbench:
cpu base patch pct
1 1808.3 1847.5 +2.2%
384 113834.2 116173.0 +2.1%
--
thanks,
kunyu
^ permalink raw reply [flat|nested] 5+ messages in thread* Re: [PATCH] sched/fair: Distribute burst-woken tasks when rq depth reaches 3x average
2026-11-04 9:18 [PATCH] sched/fair: Distribute burst-woken tasks when rq depth reaches 3x average Li kunyu
2026-11-04 9:34 ` Li kunyu
@ 2026-11-04 18:10 ` Kayra Cizmeci
2026-11-05 1:43 ` Li kunyu
2026-11-05 3:44 ` K Prateek Nayak
2 siblings, 1 reply; 5+ messages in thread
From: Kayra Cizmeci @ 2026-11-04 18:10 UTC (permalink / raw)
To: Li kunyu
Cc: mingo, peterz, juri.lelli, vincent.guittot, dietmar.eggemann,
rostedt, bsegall, mgorman, vschneid, kprateek.nayak,
linux-kernel
Hi!
On Wed, Nov 04, 2026 at 05:18:42PM +0800, Li kunyu wrote:
FWIW, This doesn't apply to the mainline:
Patch failed at 0001 sched/fair: Distribute burst-woken tasks when rq depth reaches 3x average
error: patch failed: kernel/sched/fair.c:9972
error: kernel/sched/fair.c: patch does not apply
> When a task burst-wakes a large number of tasks in a short period, tasks
> can pile up on a single CPU regardless of whether the system has idle
> CPUs or NO_HZ enabled.
>
> Track the average runqueue depth (scaled by SCHED_CAPACITY_SCALE to
> preserve fractional precision) in root_domain during the periodic
> load-balance pass.
>
> In select_task_rq_fair(), when the target runqueue depth reaches 3x the
> system-wide average, fall back to cpumask_any_and_distribute(p->cpus_ptr,
> cpu_active_mask) to rotate waking tasks across allowed CPUs and reset the
> periodic load balance intervals so regular load balancing can promptly
> smooth out the distribution.
>
> Suggested-by: Peter Zijlstra <peterz@infradead.org>
> Link: https://lore.kernel.org/all/20261021125419.GK2823843@noisy.programming.kicks-ass.net/
> Signed-off-by: Li kunyu <likunyu@open-hieco.net>
> ---
> kernel/sched/fair.c | 70 ++++++++++++++++++++++++++++++++++++++---
> kernel/sched/sched.h | 3 ++
> kernel/sched/topology.c | 2 ++
> 3 files changed, 71 insertions(+), 4 deletions(-)
>
> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
> index 6e005f1e8dc9..e4d278ac46c4 100644
> --- a/kernel/sched/fair.c
> +++ b/kernel/sched/fair.c
> @@ -9903,6 +9903,38 @@ static int find_energy_efficient_cpu(struct task_struct *p, int prev_cpu)
> return target;
> }
>
> +/*
> + * Check if a CPU's rq depth reaches 3x the system-wide average tracked
> + * in root_domain (scaled by SCHED_CAPACITY_SCALE, floored at 1 task).
> + */
> +static inline bool rq_burst_overloaded(int cpu)
> +{
> + struct rq *rq = cpu_rq(cpu);
> + unsigned long avg;
> +
> + if (unlikely(!rq->rd))
> + return false;
> +
> + avg = max_t(unsigned long, READ_ONCE(rq->rd->avg_nr_running),
> + SCHED_CAPACITY_SCALE);
> +
> + return (READ_ONCE(rq->nr_running) << SCHED_CAPACITY_SHIFT) >= avg * 3;
> +}
> +
> +static inline void reset_periodic_lb_interval(int cpu)
> +{
> + struct sched_domain *sd;
> +
> + /*
> + * Only the most basic values are updated here to avoid excessive
> + * cost.
> + */
> + for_each_domain(cpu, sd) {
> + if (READ_ONCE(sd->balance_interval) > sd->min_interval)
> + WRITE_ONCE(sd->balance_interval, sd->min_interval);
> + }
> +}
> +
> /*
> * select_task_rq_fair: Select target runqueue for the waking task in domains
> * that have the relevant SD flag set. In practice, this is SD_BALANCE_WAKE,
> @@ -9972,11 +10004,19 @@ select_task_rq_fair(struct task_struct *p, int prev_cpu, int wake_flags)
>
> /* Slow path */
> if (unlikely(sd))
> - return sched_balance_find_dst_cpu(sd, p, cpu, prev_cpu, sd_flag);
> -
> + new_cpu = sched_balance_find_dst_cpu(sd, p, cpu, prev_cpu, sd_flag);
> /* Fast path */
> - if (wake_flags & WF_TTWU)
> - return select_idle_sibling(p, prev_cpu, new_cpu);
> + else if (wake_flags & WF_TTWU)
> + new_cpu = select_idle_sibling(p, prev_cpu, new_cpu);
> +
> + if (unlikely(rq_burst_overloaded(new_cpu))) {
> + int dist_cpu = cpumask_any_and_distribute(p->cpus_ptr, cpu_active_mask);
> +
> + if (likely(dist_cpu < nr_cpumask_bits)) {
> + reset_periodic_lb_interval(new_cpu);
Why are we calling this for new_cpu?
> + return dist_cpu;
> + }
> + }
>
> return new_cpu;
> }
> @@ -11685,6 +11725,7 @@ struct sg_lb_stats {
> struct sd_lb_stats {
> struct sched_group *busiest; /* Busiest group in this sd */
> struct sched_group *local; /* Local group in this sd */
> + unsigned long total_nr_running; /* Sum of nr_running in this sd */
> unsigned long total_load; /* Total load of all groups in sd */
> unsigned long total_capacity; /* Total capacity of all groups in sd */
> unsigned long avg_load; /* Average load across all groups in sd */
> @@ -12964,6 +13005,7 @@ static inline void update_sd_lb_stats(struct lb_env *env, struct sd_lb_stats *sd
> /* Now, start updating sd_lb_stats */
> sds->total_load += sgs->group_load;
> sds->total_capacity += sgs->group_capacity;
> + sds->total_nr_running += sgs->sum_nr_running;
>
> sum_util += sgs->group_util;
> sg = sg->next;
> @@ -12982,11 +13024,31 @@ static inline void update_sd_lb_stats(struct lb_env *env, struct sd_lb_stats *sd
> env->fbq_type = fbq_classify_group(&sds->busiest_stat);
>
> if (!env->sd->parent) {
> + unsigned int weight = env->sd->span_weight;
Uh-oh. There's something wrong, no?
span_weight equals all of the CPU's in the domain.
So in sched_balance_rq() we call sched_balance_find_src_group() and that
calls update_sd_lb_stats().
But it just retries balancing when all of the tasks
in the rq is pinned. In that case the CPU is cleared from the env->cpus
bitmap. But sum_nr_running is calculated for all env->cpus while
span_weight is for all of the CPU's in that domain.
BTW, in theory this could happen multiple times in a row and
it could make things even worse.
Or am I missing something?
> +
> /* update overload indicator if we are at root domain */
> set_rd_overloaded(env->dst_rq->rd, sg_overloaded);
>
> /* Update over-utilization (tipping point, U >= 0) indicator */
> set_rd_overutilized(env->dst_rq->rd, sg_overutilized);
> +
> + /*
> + * We update the average task count at the top-level (root)
> + * domain, as this incurs the least overhead and comes
> + * closest to the ideal scenario. The trade-off is that we
> + * must accept some temporary data inaccuracy.
> + */
> + if (weight) {
> + unsigned long cur_avg;
> + unsigned long old_avg;
> +
> + cur_avg = (sds->total_nr_running << SCHED_CAPACITY_SHIFT) / weight;
> + old_avg = READ_ONCE(env->dst_rq->rd->avg_nr_running);
> + if (old_avg)
> + cur_avg = (old_avg * 7 + cur_avg) >> 3;
> +
> + WRITE_ONCE(env->dst_rq->rd->avg_nr_running, cur_avg);
> + }
> } else if (sg_overutilized) {
> set_rd_overutilized(env->dst_rq->rd, sg_overutilized);
> }
> diff --git a/kernel/sched/sched.h b/kernel/sched/sched.h
> index e656c7059bf8..4147e043407c 100644
> --- a/kernel/sched/sched.h
> +++ b/kernel/sched/sched.h
> @@ -1077,6 +1077,9 @@ struct root_domain {
> cpumask_var_t rto_mask;
> struct cpupri cpupri;
>
> + /* Scaled (SCHED_CAPACITY_SCALE) average per-CPU rq depth */
> + unsigned long avg_nr_running;
> +
> /*
> * NULL-terminated list of performance domains intersecting with the
> * CPUs of the rd. Protected by RCU.
> diff --git a/kernel/sched/topology.c b/kernel/sched/topology.c
> index 3dab0253976f..41c3b9e30d65 100644
> --- a/kernel/sched/topology.c
> +++ b/kernel/sched/topology.c
> @@ -558,6 +558,8 @@ static int init_rootdomain(struct root_domain *rd)
>
> if (cpupri_init(&rd->cpupri) != 0)
> goto free_cpudl;
> +
> + rd->avg_nr_running = SCHED_CAPACITY_SCALE;
> return 0;
>
> free_cpudl:
> --
> 2.47.3
>
BTW, if we are looking to nr_running for this how about atleast looking
at our dist_cpu and not returning it if its nr_running is bigger
than the other CPU. Right now we are looking only at the average.
Would this work for you? Peter/Li?
Thanks,
Kayra
^ permalink raw reply [flat|nested] 5+ messages in thread* Re: [PATCH] sched/fair: Distribute burst-woken tasks when rq depth reaches 3x average
2026-11-04 18:10 ` Kayra Cizmeci
@ 2026-11-05 1:43 ` Li kunyu
0 siblings, 0 replies; 5+ messages in thread
From: Li kunyu @ 2026-11-05 1:43 UTC (permalink / raw)
To: Kayra Cizmeci
Cc: mingo, peterz, juri.lelli, vincent.guittot, dietmar.eggemann,
rostedt, bsegall, mgorman, vschneid, kprateek.nayak,
linux-kernel
Hi Kayra,
On 2026/11/5 2:10, Kayra Cizmeci wrote:
>
> Hi!
>
> On Wed, Nov 04, 2026 at 05:18:42PM +0800, Li kunyu wrote:
>
> FWIW, This doesn't apply to the mainline:
>
> Patch failed at 0001 sched/fair: Distribute burst-woken tasks when rq depth reaches 3x average
> error: patch failed: kernel/sched/fair.c:9972
> error: kernel/sched/fair.c: patch does not apply
Today, I updated the warehouse branch to the latest version, addressed the
identified issues, and performed another thorough test.
>> When a task burst-wakes a large number of tasks in a short period, tasks
>> can pile up on a single CPU regardless of whether the system has idle
>> CPUs or NO_HZ enabled.
>>
>> Track the average runqueue depth (scaled by SCHED_CAPACITY_SCALE to
>> preserve fractional precision) in root_domain during the periodic
>> load-balance pass.
>>
>> In select_task_rq_fair(), when the target runqueue depth reaches 3x the
>> system-wide average, fall back to cpumask_any_and_distribute(p->cpus_ptr,
>> cpu_active_mask) to rotate waking tasks across allowed CPUs and reset the
>> periodic load balance intervals so regular load balancing can promptly
>> smooth out the distribution.
>>
>> Suggested-by: Peter Zijlstra <peterz@infradead.org>
>> Link: https://lore.kernel.org/all/20261021125419.GK2823843@noisy.programming.kicks-ass.net/
>> Signed-off-by: Li kunyu <likunyu@open-hieco.net>
>> ---
>> kernel/sched/fair.c | 70 ++++++++++++++++++++++++++++++++++++++---
>> kernel/sched/sched.h | 3 ++
>> kernel/sched/topology.c | 2 ++
>> 3 files changed, 71 insertions(+), 4 deletions(-)
>>
>> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
>> index 6e005f1e8dc9..e4d278ac46c4 100644
>> --- a/kernel/sched/fair.c
>> +++ b/kernel/sched/fair.c
>> @@ -9903,6 +9903,38 @@ static int find_energy_efficient_cpu(struct task_struct *p, int prev_cpu)
>> return target;
>> }
>>
>> +/*
>> + * Check if a CPU's rq depth reaches 3x the system-wide average tracked
>> + * in root_domain (scaled by SCHED_CAPACITY_SCALE, floored at 1 task).
>> + */
>> +static inline bool rq_burst_overloaded(int cpu)
>> +{
>> + struct rq *rq = cpu_rq(cpu);
>> + unsigned long avg;
>> +
>> + if (unlikely(!rq->rd))
>> + return false;
>> +
>> + avg = max_t(unsigned long, READ_ONCE(rq->rd->avg_nr_running),
>> + SCHED_CAPACITY_SCALE);
>> +
>> + return (READ_ONCE(rq->nr_running) << SCHED_CAPACITY_SHIFT) >= avg * 3;
>> +}
>> +
>> +static inline void reset_periodic_lb_interval(int cpu)
>> +{
>> + struct sched_domain *sd;
>> +
>> + /*
>> + * Only the most basic values are updated here to avoid excessive
>> + * cost.
>> + */
>> + for_each_domain(cpu, sd) {
>> + if (READ_ONCE(sd->balance_interval) > sd->min_interval)
>> + WRITE_ONCE(sd->balance_interval, sd->min_interval);
>> + }
>> +}
>> +
>> /*
>> * select_task_rq_fair: Select target runqueue for the waking task in domains
>> * that have the relevant SD flag set. In practice, this is SD_BALANCE_WAKE,
>> @@ -9972,11 +10004,19 @@ select_task_rq_fair(struct task_struct *p, int prev_cpu, int wake_flags)
>>
>> /* Slow path */
>> if (unlikely(sd))
>> - return sched_balance_find_dst_cpu(sd, p, cpu, prev_cpu, sd_flag);
>> -
>> + new_cpu = sched_balance_find_dst_cpu(sd, p, cpu, prev_cpu, sd_flag);
>> /* Fast path */
>> - if (wake_flags & WF_TTWU)
>> - return select_idle_sibling(p, prev_cpu, new_cpu);
>> + else if (wake_flags & WF_TTWU)
>> + new_cpu = select_idle_sibling(p, prev_cpu, new_cpu);
>> +
>> + if (unlikely(rq_burst_overloaded(new_cpu))) {
>> + int dist_cpu = cpumask_any_and_distribute(p->cpus_ptr, cpu_active_mask);
>> +
>> + if (likely(dist_cpu < nr_cpumask_bits)) {
>> + reset_periodic_lb_interval(new_cpu);
>
> Why are we calling this for new_cpu?
Here, the existing logic is reused, with new_cpu used as the final return value.
It remains unclear whether this approach is appropriate. If it causes no
practical impact, it seems reasonable to keep it unchanged.
>> + return dist_cpu;
>> + }
>> + }
>>
>> return new_cpu;
>> }
>> @@ -11685,6 +11725,7 @@ struct sg_lb_stats {
>> struct sd_lb_stats {
>> struct sched_group *busiest; /* Busiest group in this sd */
>> struct sched_group *local; /* Local group in this sd */
>> + unsigned long total_nr_running; /* Sum of nr_running in this sd */
>> unsigned long total_load; /* Total load of all groups in sd */
>> unsigned long total_capacity; /* Total capacity of all groups in sd */
>> unsigned long avg_load; /* Average load across all groups in sd */
>> @@ -12964,6 +13005,7 @@ static inline void update_sd_lb_stats(struct lb_env *env, struct sd_lb_stats *sd
>> /* Now, start updating sd_lb_stats */
>> sds->total_load += sgs->group_load;
>> sds->total_capacity += sgs->group_capacity;
>> + sds->total_nr_running += sgs->sum_nr_running;
>>
>> sum_util += sgs->group_util;
>> sg = sg->next;
>> @@ -12982,11 +13024,31 @@ static inline void update_sd_lb_stats(struct lb_env *env, struct sd_lb_stats *sd
>> env->fbq_type = fbq_classify_group(&sds->busiest_stat);
>>
>> if (!env->sd->parent) {
>> + unsigned int weight = env->sd->span_weight;
>
> Uh-oh. There's something wrong, no?
>
> span_weight equals all of the CPU's in the domain.
> So in sched_balance_rq() we call sched_balance_find_src_group() and that
> calls update_sd_lb_stats().
>
> But it just retries balancing when all of the tasks
> in the rq is pinned. In that case the CPU is cleared from the env->cpus
> bitmap. But sum_nr_running is calculated for all env->cpus while
> span_weight is for all of the CPU's in that domain.
>
> BTW, in theory this could happen multiple times in a row and
> it could make things even worse.
>
>
> Or am I missing something?
I have also noticed this. Let us optimize it based on the number of env->cpus.
>> +
>> /* update overload indicator if we are at root domain */
>> set_rd_overloaded(env->dst_rq->rd, sg_overloaded);
>>
>> /* Update over-utilization (tipping point, U >= 0) indicator */
>> set_rd_overutilized(env->dst_rq->rd, sg_overutilized);
>> +
>> + /*
>> + * We update the average task count at the top-level (root)
>> + * domain, as this incurs the least overhead and comes
>> + * closest to the ideal scenario. The trade-off is that we
>> + * must accept some temporary data inaccuracy.
>> + */
>> + if (weight) {
>> + unsigned long cur_avg;
>> + unsigned long old_avg;
>> +
>> + cur_avg = (sds->total_nr_running << SCHED_CAPACITY_SHIFT) / weight;
>> + old_avg = READ_ONCE(env->dst_rq->rd->avg_nr_running);
>> + if (old_avg)
>> + cur_avg = (old_avg * 7 + cur_avg) >> 3;
>> +
>> + WRITE_ONCE(env->dst_rq->rd->avg_nr_running, cur_avg);
>> + }
>> } else if (sg_overutilized) {
>> set_rd_overutilized(env->dst_rq->rd, sg_overutilized);
>> }
>> diff --git a/kernel/sched/sched.h b/kernel/sched/sched.h
>> index e656c7059bf8..4147e043407c 100644
>> --- a/kernel/sched/sched.h
>> +++ b/kernel/sched/sched.h
>> @@ -1077,6 +1077,9 @@ struct root_domain {
>> cpumask_var_t rto_mask;
>> struct cpupri cpupri;
>>
>> + /* Scaled (SCHED_CAPACITY_SCALE) average per-CPU rq depth */
>> + unsigned long avg_nr_running;
>> +
>> /*
>> * NULL-terminated list of performance domains intersecting with the
>> * CPUs of the rd. Protected by RCU.
>> diff --git a/kernel/sched/topology.c b/kernel/sched/topology.c
>> index 3dab0253976f..41c3b9e30d65 100644
>> --- a/kernel/sched/topology.c
>> +++ b/kernel/sched/topology.c
>> @@ -558,6 +558,8 @@ static int init_rootdomain(struct root_domain *rd)
>>
>> if (cpupri_init(&rd->cpupri) != 0)
>> goto free_cpudl;
>> +
>> + rd->avg_nr_running = SCHED_CAPACITY_SCALE;
>> return 0;
>>
>> free_cpudl:
>> --
>> 2.47.3
>>
>
> BTW, if we are looking to nr_running for this how about atleast looking
> at our dist_cpu and not returning it if its nr_running is bigger
> than the other CPU. Right now we are looking only at the average.
>
> Would this work for you? Peter/Li?
I added this condition to the new patch to determine whether it improves the
test results or reduces the impact. Ideally, if the effect proves satisfactory,
this condition should be included.
> Thanks,
>
> Kayra
>
In the next round of testing, I will also follow up on the other suggestions to
ensure that the patch meets the quality bar.
--
thanks,
kunyu
^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [PATCH] sched/fair: Distribute burst-woken tasks when rq depth reaches 3x average
2026-11-04 9:18 [PATCH] sched/fair: Distribute burst-woken tasks when rq depth reaches 3x average Li kunyu
2026-11-04 9:34 ` Li kunyu
2026-11-04 18:10 ` Kayra Cizmeci
@ 2026-11-05 3:44 ` K Prateek Nayak
2 siblings, 0 replies; 5+ messages in thread
From: K Prateek Nayak @ 2026-11-05 3:44 UTC (permalink / raw)
To: Li kunyu, mingo, peterz, juri.lelli, vincent.guittot,
dietmar.eggemann, rostedt, bsegall, mgorman, vschneid
Cc: linux-kernel
On 11/4/2026 2:48 PM, Li kunyu wrote:
> +/*
> + * Check if a CPU's rq depth reaches 3x the system-wide average tracked
> + * in root_domain (scaled by SCHED_CAPACITY_SCALE, floored at 1 task).
> + */
> +static inline bool rq_burst_overloaded(int cpu)
> +{
> + struct rq *rq = cpu_rq(cpu);
> + unsigned long avg;
> +
> + if (unlikely(!rq->rd))
> + return false;
> +
> + avg = max_t(unsigned long, READ_ONCE(rq->rd->avg_nr_running),
> + SCHED_CAPACITY_SCALE);
> +
> + return (READ_ONCE(rq->nr_running) << SCHED_CAPACITY_SHIFT) >= avg * 3;
You can just store (avg * 3) >> SCHED_CAPACITY_SHIFT in rd and skip
this math all the time.
> +}
> +
> +static inline void reset_periodic_lb_interval(int cpu)
> +{
> + struct sched_domain *sd;
> +
> + /*
> + * Only the most basic values are updated here to avoid excessive
> + * cost.
> + */
> + for_each_domain(cpu, sd) {
> + if (READ_ONCE(sd->balance_interval) > sd->min_interval)
> + WRITE_ONCE(sd->balance_interval, sd->min_interval);
Isn't 'sd->balance_interval' only stretched for LBF_ALL_PINNED cases?
Why does this make a difference?
> + }
> +}
> +
> /*
> * select_task_rq_fair: Select target runqueue for the waking task in domains
> * that have the relevant SD flag set. In practice, this is SD_BALANCE_WAKE,
> @@ -9972,11 +10004,19 @@ select_task_rq_fair(struct task_struct *p, int prev_cpu, int wake_flags)
>
> /* Slow path */
> if (unlikely(sd))
> - return sched_balance_find_dst_cpu(sd, p, cpu, prev_cpu, sd_flag);
> -
> + new_cpu = sched_balance_find_dst_cpu(sd, p, cpu, prev_cpu, sd_flag);
> /* Fast path */
> - if (wake_flags & WF_TTWU)
> - return select_idle_sibling(p, prev_cpu, new_cpu);
> + else if (wake_flags & WF_TTWU)
> + new_cpu = select_idle_sibling(p, prev_cpu, new_cpu);
Why even do select_idle_sibling() if you are not going to use that
data? Can't we check rq_burst_overloaded() beforehand?
> +
> + if (unlikely(rq_burst_overloaded(new_cpu))) {
> + int dist_cpu = cpumask_any_and_distribute(p->cpus_ptr, cpu_active_mask);
> +
> + if (likely(dist_cpu < nr_cpumask_bits)) {
> + reset_periodic_lb_interval(new_cpu);
This runs for every successful selection? Is that right? Why?
> + return dist_cpu;
> + }
> + }
>
> return new_cpu;
> }
> @@ -11685,6 +11725,7 @@ struct sg_lb_stats {
> struct sd_lb_stats {
> struct sched_group *busiest; /* Busiest group in this sd */
> struct sched_group *local; /* Local group in this sd */
> + unsigned long total_nr_running; /* Sum of nr_running in this sd */
> unsigned long total_load; /* Total load of all groups in sd */
> unsigned long total_capacity; /* Total capacity of all groups in sd */
> unsigned long avg_load; /* Average load across all groups in sd */
> @@ -12964,6 +13005,7 @@ static inline void update_sd_lb_stats(struct lb_env *env, struct sd_lb_stats *sd
> /* Now, start updating sd_lb_stats */
> sds->total_load += sgs->group_load;
> sds->total_capacity += sgs->group_capacity;
> + sds->total_nr_running += sgs->sum_nr_running;
>
> sum_util += sgs->group_util;
> sg = sg->next;
> @@ -12982,11 +13024,31 @@ static inline void update_sd_lb_stats(struct lb_env *env, struct sd_lb_stats *sd
> env->fbq_type = fbq_classify_group(&sds->busiest_stat);
>
> if (!env->sd->parent) {
On a large, busy system, load balancing at topmost domain is only
done once ever couple seconds and keeping the 'avg_nr_running' the
same for that long seems dodgy.
An overshoot shouldn't be worse than what it is now, and an
undershoot would at-least wait till 3 tasks on the CPU so it should
be fine?
> + unsigned int weight = env->sd->span_weight;
> +
> /* update overload indicator if we are at root domain */
> set_rd_overloaded(env->dst_rq->rd, sg_overloaded);
>
> /* Update over-utilization (tipping point, U >= 0) indicator */
> set_rd_overutilized(env->dst_rq->rd, sg_overutilized);
> +
> + /*
> + * We update the average task count at the top-level (root)
> + * domain, as this incurs the least overhead and comes
> + * closest to the ideal scenario. The trade-off is that we
> + * must accept some temporary data inaccuracy.
> + */
> + if (weight) {
> + unsigned long cur_avg;
> + unsigned long old_avg;
> +
> + cur_avg = (sds->total_nr_running << SCHED_CAPACITY_SHIFT) / weight;
> + old_avg = READ_ONCE(env->dst_rq->rd->avg_nr_running);
> + if (old_avg)
> + cur_avg = (old_avg * 7 + cur_avg) >> 3;
Is this an open-coded update_avg()?
> +
> + WRITE_ONCE(env->dst_rq->rd->avg_nr_running, cur_avg);
Can you do this selectively when old_avg != new_avg?
Also since you compare it with,
READ_ONCE(rq->nr_running) << SCHED_CAPACITY_SHIFT
Checking if (cur_avg * 3) >> SCHED_CAPACITY_SHIFT has changed and caching that
would be better and save on computation during wakeup.
> + }
> } else if (sg_overutilized) {
> set_rd_overutilized(env->dst_rq->rd, sg_overutilized);
> }
> diff --git a/kernel/sched/sched.h b/kernel/sched/sched.h
> index e656c7059bf8..4147e043407c 100644
> --- a/kernel/sched/sched.h
> +++ b/kernel/sched/sched.h
> @@ -1077,6 +1077,9 @@ struct root_domain {
> cpumask_var_t rto_mask;
> struct cpupri cpupri;
>
> + /* Scaled (SCHED_CAPACITY_SCALE) average per-CPU rq depth */
> + unsigned long avg_nr_running;
> +
> /*
> * NULL-terminated list of performance domains intersecting with the
> * CPUs of the rd. Protected by RCU.
--
Thanks and Regards,
Prateek
^ permalink raw reply [flat|nested] 5+ messages in thread