mahler@pur-ee.UUCP (Mahler) (08/29/84)
With a mailbox full of requests, I need to post this ...
... here is a copy of the loadav paper. Your comments about
the paper and your use of the routine would be appreciated ... tnxs ... Steve
p.s. - use the "ms" macro package
For those of you who recieved a truncated copy ... sorry ... Please place
this file in the editor and after "cutting here" edit
1,$s/^X//
good luck ... Steve
---- cut here ----
X.ps 12
X.vs 14
X.nr PS 12
X.nr VS 14
X.de ZZ
X\s-2
X..
X.de ZY
X\s+2
X..
X.ig
X$Header$
X$Log$
X..
X.DA June 1984
X.EH "'Load Average Algorithm'- % -'Load Average Algorithm'"
X.OH "'Load Average Algorithm'- % -'Load Average Algorithm'"
X.OF "'Purdue \s-1ECN\s+1'\*(DY'Simmons/Mahler/Curry'"
X.EF "'Simmons/Mahler/Curry'\*(DY'Purdue \s-1ECN\s+1'"
X.RP
X.TL
XA New Load Average Algorithm
Xfor \s-14.2 BSD\s+1
X.UX
X.AU
XWilliam R. Simmons
X.AU
XStephen J. Mahler
X.AU
XDavid A. Curry
X.AI
XEngineering Computer Network
XSchool of Electrical Engineering
XPurdue University
XWest Lafayette, Indiana 47907
X.AB
XThis paper describes briefly a direct method of computing
X\s-1VAX 4.2BSD\s+1
X.UX
XSystem load averages.
XThe load average algorithm supplied with
X\s-14.2 BSD\s+1
X.UX
Xuses an approximation algorithm to calculate its values.
XWhile the approximation is reasonable in some computing
Xenvironments,
Xits error is significant under rapidly changing load conditions.
XThe direct method presented here provides the actual load averages
Xfor the prescribed time intervals.
XSuch values allow much more definitive use and interpretation by system
Xand user programs making decisions based on system load.
X.AE
X.ig
X$Header$
X$Log$
X..
X.NH 1
XIntroduction
X.PP
XThis paper describes an implementation for directly computing load averages
Xon \s-14.2 BSD\s+1
X.UX .
XAs supplied by the University of California at Berkeley,
Xthe \s-14.2 BSD\s+1 kernel maintains three load averages in
Xdouble precision floating point form.
XThese numbers represent the load average over the past one,
Xfive,
Xand fifteen
Xminutes respectively.
XThe numbers are stored in the array
X.B avenrun ,
Xmaintained by the routines within
X.I vm_sched.c .
XBecause of the needs of the networking software,
Xthe Purdue Engineering Computer Network staff increased the
Xsize of the
X.B avenrun
Xarray to five by adding a five second load average
Xand an instantaneous count of jobs in the run queue.
XThis addition did not seriously affect the supplied algorithm,
Xit merely added another time window computation to those already being
Xperformed.
X.ig
X$Header$
X$Log$
X..
X.NH 1
XThe Standard \s-14.2 BSD\s+1 Algorithm
X.PP
XThe load average algorithm supplied with \s-14.2 BSD\s+1 uses an
Xexponential to compute the load average values.
XEach load average is calculated using the formula
X.EQ C
X{avg sub i} ~=~ {cexp sub i} ~\(mu~ {avg sub i} ~+~ n ~\(mu~ (1.0 ~-~ {cexp sub i})
X.EN
X.LP
Xwhere
X.B avg
Xis the load average,
X.B cexp
Xis an exponential constant,
Xand
X.B n
Xis the number of jobs in the run queue.
XThe exponential constants are computed as
X.EQ C
X{cexp sub i} ~=~ {e sup {-1 over {tau sub i}}}
X.EN
X.EQ C
X{tau sub i} ~=~ 12 ~\(mu~ [load~~average~~time~~in~~minutes]
X.EN
X.LP
XThe exponential constants used in the calculations have been adjusted
Xto ``forget'' 90% of their
Xvalues in five ``load average times.''
XThus,
Xthe five minute load average,
Xwith a constant input of zero,
Xwill decay to 90% of its original value in 25 minutes.
X.PP
XThe algorithm was evaluated by plotting \s-1ECN\s+1 load data collected
Xduring normal operations.
XThe results indicated that the Berkeley algorithm produced numbers which
Xdid not represent the true machine load.
XBecause of the damping property of the exponential,
Xlarge changes in the number of runnable jobs did not affect the
Xcalculated load average unless the change
Xpersisted for an extended period of time.
XInaccuracies became more significant when the number of jobs
Xin the run queue rose above ten, or when the number fluctuated over
Xa large range.
X.ig
X$Header$
X$Log$
X..
X.NH 1
XThe New Algorithm
X.PP
XAfter testing the \s-14.2 BSD\s+1 algorithm
Xand finding it suboptimal,
Xwe began to discuss the possibilities of writing a new algorithm.
XFirst the constants used in the present
Xalgorithm were changed such that the results increased and decreased more
Xrapidly.
XHowever,
Xexperimentation proved that the desired result was not yet achieved.
XSecond,
Xa true mathematical average was computed.
XThat is,
Xa history of the past
X.I n
Xload averages was stored and averaged.
X.PP
XAfter implementing the algorithm in a user-level program,
Xit was tested on the same data used previously to test the old algorithm.
XUnlike the old algorithm,
Xhowever,
Xthe new routine \fIfelt\fP even the slightest change in the number
Xof runnable jobs (well, it should have,
Xit is a true
X.I mathematical
X.I average ),
Xand the load averages changed accordingly.
XThe algorithm was declared successful.
XThe next step was to compare the two algorithms for speed and size.
XThe new algorithm,
Xalthough it took up more space (approximately 512 bytes more than
Xthe old algorithm),
Xwas no slower than the algorithm presently being used in the kernel.
X.PP
XThe final test of the algorithm was to install it in the kernel.
XAfter a brief problem introduced when ``hand optimizing'' the code,
Xthe algorithm was up and running,
Xand has been ever since.
X.NH 2
XAlgorithm Startup
X.PP
XDuring the first time period for the algorithm (immediately after the
Xmachine is booted),
Xthe algorithm assumes that the load average has consistently been zero
Xover all past time.
XFor this reason,
Xthe load average will not decay until at least one time window (in our
Xcase, the fifteen minutes for the last load average) has passed.
XWe consider this a minor annoyance,
Xbut not worth the overhead and complexity to fix.
X.EH "'The \s-14.2 BSD\s+1 Algorithm'- % -'Load Average Algorithm'"
X.OH "'Load Average Algorithm'- % -'The \s-14.2 BSD\s+1 Algorithm'"
X.bp
X.ig
X$Header$
X$Log$
X..
X.B
X.ce
XAppendix A \(em The \s-14.2 BSD\s+1 Algorithm
X.R
X.nf
X.sp .5i
X.ta 5m 10m 15m 20m 25m 30m 35m 40m 45m 50m 55m 60m
Xcexp[0] \(eq 0.36787944117144250000 /* 5 sec. e(-1/1) */
Xcexp[1] \(eq 0.92004441462932320000 /* 1 min. e(-1/12) */
Xcexp[2] \(eq 0.98347145382161740000 /* 5 min. e(-1/60) */
Xcexp[3] \(eq 0.99445984800489670000 /* 15 min. e(-1/180) */
X
X/*
X * avg is a pointer to the avenrun[] array, n is the
X * number of jobs in the run queue.
X */
X
X for (i = 0; i < 4; i++)
X avg[i] = cexp[i] * avg[i] + n * (1.0 - cexp[i]);
X avg[4] = n; /* last one is raw */
X.fi
X.EH "'The Purdue \s-1ECN\s+1 Algorithm'- % -'Load Average Algorithm'"
X.OH "'Load Average Algorithm'- % -'The Purdue \s-1ECN\s+1 Algorithm'"
X.bp
X.ig
X$Header$
X$Log$
X..
X.B
X.ce
XAppendix B \(em The Purdue \s-1ECN\s+1 Algorithm
X.R
X.nf
X.sp .5i
X.ta 5m 10m 15m 20m 25m 30m 35m 40m 45m 50m 55m 60m
X/*
X * loadav - compute load averages, Purdue EE version.
X *
X * Rather than using an exponential as the standard Berkeley kernel
X * does, this routine keeps the last LBSIZE numbers in a circular
X * buffer and uses them to compute actual averages. The lb array
X * stores the numbers, the accum array contains the sums of the
X * appropriate count of the numbers.
X *
X * The divisors array contains floating point numbers, each number
X * represents the number of 5-second intervals contained in the
X * corresponding load average time interval.
X *
X * The tails array contains pointers to the various ends of the
X * "windows" used in the sums. These should correspond to the
X * divisors array.
X *
X * The order of avenrun[] on Purdue systems is:
X *
X * avenrun[0] - 1 minute load average
X * [1] - 5 minute
X * [2] - 15 minute
X * [3] - 5 second
X * [4] - raw (no. of jobs in runq + disk wait)
X *
X * LB should be at least ([longest loadav time] / [5 seconds]) + 2
X * elements large. 5 seconds is the time interval between calls
X * to this routine.
X *
X * Arguments: avg is a pointer to the avenrun[] array, n is the number
X * of jobs in the run queue.
X *
X * This routine lives in sys/vm_sched.c
X *
X * David A. Curry / Stephen J. Mahler, 5/22/84
X */
X
X#define LB 256
X
Xloadav(avg, n)
Xregister double *avg;
Xregister int n;
X{
X register int i;
X static unsigned short lb[LB];
X static unsigned short *head = lb;
X static unsigned short *lbend = &lb[LB];
X static unsigned short accum[5] = { 0, 0, 0, 0, 0 };
X static double divisors[5] = { 12.0, 60.0, 180.0, 2.0, 1.0 };
X static unsigned short *tails[5] =
X { &lb[LB-12], &lb[LB-60], &lb[LB-180], &lb[LB-2], &lb[0] };
X
X *head = avg[4] = n;
X
X if (++head == lbend)
X head = lb;
X
X for (i=0; i < 4; i++) {
X accum[i] = accum[i] - *tails[i] + n;
X avg[i] = (double) accum[i] / divisors[i];
X
X if (++tails[i] == lbend)
X tails[i] = lb;
X }
X}jeff@voder.UUCP (Jeff Gilliam) (09/12/84)
Please be aware that if you install Purdue's modified loadav() routine
you must also change the definitions of avenrun[] in sys/vm_sched.c
(~ line 37) and h/kernel.h (~ line 24). If you do not, the results
are *heh, heh* unpredictable.
old:
double avenrun[3];
new:
double avenrun[5];
--
Jeff Gilliam {ucbvax,ihnp4!nsc}!voder!jeff