Skip to contentSkip to conversation

VST and Sched Load Balance

PATCH Srivatsa Vaddagiri 4 participants 12 messages Apr 7, 2005 – May 5, 2005 Scheduler

lore
Share & tools
lore
#0 lore raw

Hi,
VST patch (http://lwn.net/Articles/118693/) attempts to avoid useless
regular (local) timer ticks when a CPU is idle.

I think a potential area which VST may need to address is scheduler load balance. If idle CPUs stop taking local timer ticks for some time, then during that period it could cause the various runqueues to go out of balance, since the idle CPUs will no longer pull tasks from non-idle CPUs.

Do we care about this imbalance? Especially considering that most implementations will let the idle CPUs sleep only for some max duration (~900 ms in case of x86).

If we do care about this imbalance, then we could hope that the balance logic present in try_to_wake_up and sched_exec may avoid this imbalance, but can we bank upon these events to restore the runqueue balance?

If we cannot, then I had something in mind on these lines:

1. A non-idle CPU (having nr_running > 1) can wakeup a idle sleeping CPU if it finds that the sleeping CPU has not balanced itself for it's "balance_interval" period.

2. It would be nice to minimize the "cross-domain" wakeups. For ex: we may want to avoid a non-idle CPU in node B sending a wakeup to a idle sleeping CPU in another node A, when this wakeup could have been sent from another non-idle CPU in node A itself.

That is why I have imposed the condition for sending wakeup only when
a whole sched_group of CPUs are sleeping in a domain. We wake one of them up. The chosen one is one which has not balanced itself for "balance_interval" period.

I did think about avoiding all these and putting some hooks in wake_up_new_task, to wakeup the sleeping CPUs. But the problem is the woken-up CPU may refuse to pull any tasks and go to sleep again if it has balanced itself in the domain "recently" (balance_interval).

Comments?

Patch (not fully-tested) against 2.6.11 follows.

---

 linux-2.6.11-vatsa/kernel/sched.c |   52 ++++++++++++++++++++++++++++++++++++++
 1 files changed, 52 insertions(+)
kernel/sched.c renamed from kernel/sched.c~vst-sched_load_balance +52 -0
diff -puN kernel/sched.c~vst-sched_load_balance kernel/sched.c
@@ -1774,9 +1774,17 @@ find_busiest_group(struct sched_domain *
 {
 	struct sched_group *busiest = NULL, *this = NULL, *group = sd->groups;
 	unsigned long max_load, avg_load, total_load, this_load, total_pwr;
+#ifdef CONFIG_VST
+	int grp_sleeping;
+	cpumask_t tmpmask, wakemask;
+#endif
 
 	max_load = this_load = total_load = total_pwr = 0;
 
+#ifdef CONFIG_VST
+	cpus_clear(wakemask);
+#endif
+
 	do {
 		unsigned long load;
 		int local_group;
@@ -1787,7 +1795,20 @@ find_busiest_group(struct sched_domain *
 		/* Tally up the load of all CPUs in the group */
 		avg_load = 0;
 
+#ifdef CONFIG_VST
+		grp_sleeping = 0;
+		cpus_and(tmpmask, group->cpumask, nohz_cpu_mask);
+		if (cpus_equal(tmpmask, group->cpumask))
+			grp_sleeping = 1;
+#endif
+
 		for_each_cpu_mask(i, group->cpumask) {
+#ifdef CONFIG_VST
+			int cpu = smp_processor_id();
+			struct sched_domain *sd1;
+			unsigned long interval;
+			int woken = 0;
+#endif
 			/* Bias balancing toward cpus of our domain */
 			if (local_group)
 				load = target_load(i);
@@ -1796,6 +1817,25 @@ find_busiest_group(struct sched_domain *
 
 			nr_cpus++;
 			avg_load += load;
+
+#ifdef CONFIG_VST
+			if (idle != NOT_IDLE || !grp_sleeping ||
+						(grp_sleeping && woken))
+				continue;
+
+			sd1 = sd + (i-cpu);
+			interval = sd1->balance_interval;
+
+			/* scale ms to jiffies */
+			interval = msecs_to_jiffies(interval);
+	                if (unlikely(!interval))
+        	                interval = 1;
+
+			if (jiffies - sd1->last_balance >= interval) {
+				woken = 1;
+				cpu_set(i, wakemask);
+			}
+#endif
 		}
 
 		if (!nr_cpus)
@@ -1819,6 +1859,18 @@ nextgroup:
 		group = group->next;
 	} while (group != sd->groups);
 
+#ifdef CONFIG_VST
+	if (idle == NOT_IDLE && this_load > SCHED_LOAD_SCALE) {
+		int i;
+
+		for_each_cpu_mask(i, wakemask) {
+			spin_lock(&cpu_rq(i)->lock);
+			resched_task(cpu_rq(i)->idle);
+			spin_unlock(&cpu_rq(i)->lock);
+		}
+	}
+#endif
+
 	if (!busiest || this_load >= max_load)
 		goto out_balanced;
 

_

Signature · 5 lines
Thanks and Regards,
Srivatsa Vaddagiri,
Linux Technology Center,
IBM Software Labs,
Bangalore, INDIA - 560017
#1 lore raw
Quoted 2 lines · Srivatsa Vaddagiri

I think a potential area which VST may need to address is scheduler load balance. If idle CPUs stop taking local timer ticks for some time, then during that period it could cause the various runqueues to go out of balance, since the idle CPUs will no longer pull tasks from non-idle CPUs.

Yep.

Quoted 3 lines

Do we care about this imbalance? Especially considering that most implementations will let the idle CPUs sleep only for some max duration (~900 ms in case of x86).

I think we do care, yes. It could be pretty harmful to sleep for even a few 10s of ms on a regular basis for some workloads. Although I guess many of those will be covered by try_to_wake_up events...

Not sure in practice, I would imagine it will hurt some multiprocessor workloads.

Quoted 5 lines

If we do care about this imbalance, then we could hope that the balance logic
present in try_to_wake_up and sched_exec may avoid this imbalance, but can we bank upon these events to restore the runqueue balance?

If we cannot, then I had something in mind on these lines:

Quoted 9 lines

1. A non-idle CPU (having nr_running > 1) can wakeup a idle sleeping CPU if it finds that the sleeping CPU has not balanced itself for it's "balance_interval" period.

2. It would be nice to minimize the "cross-domain" wakeups. For ex: we may want to avoid a non-idle CPU in node B sending a wakeup to a idle sleeping CPU in another node A, when this wakeup could have been sent from another non-idle CPU in node A itself.

3. This is exactly one of the situations that the balancing backoff code was designed for. Can you just schedule interrupts to fire when the next balance interval has passed? This may require some adjustments to the backoff code in order to get good powersaving, but it would be the cleanest approach from the scheduler's point of view.

Nick

Signature · 1 line
SUSE Labs, Novell Inc.
#2 lore raw
Quoted 5 lines · Nick Piggin

3. This is exactly one of the situations that the balancing backoff code was designed for. Can you just schedule interrupts to fire when the next balance interval has passed? This may require some adjustments to the backoff code in order to get good powersaving, but it would be the cleanest approach from the scheduler's point of view.

Hmm ..I guess we could restrict the max time a idle CPU will sleep taking into account its balance interval. But whatever heuristics we follow to maximize balance_interval of about-to-sleep idle CPU, don't we still run the risk of idle cpu being woken up and going immediately back to sleep (because there was no imbalance)?

Moreover we may be greatly reducing the amount of time a CPU is allowed to sleep this way ...

Signature · 5 lines
Thanks and Regards,
Srivatsa Vaddagiri,
Linux Technology Center,
IBM Software Labs,
Bangalore, INDIA - 560017
#3 lore raw
Quoted 4 lines · Srivatsa Vaddagiri

Hmm ..I guess we could restrict the max time a idle CPU will sleep taking
into account its balance interval. But whatever heuristics we follow to maximize balance_interval of about-to-sleep idle CPU, don't we still run the risk of idle cpu being woken up and going immediately back to sleep (because there was no imbalance)?

Yep.

Quoted 2 lines

Moreover we may be greatly reducing the amount of time a CPU is allowed to sleep this way ...

Yes. I was assuming you get some kind of fairly rapidly diminishing efficiency return curve based on your maximum sleep time. If that is not so, then I agree this wouldn't be the best method.

Signature · 1 line
SUSE Labs, Novell Inc.
#4 lore raw
In reply to Nick Piggin
Quoted 16 lines · Nick Piggin
Quoted 6 lines · Srivatsa Vaddagiri

I think a potential area which VST may need to address is scheduler load balance. If idle CPUs stop taking local timer ticks for some time, then during that period it could cause the various runqueues to go out of balance, since the idle CPUs will no longer pull tasks from non-idle CPUs.

Yep.

Quoted 4 lines

Do we care about this imbalance? Especially considering that most implementations will let the idle CPUs sleep only for some max duration (~900 ms in case of x86).

Quoted 6 lines

I think we do care, yes. It could be pretty harmful to sleep for even a few 10s of ms on a regular basis for some workloads. Although I guess many of those will be covered by try_to_wake_up events...

Not sure in practice, I would imagine it will hurt some multiprocessor workloads.

I am looking at the recent changes in load balance and I see that load balance on fork has been introduced (SD_BALANCE_FORK). I think this changes the whole scenario.

Considering the fact that there was already balance on wake_up and the fact that the scheduler checks for imbalance before running the idle task (load_balance_newidle), I don't know if sleeping idle CPUs can cause a load imbalance (fork/wakeup happening on other CPUs will probably push tasks to it and wake it up anyway? exits can change the balance, but probably is not relevant here?)

Except for a small fact: if the CPU sleeps w/o taking rebalance_ticks, its cpu_load[] can become incorrect over a period.

I noticed that load_balance_newidle uses newidle_idx to gauge the current cpu's load. As a result, it can see non-zero load for the idle cpu. Because of this it can decide to not pull tasks.

The rationale here (of using non-zero load): is it to try and let the cpu become idle? Somehow, this doesn't make sense, because in the very next rebalance_tick (assuming that the idle cpu does not sleep), it will start using the idle_idx, which will cause the load to show up as zero and can cause the idle CPU to pull some tasks.

Have I missed something here?

Anyway, if the idle cpu were to sleep instead, the next rebalance_tick will not happen and it will not pull the tasks to restore load balance.

If my above understanding is correct, I see two potential solutions for this:

A. Have load_balance_newidle use zero load for current cpu while
checking for busiest cpu.
B. Or, if we want to retain load_balance_newidle the way it is, have
the idle thread call back scheduler to zero the load and retry load balance, _when_ it decides that it wants to sleep (there are conditions under which a idle cpu may not want to sleep. for ex:
the next timer is only a tick, 1ms, away).

In either case, if the load balance still fails to pull any tasks, then it means there is really no imbalance. Tasks that will be added into the system later (fork/wake_up) will be balanced across the CPUs because of the load-balance code that runs during those events.

A possible patch for B follows below:

---

 linux-2.6.12-rc3-mm2-vatsa/include/linux/sched.h |    1 
 linux-2.6.12-rc3-mm2-vatsa/kernel/sched.c        |   38 +++++++++++++++++++++++
 2 files changed, 39 insertions(+)
kernel/sched.c renamed from kernel/sched.c~sched-nohz +38 -0
diff -puN kernel/sched.c~sched-nohz kernel/sched.c
@@ -2214,6 +2214,44 @@ static inline void idle_balance(int this
 	}
 }
 
+#ifdef CONFIG_NO_IDLE_HZ
+/*
+ * Try hard to pull tasks. Called by idle task before it sleeps shutting off
+ * local timer ticks.  This clears the various load counters and tries to pull
+ * tasks. If it cannot, then it means that there is really no imbalance at this
+ * point. Any imbalance that arises in future (because of fork/wake_up) will be
+ * handled by the load balance that happens during those events.
+ *
+ * Returns 1 if tasks were pulled over, 0 otherwise.
+ */
+int idle_balance_retry(void)
+{
+	int j, moved = 0, this_cpu = smp_processor_id();
+	struct sched_domain *sd;
+	runqueue_t *this_rq = this_rq();
+	unsigned long flags;
+
+	spin_lock_irqsave(&this_rq->lock, flags);
+
+	for (j = 0; j < 3; j++)
+		this_rq->cpu_load[j] = 0;
+
+	for_each_domain(this_cpu, sd) {
+		if (sd->flags & SD_BALANCE_NEWIDLE) {
+			if (load_balance_newidle(this_cpu, this_rq, sd)) {
+				/* We've pulled tasks over so stop searching */
+				moved = 1;
+				break;
+			}
+		}
+	}
+
+	spin_unlock_irqrestore(&this_rq->lock, flags);
+
+	return moved;
+}
+#endif
+
 /*
  * active_load_balance is run by migration threads. It pushes running tasks
  * off the busiest CPU onto idle CPUs. It requires at least 1 task to be
include/linux/sched.h renamed from include/linux/sched.h~sched-nohz +1 -0
diff -puN include/linux/sched.h~sched-nohz include/linux/sched.h
@@ -897,6 +897,7 @@ extern int task_curr(const task_t *p);
 extern int idle_cpu(int cpu);
 extern int sched_setscheduler(struct task_struct *, int, struct sched_param *);
 extern task_t *idle_task(int cpu);
+extern int idle_balance_retry(void);
 
 void yield(void);
 

_

Signature · 5 lines
Thanks and Regards,
Srivatsa Vaddagiri,
Linux Technology Center,
IBM Software Labs,
Bangalore, INDIA - 560017
#5 lore raw
Quoted 10 lines · Srivatsa Vaddagiri
Quoted 6 lines · Nick Piggin

I think we do care, yes. It could be pretty harmful to sleep for even a few 10s of ms on a regular basis for some workloads. Although I guess many of those will be covered by try_to_wake_up events...

Not sure in practice, I would imagine it will hurt some multiprocessor workloads.

Quoted 9 lines

I am looking at the recent changes in load balance and I see that load balance on fork has been introduced (SD_BALANCE_FORK). I think this changes the whole scenario.

Considering the fact that there was already balance on wake_up and the fact that the scheduler checks for imbalance before running the idle task (load_balance_newidle), I don't know if sleeping idle CPUs can cause a load imbalance (fork/wakeup happening on other CPUs will probably push tasks to it and wake it up anyway? exits can change the balance, but probably
is not relevant here?)

Well, there are a lot of ifs and buts. Some domains won't implement fork balancing, others won't do newidle balancing, wake balancing, wake to idle, etc etc.

I think my idea of allowing max_interval to be extended to a sufficiently large value if one CPU goes idle, and shutting off all CPU's rebalancing completely if no tasks are running for some time should cater to both hypervisor images and power saving concerns. While not being very intrusive to normal operation of the scheduler.

Quoted 10 lines

Except for a small fact: if the CPU sleeps w/o taking rebalance_ticks, its cpu_load[] can become incorrect over a period.

I noticed that load_balance_newidle uses newidle_idx to gauge the current cpu's load. As a result, it can see non-zero load for the idle cpu. Because of this it can decide to not pull tasks.

The rationale here (of using non-zero load): is it to try and let the
cpu become idle? Somehow, this doesn't make sense, because in the very next rebalance_tick (assuming that the idle cpu does not sleep), it will start using the idle_idx, which will cause the load to show up as zero and can cause the idle CPU to pull some tasks.

Have I missed something here?

No. I think tou are right in that we'll want to make sure cpu_load is zero before cutting the timer tick.

Quoted 13 lines

Anyway, if the idle cpu were to sleep instead, the next rebalance_tick will not happen and it will not pull the tasks to restore load balance.

If my above understanding is correct, I see two potential solutions for this:

A. Have load_balance_newidle use zero load for current cpu while
checking for busiest cpu.
B. Or, if we want to retain load_balance_newidle the way it is, have
the idle thread call back scheduler to zero the load and retry load balance, _when_ it decides that it wants to sleep (there are conditions under which a idle cpu may not want to sleep. for ex:
the next timer is only a tick, 1ms, away).

Quoted 5 lines

In either case, if the load balance still fails to pull any tasks, then it means
there is really no imbalance. Tasks that will be added into the system later (fork/wake_up) will be balanced across the CPUs because of the load-balance code that runs during those events.

A possible patch for B follows below:

Yeah something like that should do it.

Signature · 1 line
SUSE Labs, Novell Inc.
#6 lore raw
Quoted 3 lines · Nick Piggin

Well, there are a lot of ifs and buts. Some domains won't implement fork balancing, others won't do newidle balancing, wake balancing, wake to idle, etc etc.

Good point. I had somehow assumed that these are true for all domains. My bad ..

Quoted 5 lines

I think my idea of allowing max_interval to be extended to a sufficiently large value if one CPU goes idle, and shutting off all CPU's rebalancing completely if no tasks are running for some time should cater to both hypervisor images and power saving concerns.

Maybe we should check with virtual machine folks on this. Will check with UML and S390 folks tomorrow.

Quoted 4 lines
Quoted 2 lines

A possible patch for B follows below:

Yeah something like that should do it.

Ok ..thanks. Will include this patch in the final
load-balance-fix-for-no-hz-idle-cpus's patch!

Signature · 5 lines
Thanks and Regards,
Srivatsa Vaddagiri,
Linux Technology Center,
IBM Software Labs,
Bangalore, INDIA - 560017
#7 lore raw
In reply to Srivatsa Vaddagiri
Quoted 10 lines · Srivatsa Vaddagiri

Hi,
VST patch (http://lwn.net/Articles/118693/) attempts to avoid useless
regular (local) timer ticks when a CPU is idle.

I think a potential area which VST may need to address is scheduler load balance. If idle CPUs stop taking local timer ticks for some time, then during that period it could cause the various runqueues to go out of balance, since the idle CPUs will no longer pull tasks from non-idle CPUs.

Quoted 3 lines

Do we care about this imbalance? Especially considering that most implementations will let the idle CPUs sleep only for some max duration (~900 ms in case of x86).

yeah, we care about this imbalance, it would materially change the scheduling logic, which side-effect we dont want. Interaction with VST is not a big issue right now because this only matters on SMP boxes which is a rare (but not unprecedented) target for embedded platforms.

One solution would be to add an exponential backoff would be ok (as Nick suggested too), not an unconditional 'we wont fire a timer interrupt for the next 10 seconds' logic. It still impacts scheduling though.

Another, more effective, less intrusive but also more complex approach would be to make a distinction between 'totally idle' and 'partially idle or busy' system states. When all CPUs are idle then all timer irqs may be stopped and full VST logic applies. When at least one CPU is busy, all the other CPUs may still be put to sleep completely and immediately, but the busy CPU(s) have to take over a 'watchdog' role, and need to run the 'do the idle CPUs need new tasks' balancing functions. I.e. the scheduling function of other CPUs is migrated to busy CPUs. If there are no busy CPUs then there's no work, so this ought to be simple on the VST side. This needs some reorganization on the scheduler side but ought to be doable as well.

Ingo

#8 lore raw
Quoted 3 lines · Ingo Molnar

Interaction with VST is not a big issue right now because this only matters on SMP boxes which is a rare (but not unprecedented) target for embedded platforms.

Well, I don't think VST is targetting just power management in embedded platforms. Even (virtualized) servers will benefit from this patch, by making use of the (virtual) CPU resources more efficiently.

Signature · 5 lines
Thanks and Regards,
Srivatsa Vaddagiri,
Linux Technology Center,
IBM Software Labs,
Bangalore, INDIA - 560017
#9 lore raw
Quoted 8 lines · Srivatsa Vaddagiri
Quoted 1 line · Ingo Molnar

Interaction with VST is not a big issue right now because this only matters on SMP boxes which is a rare (but not unprecedented) target for embedded platforms.

Well, I don't think VST is targetting just power management in embedded platforms. Even (virtualized) servers will benefit from this patch, by making use of the (virtual) CPU resources more efficiently.

I still think looking at just using the rebalance backoff would be a good start.

What would be really nice is to measure the power draw on your favourite SMP system with your current patches that *don't* schedule ticks to service rebalancing.

Then measure again with the current rebalance backoff settings (which will likely be not very good, because some intervals are constrained to quite small values).

Then we can aim for something like 80-90% of the first (ie perfect) efficiency rating.

Signature · 1 line
SUSE Labs, Novell Inc.
#10 lore raw
In reply to Srivatsa Vaddagiri
Quoted 3 lines · Srivatsa Vaddagiri

Hi,
VST patch (http://lwn.net/Articles/118693/) attempts to avoid useless
regular (local) timer ticks when a CPU is idle.

<snip>

Quoted 6 lines
 linux-2.6.11-vatsa/kernel/sched.c |   52 ++++++++++++++++++++++++++++++++++++++
 1 files changed, 52 insertions(+)

diff -puN kernel/sched.c~vst-sched_load_balance kernel/sched.c

kernel/sched.c 2005-04-07 17:56:18.000000000 +0530 renamed from kernel/sched.c~vst-sched_load_balance 2005-04-07 17:51:34.000000000 +0530 +0 -0

<snip>

Quoted 12 lines
kernel/sched.c 2005-04-07 17:56:18.000000000 +0530 renamed from kernel/sched.c~vst-sched_load_balance 2005-04-07 17:51:34.000000000 +0530 +8 -0
@@ -1796,6 +1817,25 @@ find_busiest_group(struct sched_domain *
 
                        nr_cpus++;
                        avg_load += load;
+
+#ifdef CONFIG_VST
+                       if (idle != NOT_IDLE || !grp_sleeping ||
+                                               (grp_sleeping && woken))
+                               continue;
+
+                       sd1 = sd + (i-cpu);
+                       interval = sd1->balance_interval;

kernel/sched.c 2005-04-07 17:56:18.000000000 +0530 find_busiest_group(struct sched_domain * · line 1837

Quoted 10 lines
kernel/sched.c 2005-04-07 17:56:18.000000000 +0530 renamed from kernel/sched.c~vst-sched_load_balance 2005-04-07 17:51:34.000000000 +0530 +10 -0
+
+                       /* scale ms to jiffies */
+                       interval = msecs_to_jiffies(interval);
+                       if (unlikely(!interval))
+                               interval = 1;
+
+                       if (jiffies - sd1->last_balance >= interval) {
+                               woken = 1;
+                               cpu_set(i, wakemask);
+                       }

Sorry for the late reply, but shouldn't this jiffies comparison be done with time_after() or time_before()?

Thanks,
Nish

#11 lore raw
Quoted 5 lines · Nish Aravamudan
Quoted 1 line

+ if (jiffies - sd1->last_balance >= interval) {

Sorry for the late reply, but shouldn't this jiffies comparison be done with time_after() or time_before()?

I think it is not needed. The check should be able to handle overflow case also.

This probably assumes that you don't sleep longer than (2e32 - 1) jiffies (which is ~1193 hrs). Current VST implementation let us sleep way less than that limit (~896 ms) since it uses 32-bit number for sampling TSC. When it is upgraded to use 64-bit number, we may have to ensure that this limit (1193 hrs) is not exceeded.

Signature · 5 lines
Thanks and Regards,
Srivatsa Vaddagiri,
Linux Technology Center,
IBM Software Labs,
Bangalore, INDIA - 560017