[PATCH 0/6] [RFC] Large weight differential leads to inefficient load balancing

[PATCH 0/6] [RFC] Large weight differential leads to inefficient load balancing

[Nikhil Rao]

Hi all,

We have observed that a large weight differential between tasks on a runqueue
leads to sub-optimal machine utilization and poor load balancing. For example,
if you have lots of SCHED_IDLE tasks (sufficient number to keep the machine 100%
busy) and a few SCHED_NORMAL soaker tasks, we see that the machine has
significant idle time.

The data below highlights this problem. The test machine is a 4 socket quad-core
box (16 cpus). These experiemnts were done with v2.6.25-rc6. We spawn 16
SCHED_IDLE soaker threads (one per-cpu) to completely fill up the machine. CPU
utilization numbers gathered from mpstat for 10s are:

03:30:24 PM  CPU   %user   %nice    %sys %iowait    %irq   %soft  %steal   %idle    intr/s
03:30:25 PM  all   99.94    0.00    0.06    0.00    0.00    0.00    0.00    0.00  16234.65
03:30:26 PM  all   99.88    0.06    0.06    0.00    0.00    0.00    0.00    0.00  16374.00
03:30:27 PM  all   99.94    0.00    0.06    0.00    0.00    0.00    0.00    0.00  16392.00
03:30:28 PM  all   99.94    0.00    0.06    0.00    0.00    0.00    0.00    0.00  16612.12
03:30:29 PM  all   99.88    0.00    0.12    0.00    0.00    0.00    0.00    0.00  16375.00
03:30:30 PM  all   99.94    0.06    0.00    0.00    0.00    0.00    0.00    0.00  16440.00
03:30:31 PM  all   99.81    0.00    0.19    0.00    0.00    0.00    0.00    0.00  16237.62
03:30:32 PM  all   99.94    0.00    0.06    0.00    0.00    0.00    0.00    0.00  16360.00
03:30:33 PM  all   99.94    0.00    0.06    0.00    0.00    0.00    0.00    0.00  16405.00
03:30:34 PM  all   99.38    0.06    0.50    0.00    0.00    0.00    0.00    0.06  18881.82
Average:     all   99.86    0.02    0.12    0.00    0.00    0.00    0.00    0.01  16628.20

We then spawn one SCHED_NORMAL while-1 task (the absolute number does not matter
so long as we introduce some large weight differential).

03:40:57 PM  CPU   %user   %nice    %sys %iowait    %irq   %soft  %steal   %idle    intr/s
03:40:58 PM  all   83.06    0.00    0.06    0.00    0.00    0.00    0.00   16.88  14555.00
03:40:59 PM  all   78.25    0.00    0.06    0.00    0.00    0.00    0.00   21.69  14527.00
03:41:00 PM  all   82.71    0.06    0.06    0.00    0.00    0.00    0.00   17.17  14879.00
03:41:01 PM  all   87.34    0.00    0.06    0.00    0.00    0.00    0.00   12.59  15466.00
03:41:02 PM  all   80.80    0.06    0.19    0.00    0.00    0.00    0.00   18.95  14584.00
03:41:03 PM  all   82.90    0.00    0.06    0.00    0.00    0.00    0.00   17.04  14570.00
03:41:04 PM  all   79.45    0.00    0.06    0.00    0.00    0.00    0.00   20.49  14536.00
03:41:05 PM  all   86.48    0.00    0.07    0.00    0.00    0.00    0.00   13.46  14577.00
03:41:06 PM  all   76.73    0.06    0.06    0.00    0.00    0.06    0.00   23.10  14594.00
03:41:07 PM  all   86.48    0.00    0.07    0.00    0.00    0.00    0.00   13.45  14703.03
Average:     all   82.31    0.02    0.08    0.00    0.00    0.01    0.00   17.59  14699.10

The machine utilization is sub-optimal and this doesn't look right.  On
investigating this further, we noticed a couple of things. When we consider
load balancing operations at any sched domain where the weight of the group is
greater than one, the group containing the SCHED_NORMAL task is always selected
as the busiest group. While this is expected (SCHED_NORMAL at nice 0 is a factor
of 512 times the weight of SCHED_IDLE), this weight differential leads to
sub-optimal machine utilization.

CPUs outside this group can only pull SCHED_IDLE tasks (because pulling a
SCHED_NORMAL would be far in excess of the imbalance). The load balancer pulls
queued SCHED_IDLE tasks away from this group, and soon it starts failing
balances because it unable to move running tasks. Eventually active migration
kicks in and boots the remaining SCHED_IDLE tasks, leaving idle cpus in the
busiest sched group.

These idle cpus remain idle for long periods of time even though other cpus have
large runqueue depths (albeit filled with SCHED_IDLE tasks). The idle balance on
these cores always select the sched group with the SCHED_NORMAL task to pull tasks
from, and always fails because this group has only one runnable task.

We see the same problem with group scheduling as well, i.e. if we have two
groups with a large weight differential, the machine utilization is sub-optimal.
While this RFC focuses on SCHED_IDLE and SCHED_NORMAL, we can extend these
arguments to SCHED_IDLE-like group entities as well (i.e. groups with cpu.shares
set to 2).

In the remainder of this RFC, we present a solution to address the problem below
and have attached a prototype patchset for feedback and comments. Please let me
know if you have alternate ideas; I would be happy to explore other solutions.

This patchset changes the way the kernel balances SCHED_IDLE tasks. Since
SCHED_IDLE tasks contribute very little weight to the runqueues, we do not
balance them with SCHED_NORMAL/SCHED_BATCH tasks. Instead, we do second pass
to balance SCHED_IDLE tasks using a different metric. We iterate through each
cpu in the sched domain span and calculate the idle load as follows:

     load = (idle_nr_runnig * WEIGHT_IDLEPRIO / idle power)

The metric used is a ratio of the load contributed by SCHED_IDLE tasks to the
available power for running SCHED_IDLE tasks. We determine available power
similar to the RT power scaling calculations, i.e. we scale a CPU's available
idle power based on the average SCHED_NORMAL/SCHED_BATCH activity over a given
period.

Here are some results for a 2.6.35-rc6 kernel + patchset. This is with 16
SCHED_IDLE soaker threads and one SCHED_NORMAL task.

06:55:16 PM  CPU   %user   %nice    %sys %iowait    %irq   %soft  %steal   %idle    intr/s
06:55:17 PM  all   99.88    0.00    0.12    0.00    0.00    0.00    0.00    0.00  16228.71
06:55:18 PM  all   99.81    0.00    0.19    0.00    0.00    0.00    0.00    0.00  16516.16
06:55:19 PM  all   99.94    0.00    0.06    0.00    0.00    0.00    0.00    0.00  16197.03
06:55:20 PM  all   99.94    0.00    0.06    0.00    0.00    0.00    0.00    0.00  16376.00
06:55:21 PM  all   99.88    0.06    0.06    0.00    0.00    0.00    0.00    0.00  16406.00
06:55:22 PM  all   99.94    0.00    0.06    0.00    0.00    0.00    0.00    0.00  16349.00
06:55:23 PM  all  100.00    0.00    0.00    0.00    0.00    0.00    0.00    0.00  16343.00
06:55:24 PM  all   99.94    0.00    0.06    0.00    0.00    0.00    0.00    0.00  16354.00
06:55:25 PM  all   99.94    0.00    0.06    0.00    0.00    0.00    0.00    0.00  16521.21
06:55:26 PM  all   99.94    0.00    0.06    0.00    0.00    0.00    0.00    0.00  16189.11
Average:     all   99.92    0.01    0.08    0.00    0.00    0.00    0.00    0.00  16347.25

Please find attached patches against v2.6.35-rc6. Note that this patchset is a
prototype and there are known limitations:
- not well integrated with the existing LB paths
- does not support group scheduling
- needs to be extended to support preempt kernels
- needs to be power-savings aware
- needs schedstat support
- written/tested for x86/64, SMP

