• P
    sched: Make __update_entity_runnable_avg() fast · 5b51f2f8
    Paul Turner 提交于
    __update_entity_runnable_avg forms the core of maintaining an entity's runnable
    load average.  In this function we charge the accumulated run-time since last
    update and handle appropriate decay.  In some cases, e.g. a waking task, this
    time interval may be much larger than our period unit.
    
    Fortunately we can exploit some properties of our series to perform decay for a
    blocked update in constant time and account the contribution for a running
    update in essentially-constant* time.
    
    [*]: For any running entity they should be performing updates at the tick which
    gives us a soft limit of 1 jiffy between updates, and we can compute up to a
    32 jiffy update in a single pass.
    
    C program to generate the magic constants in the arrays:
    
      #include <math.h>
      #include <stdio.h>
    
      #define N 32
      #define WMULT_SHIFT 32
    
      const long WMULT_CONST = ((1UL << N) - 1);
      double y;
    
      long runnable_avg_yN_inv[N];
      void calc_mult_inv() {
      	int i;
      	double yn = 0;
    
      	printf("inverses\n");
      	for (i = 0; i < N; i++) {
      		yn = (double)WMULT_CONST * pow(y, i);
      		runnable_avg_yN_inv[i] = yn;
      		printf("%2d: 0x%8lx\n", i, runnable_avg_yN_inv[i]);
      	}
      	printf("\n");
      }
    
      long mult_inv(long c, int n) {
      	return (c * runnable_avg_yN_inv[n]) >>  WMULT_SHIFT;
      }
    
      void calc_yn_sum(int n)
      {
      	int i;
      	double sum = 0, sum_fl = 0, diff = 0;
    
      	/*
      	 * We take the floored sum to ensure the sum of partial sums is never
      	 * larger than the actual sum.
      	 */
      	printf("sum y^n\n");
      	printf("   %8s  %8s %8s\n", "exact", "floor", "error");
      	for (i = 1; i <= n; i++) {
      		sum = (y * sum + y * 1024);
      		sum_fl = floor(y * sum_fl+ y * 1024);
      		printf("%2d: %8.0f  %8.0f %8.0f\n", i, sum, sum_fl,
      			sum_fl - sum);
      	}
      	printf("\n");
      }
    
      void calc_conv(long n) {
      	long old_n;
      	int i = -1;
    
      	printf("convergence (LOAD_AVG_MAX, LOAD_AVG_MAX_N)\n");
      	do {
      		old_n = n;
      		n = mult_inv(n, 1) + 1024;
      		i++;
      	} while (n != old_n);
      	printf("%d> %ld\n", i - 1, n);
      	printf("\n");
      }
    
      void main() {
      	y = pow(0.5, 1/(double)N);
      	calc_mult_inv();
      	calc_conv(1024);
      	calc_yn_sum(N);
      }
    
    [ Compile with -lm ]
    Signed-off-by: NPaul Turner <pjt@google.com>
    Reviewed-by: NBen Segall <bsegall@google.com>
    Signed-off-by: NPeter Zijlstra <a.p.zijlstra@chello.nl>
    Link: http://lkml.kernel.org/r/20120823141507.277808946@google.comSigned-off-by: NIngo Molnar <mingo@kernel.org>
    5b51f2f8
fair.c 147.4 KB