[PATCH] sched/fair: Replace random newidle_balance with Bresenham accumulator

Qing Wang
2026-05-06T02:45:07Z

The current NI_RANDOM implementation uses a random dice roll to allow
newidle_balance attempts according to the success rate. There is a better
way to implememte it.

Replace the random dice with a Bresenham accumulator that distributes the
allowed attempts with uniformly spaced evenly across a 1024-step window:

Each step do those:
- Accumulate (1 + newidle_ratio) into newidle_window_pos.
- If the accumulator reaches 1024, allow the balance attempt and
subtract 1024.

This guarantees exactly (1 + newidle_ratio) newidle_balance per 1024 steps
and per newidle_balance with uniformly spaced for any ratio in [0, 1023].

Signed-off-by: Qing Wang <wangqing7171@gmail.com>
---
include/linux/sched/topology.h | 1 +
kernel/sched/fair.c | 18 +++++++++++++-----
kernel/sched/topology.c | 1 +
3 files changed, 15 insertions(+), 5 deletions(-)

diff --git a/include/linux/sched/topology.h b/include/linux/sched/topology.h
index 36553e14866d..fd6de240fb2b 100644
--- a/include/linux/sched/topology.h
+++ b/include/linux/sched/topology.h
@@ -95,6 +95,7 @@ struct sched_domain {
unsigned int newidle_call;
unsigned int newidle_success;
unsigned int newidle_ratio;
+ unsigned int newidle_window_pos;
u64 newidle_stamp;
u64 max_newidle_lb_cost;
unsigned long last_decay_max_lb_cost;
diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index 69361c63353a..7874f795f62d 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -12509,6 +12509,7 @@ static inline void update_newidle_stats(struct sched_domain *sd, unsigned int su
ratio += sd->newidle_success;

sd->newidle_ratio = min(1024, ratio);
+ sd->newidle_window_pos = 0;
sd->newidle_call /= 2;
sd->newidle_success /= 2;
}
@@ -13217,16 +13218,23 @@ static int sched_balance_newidle(struct rq *this_rq, struct rq_flags *rf)

if (sched_feat(NI_RANDOM) && sd->newidle_ratio < 1024) {
/*
- * Throw a 1k sided dice; and only run
- * newidle_balance according to the success
- * rate.
+ * Base on accumulator of Bresenham's line algorithm
+ *
+ * Accumulate ratio each time and trigger balance
+ * when sum ≥ 1024.
+ *
+ * Ensures exactly ratio balances per 1024 calls
+ * and distributes ratio balance operations uniformly
+ * across every 1024 invocations.
*/
- u32 d1k = sched_rng() % 1024;
weight = 1 + sd->newidle_ratio;
- if (d1k > weight) {
+
+ sd->newidle_window_pos += weight;
+ if (sd->newidle_window_pos < 1024) {
update_newidle_stats(sd, 0);
continue;
}
+ sd->newidle_window_pos -= 1024;
weight = (1024 + weight/2) / weight;
}

diff --git a/kernel/sched/topology.c b/kernel/sched/topology.c
index 5847b83d9d55..0d8fa413f66c 100644
--- a/kernel/sched/topology.c
+++ b/kernel/sched/topology.c
@@ -1708,6 +1708,7 @@ sd_init(struct sched_domain_topology_level *tl,
.newidle_call = 512,
.newidle_success = 256,
.newidle_ratio = 512,
+ .newidle_window_pos = 0,
.newidle_stamp = now,

.max_newidle_lb_cost = 0,
--
2.34.1