If folks think this is a good direction and this idea has some merit, then I
will be more than happy to continue working with the community to improve this
patchset. If there is another way to fix this problem, then please do tell; I
would be more than happy to help out.

-Thanks
Nikhil

---

Nikhil Rao (6):
  sched: account SCHED_IDLE tasks on rq->idle_nr_running
  sched: add SD_IDLE_LOAD_BALANCE to sched domain flags
  sched: add moving average of time spent servicing SCHED_NORMAL tasks
  sched: add sched_idle_balance argument to lb functions
  sched: add SCHED_IDLE load balancer
  sched: enable SD_IDLE_LOAD_BALANCE on MC, CPU and NUMA (x86) domains

 arch/x86/include/asm/topology.h |    1 +
 include/linux/sched.h           |    1 +
 include/linux/topology.h        |    4 +
 kernel/sched.c                  |   27 +++++++
 kernel/sched_fair.c             |  161 +++++++++++++++++++++++++++++++++++++--
 5 files changed, 186 insertions(+), 8 deletions(-)

[PATCH 1/6] sched: account SCHED_IDLE tasks on rq->idle_nr_running

[Nikhil Rao]

Account SCHED_IDLE tasks on rq->idle_nr_running in addition to rq->nr_running.
This is a preparatory patch for the SCHED_IDLE load balancer.

Signed-off-by: Nikhil Rao <ncrao@google.com>
---
 kernel/sched.c |   15 +++++++++++++++
 1 files changed, 15 insertions(+), 0 deletions(-)

diff --git a/kernel/sched.c b/kernel/sched.c
index f52a880..26e74e9 100644
--- a/kernel/sched.c
+++ b/kernel/sched.c
@@ -456,6 +456,7 @@ struct rq {
 	unsigned long nr_running;
 	#define CPU_LOAD_IDX_MAX 5
 	unsigned long cpu_load[CPU_LOAD_IDX_MAX];
+	unsigned long idle_nr_running;
 #ifdef CONFIG_NO_HZ
 	u64 nohz_stamp;
 	unsigned char in_nohz_recently;
@@ -1838,6 +1839,16 @@ static void dec_nr_running(struct rq *rq)
 	rq->nr_running--;
 }
 
+static void inc_idle_nr_running(struct rq *rq)
+{
+	rq->idle_nr_running++;
+}
+
+static void dec_idle_nr_running(struct rq *rq)
+{
+	rq->idle_nr_running--;
+}
+
 static void set_load_weight(struct task_struct *p)
 {
 	if (task_has_rt_policy(p)) {
@@ -1885,6 +1896,8 @@ static void activate_task(struct rq *rq, struct task_struct *p, int flags)
 
 	enqueue_task(rq, p, flags);
 	inc_nr_running(rq);
+	if (p->policy == SCHED_IDLE)
+		inc_idle_nr_running(rq);
 }
 
 /*
@@ -1897,6 +1910,8 @@ static void deactivate_task(struct rq *rq, struct task_struct *p, int flags)
 
 	dequeue_task(rq, p, flags);
 	dec_nr_running(rq);
+	if (p->policy == SCHED_IDLE)
+		dec_idle_nr_running(rq);
 }
 
 #include "sched_idletask.c"
-- 
1.7.1

[PATCH 2/6] sched: add SD_IDLE_LOAD_BALANCE to sched domain flags

[Nikhil Rao]

Add a new sched domain flag called SD_IDLE_LOAD_BALANCE. SCHED_IDLE tasks are
balanced by the SCHED_IDLE balancer on this domain when enabled, and are handled
by the SCHED_NORMAL load balancer when disabled.

This patch also adds this flag to sched domain init functions in
include/linux/topology.h and arch/x86/include/asm/topology.h (disabled by
default).

Signed-off-by: Nikhil Rao <ncrao@google.com>
---
 arch/x86/include/asm/topology.h |    1 +
 include/linux/sched.h           |    1 +
 include/linux/topology.h        |    4 ++++
 3 files changed, 6 insertions(+), 0 deletions(-)

diff --git a/arch/x86/include/asm/topology.h b/arch/x86/include/asm/topology.h
index 21899cc..9f29b4e 100644
--- a/arch/x86/include/asm/topology.h
+++ b/arch/x86/include/asm/topology.h
@@ -150,6 +150,7 @@ extern unsigned long node_remap_size[];
 				| 0*SD_SHARE_PKG_RESOURCES		\
 				| 1*SD_SERIALIZE			\
 				| 0*SD_PREFER_SIBLING			\
+				| 0*SD_IDLE_LOAD_BALANCE		\
 				,					\
 	.last_balance		= jiffies,				\
 	.balance_interval	= 1,					\
diff --git a/include/linux/sched.h b/include/linux/sched.h
index 747fcae..badf2a7 100644
--- a/include/linux/sched.h
+++ b/include/linux/sched.h
@@ -806,6 +806,7 @@ enum cpu_idle_type {
 #define SD_SERIALIZE		0x0400	/* Only a single load balancing instance */
 
 #define SD_PREFER_SIBLING	0x1000	/* Prefer to place tasks in a sibling domain */
+#define SD_IDLE_LOAD_BALANCE	0x2000	/* Idle load balance on this domain */
 
 enum powersavings_balance_level {
 	POWERSAVINGS_BALANCE_NONE = 0,  /* No power saving load balance */
diff --git a/include/linux/topology.h b/include/linux/topology.h
index c44df50..97fbb1b 100644
--- a/include/linux/topology.h
+++ b/include/linux/topology.h
@@ -103,6 +103,7 @@ int arch_update_cpu_topology(void);
 				| 1*SD_SHARE_PKG_RESOURCES		\
 				| 0*SD_SERIALIZE			\
 				| 0*SD_PREFER_SIBLING			\
+				| 0*SD_IDLE_LOAD_BALANCE		\
 				,					\
 	.last_balance		= jiffies,				\
 	.balance_interval	= 1,					\
@@ -134,6 +135,7 @@ int arch_update_cpu_topology(void);
 				| 0*SD_SHARE_CPUPOWER			\
 				| 1*SD_SHARE_PKG_RESOURCES		\
 				| 0*SD_SERIALIZE			\
+				| 0*SD_IDLE_LOAD_BALANCE		\
 				| sd_balance_for_mc_power()		\
 				| sd_power_saving_flags()		\
 				,					\
@@ -167,6 +169,7 @@ int arch_update_cpu_topology(void);
 				| 0*SD_SHARE_CPUPOWER			\
 				| 0*SD_SHARE_PKG_RESOURCES		\
 				| 0*SD_SERIALIZE			\
+				| 0*SD_IDLE_LOAD_BALANCE		\
 				| sd_balance_for_package_power()	\
 				| sd_power_saving_flags()		\
 				,					\
@@ -195,6 +198,7 @@ int arch_update_cpu_topology(void);
 				| 0*SD_SHARE_PKG_RESOURCES		\
 				| 1*SD_SERIALIZE			\
 				| 0*SD_PREFER_SIBLING			\
+				| 0*SD_IDLE_LOAD_BALANCE		\
 				,					\
 	.last_balance		= jiffies,				\
 	.balance_interval	= 64,					\
-- 
1.7.1

[PATCH 3/6] sched: add moving average of time spent servicing SCHED_NORMAL tasks

[Nikhil Rao]

This patch adds a moving average of time spent servicing SCHED_NORMAL tasks.
This metric is maintained at rq->norm_avg and is similar to rq->rt_avg. This is
metric is used to provide a measure of cpu power available to run SCHED_IDLE
tasks.

Signed-off-by: Nikhil Rao <ncrao@google.com>
---
 kernel/sched.c      |   12 ++++++++++++
 kernel/sched_fair.c |    3 +++
 2 files changed, 15 insertions(+), 0 deletions(-)

diff --git a/kernel/sched.c b/kernel/sched.c
index 26e74e9..d037b6c 100644
--- a/kernel/sched.c
+++ b/kernel/sched.c
@@ -514,6 +514,7 @@ struct rq {
 	unsigned long avg_load_per_task;
 
 	u64 rt_avg;
+	u64 norm_avg;
 	u64 age_stamp;
 	u64 idle_stamp;
 	u64 avg_idle;
@@ -1263,6 +1264,7 @@ static void sched_avg_update(struct rq *rq)
 		asm("" : "+rm" (rq->age_stamp));
 		rq->age_stamp += period;
 		rq->rt_avg /= 2;
+		rq->norm_avg /= 2;
 	}
 }
 
@@ -1272,6 +1274,12 @@ static void sched_rt_avg_update(struct rq *rq, u64 rt_delta)
 	sched_avg_update(rq);
 }
 
