kern_switch.c revision 58717 
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: head/sys/kern/kern_switch.c 58717 2000-03-28 07:16:37Z dillon $
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 */
48struct rq queues[NQS];
49struct rq rtqueues[NQS];
50struct rq idqueues[NQS];
51u_int32_t queuebits;
52u_int32_t rtqueuebits;
53u_int32_t idqueuebits;
54
55/*
56 * Initialize the run queues at boot time.
57 */
58static void
59rqinit(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}
69SYSINIT(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 */
78void
79setrunqueue(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 */
110void
111remrunqueue(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 */
146u_int32_t
147procrunnable(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 */
165struct proc *
166chooseproc(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