Skip to contentSkip to conversation

scheduler scalability - cgroups, cpusets and load-balancing

DISCUSSION Peter Zijlstra 5 participants 36 messages Jan 29, 2008

lore
Share & tools
lore
#0 lore raw

Hi All,

Some of the fancy new scheduler features such as the cgroup load balancer (load_balance_monitor) and the real-time load balancer are a bit of an scalability issue. They all seem to want a rather strong global bound to keep a global fairness (which is quite understandable).

[ my own interest is currently real-time group scheduling on multiple
cpus, and that seems to require _very_ strong bonds ]

I think the current stuff would scale up to 8 maybe 16 cpus, but after that I'd be real worried.

Now we want distributions to enable most of these features. Distros seem to want containers, but distros also need to support 128+ cpu machines, so how are we going to solve this.

My thoughts were to make stronger use of disjoint cpu-sets. cgroups and cpusets are related, in that cpusets provide a property to a cgroup. However, load_balance_monitor()'s interaction with sched domains confuses me - it might DTRT, but I can't tell.

[ It looks to me it balances a group over the largest SD the current cpu
has access to, even though that might be larger than the SD associated with the cpuset of that particular cgroup. ]

Also the RT load-balance needs to become aware of such these sets, I think Paul J and Steven once talked about it, but can't quite remember where that ended. From my POV there should be sched-domain based balance information, not global.

By cutting the problem into smaller pieces, and adding tunables to weaken to global fairness, I think we can give administrators enough freedom to make use of these features, even on the largest of machines.

[ so I'd move the load_balance_monitor() tunables into cpusets as well,
I can imagine a smaller cpuset wanting a stronger fairness than a much larger cpuset. ]

I understand its a somewhat hand-wavey email, but I wanted to start discussion on the issue, or have someone show me I'm wrong and can stop worrying :-).

Peter

#1 lore raw
Quoted 3 lines · Peter

Also the RT load-balance needs to become aware of such these sets, I think Paul J and Steven once talked about it, but can't quite remember where that ended

See further the thread:

http://lkml.org/lkml/2007/10/22/400

(I don't remember where it ended up either; probably nowhere.
I'm just passing on the link, before doing any reading or thinking.)

Signature · 3 lines
                  I won't rest till it's the best ...
                  Programmer, Linux Scalability
                  Paul Jackson <[email protected]> 1.940.382.4214
#2 lore raw
Quoted 11 lines · Paul Jackson
Quoted 3 lines · Peter

Also the RT load-balance needs to become aware of such these sets, I think Paul J and Steven once talked about it, but can't quite remember where that ended

See further the thread:

http://lkml.org/lkml/2007/10/22/400

(I don't remember where it ended up either; probably nowhere.
I'm just passing on the link, before doing any reading or thinking.)

Thanks for the link. Yes I think your last suggestion of creating rt-domains ( http://lkml.org/lkml/2007/10/23/419 ) is a good one.

Upon cpuset changes we could then look for the largest disjoint set and hang the rt balance code from that.

#12 lore raw
In reply to Peter Zijlstra

Here I go, talking to myself..

Quoted 8 lines · Peter Zijlstra

My thoughts were to make stronger use of disjoint cpu-sets. cgroups and cpusets are related, in that cpusets provide a property to a cgroup. However, load_balance_monitor()'s interaction with sched domains confuses me - it might DTRT, but I can't tell.

[ It looks to me it balances a group over the largest SD the current cpu
has access to, even though that might be larger than the SD associated with the cpuset of that particular cgroup. ]

Hmm, with a bit more thought I think that does indeed DTRT. Because, if the cpu belongs to a disjoint cpuset, the highest sd (with load-balancing enabled) would be that. Right?

[ Just a bit of a shame we have all cgroups represented on each cpu. ]

Also, might be a nice idea to split the daemon up if there are indeed disjoint sets - currently there is only a single daemon which touches the whole system.

#3 lore raw
In reply to Peter Zijlstra
Quoted 2 lines · Peter

Thanks for the link. Yes I think your last suggestion of creating rt-domains ( http://lkml.org/lkml/2007/10/23/419 ) is a good one.

We now have a per-cpuset Boolean flag file called 'sched_load_balance'.

In the default case, this flag is set on, and the kernel does its usual load balancing across all CPUs in that cpuset. This means, under the covers, that there exists some sched domain such that all CPUs in that cpuset are in that same sched domain. That sched domain might contain additional CPUs from outside that cpuset as well. Indeed, in the default vanilla configuration, that sched domain contains all CPUs in the system.

If we turn the sched_load_balance flag off for some cpuset, we are telling the kernel it's ok not to load balance on the CPUs in that cpuset (unless those CPUs are in some other cpuset that needed load balancing anyway.)

This 'sched_load_balance' flag is, thus far, "the" cpuset hook supporting realtime. One can use it to configure a system so that the kernel does not do normal load balancing on select CPUs, such as those CPUs dedicated to realtime use.

It sounds like Peter is reminding us that we really have three choices for a handling a given CPU's load balancing:
1) normal kernel scheduler load balancing,
2) RT load balancing, or
3) no load balancing whatsoever.

If that's the case (if we really need choice 3) then a single Boolean flag, such as sched_load_balance, is not sufficient to select from the three choices, and it might make sense to add a second per-cpuset Boolean flag, say "sched_rt_balance", default off, which if turned on, enabled choice 2.

If that's not the case (we only need choices 1 and 2) then -logically- we could overload the meaning of the current sched_load_balance, to mean, if turned off, not only to stop doing normal balancing, but to further mean that we should commence RT balancing. However bits aren't -that- precious here, and this sounds unnecessarily confusing.

So ... would a new per-cpuset Boolean flag such as sched_rt_balance be appropriate and sufficient to mark those cpusets whose set of CPUs required RT balancing?

Signature · 3 lines
                  I won't rest till it's the best ...
                  Programmer, Linux Scalability
                  Paul Jackson <[email protected]> 1.940.382.4214
#13 lore raw
In reply to Peter Zijlstra

Peter wrote, in reply to Peter ;):

Quoted 7 lines
Quoted 3 lines

[ It looks to me it balances a group over the largest SD the current cpu
has access to, even though that might be larger than the SD associated with the cpuset of that particular cgroup. ]

Hmm, with a bit more thought I think that does indeed DTRT. Because, if the cpu belongs to a disjoint cpuset, the highest sd (with load-balancing enabled) would be that. Right?

The code that defines sched domains, kernel/sched.c partition_sched_domains(), as called from the cpuset code in kernel/cpuset.c rebuild_sched_domains(), does not make use of the full range of sched_domain possibilities.

In particular, it only sets up some non-overlapping set of sched domains. Every CPU ends up in at most a single sched domain.

The original reason that one can't define overlapping sched domains via this cpuset interface (based off the cpuset 'sched_load_balance' flag) is that I didn't realize it was even possible to overlap sched domains when I wrote the cpuset code defining sched domains. And then when I later realized one could overlap sched domains, I (a) didn't see a need to do so, and (b) couldn't see how to do so via the cpuset interface without causing my brain to explode.