+static void sched_norm_avg_update(struct rq *rq, u64 norm_delta)
+{
+	rq->norm_avg += norm_delta;
+	sched_avg_update(rq);
+}
+
 #else /* !CONFIG_SMP */
 static void resched_task(struct task_struct *p)
 {
@@ -1282,6 +1290,10 @@ static void resched_task(struct task_struct *p)
 static void sched_rt_avg_update(struct rq *rq, u64 rt_delta)
 {
 }
+
+static void sched_norm_avg_update(struct rq *rq, u64 norm_delta)
+{
+}
 #endif /* CONFIG_SMP */
 
 #if BITS_PER_LONG == 32
diff --git a/kernel/sched_fair.c b/kernel/sched_fair.c
index a878b53..0e25e51 100644
--- a/kernel/sched_fair.c
+++ b/kernel/sched_fair.c
@@ -543,6 +543,9 @@ static void update_curr(struct cfs_rq *cfs_rq)
 		trace_sched_stat_runtime(curtask, delta_exec, curr->vruntime);
 		cpuacct_charge(curtask, delta_exec);
 		account_group_exec_runtime(curtask, delta_exec);
+
+		if (curtask->policy != SCHED_IDLE)
+			sched_norm_avg_update(task_rq(curtask), delta_exec);
 	}
 }
 
-- 
1.7.1

[PATCH 4/6] sched: add sched_idle_balance argument to lb functions

[Nikhil Rao]

This patch adds an extra sched_idle_balance argument to move_tasks,
load_balance_fair and balance_tasks. This argument is required to differentiate
between SCHED_NORMAL/SCHED_BATCH load balancing and SCHED_IDLE balancing.

Signed-off-by: Nikhil Rao <ncrao@google.com>
---
 kernel/sched_fair.c |   18 ++++++++++--------
 1 files changed, 10 insertions(+), 8 deletions(-)

diff --git a/kernel/sched_fair.c b/kernel/sched_fair.c
index 0e25e51..cb270e8 100644
--- a/kernel/sched_fair.c
+++ b/kernel/sched_fair.c
@@ -1861,7 +1861,8 @@ static unsigned long
 balance_tasks(struct rq *this_rq, int this_cpu, struct rq *busiest,
 	      unsigned long max_load_move, struct sched_domain *sd,
 	      enum cpu_idle_type idle, int *all_pinned,
-	      int *this_best_prio, struct cfs_rq *busiest_cfs_rq)
+	      int *this_best_prio, struct cfs_rq *busiest_cfs_rq,
+	      int sched_idle_balance)
 {
 	int loops = 0, pulled = 0, pinned = 0;
 	long rem_load_move = max_load_move;
@@ -1923,7 +1924,7 @@ static unsigned long
 load_balance_fair(struct rq *this_rq, int this_cpu, struct rq *busiest,
 		  unsigned long max_load_move,
 		  struct sched_domain *sd, enum cpu_idle_type idle,
-		  int *all_pinned, int *this_best_prio)
+		  int *all_pinned, int *this_best_prio, int sched_idle_balance)
 {
 	long rem_load_move = max_load_move;
 	int busiest_cpu = cpu_of(busiest);
@@ -1949,7 +1950,7 @@ load_balance_fair(struct rq *this_rq, int this_cpu, struct rq *busiest,
 
 		moved_load = balance_tasks(this_rq, this_cpu, busiest,
 				rem_load, sd, idle, all_pinned, this_best_prio,
-				busiest_cfs_rq);
+				busiest_cfs_rq, sched_idle_balance);
 
 		if (!moved_load)
 			continue;
@@ -1970,11 +1971,11 @@ static unsigned long
 load_balance_fair(struct rq *this_rq, int this_cpu, struct rq *busiest,
 		  unsigned long max_load_move,
 		  struct sched_domain *sd, enum cpu_idle_type idle,
-		  int *all_pinned, int *this_best_prio)
+		  int *all_pinned, int *this_best_prio, int sched_idle_balance)
 {
 	return balance_tasks(this_rq, this_cpu, busiest,
 			max_load_move, sd, idle, all_pinned,
-			this_best_prio, &busiest->cfs);
+			this_best_prio, &busiest->cfs, sched_idle_balance);
 }
 #endif
 
