X-Git-Url: https://pintos-os.org/cgi-bin/gitweb.cgi?a=blobdiff_plain;f=doc%2Fthreads.texi;h=c9094bc2d073ddd5642aad218fc82465ecabdc5c;hb=919347c164606c3f1544b2e8bd62f505aeda80a1;hp=04d48d1c0eff50c96f56ecdeeb338382f970da5f;hpb=e2c9945359a9fe72de7a6033370d52e55a26eb9f;p=pintos-anon

diff --git a/doc/threads.texi b/doc/threads.texi
index 04d48d1..c9094bc 100644
--- a/doc/threads.texi
+++ b/doc/threads.texi
@@ -1,103 +1,108 @@
-@node Project 1--Threads, Project 2--User Programs, Pintos Tour, Top
+@node Project 1--Threads
 @chapter Project 1: Threads
 
 In this assignment, we give you a minimally functional thread system.
 Your job is to extend the functionality of this system to gain a
-better understanding of synchronization problems. Additionally, you
-will use at least part of this increased functionality in future
-assignments.
+better understanding of synchronization problems.
 
-You will be working in primarily in the @file{threads} directory for
+You will be working primarily in the @file{threads} directory for
 this assignment, with some work in the @file{devices} directory on the
 side.  Compilation should be done in the @file{threads} directory.
 
-Before you read the description of this project, you should read all
-of the following sections: @ref{Introduction}, @ref{Coding Standards},
-@ref{Project Documentation}, @ref{Debugging Tools}, and
-@ref{Development Tools}.  You should at least skim the material in
-@ref{Threads Tour}, but there's no need to fret over the details.  To
-complete this project you will also need to read @ref{Multilevel
-Feedback Scheduling}.
+Before you read the description of this project, you should read all of
+the following sections: @ref{Introduction}, @ref{Coding Standards},
+@ref{Debugging Tools}, and @ref{Development Tools}.  You should at least
+skim the material from @ref{Pintos Loading} through @ref{Memory
+Allocation}, especially @ref{Synchronization}.  To complete this project
+you will also need to read @ref{4.4BSD Scheduler}.
+
+@menu
+* Project 1 Background::        
+* Project 1 Requirements::      
+* Project 1 FAQ::               
+@end menu
+
+@node Project 1 Background
+@section Background
+
 
 @menu
 * Understanding Threads::       
-* Project 1 Code::              
-* Debugging versus Testing::    
-* Tips::                        
-* Problem 1-1 Alarm Clock::     
-* Problem 1-2 Join::            
-* Problem 1-3 Priority Scheduling::  
-* Problem 1-4 Advanced Scheduler::  
-* Threads FAQ::                 
+* Project 1 Source Files::      
+* Project 1 Synchronization::   
+* Development Suggestions::     
 @end menu
 
 @node Understanding Threads
-@section Understanding Threads
+@subsection Understanding Threads
 
-The first step is to read and understand the initial thread system.
-Pintos, by default, implements thread creation and thread completion,
+The first step is to read and understand the code for the initial thread
+system.
+Pintos already implements thread creation and thread completion,
 a simple scheduler to switch between threads, and synchronization
-primitives (semaphores, locks, and condition variables). 
+primitives (semaphores, locks, condition variables, and optimization
+barriers).
 
-However, there's a lot of magic going on in some of this code, so if
+Some of this code might seem slightly mysterious.  If
 you haven't already compiled and run the base system, as described in
 the introduction (@pxref{Introduction}), you should do so now.  You
-can read through parts of the source code by hand to see what's going
+can read through parts of the source code to see what's going
 on.  If you like, you can add calls to @func{printf} almost
 anywhere, then recompile and run to see what happens and in what
 order.  You can also run the kernel in a debugger and set breakpoints
 at interesting spots, single-step through code and examine data, and
-so on.  @xref{i386-elf-gdb}, for more information.
+so on.
 
 When a thread is created, you are creating a new context to be
-scheduled. You provide a function to be run in this context as an
-argument to @func{thread_create}. The first time the thread is
-scheduled and runs, it will start from the beginning of that function
-and execute it in the context. When that function returns, that thread
-completes. Each thread, therefore, acts like a mini-program running
+scheduled.  You provide a function to be run in this context as an
+argument to @func{thread_create}.  The first time the thread is
+scheduled and runs, it starts from the beginning of that function
+and executes in that context.  When the function returns, the thread
+terminates.  Each thread, therefore, acts like a mini-program running
 inside Pintos, with the function passed to @func{thread_create}
 acting like @func{main}.
 
-At any given time, Pintos is running exactly one thread, with the
-others switched out.  The scheduler decides which thread to run next
-when it needs to switch between them.  (If no thread is ready to run
-at any given time, then the special ``idle'' thread runs.)  The
-synchronization primitives are used to force context switches when one
+At any given time, exactly one thread runs and the rest, if any,
+become inactive.  The scheduler decides which thread to
+run next.  (If no thread is ready to run
+at any given time, then the special ``idle'' thread, implemented in
+@func{idle}, runs.)
+Synchronization primitives can force context switches when one
 thread needs to wait for another thread to do something.
 
