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 4605c2e..d6110aa 100644 (file)
--- a/usr/src/sys/kern/kern_synch.c
+++ b/usr/src/sys/kern/kern_synch.c
@@ -1,21 +1,23 @@
-/*     kern_synch.c    4.23    82/10/17        */
+/*
+ * 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/psl.h"
+#include "../machine/mtpr.h"

 
 

-#include "../h/param.h"
-#include "../h/systm.h"
-#include "../h/dir.h"
-#include "../h/user.h"
-#include "../h/proc.h"
-#include "../h/file.h"
-#include "../h/inode.h"
-#include "../h/vm.h"
-#include "../h/pte.h"
-#ifdef MUSH
-#include "../h/quota.h"
-#include "../h/share.h"
-#endif
-#include "../h/kernel.h"
-#include "../h/buf.h"
-#include "../vax/mtpr.h"       /* XXX */
+#include "param.h"
+#include "systm.h"
+#include "dir.h"
+#include "user.h"
+#include "proc.h"
+#include "vm.h"
+#include "kernel.h"
+#include "buf.h"

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


@@ -28,11 +30,71 @@ roundrobin()
        timeout(roundrobin, (caddr_t)0, hz / 10);
 }
 
        timeout(roundrobin, (caddr_t)0, hz / 10);
 }
 

