share/man/man9/scheduler.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 November 3, 2000
  27 .Dt SCHEDULER 9
  28 .Os
  29 .Sh NAME
  30 .Nm curpriority_cmp ,
  31 .Nm maybe_resched ,
  32 .Nm resetpriority ,
  33 .Nm roundrobin ,
  34 .Nm roundrobin_interval ,
  35 .Nm sched_setup ,
  36 .Nm schedclock ,
  37 .Nm schedcpu ,
  38 .Nm setrunnable ,
  39 .Nm updatepri
  40 .Nd perform round-robin scheduling of runnable processes
  41 .Sh SYNOPSIS
  42 .In sys/param.h
  43 .In sys/proc.h
  44 .Ft int
  45 .Fn curpriority_cmp "struct proc *p"
  46 .Ft void
  47 .Fn maybe_resched "struct thread *td"
  48 .Ft void
  49 .Fn propagate_priority "struct proc *p"
  50 .Ft void
  51 .Fn resetpriority "struct ksegrp *kg"
  52 .Ft void
  53 .Fn roundrobin "void *arg"
  54 .Ft int
  55 .Fn roundrobin_interval "void"
  56 .Ft void
  57 .Fn sched_setup "void *dummy"
  58 .Ft void
  59 .Fn schedclock "struct thread *td"
  60 .Ft void
  61 .Fn schedcpu "void *arg"
  62 .Ft void
  63 .Fn setrunnable "struct thread *td"
  64 .Ft void
  65 .Fn updatepri "struct thread *td"
  66 .Sh DESCRIPTION
  67 Each process has three different priorities stored in
  68 .Vt "struct proc" :
  69 .Va p_usrpri ,
  70 .Va p_nativepri ,
  71 and
  72 .Va p_priority .
  73 .Pp
  74 The
  75 .Va p_usrpri
  76 member is the user priority of the process calculated from a process'
  77 estimated CPU time and nice level.
  78 .Pp
  79 The
  80 .Va p_nativepri
  81 member is the saved priority used by
  82 .Fn propagate_priority .
  83 When a process obtains a mutex, its priority is saved in
  84 .Va p_nativepri .
  85 While it holds the mutex, the process's priority may be bumped by another
  86 process that blocks on the mutex.
  87 When the process releases the mutex, then its priority is restored to the
  88 priority saved in
  89 .Va p_nativepri .
  90 .Pp
  91 The
  92 .Va p_priority
  93 member is the actual priority of the process and is used to determine what
  94 .Xr runqueue 9
  95 it runs on, for example.
  96 .Pp
  97 The
  98 .Fn curpriority_cmp
  99 function compares the cached priority of the currently running process with
 100 process
 101 .Fa p .
 102 If the currently running process has a higher priority, then it will return
 103 a value less than zero.
 104 If the current process has a lower priority, then it will return a value
 105 greater than zero.
 106 If the current process has the same priority as
 107 .Fa p ,
 108 then
 109 .Fn curpriority_cmp
 110 will return zero.
 111 The cached priority of the currently running process is updated when a process
 112 resumes from
 113 .Xr tsleep 9
 114 or returns to userland in
 115 .Fn userret
 116 and is stored in the private variable
 117 .Va curpriority .
 118 .Pp
 119 The
 120 .Fn maybe_resched
 121 function compares the priorities of the current thread and
 122 .Fa td .
 123 If
 124 .Fa td
 125 has a higher priority than the current thread, then a context switch is
 126 needed, and
 127 .Dv KEF_NEEDRESCHED
 128 is set.
 129 .Pp
 130 The
 131 .Fn propagate_priority
 132 looks at the process that owns the mutex
 133 .Fa p
 134 is blocked on.
 135 That process's priority is bumped to the priority of
 136 .Fa p
 137 if needed.
 138 If the process is currently running, then the function returns.
 139 If the process is on a
 140 .Xr runqueue 9 ,
 141 then the process is moved to the appropriate
 142 .Xr runqueue 9
 143 for its new priority.
 144 If the process is blocked on a mutex, its position in the list of
 145 processes blocked on the mutex in question is updated to reflect its new
 146 priority.
 147 Then, the function repeats the procedure using the process that owns the
 148 mutex just encountered.
 149 Note that a process's priorities are only bumped to the priority of the
 150 original process
 151 .Fa p ,
 152 not to the priority of the previously encountered process.
 153 .Pp
 154 The
 155 .Fn resetpriority
 156 function recomputes the user priority of the ksegrp
 157 .Fa kg
 158 (stored in
 159 .Va kg_user_pri )
 160 and calls
 161 .Fn maybe_resched
 162 to force a reschedule of each thread in the group if needed.
 163 .Pp
 164 The
 165 .Fn roundrobin
 166 function is used as a
 167 .Xr timeout 9
 168 function to force a reschedule every
 169 .Va sched_quantum
 170 ticks.
 171 .Pp
 172 The
 173 .Fn roundrobin_interval
 174 function simply returns the number of clock ticks in between reschedules
 175 triggered by
 176 .Fn roundrobin .
 177 Thus, all it does is return the current value of
 178 .Va sched_quantum .
 179 .Pp
 180 The
 181 .Fn sched_setup
 182 function is a
 183 .Xr SYSINIT 9
 184 that is called to start the callout driven scheduler functions.
 185 It just calls the
 186 .Fn roundrobin
 187 and
 188 .Fn schedcpu
 189 functions for the first time.
 190 After the initial call, the two functions will propagate themselves by
 191 registering their callout event again at the completion of the respective
 192 function.
 193 .Pp
 194 The
 195 .Fn schedclock
 196 function is called by
 197 .Fn statclock
 198 to adjust the priority of the currently running thread's ksegrp.
 199 It updates the group's estimated CPU time and then adjusts the priority via
 200 .Fn resetpriority .
 201 .Pp
 202 The
 203 .Fn schedcpu
 204 function updates all process priorities.
 205 First, it updates statistics that track how long processes have been in various
 206 process states.
 207 Secondly, it updates the estimated CPU time for the current process such
 208 that about 90% of the CPU usage is forgotten in 5 * load average seconds.
 209 For example, if the load average is 2.00,
 210 then at least 90% of the estimated CPU time for the process should be based
 211 on the amount of CPU time the process has had in the last 10 seconds.
 212 It then recomputes the priority of the process and moves it to the
 213 appropriate
 214 .Xr runqueue 9
 215 if necessary.
 216 Thirdly, it updates the %CPU estimate used by utilities such as
 217 .Xr ps 1
 218 and
 219 .Xr top 1
 220 so that 95% of the CPU usage is forgotten in 60 seconds.
 221 Once all process priorities have been updated,
 222 .Fn schedcpu
 223 calls
 224 .Fn vmmeter
 225 to update various other statistics including the load average.
 226 Finally, it schedules itself to run again in
 227 .Va hz
 228 clock ticks.
 229 .Pp
 230 The
 231 .Fn setrunnable
 232 function is used to change a process's state to be runnable.
 233 The process is placed on a
 234 .Xr runqueue 9
 235 if needed, and the swapper process is woken up and told to swap the process in
 236 if the process is swapped out.
 237 If the process has been asleep for at least one run of
 238 .Fn schedcpu ,
 239 then
 240 .Fn updatepri
 241 is used to adjust the priority of the process.
 242 .Pp
 243 The
 244 .Fn updatepri
 245 function is used to adjust the priority of a process that has been asleep.
 246 It retroactively decays the estimated CPU time of the process for each
 247 .Fn schedcpu
 248 event that the process was asleep.
 249 Finally, it calls
 250 .Fn resetpriority
 251 to adjust the priority of the process.
 252 .Sh SEE ALSO
 253 .Xr mi_switch 9 ,
 254 .Xr runqueue 9 ,
 255 .Xr sleepqueue 9 ,
 256 .Xr tsleep 9
 257 .Sh BUGS
 258 The
 259 .Va curpriority
 260 variable really should be per-CPU.
 261 In addition,
 262 .Fn maybe_resched
 263 should compare the priority of
 264 .Fa chk
 265 with that of each CPU, and then send an IPI to the processor with the lowest
 266 priority to trigger a reschedule if needed.
 267 .Pp
 268 Priority propagation is broken and is thus disabled by default.
 269 The
 270 .Va p_nativepri
 271 variable is only updated if a process does not obtain a sleep mutex on the
 272 first try.
 273 Also, if a process obtains more than one sleep mutex in this manner, and
 274 had its priority bumped in between, then
 275 .Va p_nativepri
 276 will be clobbered.