[PATCH v2 0/2] sched/fair: Randomize equally shallow idle CPU picks

[PATCH v2 0/2] sched/fair: Randomize equally shallow idle CPU picks

[Christian Loehle]

Concurrent slow-path selectors can converge on the same idle CPU before
either task is enqueued. Remove the idle-recency preference and randomize
equal-latency choices in a single scan.

The testing platform is a 160-CPU, dual-socket Altra with unusually large
80-CPU candidate groups at NUMA level.

Median stress-ng throughput (bogo ops/s):

  --fork  --fork-max      Baseline       Patched    Change
  ------------------------------------------------------
       1           1        779.19        829.82    +6.50%
      16           1       5070.95       5277.62    +4.08%
      16           4       7692.64       7963.30    +3.52%
      32           1       8662.82       8733.79    +0.82%
      64           1      11880.47      12001.01    +1.01%

Separate instrumented runs observed lower conditional stale-pick rates,
i.e. a busy candidate at final return:

Workload                Baseline       Patched
----------------------------------------------
fork, 32 creators          0.771%       0.335%
fork, 64 creators          1.242%       0.633%

Changes since v1:
- Use u64 latency keys and U64_MAX for unpublished states.
- Sample unpublished-state CPUs only as fallbacks, resetting the reservoir
  when the first advertised-state candidate is found.
- Update the Altra measurements.
- Pick up Vincent Guittot's Reviewed-by for patch 1.

Christian Loehle (2):
  sched/fair: Drop idle recency from slow-path CPU selection
  sched/fair: Randomize equally shallow slow-path candidates

 kernel/sched/fair.c | 31 ++++++++++++-------------------
 1 file changed, 12 insertions(+), 19 deletions(-)


base-commit: fd73f4a6659897191fa0d40695fe370925dd3780
-- 
2.34.1

[PATCH v2 1/2] sched/fair: Drop idle recency from slow-path CPU selection

[Christian Loehle]

The slow-path CPU picker favours the most recently idle CPU as a proxy
for cache warmth.

A more recent idle stamp may make ongoing entry more likely. If entry
cannot be aborted, that CPU must finish entry and then exit, potentially
paying more than an already-resident CPU with the same advertised exit
latency. The advertised worst-case latency covers both cases. idle_stamp
does not timestamp the current CPUIdle entry, so this is only a heuristic.

A recent scheduler-idle transition may also mark a short gap in recurring
task activity, making the CPU likely to be busy again soon.

Drop the timestamp tie-break and retain the first candidate unless a
lower advertised exit latency is found.

