// SPDX-License-Identifier: GPL-2.0 /* * Per Entity Load Tracking (PELT) * * Copyright (C) 2007 Red Hat, Inc., Ingo Molnar <[email protected]> * * Interactivity improvements by Mike Galbraith * (C) 2007 Mike Galbraith <[email protected]> * * Various enhancements by Dmitry Adamushko. * (C) 2007 Dmitry Adamushko <[email protected]> * * Group scheduling enhancements by Srivatsa Vaddagiri * Copyright IBM Corporation, 2007 * Author: Srivatsa Vaddagiri <[email protected]> * * Scaled math optimizations by Thomas Gleixner * Copyright (C) 2007, Thomas Gleixner <[email protected]> * * Adaptive scheduling granularity, math enhancements by Peter Zijlstra * Copyright (C) 2007 Red Hat, Inc., Peter Zijlstra * * Move PELT related code from fair.c into this pelt.c file * Author: Vincent Guittot <[email protected]> */ /* * Approximate: * val * y^n, where y^32 ~= 0.5 (~1 scheduling period) */ static u64 decay_load(u64 val, u64 n) { … } static u32 __accumulate_pelt_segments(u64 periods, u32 d1, u32 d3) { … } /* * Accumulate the three separate parts of the sum; d1 the remainder * of the last (incomplete) period, d2 the span of full periods and d3 * the remainder of the (incomplete) current period. * * d1 d2 d3 * ^ ^ ^ * | | | * |<->|<----------------->|<--->| * ... |---x---|------| ... |------|-----x (now) * * p-1 * u' = (u + d1) y^p + 1024 \Sum y^n + d3 y^0 * n=1 * * = u y^p + (Step 1) * * p-1 * d1 y^p + 1024 \Sum y^n + d3 y^0 (Step 2) * n=1 */ static __always_inline u32 accumulate_sum(u64 delta, struct sched_avg *sa, unsigned long load, unsigned long runnable, int running) { … } /* * We can represent the historical contribution to runnable average as the * coefficients of a geometric series. To do this we sub-divide our runnable * history into segments of approximately 1ms (1024us); label the segment that * occurred N-ms ago p_N, with p_0 corresponding to the current period, e.g. * * [<- 1024us ->|<- 1024us ->|<- 1024us ->| ... * p0 p1 p2 * (now) (~1ms ago) (~2ms ago) * * Let u_i denote the fraction of p_i that the entity was runnable. * * We then designate the fractions u_i as our co-efficients, yielding the * following representation of historical load: * u_0 + u_1*y + u_2*y^2 + u_3*y^3 + ... * * We choose y based on the with of a reasonably scheduling period, fixing: * y^32 = 0.5 * * This means that the contribution to load ~32ms ago (u_32) will be weighted * approximately half as much as the contribution to load within the last ms * (u_0). * * When a period "rolls over" and we have new u_0`, multiplying the previous * sum again by y is sufficient to update: * load_avg = u_0` + y*(u_0 + u_1*y + u_2*y^2 + ... ) * = u_0 + u_1*y + u_2*y^2 + ... [re-labeling u_i --> u_{i+1}] */ static __always_inline int ___update_load_sum(u64 now, struct sched_avg *sa, unsigned long load, unsigned long runnable, int running) { … } /* * When syncing *_avg with *_sum, we must take into account the current * position in the PELT segment otherwise the remaining part of the segment * will be considered as idle time whereas it's not yet elapsed and this will * generate unwanted oscillation in the range [1002..1024[. * * The max value of *_sum varies with the position in the time segment and is * equals to : * * LOAD_AVG_MAX*y + sa->period_contrib * * which can be simplified into: * * LOAD_AVG_MAX - 1024 + sa->period_contrib * * because LOAD_AVG_MAX*y == LOAD_AVG_MAX-1024 * * The same care must be taken when a sched entity is added, updated or * removed from a cfs_rq and we need to update sched_avg. Scheduler entities * and the cfs rq, to which they are attached, have the same position in the * time segment because they use the same clock. This means that we can use * the period_contrib of cfs_rq when updating the sched_avg of a sched_entity * if it's more convenient. */ static __always_inline void ___update_load_avg(struct sched_avg *sa, unsigned long load) { … } /* * sched_entity: * * task: * se_weight() = se->load.weight * se_runnable() = !!on_rq * * group: [ see update_cfs_group() ] * se_weight() = tg->weight * grq->load_avg / tg->load_avg * se_runnable() = grq->h_nr_running * * runnable_sum = se_runnable() * runnable = grq->runnable_sum * runnable_avg = runnable_sum * * load_sum := runnable * load_avg = se_weight(se) * load_sum * * cfq_rq: * * runnable_sum = \Sum se->avg.runnable_sum * runnable_avg = \Sum se->avg.runnable_avg * * load_sum = \Sum se_weight(se) * se->avg.load_sum * load_avg = \Sum se->avg.load_avg */ int __update_load_avg_blocked_se(u64 now, struct sched_entity *se) { … } int __update_load_avg_se(u64 now, struct cfs_rq *cfs_rq, struct sched_entity *se) { … } int __update_load_avg_cfs_rq(u64 now, struct cfs_rq *cfs_rq) { … } /* * rt_rq: * * util_sum = \Sum se->avg.util_sum but se->avg.util_sum is not tracked * util_sum = cpu_scale * load_sum * runnable_sum = util_sum * * load_avg and runnable_avg are not supported and meaningless. * */ int update_rt_rq_load_avg(u64 now, struct rq *rq, int running) { … } /* * dl_rq: * * util_sum = \Sum se->avg.util_sum but se->avg.util_sum is not tracked * util_sum = cpu_scale * load_sum * runnable_sum = util_sum * * load_avg and runnable_avg are not supported and meaningless. * */ int update_dl_rq_load_avg(u64 now, struct rq *rq, int running) { … } #ifdef CONFIG_SCHED_HW_PRESSURE /* * hardware: * * load_sum = \Sum se->avg.load_sum but se->avg.load_sum is not tracked * * util_avg and runnable_load_avg are not supported and meaningless. * * Unlike rt/dl utilization tracking that track time spent by a cpu * running a rt/dl task through util_avg, the average HW pressure is * tracked through load_avg. This is because HW pressure signal is * time weighted "delta" capacity unlike util_avg which is binary. * "delta capacity" = actual capacity - * capped capacity a cpu due to a HW event. */ int update_hw_load_avg(u64 now, struct rq *rq, u64 capacity) { if (___update_load_sum(now, &rq->avg_hw, capacity, capacity, capacity)) { ___update_load_avg(&rq->avg_hw, 1); trace_pelt_hw_tp(rq); return 1; } return 0; } #endif #ifdef CONFIG_HAVE_SCHED_AVG_IRQ /* * IRQ: * * util_sum = \Sum se->avg.util_sum but se->avg.util_sum is not tracked * util_sum = cpu_scale * load_sum * runnable_sum = util_sum * * load_avg and runnable_avg are not supported and meaningless. * */ int update_irq_load_avg(struct rq *rq, u64 running) { … } #endif
Codebase Browser
linux