1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
|
<table class="head">
<tr>
<td class="head-ltitle">SCHEDULER(9)</td>
<td class="head-vol">Kernel Developer's Manual</td>
<td class="head-rtitle">SCHEDULER(9)</td>
</tr>
</table>
<div class="manual-text">
<section class="Sh">
<h1 class="Sh" id="NAME"><a class="permalink" href="#NAME">NAME</a></h1>
<p class="Pp"><code class="Nm">curpriority_cmp</code>,
<code class="Nm">maybe_resched</code>,
<code class="Nm">resetpriority</code>, <code class="Nm">roundrobin</code>,
<code class="Nm">roundrobin_interval</code>,
<code class="Nm">sched_setup</code>, <code class="Nm">schedclock</code>,
<code class="Nm">schedcpu</code>, <code class="Nm">setrunnable</code>,
<code class="Nm">updatepri</code> — <span class="Nd">perform
round-robin scheduling of runnable processes</span></p>
</section>
<section class="Sh">
<h1 class="Sh" id="SYNOPSIS"><a class="permalink" href="#SYNOPSIS">SYNOPSIS</a></h1>
<p class="Pp"><code class="In">#include
<<a class="In">sys/param.h</a>></code>
<br/>
<code class="In">#include <<a class="In">sys/proc.h</a>></code></p>
<p class="Pp"><var class="Ft">int</var>
<br/>
<code class="Fn">curpriority_cmp</code>(<var class="Fa" style="white-space: nowrap;">struct
proc *p</var>);</p>
<p class="Pp"><var class="Ft">void</var>
<br/>
<code class="Fn">maybe_resched</code>(<var class="Fa" style="white-space: nowrap;">struct
thread *td</var>);</p>
<p class="Pp"><var class="Ft">void</var>
<br/>
<code class="Fn">propagate_priority</code>(<var class="Fa" style="white-space: nowrap;">struct
proc *p</var>);</p>
<p class="Pp"><var class="Ft">void</var>
<br/>
<code class="Fn">resetpriority</code>(<var class="Fa" style="white-space: nowrap;">struct
ksegrp *kg</var>);</p>
<p class="Pp"><var class="Ft">void</var>
<br/>
<code class="Fn">roundrobin</code>(<var class="Fa" style="white-space: nowrap;">void
*arg</var>);</p>
<p class="Pp"><var class="Ft">int</var>
<br/>
<code class="Fn">roundrobin_interval</code>(<var class="Fa" style="white-space: nowrap;">void</var>);</p>
<p class="Pp"><var class="Ft">void</var>
<br/>
<code class="Fn">sched_setup</code>(<var class="Fa" style="white-space: nowrap;">void
*dummy</var>);</p>
<p class="Pp"><var class="Ft">void</var>
<br/>
<code class="Fn">schedclock</code>(<var class="Fa" style="white-space: nowrap;">struct
thread *td</var>);</p>
<p class="Pp"><var class="Ft">void</var>
<br/>
<code class="Fn">schedcpu</code>(<var class="Fa" style="white-space: nowrap;">void
*arg</var>);</p>
<p class="Pp"><var class="Ft">void</var>
<br/>
<code class="Fn">setrunnable</code>(<var class="Fa" style="white-space: nowrap;">struct
thread *td</var>);</p>
<p class="Pp"><var class="Ft">void</var>
<br/>
<code class="Fn">updatepri</code>(<var class="Fa" style="white-space: nowrap;">struct
thread *td</var>);</p>
</section>
<section class="Sh">
<h1 class="Sh" id="DESCRIPTION"><a class="permalink" href="#DESCRIPTION">DESCRIPTION</a></h1>
<p class="Pp">Each process has three different priorities stored in
<var class="Vt">struct proc</var>: <var class="Va">p_usrpri</var>,
<var class="Va">p_nativepri</var>, and <var class="Va">p_priority</var>.</p>
<p class="Pp">The <var class="Va">p_usrpri</var> member is the user priority of
the process calculated from a process' estimated CPU time and nice
level.</p>
<p class="Pp" id="propagate_priority">The <var class="Va">p_nativepri</var>
member is the saved priority used by
<a class="permalink" href="#propagate_priority"><code class="Fn">propagate_priority</code></a>().
When a process obtains a mutex, its priority is saved in
<var class="Va">p_nativepri</var>. While it holds the mutex, the process's
priority may be bumped by another process that blocks on the mutex. When the
process releases the mutex, then its priority is restored to the priority
saved in <var class="Va">p_nativepri</var>.</p>
<p class="Pp">The <var class="Va">p_priority</var> member is the actual priority
of the process and is used to determine what <a class="Xr">runqueue(9)</a>
it runs on, for example.</p>
<p class="Pp" id="curpriority_cmp">The
<a class="permalink" href="#curpriority_cmp"><code class="Fn">curpriority_cmp</code></a>()
function compares the cached priority of the currently running process with
process <var class="Fa">p</var>. If the currently running process has a
higher priority, then it will return a value less than zero. If the current
process has a lower priority, then it will return a value greater than zero.
If the current process has the same priority as <var class="Fa">p</var>,
then <code class="Fn">curpriority_cmp</code>() will return zero. The cached
priority of the currently running process is updated when a process resumes
from <a class="Xr">tsleep(9)</a> or returns to userland in
<a class="permalink" href="#userret"><code class="Fn" id="userret">userret</code></a>()
and is stored in the private variable <var class="Va">curpriority</var>.</p>
<p class="Pp" id="maybe_resched">The
<a class="permalink" href="#maybe_resched"><code class="Fn">maybe_resched</code></a>()
function compares the priorities of the current thread and
<var class="Fa">td</var>. If <var class="Fa">td</var> has a higher priority
than the current thread, then a context switch is needed, and
<code class="Dv">KEF_NEEDRESCHED</code> is set.</p>
<p class="Pp" id="propagate_priority~2">The
<a class="permalink" href="#propagate_priority~2"><code class="Fn">propagate_priority</code></a>()
looks at the process that owns the mutex <var class="Fa">p</var> is blocked
on. That process's priority is bumped to the priority of
<var class="Fa">p</var> if needed. If the process is currently running, then
the function returns. If the process is on a <a class="Xr">runqueue(9)</a>,
then the process is moved to the appropriate <a class="Xr">runqueue(9)</a>
for its new priority. If the process is blocked on a mutex, its position in
the list of processes blocked on the mutex in question is updated to reflect
its new priority. Then, the function repeats the procedure using the process
that owns the mutex just encountered. Note that a process's priorities are
only bumped to the priority of the original process <var class="Fa">p</var>,
not to the priority of the previously encountered process.</p>
<p class="Pp" id="resetpriority">The
<a class="permalink" href="#resetpriority"><code class="Fn">resetpriority</code></a>()
function recomputes the user priority of the ksegrp <var class="Fa">kg</var>
(stored in <var class="Va">kg_user_pri</var>) and calls
<code class="Fn">maybe_resched</code>() to force a reschedule of each thread
in the group if needed.</p>
<p class="Pp" id="roundrobin">The
<a class="permalink" href="#roundrobin"><code class="Fn">roundrobin</code></a>()
function is used as a <a class="Xr">timeout(9)</a> function to force a
reschedule every <var class="Va">sched_quantum</var> ticks.</p>
<p class="Pp" id="roundrobin_interval">The
<a class="permalink" href="#roundrobin_interval"><code class="Fn">roundrobin_interval</code></a>()
function simply returns the number of clock ticks in between reschedules
triggered by <code class="Fn">roundrobin</code>(). Thus, all it does is
return the current value of <var class="Va">sched_quantum</var>.</p>
<p class="Pp" id="sched_setup">The
<a class="permalink" href="#sched_setup"><code class="Fn">sched_setup</code></a>()
function is a <a class="Xr">SYSINIT(9)</a> that is called to start the
callout driven scheduler functions. It just calls the
<code class="Fn">roundrobin</code>() and <code class="Fn">schedcpu</code>()
functions for the first time. After the initial call, the two functions will
propagate themselves by registering their callout event again at the
completion of the respective function.</p>
<p class="Pp" id="schedclock">The
<a class="permalink" href="#schedclock"><code class="Fn">schedclock</code></a>()
function is called by
<a class="permalink" href="#statclock"><code class="Fn" id="statclock">statclock</code></a>()
to adjust the priority of the currently running thread's ksegrp. It updates
the group's estimated CPU time and then adjusts the priority via
<code class="Fn">resetpriority</code>().</p>
<p class="Pp" id="schedcpu">The
<a class="permalink" href="#schedcpu"><code class="Fn">schedcpu</code></a>()
function updates all process priorities. First, it updates statistics that
track how long processes have been in various process states. Secondly, it
updates the estimated CPU time for the current process such that about 90%
of the CPU usage is forgotten in 5 * load average seconds. For example, if
the load average is 2.00, then at least 90% of the estimated CPU time for
the process should be based on the amount of CPU time the process has had in
the last 10 seconds. It then recomputes the priority of the process and
moves it to the appropriate <a class="Xr">runqueue(9)</a> if necessary.
Thirdly, it updates the %CPU estimate used by utilities such as
<a class="Xr">ps(1)</a> and <a class="Xr">top(1)</a> so that 95% of the CPU
usage is forgotten in 60 seconds. Once all process priorities have been
updated, <code class="Fn">schedcpu</code>() calls
<a class="permalink" href="#vmmeter"><code class="Fn" id="vmmeter">vmmeter</code></a>()
to update various other statistics including the load average. Finally, it
schedules itself to run again in <var class="Va">hz</var> clock ticks.</p>
<p class="Pp" id="setrunnable">The
<a class="permalink" href="#setrunnable"><code class="Fn">setrunnable</code></a>()
function is used to change a process's state to be runnable. The process is
placed on a <a class="Xr">runqueue(9)</a> if needed, and the swapper process
is woken up and told to swap the process in if the process is swapped out.
If the process has been asleep for at least one run of
<code class="Fn">schedcpu</code>(), then <code class="Fn">updatepri</code>()
is used to adjust the priority of the process.</p>
<p class="Pp" id="updatepri">The
<a class="permalink" href="#updatepri"><code class="Fn">updatepri</code></a>()
function is used to adjust the priority of a process that has been asleep.
It retroactively decays the estimated CPU time of the process for each
<code class="Fn">schedcpu</code>() event that the process was asleep.
Finally, it calls <code class="Fn">resetpriority</code>() to adjust the
priority of the process.</p>
</section>
<section class="Sh">
<h1 class="Sh" id="SEE_ALSO"><a class="permalink" href="#SEE_ALSO">SEE
ALSO</a></h1>
<p class="Pp"><a class="Xr">mi_switch(9)</a>, <a class="Xr">runqueue(9)</a>,
<a class="Xr">sleepqueue(9)</a>, <a class="Xr">tsleep(9)</a></p>
</section>
<section class="Sh">
<h1 class="Sh" id="BUGS"><a class="permalink" href="#BUGS">BUGS</a></h1>
<p class="Pp">The <var class="Va">curpriority</var> variable really should be
per-CPU. In addition, <code class="Fn">maybe_resched</code>() should compare
the priority of <var class="Fa">chk</var> with that of each CPU, and then
send an IPI to the processor with the lowest priority to trigger a
reschedule if needed.</p>
<p class="Pp">Priority propagation is broken and is thus disabled by default.
The <var class="Va">p_nativepri</var> variable is only updated if a process
does not obtain a sleep mutex on the first try. Also, if a process obtains
more than one sleep mutex in this manner, and had its priority bumped in
between, then <var class="Va">p_nativepri</var> will be clobbered.</p>
</section>
</div>
<table class="foot">
<tr>
<td class="foot-date">November 3, 2000</td>
<td class="foot-os">FreeBSD 15.0</td>
</tr>
</table>
|