-/* constants to digital decay and forget 90% of usage in 5*loadav time */
-#undef ave
-#define        ave(a,b) ((int)(((int)(a*b))/(b+1)))
-int    nrscale = 2;
-double avenrun[];
+/*
+ * 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) */
 
 /*
 double ccpu = 0.95122942450071400909;          /* exp(-1/20) */
 
 /*


@@ -40,44 +102,45 @@ double     ccpu = 0.95122942450071400909;          /* exp(-1/20) */
  */
 schedcpu()
 {
  */
 schedcpu()
 {

+       register double ccpu1 = (1.0 - ccpu) / (double)hz;

        register struct proc *p;
        register int s, a;
        register struct proc *p;
        register int s, a;

+       float scale = filter(avenrun[0]);

 
        wakeup((caddr_t)&lbolt);
 
        wakeup((caddr_t)&lbolt);

-       for (p = proc; p < procNPROC; p++) if (p->p_stat && p->p_stat!=SZOMB) {
-#ifdef MUSH
-               if (p->p_quota->q_uid)
-                       p->p_quota->q_cost +=
-                           shconsts.sc_click * p->p_rssize;
-#endif
+       for (p = allproc; p != NULL; p = p->p_nxt) {

                if (p->p_time != 127)
                        p->p_time++;
                if (p->p_stat==SSLEEP || p->p_stat==SSTOP)
                        if (p->p_slptime != 127)
                                p->p_slptime++;
                if (p->p_time != 127)
                        p->p_time++;
                if (p->p_stat==SSLEEP || p->p_stat==SSTOP)
                        if (p->p_slptime != 127)
                                p->p_slptime++;

-               if (p->p_flag&SLOAD)
-                       p->p_pctcpu = ccpu * p->p_pctcpu +
-                           (1.0 - ccpu) * (p->p_cpticks/(float)hz);
+               /*
+                * If the process has slept the entire second,
+                * stop recalculating its priority until it wakes up.
+                */
+               if (p->p_slptime > 1) {
+                       p->p_pctcpu *= ccpu;
+                       continue;
+               }
+               /*
+                * p_pctcpu is only for ps.
+                */
+               p->p_pctcpu = ccpu * p->p_pctcpu + ccpu1 * p->p_cpticks;

                p->p_cpticks = 0;
                p->p_cpticks = 0;

-#ifdef MUSH
-               a = ave((p->p_cpu & 0377), avenrun[0]*nrscale) +
-                    p->p_nice - NZERO + p->p_quota->q_nice;
-#else
-               a = ave((p->p_cpu & 0377), avenrun[0]*nrscale) +
-                    p->p_nice - NZERO;
-#endif
+               a = (int) (scale * (p->p_cpu & 0377)) + p->p_nice;

                if (a < 0)
                        a = 0;
                if (a > 255)
                        a = 255;
                p->p_cpu = a;
                (void) setpri(p);
                if (a < 0)
                        a = 0;
                if (a > 255)
                        a = 255;
                p->p_cpu = a;
                (void) setpri(p);

-               s = spl6();     /* prevent state changes */
+               s = splhigh();  /* prevent state changes */

                if (p->p_pri >= PUSER) {
                if (p->p_pri >= PUSER) {

+#define        PPQ     (128 / NQS)

                        if ((p != u.u_procp || noproc) &&
                            p->p_stat == SRUN &&
                            (p->p_flag & SLOAD) &&
                        if ((p != u.u_procp || noproc) &&
                            p->p_stat == SRUN &&
                            (p->p_flag & SLOAD) &&

-                           p->p_pri != p->p_usrpri) {
+                           (p->p_pri / PPQ) != (p->p_usrpri / PPQ)) {

                                remrq(p);
                                p->p_pri = p->p_usrpri;
                                setrq(p);
                                remrq(p);
                                p->p_pri = p->p_usrpri;
                                setrq(p);


@@ -96,9 +159,33 @@ schedcpu()
        timeout(schedcpu, (caddr_t)0, hz);
 }
 
        timeout(schedcpu, (caddr_t)0, hz);
 }
 

+/*
+ * Recalculate the priority of a process after it has slept for a while.
+ */
+updatepri(p)
+       register struct proc *p;
+{
+       register int a = p->p_cpu & 0377;
+       float scale = filter(avenrun[0]);
+
+       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)
+               a = 255;
+       p->p_cpu = a;
+       (void) setpri(p);
+}
+

 #define SQSIZE 0100    /* Must be power of 2 */
 #define HASH(x)        (( (int) x >> 5) & (SQSIZE-1))
 #define SQSIZE 0100    /* Must be power of 2 */
 #define HASH(x)        (( (int) x >> 5) & (SQSIZE-1))

-struct proc *slpque[SQSIZE];
+struct slpque {
+       struct proc *sq_head;
+       struct proc **sq_tailp;
+} slpque[SQSIZE];

 
 /*
  * Give up the processor till a wakeup occurs
 
 /*
  * Give up the processor till a wakeup occurs


@@ -115,20 +202,43 @@ sleep(chan, pri)
        caddr_t chan;
        int pri;
 {
        caddr_t chan;
        int pri;
 {

-       register struct proc *rp, **hp;
+       register struct proc *rp;
+       register struct slpque *qp;

        register s;
        register s;

+       extern int cold;

 
        rp = u.u_procp;
 
        rp = u.u_procp;

-       s = spl6();
+       s = splhigh();
+       if (cold || panicstr) {
+               /*
+                * 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.
+                */
+               (void) splnet();
+               splx(s);
+               return;
+       }

        if (chan==0 || rp->p_stat != SRUN || rp->p_rlink)
                panic("sleep");
        rp->p_wchan = chan;
        rp->p_slptime = 0;
        rp->p_pri = pri;
        if (chan==0 || rp->p_stat != SRUN || rp->p_rlink)
                panic("sleep");
        rp->p_wchan = chan;
        rp->p_slptime = 0;
        rp->p_pri = pri;

-       hp = &slpque[HASH(chan)];
-       rp->p_link = *hp;
-       *hp = rp;
+       qp = &slpque[HASH(chan)];
+       if (qp->sq_head == 0)
+               qp->sq_head = rp;
+       else
+               *qp->sq_tailp = rp;
+       *(qp->sq_tailp = &rp->p_link) = 0;

        if (pri > PZERO) {
        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);


@@ -150,6 +260,7 @@ sleep(chan, pri)
                u.u_ru.ru_nvcsw++;
                swtch();
        }
                u.u_ru.ru_nvcsw++;
                swtch();
        }

+       curpri = rp->p_usrpri;

 out:
        splx(s);
        return;
 out:
        splx(s);
        return;


@@ -158,7 +269,6 @@ out:
         * If priority was low (>PZERO) and
         * there has been a signal, execute non-local goto through
         * u.u_qsave, aborting the system call in progress (see trap.c)
         * If priority was low (>PZERO) and
         * there has been a signal, execute non-local goto through
         * u.u_qsave, aborting the system call in progress (see trap.c)

-        * (or finishing a tsleep, see below)

         */
 psig:
        longjmp(&u.u_qsave);
         */
 psig:
        longjmp(&u.u_qsave);


@@ -171,15 +281,18 @@ psig:
 unsleep(p)
        register struct proc *p;
 {
 unsleep(p)
        register struct proc *p;
 {

+       register struct slpque *qp;

        register struct proc **hp;
        register struct proc **hp;

-       register s;
+       int s;

 
 

-       s = spl6();
+       s = splhigh();

        if (p->p_wchan) {
        if (p->p_wchan) {

-               hp = &slpque[HASH(p->p_wchan)];
+               hp = &(qp = &slpque[HASH(p->p_wchan)])->sq_head;

                while (*hp != p)
                        hp = &(*hp)->p_link;
                *hp = p->p_link;
                while (*hp != p)
                        hp = &(*hp)->p_link;
                *hp = p->p_link;

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

                p->p_wchan = 0;
        }
        splx(s);
                p->p_wchan = 0;
        }
        splx(s);


@@ -191,28 +304,34 @@ unsleep(p)
 wakeup(chan)
        register caddr_t chan;
 {
 wakeup(chan)
        register caddr_t chan;
 {

-       register struct proc *p, **q, **h;
+       register struct slpque *qp;
+       register struct proc *p, **q;

        int s;
 
        int s;
 

-       s = spl6();
-       h = &slpque[HASH(chan)];
+       s = splhigh();
+       qp = &slpque[HASH(chan)];

 restart:
 restart:

-       for (q = h; p = *q; ) {
+       for (q = &qp->sq_head; p = *q; ) {

                if (p->p_rlink || p->p_stat != SSLEEP && p->p_stat != SSTOP)
                        panic("wakeup");
                if (p->p_wchan==chan) {
                        p->p_wchan = 0;
                        *q = p->p_link;
                if (p->p_rlink || p->p_stat != SSLEEP && p->p_stat != SSTOP)
                        panic("wakeup");
                if (p->p_wchan==chan) {
                        p->p_wchan = 0;
                        *q = p->p_link;

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

                        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);

-                               if (p->p_pri < curpri) {
-                                       runrun++;
-                                       aston();
-                               }
+                               /*
+                                * Since curpri is a usrpri,
+                                * p->p_pri is always better than curpri.
+                                */
+                               runrun++;
+                               aston();

                                if ((p->p_flag&SLOAD) == 0) {
                                        if (runout != 0) {
                                                runout = 0;
                                if ((p->p_flag&SLOAD) == 0) {
                                        if (runout != 0) {
                                                runout = 0;


@@ -250,7 +369,7 @@ setrun(p)
 {
        register int s;
 
 {
        register int s;
 

-       s = spl6();
+       s = splhigh();

        switch (p->p_stat) {
 
        case 0:
        switch (p->p_stat) {
 
        case 0:


@@ -272,6 +391,8 @@ setrun(p)
        if (p->p_flag & SLOAD)
                setrq(p);
        splx(s);
        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();


@@ -297,7 +418,7 @@ setpri(pp)
        register int p;
 
        p = (pp->p_cpu & 0377)/4;
        register int p;
 
        p = (pp->p_cpu & 0377)/4;

-       p += PUSER + 2*(pp->p_nice - NZERO);
+       p += PUSER + 2 * pp->p_nice;

        if (pp->p_rssize > pp->p_maxrss && freemem < desfree)
                p += 2*4;       /* effectively, nice(4) */
        if (p > 127)
        if (pp->p_rssize > pp->p_maxrss && freemem < desfree)
                p += 2*4;       /* effectively, nice(4) */
        if (p > 127)