xref: /freebsd/share/man/man9/runqueue.9 (revision fa9896e082a1046ff4fbc75fcba4d18d1f2efc19)
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