The Design and Implementation of the FreeBSD Operating System, Second Edition
Now available: The Design and Implementation of the FreeBSD Operating System (Second Edition)


[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]

FreeBSD/Linux Kernel Cross Reference
sys/kern/sched_4bsd.c

Version: -  FREEBSD  -  FREEBSD-13-STABLE  -  FREEBSD-13-0  -  FREEBSD-12-STABLE  -  FREEBSD-12-0  -  FREEBSD-11-STABLE  -  FREEBSD-11-0  -  FREEBSD-10-STABLE  -  FREEBSD-10-0  -  FREEBSD-9-STABLE  -  FREEBSD-9-0  -  FREEBSD-8-STABLE  -  FREEBSD-8-0  -  FREEBSD-7-STABLE  -  FREEBSD-7-0  -  FREEBSD-6-STABLE  -  FREEBSD-6-0  -  FREEBSD-5-STABLE  -  FREEBSD-5-0  -  FREEBSD-4-STABLE  -  FREEBSD-3-STABLE  -  FREEBSD22  -  l41  -  OPENBSD  -  linux-2.6  -  MK84  -  PLAN9  -  xnu-8792 
SearchContext: -  none  -  3  -  10 

    1 /*      $NetBSD: sched_4bsd.c,v 1.24.4.1 2009/06/06 22:12:44 bouyer Exp $       */
    2 
    3 /*-
    4  * Copyright (c) 1999, 2000, 2004, 2006, 2007, 2008 The NetBSD Foundation, Inc.
    5  * All rights reserved.
    6  *
    7  * This code is derived from software contributed to The NetBSD Foundation
    8  * by Jason R. Thorpe of the Numerical Aerospace Simulation Facility,
    9  * NASA Ames Research Center, by Charles M. Hannum, Andrew Doran, and
   10  * Daniel Sieger.
   11  *
   12  * Redistribution and use in source and binary forms, with or without
   13  * modification, are permitted provided that the following conditions
   14  * are met:
   15  * 1. Redistributions of source code must retain the above copyright
   16  *    notice, this list of conditions and the following disclaimer.
   17  * 2. Redistributions in binary form must reproduce the above copyright
   18  *    notice, this list of conditions and the following disclaimer in the
   19  *    documentation and/or other materials provided with the distribution.
   20  *
   21  * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
   22  * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
   23  * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
   24  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
   25  * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
   26  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
   27  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
   28  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
   29  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
   30  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
   31  * POSSIBILITY OF SUCH DAMAGE.
   32  */
   33 
   34 /*-
   35  * Copyright (c) 1982, 1986, 1990, 1991, 1993
   36  *      The Regents of the University of California.  All rights reserved.
   37  * (c) UNIX System Laboratories, Inc.
   38  * All or some portions of this file are derived from material licensed
   39  * to the University of California by American Telephone and Telegraph
   40  * Co. or Unix System Laboratories, Inc. and are reproduced herein with
   41  * the permission of UNIX System Laboratories, Inc.
   42  *
   43  * Redistribution and use in source and binary forms, with or without
   44  * modification, are permitted provided that the following conditions
   45  * are met:
   46  * 1. Redistributions of source code must retain the above copyright
   47  *    notice, this list of conditions and the following disclaimer.
   48  * 2. Redistributions in binary form must reproduce the above copyright
   49  *    notice, this list of conditions and the following disclaimer in the
   50  *    documentation and/or other materials provided with the distribution.
   51  * 3. Neither the name of the University nor the names of its contributors
   52  *    may be used to endorse or promote products derived from this software
   53  *    without specific prior written permission.
   54  *
   55  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
   56  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
   57  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
   58  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
   59  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
   60  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
   61  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
   62  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
   63  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
   64  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
   65  * SUCH DAMAGE.
   66  *
   67  *      @(#)kern_synch.c        8.9 (Berkeley) 5/19/95
   68  */
   69 
   70 #include <sys/cdefs.h>
   71 __KERNEL_RCSID(0, "$NetBSD: sched_4bsd.c,v 1.24.4.1 2009/06/06 22:12:44 bouyer Exp $");
   72 
   73 #include "opt_ddb.h"
   74 #include "opt_lockdebug.h"
   75 #include "opt_perfctrs.h"
   76 
   77 #include <sys/param.h>
   78 #include <sys/systm.h>
   79 #include <sys/callout.h>
   80 #include <sys/cpu.h>
   81 #include <sys/proc.h>
   82 #include <sys/kernel.h>
   83 #include <sys/signalvar.h>
   84 #include <sys/resourcevar.h>
   85 #include <sys/sched.h>
   86 #include <sys/sysctl.h>
   87 #include <sys/kauth.h>
   88 #include <sys/lockdebug.h>
   89 #include <sys/kmem.h>
   90 #include <sys/intr.h>
   91 
   92 #include <uvm/uvm_extern.h>
   93 
   94 static void updatepri(struct lwp *);
   95 static void resetpriority(struct lwp *);
   96 
   97 extern unsigned int sched_pstats_ticks; /* defined in kern_synch.c */
   98 
   99 /* Number of hardclock ticks per sched_tick() */
  100 static int rrticks;
  101 
  102 /*
  103  * Force switch among equal priority processes every 100ms.
  104  * Called from hardclock every hz/10 == rrticks hardclock ticks.
  105  *
  106  * There's no need to lock anywhere in this routine, as it's
  107  * CPU-local and runs at IPL_SCHED (called from clock interrupt).
  108  */
  109 /* ARGSUSED */
  110 void
  111 sched_tick(struct cpu_info *ci)
  112 {
  113         struct schedstate_percpu *spc = &ci->ci_schedstate;
  114         lwp_t *l;
  115 
  116         spc->spc_ticks = rrticks;
  117 
  118         if (CURCPU_IDLE_P()) {
  119                 cpu_need_resched(ci, 0);
  120                 return;
  121         }
  122         l = ci->ci_data.cpu_onproc;
  123         if (l == NULL) {
  124                 return;
  125         }
  126         switch (l->l_class) {
  127         case SCHED_FIFO:
  128                 /* No timeslicing for FIFO jobs. */
  129                 break;
  130         case SCHED_RR:
  131                 /* Force it into mi_switch() to look for other jobs to run. */
  132                 cpu_need_resched(ci, RESCHED_KPREEMPT);
  133                 break;
  134         default:
  135                 if (spc->spc_flags & SPCF_SHOULDYIELD) {
  136                         /*
  137                          * Process is stuck in kernel somewhere, probably
  138                          * due to buggy or inefficient code.  Force a 
  139                          * kernel preemption.
  140                          */
  141                         cpu_need_resched(ci, RESCHED_KPREEMPT);
  142                 } else if (spc->spc_flags & SPCF_SEENRR) {
  143                         /*
  144                          * The process has already been through a roundrobin
  145                          * without switching and may be hogging the CPU.
  146                          * Indicate that the process should yield.
  147                          */
  148                         spc->spc_flags |= SPCF_SHOULDYIELD;
  149                         cpu_need_resched(ci, 0);
  150                 } else {
  151                         spc->spc_flags |= SPCF_SEENRR;
  152                 }
  153                 break;
  154         }
  155 }
  156 
  157 /*
  158  * Why PRIO_MAX - 2? From setpriority(2):
  159  *
  160  *      prio is a value in the range -20 to 20.  The default priority is
  161  *      0; lower priorities cause more favorable scheduling.  A value of
  162  *      19 or 20 will schedule a process only when nothing at priority <=
  163  *      0 is runnable.
  164  *
  165  * This gives estcpu influence over 18 priority levels, and leaves nice
  166  * with 40 levels.  One way to think about it is that nice has 20 levels
  167  * either side of estcpu's 18.
  168  */
  169 #define ESTCPU_SHIFT    11
  170 #define ESTCPU_MAX      ((PRIO_MAX - 2) << ESTCPU_SHIFT)
  171 #define ESTCPU_ACCUM    (1 << (ESTCPU_SHIFT - 1))
  172 #define ESTCPULIM(e)    min((e), ESTCPU_MAX)
  173 
  174 /*
  175  * Constants for digital decay and forget:
  176  *      90% of (l_estcpu) usage in 5 * loadav time
  177  *      95% of (l_pctcpu) usage in 60 seconds (load insensitive)
  178  *          Note that, as ps(1) mentions, this can let percentages
  179  *          total over 100% (I've seen 137.9% for 3 processes).
  180  *
  181  * Note that hardclock updates l_estcpu and l_cpticks independently.
  182  *
  183  * We wish to decay away 90% of l_estcpu in (5 * loadavg) seconds.
  184  * That is, the system wants to compute a value of decay such
  185  * that the following for loop:
  186  *      for (i = 0; i < (5 * loadavg); i++)
  187  *              l_estcpu *= decay;
  188  * will compute
  189  *      l_estcpu *= 0.1;
  190  * for all values of loadavg:
  191  *
  192  * Mathematically this loop can be expressed by saying:
  193  *      decay ** (5 * loadavg) ~= .1
  194  *
  195  * The system computes decay as:
  196  *      decay = (2 * loadavg) / (2 * loadavg + 1)
  197  *
  198  * We wish to prove that the system's computation of decay
  199  * will always fulfill the equation:
  200  *      decay ** (5 * loadavg) ~= .1
  201  *
  202  * If we compute b as:
  203  *      b = 2 * loadavg
  204  * then
  205  *      decay = b / (b + 1)
  206  *
  207  * We now need to prove two things:
  208  *      1) Given factor ** (5 * loadavg) ~= .1, prove factor == b/(b+1)
  209  *      2) Given b/(b+1) ** power ~= .1, prove power == (5 * loadavg)
  210  *
  211  * Facts:
  212  *         For x close to zero, exp(x) =~ 1 + x, since
  213  *              exp(x) = 0! + x**1/1! + x**2/2! + ... .
  214  *              therefore exp(-1/b) =~ 1 - (1/b) = (b-1)/b.
  215  *         For x close to zero, ln(1+x) =~ x, since
  216  *              ln(1+x) = x - x**2/2 + x**3/3 - ...     -1 < x < 1
  217  *              therefore ln(b/(b+1)) = ln(1 - 1/(b+1)) =~ -1/(b+1).
  218  *         ln(.1) =~ -2.30
  219  *
  220  * Proof of (1):
  221  *    Solve (factor)**(power) =~ .1 given power (5*loadav):
  222  *      solving for factor,
  223  *      ln(factor) =~ (-2.30/5*loadav), or
  224  *      factor =~ exp(-1/((5/2.30)*loadav)) =~ exp(-1/(2*loadav)) =
  225  *          exp(-1/b) =~ (b-1)/b =~ b/(b+1).                    QED
  226  *
  227  * Proof of (2):
  228  *    Solve (factor)**(power) =~ .1 given factor == (b/(b+1)):
  229  *      solving for power,
  230  *      power*ln(b/(b+1)) =~ -2.30, or
  231  *      power =~ 2.3 * (b + 1) = 4.6*loadav + 2.3 =~ 5*loadav.  QED
  232  *
  233  * Actual power values for the implemented algorithm are as follows:
  234  *      loadav: 1       2       3       4
  235  *      power:  5.68    10.32   14.94   19.55
  236  */
  237 
  238 /* calculations for digital decay to forget 90% of usage in 5*loadav sec */
  239 #define loadfactor(loadav)      (2 * (loadav))
  240 
  241 static fixpt_t
  242 decay_cpu(fixpt_t loadfac, fixpt_t estcpu)
  243 {
  244 
  245         if (estcpu == 0) {
  246                 return 0;
  247         }
  248 
  249 #if !defined(_LP64)
  250         /* avoid 64bit arithmetics. */
  251 #define FIXPT_MAX ((fixpt_t)((UINTMAX_C(1) << sizeof(fixpt_t) * CHAR_BIT) - 1))
  252         if (__predict_true(loadfac <= FIXPT_MAX / ESTCPU_MAX)) {
  253                 return estcpu * loadfac / (loadfac + FSCALE);
  254         }
  255 #endif /* !defined(_LP64) */
  256 
  257         return (uint64_t)estcpu * loadfac / (loadfac + FSCALE);
  258 }
  259 
  260 /*
  261  * For all load averages >= 1 and max l_estcpu of (255 << ESTCPU_SHIFT),
  262  * sleeping for at least seven times the loadfactor will decay l_estcpu to
  263  * less than (1 << ESTCPU_SHIFT).
  264  *
  265  * note that our ESTCPU_MAX is actually much smaller than (255 << ESTCPU_SHIFT).
  266  */
  267 static fixpt_t
  268 decay_cpu_batch(fixpt_t loadfac, fixpt_t estcpu, unsigned int n)
  269 {
  270 
  271         if ((n << FSHIFT) >= 7 * loadfac) {
  272                 return 0;
  273         }
  274 
  275         while (estcpu != 0 && n > 1) {
  276                 estcpu = decay_cpu(loadfac, estcpu);
  277                 n--;
  278         }
  279 
  280         return estcpu;
  281 }
  282 
  283 /*
  284  * sched_pstats_hook:
  285  *
  286  * Periodically called from sched_pstats(); used to recalculate priorities.
  287  */
  288 void
  289 sched_pstats_hook(struct lwp *l, int batch)
  290 {
  291         fixpt_t loadfac;
  292 
  293         /*
  294          * If the LWP has slept an entire second, stop recalculating
  295          * its priority until it wakes up.
  296          */
  297         KASSERT(lwp_locked(l, NULL));
  298         if (l->l_stat == LSSLEEP || l->l_stat == LSSTOP ||
  299             l->l_stat == LSSUSPENDED) {
  300                 if (l->l_slptime > 1) {
  301                         return;
  302                 }
  303         }
  304         loadfac = 2 * (averunnable.ldavg[0]);
  305         l->l_estcpu = decay_cpu(loadfac, l->l_estcpu);
  306         resetpriority(l);
  307 }
  308 
  309 /*
  310  * Recalculate the priority of a process after it has slept for a while.
  311  */
  312 static void
  313 updatepri(struct lwp *l)
  314 {
  315         fixpt_t loadfac;
  316 
  317         KASSERT(lwp_locked(l, NULL));
  318         KASSERT(l->l_slptime > 1);
  319 
  320         loadfac = loadfactor(averunnable.ldavg[0]);
  321 
  322         l->l_slptime--; /* the first time was done in sched_pstats */
  323         l->l_estcpu = decay_cpu_batch(loadfac, l->l_estcpu, l->l_slptime);
  324         resetpriority(l);
  325 }
  326 
  327 void
  328 sched_rqinit(void)
  329 {
  330 
  331 }
  332 
  333 void
  334 sched_setrunnable(struct lwp *l)
  335 {
  336 
  337         if (l->l_slptime > 1)
  338                 updatepri(l);
  339 }
  340 
  341 void
  342 sched_nice(struct proc *p, int n)
  343 {
  344         struct lwp *l;
  345 
  346         KASSERT(mutex_owned(p->p_lock));
  347 
  348         p->p_nice = n;
  349         LIST_FOREACH(l, &p->p_lwps, l_sibling) {
  350                 lwp_lock(l);
  351                 resetpriority(l);
  352                 lwp_unlock(l);
  353         }
  354 }
  355 
  356 /*
  357  * Recompute the priority of an LWP.  Arrange to reschedule if
  358  * the resulting priority is better than that of the current LWP.
  359  */
  360 static void
  361 resetpriority(struct lwp *l)
  362 {
  363         pri_t pri;
  364         struct proc *p = l->l_proc;
  365 
  366         KASSERT(lwp_locked(l, NULL));
  367 
  368         if (l->l_class != SCHED_OTHER)
  369                 return;
  370 
  371         /* See comments above ESTCPU_SHIFT definition. */
  372         pri = (PRI_KERNEL - 1) - (l->l_estcpu >> ESTCPU_SHIFT) - p->p_nice;
  373         pri = imax(pri, 0);
  374         if (pri != l->l_priority)
  375                 lwp_changepri(l, pri);
  376 }
  377 
  378 /*
  379  * We adjust the priority of the current process.  The priority of a process
  380  * gets worse as it accumulates CPU time.  The CPU usage estimator (l_estcpu)
  381  * is increased here.  The formula for computing priorities (in kern_synch.c)
  382  * will compute a different value each time l_estcpu increases. This can
  383  * cause a switch, but unless the priority crosses a PPQ boundary the actual
  384  * queue will not change.  The CPU usage estimator ramps up quite quickly
  385  * when the process is running (linearly), and decays away exponentially, at
  386  * a rate which is proportionally slower when the system is busy.  The basic
  387  * principle is that the system will 90% forget that the process used a lot
  388  * of CPU time in 5 * loadav seconds.  This causes the system to favor
  389  * processes which haven't run much recently, and to round-robin among other
  390  * processes.
  391  */
  392 
  393 void
  394 sched_schedclock(struct lwp *l)
  395 {
  396 
  397         if (l->l_class != SCHED_OTHER)
  398                 return;
  399 
  400         KASSERT(!CURCPU_IDLE_P());
  401         l->l_estcpu = ESTCPULIM(l->l_estcpu + ESTCPU_ACCUM);
  402         lwp_lock(l);
  403         resetpriority(l);
  404         lwp_unlock(l);
  405 }
  406 
  407 /*
  408  * sched_proc_fork:
  409  *
  410  *      Inherit the parent's scheduler history.
  411  */
  412 void
  413 sched_proc_fork(struct proc *parent, struct proc *child)
  414 {
  415         lwp_t *pl;
  416 
  417         KASSERT(mutex_owned(parent->p_lock));
  418 
  419         pl = LIST_FIRST(&parent->p_lwps);
  420         child->p_estcpu_inherited = pl->l_estcpu;
  421         child->p_forktime = sched_pstats_ticks;
  422 }
  423 
  424 /*
  425  * sched_proc_exit:
  426  *
  427  *      Chargeback parents for the sins of their children.
  428  */
  429 void
  430 sched_proc_exit(struct proc *parent, struct proc *child)
  431 {
  432         fixpt_t loadfac = loadfactor(averunnable.ldavg[0]);
  433         fixpt_t estcpu;
  434         lwp_t *pl, *cl;
  435 
  436         /* XXX Only if parent != init?? */
  437 
  438         mutex_enter(parent->p_lock);
  439         pl = LIST_FIRST(&parent->p_lwps);
  440         cl = LIST_FIRST(&child->p_lwps);
  441         estcpu = decay_cpu_batch(loadfac, child->p_estcpu_inherited,
  442             sched_pstats_ticks - child->p_forktime);
  443         if (cl->l_estcpu > estcpu) {
  444                 lwp_lock(pl);
  445                 pl->l_estcpu = ESTCPULIM(pl->l_estcpu + cl->l_estcpu - estcpu);
  446                 lwp_unlock(pl);
  447         }
  448         mutex_exit(parent->p_lock);
  449 }
  450 
  451 void
  452 sched_wakeup(struct lwp *l)
  453 {
  454 
  455 }
  456 
  457 void
  458 sched_slept(struct lwp *l)
  459 {
  460 
  461 }
  462 
  463 void
  464 sched_lwp_fork(struct lwp *l1, struct lwp *l2)
  465 {
  466 
  467         l2->l_estcpu = l1->l_estcpu;
  468 }
  469 
  470 void
  471 sched_lwp_collect(struct lwp *t)
  472 {
  473         lwp_t *l;
  474 
  475         /* Absorb estcpu value of collected LWP. */
  476         l = curlwp;
  477         lwp_lock(l);
  478         l->l_estcpu += t->l_estcpu;
  479         lwp_unlock(l);
  480 }
  481 
  482 void
  483 sched_oncpu(lwp_t *l)
  484 {
  485 
  486 }
  487 
  488 void
  489 sched_newts(lwp_t *l)
  490 {
  491 
  492 }
  493 
  494 /*
  495  * Sysctl nodes and initialization.
  496  */
  497 
  498 static int
  499 sysctl_sched_rtts(SYSCTLFN_ARGS)
  500 {
  501         struct sysctlnode node;
  502         int rttsms = hztoms(rrticks);
  503 
  504         node = *rnode;
  505         node.sysctl_data = &rttsms;
  506         return sysctl_lookup(SYSCTLFN_CALL(&node));
  507 }
  508 
  509 SYSCTL_SETUP(sysctl_sched_4bsd_setup, "sysctl sched setup")
  510 {
  511         const struct sysctlnode *node = NULL;
  512 
  513         sysctl_createv(clog, 0, NULL, NULL,
  514                 CTLFLAG_PERMANENT,
  515                 CTLTYPE_NODE, "kern", NULL,
  516                 NULL, 0, NULL, 0,
  517                 CTL_KERN, CTL_EOL);
  518         sysctl_createv(clog, 0, NULL, &node,
  519                 CTLFLAG_PERMANENT,
  520                 CTLTYPE_NODE, "sched",
  521                 SYSCTL_DESCR("Scheduler options"),
  522                 NULL, 0, NULL, 0,
  523                 CTL_KERN, CTL_CREATE, CTL_EOL);
  524 
  525         if (node == NULL)
  526                 return;
  527 
  528         rrticks = hz / 10;
  529 
  530         sysctl_createv(NULL, 0, &node, NULL,
  531                 CTLFLAG_PERMANENT,
  532                 CTLTYPE_STRING, "name", NULL,
  533                 NULL, 0, __UNCONST("4.4BSD"), 0,
  534                 CTL_CREATE, CTL_EOL);
  535         sysctl_createv(NULL, 0, &node, NULL,
  536                 CTLFLAG_PERMANENT,
  537                 CTLTYPE_INT, "rtts",
  538                 SYSCTL_DESCR("Round-robin time quantum (in miliseconds)"),
  539                 sysctl_sched_rtts, 0, NULL, 0,
  540                 CTL_CREATE, CTL_EOL);
  541 }

Cache object: ea4bc6d64d2c8bcbb582711c5438168e


[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]


This page is part of the FreeBSD/Linux Linux Kernel Cross-Reference, and was automatically generated using a modified version of the LXR engine.