-The exact mechanics of a context switch are pretty gruesome and have
-been provided for you in @file{threads/switch.S} (this is 80@var{x}86
-assembly; don't worry about understanding it).  It involves saving the
-state of the currently running thread and restoring the state of the
+The mechanics of a context switch are
+in @file{threads/switch.S}, which is 80@var{x}86
+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.
 
-Using the @command{gdb} debugger, slowly trace through a context
-switch to see what happens (@pxref{i386-elf-gdb}).  You can set a
-breakpoint on the @func{schedule} function to start out, and then
-single-step from there.  Be sure to keep track of each thread's
-address and state, and what procedures are on the call stack for each
-thread.  You will notice that when one thread calls
-@func{switch_threads}, another thread starts running, and the first
-thing the new thread does is to return from
-@func{switch_threads}.  We realize this comment will seem cryptic to
-you at this point, but you will understand threads once you understand
-why the @func{switch_threads} that gets called is different from the
-@func{switch_threads} that returns.
+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
+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
+to keep track of each thread's address
+and state, and what procedures are on the call stack for each thread.
+You will notice that when one thread calls @func{switch_threads},
+another thread starts running, and the first thing the new thread does
+is to return from @func{switch_threads}.  You will understand the thread
+system once you understand why and how the @func{switch_threads} that
+gets called is different from the @func{switch_threads} that returns.
+@xref{Thread Switching}, for more information.
 
 @strong{Warning}: In Pintos, each thread is assigned a small,
 fixed-size execution stack just under @w{4 kB} in size.  The kernel
-does try to detect stack overflow, but it cannot always succeed.  You
+tries to detect stack overflow, but it cannot do so perfectly.  You
 may cause bizarre problems, such as mysterious kernel panics, if you
 declare large data structures as non-static local variables,
 e.g. @samp{int buf[1000];}.  Alternatives to stack allocation include
-the page allocator in @file{threads/palloc.c} and the block allocator
-in @file{threads/malloc.c}.  Note that the page allocator doles out
-@w{4 kB} chunks and that @func{malloc} has a @w{2 kB} block size
-limit.  If you need larger chunks, consider using a linked structure
-instead.
+the page allocator and the block allocator (@pxref{Memory Allocation}).
 
-@node Project 1 Code
-@section Code
+@node Project 1 Source Files
+@subsection Source Files
 
 Here is a brief overview of the files in the @file{threads}
 directory.  You will not need to modify most of this code, but the
@@ -108,75 +113,84 @@ code to look at.
 @item loader.S
 @itemx loader.h
 The kernel loader.  Assembles to 512 bytes of code and data that the
-PC BIOS loads into memory and which in turn loads the kernel into
-memory, does basic processor initialization, and jumps to the
-beginning of the kernel.  You should not need to look at this code or
-modify it.
+PC BIOS loads into memory and which in turn finds the kernel on disk,
+loads it into memory, and jumps to @func{start} in @file{start.S}.
+@xref{Pintos Loader}, for details.  You should not need to look at
+this code or modify it.
+
+@item start.S
+Does basic setup needed for memory protection and 32-bit
+operation on 80@var{x}86 CPUs.  Unlike the loader, this code is
+actually part of the kernel.  @xref{Low-Level Kernel Initialization},
+for details.
 
 @item kernel.lds.S
 The linker script used to link the kernel.  Sets the load address of
-the kernel and arranges for @file{start.S} to be at the very beginning
-of the kernel image.  Again, you should not need to look at this code
+the kernel and arranges for @file{start.S} to be near the beginning
+of the kernel image.  @xref{Pintos Loader}, for details. Again, you
+should not need to look at this code
 or modify it, but it's here in case you're curious.
 
-@item start.S
-Jumps to @func{main}.
-
 @item init.c
 @itemx init.h
 Kernel initialization, including @func{main}, the kernel's ``main
 program.''  You should look over @func{main} at least to see what
-gets initialized.
+gets initialized.  You might want to add your own initialization code
+here.  @xref{High-Level Kernel Initialization}, for details.
 
 @item thread.c
 @itemx thread.h
-Basic thread support.  Much of your work will take place in these
-files.  @file{thread.h} defines @code{struct thread}, which you will
-modify in the first three projects.
+Basic thread support.  Much of your work will take place in these files.
+@file{thread.h} defines @struct{thread}, which you are likely to modify
+in all four projects.  See @ref{struct thread} and @ref{Threads} for
+more information.
 
 @item switch.S
 @itemx switch.h
 Assembly language routine for switching threads.  Already discussed
-above.
+above.  @xref{Thread Functions}, for more information.
 
 @item palloc.c
 @itemx palloc.h
 Page allocator, which hands out system memory in multiples of 4 kB
-pages.
+pages.  @xref{Page Allocator}, for more information.
 
 @item malloc.c
 @itemx malloc.h
-A very simple implementation of @func{malloc} and @func{free} for
-the kernel.
+A simple implementation of @func{malloc} and @func{free} for
+the kernel.  @xref{Block Allocator}, for more information.
 
 @item interrupt.c
 @itemx interrupt.h
 Basic interrupt handling and functions for turning interrupts on and
-off.
+off.  @xref{Interrupt Handling}, for more information.
 
-@item intr-stubs.pl
+@item intr-stubs.S
 @itemx intr-stubs.h
-A Perl program that outputs assembly for low-level interrupt handling.
+Assembly code for low-level interrupt handling.  @xref{Interrupt
+Infrastructure}, for more information.
 
 @item synch.c
 @itemx synch.h
-Basic synchronization primitives: semaphores, locks, and condition
-variables.  You will need to use these for synchronization through all
-four projects.
-
-@item test.c
-@itemx test.h
-Test code.  For project 1, you will replace this file with your test
-cases.
+Basic synchronization primitives: semaphores, locks, condition
+variables, and optimization barriers.  You will need to use these for
+synchronization in all
+four projects.  @xref{Synchronization}, for more information.
 
 @item io.h
 Functions for I/O port access.  This is mostly used by source code in
 the @file{devices} directory that you won't have to touch.
 
-@item mmu.h
-Functions and macros related to memory management, including page
-directories and page tables.  This will be more important to you in
-project 3.  For now, you can ignore it.
+@item vaddr.h
+@itemx pte.h
+Functions and macros for working with virtual addresses and page table
+entries.  These will be more important to you in project 3.  For now,
+you can ignore them.
+
+@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, ``EFLAGS
+Register,'' for more information.
 @end table
 
 @menu
@@ -185,7 +199,7 @@ project 3.  For now, you can ignore it.
 @end menu
 
 @node devices code
-@subsection @file{devices} code
+@subsubsection @file{devices} code
 
 The basic threaded kernel also includes these files in the
 @file{devices} directory:
@@ -194,35 +208,74 @@ The basic threaded kernel also includes these files in the
 @item timer.c
 @itemx timer.h
 System timer that ticks, by default, 100 times per second.  You will
-modify this code in Problem 1-1.
+modify this code in this project.
 
 @item vga.c
 @itemx vga.h
 VGA display driver.  Responsible for writing text to the screen.
-You should have no need to look at this code.  @func{printf} will
-call into the VGA display driver for you, so there's little reason to
+You should have no need to look at this code.  @func{printf}
+calls into the VGA display driver for you, so there's little reason to
 call this code yourself.
 
 @item serial.c
 @itemx serial.h
 Serial port driver.  Again, @func{printf} calls this code for you,
-so you don't need to do so yourself.  Feel free to look through it if
-you're curious.
-
-@item disk.c
-@itemx disk.h
-Supports reading and writing sectors on up to 4 IDE disks.  This won't
-actually be used until project 2.
+so you don't need to do so yourself.
+It handles serial input by passing it to the input layer (see below).
+
+@item block.c
+@itemx block.h
+An abstraction layer for @dfn{block devices}, that is, random-access,
+disk-like devices that are organized as arrays of fixed-size blocks.
+Out of the box, Pintos supports two types of block devices: IDE disks
+and partitions.  Block devices, regardless of type, won't actually be
+used until project 2.
+
+@item ide.c
+@itemx ide.h
+Supports reading and writing sectors on up to 4 IDE disks.
+
+@item partition.c
+@itemx partition.h
+Understands the structure of partitions on disks, allowing a single
+disk to be carved up into multiple regions (partitions) for
+independent use.
+
+@item kbd.c
+@itemx kbd.h
+Keyboard driver.  Handles keystrokes passing them to the input layer
+(see below).
+
+@item input.c
+@itemx input.h
+Input layer.  Queues input characters passed along by the keyboard or
+serial drivers.
 
 @item intq.c
 @itemx intq.h
 Interrupt queue, for managing a circular queue that both kernel
 threads and interrupt handlers want to access.  Used by the keyboard
 and serial drivers.
+
+@item rtc.c
+@itemx rtc.h
+Real-time clock driver, to enable the kernel to determine the current
+date and time.  By default, this is only used by @file{thread/init.c}
+to choose an initial seed for the random number generator.
+
+@item speaker.c
+@itemx speaker.h
+Driver that can produce tones on the PC speaker.
+
+@item pit.c
+@itemx pit.h
+Code to configure the 8254 Programmable Interrupt Timer.  This code is
+used by both @file{devices/timer.c} and @file{devices/speaker.c}
+because each device uses one of the PIT's output channel.
 @end table
 
 @node lib files
-@subsection @file{lib} files
+@subsubsection @file{lib} files
 
 Finally, @file{lib} and @file{lib/kernel} contain useful library
 routines.  (@file{lib/user} will be used by user programs, starting in
@@ -243,7 +296,8 @@ details:
 @itemx stdlib.h
 @itemx string.c
 @itemx string.h
-Implementation of the standard C library.  @xref{C99}, for information
+A subset of the standard C library.  @xref{C99}, for
+information
 on a few recently introduced pieces of the C library that you might
 not have encountered before.  @xref{Unsafe String Functions}, for
 information on what's been intentionally left out for safety.
@@ -255,7 +309,11 @@ more information.
 
 @item random.c
 @itemx random.h
-Pseudo-random number generator.
+Pseudo-random number generator.  The actual sequence of random values
+will not vary from one Pintos run to another, unless you do one of
+three things: specify a new random seed value on the @option{-rs}
+kernel command-line option on each run, or use a simulator other than
+Bochs, or specify the @option{-r} option to @command{pintos}.
 
 @item round.h
 Macros for rounding.
@@ -271,7 +329,7 @@ you'll probably want to use it a few places yourself in project 1.
 @item kernel/bitmap.c
 @itemx kernel/bitmap.h
 Bitmap implementation.  You can use this in your code if you like, but
-you probably won't have any need for project 1.
+you probably won't have any need for it in project 1.
 
 @item kernel/hash.c
 @itemx kernel/hash.h
@@ -279,310 +337,282 @@ Hash table implementation.  Likely to come in handy for project 3.
 
 @item kernel/console.c
 @itemx kernel/console.h
+@item kernel/stdio.h
 Implements @func{printf} and a few other functions.
 @end table
 
-@node Debugging versus Testing
-@section Debugging versus Testing
-
-When you're debugging code, it's useful to be able to be able to run a
-program twice and have it do exactly the same thing.  On second and
-later runs, you can make new observations without having to discard or
-verify your old observations.  This property is called
-``reproducibility.''  The simulator we use, Bochs, can be set up for
-reproducibility, and that's the way that @command{pintos} invokes it.
-
-Of course, a simulation can only be reproducible from one run to the
-next if its input is the same each time.  For simulating an entire
-computer, as we do, this means that every part of the computer must be
-the same.  For example, you must use the same disks, the same version
-of Bochs, and you must not hit any keys on the keyboard (because you
-could not be sure to hit them at exactly the same point each time)
-during the runs.
-
-While reproducibility is useful for debugging, it is a problem for
-testing thread synchronization, an important part of this project.  In
-particular, when Bochs is set up for reproducibility, timer interrupts
-will come at perfectly reproducible points, and therefore so will
-thread switches.  That means that running the same test several times
-doesn't give you any greater confidence in your code's correctness
-than does running it only once.
-
-So, to make your code easier to test, we've added a feature to Bochs
-that makes timer interrupts come at random intervals, but in a
-perfectly predictable way.  In particular, if you invoke
-@command{pintos} with the option @option{-j @var{seed}}, timer
-interrupts will come at irregularly spaced intervals.  Within a single
-@var{seed} value, execution will still be reproducible, but timer
-behavior will change as @var{seed} is varied.  Thus, for the highest
-degree of confidence you should test your code with many seed values.
-
-@node Tips
-@section Tips
-
-There should be no busy-waiting in any of your solutions to this
-assignment.  Furthermore, resist the temptation to directly disable
-interrupts in your solution by calling @func{intr_disable} or
-@func{intr_set_level}, although you may find doing so to be useful
-while debugging.  Instead, use semaphores, locks and condition
-variables to solve synchronization problems.  Hint: read the comments
-in @file{threads/synch.h} if you're unsure what synchronization
-primitives may be used in what situations.
-
-Given some designs of some problems, there may be one or two instances
-in which it is appropriate to directly change the interrupt levels
-instead of relying on the given synchroniztion primitives.  This must
-be justified in your @file{DESIGNDOC} file.  If you're not sure you're
-justified, ask!
-
-While all parts of this assignment are required if you intend to earn
-full credit on this project, keep in mind that Problem 1-2 (Join) will
-be needed for future assignments, so you'll want to get this one
-right.  We don't give out solutions, so you're stuck with your Join
-code for the whole quarter.  Problem 1-1 (Alarm Clock) could be very
-handy, but not strictly required in the future.  The upshot of all
-this is that you should focus heavily on making sure that your
-implementation of @func{thread_join} works correctly, since if it's
-broken, you will need to fix it for future assignments.  The other
-parts can be turned off in the future if you find you can't make them
-work quite right.
-
-Also keep in mind that Problem 1-4 (the MLFQS) builds on the features you
-implement in Problem 1-3, so to avoid unnecessary code duplication, it
-would be a good idea to divide up the work among your team members
-such that you have Problem 1-3 fully working before you begin to tackle
-Problem 1-4.
-
-@node Problem 1-1 Alarm Clock
-@section Problem 1-1: Alarm Clock
-
-Improve the implementation of the timer device defined in
-@file{devices/timer.c} by reimplementing @func{timer_sleep}.
-Threads call @code{timer_sleep(@var{x})} to suspend execution until
-time has advanced by at least @w{@var{x} timer ticks}.  This is
-useful for threads that operate in real-time, for example, for
-blinking the cursor once per second.  There is no requirement that
-threads start running immediately after waking up; just put them on
-the ready queue after they have waited for approximately the right
-amount of time.
-
-A working implementation of this function is provided.  However, the
-version provided is poor, because it ``busy waits,'' that is, it spins
-in a tight loop checking the current time until the current time has
-advanced far enough.  This is undesirable because it wastes time that
-could potentially be used more profitably by another thread.  Your
-solution should not busy wait.
-
-The argument to @func{timer_sleep} is expressed in timer ticks, not
-in milliseconds or another unit.  There are @code{TIMER_FREQ} timer
+@node Project 1 Synchronization
+@subsection Synchronization
+
+Proper synchronization is an important part of the solutions to these
+problems.  Any synchronization problem can be easily solved by turning
+interrupts off: while interrupts are off, there is no concurrency, so
+there's no possibility for race conditions.  Therefore, it's tempting to
+solve all synchronization problems this way, but @strong{don't}.
+Instead, use semaphores, locks, and condition variables to solve the
+bulk of your synchronization problems.  Read the tour section on
+synchronization (@pxref{Synchronization}) or the comments in
+@file{threads/synch.c} if you're unsure what synchronization primitives
+may be used in what situations.
+
+In the Pintos projects, the only class of problem best solved by
+disabling interrupts is coordinating data shared between a kernel thread
+and an interrupt handler.  Because interrupt handlers can't sleep, they
+can't acquire locks.  This means that data shared between kernel threads
+and an interrupt handler must be protected within a kernel thread by
+turning off interrupts.
+
+This project only requires accessing a little bit of thread state from
+interrupt handlers.  For the alarm clock, the timer interrupt needs to
+wake up sleeping threads.  In the advanced scheduler, the timer
+interrupt needs to access a few global and per-thread variables.  When
+you access these variables from kernel threads, you will need to disable
+interrupts to prevent the timer interrupt from interfering.
+
+When you do turn off interrupts, take care to do so for the least amount
+of code possible, or you can end up losing important things such as
+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.
+
+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
+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.
+
+@node Development Suggestions
+@subsection Development Suggestions
+
+In the past, many groups divided the assignment into pieces, then each
+group member worked on his or her piece until just before the
+deadline, at which time the group reconvened to combine their code and
+submit.  @strong{This is a bad idea.  We do not recommend this
+approach.}  Groups that do this often find that two changes conflict
+with each other, requiring lots of last-minute debugging.  Some groups
+who have done this have turned in code that did not even compile or
+boot, much less pass any tests.
+
+@localcvspolicy{}
+
+You should expect to run into bugs that you simply don't understand
+while working on this and subsequent projects.  When you do,
+reread the appendix on debugging tools, which is filled with
+useful debugging tips that should help you to get back up to speed
+(@pxref{Debugging Tools}).  Be sure to read the section on backtraces
+(@pxref{Backtraces}), which will help you to get the most out of every
+kernel panic or assertion failure.
+
+@node Project 1 Requirements
+@section Requirements
+
+@menu
+* Project 1 Design Document::   
+* Alarm Clock::                 
+* Priority Scheduling::         
+* Advanced Scheduler::          
+@end menu
+
+@node Project 1 Design Document
+@subsection Design Document
+
+Before you turn in your project, you must copy @uref{threads.tmpl, , the
+project 1 design document template} into your source tree under the name
+@file{pintos/src/threads/DESIGNDOC} and fill it in.  We recommend that
+you read the design document template before you start working on the
+project.  @xref{Project Documentation}, for a sample design document
+that goes along with a fictitious project.
+
+@node Alarm Clock
+@subsection Alarm Clock
+
+Reimplement @func{timer_sleep}, defined in @file{devices/timer.c}.
+Although a working implementation is provided, it ``busy waits,'' that
+is, it spins in a loop checking the current time and calling
+@func{thread_yield} until enough time has gone by.  Reimplement it to
+avoid busy waiting.
+
+@deftypefun void timer_sleep (int64_t @var{ticks})
+Suspends execution of the calling thread until time has advanced by at
+least @w{@var{x} timer ticks}.  Unless the system is otherwise idle, the
+thread need not wake up after exactly @var{x} ticks.  Just put it on
+the ready queue after they have waited for the right amount of time.
+
+@func{timer_sleep} is useful for threads that operate in real-time,
+e.g.@: for blinking the cursor once per second.
+
+The argument to @func{timer_sleep} is expressed in timer ticks, not in
+milliseconds or any another unit.  There are @code{TIMER_FREQ} timer
 ticks per second, where @code{TIMER_FREQ} is a macro defined in
-@code{devices/timer.h}.
-
-@node Problem 1-2 Join
-@section Problem 1-2: Join
-
-Implement @code{thread_join(tid_t)} in @file{threads/thread.c}.  There
-is already a prototype for it in @file{threads/thread.h}, which you
-should not change.  This function causes the currently running thread
-to block until the thread whose thread id is passed as an argument
-exits.  If @var{A} is the running thread and @var{B} is the argument,
-then we say that ``@var{A} joins @var{B}.''
-
-Incidentally, we don't use @code{struct thread *} as
-@func{thread_join}'s parameter type because a thread pointer is not
-unique over time.  That is, when a thread dies, its memory may be,
-whether immediately or much later, reused for another thread.  If
-thread A over time had two children B and C that were stored at the
-same address, then @code{thread_join(@var{B})} and
-@code{thread_join(@var{C})} would be ambiguous.  Introducing a thread
-id or @dfn{tid}, represented by type @code{tid_t}, that is
-intentionally unique over time solves the problem.  The provided code
-uses an @code{int} for @code{tid_t}, but you may decide you prefer to
-use some other type.
-
-The model for @func{thread_join} is the @command{wait} system call
-in Unix-like systems.  (Try reading the manpages.)  That system call
-can only be used by a parent process to wait for a child's death.  You
-should implement @func{thread_join} to have the same restriction.
-That is, a thread may only join its immediate children.
-
-A thread need not ever be joined.  Your solution should properly free
-all of a thread's resources, including its @code{struct thread},
-whether it is ever joined or not, and regardless of whether the child
-exits before or after its parent.  That is, a thread should be freed
-exactly once in all cases.
-
-Joining a given thread is idempotent.  That is, joining a thread T
-multiple times is equivalent to joining it once, because T has already
-exited at the time of the later joins.  Thus, joins on T after the
-first should return immediately.
-
-Calling @func{thread_join} on an thread that is not the caller's
-child should cause the caller to return immediately.
-
-Consider all the ways a join can occur: nested joins (@var{A} joins
-@var{B}, then @var{B} joins @var{C}), multiple joins (@var{A} joins
-@var{B}, then @var{A} joins @var{C}), and so on.  Does your join work
-if @func{thread_join} is called on a thread that has not yet been
-scheduled for the first time?  You should handle all of these cases.
-Write test code that demonstrates the cases your join works for.
-Don't overdo the output volume, please!
-
-Be careful to program this function correctly.  You will need its
-functionality for project 2.
-
-Once you've implemented @func{thread_join}, define
-@code{THREAD_JOIN_IMPLEMENTED} in @file{constants.h}.
-@xref{Conditional Compilation}, for more information.
-
-@node Problem 1-3 Priority Scheduling
-@section Problem 1-3: Priority Scheduling
-
-Implement priority scheduling in Pintos.  Priority scheduling is a key
-building block for real-time systems.  Implement functions
-@func{thread_set_priority} to set the priority of the running thread
-and @func{thread_get_priority} to get the running thread's priority.
-(A thread can examine and modify only its own priority.)  There are
-already prototypes for these functions in @file{threads/thread.h},
-which you should not change.
-
-Thread priority ranges from @code{PRI_MIN} (0) to @code{PRI_MAX} (59).
+@code{devices/timer.h}.  The default value is 100.  We don't recommend
+changing this value, because any change is likely to cause many of
+the tests to fail.
+@end deftypefun
+
+Separate functions @func{timer_msleep}, @func{timer_usleep}, and
+@func{timer_nsleep} do exist for sleeping a specific number of
+milliseconds, microseconds, or nanoseconds, respectively, but these will
+call @func{timer_sleep} automatically when necessary.  You do not need
+to modify them.
+
+If your delays seem too short or too long, reread the explanation of the
+@option{-r} option to @command{pintos} (@pxref{Debugging versus
+Testing}).
+
+The alarm clock implementation is not needed for later projects,
+although it could be useful for project 4.
+
+@node Priority Scheduling
+@subsection Priority Scheduling
+
+Implement priority scheduling in Pintos.
+When a thread is added to the ready list that has a higher priority
+than the currently running thread, the current thread should
+immediately yield the processor to the new thread.  Similarly, when
+threads are waiting for a lock, semaphore, or condition variable, the
+highest priority waiting thread should be awakened first.  A thread
+may raise or lower its own priority at any time, but lowering its
+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).
+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} (29).  The @code{PRI_} macros are
+priority, use @code{PRI_DEFAULT} (31).  The @code{PRI_} macros are
 defined in @file{threads/thread.h}, and you should not change their
 values.
 
-When a thread is added to the ready list that has a higher priority
-than the currently running thread, the current thread should
-immediately yield the processor to the new thread.  Similarly, when
-threads are waiting for a lock, semaphore or condition variable, the
-highest priority waiting thread should be woken up first.  A thread's
-priority may be set at any time, including while the thread is waiting
-on a lock, semaphore, or condition variable.
-
-One issue with priority scheduling is ``priority inversion'': if a
-high priority thread needs to wait for a low priority thread (for
-instance, for a lock held by a low priority thread, or in
-@func{thread_join} for a thread to complete), and a middle priority
-thread is on the ready list, then the high priority thread will never
-get the CPU because the low priority thread will not get any CPU time.
-A partial fix for this problem is to have the waiting thread
-``donate'' its priority to the low priority thread while it is holding
-the lock, then recall the donation once it has acquired the lock.
-Implement this fix.
-
-You will need to account for all different orders that priority
-donation and inversion can occur.  Be sure to handle multiple
-donations, in which multiple priorities are donated to a thread.  You
-must also handle nested donation: given high, medium, and low priority
-threads @var{H}, @var{M}, and @var{L}, respectively, 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.
-
-You only need to implement priority donation when a thread is waiting
-for a lock held by a lower-priority thread.  You do not need to
-implement this fix for semaphores, condition variables or joins.
-However, you do need to implement priority scheduling in all cases.
-
-@node Problem 1-4 Advanced Scheduler
-@section Problem 1-4: Advanced Scheduler
-
-Implement Solaris's multilevel feedback queue scheduler (MLFQS) to
-reduce the average response time for running jobs on your system.
-@xref{Multilevel Feedback Scheduling}, for a detailed description of
-the MLFQS requirements.
+One issue with priority scheduling is ``priority inversion''.  Consider
+high, medium, and low priority threads @var{H}, @var{M}, and @var{L},
+respectively.  If @var{H} needs to wait for @var{L} (for instance, for a
+lock held by @var{L}), and @var{M} is on the ready list, then @var{H}
+will never get the CPU because the low priority thread will not get any
+CPU time.  A partial fix for this problem is for @var{H} to ``donate''
+its priority to @var{L} while @var{L} is holding the lock, then recall
+the donation once @var{L} releases (and thus @var{H} acquires) the lock.
+
+Implement priority donation.  You will need to account for all different
+situations in which priority donation is required.  Be sure to handle
+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
+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 the other Pintos synchronization
+constructs.  You do need to implement priority scheduling in all
+cases.
 
-Demonstrate that your scheduling algorithm reduces response time
-relative to the original Pintos scheduling algorithm (round robin) for
-at least one workload of your own design (i.e.@: in addition to the
-provided test).
+Finally, implement the following functions that allow a thread to
+examine and modify its own priority.  Skeletons for these functions are
+provided in @file{threads/thread.c}.
 
-You may assume a static priority for this problem. It is not necessary
-to ``re-donate'' a thread's priority if it changes (although you are
-free to do so).
+@deftypefun void thread_set_priority (int @var{new_priority})
+Sets the current thread's priority to @var{new_priority}.  If the
+current thread no longer has the highest priority, yields.
+@end deftypefun
 