Now, back to Peter's question, being a bit pedantic, CPUs don't belong to disjoint cpusets, except in the most minimal situation that there is only one cpuset covering all CPUs.

Rather what happens, when you have need for some realtime CPUs, is that:
1) you turn off sched_load_balance on the top cpuset,
2) you setup your realtime cpuset as a child cpuset of the top cpuset such that its CPUs doesn't overlap any of its siblings, and
3) you turn off sched_load_balance in that realtime cpuset.

At that point, sched domains are rebuilt, including providing a sched domain that just contains the CPUs in that realtime cpuset, and normal scheduler load balancing ceases on the CPUs in that realtime cpuset.

Quoted 1 line

[ Just a bit of a shame we have all cgroups represented on each cpu. ]

Could you restate this -- I suspect it's obvious, but I'm oblivious ;).

Signature · 3 lines
                  I won't rest till it's the best ...
                  Programmer, Linux Scalability
                  Paul Jackson <[email protected]> 1.940.382.4214
#4 lore raw
In reply to Paul Jackson
Quoted 5 lines · Paul Jackson
Quoted 2 lines · Peter

Thanks for the link. Yes I think your last suggestion of creating rt-domains ( http://lkml.org/lkml/2007/10/23/419 ) is a good one.

We now have a per-cpuset Boolean flag file called 'sched_load_balance'.

SD_LOAD_BALANCE, right?

Quoted 13 lines

In the default case, this flag is set on, and the kernel does its usual load balancing across all CPUs in that cpuset. This means, under the covers, that there exists some sched domain such that all CPUs in that cpuset are in that same sched domain. That sched domain might contain additional CPUs from outside that cpuset as well. Indeed, in the default vanilla configuration, that sched domain contains all CPUs in the system.

If we turn the sched_load_balance flag off for some cpuset, we are telling the kernel it's ok not to load balance on the CPUs in that cpuset (unless those CPUs are in some other cpuset that needed load balancing anyway.)

Quoted 4 lines

This 'sched_load_balance' flag is, thus far, "the" cpuset hook supporting realtime. One can use it to configure a system so that the kernel does not do normal load balancing on select CPUs, such as those CPUs dedicated to realtime use.

Ah, here I disagree, it is possible to do (hard) realtime scheduling over multiple cpus, the only draw back is that it requires a very strong load-balancer, making it unsuitable for large number of cpus.

( of course, having a strong rt load balancer on a large cpuset doesn't
harm, as long as there are no rt tasks to balance )

So if we have a system like so:

             __A__
            /  |  \
          B1  B2  B3
          /\
         /  \
       C1   C2

A comprises of cpus 0-127, !SD_LOAD_BALANCE

B1 comprises of cpus 0-63, !SD_LOAD_BALANCE
B2 comprises of cpus 64-119
B3 120-127

C1 0-3
C2 5-63

We end up with 4 disjoint load-balanced sets.

I would then attach the rt balance information to: C1, C2, B2, B3.

If, for example, B1 would be load-balanced, we'd only have 3 disjoint sets left: B1, B2 and B3, and the rt balance data would be there.

Quoted 18 lines

It sounds like Peter is reminding us that we really have three choices for a handling a given CPU's load balancing:
1) normal kernel scheduler load balancing,
2) RT load balancing, or
3) no load balancing whatsoever.

If that's the case (if we really need choice 3) then a single Boolean flag, such as sched_load_balance, is not sufficient to select from the three choices, and it might make sense to add a second per-cpuset Boolean flag, say "sched_rt_balance", default off, which if turned on, enabled choice 2.

If that's not the case (we only need choices 1 and 2) then -logically- we could overload the meaning of the current sched_load_balance, to mean, if turned off, not only to stop doing normal balancing, but to further mean that we should commence RT balancing. However bits aren't -that- precious here, and this sounds unnecessarily confusing.

Quoted 3 lines

So ... would a new per-cpuset Boolean flag such as sched_rt_balance be appropriate and sufficient to mark those cpusets whose set of CPUs required RT balancing?

So, I don't think we need that, I think we can do with the single flag, we just need to find these disjoint sets and stick our rt-domain there.

#14 lore raw
In reply to Paul Jackson

Paul, talking to himself:

Quoted 4 lines

At that point, sched domains are rebuilt, including providing a sched domain that just contains the CPUs in that realtime cpuset, and normal scheduler load balancing ceases on the CPUs in that realtime cpuset.

Oops - correction - at that point sched domains are rebuilt, and the CPUs in that realtime cpuset are not included in any sched domain at all.

Signature · 3 lines
                  I won't rest till it's the best ...
                  Programmer, Linux Scalability
                  Paul Jackson <[email protected]> 1.940.382.4214
#5 lore raw
In reply to Peter Zijlstra

Peter wrote;

Quoted 2 lines

So, I don't think we need that, I think we can do with the single flag, we just need to find these disjoint sets and stick our rt-domain there.

Ah - perhaps you don't need that flag - but my other cpuset users do ;).

You see, there are two very different ways that 'sched_load_balance' is used in practice.

The other way is by big batch schedulers. They may be placed in charge of managing a few hundred CPUs on a system, and might be running a mix of many small jobs each covering only a few CPUs. They routinely setup one cpuset for each job, to contain that job to the CPUs and memory nodes assigned to it. This is actually the original motivating use for cpusets.

As a bit of optimization, batch schedulers desire to tell the normal kernel scheduler -not- to bother load balancing across the big set of CPUs controlled by the batch scheduler, but only to load balance within each of the smaller per-job cpusets. Load balancing across hundreds of CPUs when the batch scheduler knows such efforts would be fruitless is a waste of good CPU cycles in kernel/sched.c.

I really doubt we'd want to have such systems triggering the hard RT scheduler on whatever CPUs were in the batch schedulers big cpuset that didn't happened to have an active job currently assigned to them.

Signature · 3 lines
                  I won't rest till it's the best ...
                  Programmer, Linux Scalability
                  Paul Jackson <[email protected]> 1.940.382.4214
#8 lore raw
In reply to Peter Zijlstra

Paul, responding to Peter:

Quoted 3 lines
Quoted 1 line

We now have a per-cpuset Boolean flag file called 'sched_load_balance'.

SD_LOAD_BALANCE, right?

No. SD_LOAD_BALANCE is some attribute of sched domains.

The 'sched_load_balance' flag is an attribute of cpusets.

The mapping of cpusets to sched domains required several pages of 'fun to write' code, which had to go through a couple of years of fixing and one major rewrite before it (knock on wood) worked correctly. It's not a one-to-one relation, in other words. See my earlier messages for further explanation of how this works.

I'm not sure what SD_LOAD_BALANCE does ... I guess from a quick read that it just optimizes the recognition of singleton sched domains for which load balancing would be a wasted effort.

Quoted 8 lines
Quoted 4 lines

This 'sched_load_balance' flag is, thus far, "the" cpuset hook supporting realtime. One can use it to configure a system so that the kernel does not do normal load balancing on select CPUs, such as those CPUs dedicated to realtime use.

Ah, here I disagree, it is possible to do (hard) realtime scheduling over multiple cpus, the only draw back is that it requires a very strong load-balancer, making it unsuitable for large number of cpus.

