Database regression due to scheduler changes ?
Hi,
We observed a 1.5% regression in an OLTP database workload going from 2.6.13-rc4 to 2.6.13-rc5. The regression has been carried forward at least as far as 2.6.14-rc5.
Through experimentation, and through examining the changes that went into 2.6.13-rc5, we found that we can eliminate the regression in 2.6.13-rc5 with one straightforward change: eliminating the NUMA level from the CPU scheduler domain structures.
After observing this, we collected schedstats (provided below) to try to determine how the scheduler behaves differently when the NUMA level is eliminated. It appears to us that the scheduler is having more success in balancing in this case. We tried to duplicate this effect by changing parameters in the NUMA-level and SMP-level domain definitions to increase the aggressiveness of the balancing, but none of the changes could recoup the regression.
We suspect the regression was introduced in the scheduler changes that went into 2.6.13-rc1. However, the regression was hidden from us by a bug in include/asm-ppc64/topology.h that made ppc64 look non-NUMA from 2.6.13-rc1 through 2.6.13-rc4. That bug was fixed in 2.6.13-rc5. Unfortunately the workload does not run to completion on 2.6.12 or 2.6.13-rc1. We have measurements on 2.6.12-rc6-git7 that do not show the regression.
One alternative for fixing this in 2.6.13 would have been to #define ARCH_HAS_SCHED_DOMAINS and to introduce a ppc64-specific version of build_sched_domains that eliminates the NUMA-level domain for small (e.g. 4-way) ppc64 systems. However, ARCH_HAS_SCHED_DOMAINS has been eliminated from 2.6.14, and anyways that solution doesn't seem very encompassing to me.
So, at this point I am soliciting assistance from scheduler experts to determine how this regression can be eliminated. We are keen to prevent this regression from going into the next distro versions. Simply shipping a distro kernel with CONFIG_NUMA off isn't a viable option because we need it for our larger configurations.
Our system configuration is a 4-way 1.9 GHz Power5-based server. As the system supports SMT, it shows eight online CPUs.
Below are the schedstats. The first set is with the NUMA-level domain, while the second set is without the NUMA-level domain.
Cheers,
Brian Twichell
Schedstats (NUMA-level domain included)
----------------------------------------------------------------------
00:09:05--------------------------------------------------------------
2845 sys_sched_yield()
0( 0.00%) found (only) active queue empty on current cpu 0( 0.00%) found (only) expired queue empty on current cpu
157( 5.52%) found both queues empty on current cpu
2688( 94.48%) found neither queue empty on current cpu
23287180 schedule()
1( 0.00%) switched active and expired queues 0( 0.00%) used existing active queue
0 active_load_balance()
0 sched_balance_exec()
0.19/1.17 avg runtime/latency over all cpus (ms)
[scheduler domain #0]
1418943 load_balance()
112240( 7.91%) called while idle
499( 0.44%) tried but failed to move any tasks
80433( 71.66%) found no busier group
31308( 27.89%) succeeded in moving at least one task
(average imbalance: 1.549)
316022( 22.27%) called while busy
21( 0.01%) tried but failed to move any tasks
220440( 69.75%) found no busier group
95561( 30.24%) succeeded in moving at least one task
(average imbalance: 1.727)
990681( 69.82%) called when newly idle
533( 0.05%) tried but failed to move any tasks
808816( 81.64%) found no busier group
181332( 18.30%) succeeded in moving at least one task
(average imbalance: 1.500)
0 sched_balance_exec() tried to push a task[scheduler domain #1]
922193 load_balance()
85822( 9.31%) called while idle
4032( 4.70%) tried but failed to move any tasks
70982( 82.71%) found no busier group
10808( 12.59%) succeeded in moving at least one task
(average imbalance: 1.348)
27022( 2.93%) called while busy
106( 0.39%) tried but failed to move any tasks
25478( 94.29%) found no busier group
1438( 5.32%) succeeded in moving at least one task
(average imbalance: 1.712)
809349( 87.76%) called when newly idle
6967( 0.86%) tried but failed to move any tasks
757097( 93.54%) found no busier group
45285( 5.60%) succeeded in moving at least one task
(average imbalance: 1.338)
0 sched_balance_exec() tried to push a task[scheduler domain #2]
825662 load_balance()
52074( 6.31%) called while idle
17791( 34.16%) tried but failed to move any tasks
32839( 63.06%) found no busier group
1444( 2.77%) succeeded in moving at least one task
(average imbalance: 1.981)
9524( 1.15%) called while busy
1072( 11.26%) tried but failed to move any tasks
7654( 80.37%) found no busier group
798( 8.38%) succeeded in moving at least one task
(average imbalance: 2.976)
764064( 92.54%) called when newly idle
262831( 34.40%) tried but failed to move any tasks
409353( 53.58%) found no busier group
91880( 12.03%) succeeded in moving at least one task
(average imbalance: 2.518)
0 sched_balance_exec() tried to push a taskSchedstats (NUMA-level domain eliminated)
----------------------------------------------------------------------
00:09:03--------------------------------------------------------------
2576 sys_sched_yield()
0( 0.00%) found (only) active queue empty on current cpu 0( 0.00%) found (only) expired queue empty on current cpu
118( 4.58%) found both queues empty on current cpu
2458( 95.42%) found neither queue empty on current cpu
23617887 schedule()
1106774 goes idle
0( 0.00%) switched active and expired queues 0( 0.00%) used existing active queue
0 active_load_balance()
0 sched_balance_exec()
0.19/1.10 avg runtime/latency over all cpus (ms)
[scheduler domain #0]
1810988 load_balance()
153509( 8.48%) called while idle
680( 0.44%) tried but failed to move any tasks
104906( 68.34%) found no busier group
47923( 31.22%) succeeded in moving at least one task
(average imbalance: 1.658)
317016( 17.51%) called while busy
30( 0.01%) tried but failed to move any tasks
217438( 68.59%) found no busier group
99548( 31.40%) succeeded in moving at least one task
(average imbalance: 1.831)
1340463( 74.02%) called when newly idle
762( 0.06%) tried but failed to move any tasks
1092960( 81.54%) found no busier group
246741( 18.41%) succeeded in moving at least one task
(average imbalance: 1.564)
0 sched_balance_exec() tried to push a task[scheduler domain #1]
1244187 load_balance()
111326( 8.95%) called while idle
8396( 7.54%) tried but failed to move any tasks
71276( 64.02%) found no busier group
31654( 28.43%) succeeded in moving at least one task
(average imbalance: 1.412)
39138( 3.15%) called while busy
220( 0.56%) tried but failed to move any tasks
34676( 88.60%) found no busier group
4242( 10.84%) succeeded in moving at least one task
(average imbalance: 1.360)
1093723( 87.91%) called when newly idle
15971( 1.46%) tried but failed to move any tasks
932422( 85.25%) found no busier group
145330( 13.29%) succeeded in moving at least one task
(average imbalance: 1.189)
0 sched_balance_exec() tried to push a taskBrian,
If I am understanding the data you posted, it looks like you are useingsched_yield extensivly in your database. This is known to have significant problems on SMP machines, and even bigger ones on NUMA machines, in part becouse the process doing the sched_yield may get rescheduled immediatly and not allow other processes to run (to free up whatever resource it's waiting for). This causes the processor to look busy to the scheduler and therefor the scheduler doesn't migrate other processes to the CPU that's spinning on sched_yield. On NUMA machines this is even more noticable as processes now have to migrate through an additional layer of the scheduler.
have to tried eliminating the sched_yield to see what difference it makes?
David Lang
Signature · 2 lines
There are two ways of constructing a software design. One way is to make it so simple that there are obviously no deficiencies. And the other way is to make it so complicated that there are no obvious deficiencies. -- C.A.R. Hoare
Quoted 2 lines · David Lang
If I am understanding the data you posted, it looks like you are
useingsched_yieldextensivly in your database.
Yes, I've seen problems in the past with workloads that use sched_yield heavily.
But bear in mind, the ~2700 sched_yields shown in the schedstats occurred over a 9 minute period. That means that sched_yield is being called at a rate of around 5 per second -- this is not a heavy user of sched_yield.
To put this into a broader perspective, this workload has around 270 tasks, and the context switch rate is around 45,000 per second.
Quoted 6 lines · Brian Twichell
Quoted 2 lines · David Lang
If I am understanding the data you posted, it looks like you are
useingsched_yieldextensivly in your database.
Quoted 7 lines
Yes, I've seen problems in the past with workloads that use
sched_yieldheavily.But bear in mind, the ~2700
sched_yieldsshown in the schedstats occurred over a 9 minute period. That means thatsched_yieldis being called at a rate of around 5 per second -- this is not a heavy user ofsched_yield.To put this into a broader perspective, this workload has around 270 tasks, and the context switch rate is around 45,000 per second.
Hi,
Thanks for your detailed report (and schedstats analysis). Sorry I didn't see it until now.
I think you are right that the NUMA domain is probably being too constrictive of task balancing, and that is where the regression is coming from.
For some workloads it is definitely important to have the NUMA domain, because it helps spread load over memory controllers as well as CPUs - so I guess eliminating that domain is not a good long term solution.
I would look at changing parameters of SD_NODE_INIT in include/ asm-powerpc/topology.h so they are closer to SD_CPU_INIT parameters (ie. more aggressive).
Reducing min_ and max_interval, busy_factor, cache_hot_time, will all do this.
I would also take a look at removing SD_WAKE_IDLE from the flags. This flag should make balancing more aggressive, but it can have problems when applied to a NUMA domain due to too much task movement.
I agree that sched_yield would be unlikely to be a problem at those rates, and either way it doesn't explain the regression.
Signature · 3 lines
SUSE Labs, Novell Inc. Send instant messages to your online friends http://au.messenger.yahoo.com
Hi Nick,
Quoted 4 lines
I would also take a look at removing
SD_WAKE_IDLEfrom the flags. This flag should make balancing more aggressive, but it can have problems when applied to a NUMA domain due to too much task movement.
I was wondering how ppc64 ended up with different parameters in the NODE
definitions (added SD_BALANCE_NEWIDLE and SD_WAKE_IDLE) and it looks
like it was Andrew :)
http://lkml.org/lkml/2004/11/2/205
It looks like balancing was not agressive enough on his workload too. Im a bit uneasy with only ppc64 having the two flags though.
Im also considering adding balance on fork for ppc64, it seems like a lot of people like to run stream like benchmarks and Im getting tired of telling them to lock their threads down to cpus.
Anton
Quoted 9 lines
Quoted 4 lines
I would also take a look at removing
SD_WAKE_IDLEfrom the flags. This flag should make balancing more aggressive, but it can have problems when applied to a NUMA domain due to too much task movement.I was wondering how ppc64 ended up with different parameters in the NODE
definitions (addedSD_BALANCE_NEWIDLEandSD_WAKE_IDLE) and it looks
like it was Andrew :)
Quoted 8 lines
http://lkml.org/lkml/2004/11/2/205
It looks like balancing was not agressive enough on his workload too. Im a bit uneasy with only ppc64 having the two flags though.
Im also considering adding balance on fork for ppc64, it seems like a lot of people like to run stream like benchmarks and Im getting tired of telling them to lock their threads down to cpus.
Please don't screw up everything else just for stream. It's a silly frigging benchmark. There's very little real-world stuff that really needs balance on fork, as opposed to balance on clone, and it'll slow down everything else.
M.
Quoted 9 lines · Martin J. Bligh
Quoted 3 lines
Im also considering adding balance on fork for ppc64, it seems like a lot of people like to run stream like benchmarks and Im getting tired of telling them to lock their threads down to cpus.
Please don't screw up everything else just for stream. It's a silly frigging benchmark. There's very little real-world stuff that really needs balance on fork, as opposed to balance on clone, and it'll slow
down everything else.
Long lived and memory intensive cloned or forked tasks will often [but far from always :(] want to be put on another memory controller from their siblings.
On workloads where there are lots of short lived ones (some bloated java programs), the load balancer should normally detect this and cut the balance-on-fork/clone.
Of course there are going to be cases where this fails. I haven't seen significant slowdowns in tests, although I'm sure there would be some at least small regressions. Have you seen any? Do you have any tests in mind that might show a problem?
Thanks,
Nick
Signature · 3 lines
SUSE Labs, Novell Inc. Send instant messages to your online friends http://au.messenger.yahoo.com
Nick Piggin wrote:
[...]
Quoted 3 lines
be some at least small regressions. Have you seen any? Do you have any tests in mind that might show a problem?
To clarify, I'm not suggesting you should go one way or the other for POWER4/5, but if you did have regressions I would be interested at least so I can try helping platforms that do use balance on clone.
Thanks,
Nick
Signature · 3 lines
SUSE Labs, Novell Inc. Send instant messages to your online friends http://au.messenger.yahoo.com
Quoted 13 lines
Quoted 8 lines
Quoted 3 lines
Im also considering adding balance on fork for ppc64, it seems like a lot of people like to run stream like benchmarks and Im getting tired of telling them to lock their threads down to cpus.
Please don't screw up everything else just for stream. It's a silly frigging benchmark. There's very little real-world stuff that really needs balance on fork, as opposed to balance on clone, and it'll slow down everything else.
Long lived and memory intensive cloned or forked tasks will often [but far from always :(] want to be put on another memory controller from their siblings.
Quoted 8 lines
On workloads where there are lots of short lived ones (some bloated java programs), the load balancer should normally detect this and cut the balance-on-fork/clone.
Of course there are going to be cases where this fails. I haven't seen significant slowdowns in tests, although I'm sure there would be some at least small regressions. Have you seen any? Do you have any tests in mind that might show a problem?
Anything fork/exec-y should show it's slower. Most stuff either forks and execs (in case it's silly to do it twice, and much cheaper to do it at exec time), or it's a clone, in which case a different set of rules applies for what you want (and actually, I suspect fork w/o exec is much the same).
Of course the pig is you can't determine at fork whether it'll exec or not, so you optimise for the common case, which is "do exec", unless given a hint otherwise.
For clone, and I suspect fork w/o exec, you have a tightly coupled group of processes that really would like to be close to each other. If you have 1 app on the whole system, you *may* want it spread across the system. If you have nr_apps >= nr_nodes, you probably want them node local. Determining which workload you have is messy, and may change.
Tweak the freak benchmark, not everything else ;-)
M.
Quoted 12 lines · Nick Piggin
Quoted 9 lines · Martin J. Bligh
Quoted 3 lines
Im also considering adding balance on fork for ppc64, it seems like a lot of people like to run stream like benchmarks and Im getting tired of telling them to lock their threads down to cpus.
Please don't screw up everything else just for stream. It's a silly frigging benchmark. There's very little real-world stuff that really needs balance on fork, as opposed to balance on clone, and it'll slow
down everything else.
Quoted 7 lines
Long lived and memory intensive cloned or forked tasks will often [but far from always :(] want to be put on another memory controller from their siblings.
On workloads where there are lots of short lived ones (some bloated java programs), the load balancer should normally detect this and cut the balance-on-fork/clone.
although if the primary workload is short-lived tasks and you don't do balance-on-fork/clone won't you have trouble ever balancing things? (anything that you do move over will probably exit quickly and put you right back where you started)
at the risk of a slowdown from an extra test it almost sounds like what is needed is to get feedback from the last scheduled balance attempt and use that to decide per-fork what to do.
for example say the scheduled balance attempt leaves a per-cpu value that has it's high bit tested every fork/clone (and then rotated left 1 bit) and if it's a 1 do a balance for this new process.
with a reasonable sized item (I would guess the default int size would probably be the most efficiant to process, but even 8 bits may be enough) the scheduled balance attempt can leave quite an extensive range of behavior, from 'always balance' to 'never balance' to 'balance every 5th and 8th fork', etc.
Quoted 4 lines
Of course there are going to be cases where this fails. I haven't seen significant slowdowns in tests, although I'm sure there would be some at least small regressions. Have you seen any? Do you have any tests in mind that might show a problem?
even though people will point out that it's a brin-dead workload (that should be converted to a state machine) I would expect that most fork-per-connection servers would show problems if the work per connection is small
David Lang
Signature · 2 lines
There are two ways of constructing a software design. One way is to make it so simple that there are obviously no deficiencies. And the other way is to make it so complicated that there are no obvious deficiencies. -- C.A.R. Hoare
Quoted 19 lines · --On Monday, November 07, 2005 18:04:23 -0800 David Lang…
Quoted 17 lines · Nick Piggin
Quoted 10 lines · Martin J. Bligh
Quoted 3 lines
Im also considering adding balance on fork for ppc64, it seems like a lot of people like to run stream like benchmarks and Im getting tired of telling them to lock their threads down to cpus.
Please don't screw up everything else just for stream. It's a silly frigging benchmark. There's very little real-world stuff that really needs balance on fork, as opposed to balance on clone, and it'll slow down everything else.
Long lived and memory intensive cloned or forked tasks will often [but far from always :(] want to be put on another memory controller from their siblings.
Quoted 5 lines
Quoted 3 lines
On workloads where there are lots of short lived ones (some bloated java programs), the load balancer should normally detect this and cut the balance-on-fork/clone.
although if the primary workload is short-lived tasks and you don't do balance-on-fork/clone won't you have trouble ever balancing things?
(anything that you do move over will probably exit quickly and put you right back where you started)
If you fork without execing a lot, with no hints, and they all exit quickly, then yes. But I don't think that's a common workload ;-)
Quoted 5 lines
at the risk of a slowdown from an extra test it almost sounds like what is needed is to get feedback from the last scheduled balance attempt and use that to decide per-fork what to do.
for example say the scheduled balance attempt leaves a per-cpu value that has it's high bit tested every fork/clone (and then rotated left 1 bit) and if it's a 1 do a balance for this new process.
with a reasonable sized item (I would guess the default int size would probably be the most efficiant to process, but even 8 bits may be enough) the scheduled balance attempt can leave quite an extensive range of behavior, from 'always balance' to 'never balance' to 'balance every 5th and 8th fork', etc.
That might work, yes. But I'd prefer to see a real workload that suffers before worrying about it too much. You have something in mind?
Quoted 6 lines
Quoted 4 lines
Of course there are going to be cases where this fails. I haven't seen significant slowdowns in tests, although I'm sure there would be some at least small regressions. Have you seen any? Do you have any tests in mind that might show a problem?
even though people will point out that it's a brin-dead workload (that should be converted to a state machine) I would expect that most fork-per-connection servers would show problems if the work per connection is small
I suspect most of those are either inetd (exec's) or multiple servers that service requests by now. maybe not. Threads might be quicker if it's heavy anyway ;-)
M.
Quoted 7 lines · David Lang
Quoted 5 lines · Nick Piggin
Long lived and memory intensive cloned or forked tasks will often [but far from always :(] want to be put on another memory controller from their siblings.
Quoted 7 lines
Quoted 3 lines
On workloads where there are lots of short lived ones (some bloated java programs), the load balancer should normally detect this and cut the balance-on-fork/clone.
although if the primary workload is short-lived tasks and you don't do balance-on-fork/clone won't you have trouble ever balancing things? (anything that you do move over will probably exit quickly and put you right back where you started)
You'll have no trouble if things *need* to be balanced, because that would imply the runqueue length average is significantly above the lengths of other runqueues.
As far as the extra test goes, it's really a miniscule overhead compared with the fork / clone cost itself, and can be really worthwhile if we get it right.
Quoted 9 lines
Quoted 5 lines
Of course there are going to be cases where this fails. I haven't seen significant slowdowns in tests, although I'm sure there would be some at least small regressions. Have you seen any? Do you have any tests in mind that might show a problem?
even though people will point out that it's a brin-dead workload (that should be converted to a state machine) I would expect that most fork-per-connection servers would show problems if the work per connection is small
Well it may be brain-dead, but if people use them (and they do) then I would really be interested to see results.
I did testing with some things like apache and volanomark, however I was not able to make out much difference on my setups. Though obviously that's not to say that there won't be with other software or other workloads / architectures etc.
Signature · 3 lines
SUSE Labs, Novell Inc. Send instant messages to your online friends http://au.messenger.yahoo.com
Quoted 5 lines · Nick Piggin
I think you are right that the NUMA domain is probably being too constrictive of task balancing, and that is where the regression is coming from.
Quoted 8 lines
For some workloads it is definitely important to have the NUMA domain, because it helps spread load over memory controllers as well as CPUs - so I guess eliminating that domain is not a good long term solution.
I would look at changing parameters of
SD_NODE_INITininclude/asm-powerpc/topology.hso they are closer toSD_CPU_INITparameters (ie. more aggressive).
I ran with the following:
topology.h 2005-11-08 13:17:15.000000000 -0600 renamed from topology.h.orig 2005-11-08 13:11:57.000000000 -0600 +4 -4
@@ -43,11 +43,11 @@ static inline int node_to_first_cpu(int .span = CPU_MASK_NONE, \ .parent = NULL, \ .groups = NULL, \ - .min_interval = 8, \ - .max_interval = 32, \ - .busy_factor = 32, \ + .min_interval = 1, \ + .max_interval = 4, \ + .busy_factor = 64, \ .imbalance_pct = 125, \ - .cache_hot_time = (10*1000000), \ + .cache_hot_time = (5*1000000/2), \ .cache_nice_tries = 1, \ .per_cpu_gain = 100, \ .flags = SD_LOAD_BALANCE \
There was no improvement in performance. The schedstats from this run follow:
2516 sys_sched_yield()
0( 0.00%) found (only) active queue empty on current cpu 0( 0.00%) found (only) expired queue empty on current cpu
46( 1.83%) found both queues empty on current cpu
2470( 98.17%) found neither queue empty on current cpu
22969106 schedule()
694922 goes idle
3( 0.00%) switched active and expired queues 0( 0.00%) used existing active queue
0 active_load_balance()
0 sched_balance_exec()
0.19/1.28 avg runtime/latency over all cpus (ms)
[scheduler domain #0]
1153606 load_balance()
82580( 7.16%) called while idle
488( 0.59%) tried but failed to move any tasks
63876( 77.35%) found no busier group
18216( 22.06%) succeeded in moving at least one task
(average imbalance: 1.526)
317610( 27.53%) called while busy
15( 0.00%) tried but failed to move any tasks
220139( 69.31%) found no busier group
97456( 30.68%) succeeded in moving at least one task
(average imbalance: 1.752)
753416( 65.31%) called when newly idle
487( 0.06%) tried but failed to move any tasks
624132( 82.84%) found no busier group
128797( 17.10%) succeeded in moving at least one task
(average imbalance: 1.531)
0 sched_balance_exec() tried to push a task[scheduler domain #1]
715638 load_balance()
68533( 9.58%) called while idle
3140( 4.58%) tried but failed to move any tasks
60357( 88.07%) found no busier group
5036( 7.35%) succeeded in moving at least one task
(average imbalance: 1.251)
22486( 3.14%) called while busy
64( 0.28%) tried but failed to move any tasks
21352( 94.96%) found no busier group
1070( 4.76%) succeeded in moving at least one task
(average imbalance: 1.922)
624619( 87.28%) called when newly idle
5218( 0.84%) tried but failed to move any tasks
591970( 94.77%) found no busier group
27431( 4.39%) succeeded in moving at least one task
(average imbalance: 1.382)
0 sched_balance_exec() tried to push a task[scheduler domain #2]
685164 load_balance()
63247( 9.23%) called while idle
7280( 11.51%) tried but failed to move any tasks
52200( 82.53%) found no busier group
3767( 5.96%) succeeded in moving at least one task
(average imbalance: 1.361)
24729( 3.61%) called while busy
418( 1.69%) tried but failed to move any tasks
21025( 85.02%) found no busier group
3286( 13.29%) succeeded in moving at least one task
(average imbalance: 3.579)
597188( 87.16%) called when newly idle
67577( 11.32%) tried but failed to move any tasks
371377( 62.19%) found no busier group
158234( 26.50%) succeeded in moving at least one task
(average imbalance: 2.146)
0 sched_balance_exec() tried to push a taskQuoted 5 lines
I would also take a look at removing
SD_WAKE_IDLEfrom the flags. This flag should make balancing more aggressive, but it can have problems when applied to a NUMA domain due to too much task movement.
Independent from the run above, I ran with the following:
topology.h 2005-11-08 19:34:25.000000000 -0600 renamed from topology.h.orig 2005-11-08 19:32:19.000000000 -0600 +0 -1
@@ -53,7 +53,6 @@ static inline int node_to_first_cpu(int .flags = SD_LOAD_BALANCE \ | SD_BALANCE_EXEC \ | SD_BALANCE_NEWIDLE \ - | SD_WAKE_IDLE \ | SD_WAKE_BALANCE, \ .last_balance = jiffies, \ .balance_interval = 1, \
There was no improvement in performance.
I didn't expect any change in performance this time, because I don't think the SD_WAKE_IDLE flag is effective in the NUMA domain, due to the following code in wake_idle:
for_each_domain(cpu, sd) {
if (sd->flags & SD_WAKE_IDLE) {
cpus_and(tmp, sd->span, p->cpus_allowed);
for_each_cpu_mask(i, tmp) {
if (idle_cpu(i))
return i;
}
}
else
break;
}If I read that loop correctly it stops at the first domain which doesn't have SD_WAKE_IDLE set, which is the CPU domain (see SD_CPU_INIT), and thus it never gets to the NUMA domain.
Thanks for the suggestions Nick. Andrew raises some good questions that I will address tomorrow.
Cheers,
Brian
A message that is not in the archive (sent off-list or not yet received): [email protected]
Quoted 15 lines · Nick Piggin
Just one other thing - A couple of fields aren't actually getting initialised at all, which I didn't pick up on.
This bug looks to have been due to a mismerge between the common asm-powerpc directory and one of my scheduler changes somewhere along the line.
If you get time to try this out, that would be great.
===================================================================
include/asm-powerpc/topology.h static inline int node_to_first_cpu(int · line 60
Quoted 10 lines
include/asm-powerpc/topology.h +4
-0@@ -51,6 +51,10 @@ static inline int node_to_first_cpu(int .cache_hot_time = (10*1000000), \ .cache_nice_tries = 1, \ .per_cpu_gain = 100, \ + .busy_idx = 3, \ + .idle_id = 1, \ + .newidle_idx = 2, \ + .wake_idx =1 , \ .flags = SD_LOAD_BALANCE \ |SD_BALANCE_EXEC \ |SD_BALANCE_NEWIDLE \
Nick,
That patch eliminates the regression on 2.6.13-rc5. Thanks !! We are currently evaluating it with other workloads.
It also gives a boost on 2.6.14, but unfortunately we are still 1% regressed on 2.6.14. (The regression on 2.6.14 was larger than the regression on 2.6.13-rc5.) We're trying to isolate the 2.6.14 regression now. I'll let you know if we isolate it to a scheduler change.
Cheers,
Brian
Quoted 3 lines · David Lang
Brian,
If I am understanding the data you posted, it looks like you are useingsched_yieldextensivly in your database. This is known to have significant problems on SMP machines, and even bigger ones on NUMA machines, in part becouse the process doing thesched_yieldmay get rescheduled immediatly and not allow other processes to run (to free up whatever resource it's waiting for). This causes the processor to look busy to the scheduler and therefor the scheduler doesn't migrate other processes to the CPU that's spinning onsched_yield. On NUMA machines this is even more noticable as processes now have to migrate through an additional layer of the scheduler.
I have an application designed on Linux where the only processes running are 'init' and those integral to the application. Each communicates using mutual exclusion & semaphores across a shared file/memory backing.
The application was designed to be as close intrinsically as to what Linux does--manage processes. There's only 1 thread per process, and each process has a different executable for its own task.
One day I plan to extend this application across multiple CPUs using either SMP or NUMA. Therefore a lot of the mutual exclusion routines I've coded in use sched_yield().
What should I do instead to alleviate the problem of causing the processor to look busy? In this case I _want_ other processes to be migrated over to the CPU in order to free up the critical section faster.
A simple test using a 2-cpu SMP system resulted in sched_yield() being a lot faster than using futexes, but I don't know for the NUMA case.
Best regards,
-Byron
--
Byron Stanoszek Ph: (330) 644-3059 Systems Programmer Fax: (330) 644-8110 Commercial Timesharing Inc. Email: [email protected]
Quoted 181 lines · Brian Twichell
Hi,
We observed a 1.5% regression in an OLTP database workload going from 2.6.13-rc4 to 2.6.13-rc5. The regression has been carried forward at least as far as 2.6.14-rc5.
Through experimentation, and through examining the changes that went into 2.6.13-rc5, we found that we can eliminate the regression in 2.6.13-rc5 with one straightforward change: eliminating the NUMA level from the CPU scheduler domain structures.
After observing this, we collected schedstats (provided below) to try to determine how the scheduler behaves differently when the NUMA level is eliminated. It appears to us that the scheduler is having more success in balancing in this case. We tried to duplicate this effect by changing parameters in the NUMA-level and SMP-level domain definitions to increase the aggressiveness of the balancing, but none of the changes could recoup the regression.
We suspect the regression was introduced in the scheduler changes that went into 2.6.13-rc1. However, the regression was hidden from us by a bug in
include/asm-ppc64/topology.hthat made ppc64 look non-NUMA from 2.6.13-rc1 through 2.6.13-rc4. That bug was fixed in 2.6.13-rc5. Unfortunately the workload does not run to completion on 2.6.12 or 2.6.13-rc1. We have measurements on 2.6.12-rc6-git7 that do not show the regression.One alternative for fixing this in 2.6.13 would have been to #define
ARCH_HAS_SCHED_DOMAINSand to introduce a ppc64-specific version ofbuild_sched_domainsthat eliminates the NUMA-level domain for small (e.g. 4-way) ppc64 systems. However,ARCH_HAS_SCHED_DOMAINShas been eliminated from 2.6.14, and anyways that solution doesn't seem very encompassing to me.So, at this point I am soliciting assistance from scheduler experts to determine how this regression can be eliminated. We are keen to prevent this regression from going into the next distro versions. Simply shipping a distro kernel with
CONFIG_NUMAoff isn't a viable option because we need it for our larger configurations.Our system configuration is a 4-way 1.9 GHz Power5-based server. As the system supports SMT, it shows eight online CPUs.
Below are the schedstats. The first set is with the NUMA-level domain, while the second set is without the NUMA-level domain.
Cheers,
Brian TwichellSchedstats (NUMA-level domain included)
----------------------------------------------------------------------
00:09:05--------------------------------------------------------------
2845sys_sched_yield()
0( 0.00%) found (only) active queue empty on current cpu 0( 0.00%) found (only) expired queue empty on current cpu
157( 5.52%) found both queues empty on current cpu
2688( 94.48%) found neither queue empty on current cpu23287180
schedule()
1( 0.00%) switched active and expired queues 0( 0.00%) used existing active queue0
active_load_balance()
0sched_balance_exec()0.19/1.17 avg runtime/latency over all cpus (ms)
[scheduler domain #0]
1418943load_balance()112240( 7.91%) called while idle 499( 0.44%) tried but failed to move any tasks 80433( 71.66%) found no busier group 31308( 27.89%) succeeded in moving at least one task (average imbalance: 1.549) 316022( 22.27%) called while busy 21( 0.01%) tried but failed to move any tasks 220440( 69.75%) found no busier group 95561( 30.24%) succeeded in moving at least one task (average imbalance: 1.727) 990681( 69.82%) called when newly idle 533( 0.05%) tried but failed to move any tasks 808816( 81.64%) found no busier group 181332( 18.30%) succeeded in moving at least one task (average imbalance: 1.500) 0 sched_balance_exec() tried to push a task[scheduler domain #1]
922193 load_balance() 85822( 9.31%) called while idle 4032( 4.70%) tried but failed to move any tasks 70982( 82.71%) found no busier group 10808( 12.59%) succeeded in moving at least one task (average imbalance: 1.348) 27022( 2.93%) called while busy 106( 0.39%) tried but failed to move any tasks 25478( 94.29%) found no busier group 1438( 5.32%) succeeded in moving at least one task (average imbalance: 1.712) 809349( 87.76%) called when newly idle 6967( 0.86%) tried but failed to move any tasks 757097( 93.54%) found no busier group 45285( 5.60%) succeeded in moving at least one task (average imbalance: 1.338) 0 sched_balance_exec() tried to push a task[scheduler domain #2]
825662 load_balance() 52074( 6.31%) called while idle 17791( 34.16%) tried but failed to move any tasks 32839( 63.06%) found no busier group 1444( 2.77%) succeeded in moving at least one task (average imbalance: 1.981) 9524( 1.15%) called while busy 1072( 11.26%) tried but failed to move any tasks 7654( 80.37%) found no busier group 798( 8.38%) succeeded in moving at least one task (average imbalance: 2.976) 764064( 92.54%) called when newly idle 262831( 34.40%) tried but failed to move any tasks 409353( 53.58%) found no busier group 91880( 12.03%) succeeded in moving at least one task (average imbalance: 2.518) 0 sched_balance_exec() tried to push a taskSchedstats (NUMA-level domain eliminated)
----------------------------------------------------------------------
00:09:03--------------------------------------------------------------
2576sys_sched_yield()
0( 0.00%) found (only) active queue empty on current cpu 0( 0.00%) found (only) expired queue empty on current cpu
118( 4.58%) found both queues empty on current cpu
2458( 95.42%) found neither queue empty on current cpu23617887
schedule()
1106774 goes idle
0( 0.00%) switched active and expired queues 0( 0.00%) used existing active queue0
active_load_balance()
0sched_balance_exec()0.19/1.10 avg runtime/latency over all cpus (ms)
[scheduler domain #0]
1810988load_balance()153509( 8.48%) called while idle 680( 0.44%) tried but failed to move any tasks 104906( 68.34%) found no busier group 47923( 31.22%) succeeded in moving at least one task (average imbalance: 1.658) 317016( 17.51%) called while busy 30( 0.01%) tried but failed to move any tasks 217438( 68.59%) found no busier group 99548( 31.40%) succeeded in moving at least one task (average imbalance: 1.831) 1340463( 74.02%) called when newly idle 762( 0.06%) tried but failed to move any tasks 1092960( 81.54%) found no busier group 246741( 18.41%) succeeded in moving at least one task (average imbalance: 1.564) 0 sched_balance_exec() tried to push a task[scheduler domain #1]
1244187load_balance()111326( 8.95%) called while idle 8396( 7.54%) tried but failed to move any tasks 71276( 64.02%) found no busier group 31654( 28.43%) succeeded in moving at least one task (average imbalance: 1.412) 39138( 3.15%) called while busy 220( 0.56%) tried but failed to move any tasks 34676( 88.60%) found no busier group 4242( 10.84%) succeeded in moving at least one task
Quoted 9 lines
(average imbalance: 1.360)
1093723( 87.91%) called when newly idle
15971( 1.46%) tried but failed to move any tasks
932422( 85.25%) found no busier group
145330( 13.29%) succeeded in moving at least one task
(average imbalance: 1.189)
0 sched_balance_exec() tried to push a taskCan you change sched_yield() to usleep(1) or usleep(0) and see if that works. I found that in recent kernels sched_yield() just seems to spin (may not actually spin, but seems to with a high CPU usage).
Cheers,
Dick Johnson
Penguin : Linux version 2.6.13.4 on an i686 machine (5589.55 BogoMips). Warning : 98.36% of all statistics are fiction.
.
****************************************************************
The information transmitted in this message is confidential and may be privileged. Any review, retransmission, dissemination, or other use of this information by persons or entities other than the intended recipient is prohibited. If you are not the intended recipient, please notify Analogic Corporation immediately - by replying to this message or by sending an email to [email protected] - and destroy all copies of this information, including any attachments, without reading or disclosing them.
Thank you.
Quoted 5 lines · linux-os (Dick Johnson)
Can you change
sched_yield()to usleep(1) or usleep(0) and see if that works. I found that in recent kernelssched_yield()just seems to spin (may not actually spin, but seems to with a high CPU usage).
I've told you that it *does* spin and always has. Even with 2.4 kernels. In fact, it is *specified* to spin, anything else would be a bug.
Caveat: it also yields the CPU, but only if there is another runnable task with a higher priority (which is meaningless between SCHED_OTHER tasks, though we try to do something sane there too).
Secondly, Brian actually pinpointed the source of the regression and it is not sched_yield(), nor has sched_yield changed since the regression. So wouldn't this just be a wild goose chase.
Nick
Signature · 3 lines
SUSE Labs, Novell Inc. Send instant messages to your online friends http://au.messenger.yahoo.com