Multiple facets of the scheduler require data to be updated after a
certain number of timer ticks. In every case, these updates should
occur before any ordinary kernel thread has a chance to run, so that
-there is no chance that a kernel thread could see @func{timer_ticks}
-increased but these old values for these data.
+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
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}. by test programs
@deftypefun int thread_get_nice (void)
Returns the current thread's @var{nice} value.
@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
+
+This section summarizes the calculations required to implement the
+scheduler. It is 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 whenever the value of either term changes:
+
+@center @t{@var{priority} = (@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