1 @node 4.4BSD Scheduler, Coding Standards, References, Top
2 @appendix 4.4@acronym{BSD} Scheduler
36 The goal of a general-purpose scheduler is to balance threads' different
37 scheduling needs. Threads that perform a lot of I/O require a fast
38 response time to keep input and output devices busy, but need little CPU
39 time. On the other hand, compute-bound threads need to receive a lot of
40 CPU time to finish their work, but have no requirement for fast response
41 time. Other threads lie somewhere in between, with periods of I/O
42 punctuated by periods of computation, and thus have requirements that
43 vary over time. A well-designed scheduler can often accommodate threads
44 with all these requirements simultaneously.
46 For project 1, you must implement the scheduler described in this
47 appendix. Our scheduler resembles the one described in @bibref{4.4BSD},
48 which is one example of a @dfn{multilevel feedback queue} scheduler.
49 This type of scheduler maintains several queues of ready-to-run threads,
50 where each queue holds threads with a different priority. At any given
51 time, the scheduler chooses a thread from the highest-priority non-empty
52 queue. If the highest-priority queue contains multiple threads, then
53 they run in ``round robin'' order.
55 Multiple facets of the scheduler require data to be updated after a
56 certain number of timer ticks. In every case, these updates should
57 occur before any ordinary kernel thread has a chance to run, so that
58 there is no chance that a kernel thread could see a newly increased
59 @func{timer_ticks} value but old scheduler data values.
63 * Calculating Priority::
64 * Calculating recent_cpu::
65 * Calculating load_avg::
66 * Fixed-Point Real Arithmetic::
72 Thread priority is dynamically determined by the scheduler using a
73 formula given below. However, each thread also has an integer
74 @dfn{nice} value that determines how ``nice'' the thread should be to
75 other threads. A @var{nice} of zero does not affect thread priority. A
76 positive @var{nice}, to the maximum of 20, increases the numeric
77 priority of a thread, decreasing its effective priority, and causes it
78 to give up some CPU time it would otherwise receive. On the other hand,
79 a negative @var{nice}, to the minimum of -20, tends to take away CPU
80 time from other threads.
82 The initial thread starts with a @var{nice} value of zero. Other
83 threads start with a @var{nice} value inherited from their parent
84 thread. You must implement the functions described below, which are for
85 use by test programs. We have provided skeleton definitions for them in
86 @file{threads/thread.c}. by test programs
88 @deftypefun int thread_get_nice (void)
89 Returns the current thread's @var{nice} value.
92 @deftypefun void thread_set_nice (int @var{new_nice})
93 Sets the current thread's @var{nice} value to @var{new_nice} and
94 recalculates the thread's priority based on the new value
95 (@pxref{Calculating Priority}). If the running thread no longer has the
96 highest priority, yields.
99 @node Calculating Priority
100 @section Calculating Priority
102 Our scheduler has 64 priorities and thus 64 ready queues, numbered 0
103 (@code{PRI_MIN}) through 63 (@code{PRI_MAX}). Lower numbers correspond
104 to @emph{higher} priorities, so that priority 0 is the highest priority
105 and priority 63 is the lowest. Thread priority is calculated initially
106 at thread initialization. It is also recalculated once every fourth
107 clock tick, for every thread. In either case, it is determined by
110 @center @t{@var{priority} = (@var{recent_cpu} / 4) + (@var{nice} * 2)},
112 @noindent where @var{recent_cpu} is an estimate of the CPU time the
113 thread has used recently (see below) and @var{nice} is the thread's
114 @var{nice} value. The coefficients @math{1/4} and 2 on @var{recent_cpu}
115 and @var{nice}, respectively, have been found to work well in practice
116 but lack deeper meaning. The calculated @var{priority} is always
117 adjusted to lie in the valid range @code{PRI_MIN} to @code{PRI_MAX}.
119 This formula gives a thread that has received CPU
120 time recently lower priority for being reassigned the CPU the next
121 time the scheduler runs. This is key to preventing starvation: a
122 thread that has not received any CPU time recently will have a
123 @var{recent_cpu} of 0, which barring a high @var{nice} value should
124 ensure that it receives CPU time soon.
126 @node Calculating recent_cpu
127 @section Calculating @var{recent_cpu}
129 We wish @var{recent_cpu} to measure how much CPU time each process has
130 received ``recently.'' Furthermore, as a refinement, more recent CPU
131 time should be weighted more heavily than less recent CPU time. One
132 approach would use an array of @var{n} elements to
133 track the CPU time received in each of the last @var{n} seconds.
134 However, this approach requires O(@var{n}) space per thread and
135 O(@var{n}) time per calculation of a new weighted average.
137 Instead, we use a @dfn{exponentially weighted moving average}, which
138 takes this general form:
140 @center @tm{x(0) = f(0),}@nm{x(0) = f(0),}
141 @center @tm{x(t) = ax(t-1) + (1-a)f(t),}@nm{x(t) = a*x(t-1) + f(t),}
142 @center @tm{a = k/(k+1),}@nm{a = k/(k+1),}
144 @noindent where @math{x(t)} is the moving average at integer time @am{t
145 \ge 0, t >= 0}, @math{f(t)} is the function being averaged, and @math{k
146 > 0} controls the rate of decay. We can iterate the formula over a few
149 @center @math{x(1) = f(1)},
150 @center @am{x(2) = af(1) + f(2), x(2) = a*f(1) + f(2)},
151 @center @am{\vdots, ...}
152 @center @am{x(5) = a^4f(1) + a^3f(2) + a^2f(3) + af(4) + f(5), x(5) = a**4*f(1) + a**3*f(2) + a**2*f(3) + a*f(4) + f(5)}.
154 @noindent The value of @math{f(t)} has a weight of 1 at time @math{t}, a
155 weight of @math{a} at time @math{t+1}, @am{a^2, a**2} at time
156 @math{t+2}, and so on. We can also relate @math{x(t)} to @math{k}:
157 @math{f(t)} has a weight of approximately @math{1/e} at time @math{t+k},
158 approximately @am{1/e^2, 1/e**2} at time @am{t+2k, t+2*k}, and so on.
159 From the opposite direction, @math{f(t)} decays to weight @math{w} at
160 @am{t = \log_aw, t = ln(w)/ln(a)}.
162 The initial value of @var{recent_cpu} is 0 in the first thread
163 created, or the parent's value in other new threads. Each time a timer
164 interrupt occurs, @var{recent_cpu} is incremented by 1 for the running
165 thread only. In addition, once per second the value of @var{recent_cpu}
166 is recalculated for every thread (whether running, ready, or blocked),
169 @center @t{@var{recent_cpu} = (2*@var{load_avg})/(2*@var{load_avg} + 1) * @var{recent_cpu} + @var{nice}},
171 @noindent where @var{load_avg} is a moving average of the number of
172 threads ready to run (see below). If @var{load_avg} is 1, indicating
173 that a single thread, on average, is competing for the CPU, then the
174 current value of @var{recent_cpu} decays to a weight of .1 in
175 @am{\log_{2/3}.1 \approx 6, ln(2/3)/ln(.1) = approx. 6} seconds; if
176 @var{load_avg} is 2, then decay to a weight of .1 takes @am{\log_{3/4}.1
177 \approx 8, ln(3/4)/ln(.1) = approx. 8} seconds. The effect is that
178 @var{recent_cpu} estimates the amount of CPU time the thread has
179 received ``recently,'' with the rate of decay inversely proportional to
180 the number of threads competing for the CPU.
182 Assumptions made by some of the tests require that updates to
183 @var{recent_cpu} be made exactly when the system tick counter reaches a
184 multiple of a second, that is, when @code{timer_ticks () % TIMER_FREQ ==
185 0}, and not at any other time.
187 The value of @var{recent_cpu} can be negative for a thread with a
188 negative @var{nice} value. Do not clamp negative @var{recent_cpu} to 0.
190 You must implement @func{thread_get_recent_cpu}, for which there is a
191 skeleton in @file{threads/thread.c}.
193 @deftypefun int thread_get_recent_cpu (void)
194 Returns 100 times the current thread's @var{recent_cpu} value, rounded
195 to the nearest integer.
198 @node Calculating load_avg
199 @section Calculating @var{load_avg}
201 Finally, @var{load_avg}, often known as the system load average,
202 estimates the average number of threads ready to run over the past
203 minute. Like @var{recent_cpu}, it is an exponentially weighted moving
204 average. Unlike @var{priority} and @var{recent_cpu}, @var{load_avg} is
205 system-wide, not thread-specific. At system boot, it is initialized to
206 0. Once per second thereafter, it is updated according to the following
209 @center @t{@var{load_avg} = (59/60)*@var{load_avg} + (1/60)*@var{ready_threads}},
211 @noindent where @var{ready_threads} is the number of threads that are
212 either running or ready to run at time of update (not including the idle
215 Because of assumptions made by some of the tests, @var{load_avg} must be
216 updated exactly when the system tick counter reaches a multiple of a
217 second, that is, when @code{timer_ticks () % TIMER_FREQ == 0}, and not
220 You must implement @func{thread_get_load_avg}, for which there is a
221 skeleton in @file{threads/thread.c}.
223 @deftypefun int thread_get_load_avg (void)
224 Returns 100 times the current system load average, rounded to the
229 * Fixed-Point Real Arithmetic::
232 @node Fixed-Point Real Arithmetic
233 @section Fixed-Point Real Arithmetic
235 In the formulas above, @var{priority}, @var{nice}, and
236 @var{ready_threads} are integers, but @var{recent_cpu} and @var{load_avg}
237 are real numbers. Unfortunately, Pintos does not support floating-point
238 arithmetic in the kernel, because it would
239 complicate and slow the kernel. Real kernels often have the same
240 limitation, for the same reason. This means that calculations on real
241 quantities must be simulated using integers. This is not
242 difficult, but many students do not know how to do it. This
243 section explains the basics.
245 The fundamental idea is to treat the rightmost bits of an integer as
246 representing a fraction. For example, we can designate the lowest 10
247 bits of a signed 32-bit integer as fractional bits, so that an integer
248 @var{x} represents the real number
253 @m{x/(2**10)}, where ** represents exponentiation.
255 This is called a 21.10 fixed-point number representation, because there
256 are 21 bits before the decimal point, 10 bits after it, and one sign
257 bit.@footnote{Because we are working in binary, the ``decimal'' point
258 might more correctly be called the ``binary'' point, but the meaning
259 should be clear.} A number in 21.10 format represents, at maximum, a
260 value of @am{(2^{31} - 1) / 2^{10} \approx, (2**31 - 1)/(2**10) =
261 approx.} 2,097,151.999.
263 Suppose that we are using a @m{p.q} fixed-point format, and let @am{f =
264 2^q, f = 2**q}. By the definition above, we can convert an integer or
265 real number into @m{p.q} format by multiplying with @m{f}. For example,
266 in 21.10 format the fraction 59/60 used in the calculation of
267 @var{load_avg}, above, is @am{(59/60)2^{10}, 59/60*(2**10)} = 1,007
268 (rounded to nearest). To convert a fixed-point value back to an
269 integer, divide by @m{f}. (The normal @samp{/} operator in C rounds
270 down. To round to nearest, add @m{f / 2} before dividing.)
272 Many operations on fixed-point numbers are straightforward. Let
273 @code{x} and @code{y} be fixed-point numbers, and let @code{n} be an
274 integer. Then the sum of @code{x} and @code{y} is @code{x + y} and
275 their difference is @code{x - y}. The sum of @code{x} and @code{n} is
276 @code{x + n * f}; difference, @code{x - n * f}; product, @code{x * n};
277 quotient, @code{x / n}.
279 Multiplying two fixed-point values has two complications. First, the
280 decimal point of the result is @m{q} bits too far to the left. Consider
281 that @am{(59/60)(59/60), (59/60)*(59/60)} should be slightly less than
282 1, but @tm{1,007\times 1,007}@nm{1,007*1,007} = 1,014,049 is much
283 greater than @am{2^{10},2**10} = 1,024. Shifting @m{q} bits right, we
284 get @tm{1,014,049/2^{10}}@nm{1,014,049/(2**10)} = 990, or about 0.97,
285 the correct answer. Second, the multiplication can overflow even though
286 the answer is representable. For example, 128 in 21.10 format is
287 @am{128 \times 2^{10}, 128*(2**10)} = 131,072 and its square @am{128^2,
288 128**2} = 16,384 is well within the 21.10 range, but @tm{131,072^2 =
289 2^{34}}@nm{131,072**2 = 2**34}, greater than the maximum signed 32-bit
290 integer value @am{2^{31} - 1, 2**31 - 1}. An easy solution is to do the
291 multiplication as a 64-bit operation. The product of @code{x} and
292 @code{y} is then @code{((int64_t) x) * y / f}.
294 Dividing two fixed-point values has the opposite complications. The
295 decimal point will be too far to the right, which we fix by shifting the
296 dividend @m{q} bits to the left before the division. The left shift
297 discards the top @m{q} bits of the dividend, which we can again fix by
298 doing the division in 64 bits. Thus, the quotient when @code{x} is
299 divided by @code{y} is @code{((int64_t) x) * f / y}.
301 This section has consistently used multiplication or division by @m{f},
302 instead of @m{q}-bit shifts, for two reasons. First, multiplication and
303 division do not have the surprising operator precedence of the C shift
304 operators. Second, multiplication and division are well-defined on
305 negative operands, but the C shift operators are not. Take care with
306 these issues in your implementation.
308 The following table summarizes how fixed-point arithmetic operations can
309 be implemented in C. In the table, @code{x} and @code{y} are
310 fixed-point numbers, @code{n} is an integer, fixed-point numbers are in
311 signed @m{p.q} format where @m{p + q = 31}, and @code{f} is @code{1 <<
317 @multitable @columnfractions .5 .5
318 @item Convert @code{n} to fixed point:
321 @item Convert @code{x} to integer (rounding toward zero):
324 @item Convert @code{x} to integer (rounding to nearest):
325 @tab @code{(x + f / 2) / f} if @code{x >= 0}, @*
326 @code{(x - f / 2) / f} if @code{x <= 0}.
328 @item Add @code{x} and @code{y}:
331 @item Subtract @code{y} from @code{x}:
334 @item Add @code{x} and @code{n}:
335 @tab @code{x + n * f}
337 @item Subtract @code{n} from @code{x}:
338 @tab @code{x - n * f}
340 @item Multiply @code{x} by @code{y}:
341 @tab @code{((int64_t) x) * y / f}
343 @item Multiply @code{x} by @code{n}:
346 @item Divide @code{x} by @code{y}:
347 @tab @code{((int64_t) x) * f / y}
349 @item Divide @code{x} by @code{n}: