-@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. If you use the Bochs configuration files we provide,
-which specify @samp{ips: @var{n}} where @var{n} is a number of
-simulated instructions per second, your simulations can be
-reproducible.
-
-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 put a line
-@samp{ips-jitter: @var{seed}}, where @var{seed} is an integer, into
-your Bochs configuration file, then 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 @code{intr_disable()} or
-@code{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 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 (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 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 4 (the MLFQS) builds on the features you
-implement in Problem 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 3 fully working before you begin to tackle
-Problem 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 @code{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 @code{timer_sleep()} is expressed in timer ticks, not
-in milliseconds or some other unit.
-
-@node Problem 1-2 Join
-@section Problem 1-2: Join
-
-Implement @code{thread_join(struct thread *)} 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 thread passed as an
-argument exits. If A is the running thread and B is the argument,
-then we say that ``A joins B'' in this case.
-
-The model for @code{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 @code{thread_join()} to have the same restriction.
-That is, a thread may only join on 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.
-
-The behavior of calling @code{thread_join()} on an thread that is not
-the caller's child is undefined. You need not handle this case
-gracefully.
-
-Consider all the ways a join can occur: nested joins (A joins B when B
-is joined on C), multiple joins (A joins B, then A joins C), and so
-on. Does your join work if @code{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.
-
-@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
-@code{thread_set_priority()} to set the priority of a thread and
-@code{thread_get_priority()} to get the priority of a thread. There
-are already prototypes for these functions in @file{threads/thread.h},
-which you should not change.
+@table @file
+@item ctype.h
+@itemx inttypes.h
+@itemx limits.h
+@itemx stdarg.h
+@itemx stdbool.h
+@itemx stddef.h
+@itemx stdint.h
+@itemx stdio.c
+@itemx stdio.h
+@itemx stdlib.c
+@itemx stdlib.h
+@itemx string.c
+@itemx string.h
+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.
+
+@item debug.c
+@itemx debug.h
+Functions and macros to aid debugging. @xref{Debugging Tools}, for
+more information.
+
+@item random.c
+@itemx random.h
+Pseudo-random number generator.
+
+@item round.h
+Macros for rounding.
+
+@item syscall-nr.h
+System call numbers. Not used until project 2.
+
+@item kernel/list.c
+@itemx kernel/list.h
+Doubly linked list implementation. Used all over the Pintos code, and
+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 it in project 1.
+
+@item kernel/hash.c
+@itemx kernel/hash.h
+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 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