4 1.1 Heterogeneous Systems
5 1.2 CPU Frequency Guidance
6 2. Window-Based Load Tracking Scheme
7 2.1 Synchronized Windows
9 2.3 Scaling Load Statistics
10 2.4 sched_window_stats_policy
12 2.6 update_task_ravg()
14 2.8 Per-task 'initial task load'
20 5.1 Classification of Tasks and CPUs
24 5.2.3 Tunables affecting select_best_cpu()
31 6.1 Per-CPU Window-Based Stats
32 6.2 Per-task Window-Based Stats
33 6.3 Effect of various task events
34 6.4 Tying it all together
36 8. HMP Scheduler Trace Points
37 8.1 sched_enq_deq_task
40 8.4 sched_update_task_ravg
41 8.5 sched_update_history
42 8.6 sched_reset_all_windows_stats
43 8.7 sched_migration_update_sum
47 9. Device Tree bindings
53 Scheduler extensions described in this document serves two goals:
55 1) handle heterogeneous multi-processor (HMP) systems
56 2) guide cpufreq governor on proactive changes to cpu frequency
58 *** 1.1 Heterogeneous systems
60 Heterogeneous systems have cpus that differ with regard to their performance and
61 power characteristics. Some cpus could offer peak performance better than
62 others, although at cost of consuming more power. We shall refer such cpus as
63 "high performance" or "performance efficient" cpus. Other cpus that offer lesser
64 peak performance are referred to as "power efficient".
66 In this situation the scheduler is tasked with the responsibility of assigning
67 tasks to run on the right cpus where their performance requirements can be met
68 at the least expense of power.
70 Achieving that goal is made complicated by the fact that the scheduler has
71 little clue about performance requirements of tasks and how they may change by
72 running on power or performance efficient cpus! One simplifying assumption here
73 could be that a task's desire for more performance is expressed by its cpu
74 utilization. A task demanding high cpu utilization on a power-efficient cpu
75 would likely improve in its performance by running on a performance-efficient
76 cpu. This idea forms the basis for HMP-related scheduler extensions.
78 Key inputs required by the HMP scheduler for its task placement decisions are:
80 a) task load - this reflects cpu utilization or demand of tasks
81 b) CPU capacity - this reflects peak performance offered by cpus
82 c) CPU power - this reflects power or energy cost of cpus
84 Once all 3 pieces of information are available, the HMP scheduler can place
85 tasks on the lowest power cpus where their demand can be satisfied.
87 *** 1.2 CPU Frequency guidance
89 A somewhat separate but related goal of the scheduler extensions described here
90 is to provide guidance to the cpufreq governor on the need to change cpu
91 frequency. Most governors that control cpu frequency work on a reactive basis.
92 CPU utilization is sampled at regular intervals, based on which the need to
93 change frequency is determined. Higher utilization leads to a frequency increase
94 and vice-versa. There are several problems with this approach that scheduler
99 Reactive nature introduces latency for cpus to ramp up to desired speed
100 which can hurt application performance. This is inevitable as cpufreq
101 governors can only track cpu utilization as a whole and not tasks which
102 are driving that demand. Scheduler can however keep track of individual
103 task demand and can alert the governor on changing task activity. For
104 example, request raise in frequency when tasks activity is increasing on
105 a cpu because of wakeup or migration or request frequency to be lowered
106 when task activity is decreasing because of sleep/exit or migration.
110 Most governors track utilization of each CPU independently. When a task
111 migrates from one cpu to another the task's execution time is split
112 across the two cpus. The governor can fail to see the full picture of
113 task demand in this case and thus the need for increasing frequency,
114 affecting the task's performance. Scheduler can keep track of task
115 migrations, fix up busy time upon migration and report per-cpu busy time
116 to the governor that reflects task demand accurately.
118 The rest of this document explains key enhancements made to the scheduler to
119 accomplish both of the aforementioned goals.
121 ====================================
122 2. WINDOW-BASED LOAD TRACKING SCHEME
123 ====================================
125 As mentioned in the introduction section, knowledge of the CPU demand exerted by
126 a task is a prerequisite to knowing where to best place the task in an HMP
127 system. The per-entity load tracking (PELT) scheme, present in Linux kernel
128 since v3.7, has some perceived shortcomings when used to place tasks on HMP
129 systems or provide recommendations on CPU frequency.
131 Per-entity load tracking does not make a distinction between the ramp up
132 vs ramp down time of task load. It also decays task load without exception when
133 a task sleeps. As an example, a cpu bound task at its peak load (LOAD_AVG_MAX or
134 47742) can see its load decay to 0 after a sleep of just 213ms! A cpu-bound task
135 running on a performance-efficient cpu could thus get re-classified as not
136 requiring such a cpu after a short sleep. In the case of mobile workloads, tasks
137 could go to sleep due to a lack of user input. When they wakeup it is very
138 likely their cpu utilization pattern repeats. Resetting their load across sleep
139 and incurring latency to reclassify them as requiring a high performance cpu can
140 hurt application performance.
142 The window-based load tracking scheme described in this document avoids these
143 drawbacks. It keeps track of N windows of execution for every task. Windows
144 where a task had no activity are ignored and not recorded. N can be tuned at
145 compile time (RAVG_HIST_SIZE defined in include/linux/sched.h) or at runtime
146 (/proc/sys/kernel/sched_ravg_hist_size). The window size, W, is common for all
147 tasks and currently defaults to 10ms ('sched_ravg_window' defined in
148 kernel/sched/core.c). The window size can be tuned at boot time via the
149 sched_ravg_window=W argument to kernel. Alternately it can be tuned after boot
150 via tunables provided by the interactive governor. More on this later.
152 Based on the N samples available per-task, a per-task "demand" attribute is
153 calculated which represents the cpu demand of that task. The demand attribute is
154 used to classify tasks as to whether or not they need a performance-efficient
155 CPU and also serves to provide inputs on frequency to the cpufreq governor. More
156 on this later. The 'sched_window_stats_policy' tunable (defined in
157 kernel/sched/core.c) controls how the demand field for a task is derived from
160 *** 2.1 Synchronized windows
162 Windows of observation for task activity are synchronized across cpus. This
163 greatly aids in the scheduler's frequency guidance feature. Scheduler currently
164 relies on a synchronized clock (sched_clock()) for this feature to work. It may
165 be possible to extend this feature to work on systems having an unsynchronized
177 The 'window_start' attribute represents the time when current window began on a
178 cpu. It is updated when key task events such as wakeup or context-switch call
179 update_task_ravg() to record task activity. The window_start value is expected
180 to be the same for all cpus, although it could be behind on some cpus where it
181 has not yet been updated because update_task_ravg() has not been recently
182 called. For example, when a cpu is idle for a long time its window_start could
183 be stale. The window_start value for such cpus is rolled forward upon
184 occurrence of a task event resulting in a call to update_task_ravg().
188 The ravg struct contains information tracked per-task.
193 u32 sum_history[RAVG_HIST_SIZE];
205 sum_history[] - stores cpu utilization samples from N previous windows
206 where task had activity
208 sum - stores cpu utilization of the task in its most recently
209 tracked window. Once the corresponding window terminates,
210 'sum' will be pushed into the sum_history[] array and is then
211 reset to 0. It is possible that the window corresponding to
212 sum is not the current window being tracked on a cpu. For
213 example, a task could go to sleep in window X and wakeup in
214 window Y (Y > X). In this case, sum would correspond to the
215 task's activity seen in window X. When update_task_ravg() is
216 called during the task's wakeup event it will be seen that
217 window X has elapsed. The sum value will be pushed to
218 'sum_history[]' array before being reset to 0.
220 demand - represents task's cpu demand and is derived from the
221 elements in sum_history[]. The section on
222 'sched_window_stats_policy' provides more details on how
223 'demand' is derived from elements in sum_history[] array
225 mark_start - records timestamp of the beginning of the most recent task
226 event. See section on 'Task events' for possible events that
229 curr_window - this is described in the section on 'Frequency guidance'
231 prev_window - this is described in the section on 'Frequency guidance'
234 *** 2.3 Scaling load statistics
236 Time required for a task to complete its work (and hence its load) depends on,
237 among various other factors, cpu frequency and its efficiency. In a HMP system,
238 some cpus are more performance efficient than others. Performance efficiency of
239 a cpu can be described by its "instructions-per-cycle" (IPC) attribute. History
240 of task execution could involve task having run at different frequencies and on
241 cpus with different IPC attributes. To avoid ambiguity of how task load relates
242 to the frequency and IPC of cpus on which a task has run, task load is captured
243 in a scaled form, with scaling being done in reference to an "ideal" cpu that
244 has best possible IPC and frequency. Such an "ideal" cpu, having the best
245 possible frequency and IPC, may or may not exist in system.
247 As an example, consider a HMP system, with two types of cpus, A53 and A57. A53
248 has IPC count of 1024 and can run at maximum frequency of 1 GHz, while A57 has
249 IPC count of 2048 and can run at maximum frequency of 2 GHz. Ideal cpu in this
250 case is A57 running at 2 GHz.
252 A unit of work that takes 100ms to finish on A53 running at 100MHz would get
253 done in 10ms on A53 running at 1GHz, in 5 ms running on A57 at 1 GHz and 2.5ms
254 on A57 running at 2 GHz. Thus a load of 100ms can be expressed as 2.5ms in
255 reference to ideal cpu of A57 running at 2 GHz.
257 In order to understand how much load a task will consume on a given cpu, its
258 scaled load needs to be multiplied by a factor (load scale factor). In above
259 example, scaled load of 2.5ms needs to be multiplied by a factor of 4 in order
260 to estimate the load of task on A53 running at 1 GHz.
262 /proc/sched_debug provides IPC attribute and load scale factor for every cpu.
264 In summary, task load information stored in a task's sum_history[] array is
265 scaled for both frequency and efficiency. If a task runs for X ms, then the
266 value stored in its 'sum' field is derived as:
268 X_s = X * (f_cur / max_possible_freq) *
269 (efficiency / max_possible_efficiency)
273 X = cpu utilization that needs to be accounted
274 X_s = Scaled derivative of X
275 f_cur = current frequency of the cpu where the task was
277 max_possible_freq = maximum possible frequency (across all cpus)
278 efficiency = instructions per cycle (IPC) of cpu where task was
280 max_possible_efficiency = maximum IPC offered by any cpu in system
283 *** 2.4 sched_window_stats_policy
285 sched_window_stats_policy controls how the 'demand' attribute for a task is
286 derived from elements in its 'sum_history[]' array.
288 WINDOW_STATS_RECENT (0)
294 WINDOW_STATS_MAX_RECENT_AVG (2)
295 demand = maximum(average, recent)
301 M = history size specified by
302 /proc/sys/kernel/sched_ravg_hist_size
303 average = average of first M samples found in the sum_history[] array
304 max = maximum value of first M samples found in the sum_history[]
306 recent = most recent sample (sum_history[0])
307 demand = demand attribute found in 'struct ravg'
309 This policy can be changed at runtime via
310 /proc/sys/kernel/sched_window_stats_policy. For example, the command
311 below would select WINDOW_STATS_USE_MAX policy
313 echo 1 > /proc/sys/kernel/sched_window_stats_policy
317 A number of events results in the window-based stats of a task being
320 PICK_NEXT_TASK - the task is about to start running on a cpu
321 PUT_PREV_TASK - the task stopped running on a cpu
322 TASK_WAKE - the task is waking from sleep
323 TASK_MIGRATE - the task is migrating from one cpu to another
324 TASK_UPDATE - this event is invoked on a currently running task to
325 update the task's window-stats and also the cpu's
326 window-stats such as 'window_start'
327 IRQ_UPDATE - event to record the busy time spent by an idle cpu
328 processing interrupts
330 *** 2.6 update_task_ravg()
332 update_task_ravg() is called to mark the beginning of an event for a task or a
333 cpu. It serves to accomplish these functions:
335 a. Update a cpu's window_start value
336 b. Update a task's window-stats (sum, sum_history[], demand and mark_start)
338 In addition update_task_ravg() updates the busy time information for the given
339 cpu, which is used for frequency guidance. This is described further in section
342 *** 2.7 update_history()
344 update_history() is called on a task to record its activity in an elapsed
345 window. 'sum', which represents task's cpu demand in its elapsed window is
346 pushed onto sum_history[] array and its 'demand' attribute is updated based on
347 the sched_window_stats_policy in effect.
349 *** 2.8 Initial task load attribute for a task (init_load_pct)
351 In some cases, it may be desirable for children of a task to be assigned a
352 "high" load so that they can start running on best capacity cluster. By default,
353 newly created tasks are assigned a load defined by tunable sched_init_task_load
354 (Sec 7.8). Some specialized tasks may need a higher value than the global
355 default for their child tasks. This will let child tasks run on cpus with best
356 capacity. This is accomplished by setting the 'initial task load' attribute
357 (init_load_pct) for a task. Child tasks starting load (ravg.demand and
358 ravg.sum_history[]) is initialized from their parent's 'initial task load'
359 attribute. Note that child task's 'initial task load' attribute itself will be 0
360 by default (i.e it is not inherited from parent).
362 A task's 'initial task load' attribute can be set in two ways:
366 /proc/[pid]/sched_init_task_load can be written to for setting a task's 'initial
367 task load' attribute. A numeric value between 0 - 100 (in percent scale) is
368 accepted for task's 'initial task load' attribute.
370 Reading /proc/[pid]/sched_init_task_load returns the 'initial task load'
371 attribute for the given task.
375 Following kernel APIs are provided to set or retrieve a given task's 'initial
376 task load' attribute:
378 int sched_set_init_task_load(struct task_struct *p, int init_load_pct);
379 int sched_get_init_task_load(struct task_struct *p);
386 CPU capacity reflects peak performance offered by a cpu. It is defined both by
387 maximum frequency at which cpu can run and its efficiency attribute. Capacity of
388 a cpu is defined in reference to "least" performing cpu such that "least"
389 performing cpu has capacity of 1024.
391 capacity = 1024 * (fmax_cur * / min_max_freq) *
392 (efficiency / min_possible_efficiency)
396 fmax_cur = maximum frequency at which cpu is currently
398 efficiency = IPC of cpu
399 min_max_freq = max frequency at which "least" performing cpu
401 min_possible_efficiency = IPC of "least" performing cpu
403 'fmax_cur' reflects the fact that a cpu may be constrained at runtime to run at
404 a maximum frequency less than what is supported. This may be a constraint placed
405 by user or drivers such as thermal that intends to reduce temperature of a cpu
406 by restricting its maximum frequency.
408 'max_possible_capacity' reflects the maximum capacity of a cpu based on the
409 maximum frequency it supports.
411 max_possible_capacity = 1024 * (fmax * / min_max_freq) *
412 (efficiency / min_possible_efficiency)
415 fmax = maximum frequency supported by a cpu
417 /proc/sched_debug lists capacity and maximum_capacity information for a cpu.
419 In the example HMP system quoted in Sec 2.3, "least" performing CPU is A53 and
420 thus min_max_freq = 1GHz and min_possible_efficiency = 1024.
422 Capacity of A57 = 1024 * (2GHz / 1GHz) * (2048 / 1024) = 4096
423 Capacity of A53 = 1024 * (1GHz / 1GHz) * (1024 / 1024) = 1024
425 Capacity of A57 when constrained to run at maximum frequency of 500MHz can be
428 Capacity of A57 = 1024 * (500MHz / 1GHz) * (2048 / 1024) = 1024
430 *** 3.1 load_scale_factor
432 'lsf' or load scale factor attribute of a cpu is used to estimate load of a task
433 on that cpu when running at its fmax_cur frequency. 'lsf' is defined in
434 reference to "best" performing cpu such that it's lsf is 1024. 'lsf' for a cpu
437 lsf = 1024 * (max_possible_freq / fmax_cur) *
438 (max_possible_efficiency / ipc)
441 fmax_cur = maximum frequency at which cpu is currently
444 max_possible_freq = max frequency at which "best" performing cpu
446 max_possible_efficiency = IPC of "best" performing cpu
448 In the example HMP system quoted in Sec 2.3, "best" performing CPU is A57 and
449 thus max_possible_freq = 2 GHz, max_possible_efficiency = 2048
451 lsf of A57 = 1024 * (2GHz / 2GHz) * (2048 / 2048) = 1024
452 lsf of A53 = 1024 * (2GHz / 1 GHz) * (2048 / 1024) = 4096
454 lsf of A57 constrained to run at maximum frequency of 500MHz can be calculated
457 lsf of A57 = 1024 * (2GHz / 500Mhz) * (2048 / 2048) = 4096
459 To estimate load of a task on a given cpu running at its fmax_cur:
461 load = scaled_load * lsf / 1024
463 A task with scaled load of 20% would thus be estimated to consume 80% bandwidth
464 of A53 running at 1GHz. The same task with scaled load of 20% would be estimated
465 to consume 160% bandwidth on A53 constrained to run at maximum frequency of
468 load_scale_factor, thus, is very useful to estimate load of a task on a given
469 cpu and thus to decide whether it can fit in a cpu or not.
473 A metric 'cpu_power' related to 'capacity' is also listed in /proc/sched_debug.
474 'cpu_power' is ideally same for all cpus (1024) when they are idle and running
475 at the same frequency. 'cpu_power' of a cpu can be scaled down from its ideal
476 value to reflect reduced frequency it is operating at and also to reflect the
477 amount of cpu bandwidth consumed by real-time tasks executing on it.
478 'cpu_power' metric is used by scheduler to decide task load distribution among
479 cpus. CPUs with low 'cpu_power' will be assigned less task load compared to cpus
480 with higher 'cpu_power'
486 The HMP scheduler extensions currently depend on an architecture-specific driver
487 to provide runtime information on cpu power. In the absence of an
488 architecture-specific driver, the scheduler will resort to using the
489 max_possible_capacity metric of a cpu as a measure of its power.
495 For normal (SCHED_OTHER/fair class) tasks there are three paths in the
496 scheduler which these HMP extensions affect. The task wakeup path, the
497 load balancer, and the scheduler tick are each modified.
499 Real-time and stop-class tasks are served by different code
500 paths. These will be discussed separately.
502 Prior to delving further into the algorithm and implementation however
503 some definitions are required.
505 *** 5.1 Classification of Tasks and CPUs
507 With the extensions described thus far, the following information is
508 available to the HMP scheduler:
510 - per-task CPU demand information from either Per-Entity Load Tracking
511 (PELT) or the window-based algorithm described above
513 - a power value for each frequency supported by each CPU via the API
514 described in section 4
516 - current CPU frequency, maximum CPU frequency (may be throttled by at
517 runtime due to thermal conditions), maximum possible CPU frequency supported
520 - data previously maintained within the scheduler such as the number
521 of currently runnable tasks on each CPU
523 Combined with tunable parameters, this information can be used to classify
524 both tasks and CPUs to aid in the placement of tasks.
528 A big task is one that exerts a CPU demand too high for a particular
529 CPU to satisfy. The scheduler will attempt to find a CPU with more
530 capacity for such a task.
532 The definition of "big" is specific to a task *and* a CPU. A task
533 may be considered big on one CPU in the system and not big on
534 another if the first CPU has less capacity than the second.
536 What task demand is "too high" for a particular CPU? One obvious
537 answer would be a task demand which, as measured by PELT or
538 window-based load tracking, matches or exceeds the capacity of that
539 CPU. A task which runs on a CPU for a long time, for example, might
540 meet this criteria as it would report 100% demand of that CPU. It
541 may be desirable however to classify tasks which use less than 100%
542 of a particular CPU as big so that the task has some "headroom" to grow
543 without its CPU bandwidth getting capped and its performance requirements
544 not being met. This task demand is therefore a tunable parameter:
546 /proc/sys/kernel/sched_upmigrate
548 This value is a percentage. If a task consumes more than this much of a
549 particular CPU, that CPU will be considered too small for the task. The task
550 will thus be seen as a "big" task on the cpu and will reflect in nr_big_tasks
551 statistics maintained for that cpu. Note that certain tasks (whose nice
552 value exceeds SCHED_UPMIGRATE_MIN_NICE value or those that belong to a cgroup
553 whose upmigrate_discourage flag is set) will never be classified as big tasks
554 despite their high demand.
556 As the load scale factor is calculated against current fmax, it gets boosted
557 when a lower capacity CPU is restricted to run at lower fmax. The task
558 demand is inflated in this scenario and the task upmigrates early to the
559 maximum capacity CPU. Hence this threshold is auto-adjusted by a factor
560 equal to max_possible_frequency/current_frequency of a lower capacity CPU.
561 This adjustment happens only when the lower capacity CPU frequency is
562 restricted. The same adjustment is applied to the downmigrate threshold
565 When the frequency restriction is relaxed, the previous values are restored.
566 sched_up_down_migrate_auto_update macro defined in kernel/sched/core.c
567 controls this auto-adjustment behavior and it is enabled by default.
569 If the adjusted upmigrate threshold exceeds the window size, it is clipped to
570 the window size. If the adjusted downmigrate threshold decreases the difference
571 between the upmigrate and downmigrate, it is clipped to a value such that the
572 difference between the modified and the original thresholds is same.
576 Tasks will normally be placed on lowest power-cost cluster where they can fit.
577 This could result in power-efficient cluster becoming overcrowded when there
578 are "too" many low-demand tasks. Spill threshold provides a spill over
579 criteria, wherein low-demand task are allowed to be placed on idle or
580 busy cpus in high-performance cluster.
582 Scheduler will avoid placing a task on a cpu if it can result in cpu exceeding
583 its spill threshold, which is defined by two tunables:
585 /proc/sys/kernel/sched_spill_nr_run (default: 10)
586 /proc/sys/kernel/sched_spill_load (default : 100%)
588 A cpu is considered to be above its spill level if it already has 10 tasks or
589 if the sum of task load (scaled in reference to given cpu) and
590 rq->cumulative_runnable_avg exceeds 'sched_spill_load'.
594 The scheduler may be faced with a tradeoff between power and performance when
595 placing a task. If the scheduler sees two CPUs which can accommodate a task:
597 CPU 1, power cost of 20, load of 10
598 CPU 2, power cost of 10, load of 15
600 It is not clear what the right choice of CPU is. The HMP scheduler
601 offers the sched_powerband_limit tunable to determine how this
602 situation should be handled. When the power delta between two CPUs
603 is less than sched_powerband_limit_pct, load will be prioritized as
604 the deciding factor as to which CPU is selected. If the power delta
605 between two CPUs exceeds that, the lower power CPU is considered to
606 be in a different "band" and it is selected, despite perhaps having
607 a higher current task load.
609 *** 5.2 select_best_cpu()
611 CPU placement decisions for a task at its wakeup or creation time are the
612 most important decisions made by the HMP scheduler. This section will describe
613 the call flow and algorithm used in detail.
615 The primary entry point for a task wakeup operation is try_to_wake_up(),
616 located in kernel/sched/core.c. This function relies on select_task_rq() to
617 determine the target CPU for the waking task. For fair-class (SCHED_OTHER)
618 tasks, that request will be routed to select_task_rq_fair() in
619 kernel/sched/fair.c. As part of these scheduler extensions a hook has been
620 inserted into the top of that function. If HMP scheduling is enabled the normal
621 scheduling behavior will be replaced by a call to select_best_cpu(). This
622 function, select_best_cpu(), represents the heart of the HMP scheduling
623 algorithm described in this document. Note that select_best_cpu() is also
624 invoked for a task being created.
626 The behavior of select_best_cpu() depends on several factors such as boost
627 setting, choice of several tunables and on task demand.
631 The task placement policy changes signifincantly when scheduler boost is in
632 effect. When boost is in effect the scheduler ignores the power cost of
633 placing tasks on CPUs. Instead it figures out the load on each CPU and then
634 places task on the least loaded CPU. If the load of two or more CPUs is the
635 same (generally when CPUs are idle) the task prefers to go highest capacity
638 A further enhancement during boost is the scheduler' early detection feature.
639 While boost is in effect the scheduler checks for the precence of tasks that
640 have been runnable for over some period of time within the tick. For such
641 tasks the scheduler informs the governor of imminent need for high frequency.
642 If there exists a task on the runqueue at the tick that has been runnable
643 for greater than SCHED_EARLY_DETECTION_DURATION amount of time, it notifies
644 the governor with a fabricated load of the full window at the highest
645 frequency. The fabricated load is maintained until the task is no longer
646 runnable or until the next tick.
648 Boost can be set via either /proc/sys/kernel/sched_boost or by invoking
649 kernel API sched_set_boost().
651 int sched_set_boost(int enable);
653 Once turned on, boost will remain in effect until it is explicitly turned off.
654 To allow for boost to be controlled by multiple external entities (application
655 or kernel module) at same time, boost setting is reference counted. This means
656 that two applications can turn on boost and the effect of boost is eliminated
657 only after both applications have turned off boost. boost_refcount variable
658 represents this reference count.
660 **** 5.2.2 task_will_fit()
662 The overall goal of select_best_cpu() is to place a task on the least power
663 cluster where it can "fit" i.e where its cpu usage shall be below the capacity
664 offered by cluster. Criteria for a task to be considered as fitting in a cluster
667 i) A low-priority task, whose nice value is greater than
668 SCHED_UPMIGRATE_MIN_NICE or whose cgroup has its
669 upmigrate_discourage flag set, is considered to be fitting in all clusters,
670 irrespective of their capacity and task's cpu demand.
672 ii) All tasks are considered to fit in highest capacity cluster.
674 iii) Task demand scaled in reference to the given cluster should be less than a
675 threshold. See section on load_scale_factor to know more about how task
676 demand is scaled in reference to a given cpu (cluster). The threshold used
677 is normally sched_upmigrate. Its possible for a task's demand to exceed
678 sched_upmigrate threshold in reference to a cluster when its upmigrated to
679 higher capacity cluster. To prevent it from coming back immediately to
680 lower capacity cluster, the task is not considered to "fit" on its earlier
681 cluster until its demand has dropped below sched_downmigrate in reference
682 to that earlier cluster. sched_downmigrate thus provides for some
686 **** 5.2.3 Factors affecting select_best_cpu()
688 Behavior of select_best_cpu() is further controlled by several tunables and
689 synchronous nature of wakeup.
691 a. /proc/sys/kernel/sched_cpu_high_irqload
692 A cpu whose irq load is greater than this threshold will not be
693 considered eligible for placement. This threshold value in expressed in
694 nanoseconds scale, with default threshold being 10000000 (10ms). See
695 notes on sched_cpu_high_irqload tunable to understand how irq load on a
698 b. Synchronous nature of wakeup
699 Synchronous wakeup is a hint to scheduler that the task issuing wakeup
700 (i.e task currently running on cpu where wakeup is being processed by
701 scheduler) will "soon" relinquish CPU. A simple example is two tasks
702 communicating with each other using a pipe structure. When reader task
703 blocks waiting for data, its woken by writer task after it has written
704 data to pipe. Writer task usually blocks waiting for reader task to
705 consume data in pipe (which may not have any more room for writes).
707 Synchronous wakeup is accounted for by adjusting load of a cpu to not
708 include load of currently running task. As a result, a cpu that has only
709 one runnable task and which is currently processing synchronous wakeup
710 will be considered idle.
713 Any task with this flag set will be woken up to an idle cpu (if one is
714 available) independent of sched_prefer_idle flag setting, its demand and
715 synchronous nature of wakeup. Similarly idle cpu is preferred during
716 wakeup for any task that does not have this flag set but is being woken
717 by a task with PF_WAKE_UP_IDLE flag set. For simplicity, we will use the
718 term "PF_WAKE_UP_IDLE wakeup" to signify wakeups involving a task with
719 PF_WAKE_UP_IDLE flag set.
721 d. /proc/sys/kernel/sched_select_prev_cpu_us
722 This threshold controls whether task placement goes through fast path or
723 not. If task's wakeup time since last sleep is short there are high
724 chances that it's better to place the task on its previous CPU. This
725 reduces task placement latency, cache miss and number of migrations.
726 Default value of sched_select_prev_cpu_us is 2000 (2ms). This can be
727 turned off by setting it to 0.
729 e. /proc/sys/kernel/sched_short_burst_ns
730 This threshold controls whether a task is considered as "short-burst"
731 or not. "short-burst" tasks are eligible for packing to avoid overhead
732 associated with waking up an idle CPU. "non-idle" CPUs which are not
733 loaded with IRQs and can accommodate the waking task without exceeding
734 spill limits are considered. The ties are broken with load followed
735 by previous CPU. This tunable does not affect cluster selection.
736 It only affects CPU selection in a given cluster. This packing is
737 skipped for tasks that are eligible for "wake-up-idle" and "boost".
739 **** 5.2.4 Wakeup Logic for Task "p"
741 Wakeup task placement logic is as follows:
743 1) Eliminate CPUs with high irq load based on sched_cpu_high_irqload tunable.
745 2) Eliminate CPUs where either the task does not fit or CPUs where placement
746 will result in exceeding the spill threshold tunables. CPUs elimiated at this
747 stage will be considered as backup choices incase none of the CPUs get past
750 3) Find out and return the least power CPU that satisfies all conditions above.
752 4) If two or more CPUs are projected to have the same power, break ties in the
753 following preference order:
754 a) The CPU is the task's previous CPU.
755 b) The CPU is in the same cluster as the task's previous CPU.
756 c) The CPU has the least load
758 The placement logic described above does not apply when PF_WAKE_UP_IDLE is set
759 for either the waker task or the wakee task. Instead the scheduler chooses the
760 most power efficient idle CPU.
762 5) If no CPU is found after step 2, resort to backup CPU selection logic
763 whereby the CPU with highest amount of spare capacity is selected.
765 6) If none of the CPUs have any spare capacity, return the task's previous
768 *** 5.3 Scheduler Tick
770 Every CPU is interrupted periodically to let kernel update various statistics
771 and possibly preempt the currently running task in favor of a waiting task. This
772 periodicity, determined by CONFIG_HZ value, is set at 10ms. There are various
773 optimizations by which a CPU however can skip taking these interrupts (ticks).
774 A cpu going idle for considerable time in one such case.
776 HMP scheduler extensions brings in a change in processing of tick
777 (scheduler_tick()) that can result in task migration. In case the currently
778 running task on a cpu belongs to fair_sched class, a check is made if it needs
779 to be migrated. Possible reasons for migrating task could be:
781 a) A big task is running on a power-efficient cpu and a high-performance cpu is
782 available (idle) to service it
784 b) A task is starving on a CPU with high irq load.
786 c) A task with upmigration discouraged is running on a performance cluster.
787 See notes on 'cpu.upmigrate_discourage'.
789 In case the test for migration turns out positive (which is expected to be rare
790 event), a candidate cpu is identified for task migration. To avoid multiple task
791 migrations to the same candidate cpu(s), identification of candidate cpu is
792 serialized via global spinlock (migration_lock).
794 *** 5.4 Load Balancer
796 Load balance is a key functionality of scheduler that strives to distribute task
797 across available cpus in a "fair" manner. Most of the complexity associated with
798 this feature involves balancing fair_sched class tasks. Changes made to load
799 balance code serve these goals:
801 1. Restrict flow of tasks from power-efficient cpus to high-performance cpu.
802 Provide a spill-over threshold, defined in terms of number of tasks
803 (sched_spill_nr_run) and cpu demand (sched_spill_load), beyond which tasks
804 can spill over from power-efficient cpu to high-performance cpus.
806 2. Allow idle power-efficient cpus to pick up extra load from over-loaded
807 performance-efficient cpu
809 3. Allow idle high-performance cpu to pick up big tasks from power-efficient cpu
811 *** 5.5 Real Time Tasks
813 Minimal changes introduced in treatment of real-time tasks by HMP scheduler
814 aims at preferring scheduling of real-time tasks on cpus with low load on
815 a power efficient cluster.
817 Prior to HMP scheduler, the fast-path cpu selection for placing a real-time task
818 (at wakeup) is its previous cpu, provided the currently running task on its
819 previous cpu is not a real-time task or a real-time task with lower priority.
820 Failing this, cpu selection in slow-path involves building a list of candidate
821 cpus where the waking real-time task will be of highest priority and thus can be
822 run immediately. The first cpu from this candidate list is chosen for the waking
823 real-time task. Much of the premise for this simple approach is the assumption
824 that real-time tasks often execute for very short intervals and thus the focus
825 is to place them on a cpu where they can be run immediately.
827 HMP scheduler brings in a change which avoids fast-path and always resorts to
828 slow-path. Further cpu with lowest load in a power efficient cluster from
829 candidate list of cpus is chosen as cpu for placing waking real-time task.
833 Idle cpu is preferred for any waking task that has this flag set in its
834 'task_struct.flags' field. Further idle cpu is preferred for any task woken by
835 such tasks. PF_WAKE_UP_IDLE flag of a task is inherited by it's children. It can
836 be modified for a task in two ways:
838 > kernel-space interface
839 set_wake_up_idle() needs to be called in the context of a task
840 to set or clear its PF_WAKE_UP_IDLE flag.
842 > user-space interface
843 /proc/[pid]/sched_wake_up_idle file needs to be written to for
844 setting or clearing PF_WAKE_UP_IDLE flag for a given task
846 =====================
847 6. FREQUENCY GUIDANCE
848 =====================
850 As mentioned in the introduction section the scheduler is in a unique
851 position to assist with the determination of CPU frequency. Because
852 the scheduler now maintains an estimate of per-task CPU demand, task
853 activity can be tracked, aggregated and provided to the CPUfreq
854 governor as a replacement for simple CPU busy time.
856 Two of the most popular CPUfreq governors, interactive and ondemand,
857 utilize a window-based approach for measuring CPU busy time. This
858 works well with the window-based load tracking scheme previously
859 described. The following APIs are provided to allow the CPUfreq
860 governor to query busy time from the scheduler instead of using the
861 basic CPU busy time value derived via get_cpu_idle_time_us() and
862 get_cpu_iowait_time_us() APIs.
864 int sched_set_window(u64 window_start, unsigned int window_size)
866 This API is invoked by governor at initialization time or whenever
867 window size is changed. 'window_size' argument (in jiffy units)
868 indicates the size of window to be used. The first window of size
869 'window_size' is set to begin at jiffy 'window_start'
871 -EINVAL is returned if per-entity load tracking is in use rather
872 than window-based load tracking, otherwise a success value of 0
875 int sched_get_busy(int cpu)
877 Returns the busy time for the given CPU in the most recent
878 complete window. The value returned is microseconds of busy
879 time at fmax of given CPU.
881 The values returned by sched_get_busy() take a bit of explanation,
882 both in what they mean and also how they are derived.
884 *** 6.1 Per-CPU Window-Based Stats
886 The scheduler tracks two separate types of quantities on a per CPU basis.
887 The first type has to deal with the aggregate load on a CPU and the second
888 type deals with top-tasks on that same CPU. We will first proceed to explain
889 what is maintained as part of each type of statistics and then provide the
890 connection between these two types of statistics at the end.
892 First lets describe the HMP scheduler extensions to track the aggregate load
893 seen on each CPU. This is done using the same windows that the task demand
894 is tracked with (which is in turn set by the governor when frequency guidance
895 is in use). There are four quantities maintained for each CPU by the HMP
896 scheduler for tracking CPU load:
898 curr_runnable_sum: aggregate demand from all tasks which executed during
899 the current (not yet completed) window
901 prev_runnable_sum: aggregate demand from all tasks which executed during
902 the most recent completed window
904 nt_curr_runnable_sum: aggregate demand from all 'new' tasks which executed
905 during the current (not yet completed) window
907 nt_prev_runnable_sum: aggregate demand from all 'new' tasks which executed
908 during the most recent completed window.
910 When the scheduler is updating a task's window-based stats it also
911 updates these values. Like per-task window-based demand these
912 quantities are normalized against the max possible frequency and max
913 efficiency (instructions per cycle) in the system. If an update occurs
914 and a window rollover is observed, curr_runnable_sum is copied into
915 prev_runnable_sum before being reset to 0. The sched_get_busy() API
916 returns prev_runnable_sum, scaled to the efficiency and fmax of given
917 CPU. The same applies to nt_curr_runnable_sum and nt_prev_runnable_sum.
919 A 'new' task is defined as a task whose number of active windows since fork is
920 less than SCHED_NEW_TASK_WINDOWS. An active window is defined as a window
921 where a task was observed to be runnable.
923 Moving on the second type of statistics; top-tasks, the scheduler tracks a list
924 of top tasks per CPU. A top-task is defined as the task that runs the most in a
925 given window on that CPU. This includes task that ran on that CPU through out
926 the window or were migrated to that CPU prior to window expiration. It does not
927 include tasks that were migrated away from that CPU prior to window expiration.
929 To track top tasks, we first realize that there is no strict need to maintain
930 the task struct itself as long as we know the load exerted by the top task. We
931 also realize that to maintain top tasks on every CPU we have to track the
932 execution of every single task that runs during the window. The load associated
933 with a task needs to be migrated when the task migrates from one CPU to another.
934 When the top task migrates away, we need to locate the second top task and so
937 Given the above realizations, we use hashmaps to track top task load both
938 for the current and the previous window. This hashmap is implemented as an array
939 of fixed size. The key of the hashmap is given by
940 task_execution_time_in_a_window / array_size. The size of the array (number of
941 buckets in the hashmap) dictate the load granularity of each bucket. The value
942 stored in each bucket is a refcount of all the tasks that executed long enough
943 to be in that bucket. This approach has a few benefits. Firstly, any top task
944 stats update now take O(1) time. While task migration is also O(1), it does
945 still involve going through up to the size of the array to find the second top
946 task. We optimize this search by using bitmaps. The next set bit in the bitmap
947 gives the position of the second top task in our hashamp.
949 Secondly, and more importantly, not having to store the task struct itself
950 saves a lot of memory usage in that 1) there is no need to retrieve task structs
951 later causing cache misses and 2) we don't have to unnecessarily hold up task
952 memory for up to 2 full windows by calling get_task_struct() after a task exits.
954 Given the motivation above, here are a list of quantities tracked as part of
955 per CPU task top-tasks management
957 top_tasks[NUM_TRACKED_WINDOWS] - Hashmap of top-task load for the current and
960 BITMAP_ARRAY(top_tasks_bitmap) - Two bitmaps for the current and previous
961 windows corresponding to the top-task
964 load_subs[NUM_TRACKED_WINDOWS] - An array of load subtractions to be carried
965 out form curr/prev_runnable_sums for each CPU
966 prior to reporting load to the governor. The
967 purpose for this will be explained later in
968 the section pertaining to the TASK_MIGRATE
969 event. The type struct load_subtractions,
970 stores the value of the subtraction along
971 with the window start value for the window
972 for which the subtraction has to take place.
975 curr_table - Indication of which index of the array points to the current
978 curr_top - The top task on a CPU at any given moment in the current window
980 prev_top - The top task on a CPU in the previous window
983 *** 6.2 Per-task window-based stats
985 Corresponding to curr_runnable_sum and prev_runnable_sum, two counters are
988 curr_window_cpu - represents task's contribution to cpu busy time on
989 various CPUs in the current window
991 prev_window_cpu - represents task's contribution to cpu busy time on
992 various CPUs in the previous window
994 curr_window - represents the sum of all entries in curr_window_cpu
996 prev_window - represents the sum of all entries in prev_window_cpu
998 "cpu demand" of a task includes its execution time and can also include its
999 wait time. 'SCHED_FREQ_ACCOUNT_WAIT_TIME' controls whether task's wait
1000 time is included in its CPU load counters or not.
1002 Curr_runnable_sum counter of a cpu is derived from curr_window_cpu[cpu]
1003 counter of various tasks that ran on it in its most recent window.
1005 *** 6.3 Effect of various task events
1007 We now consider various events and how they affect above mentioned counters.
1010 This represents beginning of execution for a task. Provided the task
1011 refers to a non-idle task, a portion of task's wait time that
1012 corresponds to the current window being tracked on a cpu is added to
1013 task's curr_window_cpu and curr_window counter, provided
1014 SCHED_FREQ_ACCOUNT_WAIT_TIME is set. The same quantum is also added to
1015 cpu's curr_runnable_sum counter. The remaining portion, which
1016 corresponds to task's wait time in previous window is added to task's
1017 prev_window, prev_window_cpu and cpu's prev_runnable_sum counters.
1019 CPUs top_tasks hashmap is updated if needed with the new information.
1020 Any previous entries in the hashmap are deleted and newer entries are
1021 created. The top_tasks_bitmap reflects the updated state of the
1022 hashmap. If the top task for the current and/or previous window has
1023 changed, curr_top and prev_top are updated accordingly.
1026 This represents end of execution of a time-slice for a task, where the
1027 task could refer to a cpu's idle task also. In case the task is non-idle
1028 or (in case of task being idle with cpu having non-zero rq->nr_iowait
1029 count and sched_io_is_busy =1), a portion of task's execution time, that
1030 corresponds to current window being tracked on a cpu is added to task's
1031 curr_window_cpu and curr_window counter and also to cpu's
1032 curr_runnable_sum counter. Portion of task's execution that corresponds
1033 to the previous window is added to task's prev_window, prev_window_cpu
1034 and cpu's prev_runnable_sum counters.
1036 CPUs top_tasks hashmap is updated if needed with the new information.
1037 Any previous entries in the hashmap are deleted and newer entries are
1038 created. The top_tasks_bitmap reflects the updated state of the
1039 hashmap. If the top task for the current and/or previous window has
1040 changed, curr_top and prev_top are updated accordingly.
1043 This event is called on a cpu's currently running task and hence
1044 behaves effectively as PUT_PREV_TASK. Task continues executing after
1045 this event, until PUT_PREV_TASK event occurs on the task (during
1049 This event signifies a task waking from sleep. Since many windows
1050 could have elapsed since the task went to sleep, its
1051 curr_window_cpu/curr_window and prev_window_cpu/prev_window are
1052 updated to reflect task's demand in the most recent and its previous
1053 window that is being tracked on a cpu. Updated stats will trigger
1054 the same book-keeping for top-tasks as other events.
1057 This event signifies task migration across cpus. It is invoked on the
1058 task prior to being moved. Thus at the time of this event, the task
1059 can be considered to be in "waiting" state on src_cpu. In that way
1060 this event reflects actions taken under PICK_NEXT_TASK (i.e its
1061 wait time is added to task's curr/prev_window/_cpu counters as well
1062 as src_cpu's curr/prev_runnable_sum counters, provided
1063 SCHED_FREQ_ACCOUNT_WAIT_TIME is non-zero).
1065 After that update, we make a distinction between intra-cluster and
1066 inter-cluster migrations for further book-keeping.
1068 For intra-cluster migrations, we simply remove the entry for the task
1069 in the top_tasks hashmap from the source CPU and add the entry to the
1070 destination CPU. The top_tasks_bitmap, curr_top and prev_top are
1071 updated accordingly. We then find the second top-task top in our
1072 top_tasks hashmap for both the current and previous window and set
1073 curr_top and prev_top to their new values.
1075 For inter-cluster migrations we have a much more complicated scheme.
1076 Firstly we add to the destination CPU's curr/prev_runnable_sum
1077 the tasks curr/prev_window. Note we add the sum and not the
1078 contribution any individual CPU. This is because when a tasks migrates
1079 across clusters, we need the new cluster to ramp up to the appropriate
1080 frequency given the task's total execution summed up across all CPUs
1081 in the previous cluster.
1083 Secondly the src_cpu's curr/prev_runnable_sum are reduced by task's
1084 curr/prev_window_cpu values.
1086 Thirdly, we need to walk all the CPUs in the cluster and subtract from
1087 each CPU's curr/prev_runnable_sum the task's respective
1088 curr/prev_window_cpu values. However, subtracting load from each of
1089 the source CPUs is not trivial, as it would require all runqueue
1090 locks to be held. To get around this we introduce a deferred load
1091 subtraction mechanism whereby subtracting load from each of the source
1092 CPUs is deferred until an opportune moment. This opportune moment is
1093 when the governor comes asking the scheduler for load. At that time, all
1094 necessary runqueue locks are already held.
1096 There are a few cases to consider when doing deferred subtraction. Since
1097 we are not holding all runqueue locks other CPUs in the source cluster
1098 can be in a different window than the source CPU where the task is
1102 Other CPU in the source cluster is in the same window. No special
1106 Other CPU in the source cluster is ahead by 1 window. In this
1107 case, we will be doing redundant updates to subtraction load for the
1108 prev window. There is no way to avoid this redundant update though,
1109 without holding the rq lock.
1112 Other CPU in the source cluster is trailing by 1 window In this
1113 case, we might end up overwriting old data for that CPU. But this is not
1114 a problem as when the other CPU calls update_task_ravg() it will move to
1115 the same window. This relies on maintaining synchronized windows between
1116 CPUs, which is true today.
1118 To achieve all the above, we simple add the task's curr/prev_window_cpu
1119 contributions to the per CPU load_subtractions array. These load
1120 subtractions are subtracted from the respective CPU's
1121 curr/prev_runnable_sums before the governor queries CPU load. Once this
1122 is complete, the scheduler sets all curr/prev_window_cpu contributions
1123 of the task to 0 for all CPUs in the source cluster. The destination
1124 CPUs's curr/prev_window_cpu is updated with the tasks curr/prev_window
1127 Finally, we must deal with frequency aggregation. When frequency
1128 aggregation is in effect, there is little point in dealing with per CPU
1129 footprint since the load of all related tasks have to be reported on a
1130 single CPU. Therefore when a task enters a related group we clear out
1131 all per CPU contributions and add it to the task CPU's cpu_time struct.
1132 From that point onwards we stop managing per CPU contributions upon
1133 inter cluster migrations since that work is redundant. Finally when a
1134 task exits a related group we must walk every CPU in reset all CPU
1135 contributions. We then set the task CPU contribution to the respective
1136 curr/prev sum values and add that sum to the task CPU rq runnable sum.
1138 Top-task management is the same as in the case of intra-cluster
1142 This event signifies end of execution of an interrupt handler. This
1143 event results in update of cpu's busy time counters, curr_runnable_sum
1144 and prev_runnable_sum, provided cpu was idle. When sched_io_is_busy = 0,
1145 only the interrupt handling time is added to cpu's curr_runnable_sum and
1146 prev_runnable_sum counters. When sched_io_is_busy = 1, the event mirrors
1147 actions taken under TASK_UPDATED event i.e time since last accounting
1148 of idle task's cpu usage is added to cpu's curr_runnable_sum and
1149 prev_runnable_sum counters. No update is needed for top-tasks in this
1152 *** 6.4 Tying it all together
1154 Now the scheduler maintains two independent quantities for load reporing 1) CPU
1155 load as represented by prev_runnable_sum and 2) top-tasks. The reported load
1156 is governed by tunable sched_freq_reporting_policy. The default choice is
1157 FREQ_REPORT_MAX_CPU_LOAD_TOP_TASK. In other words:
1159 max(prev_runnable_sum, top_task load)
1161 Let's explain the rationale behind the choice. CPU load tracks the exact amount
1162 of execution observed on a CPU. This is close to the quantity that the vanilla
1163 governor used to track. It offers the advantages of no load over-reporting that
1164 our earlier load fixup mechanisms had deal with. It then also tackles the part
1165 picture problem by keeping of track of tasks that might be migrating across
1166 CPUs leaving a small footprint on each CPU. Since we maintain one top task per
1167 CPU, we can handle as many top tasks as the number of CPUs in a cluster. We
1168 might miss a few cases where the combined load of the top and non-top tasks on
1169 a CPU are more representative of the true load. However, those cases have been
1170 deemed to rare and have little impact on overall load/frequency behavior.
1177 *** 7.1 sched_spill_load
1179 Appears at: /proc/sys/kernel/sched_spill_load
1183 CPU selection criteria for fair-sched class tasks is the lowest power cpu where
1184 they can fit. When the most power-efficient cpu where a task can fit is
1185 overloaded (aggregate demand of tasks currently queued on it exceeds
1186 sched_spill_load), a task can be placed on a higher-performance cpu, even though
1187 the task strictly doesn't need one.
1189 *** 7.2 sched_spill_nr_run
1191 Appears at: /proc/sys/kernel/sched_spill_nr_run
1195 The intent of this tunable is similar to sched_spill_load, except it applies to
1196 nr_running count of a cpu. A task can spill over to a higher-performance cpu
1197 when the most power-efficient cpu where it can normally fit has more tasks than
1200 *** 7.3 sched_upmigrate
1202 Appears at: /proc/sys/kernel/sched_upmigrate
1206 This tunable is a percentage. If a task consumes more than this much
1207 of a CPU, the CPU is considered too small for the task and the
1208 scheduler will try to find a bigger CPU to place the task on.
1210 *** 7.4 sched_init_task_load
1212 Appears at: /proc/sys/kernel/sched_init_task_load
1216 This tunable is a percentage. When a task is first created it has no
1217 history, so the task load tracking mechanism cannot determine a
1218 historical load value to assign to it. This tunable specifies the
1219 initial load value for newly created tasks. Also see Sec 2.8 on per-task
1220 'initial task load' attribute.
1222 *** 7.5 sched_ravg_hist_size
1224 Appears at: /proc/sys/kernel/sched_ravg_hist_size
1228 This tunable controls the number of samples used from task's sum_history[]
1229 array for determination of its demand.
1231 *** 7.6 sched_window_stats_policy
1233 Appears at: /proc/sys/kernel/sched_window_stats_policy
1237 This tunable controls the policy in how window-based load tracking
1238 calculates an overall demand value based on the windows of CPU
1239 utilization it has collected for a task.
1241 Possible values for this tunable are:
1242 0: Just use the most recent window sample of task activity when calculating
1244 1: Use the maximum value of first M samples found in task's cpu demand
1245 history (sum_history[] array), where M = sysctl_sched_ravg_hist_size
1246 2: Use the maximum of (the most recent window sample, average of first M
1247 samples), where M = sysctl_sched_ravg_hist_size
1248 3. Use average of first M samples, where M = sysctl_sched_ravg_hist_size
1250 *** 7.7 sched_ravg_window
1252 Appears at: kernel command line argument
1254 Default value: 10000000 (10ms, units of tunable are nanoseconds)
1256 This specifies the duration of each window in window-based load
1257 tracking. By default each window is 10ms long. This quantity must
1258 currently be set at boot time on the kernel command line (or the
1259 default value of 10ms can be used).
1261 *** 7.8 RAVG_HIST_SIZE
1263 Appears at: compile time only (see RAVG_HIST_SIZE in include/linux/sched.h)
1267 This macro specifies the number of windows the window-based load
1268 tracking mechanism maintains per task. If default values are used for
1269 both this and sched_ravg_window then a total of 50ms of task history
1270 would be maintained in 5 10ms windows.
1272 *** 7.9 sched_freq_inc_notify
1274 Appears at: /proc/sys/kernel/sched_freq_inc_notify
1276 Default value: 10 * 1024 * 1024 (10 Ghz)
1278 When scheduler detects that cur_freq of a cluster is insufficient to meet
1279 demand, it sends notification to governor, provided (freq_required - cur_freq)
1280 exceeds sched_freq_inc_notify, where freq_required is the frequency calculated
1281 by scheduler to meet current task demand. Note that sched_freq_inc_notify is
1282 specified in kHz units.
1284 *** 7.10 sched_freq_dec_notify
1286 Appears at: /proc/sys/kernel/sched_freq_dec_notify
1288 Default value: 10 * 1024 * 1024 (10 Ghz)
1290 When scheduler detects that cur_freq of a cluster is far greater than what is
1291 needed to serve current task demand, it will send notification to governor.
1292 More specifically, notification is sent when (cur_freq - freq_required)
1293 exceeds sched_freq_dec_notify, where freq_required is the frequency calculated
1294 by scheduler to meet current task demand. Note that sched_freq_dec_notify is
1295 specified in kHz units.
1297 *** 7.11 sched_cpu_high_irqload
1299 Appears at: /proc/sys/kernel/sched_cpu_high_irqload
1301 Default value: 10000000 (10ms)
1303 The scheduler keeps a decaying average of the amount of irq and softirq activity
1304 seen on each CPU within a ten millisecond window. Note that this "irqload"
1305 (reported in the sched_cpu_load_* tracepoint) will be higher than the typical load
1306 in a single window since every time the window rolls over, the value is decayed
1307 by some fraction and then added to the irq/softirq time spent in the next
1310 When the irqload on a CPU exceeds the value of this tunable, the CPU is no
1311 longer eligible for placement. This will affect the task placement logic
1312 described above, causing the scheduler to try and steer tasks away from
1315 *** 7.12 cpu.upmigrate_discourage
1319 This is a cgroup attribute supported by the cpu resource controller. It normally
1320 appears at [root_cpu]/[name1]/../[name2]/cpu.upmigrate_discourage. Here
1321 "root_cpu" is the mount point for cgroup (cpu resource control) filesystem
1322 and name1, name2 etc are names of cgroups that form a hierarchy.
1324 Setting this flag to 1 discourages upmigration for all tasks of a cgroup. High
1325 demand tasks of such a cgroup will never be classified as big tasks and hence
1326 not upmigrated. Any task of the cgroup is allowed to upmigrate only under
1327 overcommitted scenario. See notes on sched_spill_nr_run and sched_spill_load for
1328 how overcommitment threshold is defined.
1330 *** 7.13 sched_static_cpu_pwr_cost
1334 Appears at /sys/devices/system/cpu/cpu<x>/sched_static_cpu_pwr_cost
1336 This is the power cost associated with bringing an idle CPU out of low power
1337 mode. It ignores the actual C-state that a CPU may be in and assumes the
1338 worst case power cost of the highest C-state. It is means of biasing task
1339 placement away from idle CPUs when necessary. It can be defined per CPU,
1340 however, a more appropriate usage to define the same value for every CPU
1341 within a cluster and possibly have differing value between clusters as
1345 *** 7.14 sched_static_cluster_pwr_cost
1349 Appears at /sys/devices/system/cpu/cpu<x>/sched_static_cluster_pwr_cost
1351 This is the power cost associated with bringing an idle cluster out of low
1352 power mode. It ignores the actual D-state that a cluster may be in and assumes
1353 the worst case power cost of the highest D-state. It is means of biasing task
1354 placement away from idle clusters when necessary.
1356 *** 7.15 sched_restrict_cluster_spill
1360 Appears at /proc/sys/kernel/sched_restrict_cluster_spill
1362 This tunable can be used to restrict tasks spilling to the higher capacity
1363 (higher power) cluster. When this tunable is enabled,
1365 - Restrict the higher capacity cluster pulling tasks from the lower capacity
1366 cluster in the load balance path. The restriction is lifted if all of the CPUS
1367 in the lower capacity cluster are above spill. The power cost is used to break
1368 the ties if the capacity of clusters are same for applying this restriction.
1370 - The current CPU selection algorithm for RT tasks looks for the least loaded
1371 CPU across all clusters. When this tunable is enabled, the RT tasks are
1372 restricted to the lowest possible power cluster.
1375 *** 7.16 sched_downmigrate
1377 Appears at: /proc/sys/kernel/sched_downmigrate
1381 This tunable is a percentage. It exists to control hysteresis. Lets say a task
1382 migrated to a high-performance cpu when it crossed 80% demand on a
1383 power-efficient cpu. We don't let it come back to a power-efficient cpu until
1384 its demand *in reference to the power-efficient cpu* drops less than 60%
1385 (sched_downmigrate).
1388 *** 7.17 sched_small_wakee_task_load
1390 Appears at: /proc/sys/kernel/sched_small_wakee_task_load
1394 This tunable is a percentage. Configure the maximum demand of small wakee task.
1395 Sync wakee tasks which have demand less than sched_small_wakee_task_load are
1396 categorized as small wakee tasks. Scheduler places small wakee tasks on the
1400 *** 7.18 sched_big_waker_task_load
1402 Appears at: /proc/sys/kernel/sched_big_waker_task_load
1406 This tunable is a percentage. Configure the minimum demand of big sync waker
1407 task. Scheduler places small wakee tasks woken up by big sync waker on the
1410 *** 7.19 sched_prefer_sync_wakee_to_waker
1412 Appears at: /proc/sys/kernel/sched_prefer_sync_wakee_to_waker
1416 The default sync wakee policy has a preference to select an idle CPU in the
1417 waker cluster compared to the waker CPU running only 1 task. By selecting
1418 an idle CPU, it eliminates the chance of waker migrating to a different CPU
1419 after the wakee preempts it. This policy is also not susceptible to the
1420 incorrect "sync" usage i.e the waker does not goto sleep after waking up
1423 However LPM exit latency associated with an idle CPU outweigh the above
1424 benefits on some targets. When this knob is turned on, the waker CPU is
1425 selected if it has only 1 runnable task.
1427 *** 7.20 sched_freq_reporting_policy
1429 Appears at: /proc/sys/kernel/sched_freq_reporting_policy
1433 This dictates what the load reporting policy to the governor should be. The
1434 default value is FREQ_REPORT_MAX_CPU_LOAD_TOP_TASK. Other values include
1435 FREQ_REPORT_CPU_LOAD which only reports CPU load to the governor and
1436 FREQ_REPORT_TOP_TASK which only reports the load of the top task on a CPU
1439 =========================
1440 8. HMP SCHEDULER TRACE POINTS
1441 =========================
1443 *** 8.1 sched_enq_deq_task
1445 Logged when a task is either enqueued or dequeued on a CPU's run queue.
1447 <idle>-0 [004] d.h4 12700.711665: sched_enq_deq_task: cpu=4 enqueue comm=powertop pid=13227 prio=120 nr_running=1 cpu_load=0 rt_nr_running=0 affine=ff demand=13364423
1449 - cpu: the CPU that the task is being enqueued on to or dequeued off of
1450 - enqueue/dequeue: whether this was an enqueue or dequeue event
1451 - comm: name of task
1453 - prio: priority of task
1454 - nr_running: number of runnable tasks on this CPU
1455 - cpu_load: current priority-weighted load on the CPU (note, this is *not*
1456 the same as CPU utilization or a metric tracked by PELT/window-based tracking)
1457 - rt_nr_running: number of real-time processes running on this CPU
1458 - affine: CPU affinity mask in hex for this task (so ff is a task eligible to
1460 - demand: window-based task demand computed based on selected policy (recent,
1461 max, or average) (ns)
1463 *** 8.2 sched_task_load
1465 Logged when selecting the best CPU to run the task (select_best_cpu()).
1467 sched_task_load: 4004 (adbd): demand=698425 boost=0 reason=0 sync=0 need_idle=0 best_cpu=0 latency=103177
1469 - demand: window-based task demand computed based on selected policy (recent,
1470 max, or average) (ns)
1471 - boost: whether boost is in effect
1472 - reason: reason we are picking a new CPU:
1473 0: no migration - selecting a CPU for a wakeup or new task wakeup
1474 1: move to big CPU (migration)
1475 2: move to little CPU (migration)
1476 3: move to low irq load CPU (migration)
1477 - sync: is the nature synchronous in nature
1478 - need_idle: is an idle CPU required for this task based on PF_WAKE_UP_IDLE
1479 - best_cpu: The CPU selected by the select_best_cpu() function for placement
1480 - latency: The execution time of the function select_best_cpu()
1482 *** 8.3 sched_cpu_load_*
1484 Logged when selecting the best CPU to run a task (select_best_cpu() for fair
1485 class tasks, find_lowest_rq_hmp() for RT tasks) and load balancing
1486 (update_sg_lb_stats()).
1488 <idle>-0 [004] d.h3 12700.711541: sched_cpu_load_*: cpu 0 idle 1 nr_run 0 nr_big 0 lsf 1119 capacity 1024 cr_avg 0 irqload 3301121 fcur 729600 fmax 1459200 power_cost 5 cstate 2 temp 38
1490 - cpu: the CPU being described
1491 - idle: boolean indicating whether the CPU is idle
1492 - nr_run: number of tasks running on CPU
1493 - nr_big: number of BIG tasks running on CPU
1494 - lsf: load scale factor - multiply normalized load by this factor to determine
1495 how much load task will exert on CPU
1496 - capacity: capacity of CPU (based on max possible frequency and efficiency)
1497 - cr_avg: cumulative runnable average, instantaneous sum of the demand (either
1498 PELT or window-based) of all the runnable task on a CPU (ns)
1499 - irqload: decaying average of irq activity on CPU (ns)
1500 - fcur: current CPU frequency (Khz)
1501 - fmax: max CPU frequency (but not maximum _possible_ frequency) (KHz)
1502 - power_cost: cost of running this CPU at the current frequency
1503 - cstate: current cstate of CPU
1504 - temp: current temperature of the CPU
1506 The power_cost value above differs in how it is calculated depending on the
1507 callsite of this tracepoint. The select_best_cpu() call to this tracepoint
1508 finds the minimum frequency required to satisfy the existing load on the CPU
1509 as well as the task being placed, and returns the power cost of that frequency.
1510 The load balance and real time task placement paths used a fixed frequency
1511 (highest frequency common to all CPUs for load balancing, minimum
1512 frequency of the CPU for real time task placement).
1514 *** 8.4 sched_update_task_ravg
1516 Logged when window-based stats are updated for a task. The update may happen
1517 for a variety of reasons, see section 2.5, "Task Events."
1519 rcu_preempt-7 [000] d..3 262857.738888: sched_update_task_ravg: wc 262857521127957 ws 262857490000000 delta 31127957 event PICK_NEXT_TASK cpu 0 cur_freq 291055 cur_pid 7 task 9309 (kworker/u16:0) ms 262857520627280 delta 500677 demand 282196 sum 156201 irqtime 0 pred_demand 267103 rq_cs 478718 rq_ps 0 cur_window 78433 (78433 0 0 0 0 0 0 0 ) prev_window 146430 (0 146430 0 0 0 0 0 0 ) nt_cs 0 nt_ps 0 active_wins 149 grp_cs 0 grp_ps 0, grp_nt_cs 0, grp_nt_ps: 0 curr_top 6 prev_top 2
1521 - wc: wallclock, output of sched_clock(), monotonically increasing time since
1522 boot (will roll over in 585 years) (ns)
1523 - ws: window start, time when the current window started (ns)
1524 - delta: time since the window started (wc - ws) (ns)
1525 - event: What event caused this trace event to occur (see section 2.5 for more
1527 - cpu: which CPU the task is running on
1528 - cur_freq: CPU's current frequency in KHz
1529 - curr_pid: PID of the current running task (current)
1530 - task: PID and name of task being updated
1531 - ms: mark start - timestamp of the beginning of a segment of task activity,
1532 either sleeping or runnable/running (ns)
1533 - delta: time since last event within the window (wc - ms) (ns)
1534 - demand: task demand computed based on selected policy (recent, max, or
1536 - sum: the task's run time during current window scaled by frequency and
1538 - irqtime: length of interrupt activity (ns). A non-zero irqtime is seen
1539 when an idle cpu handles interrupts, the time for which needs to be
1540 accounted as cpu busy time
1541 - cs: curr_runnable_sum of cpu (ns). See section 6.1 for more details of this
1543 - ps: prev_runnable_sum of cpu (ns). See section 6.1 for more details of this
1545 - cur_window: cpu demand of task in its most recently tracked window summed up
1546 across all CPUs (ns). This is followed by a list of contributions on each
1548 - prev_window: cpu demand of task in its previous window summed up across
1549 all CPUs (ns). This is followed by a list of contributions on each individual
1551 - nt_cs: curr_runnable_sum of a cpu for new tasks only (ns).
1552 - nt_ps: prev_runnable_sum of a cpu for new tasks only (ns).
1553 - active_wins: No. of active windows since task statistics were initialized
1554 - grp_cs: curr_runnable_sum for colocated tasks. This is independent from
1555 cs described above. The addition of these two fields give the total CPU
1556 load for the most recent window
1557 - grp_ps: prev_runnable_sum for colocated tasks. This is independent from
1558 ps described above. The addition of these two fields give the total CPU
1559 load for the previous window.
1560 - grp_nt_cs: curr_runnable_sum of a cpu for grouped new tasks only (ns).
1561 - grp_nt_ps: prev_runnable_sum for a cpu for grouped new tasks only (ns).
1562 - curr_top: index of the top task in the top_tasks array in the current
1564 - prev_top: index of the top task in the top_tasks array in the previous
1567 *** 8.5 sched_update_history
1569 Logged when update_task_ravg() is accounting task activity into one or
1570 more windows that have completed. This may occur more than once for a
1571 single call into update_task_ravg(). A task that ran for 24ms spanning
1572 four 10ms windows (the last 2ms of window 1, all of windows 2 and 3,
1573 and the first 2ms of window 4) would result in two calls into
1574 update_history() from update_task_ravg(). The first call would record activity
1575 in completed window 1 and second call would record activity for windows 2 and 3
1576 together (samples will be 2 in second call).
1578 <idle>-0 [004] d.h4 12700.711489: sched_update_history: 13227 (powertop): runtime 13364423 samples 1 event TASK_WAKE demand 13364423 (hist: 13364423 9871252 2236009 6162476 10282078) cpu 4 nr_big 0
1580 - runtime: task cpu demand in recently completed window(s). This value is scaled
1581 to max_possible_freq and max_possible_efficiency. This value is pushed into
1582 task's demand history array. The number of windows to which runtime applies is
1583 provided by samples field.
1584 - samples: Number of samples (windows), each having value of runtime, that is
1585 recorded in task's demand history array.
1586 - event: What event caused this trace event to occur (see section 2.5 for more
1587 details) - PUT_PREV_TASK, PICK_NEXT_TASK, TASK_WAKE, TASK_MIGRATE,
1589 - demand: task demand computed based on selected policy (recent, max, or
1591 - hist: last 5 windows of history for the task with the most recent window
1593 - cpu: CPU the task is associated with
1594 - nr_big: number of big tasks on the CPU
1596 *** 8.6 sched_reset_all_windows_stats
1598 Logged when key parameters controlling window-based statistics collection are
1599 changed. This event signifies that all window-based statistics for tasks and
1600 cpus are being reset. Changes to below attributes result in such a reset:
1602 * sched_ravg_window (See Sec 2)
1603 * sched_window_stats_policy (See Sec 2.4)
1604 * sched_ravg_hist_size (See Sec 7.11)
1606 <task>-0 [004] d.h4 12700.711489: sched_reset_all_windows_stats: time_taken 1123 window_start 0 window_size 0 reason POLICY_CHANGE old_val 0 new_val 1
1608 - time_taken: time taken for the reset function to complete (ns)
1609 - window_start: Beginning of first window following change to window size (ns)
1610 - window_size: Size of window. Non-zero if window-size is changing (in ticks)
1611 - reason: Reason for reset of statistics.
1612 - old_val: Old value of variable, change of which is triggering reset
1613 - new_val: New value of variable, change of which is triggering reset
1615 *** 8.7 sched_migration_update_sum
1617 Logged when a task is migrating to another cpu.
1619 <task>-0 [000] d..8 5020.404137: sched_migration_update_sum: cpu 0: cs 471278 ps 902463 nt_cs 0 nt_ps 0 pid 2645
1621 - cpu: cpu, away from which or to which, task is migrating
1622 - cs: curr_runnable_sum of cpu (ns). See Sec 6.1 for more details of this
1624 - ps: prev_runnable_sum of cpu (ns). See Sec 6.1 for more details of this
1626 - nt_cs: nt_curr_runnable_sum of cpu (ns). See Sec 6.1 for more details of
1628 - nt_ps: nt_prev_runnable_sum of cpu (ns). See Sec 6.1 for more details of
1630 - pid: PID of migrating task
1632 *** 8.8 sched_get_busy
1634 Logged when scheduler is returning busy time statistics for a cpu.
1636 <...>-4331 [003] d.s3 313.700108: sched_get_busy: cpu 3 load 19076 new_task_load 0 early 0
1639 - cpu: cpu, for which busy time statistic (prev_runnable_sum) is being
1641 - load: corresponds to prev_runnable_sum (ns), scaled to fmax of cpu
1642 - new_task_load: corresponds to nt_prev_runnable_sum to fmax of cpu
1643 - early: A flag indicating whether the scheduler is passing regular load or early detection load
1645 1 - early detection load
1647 *** 8.9 sched_freq_alert
1649 Logged when scheduler is alerting cpufreq governor about need to change
1652 <task>-0 [004] d.h4 12700.711489: sched_freq_alert: cpu 0 old_load=XXX new_load=YYY
1654 - cpu: cpu in cluster that has highest load (prev_runnable_sum)
1655 - old_load: cpu busy time last reported to governor. This is load scaled in
1656 reference to max_possible_freq and max_possible_efficiency.
1657 - new_load: recent cpu busy time. This is load scaled in
1658 reference to max_possible_freq and max_possible_efficiency.
1660 *** 8.10 sched_set_boost
1662 Logged when boost settings are being changed
1664 <task>-0 [004] d.h4 12700.711489: sched_set_boost: ref_count=1
1666 - ref_count: A non-zero value indicates boost is in effect
1668 ========================
1669 9. Device Tree bindings
1670 ========================
1672 The device tree bindings for the HMP scheduler are defined in
1673 Documentation/devicetree/bindings/sched/sched_hmp.txt