+@section Threads Project
+
+@menu
+* Thread Support::
+* Synchronization::
+* Interrupt Handling::
+* Memory Allocation::
+@end menu
+
+@node Thread Support
+@subsection Thread Support
+
+@menu
+* struct thread::
+* Thread Functions::
+* Thread Switching::
+@end menu
+
+@node struct thread
+@subsubsection @code{struct thread}
+
+The main Pintos data structure for threads is @struct{thread},
+declared in @file{threads/thread.h}.
+
+@deftp {Structure} {@struct{thread}}
+Represents a thread or a user process. In the projects, you will have
+to add your own members to @struct{thread}. You may also change or
+delete the definitions of existing members.
+
+Every @struct{thread} occupies the beginning of its own page of
+memory. The rest of the page is used for the thread's stack, which
+grows downward from the end of the page. It looks like this:
+
+@example
+@group
+ 4 kB +---------------------------------+
+ | kernel stack |
+ | | |
+ | | |
+ | V |
+ | grows downward |
+ | |
+ | |
+ | |
+ | |
+ | |
+ | |
+ | |
+ | |
+ +---------------------------------+
+ | magic |
+ | : |
+ | : |
+ | status |
+ | tid |
+ 0 kB +---------------------------------+
+@end group
+@end example
+
+This has two consequences. First, @struct{thread} must not be allowed
+to grow too big. If it does, then there will not be enough room for the
+kernel stack. The base @struct{thread} is only a few bytes in size. It
+probably should stay well under 1 kB.
+
+Second, kernel stacks must not be allowed to grow too large. If a stack
+overflows, it will corrupt the thread state. Thus, kernel functions
+should not allocate large structures or arrays as non-static local
+variables. Use dynamic allocation with @func{malloc} or
+@func{palloc_get_page} instead (@pxref{Memory Allocation}).
+@end deftp
+
+@deftypecv {Member} {@struct{thread}} {tid_t} tid
+The thread's thread identifier or @dfn{tid}. Every thread must have a
+tid that is unique over the entire lifetime of the kernel. By
+default, @code{tid_t} is a @code{typedef} for @code{int} and each new
+thread receives the numerically next higher tid, starting from 1 for
+the initial process. You can change the type and the numbering scheme
+if you like.
+@end deftypecv
+
+@deftypecv {Member} {@struct{thread}} {enum thread_status} status
+The thread's state, one of the following:
+
+@defvr {Thread State} @code{THREAD_RUNNING}
+The thread is running. Exactly one thread is running at a given time.
+@func{thread_current} returns the running thread.
+@end defvr
+
+@defvr {Thread State} @code{THREAD_READY}
+The thread is ready to run, but it's not running right now. The
+thread could be selected to run the next time the scheduler is
+invoked. Ready threads are kept in a doubly linked list called
+@code{ready_list}.
+@end defvr
+
+@defvr {Thread State} @code{THREAD_BLOCKED}
+The thread is waiting for something, e.g.@: a lock to become
+available, an interrupt to be invoked. The thread won't be scheduled
+again until it transitions to the @code{THREAD_READY} state with a
+call to @func{thread_unblock}.
+@end defvr
+
+@defvr {Thread State} @code{THREAD_DYING}
+The thread will be destroyed by the scheduler after switching to the
+next thread.
+@end defvr
+@end deftypecv
+
+@deftypecv {Member} {@struct{thread}} {char} name[16]
+The thread's name as a string, or at least the first few characters of
+it.
+@end deftypecv
+
+@deftypecv {Member} {@struct{thread}} {uint8_t *} stack
+Every thread has its own stack to keep track of its state. When the
+thread is running, the CPU's stack pointer register tracks the top of
+the stack and this member is unused. But when the CPU switches to
+another thread, this member saves the thread's stack pointer. No
+other members are needed to save the thread's registers, because the
+other registers that must be saved are saved on the stack.
+
+When an interrupt occurs, whether in the kernel or a user program, an
+@struct{intr_frame} is pushed onto the stack. When the interrupt occurs
+in a user program, the @struct{intr_frame} is always at the very top of
+the page. @xref{Interrupt Handling}, for more information.
+@end deftypecv
+
+@deftypecv {Member} {@struct{thread}} {int} priority
+A thread priority, ranging from @code{PRI_MIN} (0) to @code{PRI_MAX}
+(63). Lower numbers correspond to @emph{higher} priorities, so that
+priority 0 is the highest priority and priority 63 is the lowest.
+Pintos as provided ignores thread priorities, but you will implement
+priority scheduling in project 1 (@pxref{Priority Scheduling}).
+@end deftypecv
+
+@deftypecv {Member} {@struct{thread}} {@struct{list_elem}} elem
+A ``list element'' used to put the thread into doubly linked lists,
+either the list of threads ready to run or a list of threads waiting
+on a semaphore. Take a look at @file{lib/kernel/list.h} for
+information on how to use Pintos doubly linked lists.
+@end deftypecv
+
+@deftypecv {Member} {@struct{thread}} {uint32_t *} pagedir
+Only present in project 2 and later.
+@end deftypecv
+
+@deftypecv {Member} {@struct{thread}} {unsigned} magic
+Always set to @code{THREAD_MAGIC}, which is just a random number defined
+in @file{threads/thread.c}, and used to detect stack overflow.
+@func{thread_current} checks that the @code{magic} member of the running
+thread's @struct{thread} is set to @code{THREAD_MAGIC}. Stack overflow
+will normally change this value, triggering the assertion. For greatest
+benefit, as you add members to @struct{thread}, leave @code{magic} as
+the final member.
+@end deftypecv
+
+@node Thread Functions
+@subsubsection Thread Functions
+
+@file{threads/thread.c} implements several public functions for thread
+support. Let's take a look at the most useful:
+
+@deftypefun void thread_init (void)
+Called by @func{main} to initialize the thread system. Its main
+purpose is to create a @struct{thread} for Pintos's initial thread.
+This is possible because the Pintos loader puts the initial
+thread's stack at the top of a page, in the same position as any other
+Pintos thread.
+
+Before @func{thread_init} runs,
+@func{thread_current} will fail because the running thread's
+@code{magic} value is incorrect. Lots of functions call
+@func{thread_current} directly or indirectly, including
+@func{lock_acquire} for locking a lock, so @func{thread_init} is
+called early in Pintos initialization.
+@end deftypefun
+
+@deftypefun void thread_start (void)
+Called by @func{main} to start the scheduler. Creates the idle
+thread, that is, the thread that is scheduled when no other thread is
+ready. Then enables interrupts, which as a side effect enables the
+scheduler because the scheduler runs on return from the timer interrupt, using
+@func{intr_yield_on_return} (@pxref{External Interrupt Handling}).
+@end deftypefun
+
+@deftypefun void thread_tick (void)
+Called by the timer interrupt at each timer tick. It keeps track of
+thread statistics and triggers the scheduler when a time slice expires.
+@end deftypefun
+
+@deftypefun void thread_print_stats (void)
+Called during Pintos shutdown to print thread statistics.
+@end deftypefun
+
+@deftypefun void thread_create (const char *@var{name}, int @var{priority}, thread_func *@var{func}, void *@var{aux})
+Creates and starts a new thread named @var{name} with the given
+@var{priority}, returning the new thread's tid. The thread executes
+@var{func}, passing @var{aux} as the function's single argument.
+
+@func{thread_create} allocates a page for the thread's
+@struct{thread} and stack and initializes its members, then it sets
+up a set of fake stack frames for it (more about this
+later). The thread is initialized in the blocked state, so the final
+action before returning is to unblock it, which allows the new thread to
+be scheduled.
+@end deftypefun
+
+@deftp {Type} {void thread_func (void *@var{aux})}
+This is the type of a thread function. Its @var{aux} argument is the
+value passed to @func{thread_create}.
+@end deftp
+
+@deftypefun void thread_block (void)
+Transitions the running thread from the running state to the blocked
+state. The thread will not run again until @func{thread_unblock} is
+called on it, so you'd better have some way arranged for that to happen.
+Because @func{thread_block} is so low-level, you should prefer to use
+one of the synchronization primitives instead (@pxref{Synchronization}).
+@end deftypefun
+
+@deftypefun void thread_unblock (struct thread *@var{thread})
+Transitions @var{thread}, which must be in the blocked state, to the
+ready state, allowing it to resume running. This is called when the
+event that the thread is waiting for occurs, e.g.@: when the lock that
+the thread is waiting on becomes available.
+@end deftypefun
+
+@deftypefun {struct thread *} thread_current (void)
+Returns the running thread.
+@end deftypefun
+
+@deftypefun {tid_t} thread_tid (void)
+Returns the running thread's thread id. Equivalent to
+@code{thread_current ()->tid}.
+@end deftypefun
+
+@deftypefun {const char *} thread_name (void)
+Returns the running thread's name. Equivalent to @code{thread_current
+()->name}.
+@end deftypefun
+
+@deftypefun void thread_exit (void) @code{NO_RETURN}
+Causes the current thread to exit. Never returns, hence
+@code{NO_RETURN} (@pxref{Function and Parameter Attributes}).
+@end deftypefun
+
+@deftypefun void thread_yield (void)
+Yields the CPU to the scheduler, which picks a new thread to run. The
+new thread might be the current thread, so you can't depend on this
+function to keep this thread from running for any particular length of
+time.
+@end deftypefun
+
+@deftypefun int thread_get_priority (void)
+@deftypefunx void thread_set_priority (int @var{new_priority})
+Skeleton to set and get thread priority. @xref{Priority Scheduling}.
+@end deftypefun
+
+@deftypefun int thread_get_nice (void)
+@deftypefunx void thread_set_nice (int @var{new_nice})
+@deftypefunx int thread_get_recent_cpu (void)
+@deftypefunx int thread_get_load_avg (void)
+Skeletons for the advanced scheduler. @xref{4.4BSD Scheduler}.
+@end deftypefun
+
+@node Thread Switching
+@subsubsection Thread Switching
+
+@func{schedule} is the function responsible for switching threads. It
+is internal to @file{threads/thread.c} and called only by the three
+public thread functions that need to switch threads:
+@func{thread_block}, @func{thread_exit}, and @func{thread_yield}.
+Before any of these functions call @func{schedule}, they disable
+interrupts (or ensure that they are already disabled) and then change
+the running thread's state to something other than running.
+
+The actual @func{schedule} implementation is simple. It records the
+current thread in local variable @var{cur}, determines the next thread
+to run as local variable @var{next} (by calling
+@func{next_thread_to_run}), and then calls @func{switch_threads} to do
+the actual thread switch. The thread we switched to was also running
+inside @func{switch_threads}, as are all the threads not currently
+running in Pintos, so the new thread now returns out of
+@func{switch_threads}, returning the previously running thread.
+
+@func{switch_threads} is an assembly language routine in
+@file{threads/switch.S}. It saves registers on the stack, saves the
+CPU's current stack pointer in the current @struct{thread}'s @code{stack}
+member, restores the new thread's @code{stack} into the CPU's stack
+pointer, restores registers from the stack, and returns.
+
+The rest of the scheduler is implemented as @func{schedule_tail}. It
+marks the new thread as running. If the thread we just switched from
+is in the dying state, then it also frees the page that contained the
+dying thread's @struct{thread} and stack. These couldn't be freed
+prior to the thread switch because the switch needed to use it.
+
+Running a thread for the first time is a special case. When
+@func{thread_create} creates a new thread, it goes through a fair
+amount of trouble to get it started properly. In particular, a new
+thread hasn't started running yet, so there's no way for it to be
+running inside @func{switch_threads} as the scheduler expects. To
+solve the problem, @func{thread_create} creates some fake stack frames
+in the new thread's stack:
+
+@itemize @bullet
+@item
+The topmost fake stack frame is for @func{switch_threads}, represented
+by @struct{switch_threads_frame}. The important part of this frame is
+its @code{eip} member, the return address. We point @code{eip} to
+@func{switch_entry}, indicating it to be the function that called
+@func{switch_entry}.
+
+@item
+The next fake stack frame is for @func{switch_entry}, an assembly
+language routine in @file{threads/switch.S} that adjusts the stack
+pointer,@footnote{This is because @func{switch_threads} takes
+arguments on the stack and the 80@var{x}86 SVR4 calling convention
+requires the caller, not the called function, to remove them when the
+call is complete. See @bibref{SysV-i386} chapter 3 for details.}
+calls @func{schedule_tail} (this special case is why
+@func{schedule_tail} is separate from @func{schedule}), and returns.
+We fill in its stack frame so that it returns into
+@func{kernel_thread}, a function in @file{threads/thread.c}.
+
+@item
+The final stack frame is for @func{kernel_thread}, which enables
+interrupts and calls the thread's function (the function passed to
+@func{thread_create}). If the thread's function returns, it calls
+@func{thread_exit} to terminate the thread.
+@end itemize
+
+@node Synchronization
+@subsection Synchronization
+
+If sharing of resources between threads is not handled in a careful,
+controlled fashion, then the result is usually a big mess.
+This is especially the case in operating system kernels, where
+faulty sharing can crash the entire machine. Pintos provides several
+synchronization primitives to help out.
+
+@menu
+* Disabling Interrupts::
+* Semaphores::
+* Locks::
+* Condition Variables::
+* Memory Barriers::
+@end menu
+
+@node Disabling Interrupts
+@subsubsection Disabling Interrupts
+
+The crudest way to do synchronization is to disable interrupts, that
+is, to temporarily prevent the CPU from responding to interrupts. If
+interrupts are off, no other thread will preempt the running thread,
+because thread preemption is driven by the timer interrupt. If
+interrupts are on, as they normally are, then the running thread may
+be preempted by another at any time, whether between two C statements
+or even within the execution of one.
+
+Incidentally, this means that Pintos is a ``preemptible kernel,'' that
+is, kernel threads can be preempted at any time. Traditional Unix
+systems are ``nonpreemptible,'' that is, kernel threads can only be
+preempted at points where they explicitly call into the scheduler.
+(User programs can be preempted at any time in both models.) As you
+might imagine, preemptible kernels require more explicit
+synchronization.
+
+You should have little need to set the interrupt state directly. Most
+of the time you should use the other synchronization primitives
+described in the following sections. The main reason to disable
+interrupts is to synchronize kernel threads with external interrupt
+handlers, which cannot sleep and thus cannot use most other forms of
+synchronization (@pxref{External Interrupt Handling}).
+
+Types and functions for disabling and enabling interrupts are in
+@file{threads/interrupt.h}.
+
+@deftp Type {enum intr_level}
+One of @code{INTR_OFF} or @code{INTR_ON}, denoting that interrupts are
+disabled or enabled, respectively.
+@end deftp
+
+@deftypefun {enum intr_level} intr_get_level (void)
+Returns the current interrupt state.
+@end deftypefun
+
+@deftypefun {enum intr_level} intr_set_level (enum intr_level @var{level})
+Turns interrupts on or off according to @var{level}. Returns the
+previous interrupt state.
+@end deftypefun
+
+@deftypefun {enum intr_level} intr_enable (void)
+Turns interrupts on. Returns the previous interrupt state.
+@end deftypefun
+
+@deftypefun {enum intr_level} intr_disable (void)
+Turns interrupts off. Returns the previous interrupt state.
+@end deftypefun
+
+@node Semaphores
+@subsubsection Semaphores
+
+Pintos' semaphore type and operations are declared in
+@file{threads/synch.h}.
+
+@deftp {Type} {struct semaphore}
+Represents a @dfn{semaphore}, a nonnegative integer together with two
+operators that manipulate it atomically, which are:
+
+@itemize @bullet
+@item
+``Down'' or ``P'': wait for the value to become positive, then
+decrement it.
+
+@item
+``Up'' or ``V'': increment the value (and wake up one waiting thread,
+if any).
+@end itemize
+
+A semaphore initialized to 0 may be used to wait for an event
+that will happen exactly once. For example, suppose thread @var{A}
+starts another thread @var{B} and wants to wait for @var{B} to signal
+that some activity is complete. @var{A} can create a semaphore
+initialized to 0, pass it to @var{B} as it starts it, and then
+``down'' the semaphore. When @var{B} finishes its activity, it
+``ups'' the semaphore. This works regardless of whether @var{A}
+``downs'' the semaphore or @var{B} ``ups'' it first.
+
+A semaphore initialized to 1 is typically used for controlling access
+to a resource. Before a block of code starts using the resource, it
+``downs'' the semaphore, then after it is done with the resource it
+``ups'' the resource. In such a case a lock, described below, may be
+more appropriate.
+
+Semaphores can also be initialized to values larger than 1. These are
+rarely used.
+@end deftp
+
+@deftypefun void sema_init (struct semaphore *@var{sema}, unsigned @var{value})
+Initializes @var{sema} as a new semaphore with the given initial
+@var{value}.
+@end deftypefun
+
+@deftypefun void sema_down (struct semaphore *@var{sema})
+Executes the ``down'' or ``P'' operation on @var{sema}, waiting for
+its value to become positive and then decrementing it by one.
+@end deftypefun
+
+@deftypefun bool sema_try_down (struct semaphore *@var{sema})
+Tries to execute the ``down'' or ``P'' operation on @var{sema},
+without waiting. Returns true if @var{sema} had a positive value
+that was successfully decremented, or false if it was already
+zero and thus could not be decremented. Calling this function in a
+tight loop wastes CPU time (use @func{sema_down} instead, or find a
+different approach).
+@end deftypefun
+
+@deftypefun void sema_up (struct semaphore *@var{sema})
+Executes the ``up'' or ``V'' operation on @var{sema},
+incrementing its value. If any threads are waiting on
+@var{sema}, wakes one of them up.
+@end deftypefun
+
+Semaphores are internally built out of disabling interrupt
+(@pxref{Disabling Interrupts}) and thread blocking and unblocking
+(@func{thread_block} and @func{thread_unblock}). Each semaphore maintains
+a list of waiting threads, using the linked list
+implementation in @file{lib/kernel/list.c}.
+
+@node Locks
+@subsubsection Locks
+
+Lock types and functions are declared in @file{threads/synch.h}.
+
+@deftp {Type} {struct lock}
+Represents a @dfn{lock}, a specialized semaphore with an initial value
+of 1 (@pxref{Semaphores}). The difference between a lock and such a
+semaphore is twofold. First, a semaphore does not have an owner,
+meaning that one thread can ``down'' the semaphore and then another one
+``up'' it, but a single thread must both acquire and release a lock.
+Second, a semaphore can have a value greater than 1, but a lock can only
+be owned by a single thread at a time. If these restrictions prove
+onerous, it's a good sign that a semaphore should be used, instead of a
+lock.
+
+Locks in Pintos are not ``recursive,'' that is, it is an error for the
+thread currently holding a lock to try to acquire that lock.
+@end deftp
+
+@deftypefun void lock_init (struct lock *@var{lock})
+Initializes @var{lock} as a new lock.
+@end deftypefun
+
+@deftypefun void lock_acquire (struct lock *@var{lock})
+Acquires @var{lock} for use by the current thread, first waiting for
+any current owner to release it if necessary.
+@end deftypefun
+
+@deftypefun bool lock_try_acquire (struct lock *@var{lock})
+Tries to acquire @var{lock} for use by the current thread, without
+waiting. Returns true if successful, false if the lock is already
+owned. Calling this function in a tight loop is a bad idea because it
+wastes CPU time (use @func{lock_acquire} instead).
+@end deftypefun
+
+@deftypefun void lock_release (struct lock *@var{lock})
+Releases @var{lock}, which the current thread must own.
+@end deftypefun
+
+@deftypefun bool lock_held_by_current_thread (const struct lock *@var{lock})
+Returns true if the running thread owns @var{lock},
+false otherwise.
+@end deftypefun
+
+@node Condition Variables
+@subsubsection Condition Variables
+
+Condition variable types and functions are declared in
+@file{threads/synch.h}.
+
+@deftp {Type} {struct condition}
+Represents a condition variable, which allows one piece of code to
+signal a condition
+and cooperating code to receive the signal and act upon it. Each
+condition variable is associated with a lock. A given condition
+variable is associated with only a single lock, but one lock may be
+associated with any number of condition variables. A set of condition
+variables taken together with their lock is called a ``monitor.''
+
+A thread that owns the monitor lock is said to be ``in the monitor.''
+The thread in the monitor has control over all the data protected by
+the lock. It may freely examine or modify this data. If it discovers
+that it needs to wait for some condition to become true, then it
+``waits'' on the associated condition, which releases the lock and
+waits for the condition to be signaled. If, on the other hand, it has
+caused one of these conditions to become true, it ``signals'' the
+condition to wake up one waiter, or ``broadcasts'' the condition to
+wake all of them.
+
+Pintos monitors are ``Mesa'' style, not
+``Hoare'' style. That is, sending and receiving a signal are not an
+atomic operation. Thus, typically the caller must recheck the
+condition after the wait completes and, if necessary, wait again.
+@end deftp
+
+@deftypefun void cond_init (struct condition *@var{cond})
+Initializes @var{cond} as a new condition variable.
+@end deftypefun
+
+@deftypefun void cond_wait (struct condition *@var{cond})
+Atomically releases @var{lock} (the monitor lock) and waits for
+@var{cond} to be signaled by some other piece of code. After
+@var{cond} is signaled, reacquires @var{lock} before returning.
+@var{lock} must be held before calling this function.
+@end deftypefun
+
+@deftypefun void cond_signal (struct condition *@var{cond}, struct lock *@var{lock})
+If any threads are waiting on @var{cond} (protected by monitor lock
+@var{lock}), then this function wakes up one of them. If no threads are
+waiting, returns without performing any action.
+@var{lock} must be held before calling this function.
+@end deftypefun
+
+@deftypefun void cond_broadcast (struct condition *@var{cond}, struct lock *@var{lock})
+Wakes up all threads, if any, waiting on @var{cond} (protected by
+monitor lock @var{lock}). @var{lock} must be held before calling this
+function.
+@end deftypefun
+
+@subsubheading Monitor Example
+
+The classical example of a monitor is handling a buffer into which one
+``producer'' thread writes characters and out of which a second
+``consumer'' thread reads characters. To implement this case we need,
+besides the monitor lock, two condition variables which we will call
+@var{not_full} and @var{not_empty}:
+
+@example
+char buf[BUF_SIZE]; /* @r{Buffer.} */
+size_t n = 0; /* @r{0 <= n <= @var{BUF_SIZE}: # of characters in buffer.} */
+size_t head = 0; /* @r{@var{buf} index of next char to write (mod @var{BUF_SIZE}).} */
+size_t tail = 0; /* @r{@var{buf} index of next char to read (mod @var{BUF_SIZE}).} */
+struct lock lock; /* @r{Monitor lock.} */
+struct condition not_empty; /* @r{Signaled when the buffer is not empty.} */
+struct condition not_full; /* @r{Signaled when the buffer is not full.} */
+
+@dots{}@r{initialize the locks and condition variables}@dots{}
+
+void put (char ch) @{
+ lock_acquire (&lock);
+ while (n == BUF_SIZE) /* @r{Can't add to @var{buf} as long as it's full.} */
+ cond_wait (¬_full, &lock);
+ buf[head++ % BUF_SIZE] = ch; /* @r{Add @var{ch} to @var{buf}.} */
+ n++;
+ cond_signal (¬_empty, &lock); /* @r{@var{buf} can't be empty anymore.} */
+ lock_release (&lock);
+@}
+
+char get (void) @{
+ char ch;
+ lock_acquire (&lock);
+ while (n == 0) /* @r{Can't read @var{buf} as long as it's empty.} */
+ cond_wait (¬_empty, &lock);
+ ch = buf[tail++ % BUF_SIZE]; /* @r{Get @var{ch} from @var{buf}.} */
+ n--;
+ cond_signal (¬_full, &lock); /* @r{@var{buf} can't be full anymore.} */
+ lock_release (&lock);
+@}
+@end example
+
+@node Memory Barriers
+@subsubsection Memory Barriers
+
+Suppose we add a ``feature'' that, whenever a timer interrupt
+occurs, the character in global variable @code{timer_put_char} is
+printed on the console, but only if global Boolean variable
+@code{timer_do_put} is true.
+
+If interrupts are enabled, this code for setting up @samp{x} to be
+printed is clearly incorrect, because the timer interrupt could intervene
+between the two assignments:
+
+@example
+timer_do_put = true; /* INCORRECT CODE */
+timer_put_char = 'x';
+@end example
+
+It might not be as obvious that the following code is just as
+incorrect:
+
+@example
+timer_put_char = 'x'; /* INCORRECT CODE */
+timer_do_put = true;
+@end example
+
+The reason this second example might be a problem is that the compiler
+is, in general, free to reorder operations when it doesn't have a
+visible reason to keep them in the same order. In this case, the
+compiler doesn't know that the order of assignments is important, so its
+optimization pass is permitted to exchange their order.
+There's no telling whether it will actually do this, and it is possible
+that passing the compiler different optimization flags or changing
+compiler versions will produce different behavior.
+
+The following is @emph{not} a solution, because locks neither prevent
+interrupts nor prevent the compiler from reordering the code within the
+region where the lock is held:
+
+@example
+lock_acquire (&timer_lock); /* INCORRECT CODE */
+timer_put_char = 'x';
+timer_do_put = true;
+lock_release (&timer_lock);
+@end example
+
+Fortunately, real solutions do exist. One possibility is to
+disable interrupts around the assignments. This does not prevent
+reordering, but it makes the assignments atomic as observed by the
+interrupt handler. It also has the extra runtime cost of disabling and
+re-enabling interrupts:
+
+@example
+enum intr_level old_level = intr_disable ();
+timer_put_char = 'x';
+timer_do_put = true;
+intr_set_level (old_level);
+@end example
+
+A second possibility is to mark the declarations of
+@code{timer_put_char} and @code{timer_do_put} as @samp{volatile}. This
+keyword tells the compiler that the variables are externally observable
+and allows it less latitude for optimization. However, the semantics of
+@samp{volatile} are not well-defined, so it is not a good general
+solution.
+
+Usually, the best solution is to use a compiler feature called a
+@dfn{memory barrier}, a special statement that prevents the compiler
+from reordering memory operations across the barrier. In Pintos,
+@file{threads/synch.h} defines the @code{barrier()} macro as a memory
+barrier. Here's how we would use a memory barrier to fix this code:
+
+@example
+timer_put_char = 'x';
+barrier ();
+timer_do_put = true;
+@end example
+
+The compiler also treats invocation of any function defined externally,
+that is, in another source file, as a limited form of a memory barrier.
+Specifically, the compiler assumes that any externally defined function
+may access any statically or dynamically allocated data and any local
+variable whose address is taken. This often means that explicit
+barriers can be omitted, and, indeed, this is why the base Pintos code
+does not need any barriers.
+
+A function defined in the same source file, or in a header included by
+the source file, cannot be relied upon as a memory barrier.
+This applies even to invocation of a function before its
+definition, because the compiler may read and parse the entire source
+file before performing optimization.
+
+@node Interrupt Handling
+@subsection Interrupt Handling
+
+An @dfn{interrupt} notifies the CPU of some event. Much of the work
+of an operating system relates to interrupts in one way or another.
+For our purposes, we classify interrupts into two broad categories:
+
+@itemize @bullet
+@item
+@dfn{External interrupts}, that is, interrupts originating outside the
+CPU. These interrupts come from hardware devices such as the system
+timer, keyboard, serial ports, and disks. External interrupts are
+@dfn{asynchronous}, meaning that their delivery is not
+synchronized with normal CPU activities. External interrupts
+are what @func{intr_disable} and related functions
+postpone (@pxref{Disabling Interrupts}).
+
+@item
+@dfn{Internal interrupts}, that is, interrupts caused by something
+executing on the CPU. These interrupts are caused by something
+unusual happening during instruction execution: accessing invalid
+memory (a @dfn{page fault}), executing invalid instructions, and
+various other disallowed activities. Because they are caused by CPU
+instructions, internal interrupts are @dfn{synchronous} or
+synchronized with CPU instructions. @func{intr_disable} does not
+disable internal interrupts.
+@end itemize
+
+Because the CPU treats all interrupts largely the same way, regardless
+of source, Pintos uses the same infrastructure for both internal and
+external interrupts, to a point. The following section describes this
+common infrastructure, and sections after that give the specifics of
+external and internal interrupts.
+
+If you haven't already read chapter 3 in @bibref{IA32-v1}, it is
+recommended that you do so now. You might also want to skim chapter 5
+in @bibref{IA32-v3}.
+
+@menu
+* Interrupt Infrastructure::
+* Internal Interrupt Handling::
+* External Interrupt Handling::
+@end menu
+
+@node Interrupt Infrastructure
+@subsubsection Interrupt Infrastructure
+
+When an interrupt occurs while the kernel is running, the CPU saves
+its most essential state on the stack and jumps to an interrupt
+handler routine. The 80@var{x}86 architecture allows for 256 possible
+interrupts, each of which can have its own handler. The handler for
+each interrupt is defined in an array called the @dfn{interrupt
+descriptor table} or IDT.
+
+In Pintos, @func{intr_init} in @file{threads/interrupt.c} sets up the
+IDT so that each entry points to a unique entry point in
+@file{threads/intr-stubs.S} named @func{intr@var{NN}_stub}, where
+@var{NN} is the interrupt number in
+hexadecimal. Because the CPU doesn't give
+us any other way to find out the interrupt number, this entry point
+pushes the interrupt number on the stack. Then it jumps to
+@func{intr_entry}, which pushes all the registers that the processor
+didn't already save for us, and then calls @func{intr_handler}, which
+brings us back into C in @file{threads/interrupt.c}.
+
+The main job of @func{intr_handler} is to call any function that has
+been registered for handling the particular interrupt. (If no
+function is registered, it dumps some information to the console and
+panics.) It does some extra processing for external
+interrupts that we'll discuss later.
+
+When @func{intr_handler} returns, the assembly code in
+@file{threads/intr-stubs.S} restores all the CPU registers saved
+earlier and directs the CPU to return from the interrupt.
+
+A few types and functions apply to both internal and external
+interrupts.
+
+@deftp {Type} {void intr_handler_func (struct intr_frame *@var{frame})}
+This is how an interrupt handler function must be declared. Its @var{frame}
+argument (see below) allows it to determine the cause of the interrupt
+and the state of the thread that was interrupted.
+@end deftp
+
+@deftp {Type} {struct intr_frame}
+The stack frame of an interrupt handler, as saved by CPU, the interrupt
+stubs, and @func{intr_entry}. Its most interesting members are described
+below.
+@end deftp
+
+@deftypecv {Member} {@struct{intr_frame}} uint32_t edi
+@deftypecvx {Member} {@struct{intr_frame}} uint32_t esi
+@deftypecvx {Member} {@struct{intr_frame}} uint32_t ebp
+@deftypecvx {Member} {@struct{intr_frame}} uint32_t esp_dummy
+@deftypecvx {Member} {@struct{intr_frame}} uint32_t ebx
+@deftypecvx {Member} {@struct{intr_frame}} uint32_t edx
+@deftypecvx {Member} {@struct{intr_frame}} uint32_t ecx
+@deftypecvx {Member} {@struct{intr_frame}} uint32_t eax
+@deftypecvx {Member} {@struct{intr_frame}} uint16_t es
+@deftypecvx {Member} {@struct{intr_frame}} uint16_t ds
+Register values in the interrupted thread saved by @func{intr_entry}.
+The @code{esp_dummy} value isn't actually used (refer to the
+description of @code{PUSHA} in @bibref{IA32-v2b} for details).
+@end deftypecv
+
+@deftypecv {Member} {@struct{intr_frame}} uint32_t vec_no
+The interrupt vector number, ranging from 0 to 255.
+@end deftypecv
+
+@deftypecv {Member} {@struct{intr_frame}} uint32_t error_code
+The ``error code'' pushed on the stack by the CPU for some internal
+interrupts.
+@end deftypecv
+
+@deftypecv {Member} {@struct{intr_frame}} void (*eip) (void)
+The address of the next instruction to be executed by the interrupted
+thread.
+@end deftypecv
+
+@deftypecv {Member} {@struct{intr_frame}} {void *} esp
+The interrupted thread's stack pointer.
+@end deftypecv
+
+@deftypefun {const char *} intr_name (uint8_t @var{vec})
+Returns the name of the interrupt numbered @var{vec}, or
+@code{"unknown"} if the interrupt has no registered name.
+@end deftypefun
+
+@node Internal Interrupt Handling
+@subsubsection Internal Interrupt Handling
+
+When an internal interrupt occurs, it is because the running kernel
+thread (or, starting from project 2, the running user process) has
+caused it. Thus, because it is related to a thread (or process), an
+internal interrupt is said to happen in a ``process context.''
+
+In an internal interrupt, it can make sense to examine the
+@struct{intr_frame} passed to the interrupt handler, or even to modify
+it. When the interrupt returns, modified members
+in @struct{intr_frame} become changes to the thread's registers.
+We'll use this in project 2 to return values from system call
+handlers.
+
+There are no special restrictions on what an internal interrupt
+handler can or can't do. Generally they should run with interrupts
+enabled, just like other code, and so they can be preempted by other
+kernel threads. Thus, they do need to synchronize with other threads
+on shared data and other resources (@pxref{Synchronization}).
+
+@deftypefun void intr_register_int (uint8_t @var{vec}, int @var{dpl}, enum intr_level @var{level}, intr_handler_func *@var{handler}, const char *@var{name})
+Registers @var{func} to be called when internal interrupt numbered
+@var{vec} is triggered. Names the interrupt @var{name} for debugging
+purposes.
+
+If @var{level} is @code{INTR_OFF} then handling of further interrupts
+will be disabled while the interrupt is being processed. Interrupts
+should normally be turned on during the handling of an internal
+interrupt.
+
+@var{dpl} determines how the interrupt can be
+invoked. If @var{dpl} is 0, then the interrupt can be invoked only by
+kernel threads. Otherwise @var{dpl} should be 3, which allows user
+processes to invoke the interrupt as well (this is useful only
+starting with project 2).
+@end deftypefun
+
+@node External Interrupt Handling
+@subsubsection External Interrupt Handling
+
+Whereas an internal interrupt runs in the context of the thread that
+caused it, external interrupts do not have any predictable context.
+They are asynchronous, so it can be invoked at any time that
+interrupts have not been enabled. We say that an external interrupt
+runs in an ``interrupt context.''
+
+In an external interrupt, the @struct{intr_frame} passed to the
+handler is not very meaningful. It describes the state of the thread
+or process that was interrupted, but there is no way to predict which
+one that is. It is possible, although rarely useful, to examine it, but
+modifying it is a recipe for disaster.
+
+The activities of an external interrupt handler are severely
+restricted. First, only one external interrupt may be processed at a
+time, that is, nested external interrupt handling is not supported.
+This means that external interrupts must be processed with interrupts
+disabled (@pxref{Disabling Interrupts}) and that interrupts may not be
+enabled at any point during their execution.
+
+Second, an interrupt handler must not call any function that can
+sleep, which rules out @func{thread_yield}, @func{lock_acquire}, and
+many others. This is because external interrupts use space on the
+stack of the kernel thread that was running at the time the interrupt
+occurred. If the interrupt handler tried to sleep and that thread
+resumed, then the two uses of the single stack would interfere, which
+cannot be allowed.
+
+Because an external interrupt runs with interrupts disabled, it
+effectively monopolizes the machine and delays all other activities.
+Therefore, external interrupt handlers should complete as quickly as
+they can. Any activities that require much CPU time should instead
+run in a kernel thread, possibly a thread whose activity is triggered
+by the interrupt using some synchronization primitive.
+
+External interrupts are also special because they are controlled by a
+pair of devices outside the CPU called @dfn{programmable interrupt
+controllers}, @dfn{PICs} for short. When @func{intr_init} sets up the
+CPU's IDT, it also initializes the PICs for interrupt handling. The
+PICs also must be ``acknowledged'' at the end of processing for each
+external interrupt. @func{intr_handler} takes care of that by calling
+@func{pic_end_of_interrupt}, which sends the proper signals to the
+right PIC.
+
+The following additional functions are related to external
+interrupts.
+
+@deftypefun void intr_register_ext (uint8_t @var{vec}, intr_handler_func *@var{handler}, const char *@var{name})
+Registers @var{handler} to be called when external interrupt numbered
+@var{vec} is triggered. Names the interrupt @var{name} for debugging
+purposes. The handler will run with interrupts disabled.
+@end deftypefun
+
+@deftypefun bool intr_context (void)
+Returns true if we are running in an interrupt context, otherwise
+false. Mainly used at the beginning of functions that might sleep
+or that otherwise should not be called from interrupt context, in this
+form:
+@example
+ASSERT (!intr_context ());
+@end example
+@end deftypefun
+
+@deftypefun void intr_yield_on_return (void)
+When called in an interrupt context, causes @func{thread_yield} to be
+called just before the interrupt returns. This is used, for example,
+in the timer interrupt handler to cause a new thread to be scheduled
+when a thread's time slice expires.
+@end deftypefun
+
+@node Memory Allocation
+@subsection Memory Allocation
+
+Pintos contains two memory allocators, one that allocates memory in
+units of a page, and one that can allocate blocks of any size.
+
+@menu
+* Page Allocator::
+* Block Allocator::
+@end menu
+
+@node Page Allocator
+@subsubsection Page Allocator
+
+The page allocator declared in @file{threads/palloc.h} allocates
+memory in units of a page. It is most often used to allocate memory
+one page at a time, but it can also allocate multiple contiguous pages
+at once.
+
+The page allocator divides the memory it allocates into two pools,
+called the kernel and user pools. By default, each pool gets half of
+system memory, but this can be changed with a kernel command line
+option (@pxref{Why PAL_USER?}). An allocation request draws from one
+pool or the other. If one pool becomes empty, the other may still
+have free pages. The user pool should be used for allocating memory
+for user processes and the kernel pool for all other allocations.
+This will only become important starting with project 3. Until then,
+all allocations should be made from the kernel pool.
+
+Each pool's usage is tracked with a bitmap, one bit per page in
+the pool. A request to allocate @var{n} pages scans the bitmap
+for @var{n} consecutive bits set to
+false, indicating that those pages are free, and then sets those bits
+to true to mark them as used. This is a ``first fit'' allocation
+strategy.
+
+The page allocator is subject to fragmentation. That is, it may not
+be possible to allocate @var{n} contiguous pages even though @var{n}
+or more pages are free, because the free pages are separated by used
+pages. In fact, in pathological cases it may be impossible to
+allocate 2 contiguous pages even though @var{n} / 2 pages are free!
+Single-page requests can't fail due to fragmentation, so
+it is best to limit, as much as possible, the need for multiple
+contiguous pages.
+
+Pages may not be allocated from interrupt context, but they may be
+freed.
+
+When a page is freed, all of its bytes are cleared to @t{0xcc}, as
+a debugging aid (@pxref{Debugging Tips}).
+
+Page allocator types and functions are described below.
+
+@deftp {Type} {enum palloc_flags}
+A set of flags that describe how to allocate pages. These flags may
+be combined in any combination.
+@end deftp
+
+@defvr {Page Allocator Flag} @code{PAL_ASSERT}
+If the pages cannot be allocated, panic the kernel. This is only
+appropriate during kernel initialization. User processes
+should never be permitted to panic the kernel.
+@end defvr
+
+@defvr {Page Allocator Flag} @code{PAL_ZERO}
+Zero all the bytes in the allocated pages before returning them. If not
+set, the contents of newly allocated pages are unpredictable.
+@end defvr
+
+@defvr {Page Allocator Flag} @code{PAL_USER}
+Obtain the pages from the user pool. If not set, pages are allocated
+from the kernel pool.
+@end defvr
+
+@deftypefun {void *} palloc_get_page (enum palloc_flags @var{flags})
+Obtains and returns a single page, allocating it in the manner specified by
+@var{flags}. Returns a null pointer if no pages are
+free.
+@end deftypefun
+
+@deftypefun {void *} palloc_get_multiple (enum palloc_flags @var{flags}, size_t @var{page_cnt})
+Obtains @var{page_cnt} contiguous free pages, allocating them in the
+manner specified by @var{flags}, and returns them. Returns a null
+pointer if no pages are free.
+@end deftypefun
+
+@deftypefun void palloc_free_page (void *@var{page})
+Frees @var{page}, which must have been obtained using
+@func{palloc_get_page} or @func{palloc_get_multiple}.
+@end deftypefun
+
+@deftypefun void palloc_free_multiple (void *@var{pages}, size_t @var{page_cnt})
+Frees the @var{page_cnt} contiguous pages starting at @var{pages}.
+All of the pages must have been obtained using @func{palloc_get_page}
+or @func{palloc_get_multiple}.
+@end deftypefun
+
+@node Block Allocator
+@subsubsection Block Allocator
+
+The block allocator, declared in @file{threads/malloc.h}, can allocate
+blocks of any size. It is layered on top of the page allocator
+described in the previous section. Blocks returned by the block
+allocator are obtained from the kernel pool.
+
+The block allocator uses two different strategies for allocating
+memory. The first of these applies to ``small'' blocks, those 1 kB or
+smaller (one
+fourth of the the page size). These allocations are rounded up to the
+nearest power of 2, or 16 bytes, whichever is larger. Then they are
+grouped into a page used only for allocations of the smae
+size.
+
+The second strategy applies to allocating ``large'' blocks, those larger
+than 1 kB.
+These allocations (plus a small amount of overhead) are rounded up to
+the nearest page in size, and then the block allocator requests that
+number of contiguous pages from the page allocator.
+
+In either case, the difference between the allocation requested size
+and the actual block size is wasted. A real operating system would
+carefully tune its allocator to minimize this waste, but this is
+unimportant in an instructional system like Pintos.
+
+As long as a page can be obtained from the page allocator, small
+allocations always succeed. Most small allocations will not require a
+new page from the page allocator at all. However, large allocations
+always require calling into the page allocator, and any allocation
+that needs more than one contiguous page can fail due to fragmentation,
+as already discussed in the previous section. Thus, you should
+minimize the number of large allocations in your code, especially
+those over approximately 4 kB each.
+
+The interface to the block allocator is through the standard C library
+functions @func{malloc}, @func{calloc}, and @func{free}.
+
+When a block is freed, all of its bytes are cleared to @t{0xcc}, as
+a debugging aid (@pxref{Debugging Tips}).
+
+The block allocator may not be called from interrupt context.