lint, add comments on %r

[unix-history] / usr / src / sys / kern / kern_synch.c

diff --git a/usr/src/sys/kern/kern_synch.c b/usr/src/sys/kern/kern_synch.c
index 367f2fb..d6110aa 100644 (file)
--- a/usr/src/sys/kern/kern_synch.c
+++ b/usr/src/sys/kern/kern_synch.c
@@ -1,21 +1,24 @@
-/*     kern_synch.c    6.7     85/05/27        */
+/*
+ * Copyright (c) 1982, 1986 Regents of the University of California.
+ * All rights reserved.  The Berkeley software License Agreement
+ * specifies the terms and conditions for redistribution.
+ *
+ *     @(#)kern_synch.c        7.6 (Berkeley) %G%
+ */

 
 #include "../machine/pte.h"
 
 #include "../machine/pte.h"

+#include "../machine/psl.h"
+#include "../machine/mtpr.h"

 
 #include "param.h"
 #include "systm.h"
 #include "dir.h"
 #include "user.h"
 #include "proc.h"
 
 #include "param.h"
 #include "systm.h"
 #include "dir.h"
 #include "user.h"
 #include "proc.h"

-#include "file.h"
-#include "inode.h"

 #include "vm.h"
 #include "kernel.h"
 #include "buf.h"
 
 #include "vm.h"
 #include "kernel.h"
 #include "buf.h"
 

-#ifdef vax
-#include "../vax/mtpr.h"       /* XXX */
-#endif

 /*
  * Force switch among equal priority processes every 100ms.
  */
 /*
  * Force switch among equal priority processes every 100ms.
  */


@@ -27,7 +30,69 @@ roundrobin()
        timeout(roundrobin, (caddr_t)0, hz / 10);
 }
 
        timeout(roundrobin, (caddr_t)0, hz / 10);
 }
 

-/* fraction for digital decay to forget 90% of usage in 5*loadav sec */
+/*
+ * constants for digital decay and forget
+ *     90% of (p_cpu) usage in 5*loadav time
+ *     95% of (p_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).
+ *
+ * Note that hardclock updates p_cpu and p_cpticks independently.
+ *
+ * We wish to decay away 90% of p_cpu 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++)
+ *             p_cpu *= decay;
+ * will compute
+ *     p_cpu *= 0.1;
+ * for all values of loadavg:
+ *
+ * Mathematically this loop can be expressed by saying:
+ *     decay ** (5 * 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
+ *
+ * If we compute b as:
+ *     b = 2 * loadavg
+ * then
+ *     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)
+ *     
+ * 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
+ *
+ * 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
+ *
+ * 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
+ *
+ * Actual power values for the implemented algorithm are as follows:
+ *      loadav: 1       2       3       4
+ *      power:  5.68    10.32   14.94   19.55
+ */

 #define        filter(loadav) ((2 * (loadav)) / (2 * (loadav) + 1))
 
 double ccpu = 0.95122942450071400909;          /* exp(-1/20) */
 #define        filter(loadav) ((2 * (loadav)) / (2 * (loadav) + 1))
 
 double ccpu = 0.95122942450071400909;          /* exp(-1/20) */


@@ -106,6 +171,7 @@ updatepri(p)
        p->p_slptime--;         /* the first time was done in schedcpu */
        while (a && --p->p_slptime)
                a = (int) (scale * a) /* + p->p_nice */;
        p->p_slptime--;         /* the first time was done in schedcpu */
        while (a && --p->p_slptime)
                a = (int) (scale * a) /* + p->p_nice */;

+       p->p_slptime = 0;

        if (a < 0)
                a = 0;
        if (a > 255)
        if (a < 0)
                a = 0;
        if (a > 255)


@@ -139,15 +205,16 @@ sleep(chan, pri)
        register struct proc *rp;
        register struct slpque *qp;
        register s;
        register struct proc *rp;
        register struct slpque *qp;
        register s;

+       extern int cold;

 
        rp = u.u_procp;
        s = splhigh();
 
        rp = u.u_procp;
        s = splhigh();

-       if (panicstr) {
+       if (cold || panicstr) {

                /*
                /*

-                * After a panic, just give interrupts a chance,
-                * then just return; don't run any other procs 
-                * or panic below, in case this is the idle process
-                * and already asleep.
+                * After a panic, or during autoconfiguration,
+                * just give interrupts a chance, then just return;
+                * don't run any other procs or panic below,
+                * in case this is the idle process and already asleep.

                 * The splnet should be spl0 if the network was being used
                 * by the filesystem, but for now avoid network interrupts
                 * that might cause another panic.
                 * The splnet should be spl0 if the network was being used
                 * by the filesystem, but for now avoid network interrupts
                 * that might cause another panic.


@@ -168,6 +235,10 @@ sleep(chan, pri)
                *qp->sq_tailp = rp;
        *(qp->sq_tailp = &rp->p_link) = 0;
        if (pri > PZERO) {
                *qp->sq_tailp = rp;
        *(qp->sq_tailp = &rp->p_link) = 0;
        if (pri > PZERO) {

+               /*
+                * If we stop in issig(), wakeup may already have happened
+                * when we return (rp->p_wchan will then be 0).
+                */

                if (ISSIG(rp)) {
                        if (rp->p_wchan)
                                unsleep(rp);
                if (ISSIG(rp)) {
                        if (rp->p_wchan)
                                unsleep(rp);


@@ -246,13 +317,12 @@ restart:
                if (p->p_wchan==chan) {
                        p->p_wchan = 0;
                        *q = p->p_link;
                if (p->p_wchan==chan) {
                        p->p_wchan = 0;
                        *q = p->p_link;

-                       if (p->p_slptime > 1)
-                               updatepri(p);

                        if (qp->sq_tailp == &p->p_link)
                                qp->sq_tailp = q;
                        if (qp->sq_tailp == &p->p_link)
                                qp->sq_tailp = q;

-                       p->p_slptime = 0;

                        if (p->p_stat == SSLEEP) {
                                /* OPTIMIZED INLINE EXPANSION OF setrun(p) */
                        if (p->p_stat == SSLEEP) {
                                /* OPTIMIZED INLINE EXPANSION OF setrun(p) */

+                               if (p->p_slptime > 1)
+                                       updatepri(p);

                                p->p_stat = SRUN;
                                if (p->p_flag & SLOAD)
                                        setrq(p);
                                p->p_stat = SRUN;
                                if (p->p_flag & SLOAD)
                                        setrq(p);


@@ -317,12 +387,12 @@ setrun(p)
        case SIDL:
                break;
        }
        case SIDL:
                break;
        }

-       if (p->p_slptime > 1)
-               updatepri(p);

        p->p_stat = SRUN;
        if (p->p_flag & SLOAD)
                setrq(p);
        splx(s);
        p->p_stat = SRUN;
        if (p->p_flag & SLOAD)
                setrq(p);
        splx(s);

+       if (p->p_slptime > 1)
+               updatepri(p);

        if (p->p_pri < curpri) {
                runrun++;
                aston();
        if (p->p_pri < curpri) {
                runrun++;
                aston();