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/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 } 209