I don't think we are disagreeing. I was speaking of "normal" load balancing (what the mainline kernel/sched.c code normally does). You're speaking of hard realtime load balancing.

I think we agree that these both exist, and require different load balancing code, the latter 'very strong.'

Signature · 3 lines
                  I won't rest till it's the best ...
                  Programmer, Linux Scalability
                  Paul Jackson <[email protected]> 1.940.382.4214
#15 lore raw
In reply to Paul Jackson
Quoted 9 lines · Paul Jackson

Peter wrote, in reply to Peter ;):

Quoted 7 lines
Quoted 3 lines

[ It looks to me it balances a group over the largest SD the current cpu
has access to, even though that might be larger than the SD associated with the cpuset of that particular cgroup. ]

Hmm, with a bit more thought I think that does indeed DTRT. Because, if the cpu belongs to a disjoint cpuset, the highest sd (with load-balancing enabled) would be that. Right?

Quoted 6 lines

The code that defines sched domains, kernel/sched.c partition_sched_domains(), as called from the cpuset code in kernel/cpuset.c rebuild_sched_domains(), does not make use of the full range of sched_domain possibilities.

In particular, it only sets up some non-overlapping set of sched domains. Every CPU ends up in at most a single sched domain.

Ah, good to know. I thought it would reflect the hierarchy of the sets themselves.

Quoted 7 lines

The original reason that one can't define overlapping sched domains via this cpuset interface (based off the cpuset 'sched_load_balance' flag) is that I didn't realize it was even possible to overlap sched domains when I wrote the cpuset code defining sched domains. And then when I later realized one could overlap sched domains, I (a) didn't see a need to do so, and (b) couldn't see how to do so via the cpuset interface without causing my brain to explode.

Good reason :-), this code needs all the reasons it can grasp to not grow more complexity.

Quoted 9 lines

Now, back to Peter's question, being a bit pedantic, CPUs don't belong to disjoint cpusets, except in the most minimal situation that there is only one cpuset covering all CPUs.

Rather what happens, when you have need for some realtime CPUs, is that:
1) you turn off sched_load_balance on the top cpuset,
2) you setup your realtime cpuset as a child cpuset of the top cpuset such that its CPUs doesn't overlap any of its siblings, and
3) you turn off sched_load_balance in that realtime cpuset.

Ah, I don't think 3 is needed. Quite to the contrary, there is quite a large body of research work covering the scheduling of (hard and soft) realtime tasks on multiple cpus.

Quoted 4 lines

At that point, sched domains are rebuilt, including providing a sched domain that just contains the CPUs in that realtime cpuset, and normal scheduler load balancing ceases on the CPUs in that realtime cpuset.

Right, which would also disable the realtime load-balancing we do want. Hence my suggestion to stick the rt balance data in this sched domain.

Quoted 3 lines
Quoted 1 line

[ Just a bit of a shame we have all cgroups represented on each cpu. ]

Could you restate this -- I suspect it's obvious, but I'm oblivious ;).

Ah, sure. struct task_group creates cfs_rq/rt_rq entities for each cpu's runqueue. So an iteration like for_each_leaf_{cfs,rt}_rq() will touch all task_groups/cgroups, not only those that are actually schedulable on that cpu.

Now, I think that could be easily solved by adding/removing {cfs,rt}_rq->leaf_{cfs,rt}_rq_list to/from rq->leaf_{cfs,rt}_rq_list on enqueue of the first/dequeue of the last entity of its tg on that rq.

#16 lore raw

Peter, replying to Paul:

Quoted 5 lines
Quoted 1 line

3) you turn off sched_load_balance in that realtime cpuset.

Ah, I don't think 3 is needed. Quite to the contrary, there is quite a large body of research work covering the scheduling of (hard and soft) realtime tasks on multiple cpus.

Well, the way it's coded now, the user space code needs to do (3), because that's the only way they get the system to have anything other than one big fat sched domain covering the all the CPUs in the system.

Actually ... I need a picture of a bunny with a pancake hat here, as I have no idea what you just said ;).

Signature · 3 lines
                  I won't rest till it's the best ...
                  Programmer, Linux Scalability
                  Paul Jackson <[email protected]> 1.940.382.4214
#34 lore raw
In reply to Peter Zijlstra
Quoted 7 lines · Peter Zijlstra
Quoted 5 lines · Peter Zijlstra

My thoughts were to make stronger use of disjoint cpu-sets. cgroups and cpusets are related, in that cpusets provide a property to a cgroup. However, load_balance_monitor()'s interaction with sched domains confuses me - it might DTRT, but I can't tell.

Quoted 7 lines
Quoted 3 lines

[ It looks to me it balances a group over the largest SD the current cpu
has access to, even though that might be larger than the SD associated with the cpuset of that particular cgroup. ]

Hmm, with a bit more thought I think that does indeed DTRT. Because, if the cpu belongs to a disjoint cpuset, the highest sd (with load-balancing enabled) would be that. Right?

Hi Peter,
Yes, I was having this in mind when I wrote the load_balance_monitor()
function - to only balance across cpus that form a disjoint cpuset in the system.

Quoted 1 line

[ Just a bit of a shame we have all cgroups represented on each cpu. ]

After reading your explanation in the other mail abt what you mean here, I agree. Your suggestion to remove/add cfs_rq from/to the leaf_cfs_rq_list upon dequeue_of_last_task/enqueue_of_first_task AND

Quoted 3 lines

Also, might be a nice idea to split the daemon up if there are indeed disjoint sets - currently there is only a single daemon which touches the whole system.

the above suggestions seems like good ideas. I can also look at reducing the frequency at which the thread runs ..

Signature · 2 lines
Regards,
vatsa
#35 lore raw

vatsa wrote to Peter:

Quoted 2 lines

After reading your explanation in the other mail abt what you mean here, I agree.

Ah good - glad someone understood that.

Signature · 3 lines
                  I won't rest till it's the best ...
                  Programmer, Linux Scalability
                  Paul Jackson <[email protected]> 1.940.382.4214
#6 lore raw
In reply to Paul Jackson
Quoted 23 lines · Paul Jackson

Peter wrote;

Quoted 2 lines

So, I don't think we need that, I think we can do with the single flag, we just need to find these disjoint sets and stick our rt-domain there.

Ah - perhaps you don't need that flag - but my other cpuset users do ;).

You see, there are two very different ways that 'sched_load_balance' is used in practice.

The other way is by big batch schedulers. They may be placed in charge of managing a few hundred CPUs on a system, and might be running a mix of many small jobs each covering only a few CPUs. They routinely setup one cpuset for each job, to contain that job to the CPUs and memory nodes assigned to it. This is actually the original motivating use for cpusets.

As a bit of optimization, batch schedulers desire to tell the normal kernel scheduler -not- to bother load balancing across the big set of CPUs controlled by the batch scheduler, but only to load balance within each of the smaller per-job cpusets. Load balancing across hundreds of CPUs when the batch scheduler knows such efforts would be fruitless is a waste of good CPU cycles in kernel/sched.c.

Quoted 3 lines

