1.\" Copyright (c) 2000-2001 John H. Baldwin <jhb@FreeBSD.org> 2.\" All rights reserved. 3.\" 4.\" Redistribution and use in source and binary forms, with or without 5.\" modification, are permitted provided that the following conditions 6.\" are met: 7.\" 1. Redistributions of source code must retain the above copyright 8.\" notice, this list of conditions and the following disclaimer. 9.\" 2. Redistributions in binary form must reproduce the above copyright 10.\" notice, this list of conditions and the following disclaimer in the 11.\" documentation and/or other materials provided with the distribution. 12.\" 13.\" THIS SOFTWARE IS PROVIDED BY THE DEVELOPERS ``AS IS'' AND ANY EXPRESS OR 14.\" IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 15.\" OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 16.\" IN NO EVENT SHALL THE DEVELOPERS BE LIABLE FOR ANY DIRECT, INDIRECT, 17.\" INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 18.\" NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 19.\" DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 20.\" THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 21.\" (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 22.\" THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 23.\" 24.\" $FreeBSD$ 25.\" 26.Dd November 3, 2000 27.Dt RUNQUEUE 9 28.Os 29.Sh NAME 30.Nm chooseproc , 31.Nm procrunnable , 32.Nm remrunqueue , 33.Nm setrunqueue 34.Nd manage the queue of runnable processes 35.Sh SYNOPSIS 36.Fd #include <sys/param.h> 37.Fd #include <sys/proc.h> 38.Vt "extern struct rq itqueues[]" ; 39.Vt "extern struct rq rtqueues[]" ; 40.Vt "extern struct rq queues[]" ; 41.Vt "extern struct rq idqueues[]" ; 42.Ft struct proc * 43.Fn chooseproc "void" 44.Ft u_int32_t 45.Fn procrunnable "void" 46.Ft void 47.Fn remrunqueue "struct proc *p" 48.Ft void 49.Fn setrunqueue "struct proc *p" 50.Sh DESCRIPTION 51The run queue consists of four priority queues: 52.Va itqueues 53for interrupt threads, 54.Va rtqueues 55for realtime priority processes, 56.Va queues 57for time sharing processes, and 58.Va idqueues 59for idle priority processes. 60Each priority queue consists of an array of 61.Dv NQS 62queue header structures. 63Each queue header identifies a list of runnable processes of equal priority. 64Each queue also has a single word that contains a bit mask identifying 65non-empty queues to assist in selecting a process quickly. 66These are named 67.Va itqueuebits , 68.Va rtqueuebits , 69.Va queuebits , 70and 71.Va idqueuebits . 72The run queues are protected by the 73.Va sched_lock 74mutex. 75.Pp 76.Fn procrunnable 77returns zero if there are no runnable processes other than the idle process. 78If there is at least one runnable process other than the idle process, it 79will return a non-zero value. 80Note that the 81.Va sched_lock 82mutex does 83.Em not 84need to be held when this function is called. 85There is a small race window where one CPU may place a process on the run queue 86when there are currently no other runnable processes while another CPU is 87calling this function. 88In that case the second CPU will simply travel through the idle loop one 89additional time before noticing that there is a runnable process. 90This works because idle CPUs are not halted in SMP systems. 91If idle CPUs are halted in SMP systems, then this race condition might have 92more serious repercussions in the losing case, and 93.Fn procrunnable 94may have to require that the 95.Va sched_lock 96mutex be acquired. 97.Pp 98.Fn chooseproc 99returns the highest priority runnable process. 100If there are no runnable processes, then the idle process is returned. 101This function is called by 102.Fn cpu_switch 103and 104.Fn cpu_throw 105to determine which process to switch to. 106.Fn chooseproc 107must be called with the 108.Va sched_lock 109mutex held. 110.Pp 111.Fn setrunqueue 112adds the process 113.Fa p 114to the tail of the appropriate queue in the proper priority queue. 115The process must be runnable, i.e.\& 116.Va p_stat 117must be set to 118.Dv SRUN . 119This function must be called with the 120.Va sched_lock 121mutex held. 122.Pp 123.Fn remrunqueue 124removes process 125.Fa p 126from its run queue. 127If 128.Fa p 129is not on a run queue, then the kernel will 130.Xr panic 9 . 131This function must be called with the 132.Va sched_lock 133mutex held. 134.Sh SEE ALSO 135.Xr cpu_switch 9 , 136.Xr scheduler 9 , 137.Xr sleepqueue 9 138