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$ 27 */ 28 29 #include <sys/param.h> 30 #include <sys/systm.h> 31 #include <sys/kernel.h> 32 #include <sys/ktr.h> 33 #include <sys/mutex.h> 34 #include <sys/proc.h> 35 #include <sys/rtprio.h> 36 #include <sys/queue.h> 37 38 /* 39 * We have NQS (32) run queues per scheduling class. For the normal 40 * class, there are 128 priorities scaled onto these 32 queues. New 41 * processes are added to the last entry in each queue, and processes 42 * are selected for running by taking them from the head and maintaining 43 * a simple FIFO arrangement. 44 * 45 * Interrupt, real time and idle priority processes have and explicit 46 * 0-31 priority which maps directly onto their class queue index. 47 * When a queue has something in it, the corresponding bit is set in 48 * the queuebits variable, allowing a single read to determine the 49 * state of all 32 queues and then a ffs() to find the first busy 50 * queue. 51 * 52 * XXX This needs fixing. First, we only have one idle process, so we 53 * hardly need 32 queues for it. Secondly, the number of classes 54 * makes things unwieldy. We should be able to merge them into a 55 * single 96 or 128 entry queue. 56 */ 57 struct rq itqueues[NQS]; /* interrupt threads */ 58 struct rq rtqueues[NQS]; /* real time processes */ 59 struct rq queues[NQS]; /* time sharing processes */ 60 struct rq idqueues[NQS]; /* idle process */ 61 u_int32_t itqueuebits; 62 u_int32_t rtqueuebits; 63 u_int32_t queuebits; 64 u_int32_t idqueuebits; 65 66 /* 67 * Initialize the run queues at boot time. 68 */ 69 static void 70 rqinit(void *dummy) 71 { 72 int i; 73 74 for (i = 0; i < NQS; i++) { 75 TAILQ_INIT(&itqueues[i]); 76 TAILQ_INIT(&rtqueues[i]); 77 TAILQ_INIT(&queues[i]); 78 TAILQ_INIT(&idqueues[i]); 79 } 80 } 81 SYSINIT(runqueue, SI_SUB_RUN_QUEUE, SI_ORDER_FIRST, rqinit, NULL) 82 83 /* 84 * setrunqueue() examines a process priority and class and inserts it on 85 * the tail of it's appropriate run queue (based on class and priority). 86 * This sets the queue busy bit. 87 * The process must be runnable. 88 * This must be called at splhigh(). 89 */ 90 void 91 setrunqueue(struct proc *p) 92 { 93 struct rq *q; 94 u_int8_t pri; 95 96 mtx_assert(&sched_lock, MA_OWNED); 97 KASSERT(p->p_stat == SRUN, ("setrunqueue: proc %p (%s) not SRUN", p, \ 98 p->p_comm)); 99 100 /* 101 * Decide which class we want to run. We now have four 102 * queues, and this is becoming ugly. We should be able to 103 * collapse the first three classes into a single contiguous 104 * queue. XXX FIXME. 105 */ 106 CTR4(KTR_PROC, "setrunqueue: proc %p (pid %d, %s), schedlock %lx", 107 p, p->p_pid, p->p_comm, (long)sched_lock.mtx_lock); 108 if (p->p_rtprio.type == RTP_PRIO_ITHREAD) { /* interrupt thread */ 109 pri = p->p_rtprio.prio; 110 q = &itqueues[pri]; 111 itqueuebits |= 1 << pri; 112 } else if (p->p_rtprio.type == RTP_PRIO_REALTIME || /* real time */ 113 p->p_rtprio.type == RTP_PRIO_FIFO) { 114 pri = p->p_rtprio.prio; 115 q = &rtqueues[pri]; 116 rtqueuebits |= 1 << pri; 117 } else if (p->p_rtprio.type == RTP_PRIO_NORMAL) { /* time sharing */ 118 pri = p->p_priority >> 2; 119 q = &queues[pri]; 120 queuebits |= 1 << pri; 121 } else if (p->p_rtprio.type == RTP_PRIO_IDLE) { /* idle proc */ 122 pri = p->p_rtprio.prio; 123 q = &idqueues[pri]; 124 idqueuebits |= 1 << pri; 125 } else { 126 panic("setrunqueue: invalid rtprio type %d", p->p_rtprio.type); 127 } 128 p->p_rqindex = pri; /* remember the queue index */ 129 TAILQ_INSERT_TAIL(q, p, p_procq); 130 } 131 132 /* 133 * remrunqueue() removes a given process from the run queue that it is on, 134 * clearing the queue busy bit if it becomes empty. 135 * This must be called at splhigh(). 136 */ 137 void 138 remrunqueue(struct proc *p) 139 { 140 struct rq *q; 141 u_int32_t *which; 142 u_int8_t pri; 143 144 CTR4(KTR_PROC, "remrunqueue: proc %p (pid %d, %s), schedlock %lx", 145 p, p->p_pid, p->p_comm, (long)sched_lock.mtx_lock); 146 mtx_assert(&sched_lock, MA_OWNED); 147 pri = p->p_rqindex; 148 if (p->p_rtprio.type == RTP_PRIO_ITHREAD) { 149 q = &itqueues[pri]; 150 which = &itqueuebits; 151 } else if (p->p_rtprio.type == RTP_PRIO_REALTIME || 152 p->p_rtprio.type == RTP_PRIO_FIFO) { 153 q = &rtqueues[pri]; 154 which = &rtqueuebits; 155 } else if (p->p_rtprio.type == RTP_PRIO_NORMAL) { 156 q = &queues[pri]; 157 which = &queuebits; 158 } else if (p->p_rtprio.type == RTP_PRIO_IDLE) { 159 q = &idqueues[pri]; 160 which = &idqueuebits; 161 } else { 162 panic("remrunqueue: invalid rtprio type"); 163 } 164 TAILQ_REMOVE(q, p, p_procq); 165 if (TAILQ_EMPTY(q)) { 166 KASSERT((*which & (1 << pri)) != 0, 167 ("remrunqueue: remove from empty queue")); 168 *which &= ~(1 << pri); 169 } 170 } 171 172 /* 173 * procrunnable() returns a boolean true (non-zero) value if there are 174 * any runnable processes. This is intended to be called from the idle 175 * loop to avoid the more expensive (and destructive) chooseproc(). 176 * 177 * MP SAFE. CALLED WITHOUT THE MP LOCK 178 * 179 * XXX I doubt this. It's possibly fail-safe, but there's obviously 180 * the case here where one of the bits words gets loaded, the 181 * processor gets preempted, and by the time it returns from this 182 * function, some other processor has picked the runnable process. 183 * What am I missing? (grog, 23 July 2000). 184 */ 185 u_int32_t 186 procrunnable(void) 187 { 188 return (itqueuebits || rtqueuebits || queuebits || idqueuebits); 189 } 190 191 /* 192 * chooseproc() selects the next process to run. Ideally, cpu_switch() 193 * would have determined that there is a process available before calling 194 * this, but it is not a requirement. The selected process is removed 195 * from it's queue, and the queue busy bit is cleared if it becomes empty. 196 * This must be called at splhigh(). 197 * 198 * For SMP, trivial affinity is implemented by locating the first process 199 * on the queue that has a matching lastcpu id. Since normal priorities 200 * are mapped four priority levels per queue, this may allow the cpu to 201 * choose a slightly lower priority process in order to preserve the cpu 202 * caches. 203 */ 204 struct proc * 205 chooseproc(void) 206 { 207 struct proc *p; 208 struct rq *q; 209 u_int32_t *which; 210 u_int32_t pri; 211 #ifdef SMP 212 u_char id; 213 #endif 214 215 mtx_assert(&sched_lock, MA_OWNED); 216 if (itqueuebits) { 217 pri = ffs(itqueuebits) - 1; 218 q = &itqueues[pri]; 219 which = &itqueuebits; 220 } else if (rtqueuebits) { 221 pri = ffs(rtqueuebits) - 1; 222 q = &rtqueues[pri]; 223 which = &rtqueuebits; 224 } else if (queuebits) { 225 pri = ffs(queuebits) - 1; 226 q = &queues[pri]; 227 which = &queuebits; 228 } else if (idqueuebits) { 229 pri = ffs(idqueuebits) - 1; 230 q = &idqueues[pri]; 231 which = &idqueuebits; 232 } else { 233 CTR1(KTR_PROC, "chooseproc: idleproc, schedlock %lx", 234 (long)sched_lock.mtx_lock); 235 return idleproc; 236 } 237 p = TAILQ_FIRST(q); 238 #ifdef SMP 239 /* wander down the current run queue for this pri level for a match */ 240 id = cpuid; 241 while (p->p_lastcpu != id) { 242 p = TAILQ_NEXT(p, p_procq); 243 if (p == NULL) { 244 p = TAILQ_FIRST(q); 245 break; 246 } 247 } 248 #endif 249 CTR4(KTR_PROC, "chooseproc: proc %p (pid %d, %s), schedlock %lx", 250 p, p->p_pid, p->p_comm, (long)sched_lock.mtx_lock); 251 KASSERT(p, ("chooseproc: no proc on busy queue")); 252 TAILQ_REMOVE(q, p, p_procq); 253 if (TAILQ_EMPTY(q)) 254 *which &= ~(1 << pri); 255 return p; 256 } 257