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 Because of assumptions made by some of the tests, @var{recent_cpu} must
183 be updated exactly when the system tick counter reaches a multiple of a
184 second, that is, when @code{timer_ticks () % TIMER_FREQ == 0}, and not
187 Take note that @var{recent_cpu} can be a negative quantity for a thread
188 with a negative @var{nice} value. Negative values of @var{recent_cpu}
189 are not changed to 0.
191 You must implement @func{thread_get_recent_cpu}, for which there is a
192 skeleton in @file{threads/thread.c}.
194 @deftypefun int thread_get_recent_cpu (void)
195 Returns 100 times the current thread's @var{recent_cpu} value, rounded
196 to the nearest integer.
199 @node Calculating load_avg
200 @section Calculating @var{load_avg}
202 Finally, @var{load_avg}, often known as the system load average,
203 estimates the average number of threads ready to run over the past
204 minute. Like @var{recent_cpu}, it is an exponentially weighted moving
205 average. Unlike @var{priority} and @var{recent_cpu}, @var{load_avg} is
206 system-wide, not thread-specific. At system boot, it is initialized to
207 0. Once per second thereafter, it is updated according to the following
210 @center @t{@var{load_avg} = (59/60)*@var{load_avg} + (1/60)*@var{ready_threads}},
212 @noindent where @var{ready_threads} is the number of threads that are
213 either running or ready to run at time of update (not including the idle
216 Because of assumptions made by some of the tests, @var{load_avg} must be
217 updated exactly when the system tick counter reaches a multiple of a
218 second, that is, when @code{timer_ticks () % TIMER_FREQ == 0}, and not
221 You must implement @func{thread_get_load_avg}, for which there is a
222 skeleton in @file{threads/thread.c}.
224 @deftypefun int thread_get_load_avg (void)
225 Returns 100 times the current system load average, rounded to the
230 * Fixed-Point Real Arithmetic::
233 @node Fixed-Point Real Arithmetic
234 @section Fixed-Point Real Arithmetic
236 In the formulas above, @var{priority}, @var{nice}, and
237 @var{ready_threads} are integers, but @var{recent_cpu} and @var{load_avg}
238 are real numbers. Unfortunately, Pintos does not support floating-point
239 arithmetic in the kernel, because it would
240 complicate and slow the kernel. Real kernels often have the same
241 limitation, for the same reason. This means that calculations on real
242 quantities must be simulated using integers. This is not
243 difficult, but many students do not know how to do it. This
244 section explains the basics.
246 The fundamental idea is to treat the rightmost bits of an integer as
247 representing a fraction. For example, we can designate the lowest 10
248 bits of a signed 32-bit integer as fractional bits, so that an integer
249 @var{x} represents the real number
254 @m{x/(2**10)}, where ** represents exponentiation.
256 This is called a 21.10 fixed-point number representation, because there
257 are 21 bits before the decimal point, 10 bits after it, and one sign
258 bit.@footnote{Because we are working in binary, the ``decimal'' point
259 might more correctly be called the ``binary'' point, but the meaning
260 should be clear.} A number in 21.10 format represents, at maximum, a
261 value of @am{(2^{31} - 1) / 2^{10} \approx, (2**31 - 1)/(2**10) =
262 approx.} 2,097,151.999.
264 Suppose that we are using a @m{p.q} fixed-point format, and let @am{f =
265 2^q, f = 2**q}. By the definition above, we can convert an integer or
266 real number into @m{p.q} format by multiplying with @m{f}. For example,
267 in 21.10 format the fraction 59/60 used in the calculation of
268 @var{load_avg}, above, is @am{(59/60)2^{10}, 59/60*(2**10)} = 1,007
269 (rounded to nearest). To convert a fixed-point value back to an
270 integer, divide by @m{f}. (The normal @samp{/} operator in C rounds
271 down. To round to nearest, add @m{f / 2} before dividing.)
273 Many operations on fixed-point numbers are straightforward. Let
274 @code{x} and @code{y} be fixed-point numbers, and let @code{n} be an
275 integer. Then the sum of @code{x} and @code{y} is @code{x + y} and
276 their difference is @code{x - y}. The sum of @code{x} and @code{n} is
277 @code{x + n * f}; difference, @code{x - n * f}; product, @code{x * n};
278 quotient, @code{x / n}.
280 Multiplying two fixed-point values has two complications. First, the
281 decimal point of the result is @m{q} bits too far to the left. Consider
282 that @am{(59/60)(59/60), (59/60)*(59/60)} should be slightly less than
283 1, but @tm{1,007\times 1,007}@nm{1,007*1,007} = 1,014,049 is much
284 greater than @am{2^{10},2**10} = 1,024. Shifting @m{q} bits right, we
285 get @tm{1,014,049/2^{10}}@nm{1,014,049/(2**10)} = 990, or about 0.97,
286 the correct answer. Second, the multiplication can overflow even though
287 the answer is representable. For example, 128 in 21.10 format is
288 @am{128 \times 2^{10}, 128*(2**10)} = 131,072 and its square @am{128^2,
289 128**2} = 16,384 is well within the 21.10 range, but @tm{131,072^2 =
290 2^{34}}@nm{131,072**2 = 2**34}, greater than the maximum signed 32-bit
291 integer value @am{2^{31} - 1, 2**31 - 1}. An easy solution is to do the
292 multiplication as a 64-bit operation. The product of @code{x} and
293 @code{y} is then @code{((int64_t) x) * y / f}.
295 Dividing two fixed-point values has the opposite complications. The
296 decimal point will be too far to the right, which we fix by shifting the
297 dividend @m{q} bits to the left before the division. The left shift
298 discards the top @m{q} bits of the dividend, which we can again fix by
299 doing the division in 64 bits. Thus, the quotient when @code{x} is
300 divided by @code{y} is @code{((int64_t) x) * f / y}.
302 This section has consistently used multiplication or division by @m{f},
303 instead of @m{q}-bit shifts, for two reasons. First, multiplication and
304 division do not have the surprising operator precedence of the C shift
305 operators. Second, multiplication and division are well-defined on
306 negative operands, but the C shift operators are not. Take care with
307 these issues in your implementation.
309 The following table summarizes how fixed-point arithmetic operations can
310 be implemented in C. In the table, @code{x} and @code{y} are
311 fixed-point numbers, @code{n} is an integer, fixed-point numbers are in
312 signed @m{p.q} format where @m{p + q = 31}, and @code{f} is @code{1 <<
318 @multitable @columnfractions .5 .5
319 @item Convert @code{n} to fixed point:
322 @item Convert @code{x} to integer (rounding down):
325 @item Convert @code{x} to integer (rounding to nearest):
326 @tab @code{(x + f / 2) / f}
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}: