[src/netbsd-8]: src/sys/kern Pull up following revision(s) (requested by maxv...

[martin <martin%NetBSD.org@localhost>]

details:   https://anonhg.NetBSD.org/src/rev/abf605ef7dae
branches:  netbsd-8
changeset: 850884:abf605ef7dae
user:      martin <martin%NetBSD.org@localhost>
date:      Wed Jul 26 07:29:34 2017 +0000

description:
Pull up following revision(s) (requested by maxv in ticket #158):
        sys/kern/sched_4bsd.c: revision 1.31-1.33

explain a bit
-
Revert rev1.26. l_estcpu is increased by only one cpu, not all of them.
-
Should be loadfactor().

diffstat:

 sys/kern/sched_4bsd.c |  148 ++++++++++++++++++++++++++++---------------------
 1 files changed, 83 insertions(+), 65 deletions(-)

diffs (259 lines):

diff -r 15ee1b0b7ea1 -r abf605ef7dae sys/kern/sched_4bsd.c
--- a/sys/kern/sched_4bsd.c     Tue Jul 25 02:23:33 2017 +0000
+++ b/sys/kern/sched_4bsd.c     Wed Jul 26 07:29:34 2017 +0000
@@ -1,6 +1,6 @@
-/*     $NetBSD: sched_4bsd.c,v 1.30 2014/06/24 10:08:45 maxv Exp $     */
+/*     $NetBSD: sched_4bsd.c,v 1.30.20.1 2017/07/26 07:29:34 martin Exp $      */
 
-/*-
+/*
  * Copyright (c) 1999, 2000, 2004, 2006, 2007, 2008 The NetBSD Foundation, Inc.
  * All rights reserved.
  *
@@ -31,7 +31,7 @@
  * POSSIBILITY OF SUCH DAMAGE.
  */
 
-/*-
+/*
  * Copyright (c) 1982, 1986, 1990, 1991, 1993
  *     The Regents of the University of California.  All rights reserved.
  * (c) UNIX System Laboratories, Inc.
@@ -68,7 +68,7 @@
  */
 
 #include <sys/cdefs.h>
-__KERNEL_RCSID(0, "$NetBSD: sched_4bsd.c,v 1.30 2014/06/24 10:08:45 maxv Exp $");
+__KERNEL_RCSID(0, "$NetBSD: sched_4bsd.c,v 1.30.20.1 2017/07/26 07:29:34 martin Exp $");
 
 #include "opt_ddb.h"
 #include "opt_lockdebug.h"
@@ -80,13 +80,10 @@
 #include <sys/cpu.h>
 #include <sys/proc.h>
 #include <sys/kernel.h>
-#include <sys/signalvar.h>
 #include <sys/resourcevar.h>
 #include <sys/sched.h>
 #include <sys/sysctl.h>
-#include <sys/kauth.h>
 #include <sys/lockdebug.h>
-#include <sys/kmem.h>
 #include <sys/intr.h>
 
 static void updatepri(struct lwp *);
@@ -95,7 +92,7 @@
 extern unsigned int sched_pstats_ticks; /* defined in kern_synch.c */
 
 /* Number of hardclock ticks per sched_tick() */
-static int rrticks;
+static int rrticks __read_mostly;
 
 /*
  * Force switch among equal priority processes every 100ms.
@@ -133,7 +130,7 @@
                if (spc->spc_flags & SPCF_SHOULDYIELD) {
                        /*
                         * Process is stuck in kernel somewhere, probably
-                        * due to buggy or inefficient code.  Force a 
+                        * due to buggy or inefficient code.  Force a
                         * kernel preemption.
                         */
                        cpu_need_resched(ci, RESCHED_KPREEMPT);
@@ -170,71 +167,90 @@
 #define        ESTCPULIM(e)    min((e), ESTCPU_MAX)
 
 /*
- * Constants for digital decay and forget:
- *     90% of (l_estcpu) usage in 5 * loadav time
- *     95% of (l_pctcpu) usage in 60 seconds (load insensitive)
- *          Note that, as ps(1) mentions, this can let percentages
- *          total over 100% (I've seen 137.9% for 3 processes).
+ * The main parameter used by this algorithm is 'l_estcpu'. It is an estimate
+ * of the recent CPU utilization of the thread.
+ *
+ * l_estcpu is:
+ *  - increased each time the hardclock ticks and the thread is found to
+ *    be executing, in sched_schedclock() called from hardclock()
+ *  - decreased (filtered) on each sched tick, in sched_pstats_hook()
+ * If the lwp is sleeping for more than a second, we don't touch l_estcpu: it
+ * will be updated in sched_setrunnable() when the lwp wakes up, in burst mode
+ * (ie, we decrease it n times).
  *
  * Note that hardclock updates l_estcpu and l_cpticks independently.
  *
- * We wish to decay away 90% of l_estcpu in (5 * loadavg) seconds.
- * That is, the system wants to compute a value of decay such
- * that the following for loop:
- *     for (i = 0; i < (5 * loadavg); i++)
- *             l_estcpu *= decay;
- * will compute
- *     l_estcpu *= 0.1;
- * for all values of loadavg:
+ * -----------------------------------------------------------------------------
+ *
+ * Here we describe how l_estcpu is decreased.
+ *
+ * Constants for digital decay (filter):
+ *     90% of l_estcpu usage in (5 * loadavg) seconds
+ *
+ * We wish to decay away 90% of l_estcpu in (5 * loadavg) seconds. That is, we
+ * want to compute a value of decay such that the following loop:
+ *     for (i = 0; i < (5 * loadavg); i++)
+ *         l_estcpu *= decay;
+ * will result in
+ *     l_estcpu *= 0.1;
+ * for all values of loadavg.
  *
  * Mathematically this loop can be expressed by saying:
- *     decay ** (5 * loadavg) ~= .1
+ *     decay ** (5 * loadavg) ~= .1
+ *
+ * And finally, the corresponding value of decay we're using is:
+ *     decay = (2 * loadavg) / (2 * loadavg + 1)
  *
- * The system computes decay as:
- *     decay = (2 * loadavg) / (2 * loadavg + 1)
+ * -----------------------------------------------------------------------------
  *
- * We wish to prove that the system's computation of decay
- * will always fulfill the equation:
- *     decay ** (5 * loadavg) ~= .1
+ * Now, let's prove that the value of decay stated above will always fulfill
+ * the equation:
+ *     decay ** (5 * loadavg) ~= .1
  *
  * If we compute b as:
- *     b = 2 * loadavg
+ *     b = 2 * loadavg
  * then
- *     decay = b / (b + 1)
+ *     decay = b / (b + 1)
  *
  * We now need to prove two things:
- *     1) Given factor ** (5 * loadavg) ~= .1, prove factor == b/(b+1)
- *     2) Given b/(b+1) ** power ~= .1, prove power == (5 * loadavg)
+ *     1) Given [factor ** (5 * loadavg) =~ .1], prove [factor == b/(b+1)].
+ *     2) Given [b/(b+1) ** power =~ .1], prove [power == (5 * loadavg)].
  *
  * Facts:
- *         For x close to zero, exp(x) =~ 1 + x, since
- *              exp(x) = 0! + x**1/1! + x**2/2! + ... .
- *              therefore exp(-1/b) =~ 1 - (1/b) = (b-1)/b.
- *         For x close to zero, ln(1+x) =~ x, since
- *              ln(1+x) = x - x**2/2 + x**3/3 - ...     -1 < x < 1
- *              therefore ln(b/(b+1)) = ln(1 - 1/(b+1)) =~ -1/(b+1).
- *         ln(.1) =~ -2.30
+ *   * For x real: exp(x) = 0! + x**1/1! + x**2/2! + ...
+ *     Therefore, for x close to zero, exp(x) =~ 1 + x.
+ *     In turn, for b large enough, exp(-1/b) =~ 1 - (1/b) = (b-1)/b.
+ *
+ *   * For b large enough, (b-1)/b =~ b/(b+1).
+ *
+ *   * For x belonging to [-1;1[, ln(1-x) = - x - x**2/2 - x**3/3 - ...
+ *     Therefore ln(b/(b+1)) = ln(1 - 1/(b+1)) =~ -1/(b+1).
+ *
+ *   * ln(0.1) =~ -2.30
  *
  * Proof of (1):
- *    Solve (factor)**(power) =~ .1 given power (5*loadav):
- *     solving for factor,
- *      ln(factor) =~ (-2.30/5*loadav), or
- *      factor =~ exp(-1/((5/2.30)*loadav)) =~ exp(-1/(2*loadav)) =
- *          exp(-1/b) =~ (b-1)/b =~ b/(b+1).                    QED
+ *     factor ** (5 * loadavg) =~ 0.1
+ *  => ln(factor) =~ -2.30 / (5 * loadavg)
+ *  => factor =~ exp(-1 / ((5 / 2.30) * loadavg))
+ *            =~ exp(-1 / (2 * loadavg))
+ *            =~ exp(-1 / b)
+ *            =~ (b - 1) / b
+ *            =~ b / (b + 1)
+ *            =~ (2 * loadavg) / ((2 * loadavg) + 1)
  *
  * Proof of (2):
- *    Solve (factor)**(power) =~ .1 given factor == (b/(b+1)):
- *     solving for power,
- *      power*ln(b/(b+1)) =~ -2.30, or
- *      power =~ 2.3 * (b + 1) = 4.6*loadav + 2.3 =~ 5*loadav.  QED
+ *     (b / (b + 1)) ** power =~ .1
+ *  => power * ln(b / (b + 1)) =~ -2.30
+ *  => power * (-1 / (b + 1)) =~ -2.30
+ *  => power =~ 2.30 * (b + 1)
+ *  => power =~ 4.60 * loadavg + 2.30
+ *  => power =~ 5 * loadavg
  *
- * Actual power values for the implemented algorithm are as follows:
- *      loadav: 1       2       3       4
- *      power:  5.68    10.32   14.94   19.55
+ * Conclusion: decay = (2 * loadavg) / (2 * loadavg + 1)
  */
 
-/* calculations for digital decay to forget 90% of usage in 5*loadav sec */
-#define        loadfactor(loadav)      (2 * (loadav) / ncpu)
+/* See calculations above */
+#define        loadfactor(loadavg)  (2 * (loadavg))
 
 static fixpt_t
 decay_cpu(fixpt_t loadfac, fixpt_t estcpu)
@@ -250,22 +266,24 @@
        if (__predict_true(loadfac <= FIXPT_MAX / ESTCPU_MAX)) {
                return estcpu * loadfac / (loadfac + FSCALE);
        }
-#endif /* !defined(_LP64) */
+#endif
 
        return (uint64_t)estcpu * loadfac / (loadfac + FSCALE);
 }
 
-/*
- * For all load averages >= 1 and max l_estcpu of (255 << ESTCPU_SHIFT),
- * sleeping for at least seven times the loadfactor will decay l_estcpu to
- * less than (1 << ESTCPU_SHIFT).
- *
- * note that our ESTCPU_MAX is actually much smaller than (255 << ESTCPU_SHIFT).
- */
 static fixpt_t
 decay_cpu_batch(fixpt_t loadfac, fixpt_t estcpu, unsigned int n)
 {
 
+       /*
+        * For all load averages >= 1 and max l_estcpu of (255 << ESTCPU_SHIFT),
+        * if we slept for at least seven times the loadfactor, we will decay
+        * l_estcpu to less than (1 << ESTCPU_SHIFT), and therefore we can
+        * return zero directly.
+        *
+        * Note that our ESTCPU_MAX is actually much smaller than
+        * (255 << ESTCPU_SHIFT).
+        */
        if ((n << FSHIFT) >= 7 * loadfac) {
                return 0;
        }
@@ -299,13 +317,14 @@
                        return;
                }
        }
-       loadfac = 2 * (averunnable.ldavg[0]);
+
+       loadfac = loadfactor(averunnable.ldavg[0]);
        l->l_estcpu = decay_cpu(loadfac, l->l_estcpu);
        resetpriority(l);
 }
 
 /*
- * Recalculate the priority of a process after it has slept for a while.
+ * Recalculate the priority of an LWP after it has slept for a while.
  */
 static void
 updatepri(struct lwp *l)
@@ -383,10 +402,9 @@
  * is running (linearly), and decays away exponentially, at a rate which is
  * proportionally slower when the system is busy.  The basic principle is
  * that the system will 90% forget that the process used a lot of CPU time
- * in 5 * loadav seconds.  This causes the system to favor processes which
+ * in (5 * loadavg) seconds.  This causes the system to favor processes which
  * haven't run much recently, and to round-robin among other processes.
  */
-
 void
 sched_schedclock(struct lwp *l)
 {