I really doubt we'd want to have such systems triggering the hard RT scheduler on whatever CPUs were in the batch schedulers big cpuset that didn't happened to have an active job currently assigned to them.

My turn to be confused..

If SD_LOAD_BALANCE is only set on the smaller, per-job, sets, how will the RT balancer trigger on the large set?

#7 lore raw

Peter, responding to Paul:

Quoted 8 lines
Quoted 3 lines

I really doubt we'd want to have such systems triggering the hard RT scheduler on whatever CPUs were in the batch schedulers big cpuset that didn't happened to have an active job currently assigned to them.

My turn to be confused..

If SD_LOAD_BALANCE is only set on the smaller, per-job, sets, how will the RT balancer trigger on the large set?

What 'sched_load_balance' does now is help you setup a -partial- covering of non-overlappping sched domains. In the batch scheduler example, those CPUs that were:
1) being managed by the batch scheduler, but
2) were not assigned to any active job at the moment
would -not- be in any sched domain.

It's not a question of the SC_LOAD_BALANCE flag. It's a question of whether a given CPU is even included in any sched domain.

If we did as you are suggesting (if I understand) then instead of leaving these CPUs out of any sched domain, rather we'd setup a new kind of sched domain for these CPUs, marked for hard real time load balancing, rather than the somewhat more scalable, but softer normal load balancing.

We want no load balancing on those CPUs, not realtime load balancing. Indeed, I suspect, we especially do not want realtime load balancing on those CPUs as that kind of load balancing is (I'm suspecting) more expensive and less scalable than normal load balancing.

Signature · 3 lines
                  I won't rest till it's the best ...
                  Programmer, Linux Scalability
                  Paul Jackson <[email protected]> 1.940.382.4214
#9 lore raw
In reply to Paul Jackson
Quoted 7 lines · Paul Jackson

Paul, responding to Peter:

Quoted 3 lines
Quoted 1 line

We now have a per-cpuset Boolean flag file called 'sched_load_balance'.

SD_LOAD_BALANCE, right?

No. SD_LOAD_BALANCE is some attribute of sched domains.

Quoted 7 lines

The 'sched_load_balance' flag is an attribute of cpusets.

The mapping of cpusets to sched domains required several pages of 'fun to write' code, which had to go through a couple of years of fixing and one major rewrite before it (knock on wood) worked correctly. It's not a one-to-one relation, in other words. See my earlier messages for further explanation of how this works.

Ok, I'll take a stab at understanding that code. Perhaps it seems to me a lot of confusion could be solved by getting a more level playing ground :-)

Quoted 9 lines
Quoted 8 lines
Quoted 4 lines

This 'sched_load_balance' flag is, thus far, "the" cpuset hook supporting realtime. One can use it to configure a system so that the kernel does not do normal load balancing on select CPUs, such as those CPUs dedicated to realtime use.

Ah, here I disagree, it is possible to do (hard) realtime scheduling over multiple cpus, the only draw back is that it requires a very strong load-balancer, making it unsuitable for large number of cpus.

Quoted 6 lines

I don't think we are disagreeing. I was speaking of "normal" load balancing (what the mainline kernel/sched.c code normally does). You're speaking of hard realtime load balancing.

I think we agree that these both exist, and require different load balancing code, the latter 'very strong.'

Great :-)

#10 lore raw
Quoted 1 line

Ok, I'll take a stab at understanding that code.

See also the section:

1.7 What is sched_load_balance ?

in Documentation/cpusets.txt.

Good luck ;).

Signature · 3 lines
                  I won't rest till it's the best ...
                  Programmer, Linux Scalability
                  Paul Jackson <[email protected]> 1.940.382.4214
#11 lore raw
Quoted 9 lines · Paul Jackson
Quoted 1 line

Ok, I'll take a stab at understanding that code.

See also the section:

1.7 What is sched_load_balance ?

in Documentation/cpusets.txt.

Good luck ;).

It seems Gregory tricked us both:

57d885fea0da0e9541d7730a9e1dcf734981a173

#19 lore raw
In reply to Peter Zijlstra
Quoted 1 line
Quoted 1 line
Quoted 1 line

On Tue, Jan 29, 2008 at 6:50 AM, in message

<1201607401.28547.124.camel@lappy>, Peter Zijlstra <[email protected]>

Quoted 42 lines · wrote:
Quoted 10 lines · Paul Jackson

Peter wrote, in reply to Peter ;):

Quoted 7 lines
Quoted 3 lines

[ It looks to me it balances a group over the largest SD the current cpu
has access to, even though that might be larger than the SD associated with the cpuset of that particular cgroup. ]

Hmm, with a bit more thought I think that does indeed DTRT. Because, if the cpu belongs to a disjoint cpuset, the highest sd (with load-balancing enabled) would be that. Right?

The code that defines sched domains, kernel/sched.c

partition_sched_domains(),

Quoted 5 lines

as called from the cpuset code in kernel/cpuset.c rebuild_sched_domains(), does not make use of the full range of sched_domain possibilities.

In particular, it only sets up some non-overlapping set of sched domains. Every CPU ends up in at most a single sched domain.

Ah, good to know. I thought it would reflect the hierarchy of the sets themselves.

Quoted 7 lines

The original reason that one can't define overlapping sched domains via this cpuset interface (based off the cpuset 'sched_load_balance' flag) is that I didn't realize it was even possible to overlap sched domains when I wrote the cpuset code defining sched domains. And then when I later realized one could overlap sched domains, I (a) didn't see a need to do so, and (b) couldn't see how to do so via the cpuset interface without causing my brain to explode.

Good reason :-), this code needs all the reasons it can grasp to not grow more complexity.

Quoted 9 lines

Now, back to Peter's question, being a bit pedantic, CPUs don't belong to disjoint cpusets, except in the most minimal situation that there is only one cpuset covering all CPUs.

Rather what happens, when you have need for some realtime CPUs, is that:
1) you turn off sched_load_balance on the top cpuset,
2) you setup your realtime cpuset as a child cpuset of the top cpuset such that its CPUs doesn't overlap any of its siblings, and
3) you turn off sched_load_balance in that realtime cpuset.

Quoted 3 lines

Ah, I don't think 3 is needed. Quite to the contrary, there is quite a large body of research work covering the scheduling of (hard and soft) realtime tasks on multiple cpus.

This is correct. We have the balance policy polymorphically associated with each sched_class, and the CFS load-balancer and RT "load" (really, priority) balancer can coexist together at the same time and across arbitrary #s of cores. From an RT perspective, this works great. Its a little trickier (and I dont think we have this quite right, yet) for the CFS side, since that interface deals strictly in terms of load. As such, it gets a little perturbed by these "rude" RT tasks that arbitrarily preempt its tasks. :) I think Steven may have done some work in that area by playing with the associated weight of RT tasks, etc so that the CFS balancer can more accurate account for the externally managed RT load on the system. But AFAIK, its not in the tree yet.

Quoted 21 lines
Quoted 5 lines

At that point, sched domains are rebuilt, including providing a sched domain that just contains the CPUs in that realtime cpuset, and normal scheduler load balancing ceases on the CPUs in that realtime cpuset.

Right, which would also disable the realtime load-balancing we do want. Hence my suggestion to stick the rt balance data in this sched domain.

