blob: b7ee379b651bea7d962fcb51789b40689bb0e112 [file] [log] [blame]
Borislav Petkove2495b52011-03-27 17:57:13 +02001Each CPU has a "base" scheduling domain (struct sched_domain). The domain
Linus Torvalds1da177e2005-04-16 15:20:36 -07002hierarchy is built from these base domains via the ->parent pointer. ->parent
Borislav Petkove2495b52011-03-27 17:57:13 +02003MUST be NULL terminated, and domain structures should be per-CPU as they are
4locklessly updated.
Linus Torvalds1da177e2005-04-16 15:20:36 -07005
6Each scheduling domain spans a number of CPUs (stored in the ->span field).
7A domain's span MUST be a superset of it child's span (this restriction could
8be relaxed if the need arises), and a base domain for CPU i MUST span at least
9i. The top domain for each CPU will generally span all CPUs in the system
10although strictly it doesn't have to, but this could lead to a case where some
11CPUs will never be given tasks to run unless the CPUs allowed mask is
12explicitly set. A sched domain's span means "balance process load among these
13CPUs".
14
15Each scheduling domain must have one or more CPU groups (struct sched_group)
16which are organised as a circular one way linked list from the ->groups
17pointer. The union of cpumasks of these groups MUST be the same as the
18domain's span. The intersection of cpumasks from any two of these groups
19MUST be the empty set. The group pointed to by the ->groups pointer MUST
20contain the CPU to which the domain belongs. Groups may be shared among
21CPUs as they contain read only data after they have been set up.
22
23Balancing within a sched domain occurs between groups. That is, each group
24is treated as one entity. The load of a group is defined as the sum of the
25load of each of its member CPUs, and only when the load of a group becomes
26out of balance are tasks moved between groups.
27
Borislav Petkove2495b52011-03-27 17:57:13 +020028In kernel/sched.c, trigger_load_balance() is run periodically on each CPU
29through scheduler_tick(). It raises a softirq after the next regularly scheduled
30rebalancing event for the current runqueue has arrived. The actual load
31balancing workhorse, run_rebalance_domains()->rebalance_domains(), is then run
32in softirq context (SCHED_SOFTIRQ).
33
34The latter function takes two arguments: the current CPU and whether it was idle
35at the time the scheduler_tick() happened and iterates over all sched domains
36our CPU is on, starting from its base domain and going up the ->parent chain.
37While doing that, it checks to see if the current domain has exhausted its
38rebalance interval. If so, it runs load_balance() on that domain. It then checks
39the parent sched_domain (if it exists), and the parent of the parent and so
40forth.
41
42Initially, load_balance() finds the busiest group in the current sched domain.
43If it succeeds, it looks for the busiest runqueue of all the CPUs' runqueues in
44that group. If it manages to find such a runqueue, it locks both our initial
45CPU's runqueue and the newly found busiest one and starts moving tasks from it
46to our runqueue. The exact number of tasks amounts to an imbalance previously
47computed while iterating over this sched domain's groups.
Linus Torvalds1da177e2005-04-16 15:20:36 -070048
49*** Implementing sched domains ***
50The "base" domain will "span" the first level of the hierarchy. In the case
51of SMT, you'll span all siblings of the physical CPU, with each group being
52a single virtual CPU.
53
54In SMP, the parent of the base domain will span all physical CPUs in the
55node. Each group being a single physical CPU. Then with NUMA, the parent
56of the SMP domain will span the entire machine, with each group having the
57cpumask of a node. Or, you could do multi-level NUMA or Opteron, for example,
58might have just one domain covering its one NUMA level.
59
60The implementor should read comments in include/linux/sched.h:
61struct sched_domain fields, SD_FLAG_*, SD_*_INIT to get an idea of
62the specifics and what to tune.
63
64For SMT, the architecture must define CONFIG_SCHED_SMT and provide a
65cpumask_t cpu_sibling_map[NR_CPUS], where cpu_sibling_map[i] is the mask of
66all "i"'s siblings as well as "i" itself.
67
68Architectures may retain the regular override the default SD_*_INIT flags
69while using the generic domain builder in kernel/sched.c if they wish to
70retain the traditional SMT->SMP->NUMA topology (or some subset of that). This
71can be done by #define'ing ARCH_HASH_SCHED_TUNE.
72
73Alternatively, the architecture may completely override the generic domain
74builder by #define'ing ARCH_HASH_SCHED_DOMAIN, and exporting your
75arch_init_sched_domains function. This function will attach domains to all
76CPUs using cpu_attach_domain.
77
Gautham R Shenoye29c98d2008-05-29 12:36:18 +053078The sched-domains debugging infrastructure can be enabled by enabling
79CONFIG_SCHED_DEBUG. This enables an error checking parse of the sched domains
Linus Torvalds1da177e2005-04-16 15:20:36 -070080which should catch most possible errors (described above). It also prints out
81the domain structure in a visual format.