Move more scheduler-specific defines from various places into usched_bsd4.c
authorMatthew Dillon <dillon@dragonflybsd.org>
Sun, 26 Jun 2005 22:03:29 +0000 (22:03 +0000)
committerMatthew Dillon <dillon@dragonflybsd.org>
Sun, 26 Jun 2005 22:03:29 +0000 (22:03 +0000)
and revamp our scheduler algorithms.

* Get rid of the multiple layers of abstraction in the nice and frequency
  calculations.

* Increase the scheduling freqency from 20hz to 50hz.

* Greatly reduce the number of scheduling ticks that occur before a
  reschedule is issued.

* Fix a bug where the scheduler was not rescheduling when estcpu drops
  a process into a lower priority queue.

* Implement a new batch detection algorithm.  This algorithm gives
  forked children slightly more batchness then their parents (which
  is recovered quickly if the child is interactive), and propogates
  estcpu data from exiting children to future forked children (which
  handles fork/exec/wait loops such as used by make, scripts, etc).

* Change the way NICE priorities effect process execution.  The NICE
  value is used in two ways:  First, it determines the initial process
  priority.  The estcpu will have a tendancy to correct for this so the NICE
  value is also used to control estcpu's decay rate.

  This means that niced processes will have both an initial penalty for
  startup and stabilization, and an ongoing penalty if they become cpu
  bound.

Examples from cpu-bound loops:

CPU PRI  NI   PID %CPU      TIME COMMAND
 42 159 -20   706 20.5   0:38.88 /bin/csh /tmp/dowhile
 37 159 -15   704 17.6   0:35.09 /bin/csh /tmp/dowhile
 29 157 -10   702 15.3   0:30.41 /bin/csh /tmp/dowhile
 28 160  -5   700 13.0   0:26.73 /bin/csh /tmp/dowhile
 23 160   0   698 11.5   0:20.52 /bin/csh /tmp/dowhile
 18 160   5   696  9.2   0:16.85 /bin/csh /tmp/dowhile
 13 160  10   694  7.1   0:10.82 /bin/csh /tmp/dowhile
  3 160  20   692  1.5   0:02.14 /bin/csh /tmp/dowhile

sys/dev/netif/iwi/if_iwi.c
sys/dev/netif/ndis/if_ndis.c
sys/dev/raid/twa/twa.c
sys/dev/raid/twe/twe.c
sys/kern/kern_synch.c
sys/kern/subr_param.c
sys/sys/param.h
sys/sys/proc.h
sys/sys/usched.h

index 9f66949..94d87e9 100644 (file)
@@ -28,7 +28,7 @@
  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  * SUCH DAMAGE.
  *
- * $DragonFly: src/sys/dev/netif/iwi/if_iwi.c,v 1.3 2005/05/24 20:59:01 dillon Exp $
+ * $DragonFly: src/sys/dev/netif/iwi/if_iwi.c,v 1.4 2005/06/26 22:03:25 dillon Exp $
  */
 
 #include "opt_inet.h"
@@ -1733,7 +1733,7 @@ iwi_wi_ioctl_get(struct ifnet *ifp, caddr_t data)
        case WI_RID_READ_APS:
                ieee80211_begin_scan(ifp);
                (void) tsleep(IWI_FW_SCAN_COMPLETED(sc), 
-                       PPAUSE|PCATCH, "ssidscan", hz * 2);
+                       PCATCH, "ssidscan", hz * 2);
                ieee80211_end_scan(ifp);
                break;
        default:
index 514c166..f75d8f6 100644 (file)
@@ -30,7 +30,7 @@
  * THE POSSIBILITY OF SUCH DAMAGE.
  *
  * $FreeBSD: src/sys/dev/if_ndis/if_ndis.c,v 1.65 2004/07/07 17:46:30 wpaul Exp $
- * $DragonFly: src/sys/dev/netif/ndis/if_ndis.c,v 1.5 2005/05/24 20:59:01 dillon Exp $
+ * $DragonFly: src/sys/dev/netif/ndis/if_ndis.c,v 1.6 2005/06/26 22:03:26 dillon Exp $
  */
 
 #include <sys/param.h>
@@ -1977,7 +1977,7 @@ ndis_wi_ioctl_get(ifp, command, data)
                error = ndis_set_info(sc, OID_802_11_BSSID_LIST_SCAN,
                    NULL, &len);
                if (error == 0)
-                       tsleep(&error, PPAUSE|PCATCH, "ssidscan", hz * 2);
+                       tsleep(&error, PCATCH, "ssidscan", hz * 2);
                len = 0;
                error = ndis_get_info(sc, OID_802_11_BSSID_LIST, NULL, &len);
                if (error != ENOSPC)