Quoted 3 lines
Quoted 1 line

[ Just a bit of a shame we have all cgroups represented on each cpu. ]

Could you restate this -- I suspect it's obvious, but I'm oblivious ;).

Ah, sure. struct task_group creates cfs_rq/rt_rq entities for each cpu's runqueue. So an iteration like for_each_leaf_{cfs,rt}_rq() will touch all task_groups/cgroups, not only those that are actually schedulable on that cpu.

Now, I think that could be easily solved by adding/removing {cfs,rt}_rq->leaf_{cfs,rt}_rq_list to/from rq->leaf_{cfs,rt}_rq_list on enqueue of the first/dequeue of the last entity of its tg on that rq.

#26 lore raw
In reply to Paul Jackson
Quoted 1 line
Quoted 1 line
Quoted 1 line

On Tue, Jan 29, 2008 at 6:30 AM, in message

Quoted 35 lines · Paul Jackson

Peter wrote, in reply to Peter ;):

Quoted 7 lines
Quoted 3 lines

[ It looks to me it balances a group over the largest SD the current cpu
has access to, even though that might be larger than the SD associated with the cpuset of that particular cgroup. ]

Hmm, with a bit more thought I think that does indeed DTRT. Because, if the cpu belongs to a disjoint cpuset, the highest sd (with load-balancing enabled) would be that. Right?

The code that defines sched domains, kernel/sched.c partition_sched_domains(),
as called from the cpuset code in kernel/cpuset.c rebuild_sched_domains(), does not make use of the full range of sched_domain possibilities.

In particular, it only sets up some non-overlapping set of sched domains. Every CPU ends up in at most a single sched domain.

The original reason that one can't define overlapping sched domains via this cpuset interface (based off the cpuset 'sched_load_balance' flag) is that I didn't realize it was even possible to overlap sched domains when I wrote the cpuset code defining sched domains. And then when I later realized one could overlap sched domains, I (a) didn't see a need to do so, and (b) couldn't see how to do so via the cpuset interface without causing my brain to explode.

Now, back to Peter's question, being a bit pedantic, CPUs don't belong to disjoint cpusets, except in the most minimal situation that there is only one cpuset covering all CPUs.

Rather what happens, when you have need for some realtime CPUs, is that:
1) you turn off sched_load_balance on the top cpuset,
2) you setup your realtime cpuset as a child cpuset of the top cpuset such that its CPUs doesn't overlap any of its siblings, and
3) you turn off sched_load_balance in that realtime cpuset.

Quoted 4 lines

At that point, sched domains are rebuilt, including providing a sched domain that just contains the CPUs in that realtime cpuset, and normal scheduler load balancing ceases on the CPUs in that realtime cpuset.

Hi Paul,
I am a bit confused as to why you disable load-balancing in the RT cpuset? It shouldn't be strictly necessary in order for the RT scheduler to do its job (unless I am misunderstanding what you are trying to accomplish?). Do you do this because you *have* to in order to make real-time deadlines, or because its just a further optimization?

-Greg

Quoted 4 lines
Quoted 2 lines

[ Just a bit of a shame we have all cgroups represented on each cpu. ]

Could you restate this -- I suspect it's obvious, but I'm oblivious ;).

#17 lore raw
In reply to Paul Jackson
Quoted 1 line
Quoted 1 line
Quoted 1 line

On Tue, Jan 29, 2008 at 7:12 AM, in message

Quoted 11 lines · Paul Jackson

Peter, replying to Paul:

Quoted 5 lines
Quoted 1 line

3) you turn off sched_load_balance in that realtime cpuset.

Ah, I don't think 3 is needed. Quite to the contrary, there is quite a large body of research work covering the scheduling of (hard and soft) realtime tasks on multiple cpus.

Well, the way it's coded now, the user space code needs to do (3), because that's the only way they get the system to have anything other than one big fat sched domain covering the all the CPUs in the system.

What about exclusive cpusets? Don't they create a new sched-domain or did I misunderstand there?

-Greg

Quoted 3 lines

Actually ... I need a picture of a bunny with a pancake hat here, as I have no idea what you just said ;).

#27 lore raw
In reply to Gregory Haskins
Quoted 6 lines · Gregory

I am a bit confused as to why you disable load-balancing in the RT cpuset? It shouldn't be strictly necessary in order for the RT scheduler to do its job (unless I am misunderstanding what you are trying to accomplish?). Do you do this because you *have* to in order to make real-time deadlines, or because its just a further optimization?

My primary motivation for cpusets originally, and for the sched_load_balance flag now, was not realtime, but "soft partitioning" of big NUMA systems, especially for batch schedulers. They sometimes have large cpusets which are only being used to hold smaller, per-job, cpusets. It is a waste of time (CPU cycles in the kernel sched code) to load balance those large cpusets. Load balancing doesn't scale easily to high CPU counts, and it's nice to avoid doing that where not needed.

See the following lkml message for a fuller explanation:

http://lkml.org/lkml/2008/1/29/85

As a secondary motivation, I thought that disabling load balancing on the RT cpuset was the right thing to do for RT needs, but I make no claim to knowing much about RT.

I just now realized that you added a 'root_domain' in a patch in
late Nov and early Dec. I was on the road then, moving from
California to Texas, and not paying much attention to Linux.

A couple of questions on that patch, both involving a comment it adds to kernel/sched.c:

/*
* We add the notion of a root-domain which will be used to define per-domain
* variables. Each exclusive cpuset essentially defines an island domain by
* fully partitioning the member cpus from any other cpuset. Whenever a new
* exclusive cpuset is created, we also create and attach a new root-domain
* object.
*/

1) What are 'per-domain' variables?

2) The mention of 'exclusive cpuset' is no longer correct.

With the patch 'remove sched domain hooks from cpusets' cpusets no longer defines sched domains using the cpu_exclusive flag.

