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