Signed-off-by: Christian Loehle <christian.loehle@arm.com>
Reviewed-by: Vincent Guittot <vincent.guittot@linaro.org>
---
 kernel/sched/fair.c | 15 +--------------
 1 file changed, 1 insertion(+), 14 deletions(-)

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index 7455a83a6a99..ff5793bddc35 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -8459,7 +8459,6 @@ sched_balance_find_dst_group_cpu(struct sched_group *group, struct task_struct *
 {
 	unsigned long load, min_load = ULONG_MAX;
 	unsigned int min_exit_latency = UINT_MAX;
-	u64 latest_idle_timestamp = 0;
 	int least_loaded_cpu = this_cpu;
 	int shallowest_idle_cpu = -1;
 	int i;
@@ -8481,22 +8480,10 @@ sched_balance_find_dst_group_cpu(struct sched_group *group, struct task_struct *
 		if (available_idle_cpu(i)) {
 			struct cpuidle_state *idle = idle_get_state(rq);
 			if (idle && idle->exit_latency < min_exit_latency) {
-				/*
-				 * We give priority to a CPU whose idle state
-				 * has the smallest exit latency irrespective
-				 * of any idle timestamp.
-				 */
 				min_exit_latency = idle->exit_latency;
-				latest_idle_timestamp = rq->idle_stamp;
 				shallowest_idle_cpu = i;
 			} else if ((!idle || idle->exit_latency == min_exit_latency) &&
-				   rq->idle_stamp > latest_idle_timestamp) {
-				/*
-				 * If equal or no active idle state, then
-				 * the most recently idled CPU might have
-				 * a warmer cache.
-				 */
-				latest_idle_timestamp = rq->idle_stamp;
+				   shallowest_idle_cpu == -1) {
 				shallowest_idle_cpu = i;
 			}
 		} else if (shallowest_idle_cpu == -1) {
-- 
2.34.1

[PATCH v2 2/2] sched/fair: Randomize equally shallow slow-path candidates

[Christian Loehle]

Picking the first eligible idle CPU leaves a scan-order bias. Concurrent
slow-path selectors can choose the same CPU before either task is enqueued.

Use reservoir sampling for equal exit latencies, resetting the candidate
count when a shallower candidate appears. Use the per-CPU scheduler PRNG
and reciprocal_scale() to avoid variable division or a second scan.

Use a u64 latency key with U64_MAX for unpublished states. Published
states take precedence; when none are found, sample among the idle CPUs
without a published state.

Signed-off-by: Christian Loehle <christian.loehle@arm.com>
---
 kernel/sched/fair.c | 18 ++++++++++++------
 1 file changed, 12 insertions(+), 6 deletions(-)

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index ff5793bddc35..810343f40316 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -24,6 +24,7 @@
 #include <linux/mmap_lock.h>
 #include <linux/hugetlb_inline.h>
 #include <linux/jiffies.h>
+#include <linux/math.h>
 #include <linux/mm_api.h>
 #include <linux/highmem.h>
 #include <linux/hrtimer.h>
@@ -8458,7 +8459,8 @@ static int
 sched_balance_find_dst_group_cpu(struct sched_group *group, struct task_struct *p, int this_cpu)
 {
 	unsigned long load, min_load = ULONG_MAX;
-	unsigned int min_exit_latency = UINT_MAX;
+	u64 min_exit_latency = U64_MAX;
+	unsigned int nr_candidates = 0;
 	int least_loaded_cpu = this_cpu;
 	int shallowest_idle_cpu = -1;
 	int i;
@@ -8479,12 +8481,16 @@ sched_balance_find_dst_group_cpu(struct sched_group *group, struct task_struct *
 
 		if (available_idle_cpu(i)) {
 			struct cpuidle_state *idle = idle_get_state(rq);
-			if (idle && idle->exit_latency < min_exit_latency) {
-				min_exit_latency = idle->exit_latency;
-				shallowest_idle_cpu = i;
-			} else if ((!idle || idle->exit_latency == min_exit_latency) &&
-				   shallowest_idle_cpu == -1) {
+			u64 exit_latency = idle ? idle->exit_latency : U64_MAX;
+
+			if (shallowest_idle_cpu == -1 || exit_latency < min_exit_latency) {
+				min_exit_latency = exit_latency;
 				shallowest_idle_cpu = i;
+				nr_candidates = 1;
+			} else if (exit_latency == min_exit_latency) {
+				nr_candidates++;
+				if (!reciprocal_scale(sched_rng(), nr_candidates))
+					shallowest_idle_cpu = i;
 			}
 		} else if (shallowest_idle_cpu == -1) {
 			load = cpu_load(cpu_rq(i));
-- 
2.34.1

Re: [PATCH v2 2/2] sched/fair: Randomize equally shallow slow-path candidates

[Vincent Guittot]

On Thu, 17 Sept 2026 at 17:41, Christian Loehle
<christian.loehle@arm.com> wrote:
>
> Picking the first eligible idle CPU leaves a scan-order bias. Concurrent
> slow-path selectors can choose the same CPU before either task is enqueued.
>
> Use reservoir sampling for equal exit latencies, resetting the candidate
> count when a shallower candidate appears. Use the per-CPU scheduler PRNG
> and reciprocal_scale() to avoid variable division or a second scan.
>
> Use a u64 latency key with U64_MAX for unpublished states. Published
> states take precedence; when none are found, sample among the idle CPUs
> without a published state.
>
> Signed-off-by: Christian Loehle <christian.loehle@arm.com>

Reviewed-by: Vincent Guittot <vincent.guittot@linaro.org>

> ---
>  kernel/sched/fair.c | 18 ++++++++++++------
>  1 file changed, 12 insertions(+), 6 deletions(-)
>
> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
> index ff5793bddc35..810343f40316 100644
> --- a/kernel/sched/fair.c
> +++ b/kernel/sched/fair.c
> @@ -24,6 +24,7 @@
>  #include <linux/mmap_lock.h>
>  #include <linux/hugetlb_inline.h>
>  #include <linux/jiffies.h>
> +#include <linux/math.h>
>  #include <linux/mm_api.h>
>  #include <linux/highmem.h>
>  #include <linux/hrtimer.h>
> @@ -8458,7 +8459,8 @@ static int
>  sched_balance_find_dst_group_cpu(struct sched_group *group, struct task_struct *p, int this_cpu)
>  {
>         unsigned long load, min_load = ULONG_MAX;
> -       unsigned int min_exit_latency = UINT_MAX;
> +       u64 min_exit_latency = U64_MAX;
> +       unsigned int nr_candidates = 0;
>         int least_loaded_cpu = this_cpu;
>         int shallowest_idle_cpu = -1;
>         int i;
> @@ -8479,12 +8481,16 @@ sched_balance_find_dst_group_cpu(struct sched_group *group, struct task_struct *
>
>                 if (available_idle_cpu(i)) {
>                         struct cpuidle_state *idle = idle_get_state(rq);
> -                       if (idle && idle->exit_latency < min_exit_latency) {
> -                               min_exit_latency = idle->exit_latency;
> -                               shallowest_idle_cpu = i;
> -                       } else if ((!idle || idle->exit_latency == min_exit_latency) &&
> -                                  shallowest_idle_cpu == -1) {
> +                       u64 exit_latency = idle ? idle->exit_latency : U64_MAX;
> +
> +                       if (shallowest_idle_cpu == -1 || exit_latency < min_exit_latency) {
> +                               min_exit_latency = exit_latency;
>                                 shallowest_idle_cpu = i;
> +                               nr_candidates = 1;
> +                       } else if (exit_latency == min_exit_latency) {
> +                               nr_candidates++;
> +                               if (!reciprocal_scale(sched_rng(), nr_candidates))
> +                                       shallowest_idle_cpu = i;
>                         }
>                 } else if (shallowest_idle_cpu == -1) {
>                         load = cpu_load(cpu_rq(i));
> --
> 2.34.1
>

Re: [PATCH v2 2/2] sched/fair: Randomize equally shallow slow-path candidates

[Peter Zijlstra]

On Thu, Sep 17, 2026 at 06:06:42PM +0200, Vincent Guittot wrote:
> On Thu, 17 Sept 2026 at 17:41, Christian Loehle
> <christian.loehle@arm.com> wrote:
> >
> > Picking the first eligible idle CPU leaves a scan-order bias. Concurrent
> > slow-path selectors can choose the same CPU before either task is enqueued.
> >
> > Use reservoir sampling for equal exit latencies, resetting the candidate
> > count when a shallower candidate appears. Use the per-CPU scheduler PRNG
> > and reciprocal_scale() to avoid variable division or a second scan.
> >
> > Use a u64 latency key with U64_MAX for unpublished states. Published
> > states take precedence; when none are found, sample among the idle CPUs
> > without a published state.
> >
> > Signed-off-by: Christian Loehle <christian.loehle@arm.com>
> 
> Reviewed-by: Vincent Guittot <vincent.guittot@linaro.org>

Thanks, let me go queue this.