With the subsequent sched_load_balance patch (see
http://lkml.org/lkml/2007/10/6/19) cpusets uses a new per-cpuset flag 'sched_load_balance' to define sched domains.

The following revised comment might be more accurate:

/*
* We add the notion of a root-domain which will be used to define per-domain
* variables. Each non-overlapping sched domain defines an island domain by
* fully partitioning the member cpus from any other cpuset. Whenever a new
* such a sched domain is created, we also create and attach a new root-domain
* object. These non-overlapping sched domains are determined by the cpuset
* configuration, via a call to partition_sched_domains().
*/

It sounds like you (Gregory, others) want your RT CPUs to be in a sched domain, unlike the current way things are, where my cpuset code carefully avoids setting up a sched domain for those CPUs. However I still have need, in the batch scheduler case explained above, to have some CPUs not in any sched domain.

If you require these RT sched domains to be setup differently somehow, in some way that is visible to partition_sched_domains, then that apparently means we need a per-cpuset flag to mark those RT cpusets.

If you just want an ordinary sched domain setup (just so long as it contains only the intended RT CPUs, not others) then I guess we don't technically need any more per-cpuset flags, but I'm worried, because the API we're presenting to users for this has just gone from subtle to bizarre. I suspect I'll want to add a flag anyway, if by doing so, I can make the kernel-user API, via cpusets, easier to understand.

Signature · 3 lines
                  I won't rest till it's the best ...
                  Programmer, Linux Scalability
                  Paul Jackson <[email protected]> 1.940.382.4214
#18 lore raw
In reply to Gregory Haskins
Quoted 2 lines · Gregory

What about exclusive cpusets? Don't they create a new sched-domain or did I misunderstand there?

cpu_exclusive cpusets no longer determine sched domains. I just said more in this in an earlier reply.

Signature · 3 lines
                  I won't rest till it's the best ...
                  Programmer, Linux Scalability
                  Paul Jackson <[email protected]> 1.940.382.4214
#28 lore raw
In reply to Paul Jackson
Quoted 1 line
Quoted 1 line
Quoted 1 line

On Tue, Jan 29, 2008 at 11:28 AM, in message

Quoted 8 lines · Paul Jackson
Quoted 6 lines · Gregory

I am a bit confused as to why you disable load-balancing in the RT cpuset? It shouldn't be strictly necessary in order for the RT scheduler to do its job (unless I am misunderstanding what you are trying to accomplish?). Do you do this because you *have* to in order to make real-time deadlines, or because its just a further optimization?

Quoted 8 lines

My primary motivation for cpusets originally, and for the sched_load_balance flag now, was not realtime, but "soft partitioning" of big NUMA systems, especially for batch schedulers. They sometimes have large cpusets which are only being used to hold smaller, per-job, cpusets. It is a waste of time (CPU cycles in the kernel sched code) to load balance those large cpusets. Load balancing doesn't scale easily to high CPU counts, and it's nice to avoid doing that where not needed.

Understood, and that makes tons of sense.

Quoted 8 lines

See the following lkml message for a fuller explanation:

http://lkml.org/lkml/2008/1/29/85

As a secondary motivation, I thought that disabling load balancing on the RT cpuset was the right thing to do for RT needs, but I make no claim to knowing much about RT.

Well, I make no claim to understand the large batch systems you work on either ;) Everything you said made a ton of sense other than the RT/load-balance thing, but I think we are on the same page now.

Quoted 4 lines

I just now realized that you added a 'root_domain' in a patch in
late Nov and early Dec. I was on the road then, moving from
California to Texas, and not paying much attention to Linux.

np (though I was wondering why you had no comment before ;)

Quoted 12 lines

A couple of questions on that patch, both involving a comment it adds to kernel/sched.c:

/*
* We add the notion of a root-domain which will be used to define per-domain
* variables. Each exclusive cpuset essentially defines an island domain by
* fully partitioning the member cpus from any other cpuset. Whenever a new
* exclusive cpuset is created, we also create and attach a new root-domain
* object.
*/

Quoted 1 line

1) What are 'per-domain' variables?

s/per-domain/per-root-domain

Quoted 9 lines

2) The mention of 'exclusive cpuset' is no longer correct.

With the patch 'remove sched domain hooks from cpusets' cpusets no longer defines sched domains using the cpu_exclusive flag.

With the subsequent sched_load_balance patch (see
http://lkml.org/lkml/2007/10/6/19) cpusets uses a new per-cpuset flag 'sched_load_balance' to define sched domains.

Doh! Thanks for the heads up.

Quoted 19 lines

The following revised comment might be more accurate:

/*
* We add the notion of a root-domain which will be used to define per-domain
* variables. Each non-overlapping sched domain defines an island domain by
* fully partitioning the member cpus from any other cpuset. Whenever a new
* such a sched domain is created, we also create and attach a new
root-domain
* object. These non-overlapping sched domains are determined by the cpuset
* configuration, via a call to partition_sched_domains().
*/

It sounds like you (Gregory, others) want your RT CPUs to be in a sched domain, unlike the current way things are, where my cpuset code carefully avoids setting up a sched domain for those CPUs. However I still have need, in the batch scheduler case explained above, to have some CPUs not in any sched domain.

Quoted 3 lines

If you require these RT sched domains to be setup differently somehow, in some way that is visible to partition_sched_domains, then that apparently means we need a per-cpuset flag to mark those RT cpusets.

I think we only need a plain-vanilla partition, so no flags should be necessary.

-Greg

Quoted 7 lines

If you just want an ordinary sched domain setup (just so long as it contains only the intended RT CPUs, not others) then I guess we don't technically need any more per-cpuset flags, but I'm worried, because the API we're presenting to users for this has just gone from subtle to bizarre. I suspect I'll want to add a flag anyway, if by doing so, I can make the kernel-user API, via cpusets, easier to understand.

#20 lore raw
In reply to Gregory Haskins
Quoted 4 lines · Gregory

This is correct. We have the balance policy polymorphically associated with each sched_class, and the CFS load-balancer and RT "load" (really, priority) balancer can coexist together at the same time and across arbitrary #s of cores

So ... we have the option of having all sched_classes coexist polymorphically.

That I didn't realize until this thread.

Now ... do we -want- to ?)

That is, what is the easiest kernel-user API to work with and understand?

Is it one where we essentially expose sched_class to user space, and let them pick their sched_class, or pick none of the above (don't balance)?

Or is it one where, other than the special case my batch schedulers need to not balance at all, we expose nothing more to user space, and provide all sched_class load balancers to all sched_domains (other than those not balanced at all)?

Signature · 3 lines
                  I won't rest till it's the best ...
                  Programmer, Linux Scalability
                  Paul Jackson <[email protected]> 1.940.382.4214
#21 lore raw
Quoted 1 line
Quoted 1 line
Quoted 1 line

On Tue, Jan 29, 2008 at 11:51 AM, in message

Quoted 10 lines · Paul Jackson
Quoted 4 lines · Gregory

This is correct. We have the balance policy polymorphically associated with each sched_class, and the CFS load-balancer and RT "load" (really, priority) balancer can coexist together at the same time and across arbitrary #s of cores

So ... we have the option of having all sched_classes coexist polymorphically.

That I didn't realize until this thread.

Its on a per-task basis when the task elects SCHED_FIFO/RR/BATCH/OTHER, etc. If the task is on a particular RQ, the RQ operates under the policy of that class. There are some cases where the RQ consults the policy of all classes, but they are still influenced by whether there are actual tasks running within the scope of the current cpuset (or root-domain).

Quoted 2 lines

Now ... do we -want- to ?)

I think so, yes. But I will give the disclaimer that I don't fully understand your world ;)

You could certainly create a group of cpus with homogeneous policy by creating a cpuset with only tasks of a single class as members. But likewise, if you populate a cpuset with tasks from mixed classes, you have mixed balance policy affecting those cpus.

Quoted 5 lines

That is, what is the easiest kernel-user API to work with and understand?

