share/man/man9/runqueue.9

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