Clarify that struct intr_frame is on the kernel stack.

[pintos-anon] / doc / threads.texi

diff --git a/doc/threads.texi b/doc/threads.texi
index 58cf31609fd1d956e2c70285db3d4bfa1c1e8adf..40565994f536bbbec06e7a9beb25ae494cd4a60a 100644 (file)
--- a/doc/threads.texi
+++ b/doc/threads.texi
@@ -328,9 +328,14 @@ 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.
 

+You may need to add or modify code where interrupts are already
+disabled, such as in @func{sema_up} or @func{sema_down}.  You should
+still try to keep this code as short as you can.
+

 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.


@@ -459,12 +464,12 @@ 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 need not implement priority donation when a thread is waiting
-for a lock held by a lower-priority thread.  You need not
-implement priority donation for semaphores or condition variables,
-but you are welcome to do so.  You do need to implement
+You must implement priority donation for locks.  You need not
+implement priority donation for semaphores or condition variables
+(but you are welcome to do so).  You do need to implement

 priority scheduling in all cases.
 
 Finally, implement the following functions that allow a thread to
 priority scheduling in all cases.
 
 Finally, implement the following functions that allow a thread to


@@ -481,6 +486,9 @@ Returns the current thread's priority.  In the presence of priority
 donation, returns the higher (donated) priority.
 @end deftypefun
 
 donation, returns the higher (donated) priority.
 @end deftypefun
 

+You need not provide any interface to allow a thread to directly modify
+other threads' priorities.
+

 The priority scheduler is not used in any later project.
 
 @node Advanced Scheduler
 The priority scheduler is not used in any later project.
 
 @node Advanced Scheduler


@@ -489,15 +497,16 @@ 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
 must be active, but we must be able to choose the 4.4@acronym{BSD}
 scheduler
 with the @option{-mlfqs} kernel option.  Passing this


@@ -576,8 +585,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


@@ -627,7 +668,7 @@ list.
 Yes.  As long as there is a single highest-priority thread, it continues
 running until it blocks or finishes, even if it calls
 @func{thread_yield}.
 Yes.  As long as there is a single highest-priority thread, it continues
 running until it blocks or finishes, even if it calls
 @func{thread_yield}.

-If there are multiple threads have the same highest priority,
+If multiple threads have the same highest priority,

 @func{thread_yield} should switch among them in ``round robin'' order.
 
 @item What happens to the priority of a donating thread?
 @func{thread_yield} should switch among them in ``round robin'' order.
 
 @item What happens to the priority of a donating thread?


@@ -653,6 +694,12 @@ processor.  It is not acceptable to wait for the next timer interrupt.
 The highest priority thread should run as soon as it is runnable,
 preempting whatever thread is currently running.
 
 The highest priority thread should run as soon as it is runnable,
 preempting whatever thread is currently running.
 

+@item How does @func{thread_set_priority} affect a thread receiving donations?
+
+It should do something sensible, but no particular behavior is
+required.  None of the test cases call @func{thread_set_priority} from a
+thread while it is receiving a priority donation.
+

 @item Calling @func{printf} in @func{sema_up} or @func{sema_down} reboots!
 
 @anchor{printf Reboots}
 @item Calling @func{printf} in @func{sema_up} or @func{sema_down} reboots!
 
 @anchor{printf Reboots}


@@ -670,4 +717,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