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.4 2003/06/30 19:50:31 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. If no user processes have been scheduled
76 * on the LWKT subsystem we schedule this one.
78 * The process must be runnable.
79 * This must be called at splhigh().
82 setrunqueue(struct proc *p)
86 struct globaldata *gd;
88 KASSERT(p->p_stat == SRUN, ("setrunqueue: proc not SRUN"));
91 * If we are already the designated current process just
94 if (p->p_flag & P_CURPROC) {
95 KASSERT((p->p_flag & P_ONRUNQ) == 0, ("already on runq!"));
96 lwkt_schedule(p->p_thread);
101 * If the process's cpu is not running any userland processes
102 * then schedule this one's thread.
104 gd = p->p_thread->td_gd;
105 if (gd->gd_uprocscheduled == 0) {
106 gd->gd_uprocscheduled = 1;
107 p->p_flag |= P_CURPROC;
108 lwkt_schedule(p->p_thread);
109 KASSERT((p->p_flag & P_ONRUNQ) == 0, ("already on runq2!"));
113 KASSERT((p->p_flag & P_ONRUNQ) == 0, ("already on runq3!"));
114 p->p_flag |= P_ONRUNQ;
116 * Otherwise place this process on the userland scheduler's run
120 if (p->p_rtprio.type == RTP_PRIO_NORMAL) {
121 pri = p->p_priority >> 2;
123 queuebits |= 1 << pri;
124 } else if (p->p_rtprio.type == RTP_PRIO_REALTIME ||
125 p->p_rtprio.type == RTP_PRIO_FIFO) {
126 pri = p->p_rtprio.prio;
128 rtqueuebits |= 1 << pri;
129 } else if (p->p_rtprio.type == RTP_PRIO_IDLE) {
130 pri = p->p_rtprio.prio;
132 idqueuebits |= 1 << pri;
134 panic("setrunqueue: invalid rtprio type");
136 p->p_rqindex = pri; /* remember the queue index */
137 TAILQ_INSERT_TAIL(q, p, p_procq);
141 * remrunqueue() removes a given process from the run queue that it is on,
142 * clearing the queue busy bit if it becomes empty. This function is called
143 * when a userland process is selected for LWKT scheduling. Note that
144 * LWKT scheduling is an abstraction of 'curproc'.. there could very well be
145 * several userland processes whos threads are scheduled or otherwise in
146 * a special state, and such processes are NOT on the userland scheduler's
149 * This must be called at splhigh().
152 remrunqueue(struct proc *p)
158 KASSERT((p->p_flag & P_ONRUNQ) != 0, ("not on runq4!"));
159 p->p_flag &= ~P_ONRUNQ;
161 if (p->p_rtprio.type == RTP_PRIO_NORMAL) {
164 } else if (p->p_rtprio.type == RTP_PRIO_REALTIME ||
165 p->p_rtprio.type == RTP_PRIO_FIFO) {
167 which = &rtqueuebits;
168 } else if (p->p_rtprio.type == RTP_PRIO_IDLE) {
170 which = &idqueuebits;
172 panic("remrunqueue: invalid rtprio type");
174 TAILQ_REMOVE(q, p, p_procq);
175 if (TAILQ_EMPTY(q)) {
176 KASSERT((*which & (1 << pri)) != 0,
177 ("remrunqueue: remove from empty queue"));
178 *which &= ~(1 << pri);
183 * chooseproc() is called when a cpu needs a user process to LWKT schedule.
184 * chooseproc() will select a user process and return it.
195 pri = ffs(rtqueuebits) - 1;
197 which = &rtqueuebits;
198 } else if (queuebits) {
199 pri = ffs(queuebits) - 1;
202 } else if (idqueuebits) {
203 pri = ffs(idqueuebits) - 1;
205 which = &idqueuebits;
210 KASSERT(p, ("chooseproc: no proc on busy queue"));
211 TAILQ_REMOVE(q, p, p_procq);
213 *which &= ~(1 << pri);
214 KASSERT((p->p_flag & P_ONRUNQ) != 0, ("not on runq6!"));
215 p->p_flag &= ~P_ONRUNQ;