1 ================= 2 Scheduler Domains 3 ================= 4 5 Each CPU has a "base" scheduling domain (struct sched_domain). The domain 6 hierarchy is built from these base domains via the ->parent pointer. ->parent 7 MUST be NULL terminated, and domain structures should be per-CPU as they are 8 locklessly updated. 9 10 Each scheduling domain spans a number of CPUs (stored in the ->span field). 11 A domain's span MUST be a superset of it child's span (this restriction could 12 be relaxed if the need arises), and a base domain for CPU i MUST span at least 13 i. The top domain for each CPU will generally span all CPUs in the system 14 although strictly it doesn't have to, but this could lead to a case where some 15 CPUs will never be given tasks to run unless the CPUs allowed mask is 16 explicitly set. A sched domain's span means "balance process load among these 17 CPUs". 18 19 Each scheduling domain must have one or more CPU groups (struct sched_group) 20 which are organised as a circular one way linked list from the ->groups 21 pointer. The union of cpumasks of these groups MUST be the same as the 22 domain's span. The group pointed to by the ->groups pointer MUST contain the CPU 23 to which the domain belongs. Groups may be shared among CPUs as they contain 24 read only data after they have been set up. The intersection of cpumasks from 25 any two of these groups may be non empty. If this is the case the SD_OVERLAP 26 flag is set on the corresponding scheduling domain and its groups may not be 27 shared between CPUs. 28 29 Balancing within a sched domain occurs between groups. That is, each group 30 is treated as one entity. The load of a group is defined as the sum of the 31 load of each of its member CPUs, and only when the load of a group becomes 32 out of balance are tasks moved between groups. 33 34 In kernel/sched/core.c, sched_balance_trigger() is run periodically on each CPU 35 through sched_tick(). It raises a softirq after the next regularly scheduled 36 rebalancing event for the current runqueue has arrived. The actual load 37 balancing workhorse, sched_balance_softirq()->sched_balance_domains(), is then run 38 in softirq context (SCHED_SOFTIRQ). 39 40 The latter function takes two arguments: the runqueue of current CPU and whether 41 the CPU was idle at the time the sched_tick() happened and iterates over all 42 sched domains our CPU is on, starting from its base domain and going up the ->parent 43 chain. While doing that, it checks to see if the current domain has exhausted its 44 rebalance interval. If so, it runs sched_balance_rq() on that domain. It then checks 45 the parent sched_domain (if it exists), and the parent of the parent and so 46 forth. 47 48 Initially, sched_balance_rq() finds the busiest group in the current sched domain. 49 If it succeeds, it looks for the busiest runqueue of all the CPUs' runqueues in 50 that group. If it manages to find such a runqueue, it locks both our initial 51 CPU's runqueue and the newly found busiest one and starts moving tasks from it 52 to our runqueue. The exact number of tasks amounts to an imbalance previously 53 computed while iterating over this sched domain's groups. 54 55 Implementing sched domains 56 ========================== 57 58 The "base" domain will "span" the first level of the hierarchy. In the case 59 of SMT, you'll span all siblings of the physical CPU, with each group being 60 a single virtual CPU. 61 62 In SMP, the parent of the base domain will span all physical CPUs in the 63 node. Each group being a single physical CPU. Then with NUMA, the parent 64 of the SMP domain will span the entire machine, with each group having the 65 cpumask of a node. Or, you could do multi-level NUMA or Opteron, for example, 66 might have just one domain covering its one NUMA level. 67 68 The implementor should read comments in include/linux/sched/sd_flags.h: 69 SD_* to get an idea of the specifics and what to tune for the SD flags 70 of a sched_domain. 71 72 Architectures may override the generic domain builder and the default SD flags 73 for a given topology level by creating a sched_domain_topology_level array and 74 calling set_sched_topology() with this array as the parameter. 75 76 The sched-domains debugging infrastructure can be enabled by enabling 77 CONFIG_SCHED_DEBUG and adding 'sched_verbose' to your cmdline. If you 78 forgot to tweak your cmdline, you can also flip the 79 /sys/kernel/debug/sched/verbose knob. This enables an error checking parse of 80 the sched domains which should catch most possible errors (described above). It 81 also prints out the domain structure in a visual format.
Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.