why are scheduling domains used in multiprocessor systems

[Preeti U Murthy]

On 01/09/2013 01:33 PM, Bond wrote:

> The answer of the question that I want to know is
> why is a scheduling domain actually needed?

Scheduling domains and scheduler groups/cpu groups help to ease the
process of scheduling tasks like:
1.load balancing tasks across cpus.
2.choosing a cpu for a new task to run on.
3.choosing a cpu for a sleeping task to run when it wakes up.

It has a two fold advantage:
1.It organises the cpus in the system very well into groups and hierarchies.
2.It organises the cpus in such a way that it is useful.All cpus which
share an l2 cache belong to one domain.All cpus which share an l3 cache
belong to a higher level domain,which encompasses all the domains which
share the l2 cache.

The advantages that you see with a tree like data structure are similar
here to the advantages of scheduler domains and groups.

Let me explain the use cases with a simple diagram:

 _________sd1________
/                    \
----------------------
     l3 cache
----------------------
---------   ----------
l2 cache    l2 cache
---------   ----------
cpu0 cpu1   cpu2 cpu3
\_______/   \________/
  sd0          sd0


 ________sd1_________
/                    \
----------------------
      l3 cache
----------------------
---------   ----------
l2 cache    l2 cache
---------   ----------
cpu4 cpu5   cpu6 cpu7
\_______/   \________/
  sd0          sd0

What you see above is a scheduler domain hierarchy.sd1 encompasses sd0s
which happen to be scheduler groups of sd1.Every cpu has a scheduler
domain hierarchy associated with it.For eg.
cpu0->sd=sd0; sd0->parent=sd1.This way through a linked list we can
iterate through all the scheduler domains to which a cpu belongs to.

How does this help?

1.load balancing: Say cpu0 is idle and is ready to pull tasks upon
itself to relieve any other burdened cpu.In the above approach,it first
checks if the other cpus that belong to the first level sched domain
,needs to be relieved of load.Here, cpu1.If so it takes on tasks from
cpu1,else it goes to the higher level domain sd1.If it chooses to
migrate task from cpu1 it is the best thing,because the cache contents
can be utilized;shared cache.no need to fetch from memory again.This is
the first advantage:sched domains are formed based upon the advantages
that hardware has to provide.

If it goes to sd1,then it probes sd1's 'groups',both the sd0s.Here is
the next advantage.It needs information about the sched group alone and
will not bother about the individual cpus in it.it checks if
load(sd0[cpu2,cpu3]) > load(sd0[cpu0,cpu1])
Only if this is true does it go on to see if cpu2/3 is more loaded.If
there were no scheduler domain or groups,we would have to see the states
of cpu2 and cpu3 in two iterations instead of 1 iteration like we are
doing now.

Now scale this problem and solution to 128 cpus! imagine what a mess it
would have been if there was nothing to tell you which cpu would be the
best to relieve load from,in the worst case you would have to iterate
through all the 128 cpus.

But with scheduler domain or groups,say you divide the 128 cpus into
groups of 16 cpus,you would have 8 groups.see which is the busiest,so
that would be 8 iterations,then you would know the busiest group,then
descend down.another 16 iterations.so worst case

8+16 = 24 iterations.And this decrease is only with one level of sched
domain. Imagine if you had more levels,you would make the number of
iterations even lower.


So in short the scheduler domains and groups are a 'divide and conquer
;but conquer as much as possible what is more useful' solution to
scheduling related stuff :)


Thank you

Regards
Preeti U Murthy