1 ================= 1 =================
2 Scheduler Domains 2 Scheduler Domains
3 ================= 3 =================
4 4
5 Each CPU has a "base" scheduling domain (struc 5 Each CPU has a "base" scheduling domain (struct sched_domain). The domain
6 hierarchy is built from these base domains via 6 hierarchy is built from these base domains via the ->parent pointer. ->parent
7 MUST be NULL terminated, and domain structures 7 MUST be NULL terminated, and domain structures should be per-CPU as they are
8 locklessly updated. 8 locklessly updated.
9 9
10 Each scheduling domain spans a number of CPUs 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 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 dom 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 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 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 t 15 CPUs will never be given tasks to run unless the CPUs allowed mask is
16 explicitly set. A sched domain's span means "b 16 explicitly set. A sched domain's span means "balance process load among these
17 CPUs". 17 CPUs".
18 18
19 Each scheduling domain must have one or more C 19 Each scheduling domain must have one or more CPU groups (struct sched_group)
20 which are organised as a circular one way link 20 which are organised as a circular one way linked list from the ->groups
21 pointer. The union of cpumasks of these 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 ->g !! 22 domain's span. The intersection of cpumasks from any two of these groups
23 to which the domain belongs. Groups may be sha !! 23 MUST be the empty set. The group pointed to by the ->groups pointer MUST
24 read only data after they have been set up. Th !! 24 contain the CPU to which the domain belongs. Groups may be shared among
25 any two of these groups may be non empty. If t !! 25 CPUs as they contain read only data after they have been set up.
26 flag is set on the corresponding scheduling do <<
27 shared between CPUs. <<
28 26
29 Balancing within a sched domain occurs between 27 Balancing within a sched domain occurs between groups. That is, each group
30 is treated as one entity. The load of a group 28 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 29 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. 30 out of balance are tasks moved between groups.
33 31
34 In kernel/sched/core.c, sched_balance_trigger( !! 32 In kernel/sched/core.c, trigger_load_balance() is run periodically on each CPU
35 through sched_tick(). It raises a softirq afte !! 33 through scheduler_tick(). It raises a softirq after the next regularly scheduled
36 rebalancing event for the current runqueue has 34 rebalancing event for the current runqueue has arrived. The actual load
37 balancing workhorse, sched_balance_softirq()-> !! 35 balancing workhorse, run_rebalance_domains()->rebalance_domains(), is then run
38 in softirq context (SCHED_SOFTIRQ). 36 in softirq context (SCHED_SOFTIRQ).
39 37
40 The latter function takes two arguments: the r !! 38 The latter function takes two arguments: the current CPU and whether it was idle
41 the CPU was idle at the time the sched_tick() !! 39 at the time the scheduler_tick() happened and iterates over all sched domains
42 sched domains our CPU is on, starting from its !! 40 our CPU is on, starting from its base domain and going up the ->parent chain.
43 chain. While doing that, it checks to see if t !! 41 While doing that, it checks to see if the current domain has exhausted its
44 rebalance interval. If so, it runs sched_balan !! 42 rebalance interval. If so, it runs load_balance() on that domain. It then checks
45 the parent sched_domain (if it exists), and th 43 the parent sched_domain (if it exists), and the parent of the parent and so
46 forth. 44 forth.
47 45
48 Initially, sched_balance_rq() finds the busies !! 46 Initially, load_balance() finds the busiest group in the current sched domain.
49 If it succeeds, it looks for the busiest runqu 47 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 runqu 48 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 49 CPU's runqueue and the newly found busiest one and starts moving tasks from it
52 to our runqueue. The exact number of tasks amo 50 to our runqueue. The exact number of tasks amounts to an imbalance previously
53 computed while iterating over this sched domai 51 computed while iterating over this sched domain's groups.
54 52
55 Implementing sched domains 53 Implementing sched domains
56 ========================== 54 ==========================
57 55
58 The "base" domain will "span" the first level 56 The "base" domain will "span" the first level of the hierarchy. In the case
59 of SMT, you'll span all siblings of the physic 57 of SMT, you'll span all siblings of the physical CPU, with each group being
60 a single virtual CPU. 58 a single virtual CPU.
61 59
62 In SMP, the parent of the base domain will spa 60 In SMP, the parent of the base domain will span all physical CPUs in the
63 node. Each group being a single physical CPU. 61 node. Each group being a single physical CPU. Then with NUMA, the parent
64 of the SMP domain will span the entire machine 62 of the SMP domain will span the entire machine, with each group having the
65 cpumask of a node. Or, you could do multi-leve 63 cpumask of a node. Or, you could do multi-level NUMA or Opteron, for example,
66 might have just one domain covering its one NU 64 might have just one domain covering its one NUMA level.
67 65
68 The implementor should read comments in includ !! 66 The implementor should read comments in include/linux/sched.h:
69 SD_* to get an idea of the specifics and what !! 67 struct sched_domain fields, SD_FLAG_*, SD_*_INIT to get an idea of
70 of a sched_domain. !! 68 the specifics and what to tune.
71 !! 69
72 Architectures may override the generic domain !! 70 Architectures may retain the regular override the default SD_*_INIT flags
73 for a given topology level by creating a sched !! 71 while using the generic domain builder in kernel/sched/core.c if they wish to
74 calling set_sched_topology() with this array a !! 72 retain the traditional SMT->SMP->NUMA topology (or some subset of that). This
>> 73 can be done by #define'ing ARCH_HASH_SCHED_TUNE.
>> 74
>> 75 Alternatively, the architecture may completely override the generic domain
>> 76 builder by #define'ing ARCH_HASH_SCHED_DOMAIN, and exporting your
>> 77 arch_init_sched_domains function. This function will attach domains to all
>> 78 CPUs using cpu_attach_domain.
75 79
76 The sched-domains debugging infrastructure can 80 The sched-domains debugging infrastructure can be enabled by enabling
77 CONFIG_SCHED_DEBUG and adding 'sched_verbose' !! 81 CONFIG_SCHED_DEBUG. This enables an error checking parse of the sched domains
78 forgot to tweak your cmdline, you can also fli !! 82 which should catch most possible errors (described above). It also prints out
79 /sys/kernel/debug/sched/verbose knob. This ena !! 83 the domain structure in a visual format.
80 the sched domains which should catch most poss <<
81 also prints out the domain structure in a visu <<
Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.