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 }
Cache object: 4fa87fadb645bd48d5310e3c5935c013
|