-You must write your code so that we can turn the MLFQS on and off at
-compile time.  By default, it must be off, but we must be able to turn
-it on by inserting the line @code{#define MLFQS 1} in
-@file{constants.h}.  @xref{Conditional Compilation}, for details.
+@deftypefun int thread_get_priority (void)
+Returns the current thread's priority.  In the presence of priority
+donation, returns the higher (donated) priority.
+@end deftypefun
 
-@node Threads FAQ
-@section FAQ
+You need not provide any interface to allow a thread to directly modify
+other threads' priorities.
 
-@enumerate 1
-@item
-@b{I am adding a new @file{.h} or @file{.c} file.  How do I fix the
-@file{Makefile}s?}@anchor{Adding c or h Files}
+The priority scheduler is not used in any later project.
 
-To add a @file{.c} file, edit the top-level @file{Makefile.build}.
-You'll want to add your file to variable @samp{@var{dir}_SRC}, where
-@var{dir} is the directory where you added the file.  For this
-project, that means you should add it to @code{threads_SRC}, or
-possibly @code{devices_SRC} if you put in the @file{devices}
-directory.  Then run @code{make}.  If your new file doesn't get
-compiled, run @code{make clean} and then try again.
+@node Advanced Scheduler
+@subsection Advanced Scheduler
 
-When you modify the top-level @file{Makefile.build}, the modified
-version should be automatically copied to
-@file{threads/build/Makefile} when you re-run make.  The opposite is
-not true, so any changes will be lost the next time you run @code{make
-clean} from the @file{threads} directory.  Therefore, you should
-prefer to edit @file{Makefile.build} (unless your changes are meant to
-be truly temporary).
+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 detailed requirements.
+
+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 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{thread_mlfqs}, declared in @file{threads/thread.h}, to
+true when the options are parsed by @func{parse_options}, which happens
+early in @func{main}.
+
+When the 4.4@acronym{BSD} scheduler is enabled, threads no longer
+directly control their own priorities.  The @var{priority} argument to
+@func{thread_create} should be ignored, as well as any calls to
+@func{thread_set_priority}, and @func{thread_get_priority} should return
+the thread's current priority as set by the scheduler.
+
+The advanced scheduler is not used in any later project.
+
+@node Project 1 FAQ
+@section FAQ
 
-There is no need to edit the @file{Makefile}s to add a @file{.h} file.
+@table @b
+@item How much code will I need to write?
 
-@item
-@b{How do I write my test cases?}
+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.
 
-Test cases should be replacements for the existing @file{test.c}
-file.  Put them in a @file{threads/testcases} directory.
-@xref{TESTCASE}, for more information.
+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.
 
-@item
-@b{Why can't I disable interrupts?}
-
-Turning off interrupts should only be done for short amounts of time,
-or else you end up losing important things such as disk or input
-events.  Turning off interrupts also increases the interrupt handling
-latency, which can make a machine feel sluggish if taken too far.
-Therefore, in general, setting the interrupt level should be used
-sparingly.  Also, any synchronization problem can be easily solved by
-turning interrupts off, since while interrupts are off, there is no
-concurrency, so there's no possibility for race condition.
-
-To make sure you understand concurrency well, we are discouraging you
-from taking this shortcut at all in your solution.  If you are unable
-to solve a particular synchronization problem with semaphores, locks,
-or conditions, or think that they are inadequate for a particular
-reason, you may turn to disabling interrupts.  If you want to do this,
-we require in your design document a complete justification and
-scenario (i.e.@: exact sequence of events) to show why interrupt
-manipulation is the best solution.  If you are unsure, the TAs can
-help you determine if you are using interrupts too haphazardly.  We
-want to emphasize that there are only limited cases where this is
-appropriate.
-
-You might find @file{devices/intq.h} and its users to be an
-inspiration or source of rationale.
+@verbatim
+ devices/timer.c       |   42 +++++-
+ threads/fixed-point.h |  120 ++++++++++++++++++
+ threads/synch.c       |   88 ++++++++++++-
+ threads/thread.c      |  196 ++++++++++++++++++++++++++----
+ threads/thread.h      |   23 +++
+ 5 files changed, 440 insertions(+), 29 deletions(-)
+@end verbatim
 
-@item
-@b{Where might interrupt-level manipulation be appropriate?}
+@file{fixed-point.h} is a new file added by the reference solution.
 
-You might find it necessary in some solutions to the Alarm problem.
+@item How do I update the @file{Makefile}s when I add a new source file?
 
-You might want it at one small point for the priority scheduling
-problem.  Note that it is not required to use interrupts for these
-problems.  There are other, equally correct solutions that do not
-require interrupt manipulation.  However, if you do manipulate
-interrupts and @strong{correctly and fully document it} in your design
-document, we will allow limited use of interrupt disabling.
+@anchor{Adding Source Files}
+To add a @file{.c} file, edit the top-level @file{Makefile.build}.
+Add the new file to variable @samp{@var{dir}_SRC}, where
+@var{dir} is the directory where you added the file.  For this
+project, that means you should add it to @code{threads_SRC} or
+@code{devices_SRC}.  Then run @code{make}.  If your new file
+doesn't get
+compiled, run @code{make clean} and then try again.
 
-@item
-@b{What does ``warning: no previous prototype for `@var{function}''
-mean?}
+When you modify the top-level @file{Makefile.build} and re-run
+@command{make}, the modified
+version should be automatically copied to
+@file{threads/build/Makefile}.  The converse is
+not true, so any changes will be lost the next time you run @code{make
+clean} from the @file{threads} directory.  Unless your changes are
+truly temporary, you should prefer to edit @file{Makefile.build}.
+
+A new @file{.h} file does not require editing the @file{Makefile}s.
+
+@item What does @code{warning: no previous prototype for `@var{func}'} mean?
 
 It means that you defined a non-@code{static} function without
 preceding it by a prototype.  Because non-@code{static} functions are
@@ -591,245 +621,264 @@ prototyped in a header file included before their definition.  To fix
 the problem, add a prototype in a header file that you include, or, if
 the function isn't actually used by other @file{.c} files, make it
 @code{static}.
-@end enumerate
 
-@menu
-* Problem 1-1 Alarm Clock FAQ::  
-* Problem 1-2 Join FAQ::        
-* Problem 1-3 Priority Scheduling FAQ::  
-* Problem 1-4 Advanced Scheduler FAQ::  
-@end menu
+@item What is the interval between timer interrupts?
 
-@node Problem 1-1 Alarm Clock FAQ
-@subsection Problem 1-1: Alarm Clock FAQ
+Timer interrupts occur @code{TIMER_FREQ} times per second.  You can
+adjust this value by editing @file{devices/timer.h}.  The default is
+100 Hz.
 
-@enumerate 1
-@item
-@b{Why can't I use most synchronization primitives in an interrupt
-handler?}
+We don't recommend changing this value, because any changes are likely
+to cause many of the tests to fail.
 
-As you've discovered, you cannot sleep in an external interrupt
-handler.  Since many lock, semaphore, and condition variable functions
-attempt to sleep, you won't be able to call those in
-@func{timer_interrupt}.  You may still use those that never sleep.
+@item How long is a time slice?
 
-Having said that, you need to make sure that global data does not get
-updated by multiple threads simultaneously executing
-@func{timer_sleep}.  Here are some pieces of information to think
-about:
+There are @code{TIME_SLICE} ticks per time slice.  This macro is
+declared in @file{threads/thread.c}.  The default is 4 ticks.
 
-@enumerate a
-@item
-Interrupts are turned off while @func{timer_interrupt} runs.  This
-means that @func{timer_interrupt} will not be interrupted by a
-thread running in @func{timer_sleep}.
+We don't recommend changing this value, because any changes are likely
+to cause many of the tests to fail.
+
+@item How do I run the tests?
+
+@xref{Testing}.
+
+@item Should I try running the tests with jitter?
+
+Using the jitter feature in Bochs (@pxref{Debugging versus Testing})
+is a great way to discover bugs that are timing dependent. However,
+the following tests are known to
+fail with jitter even if your code is correct: @code{alarm-priority},
+@code{alarm-simultaneous},
+@code{mlfqs-recent-1}, @code{mlfqs-fair-2}, @code{mlfqs-fair-20},
+@code{mlfqs-nice-2}, @code{mlfqs-nice-10}, and @code{priority-fifo}.
+The behavior of these tests can sometimes vary based on timing (e.g.,
+if a timer interrupt arrives at an inconvenient time).
+
+@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 (...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{fail} 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.
+
+@item How do interrupts get re-enabled in the new thread following @func{schedule}?
+
+Every path into @func{schedule} disables interrupts.  They eventually
+get re-enabled by the next thread to be scheduled.  Consider the
+possibilities: the new thread is running in @func{switch_thread} (but
+see below), which is called by @func{schedule}, which is called by one
+of a few possible functions:
+
+@itemize @bullet
 @item
-A thread in @func{timer_sleep}, however, can be interrupted by a
-call to @func{timer_interrupt}, except when that thread has turned
-off interrupts.
+@func{thread_exit}, but we'll never switch back into such a thread, so
+it's uninteresting.
 
 @item
-Examples of synchronization mechanisms have been presented in lecture.
-Going over these examples should help you understand when each type is
-useful or needed.
-@end enumerate
+@func{thread_yield}, which immediately restores the interrupt level upon
+return from @func{schedule}.
 
 @item
-@b{What about timer overflow due to the fact that times are defined as
-integers? Do I need to check for that?}
+@func{thread_block}, which is called from multiple places:
 
-Don't worry about the possibility of timer values overflowing.  Timer
-values are expressed as signed 63-bit numbers, which at 100 ticks per
-second should be good for almost 2,924,712,087 years.
-@end enumerate
+@itemize @minus
+@item
+@func{sema_down}, which restores the interrupt level before returning.
 
-@node Problem 1-2 Join FAQ
-@subsection Problem 1-2: Join FAQ
+@item
+@func{idle}, which enables interrupts with an explicit assembly STI
+instruction.
 
-@enumerate 1
 @item
-@b{Am I correct to assume that once a thread is deleted, it is no
-longer accessible by the parent (i.e.@: the parent can't call
-@code{thread_join(child)})?}
+@func{wait} in @file{devices/intq.c}, whose callers are responsible for
+re-enabling interrupts.
+@end itemize
+@end itemize
+
+There is a special case when a newly created thread runs for the first
+time.  Such a thread calls @func{intr_enable} as the first action in
+@func{kernel_thread}, which is at the bottom of the call stack for every
+kernel thread but the first.
+@end table
 
-A parent joining a child that has completed should be handled
-gracefully and should act as a no-op.
-@end enumerate
+@menu
+* Alarm Clock FAQ::             
+* Priority Scheduling FAQ::     
+* Advanced Scheduler FAQ::      
+@end menu
 
-@node Problem 1-3 Priority Scheduling FAQ
-@subsection Problem 1-3: Priority Scheduling FAQ
+@node Alarm Clock FAQ
+@subsection Alarm Clock FAQ
 
-@enumerate 1
-@item
-@b{Doesn't the priority scheduling lead to starvation? Or do I have to
-implement some sort of aging?}
+@table @b
+@item Do I need to account for timer values overflowing?
+
+Don't worry about the possibility of timer values overflowing.  Timer
+values are expressed as signed 64-bit numbers, which at 100 ticks per
+second should be good for almost 2,924,712,087 years.  By then, we
+expect Pintos to have been phased out of the Computer Science curriculum.
+@end table
+
+@node Priority Scheduling FAQ
+@subsection Priority Scheduling FAQ
+
+@table @b
+@item Doesn't priority scheduling lead to starvation?
 
-It is true that strict priority scheduling can lead to starvation
-because thread may not run if a higher-priority thread is runnable.
-In this problem, don't worry about starvation or any sort of aging
-technique.  Problem 4 will introduce a mechanism for dynamically
+Yes, strict priority scheduling can lead to starvation
+because a thread will not run if any higher-priority thread is runnable.
+The advanced scheduler introduces a mechanism for dynamically
 changing thread priorities.
 
-This sort of scheduling is valuable in real-time systems because it
+Strict priority scheduling is valuable in real-time systems because it
 offers the programmer more control over which jobs get processing
 time.  High priorities are generally reserved for time-critical
 tasks. It's not ``fair,'' but it addresses other concerns not
 applicable to a general-purpose operating system.
 
-@item
-@b{After a lock has been released, does the program need to switch to
-the highest priority thread that needs the lock (assuming that its
-priority is higher than that of the current thread)?}
+@item What thread should run after a lock has been released?
 
 When a lock is released, the highest priority thread waiting for that
-lock should be unblocked and put on the ready to run list.  The
+lock should be unblocked and put on the list of ready threads.  The
 scheduler should then run the highest priority thread on the ready
 list.
 
-@item
-@b{If a thread calls @func{thread_yield} and then it turns out that
-it has higher priority than any other threads, does the high-priority
-thread continue running?}
+@item If the highest-priority thread yields, does it continue running?
 
 Yes.  If there is a single highest-priority thread, it continues
 running until it blocks or finishes, even if it calls
 @func{thread_yield}.
+If multiple threads have the same highest priority,
+@func{thread_yield} should switch among them in ``round robin'' order.
 
-@item
-@b{If the highest priority thread is added to the ready to run list it
-should start execution immediately.  Is it immediate enough if I
-wait until next timer interrupt occurs?}
+@item What happens to the priority of a donating thread?
 
-The highest priority thread should run as soon as it is runnable,
-preempting whatever thread is currently running.
+Priority donation only changes the priority of the donee
+thread.  The donor thread's priority is unchanged.  
+Priority donation is not additive: if thread @var{A} (with priority 5) donates
+to thread @var{B} (with priority 3), then @var{B}'s new priority is 5, not 8.
 
-@item
-@b{What happens to the priority of the donating thread?  Do the priorities
-get swapped?}
+@item Can a thread's priority change while it is on the ready queue?
 
-No.  Priority donation only changes the priority of the low-priority
-thread.  The donating thread's priority stays unchanged.  Also note
-that priorities aren't additive: if thread A (with priority 5) donates
-to thread B (with priority 3), then B's new priority is 5, not 8.
+Yes.  Consider a ready, low-priority thread @var{L} that holds a lock.
+High-priority thread @var{H} attempts to acquire the lock and blocks,
+thereby donating its priority to ready thread @var{L}.
 
-@item 
-@b{Can a thread's priority be changed while it is sitting on the ready
-queue?}
+@item Can a thread's priority change while it is blocked?
 
-Yes.  Consider this case: low-priority thread L currently has a lock
-that high-priority thread H wants.  H donates its priority to L (the
-lock holder).  L finishes with the lock, and then loses the CPU and is
-moved to the ready queue.  Now L's old priority is restored while it
-is in the ready queue.
+Yes.  While a thread that has acquired lock @var{L} is blocked for any
+reason, its priority can increase by priority donation if a
+higher-priority thread attempts to acquire @var{L}.  This case is
+checked by the @code{priority-donate-sema} test.
 
-@item
-@b{Can a thread's priority change while it is sitting on the queue of a
-semaphore?}
+@item Can a thread added to the ready list preempt the processor?
 
-Yes.  Same scenario as above except L gets blocked waiting on a new
-lock when H restores its priority.
+Yes.  If a thread added to the ready list has higher priority than the
+running thread, the correct behavior is to immediately yield the
+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.
 
-@item
-@b{Why is pubtest3's FIFO test skipping some threads! I know my scheduler
-is round-robin'ing them like it's supposed to!  Our output is like this:}
+@item How does @func{thread_set_priority} affect a thread receiving donations?
 
-@example
-Thread 0 goes.
-Thread 2 goes.
-Thread 3 goes.
-Thread 4 goes.
-Thread 0 goes.
-Thread 1 goes.
-Thread 2 goes.
-Thread 3 goes.
-Thread 4 goes.
-@end example
+It sets the thread's base priority.  The thread's effective priority
+becomes the higher of the newly set priority or the highest donated
+priority.  When the donations are released, the thread's priority
+becomes the one set through the function call.  This behavior is checked
+by the @code{priority-donate-lower} test.
 
-@noindent @b{which repeats 5 times and then}
+@item Doubled test names in output make them fail.
+
+Suppose you are seeing output in which some test names are doubled,
+like this:
 
 @example
-Thread 1 goes.
-Thread 1 goes.
-Thread 1 goes.
-Thread 1 goes.
-Thread 1 goes.
+(alarm-priority) begin
+(alarm-priority) (alarm-priority) Thread priority 30 woke up.
+Thread priority 29 woke up.
+(alarm-priority) Thread priority 28 woke up.
 @end example
 
-This happens because context switches are being invoked by the test
-when it explicitly calls @func{thread_yield}.  However, the time
-slice timer is still alive and so, every tick (by default), thread 1
-gets switched out (caused by @func{timer_interrupt} calling
-@func{intr_yield_on_return}) before it gets a chance to run its
-mainline.  It is by coincidence that Thread 1 is the one that gets
-skipped in our example.  If we use a different jitter value, the same
-behavior is seen where a thread gets started and switched out
-completely.
-
-Solution: Increase the value of @code{TIME_SLICE} in
-@file{devices/timer.c} to a very high value, such as 10000, to see
-that the threads will round-robin if they aren't interrupted.
-
-@item
-@b{What happens when a thread is added to the ready list which has
-higher priority than the currently running thread?}
+What is happening is that output from two threads is being
+interleaved.  That is, one thread is printing @code{"(alarm-priority)
+Thread priority 29 woke up.\n"} and another thread is printing
+@code{"(alarm-priority) Thread priority 30 woke up.\n"}, but the first
+thread is being preempted by the second in the middle of its output.
+
+This problem indicates a bug in your priority scheduler.  After all, a
+thread with priority 29 should not be able to run while a thread with
+priority 30 has work to do.
+
+Normally, the implementation of the @code{printf()} function in the
+Pintos kernel attempts to prevent such interleaved output by acquiring
+a console lock during the duration of the @code{printf} call and
+releasing it afterwards.  However, the output of the test name,
+e.g., @code{(alarm-priority)}, and the message following it is output
+using two calls to @code{printf}, resulting in the console lock being
+acquired and released twice.
+@end table
 
-The correct behavior is to immediately yield the processor.  Your
-solution must act this way.
+@node Advanced Scheduler FAQ
+@subsection Advanced Scheduler FAQ
 
-@item
-@b{What should @func{thread_get_priority} return in a thread while
-its priority has been increased by a donation?}
+@table @b
+@item How does priority donation interact with the advanced scheduler?
 
-The higher (donated) priority.
-@end enumerate
+It doesn't have to.  We won't test priority donation and the advanced
+scheduler at the same time.
 
-@node Problem 1-4 Advanced Scheduler FAQ
-@subsection Problem 1-4: Advanced Scheduler FAQ
+@item Can I use one queue instead of 64 queues?
 
-@enumerate 1
-@item
-@b{What is the interval between timer interrupts?}
+Yes.  In general, your implementation may differ from the description,
+as long as its behavior is the same.
 
-Timer interrupts occur @code{TIMER_FREQ} times per second.  You can
-adjust this value by editing @file{devices/timer.h}.  The default is
-100 Hz.
+@item Some scheduler tests fail and I don't understand why.  Help!
 
-You can also adjust the number of timer ticks per time slice by
-modifying @code{TIME_SLICE} in @file{devices/timer.c}.
+If your implementation mysteriously fails some of the advanced
+scheduler tests, try the following:
 
+@itemize
 @item
-@b{Do I have to modify the dispatch table?}
-
-No, although you are allowed to. It is possible to complete
-this problem (i.e.@: demonstrate response time improvement)
-without doing so.
+Read the source files for the tests that you're failing, to make sure
+that you understand what's going on.  Each one has a comment at the
+top that explains its purpose and expected results.
 
 @item
-@b{When the scheduler changes the priority of a thread, how does this
-affect priority donation?}
-
-Short (official) answer: Don't worry about it. Your priority donation
-code may assume static priority assignment.
-
-Longer (unofficial) opinion: If you wish to take this into account,
-however, your design may end up being ``cleaner.''  You have
-considerable freedom in what actually takes place. I believe what
-makes the most sense is for scheduler changes to affect the
-``original'' (non-donated) priority.  This change may actually be
-masked by the donated priority.  Priority changes should only
-propagate with donations, not ``backwards'' from donees to donors.
+Double-check your fixed-point arithmetic routines and your use of them
+in the scheduler routines.
 
 @item
-@b{What is meant by ``static priority''?}
-
-Once thread A has donated its priority to thread B, if thread A's
-priority changes (due to the scheduler) while the donation still
-exists, you do not have to change thread B's donated priority.
-However, you are free to do so.
-
-@item
-@b{Do I have to make my dispatch table user-configurable?}
-
-No.  Hard-coding the dispatch table values is fine.
-@end enumerate
+Consider how much work your implementation does in the timer
+interrupt.  If the timer interrupt handler takes too long, then it
+will take away most of a timer tick from the thread that the timer
+interrupt preempted.  When it returns control to that thread, it
+therefore won't get to do much work before the next timer interrupt
+arrives.  That thread will therefore get blamed for a lot more CPU
+time than it actually got a chance to use.  This raises the
+interrupted thread's recent CPU count, thereby lowering its priority.
+It can cause scheduling decisions to change.  It also raises the load
+average.
+@end itemize
+@end table