@@ -1988,7 +1989,7 @@ load_balance_fair(struct rq *this_rq, int this_cpu, struct rq *busiest,
 static int move_tasks(struct rq *this_rq, int this_cpu, struct rq *busiest,
 		      unsigned long max_load_move,
 		      struct sched_domain *sd, enum cpu_idle_type idle,
-		      int *all_pinned)
+		      int *all_pinned, int sched_idle_balance)
 {
 	unsigned long total_load_moved = 0, load_moved;
 	int this_best_prio = this_rq->curr->prio;
@@ -1996,7 +1997,8 @@ static int move_tasks(struct rq *this_rq, int this_cpu, struct rq *busiest,
 	do {
 		load_moved = load_balance_fair(this_rq, this_cpu, busiest,
 				max_load_move - total_load_moved,
-				sd, idle, all_pinned, &this_best_prio);
+				sd, idle, all_pinned, &this_best_prio,
+				sched_idle_balance);
 
 		total_load_moved += load_moved;
 
@@ -2878,7 +2880,7 @@ redo:
 		local_irq_save(flags);
 		double_rq_lock(this_rq, busiest);
 		ld_moved = move_tasks(this_rq, this_cpu, busiest,
-				      imbalance, sd, idle, &all_pinned);
+				      imbalance, sd, idle, &all_pinned, 0);
 		double_rq_unlock(this_rq, busiest);
 		local_irq_restore(flags);
 
-- 
1.7.1

[PATCH 5/6] sched: add SCHED_IDLE load balancer

[Nikhil Rao]

This patch adds a load balancer for SCHED_IDLE tasks (sched_idle_load_balance).
The metric used to balance SCHED_IDLE tasks is calculated as:

  load = (idle_nr_runnig * WEIGHT_IDLEPRIO / idle power)

The metric used is a ratio of the load contributed by SCHED_IDLE tasks to the
available power for running SCHED_IDLE tasks. We determine available power
similar to the RT power scaling calculations, i.e. we scale a CPU's available
idle power based on the average SCHED_NORMAL/SCHED_BATCH activity over a given
period.

The SCHED_IDLE load balancer is called at the end of rebalance domain. It runs
only when the SCHED_NORMAL/SCHED_BATCH balancer runs (i.e. it follows the same
rate limit).

Signed-off-by: Nikhil Rao <ncrao@google.com>
---
 kernel/sched_fair.c |  140 +++++++++++++++++++++++++++++++++++++++++++++++++++
 1 files changed, 140 insertions(+), 0 deletions(-)

diff --git a/kernel/sched_fair.c b/kernel/sched_fair.c
index cb270e8..134ddbf 100644
--- a/kernel/sched_fair.c
+++ b/kernel/sched_fair.c
@@ -1874,6 +1874,20 @@ balance_tasks(struct rq *this_rq, int this_cpu, struct rq *busiest,
 	pinned = 1;
 
 	list_for_each_entry_safe(p, n, &busiest_cfs_rq->tasks, se.group_node) {
+		/*
+		 * We skip this task if the following conditions are satisfied:
+		 * 1. This sched domain has SD_IDLE_LOAD_BALANCE set
+		 * 2. If sched_idle_balance is not set (i.e. we are doing a
+		 * SCHED_NORMAL/SCHED_BATCH balance) and this is a SCHED_IDLE
+		 * task
+		 * 3. If sched_idle_balance is set (i.e. we are doing a
+		 * SCHED_IDLE balance) and this is not a SCHED_IDLE task
+		 */
+		if (sd->flags & SD_IDLE_LOAD_BALANCE &&
+		    ((sched_idle_balance && p->policy != SCHED_IDLE) ||
+		    (!sched_idle_balance && p->policy == SCHED_IDLE)))
+			continue;
+
 		if (loops++ > sysctl_sched_nr_migrate)
 			break;
 
@@ -3097,6 +3111,119 @@ out_unlock:
 	return 0;
 }
 
+/*
+ * SCHED_IDLE balancing functions
+ */
+unsigned long scale_norm_power(int cpu)
+{
+	struct rq *rq = cpu_rq(cpu);
+	u64 total, available;
+
+	sched_avg_update(rq);
+
+	total = sched_avg_period() + (rq->clock - rq->age_stamp);
+	available = total - (rq->rt_avg + rq->norm_avg);
+
+	if (unlikely((s64)total < SCHED_LOAD_SCALE))
+		total = SCHED_LOAD_SCALE;
+
+	total >>= SCHED_LOAD_SHIFT;
+
+	return div_u64(available, total);
+}
+
+unsigned long sched_idle_cpu_load(struct rq *rq)
+{
+	unsigned long sched_idle_load, power = SCHED_LOAD_SCALE;
+
+	power *= scale_norm_power(cpu_of(rq));
+	power >>= SCHED_LOAD_SHIFT;
+
+	if (!power)
+		power = 1;
+
+	sched_idle_load = rq->idle_nr_running * WEIGHT_IDLEPRIO;
+
+	return div_u64(sched_idle_load * SCHED_LOAD_SCALE, power);
+}
+
+static struct rq *busiest_idle_balance_queue(struct sched_domain *sd,
+		int this_cpu, unsigned long *sched_idle_imbalance)
+{
+	struct rq *busiest = NULL;
+	unsigned long this_load = 0, max_load = 0;
+	unsigned long this_nr_running = 0, max_nr_running = 0;
+	int local_cpu, i;
+
+	for_each_cpu(i, sched_domain_span(sd)) {
+		struct rq *rq = cpu_rq(i);
+		unsigned long load, idle_nr_running;
+
+		local_cpu = (i == this_cpu);
+
+		load = sched_idle_cpu_load(rq);
+		idle_nr_running = rq->idle_nr_running;
+
+		if (local_cpu) {
+			this_load = load;
+			this_nr_running = idle_nr_running;
+		} else if (load > max_load) {
+			busiest = rq;
+			max_load = load;
+			max_nr_running = idle_nr_running;
+		}
+	}
+
+	if (!busiest || max_nr_running < 1)
+		goto out_balanced;
+
+	if (this_load > max_load)
+		goto out_balanced;
+
+	*sched_idle_imbalance = (max_load - this_load) / 2;
+
+	if (100 * max_load <= sd->imbalance_pct * this_load)
+		goto out_balanced;
+
+	return busiest;
+
+out_balanced:
+	*sched_idle_imbalance = 0;
+	return NULL;
+}
+
+static int sched_idle_load_balance(int this_cpu, struct rq *this_rq,
+		struct sched_domain *sd, enum cpu_idle_type idle)
+{
+	struct rq *busiest = NULL;
+	unsigned long sched_idle_imbalance;
+	int ld_moved;
+
+	busiest = busiest_idle_balance_queue(sd, this_cpu,
+			&sched_idle_imbalance);
+	if (!busiest)
+		return 0;
+
+	WARN_ON(busiest == this_rq);
+
+	if (busiest->idle_nr_running > 1) {
+		unsigned long flags;
+		int ld_moved, tmp = 0;
+
+		local_irq_save(flags);
+		double_rq_lock(this_rq, busiest);
+		ld_moved = move_tasks(this_rq, this_cpu, busiest,
+				sched_idle_imbalance, sd, idle, &tmp, 1);
+		double_rq_unlock(this_rq, busiest);
+		local_irq_restore(flags);
+
+		if (ld_moved && this_cpu != smp_processor_id())
+			resched_cpu(this_cpu);
+	}
+
+	return ld_moved;
+}
+
 #ifdef CONFIG_NO_HZ
 static struct {
 	atomic_t load_balancer;
@@ -3330,6 +3457,7 @@ static void rebalance_domains(int cpu, enum cpu_idle_type idle)
 	unsigned long next_balance = jiffies + 60*HZ;
 	int update_next_balance = 0;
 	int need_serialize;
+	int do_sched_idle_balance = 0;
 
 	for_each_domain(cpu, sd) {
 		if (!(sd->flags & SD_LOAD_BALANCE))
@@ -3363,6 +3491,7 @@ static void rebalance_domains(int cpu, enum cpu_idle_type idle)
 				idle = CPU_NOT_IDLE;
 			}
 			sd->last_balance = jiffies;
+			do_sched_idle_balance = 1;
 		}
 		if (need_serialize)
 			spin_unlock(&balancing);
@@ -3388,6 +3517,17 @@ out:
 	 */
 	if (likely(update_next_balance))
 		rq->next_balance = next_balance;
+
+	if (do_sched_idle_balance)
+		for_each_domain(cpu, sd) {
+			/*
+			 * Skip SCHED_IDLE balance on domains where
+			 * SD_LOAD_BALANCE is not set
+			 */
+			if (!(sd->flags & SD_IDLE_LOAD_BALANCE))
+				continue;
+			sched_idle_load_balance(cpu, rq, sd, idle);
+		}
 }
 
 /*
-- 
1.7.1

[PATCH 6/6] sched: enable SD_IDLE_LOAD_BALANCE on MC, CPU and NUMA (x86) domains

[Nikhil Rao]

Enable SD_IDLE_LOAD_BALANCE on MC, CPU and NUMA for x86. This sched
flag enables the idle load balancer on these scheduling domains.

Signed-off-by: Nikhil Rao <ncrao@google.com>
---
 arch/x86/include/asm/topology.h |    2 +-
 include/linux/topology.h        |    4 ++--
 2 files changed, 3 insertions(+), 3 deletions(-)

diff --git a/arch/x86/include/asm/topology.h b/arch/x86/include/asm/topology.h
index 9f29b4e..8b27b3f 100644
--- a/arch/x86/include/asm/topology.h
+++ b/arch/x86/include/asm/topology.h
@@ -150,7 +150,7 @@ extern unsigned long node_remap_size[];
 				| 0*SD_SHARE_PKG_RESOURCES		\
 				| 1*SD_SERIALIZE			\
 				| 0*SD_PREFER_SIBLING			\
-				| 0*SD_IDLE_LOAD_BALANCE		\
+				| 1*SD_IDLE_LOAD_BALANCE		\
 				,					\
 	.last_balance		= jiffies,				\
 	.balance_interval	= 1,					\
diff --git a/include/linux/topology.h b/include/linux/topology.h
index 97fbb1b..cef87aa 100644
--- a/include/linux/topology.h
+++ b/include/linux/topology.h
@@ -135,7 +135,7 @@ int arch_update_cpu_topology(void);
 				| 0*SD_SHARE_CPUPOWER			\
 				| 1*SD_SHARE_PKG_RESOURCES		\
 				| 0*SD_SERIALIZE			\
-				| 0*SD_IDLE_LOAD_BALANCE		\
+				| 1*SD_IDLE_LOAD_BALANCE		\
 				| sd_balance_for_mc_power()		\
 				| sd_power_saving_flags()		\
 				,					\
@@ -169,7 +169,7 @@ int arch_update_cpu_topology(void);
 				| 0*SD_SHARE_CPUPOWER			\
 				| 0*SD_SHARE_PKG_RESOURCES		\
 				| 0*SD_SERIALIZE			\
-				| 0*SD_IDLE_LOAD_BALANCE		\
+				| 1*SD_IDLE_LOAD_BALANCE		\
 				| sd_balance_for_package_power()	\
 				| sd_power_saving_flags()		\
 				,					\
-- 
1.7.1

Re: [PATCH 0/6] [RFC] Large weight differential leads to inefficient load balancing

[Mike Galbraith]

On Thu, 2010-07-29 at 22:19 -0700, Nikhil Rao wrote:
> Hi all,
> 
> We have observed that a large weight differential between tasks on a runqueue
> leads to sub-optimal machine utilization and poor load balancing. For example,
> if you have lots of SCHED_IDLE tasks (sufficient number to keep the machine 100%
> busy) and a few SCHED_NORMAL soaker tasks, we see that the machine has
> significant idle time.
> 
> The data below highlights this problem. The test machine is a 4 socket quad-core
> box (16 cpus). These experiemnts were done with v2.6.25-rc6. We spawn 16
> SCHED_IDLE soaker threads (one per-cpu) to completely fill up the machine. CPU
> utilization numbers gathered from mpstat for 10s are:
> 
> 03:30:24 PM  CPU   %user   %nice    %sys %iowait    %irq   %soft  %steal   %idle    intr/s
> 03:30:25 PM  all   99.94    0.00    0.06    0.00    0.00    0.00    0.00    0.00  16234.65
> 03:30:26 PM  all   99.88    0.06    0.06    0.00    0.00    0.00    0.00    0.00  16374.00
> 03:30:27 PM  all   99.94    0.00    0.06    0.00    0.00    0.00    0.00    0.00  16392.00
> 03:30:28 PM  all   99.94    0.00    0.06    0.00    0.00    0.00    0.00    0.00  16612.12
> 03:30:29 PM  all   99.88    0.00    0.12    0.00    0.00    0.00    0.00    0.00  16375.00
> 03:30:30 PM  all   99.94    0.06    0.00    0.00    0.00    0.00    0.00    0.00  16440.00
> 03:30:31 PM  all   99.81    0.00    0.19    0.00    0.00    0.00    0.00    0.00  16237.62
> 03:30:32 PM  all   99.94    0.00    0.06    0.00    0.00    0.00    0.00    0.00  16360.00
> 03:30:33 PM  all   99.94    0.00    0.06    0.00    0.00    0.00    0.00    0.00  16405.00
> 03:30:34 PM  all   99.38    0.06    0.50    0.00    0.00    0.00    0.00    0.06  18881.82
> Average:     all   99.86    0.02    0.12    0.00    0.00    0.00    0.00    0.01  16628.20
> 
> We then spawn one SCHED_NORMAL while-1 task (the absolute number does not matter
> so long as we introduce some large weight differential).
> 
> 03:40:57 PM  CPU   %user   %nice    %sys %iowait    %irq   %soft  %steal   %idle    intr/s
> 03:40:58 PM  all   83.06    0.00    0.06    0.00    0.00    0.00    0.00   16.88  14555.00
> 03:40:59 PM  all   78.25    0.00    0.06    0.00    0.00    0.00    0.00   21.69  14527.00
> 03:41:00 PM  all   82.71    0.06    0.06    0.00    0.00    0.00    0.00   17.17  14879.00
> 03:41:01 PM  all   87.34    0.00    0.06    0.00    0.00    0.00    0.00   12.59  15466.00
> 03:41:02 PM  all   80.80    0.06    0.19    0.00    0.00    0.00    0.00   18.95  14584.00
> 03:41:03 PM  all   82.90    0.00    0.06    0.00    0.00    0.00    0.00   17.04  14570.00
> 03:41:04 PM  all   79.45    0.00    0.06    0.00    0.00    0.00    0.00   20.49  14536.00
> 03:41:05 PM  all   86.48    0.00    0.07    0.00    0.00    0.00    0.00   13.46  14577.00
> 03:41:06 PM  all   76.73    0.06    0.06    0.00    0.00    0.06    0.00   23.10  14594.00
> 03:41:07 PM  all   86.48    0.00    0.07    0.00    0.00    0.00    0.00   13.45  14703.03
> Average:     all   82.31    0.02    0.08    0.00    0.00    0.01    0.00   17.59  14699.10

What happens with s/SCHED_IDLE/nice 19?

	-Mike

Re: [PATCH 0/6] [RFC] Large weight differential leads to inefficient load balancing

[Nikhil Rao]

On Fri, Jul 30, 2010 at 6:32 AM, Mike Galbraith <efault@gmx.de> wrote:
> On Thu, 2010-07-29 at 22:19 -0700, Nikhil Rao wrote:
>> Hi all,
>>
>> We have observed that a large weight differential between tasks on a runqueue
>> leads to sub-optimal machine utilization and poor load balancing. For example,
>> if you have lots of SCHED_IDLE tasks (sufficient number to keep the machine 100%
>> busy) and a few SCHED_NORMAL soaker tasks, we see that the machine has
>> significant idle time.
>>
>> The data below highlights this problem. The test machine is a 4 socket quad-core
>> box (16 cpus). These experiemnts were done with v2.6.25-rc6. We spawn 16
>> SCHED_IDLE soaker threads (one per-cpu) to completely fill up the machine. CPU
>> utilization numbers gathered from mpstat for 10s are:
>>
>> 03:30:24 PM  CPU   %user   %nice    %sys %iowait    %irq   %soft  %steal   %idle    intr/s
>> 03:30:25 PM  all   99.94    0.00    0.06    0.00    0.00    0.00    0.00    0.00  16234.65
>> 03:30:26 PM  all   99.88    0.06    0.06    0.00    0.00    0.00    0.00    0.00  16374.00
>> 03:30:27 PM  all   99.94    0.00    0.06    0.00    0.00    0.00    0.00    0.00  16392.00
>> 03:30:28 PM  all   99.94    0.00    0.06    0.00    0.00    0.00    0.00    0.00  16612.12
>> 03:30:29 PM  all   99.88    0.00    0.12    0.00    0.00    0.00    0.00    0.00  16375.00
>> 03:30:30 PM  all   99.94    0.06    0.00    0.00    0.00    0.00    0.00    0.00  16440.00
>> 03:30:31 PM  all   99.81    0.00    0.19    0.00    0.00    0.00    0.00    0.00  16237.62
>> 03:30:32 PM  all   99.94    0.00    0.06    0.00    0.00    0.00    0.00    0.00  16360.00
>> 03:30:33 PM  all   99.94    0.00    0.06    0.00    0.00    0.00    0.00    0.00  16405.00
>> 03:30:34 PM  all   99.38    0.06    0.50    0.00    0.00    0.00    0.00    0.06  18881.82
>> Average:     all   99.86    0.02    0.12    0.00    0.00    0.00    0.00    0.01  16628.20
>>
>> We then spawn one SCHED_NORMAL while-1 task (the absolute number does not matter
>> so long as we introduce some large weight differential).
>>
>> 03:40:57 PM  CPU   %user   %nice    %sys %iowait    %irq   %soft  %steal   %idle    intr/s
>> 03:40:58 PM  all   83.06    0.00    0.06    0.00    0.00    0.00    0.00   16.88  14555.00
>> 03:40:59 PM  all   78.25    0.00    0.06    0.00    0.00    0.00    0.00   21.69  14527.00
>> 03:41:00 PM  all   82.71    0.06    0.06    0.00    0.00    0.00    0.00   17.17  14879.00
>> 03:41:01 PM  all   87.34    0.00    0.06    0.00    0.00    0.00    0.00   12.59  15466.00
>> 03:41:02 PM  all   80.80    0.06    0.19    0.00    0.00    0.00    0.00   18.95  14584.00
>> 03:41:03 PM  all   82.90    0.00    0.06    0.00    0.00    0.00    0.00   17.04  14570.00
>> 03:41:04 PM  all   79.45    0.00    0.06    0.00    0.00    0.00    0.00   20.49  14536.00
>> 03:41:05 PM  all   86.48    0.00    0.07    0.00    0.00    0.00    0.00   13.46  14577.00
>> 03:41:06 PM  all   76.73    0.06    0.06    0.00    0.00    0.06    0.00   23.10  14594.00
>> 03:41:07 PM  all   86.48    0.00    0.07    0.00    0.00    0.00    0.00   13.45  14703.03
>> Average:     all   82.31    0.02    0.08    0.00    0.00    0.01    0.00   17.59  14699.10
>
> What happens with s/SCHED_IDLE/nice 19?
>
>        -Mike

We see the same result with nice 19 as well.

w/ 16 nice-19 soakers:

10:15:16 AM  CPU   %user   %nice    %sys %iowait    %irq   %soft
%steal   %idle    intr/s
10:15:17 AM  all    0.06   99.94    0.00    0.00    0.00    0.00
0.00    0.00  16296.04
10:15:18 AM  all    0.00   99.94    0.06    0.00    0.00    0.00
0.00    0.00  16379.00
10:15:19 AM  all    0.00   99.94    0.06    0.00    0.00    0.00
0.00    0.00  16414.00
10:15:20 AM  all    0.00   99.94    0.06    0.00    0.00    0.00
0.00    0.00  16413.00
10:15:21 AM  all    0.00  100.00    0.00    0.00    0.00    0.00
0.00    0.00  16402.00
10:15:22 AM  all    0.00   99.88    0.06    0.00    0.00    0.06
0.00    0.00  16419.00
10:15:23 AM  all    0.00   99.94    0.06    0.00    0.00    0.00
0.00    0.00  16406.00
10:15:24 AM  all    0.19   99.69    0.12    0.00    0.00    0.00
0.00    0.00  16613.13
10:15:25 AM  all    0.38   99.31    0.31    0.00    0.00    0.00
0.00    0.00  16313.86
10:15:26 AM  all    0.50   99.31    0.19    0.00    0.00    0.00
0.00    0.00  16623.23
Average:     all    0.11   99.79    0.09    0.00    0.00    0.01
0.00    0.00  16427.30

w/ adding a SCHED_NORMAL soaker to the mix:

10:17:44 AM  CPU   %user   %nice    %sys %iowait    %irq   %soft
%steal   %idle    intr/s
10:17:45 AM  all    6.20   74.38    0.06    0.00    0.00    0.00
0.00   19.35  14419.80
10:17:46 AM  all    6.25   74.89    0.06    0.00    0.00    0.00
0.00   18.80  14619.00
10:17:47 AM  all    6.30   74.84    0.06    0.00    0.00    0.00
0.00   18.79  14590.00
10:17:48 AM  all    6.25   80.57    0.06    0.00    0.00    0.00
0.00   13.12  15511.00
10:17:49 AM  all    6.51   80.33    0.07    0.00    0.00    0.00
0.00   13.09  14904.00
10:17:50 AM  all    6.06   72.62    0.06    0.00    0.00    0.00
0.00   21.26  14564.00
10:17:51 AM  all    6.21   74.47    0.06    0.00    0.00    0.00
0.00   19.25  14584.00
10:17:52 AM  all    6.47   77.67    0.12    0.00    0.00    0.00
0.00   15.73  15295.96
10:17:53 AM  all    6.27   79.39    0.06    0.00    0.00    0.00
0.00   14.29  15251.00
10:17:54 AM  all    6.32   75.85    0.00    0.00    0.00    0.00
0.00   17.83  14537.00
Average:     all    6.28   76.47    0.06    0.00    0.00    0.00
0.00   17.18  14826.70

The problem is the large weight differential between nice
19/SCHED_IDLE and SCHED_NORMAL. I ran a quick experiment with the
soaker tasks at different nice levels. Data is in the table below.
First column is nice level, second is idle% on the machine (mpstat 10s
average) and third is ratio of nice weight/1024.

0          0.00          1
1          0.00          0.800781
2          0.00          0.639648
3          0.00          0.513672
4          0.00          0.413086
5          0.17          0.327148
6          1.06          0.265625
7          7.62          0.209961
8          4.47          0.167969
9          11.78          0.133789
10          13.52          0.107422
11          14.92          0.0849609
12          14.33          0.0683594
13          17.47          0.0546875
14          15.89          0.0439453
15          18.69          0.0351562
16          16.63          0.0283203
17          17.04          0.0224609
18          17.86          0.0175781
19          18.13          0.0146484

It looks like we start seeing seeing sub-optimal performance when the
weight ratio is >0.3.

-Thanks,
Nikhil

Re: [PATCH 0/6] [RFC] Large weight differential leads to inefficient load balancing

[Paul Turner]

On Fri, Jul 30, 2010 at 6:32 AM, Mike Galbraith <efault@gmx.de> wrote:
> On Thu, 2010-07-29 at 22:19 -0700, Nikhil Rao wrote:
>> Hi all,
>>
>> We have observed that a large weight differential between tasks on a runqueue
>> leads to sub-optimal machine utilization and poor load balancing. For example,
>> if you have lots of SCHED_IDLE tasks (sufficient number to keep the machine 100%
>> busy) and a few SCHED_NORMAL soaker tasks, we see that the machine has
>> significant idle time.
>>
>> The data below highlights this problem. The test machine is a 4 socket quad-core
>> box (16 cpus). These experiemnts were done with v2.6.25-rc6. We spawn 16
>> SCHED_IDLE soaker threads (one per-cpu) to completely fill up the machine. CPU
>> utilization numbers gathered from mpstat for 10s are:
>>
>> 03:30:24 PM  CPU   %user   %nice    %sys %iowait    %irq   %soft  %steal   %idle    intr/s
>> 03:30:25 PM  all   99.94    0.00    0.06    0.00    0.00    0.00    0.00    0.00  16234.65
>> 03:30:26 PM  all   99.88    0.06    0.06    0.00    0.00    0.00    0.00    0.00  16374.00
>> 03:30:27 PM  all   99.94    0.00    0.06    0.00    0.00    0.00    0.00    0.00  16392.00
>> 03:30:28 PM  all   99.94    0.00    0.06    0.00    0.00    0.00    0.00    0.00  16612.12
>> 03:30:29 PM  all   99.88    0.00    0.12    0.00    0.00    0.00    0.00    0.00  16375.00
>> 03:30:30 PM  all   99.94    0.06    0.00    0.00    0.00    0.00    0.00    0.00  16440.00
>> 03:30:31 PM  all   99.81    0.00    0.19    0.00    0.00    0.00    0.00    0.00  16237.62
>> 03:30:32 PM  all   99.94    0.00    0.06    0.00    0.00    0.00    0.00    0.00  16360.00
>> 03:30:33 PM  all   99.94    0.00    0.06    0.00    0.00    0.00    0.00    0.00  16405.00
>> 03:30:34 PM  all   99.38    0.06    0.50    0.00    0.00    0.00    0.00    0.06  18881.82
>> Average:     all   99.86    0.02    0.12    0.00    0.00    0.00    0.00    0.01  16628.20
>>
>> We then spawn one SCHED_NORMAL while-1 task (the absolute number does not matter
>> so long as we introduce some large weight differential).
>>
>> 03:40:57 PM  CPU   %user   %nice    %sys %iowait    %irq   %soft  %steal   %idle    intr/s
>> 03:40:58 PM  all   83.06    0.00    0.06    0.00    0.00    0.00    0.00   16.88  14555.00
>> 03:40:59 PM  all   78.25    0.00    0.06    0.00    0.00    0.00    0.00   21.69  14527.00
>> 03:41:00 PM  all   82.71    0.06    0.06    0.00    0.00    0.00    0.00   17.17  14879.00
>> 03:41:01 PM  all   87.34    0.00    0.06    0.00    0.00    0.00    0.00   12.59  15466.00
>> 03:41:02 PM  all   80.80    0.06    0.19    0.00    0.00    0.00    0.00   18.95  14584.00
>> 03:41:03 PM  all   82.90    0.00    0.06    0.00    0.00    0.00    0.00   17.04  14570.00
>> 03:41:04 PM  all   79.45    0.00    0.06    0.00    0.00    0.00    0.00   20.49  14536.00
>> 03:41:05 PM  all   86.48    0.00    0.07    0.00    0.00    0.00    0.00   13.46  14577.00
>> 03:41:06 PM  all   76.73    0.06    0.06    0.00    0.00    0.06    0.00   23.10  14594.00
>> 03:41:07 PM  all   86.48    0.00    0.07    0.00    0.00    0.00    0.00   13.45  14703.03
>> Average:     all   82.31    0.02    0.08    0.00    0.00    0.01    0.00   17.59  14699.10
>
> What happens with s/SCHED_IDLE/nice 19?
>
>        -Mike
>
>

So this is also a concern of mine that I wanted to raise.

The problem observed above is a function of balancing entities which
can't meaningfully contribute to improving the observed imbalance.

While this does occur with {nice 19, SCHED_IDLE} threads, it is a more
general problem and actually much more prevalent in the group
scheduling case where the group entity weight is more arbitrary.  This
is compounded by the fact that we iterate over the task_groups in load
balance and don't have a good way of differentiating in-group high/low
weight entities.

Something I have been investigating is how can we fix this problem
more generally: e.g. how can we effectively load-balance a low-weight
entity in the presence of high-weight competition.  This could just as
easily be a {1000, 2} share split as it could be a {64000, 2000} share
split -- the latter won't benefit from IDLE_SCHEDULING optimizations
but is a realistic test case if someone is trying to provide minimal
latencies for the high-weight task.

What I've been considering in avenue is instead of load-balancing the
low weight entities when their h_load relative to the imbalance is
'not meaningful' -- by some fitness function, tag them for a separate
load-balancing pass.  This secondary pass would only need to be
periodic in nature, and consider the 'tagged' task_groups from the
generic load_balancing operations.  At this point in time it can be
evaluated whether the load is still 'not meaningful', and distribution
towards the most idle cpu (by utilization) can be evaluated.

The one converse here is that while something like the above is more
general for the low weight-group entity case, it does not extend
particularly cleanly to the non group-scheduling case.  I haven't yet
got a particularly good answer for this since without a group entity
representing the low-weight threads tracking them for a second pass
becomes more cumbersome.

Re: [PATCH 0/6] [RFC] Large weight differential leads to inefficient load balancing

[Peter Zijlstra]

On Thu, 2010-07-29 at 22:19 -0700, Nikhil Rao wrote:
> If folks think this is a good direction and this idea has some merit, then I
> will be more than happy to continue working with the community to improve this
> patchset. If there is another way to fix this problem, then please do tell; I
> would be more than happy to help out.


No its terrible. I've already explained how to solve this on several
occasions (although my google skillz seem to fail me to find the latest
occasion a few months ago).

The thing is that from a fairness point of view 1 nice-0 (weight=1024)
on one CPU and 512 SCHED_IDLE (weight=2) tasks on another CPU and all
other CPUs idle is correct.

It just doesn't seem to be the thing that most people expect.

Special casing things like you've done is utterly the wrong thing to do.

This problem comes in two forms and its name is infeasible weight
distribution. The load-balancer tries to ensure W_k ~= W_l, k,l elem_of
CPUs, where W_k = \Sum_i w_i^k, where w_i^k is the i-th task on CPU k.

The two cases are statically infeasible, and dynamically infeasible. 

We say the task-set is statically infeasible if for a task set of n
tasks there is no way to statically distribute them on N <= n CPUs such
that each task gets equal service (assuming the scheduling on each CPU
is fair).

We say the task-set is dynamically infeasible if for the given scenario
there is no way to rotate the tasks to obtain equality.

Lets assume 2 CPUs.

Ex.1: 2 tasks of different weight.

Ex.2: 3 tasks of equal weight.

The first example is both statically and dynamically infeasible as there
is no way to occupy both CPUs such that each task gets the proportional
correct service.

The second example is statically infeasible, but dynamically feasible,
for if we rotate one task, such that we alternate between 2:1 and 1:2 in
equal measures, each task will receive its correct 2/3rd CPU service.

The current load-balancer isn't particularly skilled at either issue.

The proper solution is to 'fix' find_busiest_group() so that it will:
 - pick the heaviest cpu with more than 1 task on it
 - slowly over-balance things

The first thing will solve your issue.

Re: [PATCH 0/6] [RFC] Large weight differential leads to inefficient load balancing

[Nikhil Rao]

Peter,

Thanks for the feedback!

On Mon, Aug 2, 2010 at 4:39 AM, Peter Zijlstra <peterz@infradead.org> wrote:
> The thing is that from a fairness point of view 1 nice-0 (weight=1024)
> on one CPU and 512 SCHED_IDLE (weight=2) tasks on another CPU and all
> other CPUs idle is correct.
>
> It just doesn't seem to be the thing that most people expect.
>
> Special casing things like you've done is utterly the wrong thing to do.
>

I see your point here, and yes I agree having 1 nice-0 on one cpu, 512
SCHED_IDLE tasks on another cpu and all other cpus idle is correct if
we only considered fairness. However, we would also like to maximize
machine utilization. The fitness function we would ideally like to
optimize for is a combination of both fairness and utilization.

I'm going to take a step back here and explain the bigger problem we
are trying to solve. We have two types of workloads -- high priority
tasks that need to run for short periods of time and can consume as
much cpu as required when they run; and low priority tasks that
ideally consume slack cpu. Let's say we had a machine with enough
tasks to soak up all the cpus. There are two cases to implement the
priority scheme.

The first case is to run all tasks run as SCHED_NORMAL. The machine is
fully utilized but this has other side-effects. Low priority tasks
consume much more cpu than we would like, they get to preempt high
priority tasks, and this results in poor performance of high priority
tasks.

The second case is to run high priority tasks as SCHED_NORMAL and low
priority tasks as SCHED_IDLE. We choose SCHED_IDLE to minimize
interference with high priority tasks -- we don't want low priority
tasks to preempt high priority or to be favored over high priority
tasks in any way. When there are high priority tasks, we want low
priority tasks to get as little cpu as possible; thus giving them the
minimum possible weight works out well. In this case, we are able to
isolate high prio tasks from low prio tasks reasonably well. However,
sub-optimal machine utilization defeats the purpose of packing a
machine with lots of low priority tasks as we are not able to consume
the slack cpu.

This RFC is really meant to explain the problem that we are facing. We
presented one possible solution to fix this but we are also open to
other suggestions and ideas.

> This problem comes in two forms and its name is infeasible weight
> distribution. The load-balancer tries to ensure W_k ~= W_l, k,l elem_of
> CPUs, where W_k = \Sum_i w_i^k, where w_i^k is the i-th task on CPU k.
>
> The two cases are statically infeasible, and dynamically infeasible.
>
> We say the task-set is statically infeasible if for a task set of n
> tasks there is no way to statically distribute them on N <= n CPUs such
> that each task gets equal service (assuming the scheduling on each CPU
> is fair).
>
> We say the task-set is dynamically infeasible if for the given scenario
> there is no way to rotate the tasks to obtain equality.
>
> Lets assume 2 CPUs.
>
> Ex.1: 2 tasks of different weight.
>
> Ex.2: 3 tasks of equal weight.
>
> The first example is both statically and dynamically infeasible as there
> is no way to occupy both CPUs such that each task gets the proportional
> correct service.
>
> The second example is statically infeasible, but dynamically feasible,
> for if we rotate one task, such that we alternate between 2:1 and 1:2 in
> equal measures, each task will receive its correct 2/3rd CPU service.
>
> The current load-balancer isn't particularly skilled at either issue.
>
> The proper solution is to 'fix' find_busiest_group() so that it will:
>  - pick the heaviest cpu with more than 1 task on it
>  - slowly over-balance things
>
> The first thing will solve your issue.
>

Thanks for your suggestions; I explored the first one a bit and I
added a check into find_busiest_queue() (instead of
find_busiest_group()) to skip a cpu if it has only 1 task on it (patch
attached below - did you have something else in mind?). This fixes the
example I posted in the RFC, but it doesn't work as well when the
SCHED_NORMAL tasks have a sleep/wakeup pattern. I have some data below
where the load balancer fails to fully utilize a machine. In these
examples, I ran with the upstream kernel and with a kernel compiled
with the check in fbq().

Setup: We run 16 SCHED_IDLE soakers and about half as many
SCHED_NORMAL tasks which have 100ms / 100ms sleep/busy cycles. This is
actually a very common use case that we run into.

2.6.35-rc6

12:41:45 PM  CPU   %user   %nice    %sys %iowait    %irq   %soft
%steal   %idle    intr/s
12:41:46 PM  all   97.50    0.00    0.00    0.00    0.00    0.00
0.00    2.50  16405.00
12:41:47 PM  all   89.72    0.00    0.06    0.00    0.00    0.00
0.00   10.22  15736.00
12:41:48 PM  all   90.54    0.06    0.06    0.00    0.00    0.00
0.00    9.34  15791.09
12:41:49 PM  all   93.00    0.00    0.06    0.00    0.00    0.00
0.00    6.93  15816.83
12:41:50 PM  all   96.44    0.00    0.06    0.00    0.00    0.06
0.00    3.44  16362.00
12:41:51 PM  all   97.62    0.00    0.06    0.00    0.00    0.00
0.00    2.31  16326.00
12:41:52 PM  all   99.56    0.00    0.06    0.00    0.00    0.00
0.00    0.38  16512.12
12:41:53 PM  all   99.06    0.00    0.06    0.00    0.00    0.00
0.00    0.88  16289.00
12:41:54 PM  all   99.50    0.00    0.06    0.00    0.00    0.00
0.00    0.44  16149.50
12:41:55 PM  all   98.06    0.00    0.06    0.00    0.00    0.00
0.00    1.88  16405.05
Average:     all   96.10    0.01    0.06    0.00    0.00    0.01
0.00    3.83  16177.92

2.6.35-rc6 + fbg-fix

12:42:48 PM  CPU   %user   %nice    %sys %iowait    %irq   %soft
%steal   %idle    intr/s
12:42:49 PM  all   98.07    0.00    0.06    0.00    0.00    0.00
0.00    1.87  16346.00
12:42:50 PM  all   98.75    0.00    0.12    0.00    0.00    0.00
0.00    1.12  16236.63
12:42:51 PM  all   99.56    0.06    0.19    0.00    0.00    0.00
0.00    0.19  16616.16
12:42:52 PM  all   97.94    0.00    0.06    0.00    0.00    0.06
0.00    1.94  16348.00
12:42:53 PM  all   96.94    0.00    0.25    0.00    0.00    0.00
0.00    2.81  16234.65
12:42:54 PM  all   98.56    0.06    0.06    0.00    0.00    0.00
0.00    1.31  16339.00
12:42:55 PM  all   97.56    0.00    0.19    0.00    0.00    0.00
0.00    2.25  16570.71
12:42:56 PM  all   99.50    0.00    0.06    0.00    0.00    0.00
0.00    0.44  16400.00
12:42:57 PM  all   95.25    0.00    0.37    0.00    0.00    0.00
0.00    4.37  16367.00
12:42:58 PM  all   97.75    0.00    0.06    0.00    0.00    0.00
0.00    2.19  16409.00
Average:     all   97.99    0.01    0.14    0.00    0.00    0.01
0.00    1.85  16386.00

-Thanks,
Nikhil

---
fqb-fix patch:

diff --git a/kernel/sched_fair.c b/kernel/sched_fair.c
index a878b53..e05c61f 100644
--- a/kernel/sched_fair.c
+++ b/kernel/sched_fair.c
@@ -2742,13 +2742,8 @@ find_busiest_queue(struct sched_group *group,
enum cpu_idle_type idle,
                        continue;

                rq = cpu_rq(i);
-               wl = weighted_cpuload(i);

-               /*
-                * When comparing with imbalance, use weighted_cpuload()
-                * which is not scaled with the cpu power.
-                */
-               if (capacity && rq->nr_running == 1 && wl > imbalance)
+               if (capacity && rq->nr_running == 1)
                        continue;

                /*
@@ -2757,6 +2752,7 @@ find_busiest_queue(struct sched_group *group,
enum cpu_idle_type idle,
                 * the load can be moved away from the cpu that is potentially
                 * running at a lower capacity.
                 */
+               wl = weighted_cpuload(i);
                wl = (wl * SCHED_LOAD_SCALE) / power;

                if (wl > max_load) {

Re: [PATCH 0/6] [RFC] Large weight differential leads to inefficient load balancing

[Peter Zijlstra]

On Tue, 2010-08-03 at 14:28 -0700, Nikhil Rao wrote:

> I see your point here, and yes I agree having 1 nice-0 on one cpu, 512
> SCHED_IDLE tasks on another cpu and all other cpus idle is correct if
> we only considered fairness. However, we would also like to maximize
> machine utilization. The fitness function we would ideally like to
> optimize for is a combination of both fairness and utilization.

Sure, I see (and agree with) the fact that we want to optimize
utilization as well (although I bet the power management people might
feel otherwise :-)

> Thanks for your suggestions; I explored the first one a bit and I
> added a check into find_busiest_queue() (instead of
> find_busiest_group()) to skip a cpu if it has only 1 task on it (patch
> attached below - did you have something else in mind?). 

You might also need some changes to find_busiest_group(), suppose you
have a 4 cpu machine, with 2 groups of 2, now also assume you have 4
tasks, 2 of nice-0 and 2 idle, if both nice-0 are in the same group,
each on their own cpu, then f_b_g() could select that group as being the
busiest (its got W=2048, against W=4 of the other group after all).

Once you have that group, f_b_q() won't be able to do anything sensible.

> This fixes the
> example I posted in the RFC, but it doesn't work as well when the
> SCHED_NORMAL tasks have a sleep/wakeup pattern. I have some data below
> where the load balancer fails to fully utilize a machine. In these
> examples, I ran with the upstream kernel and with a kernel compiled
> with the check in fbq().

Right, so wakeup/sleep are indeed more interesting. For wakeup we also
have select_task_rq() to consider, it is responsible to choosing where
to run the newly woken task.

For sleeps we have new idle balancing, which is a lot like the regular
load-balancing but differs enough to need looking at.

>From the data you provided I cannot tell you which of these two is
responsible for the thing you see (although under-utilization suggests
the new-idle balancer), you can use perf/ftrace to look at what your
tasks are doing and how they could be doing it better (Arjan's timechart
might be a good help).

If they get woken to the wrong CPU, its select_task_rq(), if they leave
a CPU idle too long, its new idle balancing -- or possibly its something
I overlooked all together :-)