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 /*-
    2  * Copyright (c) 1982, 1986, 1990, 1991, 1993
    3  *      The Regents of the University of California.  All rights reserved.
    4  * (c) UNIX System Laboratories, Inc.
    5  * All or some portions of this file are derived from material licensed
    6  * to the University of California by American Telephone and Telegraph
    7  * Co. or Unix System Laboratories, Inc. and are reproduced herein with
    8  * the permission of UNIX System Laboratories, Inc.
    9  *
   10  * Redistribution and use in source and binary forms, with or without
   11  * modification, are permitted provided that the following conditions
   12  * are met:
   13  * 1. Redistributions of source code must retain the above copyright
   14  *    notice, this list of conditions and the following disclaimer.
   15  * 2. Redistributions in binary form must reproduce the above copyright
   16  *    notice, this list of conditions and the following disclaimer in the
   17  *    documentation and/or other materials provided with the distribution.
   18  * 4. Neither the name of the University nor the names of its contributors
   19  *    may be used to endorse or promote products derived from this software
   20  *    without specific prior written permission.
   21  *
   22  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
   23  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
   24  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
   25  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
   26  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
   27  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
   28  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
   29  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
   30  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
   31  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
   32  * SUCH DAMAGE.
   33  */
   34 
   35 #include <sys/cdefs.h>
   36 __FBSDID("$FreeBSD: src/sys/kern/sched_4bsd.c,v 1.49.2.16 2005/07/03 20:08:04 ups Exp $");
   37 
   38 #define kse td_sched
   39 
   40 #include <sys/param.h>
   41 #include <sys/systm.h>
   42 #include <sys/kernel.h>
   43 #include <sys/ktr.h>
   44 #include <sys/lock.h>
   45 #include <sys/kthread.h>
   46 #include <sys/mutex.h>
   47 #include <sys/proc.h>
   48 #include <sys/resourcevar.h>
   49 #include <sys/sched.h>
   50 #include <sys/smp.h>
   51 #include <sys/sysctl.h>
   52 #include <sys/sx.h>
   53 #include <machine/smp.h>
   54 
   55 /*
   56  * INVERSE_ESTCPU_WEIGHT is only suitable for statclock() frequencies in
   57  * the range 100-256 Hz (approximately).
   58  */
   59 #define ESTCPULIM(e) \
   60     min((e), INVERSE_ESTCPU_WEIGHT * (NICE_WEIGHT * (PRIO_MAX - PRIO_MIN) - \
   61     RQ_PPQ) + INVERSE_ESTCPU_WEIGHT - 1)
   62 #ifdef SMP
   63 #define INVERSE_ESTCPU_WEIGHT   (8 * smp_cpus)
   64 #else
   65 #define INVERSE_ESTCPU_WEIGHT   8       /* 1 / (priorities per estcpu level). */
   66 #endif
   67 #define NICE_WEIGHT             1       /* Priorities per nice level. */
   68 
   69 /*
   70  * The schedulable entity that can be given a context to run.
   71  * A process may have several of these. Probably one per processor
   72  * but posibly a few more. In this universe they are grouped
   73  * with a KSEG that contains the priority and niceness
   74  * for the group.
   75  */
   76 struct kse {
   77         TAILQ_ENTRY(kse) ke_kglist;     /* (*) Queue of KSEs in ke_ksegrp. */
   78         TAILQ_ENTRY(kse) ke_kgrlist;    /* (*) Queue of KSEs in this state. */
   79         TAILQ_ENTRY(kse) ke_procq;      /* (j/z) Run queue. */
   80         struct thread   *ke_thread;     /* (*) Active associated thread. */
   81         fixpt_t         ke_pctcpu;      /* (j) %cpu during p_swtime. */
   82         char            ke_rqindex;     /* (j) Run queue index. */
   83         enum {
   84                 KES_THREAD = 0x0,       /* slaved to thread state */
   85                 KES_ONRUNQ
   86         } ke_state;                     /* (j) KSE status. */
   87         int             ke_cpticks;     /* (j) Ticks of cpu time. */
   88         struct runq     *ke_runq;       /* runq the kse is currently on */
   89 };
   90 
   91 #define ke_proc         ke_thread->td_proc
   92 #define ke_ksegrp       ke_thread->td_ksegrp
   93 
   94 #define td_kse td_sched
   95 
   96 /* flags kept in td_flags */
   97 #define TDF_DIDRUN      TDF_SCHED0      /* KSE actually ran. */
   98 #define TDF_EXIT        TDF_SCHED1      /* KSE is being killed. */
   99 #define TDF_BOUND       TDF_SCHED2
  100 
  101 #define ke_flags        ke_thread->td_flags
  102 #define KEF_DIDRUN      TDF_DIDRUN /* KSE actually ran. */
  103 #define KEF_EXIT        TDF_EXIT /* KSE is being killed. */
  104 #define KEF_BOUND       TDF_BOUND /* stuck to one CPU */
  105 
  106 #define SKE_RUNQ_PCPU(ke)                                               \
  107     ((ke)->ke_runq != 0 && (ke)->ke_runq != &runq)
  108 
  109 struct kg_sched {
  110         struct thread   *skg_last_assigned; /* (j) Last thread assigned to */
  111                                            /* the system scheduler. */
  112         int     skg_avail_opennings;    /* (j) Num KSEs requested in group. */
  113         int     skg_concurrency;        /* (j) Num KSEs requested in group. */
  114         int     skg_runq_kses;          /* (j) Num KSEs on runq. */
  115 };
  116 #define kg_last_assigned        kg_sched->skg_last_assigned
  117 #define kg_avail_opennings      kg_sched->skg_avail_opennings
  118 #define kg_concurrency          kg_sched->skg_concurrency
  119 #define kg_runq_kses            kg_sched->skg_runq_kses
  120 
  121 #define SLOT_RELEASE(kg)                                                \
  122 do {                                                                    \
  123         kg->kg_avail_opennings++;                                       \
  124         CTR3(KTR_RUNQ, "kg %p(%d) Slot released (->%d)",                \
  125         kg,                                                             \
  126         kg->kg_concurrency,                                             \
  127          kg->kg_avail_opennings);                                       \
  128 /*      KASSERT((kg->kg_avail_opennings <= kg->kg_concurrency),         \
  129             ("slots out of whack"));*/                                  \
  130 } while (0)
  131 
  132 #define SLOT_USE(kg)                                                    \
  133 do {                                                                    \
  134         kg->kg_avail_opennings--;                                       \
  135         CTR3(KTR_RUNQ, "kg %p(%d) Slot used (->%d)",                    \
  136         kg,                                                             \
  137         kg->kg_concurrency,                                             \
  138          kg->kg_avail_opennings);                                       \
  139 /*      KASSERT((kg->kg_avail_opennings >= 0),                          \
  140             ("slots out of whack"));*/                                  \
  141 } while (0)
  142 
  143 /*
  144  * KSE_CAN_MIGRATE macro returns true if the kse can migrate between
  145  * cpus.
  146  */
  147 #define KSE_CAN_MIGRATE(ke)                                             \
  148     ((ke)->ke_thread->td_pinned == 0 && ((ke)->ke_flags & KEF_BOUND) == 0)
  149 
  150 static struct kse kse0;
  151 static struct kg_sched kg_sched0;
  152 
  153 static int      sched_tdcnt;    /* Total runnable threads in the system. */
  154 static int      sched_quantum;  /* Roundrobin scheduling quantum in ticks. */
  155 #define SCHED_QUANTUM   (hz / 10)       /* Default sched quantum */
  156 
  157 static struct callout roundrobin_callout;
  158 
  159 static void     slot_fill(struct ksegrp *kg);
  160 static struct kse *sched_choose(void);          /* XXX Should be thread * */
  161 
  162 static void     setup_runqs(void);
  163 static void     roundrobin(void *arg);
  164 static void     schedcpu(void);
  165 static void     schedcpu_thread(void);
  166 static void     sched_setup(void *dummy);
  167 static void     maybe_resched(struct thread *td);
  168 static void     updatepri(struct ksegrp *kg);
  169 static void     resetpriority(struct ksegrp *kg);
  170 #ifdef SMP
  171 static int      forward_wakeup(int  cpunum);
  172 #endif
  173 
  174 static struct kproc_desc sched_kp = {
  175         "schedcpu",
  176         schedcpu_thread,
  177         NULL
  178 };
  179 SYSINIT(schedcpu, SI_SUB_RUN_SCHEDULER, SI_ORDER_FIRST, kproc_start, &sched_kp)
  180 SYSINIT(sched_setup, SI_SUB_RUN_QUEUE, SI_ORDER_FIRST, sched_setup, NULL)
  181 
  182 /*
  183  * Global run queue.
  184  */
  185 static struct runq runq;
  186 
  187 #ifdef SMP
  188 /*
  189  * Per-CPU run queues
  190  */
  191 static struct runq runq_pcpu[MAXCPU];
  192 #endif
  193 
  194 static void
  195 setup_runqs(void)
  196 {
  197 #ifdef SMP
  198         int i;
  199 
  200         for (i = 0; i < MAXCPU; ++i)
  201                 runq_init(&runq_pcpu[i]);
  202 #endif
  203 
  204         runq_init(&runq);
  205 }
  206 
  207 static int
  208 sysctl_kern_quantum(SYSCTL_HANDLER_ARGS)
  209 {
  210         int error, new_val;
  211 
  212         new_val = sched_quantum * tick;
  213         error = sysctl_handle_int(oidp, &new_val, 0, req);
  214         if (error != 0 || req->newptr == NULL)
  215                 return (error);
  216         if (new_val < tick)
  217                 return (EINVAL);
  218         sched_quantum = new_val / tick;
  219         hogticks = 2 * sched_quantum;
  220         return (0);
  221 }
  222 
  223 SYSCTL_NODE(_kern, OID_AUTO, sched, CTLFLAG_RD, 0, "Scheduler");
  224 
  225 SYSCTL_STRING(_kern_sched, OID_AUTO, name, CTLFLAG_RD, "4BSD", 0,
  226     "Scheduler name");
  227 
  228 SYSCTL_PROC(_kern_sched, OID_AUTO, quantum, CTLTYPE_INT | CTLFLAG_RW,
  229     0, sizeof sched_quantum, sysctl_kern_quantum, "I",
  230     "Roundrobin scheduling quantum in microseconds");
  231 
  232 #ifdef SMP
  233 /* Enable forwarding of wakeups to all other cpus */
  234 SYSCTL_NODE(_kern_sched, OID_AUTO, ipiwakeup, CTLFLAG_RD, NULL, "Kernel SMP");
  235 
  236 static int forward_wakeup_enabled = 1;
  237 SYSCTL_INT(_kern_sched_ipiwakeup, OID_AUTO, enabled, CTLFLAG_RW,
  238            &forward_wakeup_enabled, 0,
  239            "Forwarding of wakeup to idle CPUs");
  240 
  241 static int forward_wakeups_requested = 0;
  242 SYSCTL_INT(_kern_sched_ipiwakeup, OID_AUTO, requested, CTLFLAG_RD,
  243            &forward_wakeups_requested, 0,
  244            "Requests for Forwarding of wakeup to idle CPUs");
  245 
  246 static int forward_wakeups_delivered = 0;
  247 SYSCTL_INT(_kern_sched_ipiwakeup, OID_AUTO, delivered, CTLFLAG_RD,
  248            &forward_wakeups_delivered, 0,
  249            "Completed Forwarding of wakeup to idle CPUs");
  250 
  251 static int forward_wakeup_use_mask = 1;
  252 SYSCTL_INT(_kern_sched_ipiwakeup, OID_AUTO, usemask, CTLFLAG_RW,
  253            &forward_wakeup_use_mask, 0,
  254            "Use the mask of idle cpus");
  255 
  256 static int forward_wakeup_use_loop = 0;
  257 SYSCTL_INT(_kern_sched_ipiwakeup, OID_AUTO, useloop, CTLFLAG_RW,
  258            &forward_wakeup_use_loop, 0,
  259            "Use a loop to find idle cpus");
  260 
  261 static int forward_wakeup_use_single = 0;
  262 SYSCTL_INT(_kern_sched_ipiwakeup, OID_AUTO, onecpu, CTLFLAG_RW,
  263            &forward_wakeup_use_single, 0,
  264            "Only signal one idle cpu");
  265 
  266 static int forward_wakeup_use_htt = 0;
  267 SYSCTL_INT(_kern_sched_ipiwakeup, OID_AUTO, htt2, CTLFLAG_RW,
  268            &forward_wakeup_use_htt, 0,
  269            "account for htt");
  270 
  271 #endif
  272 static int sched_followon = 0;
  273 SYSCTL_INT(_kern_sched, OID_AUTO, followon, CTLFLAG_RW,
  274            &sched_followon, 0,
  275            "allow threads to share a quantum");
  276 
  277 static int sched_pfollowons = 0;
  278 SYSCTL_INT(_kern_sched, OID_AUTO, pfollowons, CTLFLAG_RD,
  279            &sched_pfollowons, 0,
  280            "number of followons done to a different ksegrp");
  281 
  282 static int sched_kgfollowons = 0;
  283 static __inline void
  284 sched_load_add(void)
  285 {
  286         sched_tdcnt++;
  287         CTR1(KTR_SCHED, "global load: %d", sched_tdcnt);
  288 }
  289 
  290 static __inline void
  291 sched_load_rem(void)
  292 {
  293         sched_tdcnt--;
  294         CTR1(KTR_SCHED, "global load: %d", sched_tdcnt);
  295 }
  296 SYSCTL_INT(_kern_sched, OID_AUTO, kgfollowons, CTLFLAG_RD,
  297            &sched_kgfollowons, 0,
  298            "number of followons done in a ksegrp");
  299 
  300 /*
  301  * Arrange to reschedule if necessary, taking the priorities and
  302  * schedulers into account.
  303  */
  304 static void
  305 maybe_resched(struct thread *td)
  306 {
  307 
  308         mtx_assert(&sched_lock, MA_OWNED);
  309         if (td->td_priority < curthread->td_priority)
  310                 curthread->td_flags |= TDF_NEEDRESCHED;
  311 }
  312 
  313 /*
  314  * Force switch among equal priority processes every 100ms.
  315  * We don't actually need to force a context switch of the current process.
  316  * The act of firing the event triggers a context switch to softclock() and
  317  * then switching back out again which is equivalent to a preemption, thus
  318  * no further work is needed on the local CPU.
  319  */
  320 /* ARGSUSED */
  321 static void
  322 roundrobin(void *arg)
  323 {
  324 
  325 #ifdef SMP
  326         mtx_lock_spin(&sched_lock);
  327         forward_roundrobin();
  328         mtx_unlock_spin(&sched_lock);
  329 #endif
  330 
  331         callout_reset(&roundrobin_callout, sched_quantum, roundrobin, NULL);
  332 }
  333 
  334 /*
  335  * Constants for digital decay and forget:
  336  *      90% of (kg_estcpu) usage in 5 * loadav time
  337  *      95% of (ke_pctcpu) usage in 60 seconds (load insensitive)
  338  *          Note that, as ps(1) mentions, this can let percentages
  339  *          total over 100% (I've seen 137.9% for 3 processes).
  340  *
  341  * Note that schedclock() updates kg_estcpu and p_cpticks asynchronously.
  342  *
  343  * We wish to decay away 90% of kg_estcpu in (5 * loadavg) seconds.
  344  * That is, the system wants to compute a value of decay such
  345  * that the following for loop:
  346  *      for (i = 0; i < (5 * loadavg); i++)
  347  *              kg_estcpu *= decay;
  348  * will compute
  349  *      kg_estcpu *= 0.1;
  350  * for all values of loadavg:
  351  *
  352  * Mathematically this loop can be expressed by saying:
  353  *      decay ** (5 * loadavg) ~= .1
  354  *
  355  * The system computes decay as:
  356  *      decay = (2 * loadavg) / (2 * loadavg + 1)
  357  *
  358  * We wish to prove that the system's computation of decay
  359  * will always fulfill the equation:
  360  *      decay ** (5 * loadavg) ~= .1
  361  *
  362  * If we compute b as:
  363  *      b = 2 * loadavg
  364  * then
  365  *      decay = b / (b + 1)
  366  *
  367  * We now need to prove two things:
  368  *      1) Given factor ** (5 * loadavg) ~= .1, prove factor == b/(b+1)
  369  *      2) Given b/(b+1) ** power ~= .1, prove power == (5 * loadavg)
  370  *
  371  * Facts:
  372  *         For x close to zero, exp(x) =~ 1 + x, since
  373  *              exp(x) = 0! + x**1/1! + x**2/2! + ... .
  374  *              therefore exp(-1/b) =~ 1 - (1/b) = (b-1)/b.
  375  *         For x close to zero, ln(1+x) =~ x, since
  376  *              ln(1+x) = x - x**2/2 + x**3/3 - ...     -1 < x < 1
  377  *              therefore ln(b/(b+1)) = ln(1 - 1/(b+1)) =~ -1/(b+1).
  378  *         ln(.1) =~ -2.30
  379  *
  380  * Proof of (1):
  381  *    Solve (factor)**(power) =~ .1 given power (5*loadav):
  382  *      solving for factor,
  383  *      ln(factor) =~ (-2.30/5*loadav), or
  384  *      factor =~ exp(-1/((5/2.30)*loadav)) =~ exp(-1/(2*loadav)) =
  385  *          exp(-1/b) =~ (b-1)/b =~ b/(b+1).                    QED
  386  *
  387  * Proof of (2):
  388  *    Solve (factor)**(power) =~ .1 given factor == (b/(b+1)):
  389  *      solving for power,
  390  *      power*ln(b/(b+1)) =~ -2.30, or
  391  *      power =~ 2.3 * (b + 1) = 4.6*loadav + 2.3 =~ 5*loadav.  QED
  392  *
  393  * Actual power values for the implemented algorithm are as follows:
  394  *      loadav: 1       2       3       4
  395  *      power:  5.68    10.32   14.94   19.55
  396  */
  397 
  398 /* calculations for digital decay to forget 90% of usage in 5*loadav sec */
  399 #define loadfactor(loadav)      (2 * (loadav))
  400 #define decay_cpu(loadfac, cpu) (((loadfac) * (cpu)) / ((loadfac) + FSCALE))
  401 
  402 /* decay 95% of `ke_pctcpu' in 60 seconds; see CCPU_SHIFT before changing */
  403 static fixpt_t  ccpu = 0.95122942450071400909 * FSCALE; /* exp(-1/20) */
  404 SYSCTL_INT(_kern, OID_AUTO, ccpu, CTLFLAG_RD, &ccpu, 0, "");
  405 
  406 /*
  407  * If `ccpu' is not equal to `exp(-1/20)' and you still want to use the
  408  * faster/more-accurate formula, you'll have to estimate CCPU_SHIFT below
  409  * and possibly adjust FSHIFT in "param.h" so that (FSHIFT >= CCPU_SHIFT).
  410  *
  411  * To estimate CCPU_SHIFT for exp(-1/20), the following formula was used:
  412  *      1 - exp(-1/20) ~= 0.0487 ~= 0.0488 == 1 (fixed pt, *11* bits).
  413  *
  414  * If you don't want to bother with the faster/more-accurate formula, you
  415  * can set CCPU_SHIFT to (FSHIFT + 1) which will use a slower/less-accurate
  416  * (more general) method of calculating the %age of CPU used by a process.
  417  */
  418 #define CCPU_SHIFT      11
  419 
  420 /*
  421  * Recompute process priorities, every hz ticks.
  422  * MP-safe, called without the Giant mutex.
  423  */
  424 /* ARGSUSED */
  425 static void
  426 schedcpu(void)
  427 {
  428         register fixpt_t loadfac = loadfactor(averunnable.ldavg[0]);
  429         struct thread *td;
  430         struct proc *p;
  431         struct kse *ke;
  432         struct ksegrp *kg;
  433         int awake, realstathz;
  434 
  435         realstathz = stathz ? stathz : hz;
  436         sx_slock(&allproc_lock);
  437         FOREACH_PROC_IN_SYSTEM(p) {
  438                 /*
  439                  * Prevent state changes and protect run queue.
  440                  */
  441                 mtx_lock_spin(&sched_lock);
  442                 /*
  443                  * Increment time in/out of memory.  We ignore overflow; with
  444                  * 16-bit int's (remember them?) overflow takes 45 days.
  445                  */
  446                 p->p_swtime++;
  447                 FOREACH_KSEGRP_IN_PROC(p, kg) { 
  448                         awake = 0;
  449                         FOREACH_THREAD_IN_GROUP(kg, td) {
  450                                 ke = td->td_kse;
  451                                 /*
  452                                  * Increment sleep time (if sleeping).  We
  453                                  * ignore overflow, as above.
  454                                  */
  455                                 /*
  456                                  * The kse slptimes are not touched in wakeup
  457                                  * because the thread may not HAVE a KSE.
  458                                  */
  459                                 if (ke->ke_state == KES_ONRUNQ) {
  460                                         awake = 1;
  461                                         ke->ke_flags &= ~KEF_DIDRUN;
  462                                 } else if ((ke->ke_state == KES_THREAD) &&
  463                                     (TD_IS_RUNNING(td))) {
  464                                         awake = 1;
  465                                         /* Do not clear KEF_DIDRUN */
  466                                 } else if (ke->ke_flags & KEF_DIDRUN) {
  467                                         awake = 1;
  468                                         ke->ke_flags &= ~KEF_DIDRUN;
  469                                 }
  470 
  471                                 /*
  472                                  * ke_pctcpu is only for ps and ttyinfo().
  473                                  * Do it per kse, and add them up at the end?
  474                                  * XXXKSE
  475                                  */
  476                                 ke->ke_pctcpu = (ke->ke_pctcpu * ccpu) >>
  477                                     FSHIFT;
  478                                 /*
  479                                  * If the kse has been idle the entire second,
  480                                  * stop recalculating its priority until
  481                                  * it wakes up.
  482                                  */
  483                                 if (ke->ke_cpticks == 0)
  484                                         continue;
  485 #if     (FSHIFT >= CCPU_SHIFT)
  486                                 ke->ke_pctcpu += (realstathz == 100)
  487                                     ? ((fixpt_t) ke->ke_cpticks) <<
  488                                     (FSHIFT - CCPU_SHIFT) :
  489                                     100 * (((fixpt_t) ke->ke_cpticks)
  490                                     << (FSHIFT - CCPU_SHIFT)) / realstathz;
  491 #else
  492                                 ke->ke_pctcpu += ((FSCALE - ccpu) *
  493                                     (ke->ke_cpticks *
  494                                     FSCALE / realstathz)) >> FSHIFT;
  495 #endif
  496                                 ke->ke_cpticks = 0;
  497                         } /* end of kse loop */
  498                         /* 
  499                          * If there are ANY running threads in this KSEGRP,
  500                          * then don't count it as sleeping.
  501                          */
  502                         if (awake) {
  503                                 if (kg->kg_slptime > 1) {
  504                                         /*
  505                                          * In an ideal world, this should not
  506                                          * happen, because whoever woke us
  507                                          * up from the long sleep should have
  508                                          * unwound the slptime and reset our
  509                                          * priority before we run at the stale
  510                                          * priority.  Should KASSERT at some
  511                                          * point when all the cases are fixed.
  512                                          */
  513                                         updatepri(kg);
  514                                 }
  515                                 kg->kg_slptime = 0;
  516                         } else
  517                                 kg->kg_slptime++;
  518                         if (kg->kg_slptime > 1)
  519                                 continue;
  520                         kg->kg_estcpu = decay_cpu(loadfac, kg->kg_estcpu);
  521                         resetpriority(kg);
  522                         FOREACH_THREAD_IN_GROUP(kg, td) {
  523                                 if (td->td_priority >= PUSER) {
  524                                         sched_prio(td, kg->kg_user_pri);
  525                                 }
  526                         }
  527                 } /* end of ksegrp loop */
  528                 mtx_unlock_spin(&sched_lock);
  529         } /* end of process loop */
  530         sx_sunlock(&allproc_lock);
  531 }
  532 
  533 /*
  534  * Main loop for a kthread that executes schedcpu once a second.
  535  */
  536 static void
  537 schedcpu_thread(void)
  538 {
  539         int nowake;
  540 
  541         for (;;) {
  542                 schedcpu();
  543                 tsleep(&nowake, curthread->td_priority, "-", hz);
  544         }
  545 }
  546 
  547 /*
  548  * Recalculate the priority of a process after it has slept for a while.
  549  * For all load averages >= 1 and max kg_estcpu of 255, sleeping for at
  550  * least six times the loadfactor will decay kg_estcpu to zero.
  551  */
  552 static void
  553 updatepri(struct ksegrp *kg)
  554 {
  555         register fixpt_t loadfac;
  556         register unsigned int newcpu;
  557 
  558         loadfac = loadfactor(averunnable.ldavg[0]);
  559         if (kg->kg_slptime > 5 * loadfac)
  560                 kg->kg_estcpu = 0;
  561         else {
  562                 newcpu = kg->kg_estcpu;
  563                 kg->kg_slptime--;       /* was incremented in schedcpu() */
  564                 while (newcpu && --kg->kg_slptime)
  565                         newcpu = decay_cpu(loadfac, newcpu);
  566                 kg->kg_estcpu = newcpu;
  567         }
  568         resetpriority(kg);
  569 }
  570 
  571 /*
  572  * Compute the priority of a process when running in user mode.
  573  * Arrange to reschedule if the resulting priority is better
  574  * than that of the current process.
  575  */
  576 static void
  577 resetpriority(struct ksegrp *kg)
  578 {
  579         register unsigned int newpriority;
  580         struct thread *td;
  581 
  582         if (kg->kg_pri_class == PRI_TIMESHARE) {
  583                 newpriority = PUSER + kg->kg_estcpu / INVERSE_ESTCPU_WEIGHT +
  584                     NICE_WEIGHT * (kg->kg_proc->p_nice - PRIO_MIN);
  585                 newpriority = min(max(newpriority, PRI_MIN_TIMESHARE),
  586                     PRI_MAX_TIMESHARE);
  587                 kg->kg_user_pri = newpriority;
  588         }
  589         FOREACH_THREAD_IN_GROUP(kg, td) {
  590                 maybe_resched(td);                      /* XXXKSE silly */
  591         }
  592 }
  593 
  594 /* ARGSUSED */
  595 static void
  596 sched_setup(void *dummy)
  597 {
  598         setup_runqs();
  599 
  600         if (sched_quantum == 0)
  601                 sched_quantum = SCHED_QUANTUM;
  602         hogticks = 2 * sched_quantum;
  603 
  604         callout_init(&roundrobin_callout, CALLOUT_MPSAFE);
  605 
  606         /* Kick off timeout driven events by calling first time. */
  607         roundrobin(NULL);
  608 
  609         /* Account for thread0. */
  610         sched_load_add();
  611 }
  612 
  613 /* External interfaces start here */
  614 /*
  615  * Very early in the boot some setup of scheduler-specific
  616  * parts of proc0 and of soem scheduler resources needs to be done.
  617  * Called from:
  618  *  proc0_init()
  619  */
  620 void
  621 schedinit(void)
  622 {
  623         /*
  624          * Set up the scheduler specific parts of proc0.
  625          */
  626         proc0.p_sched = NULL; /* XXX */
  627         ksegrp0.kg_sched = &kg_sched0;
  628         thread0.td_sched = &kse0;
  629         kse0.ke_thread = &thread0;
  630         kse0.ke_state = KES_THREAD;
  631         kg_sched0.skg_concurrency = 1;
  632         kg_sched0.skg_avail_opennings = 0; /* we are already running */
  633 }
  634 
  635 int
  636 sched_runnable(void)
  637 {
  638 #ifdef SMP
  639         return runq_check(&runq) + runq_check(&runq_pcpu[PCPU_GET(cpuid)]);
  640 #else
  641         return runq_check(&runq);
  642 #endif
  643 }
  644 
  645 int 
  646 sched_rr_interval(void)
  647 {
  648         if (sched_quantum == 0)
  649                 sched_quantum = SCHED_QUANTUM;
  650         return (sched_quantum);
  651 }
  652 
  653 /*
  654  * We adjust the priority of the current process.  The priority of
  655  * a process gets worse as it accumulates CPU time.  The cpu usage
  656  * estimator (kg_estcpu) is increased here.  resetpriority() will
  657  * compute a different priority each time kg_estcpu increases by
  658  * INVERSE_ESTCPU_WEIGHT
  659  * (until MAXPRI is reached).  The cpu usage estimator ramps up
  660  * quite quickly when the process is running (linearly), and decays
  661  * away exponentially, at a rate which is proportionally slower when
  662  * the system is busy.  The basic principle is that the system will
  663  * 90% forget that the process used a lot of CPU time in 5 * loadav
  664  * seconds.  This causes the system to favor processes which haven't
  665  * run much recently, and to round-robin among other processes.
  666  */
  667 void
  668 sched_clock(struct thread *td)
  669 {
  670         struct ksegrp *kg;
  671         struct kse *ke;
  672 
  673         mtx_assert(&sched_lock, MA_OWNED);
  674         kg = td->td_ksegrp;
  675         ke = td->td_kse;
  676 
  677         ke->ke_cpticks++;
  678         kg->kg_estcpu = ESTCPULIM(kg->kg_estcpu + 1);
  679         if ((kg->kg_estcpu % INVERSE_ESTCPU_WEIGHT) == 0) {
  680                 resetpriority(kg);
  681                 if (td->td_priority >= PUSER)
  682                         td->td_priority = kg->kg_user_pri;
  683         }
  684 }
  685 
  686 /*
  687  * charge childs scheduling cpu usage to parent.
  688  *
  689  * XXXKSE assume only one thread & kse & ksegrp keep estcpu in each ksegrp.
  690  * Charge it to the ksegrp that did the wait since process estcpu is sum of
  691  * all ksegrps, this is strictly as expected.  Assume that the child process
  692  * aggregated all the estcpu into the 'built-in' ksegrp.
  693  */
  694 void
  695 sched_exit(struct proc *p, struct thread *td)
  696 {
  697         sched_exit_ksegrp(FIRST_KSEGRP_IN_PROC(p), td);
  698         sched_exit_thread(FIRST_THREAD_IN_PROC(p), td);
  699 }
  700 
  701 void
  702 sched_exit_ksegrp(struct ksegrp *kg, struct thread *childtd)
  703 {
  704 
  705         mtx_assert(&sched_lock, MA_OWNED);
  706         kg->kg_estcpu = ESTCPULIM(kg->kg_estcpu + childtd->td_ksegrp->kg_estcpu);
  707 }
  708 
  709 void
  710 sched_exit_thread(struct thread *td, struct thread *child)
  711 {
  712         CTR3(KTR_SCHED, "sched_exit_thread: %p(%s) prio %d",
  713             child, child->td_proc->p_comm, child->td_priority);
  714         if ((child->td_proc->p_flag & P_NOLOAD) == 0)
  715                 sched_load_rem();
  716 }
  717 
  718 void
  719 sched_fork(struct thread *td, struct thread *childtd)
  720 {
  721         sched_fork_ksegrp(td, childtd->td_ksegrp);
  722         sched_fork_thread(td, childtd);
  723 }
  724 
  725 void
  726 sched_fork_ksegrp(struct thread *td, struct ksegrp *child)
  727 {
  728         mtx_assert(&sched_lock, MA_OWNED);
  729         child->kg_estcpu = td->td_ksegrp->kg_estcpu;
  730 }
  731 
  732 void
  733 sched_fork_thread(struct thread *td, struct thread *childtd)
  734 {
  735         sched_newthread(childtd);
  736 }
  737 
  738 void
  739 sched_nice(struct proc *p, int nice)
  740 {
  741         struct ksegrp *kg;
  742 
  743         PROC_LOCK_ASSERT(p, MA_OWNED);
  744         mtx_assert(&sched_lock, MA_OWNED);
  745         p->p_nice = nice;
  746         FOREACH_KSEGRP_IN_PROC(p, kg) {
  747                 resetpriority(kg);
  748         }
  749 }
  750 
  751 void
  752 sched_class(struct ksegrp *kg, int class)
  753 {
  754         mtx_assert(&sched_lock, MA_OWNED);
  755         kg->kg_pri_class = class;
  756 }
  757 
  758 /*
  759  * Adjust the priority of a thread.
  760  * This may include moving the thread within the KSEGRP,
  761  * changing the assignment of a kse to the thread,
  762  * and moving a KSE in the system run queue.
  763  */
  764 void
  765 sched_prio(struct thread *td, u_char prio)
  766 {
  767         CTR6(KTR_SCHED, "sched_prio: %p(%s) prio %d newprio %d by %p(%s)",
  768             td, td->td_proc->p_comm, td->td_priority, prio, curthread, 
  769             curthread->td_proc->p_comm);
  770 
  771         mtx_assert(&sched_lock, MA_OWNED);
  772         if (TD_ON_RUNQ(td)) {
  773                 adjustrunqueue(td, prio);
  774         } else {
  775                 td->td_priority = prio;
  776         }
  777 }
  778 
  779 void
  780 sched_sleep(struct thread *td)
  781 {
  782 
  783         mtx_assert(&sched_lock, MA_OWNED);
  784         td->td_ksegrp->kg_slptime = 0;
  785         td->td_base_pri = td->td_priority;
  786 }
  787 
  788 static void remrunqueue(struct thread *td);
  789 
  790 void
  791 sched_switch(struct thread *td, struct thread *newtd, int flags)
  792 {
  793         struct kse *ke;
  794         struct ksegrp *kg;
  795         struct proc *p;
  796 
  797         ke = td->td_kse;
  798         p = td->td_proc;
  799 
  800         mtx_assert(&sched_lock, MA_OWNED);
  801 
  802         if ((p->p_flag & P_NOLOAD) == 0)
  803                 sched_load_rem();
  804         /* 
  805          * We are volunteering to switch out so we get to nominate
  806          * a successor for the rest of our quantum
  807          * First try another thread in our ksegrp, and then look for 
  808          * other ksegrps in our process.
  809          */
  810         if (sched_followon &&
  811             (p->p_flag & P_HADTHREADS) &&
  812             (flags & SW_VOL) &&
  813             newtd == NULL) {
  814                 /* lets schedule another thread from this process */
  815                  kg = td->td_ksegrp;
  816                  if ((newtd = TAILQ_FIRST(&kg->kg_runq))) {
  817                         remrunqueue(newtd);
  818                         sched_kgfollowons++;
  819                  } else {
  820                         FOREACH_KSEGRP_IN_PROC(p, kg) {
  821                                 if ((newtd = TAILQ_FIRST(&kg->kg_runq))) {
  822                                         sched_pfollowons++;
  823                                         remrunqueue(newtd);
  824                                         break;
  825                                 }
  826                         }
  827                 }
  828         }
  829 
  830         td->td_lastcpu = td->td_oncpu;
  831         td->td_flags &= ~TDF_NEEDRESCHED;
  832         td->td_pflags &= ~TDP_OWEPREEMPT;
  833         td->td_oncpu = NOCPU;
  834         /*
  835          * At the last moment, if this thread is still marked RUNNING,
  836          * then put it back on the run queue as it has not been suspended
  837          * or stopped or any thing else similar.  We never put the idle
  838          * threads on the run queue, however.
  839          */
  840         if (td == PCPU_GET(idlethread))
  841                 TD_SET_CAN_RUN(td);
  842         else {
  843                 SLOT_RELEASE(td->td_ksegrp);
  844                 if (TD_IS_RUNNING(td)) {
  845                         /* Put us back on the run queue (kse and all). */
  846                         setrunqueue(td, (flags & SW_PREEMPT) ?
  847                             SRQ_OURSELF|SRQ_YIELDING|SRQ_PREEMPTED :
  848                             SRQ_OURSELF|SRQ_YIELDING);
  849                 } else if (p->p_flag & P_HADTHREADS) {
  850                         /*
  851                          * We will not be on the run queue. So we must be
  852                          * sleeping or similar. As it's available,
  853                          * someone else can use the KSE if they need it.
  854                          * It's NOT available if we are about to need it
  855                          */
  856                         if (newtd == NULL || newtd->td_ksegrp != td->td_ksegrp)
  857                                 slot_fill(td->td_ksegrp);
  858                 }
  859         }
  860         if (newtd) {
  861                 /* 
  862                  * The thread we are about to run needs to be counted
  863                  * as if it had been added to the run queue and selected.
  864                  * It came from:
  865                  * * A preemption
  866                  * * An upcall 
  867                  * * A followon
  868                  */
  869                 KASSERT((newtd->td_inhibitors == 0),
  870                         ("trying to run inhibitted thread"));
  871                 SLOT_USE(newtd->td_ksegrp);
  872                 newtd->td_kse->ke_flags |= KEF_DIDRUN;
  873                 TD_SET_RUNNING(newtd);
  874                 if ((newtd->td_proc->p_flag & P_NOLOAD) == 0)
  875                         sched_load_add();
  876         } else {
  877                 newtd = choosethread();
  878         }
  879 
  880         if (td != newtd)
  881                 cpu_switch(td, newtd);
  882         sched_lock.mtx_lock = (uintptr_t)td;
  883         td->td_oncpu = PCPU_GET(cpuid);
  884 }
  885 
  886 void
  887 sched_wakeup(struct thread *td)
  888 {
  889         struct ksegrp *kg;
  890 
  891         mtx_assert(&sched_lock, MA_OWNED);
  892         kg = td->td_ksegrp;
  893         if (kg->kg_slptime > 1)
  894                 updatepri(kg);
  895         kg->kg_slptime = 0;
  896         setrunqueue(td, SRQ_BORING);
  897 }
  898 
  899 #ifdef SMP
  900 /* enable HTT_2 if you have a 2-way HTT cpu.*/
  901 static int
  902 forward_wakeup(int  cpunum)
  903 {
  904         cpumask_t map, me, dontuse;
  905         cpumask_t map2;
  906         struct pcpu *pc;
  907         cpumask_t id, map3;
  908 
  909         mtx_assert(&sched_lock, MA_OWNED);
  910 
  911         CTR0(KTR_RUNQ, "forward_wakeup()");
  912 
  913         if ((!forward_wakeup_enabled) ||
  914              (forward_wakeup_use_mask == 0 && forward_wakeup_use_loop == 0))
  915                 return (0);
  916         if (!smp_started || cold || panicstr)
  917                 return (0);
  918 
  919         forward_wakeups_requested++;
  920 
  921 /*
  922  * check the idle mask we received against what we calculated before
  923  * in the old version.
  924  */
  925         me = PCPU_GET(cpumask);
  926         /* 
  927          * don't bother if we should be doing it ourself..
  928          */
  929         if ((me & idle_cpus_mask) && (cpunum == NOCPU || me == (1 << cpunum)))
  930                 return (0);
  931 
  932         dontuse = me | stopped_cpus | hlt_cpus_mask;
  933         map3 = 0;
  934         if (forward_wakeup_use_loop) {
  935                 SLIST_FOREACH(pc, &cpuhead, pc_allcpu) {
  936                         id = pc->pc_cpumask;
  937                         if ( (id & dontuse) == 0 &&
  938                             pc->pc_curthread == pc->pc_idlethread) {
  939                                 map3 |= id;
  940                         }
  941                 }
  942         }
  943 
  944         if (forward_wakeup_use_mask) {
  945                 map = 0;
  946                 map = idle_cpus_mask & ~dontuse;
  947 
  948                 /* If they are both on, compare and use loop if different */
  949                 if (forward_wakeup_use_loop) {
  950                         if (map != map3) {
  951                                 printf("map (%02X) != map3 (%02X)\n",
  952                                                 map, map3);
  953                                 map = map3;
  954                         }
  955                 }
  956         } else {
  957                 map = map3;
  958         }
  959         /* If we only allow a specific CPU, then mask off all the others */
  960         if (cpunum != NOCPU) {
  961                 KASSERT((cpunum <= mp_maxcpus),("forward_wakeup: bad cpunum."));
  962                 map &= (1 << cpunum);
  963         } else {
  964                 /* Try choose an idle die. */
  965                 if (forward_wakeup_use_htt) {
  966                         map2 =  (map & (map >> 1)) & 0x5555;
  967                         if (map2) {
  968                                 map = map2;
  969                         }
  970                 }
  971 
  972                 /* set only one bit */ 
  973                 if (forward_wakeup_use_single) {
  974                         map = map & ((~map) + 1);
  975                 }
  976         }
  977         if (map) {
  978                 forward_wakeups_delivered++;
  979                 ipi_selected(map, IPI_AST);
  980                 return (1);
  981         }
  982         if (cpunum == NOCPU)
  983                 printf("forward_wakeup: Idle processor not found\n");
  984         return (0);
  985 }
  986 #endif
  987 
  988 #ifdef SMP
  989 static void kick_other_cpu(int pri,int cpuid);
  990 
  991 static void
  992 kick_other_cpu(int pri,int cpuid)
  993 {       
  994         struct pcpu * pcpu = pcpu_find(cpuid);
  995         int cpri = pcpu->pc_curthread->td_priority;
  996 
  997         if (idle_cpus_mask & pcpu->pc_cpumask) {
  998                 forward_wakeups_delivered++;
  999                 ipi_selected(pcpu->pc_cpumask, IPI_AST);
 1000                 return;
 1001         }
 1002 
 1003         if (pri >= cpri)
 1004                 return;
 1005 
 1006 #if defined(IPI_PREEMPTION) && defined(PREEMPTION)
 1007 #if !defined(FULL_PREEMPTION)
 1008         if (pri <= PRI_MAX_ITHD)
 1009 #endif /* ! FULL_PREEMPTION */
 1010         {
 1011                 ipi_selected(pcpu->pc_cpumask, IPI_PREEMPT);
 1012                 return;
 1013         }
 1014 #endif /* defined(IPI_PREEMPTION) && defined(PREEMPTION) */
 1015 
 1016         pcpu->pc_curthread->td_flags |= TDF_NEEDRESCHED;
 1017         ipi_selected( pcpu->pc_cpumask , IPI_AST);
 1018         return;
 1019 }
 1020 #endif /* SMP */
 1021 
 1022 void
 1023 sched_add(struct thread *td, int flags)
 1024 #ifdef SMP
 1025 {
 1026         struct kse *ke;
 1027         int forwarded = 0;
 1028         int cpu;
 1029         int single_cpu = 0;
 1030 
 1031         ke = td->td_kse;
 1032         mtx_assert(&sched_lock, MA_OWNED);
 1033         KASSERT(ke->ke_state != KES_ONRUNQ,
 1034             ("sched_add: kse %p (%s) already in run queue", ke,
 1035             ke->ke_proc->p_comm));
 1036         KASSERT(ke->ke_proc->p_sflag & PS_INMEM,
 1037             ("sched_add: process swapped out"));
 1038         CTR5(KTR_SCHED, "sched_add: %p(%s) prio %d by %p(%s)",
 1039             td, td->td_proc->p_comm, td->td_priority, curthread,
 1040             curthread->td_proc->p_comm);
 1041 
 1042 
 1043         if (td->td_pinned != 0) {
 1044                 cpu = td->td_lastcpu;
 1045                 ke->ke_runq = &runq_pcpu[cpu];
 1046                 single_cpu = 1;
 1047                 CTR3(KTR_RUNQ,
 1048                     "sched_add: Put kse:%p(td:%p) on cpu%d runq", ke, td, cpu);
 1049         } else if ((ke)->ke_flags & KEF_BOUND) {
 1050                 /* Find CPU from bound runq */
 1051                 KASSERT(SKE_RUNQ_PCPU(ke),("sched_add: bound kse not on cpu runq"));
 1052                 cpu = ke->ke_runq - &runq_pcpu[0];
 1053                 single_cpu = 1;
 1054                 CTR3(KTR_RUNQ,
 1055                     "sched_add: Put kse:%p(td:%p) on cpu%d runq", ke, td, cpu);
 1056         } else {        
 1057                 CTR2(KTR_RUNQ,
 1058                     "sched_add: adding kse:%p (td:%p) to gbl runq", ke, td);
 1059                 cpu = NOCPU;
 1060                 ke->ke_runq = &runq;
 1061         }
 1062         
 1063         if (single_cpu && (cpu != PCPU_GET(cpuid))) {
 1064                 kick_other_cpu(td->td_priority,cpu);
 1065         } else {
 1066                 
 1067                 if (!single_cpu) {
 1068                         cpumask_t me = PCPU_GET(cpumask);
 1069                         int idle = idle_cpus_mask & me; 
 1070 
 1071                         if (!idle && ((flags & SRQ_INTR) == 0) &&
 1072                             (idle_cpus_mask & ~(hlt_cpus_mask | me)))
 1073                                 forwarded = forward_wakeup(cpu);
 1074                 }
 1075 
 1076                 if (!forwarded) {
 1077                         if ((flags & SRQ_YIELDING) == 0 && maybe_preempt(td))
 1078                                 return;
 1079                         else
 1080                                 maybe_resched(td);
 1081                 }
 1082         }
 1083         
 1084         if ((td->td_proc->p_flag & P_NOLOAD) == 0)
 1085                 sched_load_add();
 1086         SLOT_USE(td->td_ksegrp);
 1087         runq_add(ke->ke_runq, ke, flags);
 1088         ke->ke_state = KES_ONRUNQ;
 1089 }
 1090 #else /* SMP */
 1091 {
 1092         struct kse *ke;
 1093         ke = td->td_kse;
 1094         mtx_assert(&sched_lock, MA_OWNED);
 1095         KASSERT(ke->ke_state != KES_ONRUNQ,
 1096             ("sched_add: kse %p (%s) already in run queue", ke,
 1097             ke->ke_proc->p_comm));
 1098         KASSERT(ke->ke_proc->p_sflag & PS_INMEM,
 1099             ("sched_add: process swapped out"));
 1100         CTR5(KTR_SCHED, "sched_add: %p(%s) prio %d by %p(%s)",
 1101             td, td->td_proc->p_comm, td->td_priority, curthread,
 1102             curthread->td_proc->p_comm);
 1103         CTR2(KTR_RUNQ, "sched_add: adding kse:%p (td:%p) to runq", ke, td);
 1104         ke->ke_runq = &runq;
 1105 
 1106         /* 
 1107          * If we are yielding (on the way out anyhow) 
 1108          * or the thread being saved is US,
 1109          * then don't try be smart about preemption
 1110          * or kicking off another CPU
 1111          * as it won't help and may hinder.
 1112          * In the YIEDLING case, we are about to run whoever is 
 1113          * being put in the queue anyhow, and in the 
 1114          * OURSELF case, we are puting ourself on the run queue
 1115          * which also only happens when we are about to yield.
 1116          */
 1117         if((flags & SRQ_YIELDING) == 0) {
 1118                 if (maybe_preempt(td))
 1119                         return;
 1120         }       
 1121         if ((td->td_proc->p_flag & P_NOLOAD) == 0)
 1122                 sched_load_add();
 1123         SLOT_USE(td->td_ksegrp);
 1124         runq_add(ke->ke_runq, ke, flags);
 1125         ke->ke_ksegrp->kg_runq_kses++;
 1126         ke->ke_state = KES_ONRUNQ;
 1127         maybe_resched(td);
 1128 }
 1129 #endif /* SMP */
 1130 
 1131 void
 1132 sched_rem(struct thread *td)
 1133 {
 1134         struct kse *ke;
 1135 
 1136         ke = td->td_kse;
 1137         KASSERT(ke->ke_proc->p_sflag & PS_INMEM,
 1138             ("sched_rem: process swapped out"));
 1139         KASSERT((ke->ke_state == KES_ONRUNQ),
 1140             ("sched_rem: KSE not on run queue"));
 1141         mtx_assert(&sched_lock, MA_OWNED);
 1142 
 1143         CTR5(KTR_SCHED, "sched_rem: %p(%s) prio %d by %p(%s)",
 1144             td, td->td_proc->p_comm, td->td_priority, curthread,
 1145             curthread->td_proc->p_comm);
 1146         if ((td->td_proc->p_flag & P_NOLOAD) == 0)
 1147                 sched_load_rem();
 1148         SLOT_RELEASE(td->td_ksegrp);
 1149         runq_remove(ke->ke_runq, ke);
 1150 
 1151         ke->ke_state = KES_THREAD;
 1152         td->td_ksegrp->kg_runq_kses--;
 1153 }
 1154 
 1155 /*
 1156  * Select threads to run.
 1157  * Notice that the running threads still consume a slot.
 1158  */
 1159 struct kse *
 1160 sched_choose(void)
 1161 {
 1162         struct kse *ke;
 1163         struct runq *rq;
 1164 
 1165 #ifdef SMP
 1166         struct kse *kecpu;
 1167 
 1168         rq = &runq;
 1169         ke = runq_choose(&runq);
 1170         kecpu = runq_choose(&runq_pcpu[PCPU_GET(cpuid)]);
 1171 
 1172         if (ke == NULL || 
 1173             (kecpu != NULL && 
 1174              kecpu->ke_thread->td_priority < ke->ke_thread->td_priority)) {
 1175                 CTR2(KTR_RUNQ, "choosing kse %p from pcpu runq %d", kecpu,
 1176                      PCPU_GET(cpuid));
 1177                 ke = kecpu;
 1178                 rq = &runq_pcpu[PCPU_GET(cpuid)];
 1179         } else { 
 1180                 CTR1(KTR_RUNQ, "choosing kse %p from main runq", ke);
 1181         }
 1182 
 1183 #else
 1184         rq = &runq;
 1185         ke = runq_choose(&runq);
 1186 #endif
 1187 
 1188         if (ke != NULL) {
 1189                 runq_remove(rq, ke);
 1190                 ke->ke_state = KES_THREAD;
 1191                 ke->ke_ksegrp->kg_runq_kses--;
 1192 
 1193                 KASSERT(ke->ke_proc->p_sflag & PS_INMEM,
 1194                     ("sched_choose: process swapped out"));
 1195         }
 1196         return (ke);
 1197 }
 1198 
 1199 void
 1200 sched_userret(struct thread *td)
 1201 {
 1202         struct ksegrp *kg;
 1203         /*
 1204          * XXX we cheat slightly on the locking here to avoid locking in
 1205          * the usual case.  Setting td_priority here is essentially an
 1206          * incomplete workaround for not setting it properly elsewhere.
 1207          * Now that some interrupt handlers are threads, not setting it
 1208          * properly elsewhere can clobber it in the window between setting
 1209          * it here and returning to user mode, so don't waste time setting
 1210          * it perfectly here.
 1211          */
 1212         kg = td->td_ksegrp;
 1213         if (td->td_priority != kg->kg_user_pri) {
 1214                 mtx_lock_spin(&sched_lock);
 1215                 td->td_priority = kg->kg_user_pri;
 1216                 mtx_unlock_spin(&sched_lock);
 1217         }
 1218 }
 1219 
 1220 void
 1221 sched_bind(struct thread *td, int cpu)
 1222 {
 1223         struct kse *ke;
 1224 
 1225         mtx_assert(&sched_lock, MA_OWNED);
 1226         KASSERT(TD_IS_RUNNING(td),
 1227             ("sched_bind: cannot bind non-running thread"));
 1228 
 1229         ke = td->td_kse;
 1230 
 1231         ke->ke_flags |= KEF_BOUND;
 1232 #ifdef SMP
 1233         ke->ke_runq = &runq_pcpu[cpu];
 1234         if (PCPU_GET(cpuid) == cpu)
 1235                 return;
 1236 
 1237         ke->ke_state = KES_THREAD;
 1238 
 1239         mi_switch(SW_VOL, NULL);
 1240 #endif
 1241 }
 1242 
 1243 void
 1244 sched_unbind(struct thread* td)
 1245 {
 1246         mtx_assert(&sched_lock, MA_OWNED);
 1247         td->td_kse->ke_flags &= ~KEF_BOUND;
 1248 }
 1249 
 1250 int
 1251 sched_load(void)
 1252 {
 1253         return (sched_tdcnt);
 1254 }
 1255 
 1256 int
 1257 sched_sizeof_ksegrp(void)
 1258 {
 1259         return (sizeof(struct ksegrp) + sizeof(struct kg_sched));
 1260 }
 1261 int
 1262 sched_sizeof_proc(void)
 1263 {
 1264         return (sizeof(struct proc));
 1265 }
 1266 int
 1267 sched_sizeof_thread(void)
 1268 {
 1269         return (sizeof(struct thread) + sizeof(struct kse));
 1270 }
 1271 
 1272 fixpt_t
 1273 sched_pctcpu(struct thread *td)
 1274 {
 1275         struct kse *ke;
 1276 
 1277         ke = td->td_kse;
 1278         return (ke->ke_pctcpu);
 1279 
 1280         return (0);
 1281 }
 1282 #define KERN_SWITCH_INCLUDE 1
 1283 #include "kern/kern_switch.c"

Cache object: fae69d4b38e1092800dc7aeafedd4345


[ 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.