X-Git-Url: https://pintos-os.org/cgi-bin/gitweb.cgi?a=blobdiff_plain;ds=sidebyside;f=doc%2F44bsd.texi;h=d066ee7f6806ed579db59095572818173d5bc7a8;hb=2a7b349c85aef5b3e54d3c4850a069a7c448af9a;hp=3bbce0d572c2a6b3cc051920fa7caa7906b439ae;hpb=4824d681ff6abb0014ffed11de3d2877ca1246b7;p=pintos-anon diff --git a/doc/44bsd.texi b/doc/44bsd.texi index 3bbce0d..d066ee7 100644 --- a/doc/44bsd.texi +++ b/doc/44bsd.texi @@ -58,11 +58,14 @@ occur before any ordinary kernel thread has a chance to run, so that 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 @@ -162,7 +165,8 @@ From the opposite direction, @math{f(t)} decays to weight @math{w} at 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: @@ -179,14 +183,18 @@ current value of @var{recent_cpu} decays to a weight of .1 in 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}. @@ -226,9 +234,35 @@ Returns 100 times the current system load average, rounded to the 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 @@ -244,31 +278,33 @@ difficult, but many students do not know how to do it. This 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 @@ -280,19 +316,19 @@ quotient, @code{x / n}. 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 @@ -319,11 +355,12 @@ q}: @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}