sys/kern/kern_switch.c

   1 /*
   2  * Copyright (c) 1999 Peter Wemm <peter@FreeBSD.org>
   3  * All rights reserved.
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions
   7  * are met:
   8  * 1. Redistributions of source code must retain the above copyright
   9  *    notice, this list of conditions and the following disclaimer.
  10  * 2. Redistributions in binary form must reproduce the above copyright
  11  *    notice, this list of conditions and the following disclaimer in the
  12  *    documentation and/or other materials provided with the distribution.
  13  *
  14  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
  15  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  16  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  17  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
  18  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  19  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  20  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  21  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  22  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  23  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  24  * SUCH DAMAGE.
  25  *
  26  * $FreeBSD: src/sys/kern/kern_switch.c,v 1.3.2.1 2000/05/16 06:58:12 dillon Exp $
  27  */
  28
  29 #include <sys/param.h>
  30 #include <sys/systm.h>
  31 #include <sys/kernel.h>
  32 #include <sys/proc.h>
  33 #include <sys/rtprio.h>
  34 #include <sys/queue.h>
  35
  36 /*
  37  * We have NQS (32) run queues per scheduling class.  For the normal
  38  * class, there are 128 priorities scaled onto these 32 queues.  New
  39  * processes are added to the last entry in each queue, and processes
  40  * are selected for running by taking them from the head and maintaining
  41  * a simple FIFO arrangement.  Realtime and Idle priority processes have
  42  * and explicit 0-31 priority which maps directly onto their class queue
  43  * index.  When a queue has something in it, the corresponding bit is
  44  * set in the queuebits variable, allowing a single read to determine
  45  * the state of all 32 queues and then a ffs() to find the first busy
  46  * queue.
  47  */
  48 struct rq queues[NQS];
  49 struct rq rtqueues[NQS];
  50 struct rq idqueues[NQS];
  51 u_int32_t queuebits;
  52 u_int32_t rtqueuebits;
  53 u_int32_t idqueuebits;
  54
  55 /*
  56  * Initialize the run queues at boot time.
  57  */
  58 static void
  59 rqinit(void *dummy)
  60 {
  61         int i;
  62
  63         for (i = 0; i < NQS; i++) {
  64                 TAILQ_INIT(&queues[i]);
  65                 TAILQ_INIT(&rtqueues[i]);
  66                 TAILQ_INIT(&idqueues[i]);
  67         }
  68 }
  69 SYSINIT(runqueue, SI_SUB_RUN_QUEUE, SI_ORDER_FIRST, rqinit, NULL)
  70
  71 /*
  72  * setrunqueue() examines a process priority and class and inserts it on
  73  * the tail of it's appropriate run queue (based on class and priority).
  74  * This sets the queue busy bit.
  75  * The process must be runnable.
  76  * This must be called at splhigh().
  77  */
  78 void
  79 setrunqueue(struct proc *p)
  80 {
  81         struct rq *q;
  82         u_int8_t pri;
  83
  84         KASSERT(p->p_stat == SRUN, ("setrunqueue: proc not SRUN"));
  85         if (p->p_rtprio.type == RTP_PRIO_NORMAL) {
  86                 pri = p->p_priority >> 2;
  87                 q = &queues[pri];
  88                 queuebits |= 1 << pri;
  89         } else if (p->p_rtprio.type == RTP_PRIO_REALTIME ||
  90                    p->p_rtprio.type == RTP_PRIO_FIFO) {
  91                 pri = p->p_rtprio.prio;
  92                 q = &rtqueues[pri];
  93                 rtqueuebits |= 1 << pri;
  94         } else if (p->p_rtprio.type == RTP_PRIO_IDLE) {
  95                 pri = p->p_rtprio.prio;
  96                 q = &idqueues[pri];
  97                 idqueuebits |= 1 << pri;
  98         } else {
  99                 panic("setrunqueue: invalid rtprio type");
 100         }
 101         p->p_rqindex = pri;             /* remember the queue index */
 102         TAILQ_INSERT_TAIL(q, p, p_procq);
 103 }
 104
 105 /*
 106  * remrunqueue() removes a given process from the run queue that it is on,
 107  * clearing the queue busy bit if it becomes empty.
 108  * This must be called at splhigh().
 109  */
 110 void
 111 remrunqueue(struct proc *p)
 112 {
 113         struct rq *q;
 114         u_int32_t *which;
 115         u_int8_t pri;
 116
 117         pri = p->p_rqindex;
 118         if (p->p_rtprio.type == RTP_PRIO_NORMAL) {
 119                 q = &queues[pri];
 120                 which = &queuebits;
 121         } else if (p->p_rtprio.type == RTP_PRIO_REALTIME ||
 122                    p->p_rtprio.type == RTP_PRIO_FIFO) {
 123                 q = &rtqueues[pri];
 124                 which = &rtqueuebits;
 125         } else if (p->p_rtprio.type == RTP_PRIO_IDLE) {
 126                 q = &idqueues[pri];
 127                 which = &idqueuebits;
 128         } else {
 129                 panic("remrunqueue: invalid rtprio type");
 130         }
 131         TAILQ_REMOVE(q, p, p_procq);
 132         if (TAILQ_EMPTY(q)) {
 133                 KASSERT((*which & (1 << pri)) != 0,
 134                         ("remrunqueue: remove from empty queue"));
 135                 *which &= ~(1 << pri);
 136         }
 137 }
 138
 139 /*
 140  * procrunnable() returns a boolean true (non-zero) value if there are
 141  * any runnable processes.  This is intended to be called from the idle
 142  * loop to avoid the more expensive (and destructive) chooseproc().
 143  *
 144  * MP SAFE.  CALLED WITHOUT THE MP LOCK
 145  */
 146 u_int32_t
 147 procrunnable(void)
 148 {
 149         return (rtqueuebits || queuebits || idqueuebits);
 150 }
 151
 152 /*
 153  * chooseproc() selects the next process to run.  Ideally, cpu_switch()
 154  * would have determined that there is a process available before calling
 155  * this, but it is not a requirement.  The selected process is removed
 156  * from it's queue, and the queue busy bit is cleared if it becomes empty.
 157  * This must be called at splhigh().
 158  *
 159  * For SMP, trivial affinity is implemented by locating the first process
 160  * on the queue that has a matching lastcpu id.  Since normal priorities
 161  * are mapped four priority levels per queue, this may allow the cpu to
 162  * choose a slightly lower priority process in order to preserve the cpu
 163  * caches.
 164  */
 165 struct proc *
 166 chooseproc(void)
 167 {
 168         struct proc *p;
 169         struct rq *q;
 170         u_int32_t *which;
 171         u_int32_t pri;
 172 #ifdef SMP
 173         u_char id;
 174 #endif
 175
 176         if (rtqueuebits) {
 177                 pri = ffs(rtqueuebits) - 1;
 178                 q = &rtqueues[pri];
 179                 which = &rtqueuebits;
 180         } else if (queuebits) {
 181                 pri = ffs(queuebits) - 1;
 182                 q = &queues[pri];
 183                 which = &queuebits;
 184         } else if (idqueuebits) {
 185                 pri = ffs(idqueuebits) - 1;
 186                 q = &idqueues[pri];
 187                 which = &idqueuebits;
 188         } else {
 189                 return NULL;
 190         }
 191         p = TAILQ_FIRST(q);
 192         KASSERT(p, ("chooseproc: no proc on busy queue"));
 193 #ifdef SMP
 194         /* wander down the current run queue for this pri level for a match */
 195         id = cpuid;
 196         while (p->p_lastcpu != id) {
 197                 p = TAILQ_NEXT(p, p_procq);
 198                 if (p == NULL) {
 199                         p = TAILQ_FIRST(q);
 200                         break;
 201                 }
 202         }
 203 #endif
 204         TAILQ_REMOVE(q, p, p_procq);
 205         if (TAILQ_EMPTY(q))
 206                 *which &= ~(1 << pri);
 207         return p;
 208 }