share/man/man9/runqueue.9

   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
  50 The run queue consists of four priority queues:
  51 .Va itqueues
  52 for interrupt threads,
  53 .Va rtqueues
  54 for realtime priority processes,
  55 .Va queues
  56 for time sharing processes, and
  57 .Va idqueues
  58 for idle priority processes.
  59 Each priority queue consists of an array of
  60 .Dv NQS
  61 queue header structures.
  62 Each queue header identifies a list of runnable processes of equal priority.
  63 Each queue also has a single word that contains a bit mask identifying
  64 non-empty queues to assist in selecting a process quickly.
  65 These are named
  66 .Va itqueuebits ,
  67 .Va rtqueuebits ,
  68 .Va queuebits ,
  69 and
  70 .Va idqueuebits .
  71 The run queues are protected by the
  72 .Va sched_lock
  73 mutex.
  74 .Pp
  75 .Fn procrunnable
  76 returns zero if there are no runnable processes other than the idle process.
  77 If there is at least one runnable process other than the idle process, it
  78 will return a non-zero value.
  79 Note that the
  80 .Va sched_lock
  81 mutex does
  82 .Em not
  83 need to be held when this function is called.
  84 There is a small race window where one CPU may place a process on the run queue
  85 when there are currently no other runnable processes while another CPU is
  86 calling this function.
  87 In that case the second CPU will simply travel through the idle loop one
  88 additional time before noticing that there is a runnable process.
  89 This works because idle CPUs are not halted in SMP systems.
  90 If idle CPUs are halted in SMP systems, then this race condition might have
  91 more serious repercussions in the losing case, and
  92 .Fn procrunnable
  93 may have to require that the
  94 .Va sched_lock
  95 mutex be acquired.
  96 .Pp
  97 .Fn choosethread
  98 returns the highest priority runnable thread.
  99 If there are no runnable threads, then the idle thread is returned.
 100 This function is called by
 101 .Fn cpu_switch
 102 and
 103 .Fn cpu_throw
 104 to determine which thread to switch to.
 105 .Fn choosethread
 106 must be called with the
 107 .Va sched_lock
 108 mutex held.
 109 .Pp
 110 .Fn setrunqueue
 111 adds the thread
 112 .Fa td
 113 to the tail of the appropriate queue in the proper priority queue.
 114 The thread must be runnable, i.e.\&
 115 .Va p_stat
 116 must be set to
 117 .Dv SRUN .
 118 This function must be called with the
 119 .Va sched_lock
 120 mutex held.
 121 .Pp
 122 .Fn remrunqueue
 123 removes thread
 124 .Fa td
 125 from its run queue.
 126 If
 127 .Fa td
 128 is not on a run queue, then the kernel will
 129 .Xr panic 9 .
 130 This function must be called with the
 131 .Va sched_lock
 132 mutex held.
 133 .Sh SEE ALSO
 134 .Xr cpu_switch 9 ,
 135 .Xr scheduler 9 ,
 136 .Xr sleepqueue 9