Is it one where we essentially expose sched_class to user space, and let them pick their sched_class, or pick none of the above (don't balance)?

IMHO it works well the way it is: The user selects the class for a particular task using sched_setscheduler(), and they select the cpuset (or inherit it) that defines its execution scope. If that scope has balancing enabled, the policy for the member classes is in effect.

(on this topic, note that I do not know if the RT-balancer will respect the cpuset concept of "balance-enabled" anyway. That might have to be fixed)

Again, the disclaimer that I do not have expertise in your area, so perhaps this is naive.

Quoted 5 lines

Or is it one where, other than the special case my batch schedulers need to not balance at all, we expose nothing more to user space, and provide all sched_class load balancers to all sched_domains (other than those not balanced at all)?

#22 lore raw
Quoted 4 lines · Gregory

IMHO it works well the way it is: The user selects the class for a particular task using sched_setscheduler(), and they select the cpuset (or inherit it) that defines its execution scope. If that scope has balancing enabled, the policy for the member classes is in effect.

Ok.

For the various classes of schedulers (sched_class's), it's fine by me if sched domains are polymorphic, supporting all classes, and it is left to each task to self-select the scheduling class of its preference.

For the batch scheduler case, this -must- be imposable from outside the task, by the batch scheduler that is overseeing the job, and it must support the batch scheduler being able to disable all the balancers in selected cpusets (selected sched_domains).

We have that now. Each of us only knew of part of the solution, but we managed to arrive at the desired answer even so ... amazing.

The batch scheduler just has to arrange to get 'sched_load_balance' turned off in a cpuset and all overlapping cpusets, and then the CPUS in that cpuset will not belong to -any- sched_domain, and hence (could you verify I'm right in this detail?) won't be balanced by any sched_class.

I should update the documentation for sched_load_balance, changing it from saying that you get realtime by turning off sched_load_balance in the RT cpuset, to saying that you get realtime by (1) turning off sched_load_balance in any overlapping cpusets, including all encompassing parent cpusets, (2) leaving sched_load_balance on in the RT cpuset itself, and (3) having those realtime tasks each self-select (elect) the desired SCHED_* using sched_setscheduler().

Condition (1) above is a tad difficult to understand, but servicable, I guess. The combination of (1) and (2) results in a separate sched_domain just for the CPUs in the RT cpuset.

Quoted 3 lines

(on this topic, note that I do not know if the RT-balancer will respect the cpuset concept of "balance-enabled" anyway. That might have to be fixed)

Er eh ... it has no choice. If the user space code has configured a cpuset with 'sched_load_balance' turned off in that cpuset and all overlapping cpusets, then there will not even be a sched_domain covering those CPUs, and hence no balancer, RT or other class, will even see those CPUs.

Unless I really don't understand the kernel/sched.c sched_domain code (a distinct possibility), if some CPU is not in any sched_domain, then it won't get balanced, RT or otherwise.

Signature · 3 lines
                  I won't rest till it's the best ...
                  Programmer, Linux Scalability
                  Paul Jackson <[email protected]> 1.940.382.4214
#29 lore raw
In reply to Gregory Haskins
Quoted 3 lines · Gregory
Quoted 1 line

1) What are 'per-domain' variables?

s/per-domain/per-root-domain

Oh dear - now I've got more questions, not fewer.

1) "variables" ... what variables?

2) Is a 'root-domain' just the RT specific portion of a sched_domain, or is it something else?

Signature · 3 lines
                  I won't rest till it's the best ...
                  Programmer, Linux Scalability
                  Paul Jackson <[email protected]> 1.940.382.4214
#30 lore raw
Quoted 1 line
Quoted 1 line
Quoted 1 line

On Tue, Jan 29, 2008 at 2:37 PM, in message

Quoted 8 lines · Paul Jackson
Quoted 3 lines · Gregory
Quoted 1 line

1) What are 'per-domain' variables?

s/per-domain/per-root-domain

Oh dear - now I've got more questions, not fewer.

1) "variables" ... what variables?

Well, anything that is declared in "struct root_domain" in kernel/sched.c.

For instance, today in mainline we have:

struct root_domain {
	atomic_t refcount;
	cpumask_t span;
	cpumask_t online;

	/*
	 * The "RT overload" flag: it gets set if a CPU has more than
	 * one runnable RT task.
	 */
	cpumask_t rto_mask;
	atomic_t rto_count;
};

The first three are just related to general root-domain infrastructure code. The last two in this case are related specifically to the rt-overload feature. In earlier versions of rt-balance, the rt-overload bitmap was a global variable. By moving it into the root_domain structure, there is now an instance per (um, for lack of a better, more up to date word) "exclusive" cpuset. That way, disparate cpusets will not bother each other with overload notifications, etc.

Note that in -rt, we have more variables in this structure (RQ priority info) but that patch hasnt been pulled into sched-devel/linux-2.6 yet.

Quoted 3 lines

2) Is a 'root-domain' just the RT specific portion of a sched_domain, or is it something else?

Its meant to be general, but the only current client is the RT sched_class. Reading back through the links you guys have been sending, its very similar in concept to the "rt-domain" stuff that you, Peter, and Steven were discussing a while back.

When I was originally putting this stuff together, I wanted to piggy back this data in the sched-domain code. But I soon realized that the sched-domain trees are per-cpu structures. What I needed was an "umbrella" structure that would allow cpus in a common cpuset to share arbitrary state data, but yet were associated with the sched-domains that the cpuset code setup. The first pass had the structures associated with the sched-domain hierarchy, but I soon realized that it was really a per-rq association so I could simplify the design. I.e.. Rather than have the code walk the sched-domain to find the common "root", I just hung the root directly on the rq itself.

But anyway, to answer the question: The concept is meant to be generic. For instance, if it made sense for Peters cgroup work to sit here as well, we could just add new fields to the struct root_domain and Peter could access them via rq->rd.

I realize that it could possibly have been designed to abstract away the type of objects that the root-domain manages, but I want to keep the initial code as simple as possible. We can always complicate^h^h^h^h^hcleanup the code later ;)

Regards,
-Greg

#23 lore raw
In reply to Paul Jackson
Quoted 1 line
Quoted 1 line
Quoted 1 line

On Tue, Jan 29, 2008 at 2:04 PM, in message

Quoted 17 lines · Paul Jackson
Quoted 4 lines · Gregory

IMHO it works well the way it is: The user selects the class for a particular task using sched_setscheduler(), and they select the cpuset (or inherit it) that defines its execution scope. If that scope has balancing enabled, the policy for the member classes is in effect.

Ok.

