Add summary of scheduler.

[pintos-anon] / doc / 44bsd.texi

diff --git a/doc/44bsd.texi b/doc/44bsd.texi
index 4d61c17afb995b8daf753c6a57ad42f4d1419bf8..18c5a61abd34022d9b207f12f67f4e278cbf4e1e 100644 (file)
--- a/doc/44bsd.texi
+++ b/doc/44bsd.texi
@@ -52,11 +52,20 @@ time, the scheduler chooses a thread from the highest-priority non-empty
 queue.  If the highest-priority queue contains multiple threads, then
 they run in ``round robin'' order.
 
+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 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
 
@@ -75,9 +84,9 @@ 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}.  by test programs
 
 @deftypefun int thread_get_nice (void)
 Returns the current thread's @var{nice} value.
@@ -173,14 +182,13 @@ 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 must implement @func{thread_get_recent_cpu}, for which there is a
 skeleton in @file{threads/thread.c}.
@@ -220,9 +228,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
@@ -313,11 +347,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}