2 * Copyright (c) 1999 Peter Wemm <peter@FreeBSD.org>
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
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.
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
26 * $FreeBSD: src/sys/kern/kern_switch.c,v 1.3.2.1 2000/05/16 06:58:12 dillon Exp $
27 * $DragonFly: src/sys/kern/Attic/kern_switch.c,v 1.2 2003/06/17 04:28:41 dillon Exp $
30 #include <sys/param.h>
31 #include <sys/systm.h>
32 #include <sys/kernel.h>
34 #include <sys/rtprio.h>
35 #include <sys/queue.h>
38 * We have NQS (32) run queues per scheduling class. For the normal
39 * class, there are 128 priorities scaled onto these 32 queues. New
40 * processes are added to the last entry in each queue, and processes
41 * are selected for running by taking them from the head and maintaining
42 * a simple FIFO arrangement. Realtime and Idle priority processes have
43 * and explicit 0-31 priority which maps directly onto their class queue
44 * index. When a queue has something in it, the corresponding bit is
45 * set in the queuebits variable, allowing a single read to determine
46 * the state of all 32 queues and then a ffs() to find the first busy
49 struct rq queues[NQS];
50 struct rq rtqueues[NQS];
51 struct rq idqueues[NQS];
53 u_int32_t rtqueuebits;
54 u_int32_t idqueuebits;
57 * Initialize the run queues at boot time.
64 for (i = 0; i < NQS; i++) {
65 TAILQ_INIT(&queues[i]);
66 TAILQ_INIT(&rtqueues[i]);
67 TAILQ_INIT(&idqueues[i]);
70 SYSINIT(runqueue, SI_SUB_RUN_QUEUE, SI_ORDER_FIRST, rqinit, NULL)
73 * setrunqueue() examines a process priority and class and inserts it on
74 * the tail of it's appropriate run queue (based on class and priority).
75 * This sets the queue busy bit.
76 * The process must be runnable.
77 * This must be called at splhigh().
80 setrunqueue(struct proc *p)
85 KASSERT(p->p_stat == SRUN, ("setrunqueue: proc not SRUN"));
86 if (p->p_rtprio.type == RTP_PRIO_NORMAL) {
87 pri = p->p_priority >> 2;
89 queuebits |= 1 << pri;
90 } else if (p->p_rtprio.type == RTP_PRIO_REALTIME ||
91 p->p_rtprio.type == RTP_PRIO_FIFO) {
92 pri = p->p_rtprio.prio;
94 rtqueuebits |= 1 << pri;
95 } else if (p->p_rtprio.type == RTP_PRIO_IDLE) {
96 pri = p->p_rtprio.prio;
98 idqueuebits |= 1 << pri;
100 panic("setrunqueue: invalid rtprio type");
102 p->p_rqindex = pri; /* remember the queue index */
103 TAILQ_INSERT_TAIL(q, p, p_procq);
107 * remrunqueue() removes a given process from the run queue that it is on,
108 * clearing the queue busy bit if it becomes empty.
109 * This must be called at splhigh().
112 remrunqueue(struct proc *p)
119 if (p->p_rtprio.type == RTP_PRIO_NORMAL) {
122 } else if (p->p_rtprio.type == RTP_PRIO_REALTIME ||
123 p->p_rtprio.type == RTP_PRIO_FIFO) {
125 which = &rtqueuebits;
126 } else if (p->p_rtprio.type == RTP_PRIO_IDLE) {
128 which = &idqueuebits;
130 panic("remrunqueue: invalid rtprio type");
132 TAILQ_REMOVE(q, p, p_procq);
133 if (TAILQ_EMPTY(q)) {
134 KASSERT((*which & (1 << pri)) != 0,
135 ("remrunqueue: remove from empty queue"));
136 *which &= ~(1 << pri);
141 * procrunnable() returns a boolean true (non-zero) value if there are
142 * any runnable processes. This is intended to be called from the idle
143 * loop to avoid the more expensive (and destructive) chooseproc().
145 * MP SAFE. CALLED WITHOUT THE MP LOCK
150 return (rtqueuebits || queuebits || idqueuebits);
154 * chooseproc() selects the next process to run. Ideally, cpu_switch()
155 * would have determined that there is a process available before calling
156 * this, but it is not a requirement. The selected process is removed
157 * from it's queue, and the queue busy bit is cleared if it becomes empty.
158 * This must be called at splhigh().
160 * For SMP, trivial affinity is implemented by locating the first process
161 * on the queue that has a matching lastcpu id. Since normal priorities
162 * are mapped four priority levels per queue, this may allow the cpu to
163 * choose a slightly lower priority process in order to preserve the cpu
178 pri = ffs(rtqueuebits) - 1;
180 which = &rtqueuebits;
181 } else if (queuebits) {
182 pri = ffs(queuebits) - 1;
185 } else if (idqueuebits) {
186 pri = ffs(idqueuebits) - 1;
188 which = &idqueuebits;
193 KASSERT(p, ("chooseproc: no proc on busy queue"));
195 /* wander down the current run queue for this pri level for a match */
197 while (p->p_lastcpu != id) {
198 p = TAILQ_NEXT(p, p_procq);
205 TAILQ_REMOVE(q, p, p_procq);
207 *which &= ~(1 << pri);