kern_switch.c revision 50027 
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 50027 1999-08-19 00:06:53Z peter $
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_REALTIME) {
86		pri = p->p_rtprio.prio;
87		q = &rtqueues[pri];
88		rtqueuebits |= 1 << pri;
89	} else if (p->p_rtprio.type == RTP_PRIO_NORMAL) {
90		pri = p->p_priority >> 2;
91		q = &queues[pri];
92		queuebits |= 1 << pri;
93	} else if (p->p_rtprio.type == RTP_PRIO_IDLE) {
94		pri = p->p_rtprio.prio;
95		q = &idqueues[pri];
96		idqueuebits |= 1 << pri;
97	} else {
98		panic("setrunqueue: invalid rtprio type");
99	}
100	p->p_rqindex = pri;		/* remember the queue index */
101	TAILQ_INSERT_TAIL(q, p, p_procq);
102}
103
104/*
105 * remrunqueue() removes a given process from the run queue that it is on,
106 * clearing the queue busy bit if it becomes empty.
107 * This must be called at splhigh().
108 */
109void
110remrunqueue(struct proc *p)
111{
112	struct rq *q;
113	u_int32_t *which;
114	u_int8_t pri;
115
116	pri = p->p_rqindex;
117	if (p->p_rtprio.type == RTP_PRIO_REALTIME) {
118		q = &rtqueues[pri];
119		which = &rtqueuebits;
120	} else if (p->p_rtprio.type == RTP_PRIO_NORMAL) {
121		q = &queues[pri];
122		which = &queuebits;
123	} else if (p->p_rtprio.type == RTP_PRIO_REALTIME) {
124		q = &idqueues[pri];
125		which = &idqueuebits;
126	} else {
127		panic("remrunqueue: invalid rtprio type");
128	}
129	TAILQ_REMOVE(q, p, p_procq);
130	if (TAILQ_EMPTY(q)) {
131		KASSERT((*which & (1 << pri)) != 0,
132			("remrunqueue: remove from empty queue"));
133		*which &= ~(1 << pri);
134	}
135}
136
137/*
138 * procrunnable() returns a boolean true (non-zero) value if there are
139 * any runnable processes.  This is intended to be called from the idle
140 * loop to avoid the more expensive (and destructive) chooseproc().
141 */
142u_int32_t
143procrunnable(void)
144{
145	return (rtqueuebits || queuebits || idqueuebits);
146}
147
148/*
149 * chooseproc() selects the next process to run.  Ideally, cpu_switch()
150 * would have determined that there is a process available before calling
151 * this, but it is not a requirement.  The selected process is removed
152 * from it's queue, and the queue busy bit is cleared if it becomes empty.
153 * This must be called at splhigh().
154 *
155 * For SMP, trivial affinity is implemented by locating the first process
156 * on the queue that has a matching lastcpu id.  Since normal priorities
157 * are mapped four priority levels per queue, this may allow the cpu to
158 * choose a slightly lower priority process in order to preserve the cpu
159 * caches.
160 */
161struct proc *
162chooseproc(void)
163{
164	struct proc *p;
165	struct rq *q;
166	u_int32_t *which;
167	u_int32_t pri;
168#ifdef SMP
169	u_char id;
170#endif
171
172	if (rtqueuebits) {
173		pri = ffs(rtqueuebits) - 1;
174		q = &rtqueues[pri];
175		which = &rtqueuebits;
176	} else if (queuebits) {
177		pri = ffs(queuebits) - 1;
178		q = &queues[pri];
179		which = &queuebits;
180	} else if (idqueuebits) {
181		pri = ffs(idqueuebits) - 1;
182		q = &idqueues[pri];
183		which = &idqueuebits;
184	} else {
185		return NULL;
186	}
187	p = TAILQ_FIRST(q);
188	KASSERT(p, ("chooseproc: no proc on busy queue"));
189#ifdef SMP
190	/* wander down the current run queue for this pri level for a match */
191	id = cpuid;
192	while (p->p_lastcpu != id) {
193		p = TAILQ_NEXT(p, p_procq);
194		if (p == NULL) {
195			p = TAILQ_FIRST(q);
196			break;
197		}
198	}
199#endif
200	TAILQ_REMOVE(q, p, p_procq);
201	if (TAILQ_EMPTY(q))
202		*which &= ~(1 << pri);
203	return p;
204}
205