index 2fb3ed7..949e0a8 100644 (file)
@@ -26,7 +26,7 @@
  * SUCH DAMAGE.
  *
  *     $FreeBSD$
- * $DragonFly: src/sys/dev/raid/twa/twa.c,v 1.3 2005/06/10 17:10:26 swildner Exp $
+ * $DragonFly: src/sys/dev/raid/twa/twa.c,v 1.4 2005/06/26 22:03:28 dillon Exp $
  */
 
 /*
@@ -575,7 +575,7 @@ twa_ioctl(struct twa_softc *sc, int cmd, void *buf)
                         * No free request packets available.  Sleep until
                         * one becomes available.
                         */
-                       tsleep(&(sc->twa_wait_timeout), PPAUSE, "twioctl", hz);
+                       tsleep(&(sc->twa_wait_timeout), 0, "twioctl", hz);
 
                /*
                 * Make sure that the data buffer sent to firmware is a 
index 09f9b27..da4a964 100644 (file)
@@ -25,7 +25,7 @@
  * SUCH DAMAGE.
  *
  *     $FreeBSD: src/sys/dev/twe/twe.c,v 1.1.2.6 2002/03/07 09:57:02 msmith Exp $
- *     $DragonFly: src/sys/dev/raid/twe/twe.c,v 1.10 2005/06/10 17:10:26 swildner Exp $
+ *     $DragonFly: src/sys/dev/raid/twe/twe.c,v 1.11 2005/06/26 22:03:29 dillon Exp $
  */
 
 /*
@@ -488,7 +488,7 @@ twe_ioctl(struct twe_softc *sc, int cmd, void *addr)
     case TWEIO_COMMAND:
        /* get a request */
        while (twe_get_request(sc, &tr))
-           tsleep(sc, PPAUSE, "twioctl", hz);
+           tsleep(sc, 0, "twioctl", hz);
 
        /*
         * Save the command's request ID, copy the user-supplied command in,
index 6dd4d5b..edf5226 100644 (file)
@@ -37,7 +37,7 @@
  *
  *     @(#)kern_synch.c        8.9 (Berkeley) 5/19/95
  * $FreeBSD: src/sys/kern/kern_synch.c,v 1.87.2.6 2002/10/13 07:29:53 kbyanc Exp $
- * $DragonFly: src/sys/kern/kern_synch.c,v 1.45 2005/06/26 04:36:31 dillon Exp $
+ * $DragonFly: src/sys/kern/kern_synch.c,v 1.46 2005/06/26 22:03:22 dillon Exp $
  */
 
 #include "opt_ktrace.h"
@@ -93,6 +93,10 @@ static void  roundrobin (void *arg);
 static void    schedcpu (void *arg);
 static void    updatepri (struct proc *p);
 
