-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 @code{malloc()} has a @w{2 kB} block size
-limit. If you need larger chunks, consider using a linked structure
-instead.
-
-@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-2: 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.
+the page allocator and the block allocator (@pxref{Memory Allocation}).
+
+@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
+hope is that presenting this overview will give you a start on what
+code to look at.
+
+@table @file
+@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 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 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 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. 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 @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. @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. @xref{Page Allocator}, for more information.
+
+@item malloc.c
+@itemx malloc.h
+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. @xref{Interrupt Handling}, for more information.
+
+@item intr-stubs.S
+@itemx intr-stubs.h
+Assembly code for low-level interrupt handling. @xref{Interrupt
+Infrastructure}, for more information.
+
+@item synch.c
+@itemx synch.h
+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 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
+* devices code::
+* lib files::
+@end menu
+
+@node devices code
+@subsubsection @file{devices} code
+
+The basic threaded kernel also includes these files in the
+@file{devices} directory:
+
+@table @file
+@item timer.c
+@itemx timer.h
+System timer that ticks, by default, 100 times per second. You will
+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}
+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.
+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
+@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
+project 2, but it is not part of the kernel.) Here's a few more
+details:
+
+@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. 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.
+
+@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