-@node 4.4BSD Scheduler, Coding Standards, References, Top
+@node 4.4BSD Scheduler
@appendix 4.4@acronym{BSD} Scheduler
@iftex
with all these requirements simultaneously.
For project 1, you must implement the scheduler described in this
-appendix. Our scheduler resembles the one described in @bibref{4.4BSD},
+appendix. Our scheduler resembles the one described in @bibref{McKusick},
which is one example of a @dfn{multilevel feedback queue} scheduler.
This type of scheduler maintains several queues of ready-to-run threads,
where each queue holds threads with a different priority. At any given
there is no chance that a kernel thread could see a newly increased
@func{timer_ticks} value but old scheduler data values.
+The 4.4@acronym{BSD} scheduler does not include priority donation.
+
@menu
* Thread Niceness::
* Calculating Priority::
* Calculating recent_cpu::
* Calculating load_avg::
+* 4.4BSD Scheduler Summary::
* Fixed-Point Real Arithmetic::
@end menu
formula given below. However, each thread also has an integer
@dfn{nice} value that determines how ``nice'' the thread should be to
other threads. A @var{nice} of zero does not affect thread priority. A
-positive @var{nice}, to the maximum of 20, increases the numeric
-priority of a thread, decreasing its effective priority, and causes it
-to give up some CPU time it would otherwise receive. On the other hand,
-a negative @var{nice}, to the minimum of -20, tends to take away CPU
-time from other threads.
+positive @var{nice}, to the maximum of 20, decreases the priority of a
+thread and causes it to give up some CPU time it would otherwise receive.
+On the other hand, a negative @var{nice}, to the minimum of -20, tends
+to take away CPU time from other threads.
The initial thread starts with a @var{nice} value of zero. Other
threads start with a @var{nice} value inherited from their parent
-thread. You
-must implement these functions, for which we have provided skeleton
-definitions in @file{threads/thread.c}.
+thread. You must implement the functions described below, which are for
+use by test programs. We have provided skeleton definitions for them in
+@file{threads/thread.c}.
@deftypefun int thread_get_nice (void)
Returns the current thread's @var{nice} value.
Our scheduler has 64 priorities and thus 64 ready queues, numbered 0
(@code{PRI_MIN}) through 63 (@code{PRI_MAX}). Lower numbers correspond
-to @emph{higher} priorities, so that priority 0 is the highest priority
-and priority 63 is the lowest. Thread priority is calculated initially
+to lower priorities, so that priority 0 is the lowest priority
+and priority 63 is the highest. Thread priority is calculated initially
at thread initialization. It is also recalculated once every fourth
clock tick, for every thread. In either case, it is determined by
the formula
-@center @t{@var{priority} = (@var{recent_cpu} / 4) + (@var{nice} * 2)},
+@center @t{@var{priority} = @code{PRI_MAX} - (@var{recent_cpu} / 4) - (@var{nice} * 2)},
@noindent where @var{recent_cpu} is an estimate of the CPU time the
thread has used recently (see below) and @var{nice} is the thread's
@math{f(t)} has a weight of approximately @math{1/e} at time @math{t+k},
approximately @am{1/e^2, 1/e**2} at time @am{t+2k, t+2*k}, and so on.
From the opposite direction, @math{f(t)} decays to weight @math{w} at
-@am{t = \log_aw, t = ln(w)/ln(a)}.
+time @am{t + \log_aw, t + ln(w)/ln(a)}.
The initial value of @var{recent_cpu} is 0 in the first thread
created, or the parent's value in other new threads. Each time a timer
interrupt occurs, @var{recent_cpu} is incremented by 1 for the running
-thread only. In addition, once per second the value of @var{recent_cpu}
+thread only, unless the idle thread is running. In addition, once per
+second the value of @var{recent_cpu}
is recalculated for every thread (whether running, ready, or blocked),
using this formula:
received ``recently,'' with the rate of decay inversely proportional to
the number of threads competing for the CPU.
-Because of assumptions made by some of the tests, @var{recent_cpu} must
-be updated exactly when the system tick counter reaches a multiple of a
-second, that is, when @code{timer_ticks () % TIMER_FREQ == 0}, and not
-at any other time.
+Assumptions made by some of the tests require that updates to
+@var{recent_cpu} be made exactly when the system tick counter reaches a
+multiple of a second, that is, when @code{timer_ticks () % TIMER_FREQ ==
+0}, and not at any other time.
-Take note that @var{recent_cpu} can be a negative quantity for a thread
-with a negative @var{nice} value. Negative values of @var{recent_cpu}
-are not changed to 0.
+The value of @var{recent_cpu} can be negative for a thread with a
+negative @var{nice} value. Do not clamp negative @var{recent_cpu} to 0.
+
+You may need to think about the order of calculations in this formula.
+We recommend computing the coefficient of @var{recent_cpu} first, then
+multiplying. Some students have reported that multiplying
+@var{load_avg} by @var{recent_cpu} directly can cause overflow.
You must implement @func{thread_get_recent_cpu}, for which there is a
skeleton in @file{threads/thread.c}.
nearest integer.
@end deftypefun
-@menu
-* Fixed-Point Real Arithmetic::
-@end menu
+@node 4.4BSD Scheduler Summary
+@section Summary
+
+The following formulas summarize the calculations required to implement the
+scheduler. They are not a complete description of scheduler requirements.
+
+Every thread has a @var{nice} value between -20 and 20 directly under
+its control. Each thread also has a priority, between 0
+(@code{PRI_MIN}) through 63 (@code{PRI_MAX}), which is recalculated
+using the following formula every fourth tick:
+
+@center @t{@var{priority} = @code{PRI_MAX} - (@var{recent_cpu} / 4) - (@var{nice} * 2)}.
+
+@var{recent_cpu} measures the amount of CPU time a thread has received
+``recently.'' On each timer tick, the running thread's @var{recent_cpu}
+is incremented by 1. Once per second, every thread's @var{recent_cpu}
+is updated this way:
+
+@center @t{@var{recent_cpu} = (2*@var{load_avg})/(2*@var{load_avg} + 1) * @var{recent_cpu} + @var{nice}}.
+
+@var{load_avg} estimates the average number of threads ready to run over
+the past minute. It is initialized to 0 at boot and recalculated once
+per second as follows:
+
+@center @t{@var{load_avg} = (59/60)*@var{load_avg} + (1/60)*@var{ready_threads}}.
+
+@noindent where @var{ready_threads} is the number of threads that are
+either running or ready to run at time of update (not including the idle
+thread).
@node Fixed-Point Real Arithmetic
@section Fixed-Point Real Arithmetic
section explains the basics.
The fundamental idea is to treat the rightmost bits of an integer as
-representing a fraction. For example, we can designate the lowest 10
+representing a fraction. For example, we can designate the lowest 14
bits of a signed 32-bit integer as fractional bits, so that an integer
-@var{x} represents the real number
+@m{x} represents the real number
@iftex
-@m{x/2^{10}}.
+@m{x/2^{14}}.
@end iftex
@ifnottex
-@m{x/(2**10)}, where ** represents exponentiation.
+@m{x/(2**14)}, where ** represents exponentiation.
@end ifnottex
-This is called a 21.10 fixed-point number representation, because there
-are 21 bits before the decimal point, 10 bits after it, and one sign
+This is called a 17.14 fixed-point number representation, because there
+are 17 bits before the decimal point, 14 bits after it, and one sign
bit.@footnote{Because we are working in binary, the ``decimal'' point
might more correctly be called the ``binary'' point, but the meaning
-should be clear.} A number in 21.10 format represents, at maximum, a
-value of @am{(2^{31} - 1) / 2^{10} \approx, (2**31 - 1)/(2**10) =
-approx.} 2,097,151.999.
+should be clear.} A number in 17.14 format represents, at maximum, a
+value of @am{(2^{31} - 1) / 2^{14} \approx, (2**31 - 1)/(2**14) =
+approx.} 131,071.999.
Suppose that we are using a @m{p.q} fixed-point format, and let @am{f =
2^q, f = 2**q}. By the definition above, we can convert an integer or
real number into @m{p.q} format by multiplying with @m{f}. For example,
-in 21.10 format the fraction 59/60 used in the calculation of
-@var{load_avg}, above, is @am{(59/60)2^{10}, 59/60*(2**10)} = 1,007
+in 17.14 format the fraction 59/60 used in the calculation of
+@var{load_avg}, above, is @am{(59/60)2^{14}, 59/60*(2**14)} = 16,111
(rounded to nearest). To convert a fixed-point value back to an
integer, divide by @m{f}. (The normal @samp{/} operator in C rounds
-down. To round to nearest, add @m{f / 2} before dividing.)
+toward zero, that is, it rounds positive numbers down and negative
+numbers up. To round to nearest, add @m{f / 2} to a positive number, or
+subtract it from a negative number, before dividing.)
Many operations on fixed-point numbers are straightforward. Let
@code{x} and @code{y} be fixed-point numbers, and let @code{n} be an
Multiplying two fixed-point values has two complications. First, the
decimal point of the result is @m{q} bits too far to the left. Consider
that @am{(59/60)(59/60), (59/60)*(59/60)} should be slightly less than
-1, but @tm{1,007\times 1,007}@nm{1,007*1,007} = 1,014,049 is much
-greater than @am{2^{10},2**10} = 1,024. Shifting @m{q} bits right, we
-get @tm{1,014,049/2^{10}}@nm{1,014,049/(2**10)} = 990, or about 0.97,
+1, but @tm{16,111\times 16,111}@nm{16,111*16,111} = 259,564,321 is much
+greater than @am{2^{14},2**14} = 16,384. Shifting @m{q} bits right, we
+get @tm{259,564,321/2^{14}}@nm{259,564,321/(2**14)} = 15,842, or about 0.97,
the correct answer. Second, the multiplication can overflow even though
-the answer is representable. For example, 128 in 21.10 format is
-@am{128 \times 2^{10}, 128*(2**10)} = 131,072 and its square @am{128^2,
-128**2} = 16,384 is well within the 21.10 range, but @tm{131,072^2 =
-2^{34}}@nm{131,072**2 = 2**34}, greater than the maximum signed 32-bit
+the answer is representable. For example, 64 in 17.14 format is
+@am{64 \times 2^{14}, 64*(2**14)} = 1,048,576 and its square @am{64^2,
+64**2} = 4,096 is well within the 17.14 range, but @tm{1,048,576^2 =
+2^{40}}@nm{1,048,576**2 = 2**40}, greater than the maximum signed 32-bit
integer value @am{2^{31} - 1, 2**31 - 1}. An easy solution is to do the
multiplication as a 64-bit operation. The product of @code{x} and
@code{y} is then @code{((int64_t) x) * y / f}.
-Dividing two fixed-point values has the opposite complications. The
+Dividing two fixed-point values has opposite issues. The
decimal point will be too far to the right, which we fix by shifting the
dividend @m{q} bits to the left before the division. The left shift
discards the top @m{q} bits of the dividend, which we can again fix by
@item Convert @code{n} to fixed point:
@tab @code{n * f}
-@item Convert @code{x} to integer (rounding down):
+@item Convert @code{x} to integer (rounding toward zero):
@tab @code{x / f}
@item Convert @code{x} to integer (rounding to nearest):
-@tab @code{(x + f / 2) / f}
+@tab @code{(x + f / 2) / f} if @code{x >= 0}, @*
+@code{(x - f / 2) / f} if @code{x <= 0}.
@item Add @code{x} and @code{y}:
@tab @code{x + y}
projects / pintos-anon / blobdiff