Invert the priority scheme, so that PRI_MIN is now the lowest priority

[pintos-anon] / doc / threads.texi

diff --git a/doc/threads.texi b/doc/threads.texi
index 2f42e3dc5979b8f8ab33fd79db7af020a285c932..d83b52f4525770b2a89d7768713426e1ad1821b0 100644 (file)
--- a/doc/threads.texi
+++ b/doc/threads.texi
@@ -76,11 +76,11 @@ assembly code.  (You don't have to understand it.)  It saves the
 state of the currently running thread and restores the state of the
 thread we're switching to.
 
 state of the currently running thread and restores the state of the
 thread we're switching to.
 

-Using the @command{gdb} debugger, slowly trace through a context
-switch to see what happens (@pxref{gdb}).  You can set a
+Using the GDB debugger, slowly trace through a context
+switch to see what happens (@pxref{GDB}).  You can set a

 breakpoint on @func{schedule} to start out, and then
 breakpoint on @func{schedule} to start out, and then

-single-step from there.@footnote{@command{gdb} might tell you that
-@func{schedule} doesn't exist, which is arguably a @command{gdb} bug.
+single-step from there.@footnote{GDB might tell you that
+@func{schedule} doesn't exist, which is arguably a GDB bug.

 You can work around this by setting the breakpoint by filename and
 line number, e.g.@: @code{break thread.c:@var{ln}} where @var{ln} is
 the line number of the first declaration in @func{schedule}.}  Be sure
 You can work around this by setting the breakpoint by filename and
 line number, e.g.@: @code{break thread.c:@var{ln}} where @var{ln} is
 the line number of the first declaration in @func{schedule}.}  Be sure


@@ -185,8 +185,8 @@ project 3.  For now, you can ignore it.
 
 @item flags.h
 Macros that define a few bits in the 80@var{x}86 ``flags'' register.
 
 @item flags.h
 Macros that define a few bits in the 80@var{x}86 ``flags'' register.

-Probably of no interest.  See @bibref{IA32-v1}, section 3.4.3, for more
-information.
+Probably of no interest.  See @bibref{IA32-v1}, section 3.4.3, ``EFLAGS
+Register,'' for more information.

 @end table
 
 @menu
 @end table
 
 @menu


@@ -328,9 +328,15 @@ timer ticks or input events.  Turning off interrupts also increases the
 interrupt handling latency, which can make a machine feel sluggish if
 taken too far.
 
 interrupt handling latency, which can make a machine feel sluggish if
 taken too far.
 

+The synchronization primitives themselves in @file{synch.c} are
+implemented by disabling interrupts.  You may need to increase the
+amount of code that runs with interrupts disabled here, but you should
+still try to keep it to a minimum.
+

 Disabling interrupts can be useful for debugging, if you want to make
 sure that a section of code is not interrupted.  You should remove
 Disabling interrupts can be useful for debugging, if you want to make
 sure that a section of code is not interrupted.  You should remove

-debugging code before turning in your project.
+debugging code before turning in your project.  (Don't just comment it
+out, because that can make the code difficult to read.)

 
 There should be no busy waiting in your submission.  A tight loop that
 calls @func{thread_yield} is one form of busy waiting.
 
 There should be no busy waiting in your submission.  A tight loop that
 calls @func{thread_yield} is one form of busy waiting.


@@ -436,8 +442,8 @@ priority such that it no longer has the highest priority must cause it
 to immediately yield the CPU.
 
 Thread priorities range from @code{PRI_MIN} (0) to @code{PRI_MAX} (63).
 to immediately yield the CPU.
 
 Thread priorities range from @code{PRI_MIN} (0) to @code{PRI_MAX} (63).

-Lower numbers correspond to @emph{higher} priorities, so that priority 0
-is the highest priority and priority 63 is the lowest.
+Lower numbers correspond to lower priorities, so that priority 0
+is the lowest priority and priority 63 is the highest.

 The initial thread priority is passed as an argument to
 @func{thread_create}.  If there's no reason to choose another
 priority, use @code{PRI_DEFAULT} (31).  The @code{PRI_} macros are
 The initial thread priority is passed as an argument to
 @func{thread_create}.  If there's no reason to choose another
 priority, use @code{PRI_DEFAULT} (31).  The @code{PRI_} macros are


@@ -459,7 +465,8 @@ multiple donations, in which multiple priorities are donated to a single
 thread.  You must also handle nested donation: if @var{H} is waiting on
 a lock that @var{M} holds and @var{M} is waiting on a lock that @var{L}
 holds, then both @var{M} and @var{L} should be boosted to @var{H}'s
 thread.  You must also handle nested donation: if @var{H} is waiting on
 a lock that @var{M} holds and @var{M} is waiting on a lock that @var{L}
 holds, then both @var{M} and @var{L} should be boosted to @var{H}'s

-priority.
+priority.  If necessary, you may impose a reasonable limit on depth of
+nested priority donation, such as 8 levels.

 
 You must implement priority donation for locks.  You need not
 implement priority donation for semaphores or condition variables
 
 You must implement priority donation for locks.  You need not
 implement priority donation for semaphores or condition variables


@@ -491,20 +498,22 @@ The priority scheduler is not used in any later project.
 Implement a multilevel feedback queue scheduler similar to the
 4.4@acronym{BSD} scheduler to
 reduce the average response time for running jobs on your system.
 Implement a multilevel feedback queue scheduler similar to the
 4.4@acronym{BSD} scheduler to
 reduce the average response time for running jobs on your system.

-@xref{4.4BSD Scheduler}, for a detailed description of
-the MLFQS requirements.
+@xref{4.4BSD Scheduler}, for detailed requirements.

 
 

-The advanced scheduler builds on the priority scheduler.  You should
-have the priority scheduler working, except possibly for priority
-donation, before you start work on the advanced scheduler.
+Like the priority scheduler, the advanced scheduler chooses the thread
+to run based on priorities.  However, the advanced scheduler does not do
+priority donation.  Thus, we recommend that you have the priority
+scheduler working, except possibly for priority donation, before you
+start work on the advanced scheduler.

 
 

-You must write your code so that we can choose a scheduling algorithm
-policy at Pintos startup time.  By default, the round-robin scheduler
+You must write your code to allow us to choose a scheduling algorithm
+policy at Pintos startup time.  By default, the priority scheduler

 must be active, but we must be able to choose the 4.4@acronym{BSD}
 scheduler
 with the @option{-mlfqs} kernel option.  Passing this
 option sets @code{enable_mlfqs}, declared in @file{threads/init.h}, to
 must be active, but we must be able to choose the 4.4@acronym{BSD}
 scheduler
 with the @option{-mlfqs} kernel option.  Passing this
 option sets @code{enable_mlfqs}, declared in @file{threads/init.h}, to

-true.
+true when the options are parsed by @func{parse_options}, which happens
+midway through @func{main}.

 
 When the 4.4@acronym{BSD} scheduler is enabled, threads no longer
 directly control their own priorities.  The @var{priority} argument to
 
 When the 4.4@acronym{BSD} scheduler is enabled, threads no longer
 directly control their own priorities.  The @var{priority} argument to


@@ -524,6 +533,12 @@ Here's a summary of our reference solution, produced by the
 @command{diffstat} program.  The final row gives total lines inserted
 and deleted; a changed line counts as both an insertion and a deletion.
 
 @command{diffstat} program.  The final row gives total lines inserted
 and deleted; a changed line counts as both an insertion and a deletion.
 

+The reference solution represents just one possible solution.  Many
+other solutions are also possible and many of those differ greatly from
+the reference solution.  Some excellent solutions may not modify all the
+files modified by the reference solution, and some may modify files not
+modified by the reference solution.
+

 @verbatim
  devices/timer.c       |   42 +++++-
  threads/fixed-point.h |  120 ++++++++++++++++++
 @verbatim
  devices/timer.c       |   42 +++++-
  threads/fixed-point.h |  120 ++++++++++++++++++


@@ -533,6 +548,8 @@ and deleted; a changed line counts as both an insertion and a deletion.
  5 files changed, 440 insertions(+), 29 deletions(-)
 @end verbatim
 
  5 files changed, 440 insertions(+), 29 deletions(-)
 @end verbatim
 

+@file{fixed-point.h} is a new file added by the reference solution.
+

 @item How do I update the @file{Makefile}s when I add a new source file?
 
 @anchor{Adding Source Files}
 @item How do I update the @file{Makefile}s when I add a new source file?
 
 @anchor{Adding Source Files}


@@ -578,8 +595,40 @@ to cause many of the tests to fail.
 There are @code{TIME_SLICE} ticks per time slice.  This macro is
 declared in @file{threads/thread.c}.  The default is 4 ticks.
 
 There are @code{TIME_SLICE} ticks per time slice.  This macro is
 declared in @file{threads/thread.c}.  The default is 4 ticks.
 

-We don't recommend changing this values, because any changes are likely
+We don't recommend changing this value, because any changes are likely

 to cause many of the tests to fail.
 to cause many of the tests to fail.

+
+@item How do I run the tests?
+
+@xref{Testing}.
+
+@item Why do I get a test failure in @func{pass}?
+
+@anchor{The pass function fails}
+You are probably looking at a backtrace that looks something like this:
+
+@example
+0xc0108810: debug_panic (../../lib/kernel/debug.c:32)
+0xc010a99f: pass (../../tests/threads/tests.c:93)
+0xc010bdd3: test_mlfqs_load_1 (../../tests/threads/mlfqs-load-1.c:33)
+0xc010a8cf: run_test (../../tests/threads/tests.c:51)
+0xc0100452: run_task (../../threads/init.c:283)
+0xc0100536: run_actions (../../threads/init.c:333)
+0xc01000bb: main (../../threads/init.c:137)
+@end example
+
+This is just confusing output from the @command{backtrace} program.  It
+does not actually mean that @func{pass} called @func{debug_panic}.  In
+fact, @func{fail} called @func{debug_panic} (via the @func{PANIC}
+macro).  GCC knows that @func{debug_panic} does not return, because it
+is declared @code{NO_RETURN} (@pxref{Function and Parameter
+Attributes}), so it doesn't include any code in @func{pass} to take
+control when @func{debug_panic} returns.  This means that the return
+address on the stack looks like it is at the beginning of the function
+that happens to follow @func{fail} in memory, which in this case happens
+to be @func{pass}.
+
+@xref{Backtraces}, for more information.

 @end table
 
 @menu
 @end table
 
 @menu


@@ -678,4 +727,12 @@ just before the first @func{printf} in @func{main}.  Then modify
 
 It doesn't have to.  We won't test priority donation and the advanced
 scheduler at the same time.
 
 It doesn't have to.  We won't test priority donation and the advanced
 scheduler at the same time.

+
+@item Can I use one queue instead of 64 queues?
+
+Yes, that's fine.  It's easiest to describe the algorithm in terms of 64
+separate queues, but that doesn't mean you have to implement it that
+way.
+
+If you use a single queue, it should probably be sorted.

 @end table
 @end table