kern_switch.c revision 50027
150027Speter/* 250027Speter * Copyright (c) 1999 Peter Wemm <peter@FreeBSD.org> 350027Speter * All rights reserved. 450027Speter * 550027Speter * Redistribution and use in source and binary forms, with or without 650027Speter * modification, are permitted provided that the following conditions 750027Speter * are met: 850027Speter * 1. Redistributions of source code must retain the above copyright 950027Speter * notice, this list of conditions and the following disclaimer. 1050027Speter * 2. Redistributions in binary form must reproduce the above copyright 1150027Speter * notice, this list of conditions and the following disclaimer in the 1250027Speter * documentation and/or other materials provided with the distribution. 1350027Speter * 1450027Speter * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 1550027Speter * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 1650027Speter * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 1750027Speter * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 1850027Speter * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 1950027Speter * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 2050027Speter * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 2150027Speter * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 2250027Speter * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 2350027Speter * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 2450027Speter * SUCH DAMAGE. 2550027Speter * 2650027Speter * $FreeBSD: head/sys/kern/kern_switch.c 50027 1999-08-19 00:06:53Z peter $ 2750027Speter */ 2850027Speter 2950027Speter#include <sys/param.h> 3050027Speter#include <sys/systm.h> 3150027Speter#include <sys/kernel.h> 3250027Speter#include <sys/proc.h> 3350027Speter#include <sys/rtprio.h> 3450027Speter#include <sys/queue.h> 3550027Speter 3650027Speter/* 3750027Speter * We have NQS (32) run queues per scheduling class. For the normal 3850027Speter * class, there are 128 priorities scaled onto these 32 queues. New 3950027Speter * processes are added to the last entry in each queue, and processes 4050027Speter * are selected for running by taking them from the head and maintaining 4150027Speter * a simple FIFO arrangement. Realtime and Idle priority processes have 4250027Speter * and explicit 0-31 priority which maps directly onto their class queue 4350027Speter * index. When a queue has something in it, the corresponding bit is 4450027Speter * set in the queuebits variable, allowing a single read to determine 4550027Speter * the state of all 32 queues and then a ffs() to find the first busy 4650027Speter * queue. 4750027Speter */ 4850027Speterstruct rq queues[NQS]; 4950027Speterstruct rq rtqueues[NQS]; 5050027Speterstruct rq idqueues[NQS]; 5150027Speteru_int32_t queuebits; 5250027Speteru_int32_t rtqueuebits; 5350027Speteru_int32_t idqueuebits; 5450027Speter 5550027Speter/* 5650027Speter * Initialize the run queues at boot time. 5750027Speter */ 5850027Speterstatic void 5950027Speterrqinit(void *dummy) 6050027Speter{ 6150027Speter int i; 6250027Speter 6350027Speter for (i = 0; i < NQS; i++) { 6450027Speter TAILQ_INIT(&queues[i]); 6550027Speter TAILQ_INIT(&rtqueues[i]); 6650027Speter TAILQ_INIT(&idqueues[i]); 6750027Speter } 6850027Speter} 6950027SpeterSYSINIT(runqueue, SI_SUB_RUN_QUEUE, SI_ORDER_FIRST, rqinit, NULL) 7050027Speter 7150027Speter/* 7250027Speter * setrunqueue() examines a process priority and class and inserts it on 7350027Speter * the tail of it's appropriate run queue (based on class and priority). 7450027Speter * This sets the queue busy bit. 7550027Speter * The process must be runnable. 7650027Speter * This must be called at splhigh(). 7750027Speter */ 7850027Spetervoid 7950027Spetersetrunqueue(struct proc *p) 8050027Speter{ 8150027Speter struct rq *q; 8250027Speter u_int8_t pri; 8350027Speter 8450027Speter KASSERT(p->p_stat == SRUN, ("setrunqueue: proc not SRUN")); 8550027Speter if (p->p_rtprio.type == RTP_PRIO_REALTIME) { 8650027Speter pri = p->p_rtprio.prio; 8750027Speter q = &rtqueues[pri]; 8850027Speter rtqueuebits |= 1 << pri; 8950027Speter } else if (p->p_rtprio.type == RTP_PRIO_NORMAL) { 9050027Speter pri = p->p_priority >> 2; 9150027Speter q = &queues[pri]; 9250027Speter queuebits |= 1 << pri; 9350027Speter } else if (p->p_rtprio.type == RTP_PRIO_IDLE) { 9450027Speter pri = p->p_rtprio.prio; 9550027Speter q = &idqueues[pri]; 9650027Speter idqueuebits |= 1 << pri; 9750027Speter } else { 9850027Speter panic("setrunqueue: invalid rtprio type"); 9950027Speter } 10050027Speter p->p_rqindex = pri; /* remember the queue index */ 10150027Speter TAILQ_INSERT_TAIL(q, p, p_procq); 10250027Speter} 10350027Speter 10450027Speter/* 10550027Speter * remrunqueue() removes a given process from the run queue that it is on, 10650027Speter * clearing the queue busy bit if it becomes empty. 10750027Speter * This must be called at splhigh(). 10850027Speter */ 10950027Spetervoid 11050027Speterremrunqueue(struct proc *p) 11150027Speter{ 11250027Speter struct rq *q; 11350027Speter u_int32_t *which; 11450027Speter u_int8_t pri; 11550027Speter 11650027Speter pri = p->p_rqindex; 11750027Speter if (p->p_rtprio.type == RTP_PRIO_REALTIME) { 11850027Speter q = &rtqueues[pri]; 11950027Speter which = &rtqueuebits; 12050027Speter } else if (p->p_rtprio.type == RTP_PRIO_NORMAL) { 12150027Speter q = &queues[pri]; 12250027Speter which = &queuebits; 12350027Speter } else if (p->p_rtprio.type == RTP_PRIO_REALTIME) { 12450027Speter q = &idqueues[pri]; 12550027Speter which = &idqueuebits; 12650027Speter } else { 12750027Speter panic("remrunqueue: invalid rtprio type"); 12850027Speter } 12950027Speter TAILQ_REMOVE(q, p, p_procq); 13050027Speter if (TAILQ_EMPTY(q)) { 13150027Speter KASSERT((*which & (1 << pri)) != 0, 13250027Speter ("remrunqueue: remove from empty queue")); 13350027Speter *which &= ~(1 << pri); 13450027Speter } 13550027Speter} 13650027Speter 13750027Speter/* 13850027Speter * procrunnable() returns a boolean true (non-zero) value if there are 13950027Speter * any runnable processes. This is intended to be called from the idle 14050027Speter * loop to avoid the more expensive (and destructive) chooseproc(). 14150027Speter */ 14250027Speteru_int32_t 14350027Speterprocrunnable(void) 14450027Speter{ 14550027Speter return (rtqueuebits || queuebits || idqueuebits); 14650027Speter} 14750027Speter 14850027Speter/* 14950027Speter * chooseproc() selects the next process to run. Ideally, cpu_switch() 15050027Speter * would have determined that there is a process available before calling 15150027Speter * this, but it is not a requirement. The selected process is removed 15250027Speter * from it's queue, and the queue busy bit is cleared if it becomes empty. 15350027Speter * This must be called at splhigh(). 15450027Speter * 15550027Speter * For SMP, trivial affinity is implemented by locating the first process 15650027Speter * on the queue that has a matching lastcpu id. Since normal priorities 15750027Speter * are mapped four priority levels per queue, this may allow the cpu to 15850027Speter * choose a slightly lower priority process in order to preserve the cpu 15950027Speter * caches. 16050027Speter */ 16150027Speterstruct proc * 16250027Speterchooseproc(void) 16350027Speter{ 16450027Speter struct proc *p; 16550027Speter struct rq *q; 16650027Speter u_int32_t *which; 16750027Speter u_int32_t pri; 16850027Speter#ifdef SMP 16950027Speter u_char id; 17050027Speter#endif 17150027Speter 17250027Speter if (rtqueuebits) { 17350027Speter pri = ffs(rtqueuebits) - 1; 17450027Speter q = &rtqueues[pri]; 17550027Speter which = &rtqueuebits; 17650027Speter } else if (queuebits) { 17750027Speter pri = ffs(queuebits) - 1; 17850027Speter q = &queues[pri]; 17950027Speter which = &queuebits; 18050027Speter } else if (idqueuebits) { 18150027Speter pri = ffs(idqueuebits) - 1; 18250027Speter q = &idqueues[pri]; 18350027Speter which = &idqueuebits; 18450027Speter } else { 18550027Speter return NULL; 18650027Speter } 18750027Speter p = TAILQ_FIRST(q); 18850027Speter KASSERT(p, ("chooseproc: no proc on busy queue")); 18950027Speter#ifdef SMP 19050027Speter /* wander down the current run queue for this pri level for a match */ 19150027Speter id = cpuid; 19250027Speter while (p->p_lastcpu != id) { 19350027Speter p = TAILQ_NEXT(p, p_procq); 19450027Speter if (p == NULL) { 19550027Speter p = TAILQ_FIRST(q); 19650027Speter break; 19750027Speter } 19850027Speter } 19950027Speter#endif 20050027Speter TAILQ_REMOVE(q, p, p_procq); 20150027Speter if (TAILQ_EMPTY(q)) 20250027Speter *which &= ~(1 << pri); 20350027Speter return p; 20450027Speter} 205