Re: why are scheduling domains used in multiprocessor systems
On Thu, Jan 10, 2013 at 9:00 AM, Preeti U Murthy pre...@linux.vnet.ibm.com wrote: d1'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. Thanks Peter and preeti, I had seen that intel link and had read but was not very clear with it, with both explanations and new links I am clear. ___ Kernelnewbies mailing list Kernelnewbies@kernelnewbies.org http://lists.kernelnewbies.org/mailman/listinfo/kernelnewbies
Re: why are scheduling domains used in multiprocessor systems
On Thu, Jan 10, 2013 at 6:09 PM, Bond jamesbond.2...@gmail.com wrote: On Thu, Jan 10, 2013 at 9:00 AM, Preeti U Murthy pre...@linux.vnet.ibm.com wrote: d1'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. Thanks Peter and preeti, I had seen that intel link and had read but was not very clear with it, with both explanations and new links I am clear. Sorry, I am still learning all these. On top of scheduling domain, there is also cpusets, and both are intertwined (for eg, look into sched_fair.c), and cpu inside cpuset can be offline/online, or made allow/disallowed to be used. I know not the difference between cpusets and sched_domain - conceptually. Any guidance? -- Regards, Peter Teoh ___ Kernelnewbies mailing list Kernelnewbies@kernelnewbies.org http://lists.kernelnewbies.org/mailman/listinfo/kernelnewbies
Re: why are scheduling domains used in multiprocessor systems
On Wed, Jan 9, 2013 at 4:03 PM, Bond jamesbond.2...@gmail.com wrote: Hi, please see this question http://stackoverflow.com/questions/14229793/what-does-struct-sched-domain-stands-for-in-include-linux-sched-h-scheduling-do I checked following http://lwn.net/Articles/169277/ and following http://www.kernel.org/doc/Documentation/scheduler/sched-domains.txt the first line of kernel.org doc says . Each CPU has a base scheduling domain (struct sched_domain).. and second para says each scheduling domain spans a number of CPUs (stored in the -span field). third para says Each scheduling domain must have one or more CPU groups.. The intersection of cpumasks from any two of these groups MUST be the empty set. then some where in doc it says Balancing within a sched domain occurs between groups. That is, each group is treated as one entity. the doc in details talks about the implementation of scheduling domains and mentions that CPUs should belong to one of the scheduling domain in a way that cpumasks intersection should be an empty set The answer of the question that I want to know is why is a scheduling domain actually needed? _ CPU scheduling involving many configuration and factors. https://www.cs.unm.edu/~eschulte/classes/cs587/data/10.1.1.59.6385.pdf Goto page 18 for definition of scheduler domain, and it says: Each node in a system has a scheduler domain that points to its parent scheduler domain. A node might be a uniprocessor system, an SMP system, or a node within a NUMA system. this complex hierarchies of CPU is normally associated with hardware physical proximity CPU (just one factors) or the speed of bus that connect between CPU. Not all CPU are connected to all other CPU, but perhaps only two or 4 other CPU, and therefore, when u transfer data between CPU, it is necessary to build these proximities information into the kernel, to minimize costs of data transfer between CPU. 90% (or more) of supercomputers (with thousands of CPU) are run by Linux kernel, and clearly each CPU can only have a few neighboring CPU. Other factors involved power-management: when your processing usage goes down, u have to shut down the CPU - leaving only the bare minimum to be running. Organizing in some hierarchies facilitate this scheduling algorithm. http://www.intel.com/technology/itj/2007/v11i4/9-process/6-linux-scheduler.htm http://www.cs.stonybrook.edu/~porter/courses/cse506/f12/slides/scheduling.pdf http://www.cs.stonybrook.edu/~porter/courses/cse506/f12/slides/scheduling2.pdf -- Regards, Peter Teoh ___ Kernelnewbies mailing list Kernelnewbies@kernelnewbies.org http://lists.kernelnewbies.org/mailman/listinfo/kernelnewbies
Re: why are scheduling domains used in multiprocessor systems
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 cachel2 cache - -- cpu0 cpu1 cpu2 cpu3 \___/ \/ sd0 sd0 sd1_ /\ -- l3 cache -- - -- l2 cachel2 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 ___ Kernelnewbies mailing list Kernelnewbies@kernelnewbies.org http://lists.kernelnewbies.org/mailman/listinfo/kernelnewbies