For the various classes of schedulers (sched_class's), it's fine by me if sched domains are polymorphic, supporting all classes, and it is left to each task to self-select the scheduling class of its preference.

For the batch scheduler case, this -must- be imposable from outside the task, by the batch scheduler that is overseeing the job, and it must support the batch scheduler being able to disable all the balancers in selected cpusets (selected sched_domains).

Quoted 8 lines

We have that now. Each of us only knew of part of the solution, but we managed to arrive at the desired answer even so ... amazing.

The batch scheduler just has to arrange to get 'sched_load_balance' turned off in a cpuset and all overlapping cpusets, and then the CPUS in that cpuset will not belong to -any- sched_domain, and hence (could you verify I'm right in this detail?) won't be balanced by any sched_class.

I am a little fuzzy on how this would work, so I cant say for certain. :) But it seems like that is accurate.

Quoted 9 lines

I should update the documentation for sched_load_balance, changing it from saying that you get realtime by turning off sched_load_balance in the RT cpuset, to saying that you get realtime by (1) turning off sched_load_balance in any overlapping cpusets, including all encompassing parent cpusets, (2) leaving sched_load_balance on in the RT cpuset itself, and (3) having those realtime tasks each self-select (elect) the desired SCHED_* using sched_setscheduler().

Quoted 3 lines

Condition (1) above is a tad difficult to understand, but servicable, I guess. The combination of (1) and (2) results in a separate sched_domain just for the CPUs in the RT cpuset.

Technically you only need (2). I run my 4-8 core development systems in the single default global cpuset, normally. Customers typically do use multiple sets, but we only use the vanilla balanced variety.

Quoted 11 lines
Quoted 4 lines

(on this topic, note that I do not know if the RT-balancer will respect the cpuset concept of "balance-enabled" anyway. That might have to be fixed)

Er eh ... it has no choice. If the user space code has configured a cpuset with 'sched_load_balance' turned off in that cpuset and all overlapping cpusets, then there will not even be a sched_domain covering those CPUs, and hence no balancer, RT or other class, will even see those CPUs.

Quoted 3 lines

Unless I really don't understand the kernel/sched.c sched_domain code (a distinct possibility), if some CPU is not in any sched_domain, then it won't get balanced, RT or otherwise.

Heh...I cant quite wrap my head around that, but it sounds like you are correct. The only thing I was really pointing out is that the RT code doesn't necessarily look at sched-domain flags before making balancing decisions. So as long as that is not a requirement, I think we are all set.

#31 lore raw
In reply to Gregory Haskins
Quoted 4 lines · Gregory

By moving it into the root_domain structure, there is now an instance per (um, for lack of a better, more up to date word) "exclusive"
cpuset. That way, disparate cpusets will not bother each other with
overload notifications, etc.

So the root_domain structure is meant to be the portions of the sched_domains that are shared across all CPUs in that sched_domain ?

And the word 'cpuset', occurring in the above quote twice, should be 'sched_domain', right ? Surely these aren't cpuset's ;).

And 'exclusive cpuset' really means 'non-overlapping sched_domain' ?

Or am I still confused ?

I would like to get our concepts clear, and terms consistent. That's important for those others who would try to understand this.

Signature · 3 lines
                  I won't rest till it's the best ...
                  Programmer, Linux Scalability
                  Paul Jackson <[email protected]> 1.940.382.4214
#24 lore raw
In reply to Gregory Haskins
Quoted 7 lines · Gregory
Quoted 4 lines

... (1) turning off
sched_load_balance in any overlapping cpusets, including all encompassing parent cpusets, (2) leaving sched_load_balance on in the RT cpuset itself, and ...

Technically you only need (2). I run my 4-8 core development systems in the single default global cpuset, normally.

Well, if you're running in the default cpuset, then you automatically get (1), because sched_load_balance is turned off in all overlapping cpusets (there aren't any overlapping cpusets!)

So, yes, you -do- need both (1) and (2). In your normal system, you just happen to get (1) effortlessly.

Signature · 3 lines
                  I won't rest till it's the best ...
                  Programmer, Linux Scalability
                  Paul Jackson <[email protected]> 1.940.382.4214
#32 lore raw
In reply to Paul Jackson
Quoted 1 line
Quoted 1 line
Quoted 1 line

On Tue, Jan 29, 2008 at 3:56 PM, in message

Quoted 8 lines · Paul Jackson
Quoted 4 lines · Gregory

By moving it into the root_domain structure, there is now an instance per (um, for lack of a better, more up to date word) "exclusive"
cpuset. That way, disparate cpusets will not bother each other with
overload notifications, etc.

So the root_domain structure is meant to be the portions of the sched_domains that are shared across all CPUs in that sched_domain ?

Thats exactly right.

Quoted 3 lines

And the word 'cpuset', occurring in the above quote twice, should be 'sched_domain', right ? Surely these aren't cpuset's ;).

Yeah, I think I am taking shortcuts in the language ;). I wanted the root_domain to be an object of shared data that sits at the "root sched_domain", or in other terms the terminating parent in the hierarchy. And there is one of these suckers created every time a non-overlapping cpuset is created (which was called "exclusive" at the time I wrote it, I believe, but I keep forgetting what you said they are called now ;). So because the non-overlapping cpuset configuration begat the sched_domain hierarchy, I started using them interchangeably. Sorry for the confusion :)

Quoted 4 lines

And 'exclusive cpuset' really means 'non-overlapping sched_domain' ?

Or am I still confused ?

No, I think you nailed it.

Quoted 3 lines

I would like to get our concepts clear, and terms consistent. That's important for those others who would try to understand this.

Very good idea. Thanks for doing this!

-Greg

#25 lore raw
In reply to Paul Jackson
Quoted 1 line
Quoted 1 line
Quoted 1 line

On Tue, Jan 29, 2008 at 4:02 PM, in message

Quoted 9 lines · Paul Jackson
Quoted 7 lines · Gregory
Quoted 4 lines

... (1) turning off
sched_load_balance in any overlapping cpusets, including all encompassing parent cpusets, (2) leaving sched_load_balance on in the RT cpuset itself, and ...

Technically you only need (2). I run my 4-8 core development systems in the single default global cpuset, normally.

Quoted 7 lines

Well, if you're running in the default cpuset, then you automatically get (1),
because sched_load_balance is turned off in all overlapping cpusets (there aren't any overlapping cpusets!)

So, yes, you -do- need both (1) and (2). In your normal system, you just happen to get (1) effortlessly.

Ah. Well see, I am just showing my ignorance of this area of the cpuset code then. I stand corrected, and sorry for the noise. :)

-Greg

#33 lore raw
In reply to Gregory Haskins
Quoted 6 lines · Gregory Haskins
Quoted 3 lines

I would like to get our concepts clear, and terms consistent. That's important for those others who would try to understand this.

Very good idea. Thanks for doing this!

Sorry for coming in so late, I've been banging my head on different bugs all day.

Just to clear up what our goal for the RT balancer was, and how simple it is ;-) Basically any task that has an RT priority needs to run ASAP from the time it woke up if there's a CPU available that it can run on and it has a higher priority than what is currently running on that CPU.

If an RT task wakes up, and there's a CPU available somewhere for it to run on, we want the RT task to jump to that CPU and run. RT tasks should not be waiting around for nice load balancing that optimizes the cache usage. But we also have a problem as well. We don't want to kill the cache on large NUMA architectures by looking for places for on RT task to run. With domains, we first look for a place that an RT task can run on a local CPU in the node, if so, then place it there, otherwise look at other nodes to run on.

Note, that the RT balancing is aggressive and not passive. That means that the balancing takes place at the time the RT task is awoken (perhaps by the task that is waking it) or at the time a task changes priority. It is not passive, being that it waits for something else to migrate it (i.e. migration thread)

Paul, I think you now understand that we don't have some scheduler domain that is specific for RT. The scheduling class is specific to the priority of the process and not to what domain it is in. But if you keep a domain invisible to an RT task, that domain never needs to worry about RT tasks migrating to it.

The code that Gregory and I have been adding was to try to migrate RT tasks to CPUs they can run on as quick as possible without algorithms that cause cacheline bouncing.

-- Steve