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