kernel/sched/loadavg.c

1 // SPDX-License-Identifier: GPL-2.0
11  * Global load-average calculations
13  * We take a distributed and async approach to calculating the global load-avg
16  * The global load average is an exponentially decaying average of nr_running +
23  *	nr_active += cpu_of(cpu)->nr_running + cpu_of(cpu)->nr_uninterruptible;
25  *   avenrun[n] = avenrun[0] * exp_n + nr_active * (1 - exp_n)
29  *  - for_each_possible_cpu() is prohibitively expensive on machines with
33  *        \Sum_i x_i(t) = \Sum_i x_i(t) - x_i(t_0) | x_i(t_0) := 0
34  *                      = \Sum_i { \Sum_j=1 x_i(t_j) - x_i(t_j-1) }
36  *    So assuming nr_active := 0 when we start out -- true per definition, we
37  *    can simply take per-CPU deltas and fold those into a global accumulate
40  *    Furthermore, in order to avoid synchronizing all per-CPU delta folding
44  *    This places an upper-bound on the IRQ-off latency of the machine. Then
45  *    again, being late doesn't loose the delta, just wrecks the sample.
47  *  - cpu_rq()->nr_uninterruptible isn't accurately tracked per-CPU because
48  *    this would add another cross-CPU cache-line miss and atomic operation
54  *  This covers the NO_HZ=n code, for extra head-aches, see the comment below.
64  * get_avenrun - get the load average array
82 	nr_active = this_rq->nr_running - adjust;  in calc_load_fold_active()
83 	nr_active += (int)this_rq->nr_uninterruptible;  in calc_load_fold_active()
85 	if (nr_active != this_rq->calc_load_active) {  in calc_load_fold_active()
86 		delta = nr_active - this_rq->calc_load_active;  in calc_load_fold_active()
87 		this_rq->calc_load_active = nr_active;  in calc_load_fold_active()
94  * fixed_power_int - compute: x^n, in O(log n) time
96  * @x:         base of the power
98  * @n:         power to raise @x to.
100  * By exploiting the relation between the definition of the natural power
117 				result += 1UL << (frac_bits - 1);  in fixed_power_int()
124 			x += 1UL << (frac_bits - 1);  in fixed_power_int()
133  * a1 = a0 * e + a * (1 - e)
135  * a2 = a1 * e + a * (1 - e)
136  *    = (a0 * e + a * (1 - e)) * e + a * (1 - e)
137  *    = a0 * e^2 + a * (1 - e) * (1 + e)
139  * a3 = a2 * e + a * (1 - e)
140  *    = (a0 * e^2 + a * (1 - e) * (1 + e)) * e + a * (1 - e)
141  *    = a0 * e^3 + a * (1 - e) * (1 + e + e^2)
145  * an = a0 * e^n + a * (1 - e) * (1 + e + ... + e^n-1) [1]
146  *    = a0 * e^n + a * (1 - e) * (1 - e^n)/(1 - e)
147  *    = a0 * e^n + a * (1 - e^n)
151  *              n         1 - x^(n+1)
152  *     S_n := \Sum x^i = -------------
153  *             i=0          1 - x
164  * Handle NO_HZ for the global load-average.
167  * load-average relies on per-CPU sampling from the tick, it is affected by
170  * The basic idea is to fold the nr_active delta into a global NO_HZ-delta upon
176  *  - When we go NO_HZ idle during the window, we can negate our sample
177  *    contribution, causing under-accounting.
179  *    We avoid this by keeping two NO_HZ-delta counters and flipping them
186  *        |-|-----------|-|-----------|-|-----------|-|
193  *  - When we wake up from NO_HZ during the window, we push up our
194  *    contribution, since we effectively move our sample point to a known
198  *    sample, for this CPU (effectively using the NO_HZ-delta for this CPU which
220 	 * next NO_HZ-delta.  in calc_load_write_idx()
268 	 * If we're still before the pending sample window, we're done.  in calc_load_nohz_stop()
270 	this_rq->calc_load_update = READ_ONCE(calc_load_update);  in calc_load_nohz_stop()
271 	if (time_before(jiffies, this_rq->calc_load_update))  in calc_load_nohz_stop()
275 	 * We woke inside or after the sample window, this means we're already  in calc_load_nohz_stop()
279 	if (time_before(jiffies, this_rq->calc_load_update + 10))  in calc_load_nohz_stop()
280 		this_rq->calc_load_update += LOAD_FREQ;  in calc_load_nohz_stop()
295  * NO_HZ can leave us missing all per-CPU ticks calling
311 		 * Catch-up, fold however many we are behind still  in calc_global_nohz()
313 		delta = jiffies - sample_window - 10;  in calc_global_nohz()
344  * calc_load - update the avenrun load estimates 10 ticks after the
359 	 * Fold the 'old' NO_HZ-delta to include all NO_HZ CPUs.  in calc_global_load()
389 	if (time_before(jiffies, this_rq->calc_load_update))  in calc_global_load_tick()
396 	this_rq->calc_load_update += LOAD_FREQ;  in calc_global_load_tick()