kernel/sched.c oddness?

Just a quick follow up
* using imbalance (not divided by 2) instead of nr_running in is_unbalanced would save a multiply by 3
* it is a more accurate with a small number of processes due to no divisions
* perhaps the last test should actually be if(busiest->nr_running <= nr_running)

Regards,
Nick

Quoted 32 lines · Nick Piggin

Dear Ingo,
I apologise in advance if the current behaviour of the scheduler is the result of tuning / special casing you did in the scheduler I didn't follow its development closely. However, I noticed on my 2xSMP system that quite unbalanced loads weren't getting even CPU time best example - 3 processes in busywait loops - one would get 100% of one cpu while two would get 50% each of the other.

I think find_busiest_queue might have a few problems:
* the "imbalance" value divided by 2 loses meaning and precision esp. with small number of processes

* in the 25% imbalance calculation presumably the + should be a *

* the 25% calculation uses the divided imbalance value which is inaccurate

* i think the 25% imbalance calculation should use a quarter of max_load, not three quarters.

* the second test (after the lock) isn't very good, its cheaper than the mul but having battled contention and claimed the lock it would be a
shame to
not do anything with it!

Now top says the patch has fixed up the balancing but perhaps some of these aren't bugs - perhaps they need a comment because they are a bit subtle! If they are, please recommend the patch to Linus.

Regards,
Nick

This snippet of code appears wrong... Either that, or the accompanying comment is wrong?

from kernel/sched.c::find_busiest_queue():

| *imbalance = (max_load - nr_running) / 2;
|
| /* It needs an at least ~25% imbalance to trigger balancing. */
| if (!idle && (*imbalance < (max_load + 3)/4)) {
|     busiest = NULL;
|     goto out;
| }

The comment says 25% imbalance, but the code is really checking for a ~50% imbalance. The attatched patch moves the division by two to the pull_task function where the imbalance number is actually used. This patch makes the code match the comment, and divides the imbalance by two where it is needed.

Please let me know if I've misinterpreted what this code is supposed to be doing, -or- if we really want the comment to match the current code.

Cheers!

-Matt

Hi Matt,
I think your patch is good except that it would be fine to use a /= 2 as the compiler will turn this into a shift, and imbalance is not really valid (or used) if busiest == NULL. Actually there are a number of things (I think) still wrong with this! I posted a patch to Ingo - I guess I should have cc'ed the list - we should combine our efforts! Here is my explanation and a new patch including both our fixes.

Regards,
Nick

Quoted 45 lines · Nick Piggin

Just a quick follow up
* using imbalance (not divided by 2) instead of nr_running in is_unbalanced would save a multiply by 3
* it is a more accurate with a small number of processes due to no divisions
* perhaps the last test should actually be if(busiest->nr_running <= nr_running)

Regards,
Nick

Quoted 32 lines · Nick Piggin

Dear Ingo,
I apologise in advance if the current behaviour of the scheduler is the result of tuning / special casing you did in the scheduler I didn't follow its development closely. However, I noticed on my 2xSMP system that quite unbalanced loads weren't getting even CPU time best example - 3 processes in busywait loops - one would get 100% of one cpu while two would get 50% each of the other.

I think find_busiest_queue might have a few problems:
* the "imbalance" value divided by 2 loses meaning and precision esp. with small number of processes

* in the 25% imbalance calculation presumably the + should be a *

* the 25% calculation uses the divided imbalance value which is inaccurate

* i think the 25% imbalance calculation should use a quarter of max_load, not three quarters.

* the second test (after the lock) isn't very good, its cheaper than the mul but having battled contention and claimed the lock it would be a
shame to
not do anything with it!

Now top says the patch has fixed up the balancing but perhaps some of these aren't bugs - perhaps they need a comment because they are a bit subtle! If they are, please recommend the patch to Linus.

Regards,
Nick

Quoted 12 lines · Matthew Dobson

This snippet of code appears wrong... Either that, or the accompanying comment is wrong?

from kernel/sched.c::find_busiest_queue():

| *imbalance = (max_load - nr_running) / 2;
|
| /* It needs an at least ~25% imbalance to trigger balancing. */
| if (!idle && (*imbalance < (max_load + 3)/4)) {
|     busiest = NULL;
|     goto out;
| }

Quoted 7 lines

The comment says 25% imbalance, but the code is really checking for a ~50% imbalance. The attatched patch moves the division by two to the pull_task function where the imbalance number is actually used. This patch makes the code match the comment, and divides the imbalance by two where it is needed.

Please let me know if I've misinterpreted what this code is supposed to be doing, -or- if we really want the comment to match the current code.

Cheers!

-Matt

------------------------------------------------------------------------

kernel/sched.c renamed from kernel/sched.c.old +10 -4

@@ -689,10 +689,10 @@
 	if (likely(!busiest))
 		goto out;
 
-	*imbalance = (max_load - nr_running) / 2;
+	*imbalance = max_load - nr_running;
 
 	/* It needs an at least ~25% imbalance to trigger balancing. */
-	if (!idle && (*imbalance < (max_load + 3)/4)) {
+	if (!idle && (*imbalance*4 < max_load)) {
 		busiest = NULL;
 		goto out;
 	}

@@ -702,10 +702,11 @@
 	 * Make sure nothing changed since we checked the
 	 * runqueue length.
 	 */
-	if (busiest->nr_running <= nr_running + 1) {
+	if (busiest->nr_running <= nr_running) {
 		spin_unlock(&busiest->lock);
 		busiest = NULL;
 	}
+
 out:
 	return busiest;
 }

@@ -748,7 +749,12 @@
 	busiest = find_busiest_queue(this_rq, this_cpu, idle, &imbalance);
 	if (!busiest)
 		goto out;
-
+	/*
+	 * We only want to steal a number of tasks equal to 1/2 the imbalance,
+	 * otherwise, we'll just shift the imbalance to the new queue.
+	 */
+	imbalance /= 2;
+	
 	/*
 	 * We first consider expired tasks. Those will likely not be
 	 * executed in the near future, and they are most likely to

[...] However, I noticed on my 2xSMP system that quite unbalanced loads weren't getting even CPU time best example - 3 processes in busywait loops - one would get 100% of one cpu while two would get 50% each of the other.

Quoted 5 lines

[...] However, I noticed on my 2xSMP system that quite unbalanced loads weren't getting even CPU time best example - 3 processes in busywait loops - one would get 100% of one cpu while two would get 50% each of the other.

this was done intentionally, and this scenario (1+2 tasks) is the very
worst scenario. The problem is that by trying to balance all 3 tasks we
now have 3 tasks that trash their cache going from one CPU to another. (this is what happens with your patch - even with another approach we'd have to trash at least one task)

By keeping 2 tasks on one CPU and 1 task on the other CPU we avoid cross-CPU migration of threads. Think about the 2+3 or 4+5 tasks case rather, do we want absolutely perfect balancing, or good SMP affinity and good combined performance?

Ingo

this was done intentionally, and this scenario (1+2 tasks) is the very
worst scenario. The problem is that by trying to balance all 3 tasks we
now have 3 tasks that trash their cache going from one CPU to another. (this is what happens with your patch - even with another approach we'd have to trash at least one task)

By keeping 2 tasks on one CPU and 1 task on the other CPU we avoid cross-CPU migration of threads. Think about the 2+3 or 4+5 tasks case rather, do we want absolutely perfect balancing, or good SMP affinity and good combined performance?

/* It needs an at least ~50% imbalance to trigger balancing. */

Either way works for me. I'd like to see something done, as the comments don't match the code right now...