1d265f300SJohn Baldwin.\" Copyright (c) 2000-2001 John H. Baldwin <jhb@FreeBSD.org> 240abbce7SJohn Baldwin.\" 340abbce7SJohn Baldwin.\" Redistribution and use in source and binary forms, with or without 440abbce7SJohn Baldwin.\" modification, are permitted provided that the following conditions 540abbce7SJohn Baldwin.\" are met: 640abbce7SJohn Baldwin.\" 1. Redistributions of source code must retain the above copyright 740abbce7SJohn Baldwin.\" notice, this list of conditions and the following disclaimer. 840abbce7SJohn Baldwin.\" 2. Redistributions in binary form must reproduce the above copyright 940abbce7SJohn Baldwin.\" notice, this list of conditions and the following disclaimer in the 1040abbce7SJohn Baldwin.\" documentation and/or other materials provided with the distribution. 1140abbce7SJohn Baldwin.\" 1240abbce7SJohn Baldwin.\" THIS SOFTWARE IS PROVIDED BY THE DEVELOPERS ``AS IS'' AND ANY EXPRESS OR 1340abbce7SJohn Baldwin.\" IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 1440abbce7SJohn Baldwin.\" OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 1540abbce7SJohn Baldwin.\" IN NO EVENT SHALL THE DEVELOPERS BE LIABLE FOR ANY DIRECT, INDIRECT, 1640abbce7SJohn Baldwin.\" INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 1740abbce7SJohn Baldwin.\" NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 1840abbce7SJohn Baldwin.\" DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 1940abbce7SJohn Baldwin.\" THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 2040abbce7SJohn Baldwin.\" (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 2140abbce7SJohn Baldwin.\" THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 2240abbce7SJohn Baldwin.\" 23*6a8d8aa1SChristian Brueffer.Dd August 15, 2010 2440abbce7SJohn Baldwin.Dt RUNQUEUE 9 2540abbce7SJohn Baldwin.Os 2640abbce7SJohn Baldwin.Sh NAME 27*6a8d8aa1SChristian Brueffer.Nm choosethread , 2840abbce7SJohn Baldwin.Nm procrunnable , 2940abbce7SJohn Baldwin.Nm remrunqueue , 3040abbce7SJohn Baldwin.Nm setrunqueue 3140abbce7SJohn Baldwin.Nd manage the queue of runnable processes 3240abbce7SJohn Baldwin.Sh SYNOPSIS 3332eef9aeSRuslan Ermilov.In sys/param.h 3432eef9aeSRuslan Ermilov.In sys/proc.h 359aa16122SRuslan Ermilov.Vt "extern struct rq itqueues[]" ; 369aa16122SRuslan Ermilov.Vt "extern struct rq rtqueues[]" ; 379aa16122SRuslan Ermilov.Vt "extern struct rq queues[]" ; 389aa16122SRuslan Ermilov.Vt "extern struct rq idqueues[]" ; 39f16b3c0dSChad David.Ft struct thread * 40f16b3c0dSChad David.Fn choosethread "void" 41f16b3c0dSChad David.Ft int 4240abbce7SJohn Baldwin.Fn procrunnable "void" 4340abbce7SJohn Baldwin.Ft void 44f16b3c0dSChad David.Fn remrunqueue "struct thread *td" 4540abbce7SJohn Baldwin.Ft void 46f16b3c0dSChad David.Fn setrunqueue "struct thread *td" 4740abbce7SJohn Baldwin.Sh DESCRIPTION 4840abbce7SJohn BaldwinThe run queue consists of four priority queues: 4940abbce7SJohn Baldwin.Va itqueues 5040abbce7SJohn Baldwinfor interrupt threads, 5140abbce7SJohn Baldwin.Va rtqueues 5240abbce7SJohn Baldwinfor realtime priority processes, 5340abbce7SJohn Baldwin.Va queues 5440abbce7SJohn Baldwinfor time sharing processes, and 5540abbce7SJohn Baldwin.Va idqueues 5640abbce7SJohn Baldwinfor idle priority processes. 5740abbce7SJohn BaldwinEach priority queue consists of an array of 5840abbce7SJohn Baldwin.Dv NQS 5940abbce7SJohn Baldwinqueue header structures. 6040abbce7SJohn BaldwinEach queue header identifies a list of runnable processes of equal priority. 6140abbce7SJohn BaldwinEach queue also has a single word that contains a bit mask identifying 6240abbce7SJohn Baldwinnon-empty queues to assist in selecting a process quickly. 6340abbce7SJohn BaldwinThese are named 6440abbce7SJohn Baldwin.Va itqueuebits , 6540abbce7SJohn Baldwin.Va rtqueuebits , 6640abbce7SJohn Baldwin.Va queuebits , 6740abbce7SJohn Baldwinand 6840abbce7SJohn Baldwin.Va idqueuebits . 6940abbce7SJohn BaldwinThe run queues are protected by the 7040abbce7SJohn Baldwin.Va sched_lock 7140abbce7SJohn Baldwinmutex. 7240abbce7SJohn Baldwin.Pp 7340abbce7SJohn Baldwin.Fn procrunnable 7440abbce7SJohn Baldwinreturns zero if there are no runnable processes other than the idle process. 7540abbce7SJohn BaldwinIf there is at least one runnable process other than the idle process, it 7640abbce7SJohn Baldwinwill return a non-zero value. 7740abbce7SJohn BaldwinNote that the 7840abbce7SJohn Baldwin.Va sched_lock 7940abbce7SJohn Baldwinmutex does 8040abbce7SJohn Baldwin.Em not 8140abbce7SJohn Baldwinneed to be held when this function is called. 8240abbce7SJohn BaldwinThere is a small race window where one CPU may place a process on the run queue 8340abbce7SJohn Baldwinwhen there are currently no other runnable processes while another CPU is 8440abbce7SJohn Baldwincalling this function. 8540abbce7SJohn BaldwinIn that case the second CPU will simply travel through the idle loop one 8640abbce7SJohn Baldwinadditional time before noticing that there is a runnable process. 8740abbce7SJohn BaldwinThis works because idle CPUs are not halted in SMP systems. 8840abbce7SJohn BaldwinIf idle CPUs are halted in SMP systems, then this race condition might have 899aa16122SRuslan Ermilovmore serious repercussions in the losing case, and 9040abbce7SJohn Baldwin.Fn procrunnable 9140abbce7SJohn Baldwinmay have to require that the 9240abbce7SJohn Baldwin.Va sched_lock 9340abbce7SJohn Baldwinmutex be acquired. 9440abbce7SJohn Baldwin.Pp 95f16b3c0dSChad David.Fn choosethread 96f16b3c0dSChad Davidreturns the highest priority runnable thread. 97f16b3c0dSChad DavidIf there are no runnable threads, then the idle thread is returned. 9840abbce7SJohn BaldwinThis function is called by 9940abbce7SJohn Baldwin.Fn cpu_switch 10040abbce7SJohn Baldwinand 10140abbce7SJohn Baldwin.Fn cpu_throw 102f16b3c0dSChad Davidto determine which thread to switch to. 103f16b3c0dSChad David.Fn choosethread 10440abbce7SJohn Baldwinmust be called with the 10540abbce7SJohn Baldwin.Va sched_lock 10640abbce7SJohn Baldwinmutex held. 10740abbce7SJohn Baldwin.Pp 10840abbce7SJohn Baldwin.Fn setrunqueue 109f16b3c0dSChad Davidadds the thread 110f16b3c0dSChad David.Fa td 11140abbce7SJohn Baldwinto the tail of the appropriate queue in the proper priority queue. 112f16b3c0dSChad DavidThe thread must be runnable, i.e.\& 11340abbce7SJohn Baldwin.Va p_stat 11440abbce7SJohn Baldwinmust be set to 11540abbce7SJohn Baldwin.Dv SRUN . 11640abbce7SJohn BaldwinThis function must be called with the 11740abbce7SJohn Baldwin.Va sched_lock 11840abbce7SJohn Baldwinmutex held. 11940abbce7SJohn Baldwin.Pp 12040abbce7SJohn Baldwin.Fn remrunqueue 121f16b3c0dSChad Davidremoves thread 122f16b3c0dSChad David.Fa td 12340abbce7SJohn Baldwinfrom its run queue. 12440abbce7SJohn BaldwinIf 125f16b3c0dSChad David.Fa td 12640abbce7SJohn Baldwinis not on a run queue, then the kernel will 12740abbce7SJohn Baldwin.Xr panic 9 . 12840abbce7SJohn BaldwinThis function must be called with the 12940abbce7SJohn Baldwin.Va sched_lock 13040abbce7SJohn Baldwinmutex held. 13140abbce7SJohn Baldwin.Sh SEE ALSO 13240abbce7SJohn Baldwin.Xr cpu_switch 9 , 13340abbce7SJohn Baldwin.Xr scheduler 9 , 13440abbce7SJohn Baldwin.Xr sleepqueue 9 135