+/*
+ * Adjust the scheduler quantum.  The quantum is specified in microseconds.
+ * Note that 'tick' is in microseconds per tick.
+ */
 static int
 sysctl_kern_quantum(SYSCTL_HANDLER_ARGS)
 {
@@ -159,7 +163,7 @@ resched_cpus(u_int32_t mask)
 
 /*
  * The load average is scaled by FSCALE (2048 typ).  The estimated cpu is
- * incremented at a rate of ESTCPUVFREQ per second (40hz typ), but this is
+ * incremented at a rate of ESTCPUFREQ per second (50hz typ), but this is
  * divided up across all cpu bound processes running in the system so an
  * individual process will get less under load.  ESTCPULIM typicaly caps
  * out at ESTCPUMAX (around 376, or 11 nice levels).
@@ -170,16 +174,14 @@ resched_cpus(u_int32_t mask)
  * should reach this value when estcpu reaches ESTCPUMAX.  That calculation
  * is:
  *
- *     ESTCPUMAX * decay = ESTCPUVFREQ / load
- *     decay = ESTCPUVFREQ / (load * ESTCPUMAX)
+ *     ESTCPUMAX * decay = ESTCPUFREQ / load
+ *     decay = ESTCPUFREQ / (load * ESTCPUMAX)
  *     decay = estcpu * 0.053 / load
  *
  * If the load is less then 1.0 we assume a load of 1.0.
  */
 
 #define cload(loadav)  ((loadav) < FSCALE ? FSCALE : (loadav))
-#define decay_cpu(loadav,estcpu)       \
-    ((estcpu) * (FSCALE * ESTCPUVFREQ / ESTCPUMAX) / cload(loadav))
 
 /* decay 95% of `p_pctcpu' in 60 seconds; see CCPU_SHIFT before changing */
 static fixpt_t ccpu = 0.95122942450071400909 * FSCALE; /* exp(-1/20) */
@@ -212,7 +214,7 @@ schedcpu(void *arg)
 {
        fixpt_t loadfac = averunnable.ldavg[0];
        struct proc *p;
-       unsigned int ndecay;
+       int ndecay;
 
        FOREACH_PROC_IN_SYSTEM(p) {
                /*
@@ -228,28 +230,12 @@ schedcpu(void *arg)
                /*
                 * If the process has slept the entire second,
                 * stop recalculating its priority until it wakes up.
-                *
-                * Note that interactive calculations do not occur for
-                * long sleeps (because that isn't necessarily indicative
-                * of an interactive process).
                 */
                if (p->p_slptime > 1)
                        continue;
                /* prevent state changes and protect run queue */
                crit_enter();
 
-               /*
-                * p_cpticks runs at ESTCPUFREQ but must be divided by the
-                * load average for par-100% use.  Higher p_interactive
-                * values mean less interactive, lower values mean more 
-                * interactive.
-                */
-               if ((((fixpt_t)p->p_cpticks * cload(loadfac)) >> FSHIFT)  >
-                   ESTCPUFREQ / 4) {
-                       p->p_usched->heuristic_estcpu(p, 1);
-               } else {
-                       p->p_usched->heuristic_estcpu(p, -1);
-               }
                /*
                 * p_pctcpu is only for ps.
                 */
@@ -262,13 +248,41 @@ schedcpu(void *arg)
                p->p_pctcpu += ((FSCALE - ccpu) *
                        (p->p_cpticks * FSCALE / ESTCPUFREQ)) >> FSHIFT;
 #endif
+               /*
+                * A single cpu-bound process with a system load of 1.0 will
+                * increment cpticks by ESTCPUFREQ per second.  Scale
+                * cpticks by the load to normalize it relative to 
+                * ESTCPUFREQ.  This gives us an indication as to what
+                * proportional percentage of available cpu the process has
+                * used with a nominal range of 0 to ESTCPUFREQ.
+                *
+                * It should be noted that since the load average is a
+                * trailing indicator, a jump in the load will cause this
+                * calculation to be higher then normal.  This is desireable
+                * because it penalizes the processes responsible for the
+                * spike.
+                */
+               ndecay = (int)((p->p_cpticks * cload(loadfac)) >> FSHIFT);
+
+               /*
+                * Reduce p_estcpu based on the amount of cpu that could
+                * have been used but wasn't.  Convert ndecay from the
+                * amount used to the amount not used, and scale with our
+                * nice value.
+                *
+                * The nice scaling determines how much the nice value
+                * effects the cpu the process gets.
+                */
+               ndecay = ESTCPUFREQ - ndecay;
+               ndecay -= p->p_nice * (ESTCPUMAX / 16) / PRIO_MAX;
+
                p->p_cpticks = 0;
-               ndecay = decay_cpu(loadfac, p->p_estcpu);
-               if (p->p_estcpu > ndecay)
+               if (ndecay > 0) {
+                       if (ndecay > p->p_estcpu / 2)
+                               ndecay = p->p_estcpu / 2;
                        p->p_estcpu -= ndecay;
-               else
-                       p->p_estcpu = 0;
-               p->p_usched->resetpriority(p);
+                       p->p_usched->resetpriority(p);
+               }
                crit_exit();
        }
        wakeup((caddr_t)&lbolt);
@@ -283,14 +297,16 @@ schedcpu(void *arg)
 static void
 updatepri(struct proc *p)
 {
-       unsigned int ndecay;
-
-       ndecay = decay_cpu(averunnable.ldavg[0], p->p_estcpu) * p->p_slptime;
-       if (p->p_estcpu > ndecay)
-               p->p_estcpu -= ndecay;
-       else
-               p->p_estcpu = 0;
-       p->p_usched->resetpriority(p);
+       int ndecay;
+
+       ndecay = p->p_slptime * ESTCPUFREQ;
+       if (ndecay > 0) {
+               if (p->p_estcpu > ndecay)
+                       p->p_estcpu -= ndecay;
+               else
+                       p->p_estcpu = 0;
+               p->p_usched->resetpriority(p);
+       }
 }
 
 /*
@@ -303,16 +319,15 @@ static TAILQ_HEAD(slpquehead, thread) slpque[TABLESIZE];
 #define LOOKUP(x)      (((intptr_t)(x) >> 8) & (TABLESIZE - 1))
 
 /*
- * During autoconfiguration or after a panic, a sleep will simply
- * lower the priority briefly to allow interrupts, then return.
+ * General scheduler initialization.  We force a reschedule 25 times
+ * a second by default.
  */
-
 void
 sleepinit(void)
 {
        int i;
 
-       sched_quantum = hz/10;
+       sched_quantum = (hz + 24) / 25;
        hogticks = 2 * sched_quantum;
        for (i = 0; i < TABLESIZE; i++)
                TAILQ_INIT(&slpque[i]);
@@ -331,6 +346,9 @@ sleepinit(void)
  *
  * Note that if we are a process, we release_curproc() before messing with
  * the LWKT scheduler.
+ *
+ * During autoconfiguration or after a panic, a sleep will simply
+ * lower the priority briefly to allow interrupts, then return.
  */
 int
 tsleep(void *ident, int flags, const char *wmesg, int timo)
@@ -780,12 +798,6 @@ sched_setup(void *dummy)
  * time in 5 * loadav seconds.  This causes the system to favor processes
  * which haven't run much recently, and to round-robin among other processes.
  *
- * The actual schedulerclock interrupt rate is ESTCPUFREQ, but we generally
- * want to ramp-up at a faster rate, ESTCPUVFREQ, so p_estcpu is scaled
- * by (ESTCPUVFREQ / ESTCPUFREQ).  You can control the ramp-up/ramp-down
- * rate by adjusting ESTCPUVFREQ in sys/proc.h in integer multiples
- * of ESTCPUFREQ.
- *
  * WARNING! called from a fast-int or an IPI, the MP lock MIGHT NOT BE HELD
  * and we cannot block.
  */
@@ -798,7 +810,7 @@ schedulerclock(void *dummy)
        td = curthread;
        if ((p = td->td_proc) != NULL) {
                p->p_cpticks++;         /* cpticks runs at ESTCPUFREQ */
-               p->p_estcpu = ESTCPULIM(p->p_estcpu + ESTCPUVFREQ / ESTCPUFREQ);
+               p->p_estcpu = ESTCPULIM(p->p_estcpu + 1);
                if (try_mplock()) {
                        p->p_usched->resetpriority(p);
                        rel_mplock();
index f1f40e2..5b693e8 100644 (file)
@@ -37,7 +37,7 @@
  *
  *     @(#)param.c     8.3 (Berkeley) 8/20/94
  * $FreeBSD: src/sys/kern/subr_param.c,v 1.42.2.10 2002/03/09 21:05:47 silby Exp $
- * $DragonFly: src/sys/kern/subr_param.c,v 1.6 2005/04/14 07:55:36 joerg Exp $
+ * $DragonFly: src/sys/kern/subr_param.c,v 1.7 2005/06/26 22:03:22 dillon Exp $
  */
 
 #include "opt_param.h"
@@ -73,7 +73,7 @@
 int    hz;
 int    stathz;
 int    profhz;
-int    tick;
+int    tick;                           /* tick interval in microseconds */
 int    maxusers;                       /* base tunable */
 int    maxproc;                        /* maximum # of processes */
 int    maxprocperuid;                  /* max # of procs per user */
index 3002b1c..b342674 100644 (file)
@@ -37,7 +37,7 @@
  *
  *     @(#)param.h     8.3 (Berkeley) 4/4/95
  * $FreeBSD: src/sys/sys/param.h,v 1.61.2.38 2003/05/22 17:12:01 fjoe Exp $
- * $DragonFly: src/sys/sys/param.h,v 1.23 2005/06/01 18:07:09 joerg Exp $
+ * $DragonFly: src/sys/sys/param.h,v 1.24 2005/06/26 22:03:23 dillon Exp $
  */
 
 #ifndef _SYS_PARAM_H_
 #include <machine/limits.h>
 #endif
 
-/*
- * Priorities.  Note that with 32 run queues, differences less than 4 are
- * insignificant.
- */
-#define MAXPRI 127             /* Priorities range from 0 through MAXPRI. */
-#define PPAUSE                 40
-#define PRIMASK        127
-#define PRIBASE_REALTIME       0
-#define PRIBASE_NORMAL         128
-#define PRIBASE_IDLE           256
-#define PRIBASE_THREAD         384     /* huh? */
-#define PRIBASE_NULL           512
-
 #define PCATCH         0x00000100      /* tsleep checks signals */
 #define PUSRFLAG1      0x00000200      /* Subsystem specific flag */
 #define PNORESCHED     0x00000400      /* No reschedule on wakeup */
index 51032c2..f9b49d6 100644 (file)
@@ -37,7 +37,7 @@
  *
  *     @(#)proc.h      8.15 (Berkeley) 5/19/95
  * $FreeBSD: src/sys/sys/proc.h,v 1.99.2.9 2003/06/06 20:21:32 tegge Exp $
- * $DragonFly: src/sys/sys/proc.h,v 1.59 2005/06/26 04:36:33 dillon Exp $
+ * $DragonFly: src/sys/sys/proc.h,v 1.60 2005/06/26 22:03:23 dillon Exp $
  */
 
 #ifndef _SYS_PROC_H_
@@ -369,39 +369,14 @@ extern struct proclist zombproc;  /* List of zombie processes. */
 extern struct proc *initproc;          /* Process slot for init */
 extern struct thread *pagethread, *updatethread;
 
-#define        NQS     32                      /* 32 run queues. */
-TAILQ_HEAD(rq, proc);
-
 /*
- * Scheduler estcpu macros.
- *
- * p_priority = NICE_ADJUST(p->p_nice - PRIO_MIN) +
- *                     p->p_estcpu / ESTCPURAMP;
- *
- * NICE_WEIGHT determines the p_estcpu overlap between nice levels.   It
- * cannot exceed 3.0.  A value of 2.0 gives us a nice small overlap between
- * nice -20 and nice +0.  A value of 3.0 reduces the overlap while a value
- * of 1.0 increases the overlap.
- *
- * ESTCPURAMP determines how slowly estcpu effects the process priority.
- * Higher numbers result in slower ramp-up times because estcpu is incremented
- * once per scheduler tick and maxes out at ESTCPULIM.
- *
- * ESTCPULIM = (127 - 2 * 40) * 8 = 376
- *
- * NOTE: ESTCPUVFREQ is the 'virtual' estcpu accumulation frequency, whereas
- * ESTCPUFREQ is the actual interrupt rate.  The ratio is used to scale
- * both the ramp-up and the decay calculations in kern_synch.c.  
+ * Scheduler independant variables.  The primary scheduler polling frequency,
+ * the maximum ESTCPU value, and the weighting factor for nice values.  A
+ * cpu bound program's estcpu will increase to ESTCPUMAX - 1.
  */
-
-#define ESTCPURAMP     8                       /* higher equals slower */
-#define NICE_ADJUST(value)     (((unsigned int)(NICE_WEIGHT * 128) * (value)) / 128)
-#define ESTCPUMAX      ((MAXPRI - NICE_ADJUST(PRIO_MAX - PRIO_MIN)) * ESTCPURAMP)
+#define ESTCPUMAX      128
 #define ESTCPULIM(v)   min((v), ESTCPUMAX)
-#define ESTCPUFREQ     20                      /* estcpu update frequency */
-#define ESTCPUVFREQ    40                      /* virtual freq controls ramp*/
-#define        NICE_WEIGHT     2.0                     /* priorities per nice level */
-#define        PPQ             ((MAXPRI + 1) / NQS)    /* priorities per queue */
+#define ESTCPUFREQ     50
 
 extern u_long ps_arg_cache_limit;
 extern int ps_argsopen;
@@ -425,7 +400,6 @@ void        mi_switch (struct proc *p);
 void   procinit (void);
 void   relscurproc(struct proc *curp);
 int    p_trespass (struct ucred *cr1, struct ucred *cr2);
-void   resetpriority (struct proc *);
 int    roundrobin_interval (void);
 void   resched_cpus(u_int32_t mask);
 void   schedulerclock (void *dummy);
index 6af09a4..40c89d8 100644 (file)
@@ -3,7 +3,7 @@
  *
  *     Userland scheduler API
  * 
- * $DragonFly: src/sys/sys/usched.h,v 1.2 2005/06/26 04:36:33 dillon Exp $
+ * $DragonFly: src/sys/sys/usched.h,v 1.3 2005/06/26 22:03:23 dillon Exp $
  */
 
 #ifndef _SYS_USCHED_H_
@@ -28,7 +28,6 @@ struct usched {
     void (*resetpriority)(struct proc *);
     void (*heuristic_forking)(struct proc *, struct proc *);
     void (*heuristic_exiting)(struct proc *, struct proc *);
-    void (*heuristic_estcpu)(struct proc *, int);
 };
 
 union usched_data {
@@ -37,9 +36,9 @@ union usched_data {
      */
     struct {
        short   priority;       /* lower is better */
-       char    interactive;    /* interactivity heuristic */
+       char    interactive;    /* (currently not used) */
        char    rqindex;
-       u_int   estcpu_fork;    /* interactivity heuristic */
+       u_int   childscpu;
     } bsd4;
 
     int                pad[4];         /* PAD for future expansion */