@end deftypecv
@deftypecv {Member} {@struct{thread}} {enum thread_status} status
+@anchor{Thread States}
The thread's state, one of the following:
@defvr {Thread State} @code{THREAD_RUNNING}
@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
+up a set of fake stack frames for it (@pxref{Thread Switching}). The
+thread is initialized in the blocked state, then unblocked just before
+returning, which allows the new thread to
+be scheduled (@pxref{Thread States}).
@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}.
+This is the type of the function passed to @func{thread_create}, whose
+@var{aux} argument is passed along as the function's argument.
@end deftp
+@end deftypefun
@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
+state (@pxref{Thread States}). 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}).
@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
+ready state, allowing it to resume running (@pxref{Thread States}).
+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 int thread_get_priority (void)
@deftypefunx void thread_set_priority (int @var{new_priority})
-Skeleton to set and get thread priority. @xref{Priority Scheduling}.
+Stub 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}.
+Stubs for the advanced scheduler. @xref{4.4BSD Scheduler}.
@end deftypefun
@node Thread Switching
@subsection Thread Switching
-@func{schedule} is the function responsible for switching threads. It
+@func{schedule} is 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}.
interrupts (or ensure that they are already disabled) and then change
the running thread's state to something other than running.
-@func{schedule} is simple but tricky. It records the
+@func{schedule} is short but tricky. 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
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
+The rest of the scheduler is implemented in @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
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
+amount of trouble to get it started properly. In particular, the 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
@section Synchronization
If sharing of resources between threads is not handled in a careful,
-controlled fashion, then the result is usually a big mess.
+controlled fashion, 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.
* Disabling Interrupts::
* Semaphores::
* Locks::
-* Condition Variables::
+* Monitors::
* Memory Barriers::
@end menu
handlers, which cannot sleep and thus cannot use most other forms of
synchronization (@pxref{External Interrupt Handling}).
+Some external interrupts cannot be postponed, even by disabling
+interrupts. These interrupts, called @dfn{non-maskable interrupts}
+(NMIs), are supposed to be used only in emergencies, e.g.@: when the
+computer is on fire. Pintos does not handle non-maskable interrupts.
+
Types and functions for disabling and enabling interrupts are in
@file{threads/interrupt.h}.
@node Semaphores
@subsection 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:
+A @dfn{semaphore} is a nonnegative integer together with two operators
+that manipulate it atomically, which are:
@itemize @bullet
@item
Semaphores can also be initialized to values larger than 1. These are
rarely used.
+
+Semaphores were invented by Edsger Dijkstra and first used in the THE
+operating system (@bibref{THE}).
+
+Pintos' semaphore type and operations are declared in
+@file{threads/synch.h}.
+
+@deftp {Type} {struct semaphore}
+Represents a semaphore.
@end deftp
@deftypefun void sema_init (struct semaphore *@var{sema}, unsigned @var{value})
@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).
+without waiting. Returns true if @var{sema}
+was successfully decremented, or false if it was already
+zero and thus could not be decremented without waiting. Calling this
+function in a
+tight loop wastes CPU time, so use @func{sema_down} or find a
+different approach instead.
@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.
+
+Unlike most synchronization primitives, @func{sema_up} may be called
+inside an external interrupt handler (@pxref{External Interrupt
+Handling}).
@end deftypefun
Semaphores are internally built out of disabling interrupt
@node Locks
@subsection Locks
-Lock types and functions are declared in @file{threads/synch.h}.
+A @dfn{lock} is like a semaphore with an initial value of 1
+(@pxref{Semaphores}). A lock's equivalent of ``up'' is called
+``acquire'', and the ``down'' operation is called ``release''.
-@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.
+Compared to a semaphore, a lock has one added restriction: only the
+thread that acquires a lock, called the lock's ``owner'', is allowed to
+release it. If this restriction is a problem, 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.
+
+Lock types and functions are declared in @file{threads/synch.h}.
+
+@deftp {Type} {struct lock}
+Represents a lock.
@end deftp
@deftypefun void lock_init (struct lock *@var{lock})
Initializes @var{lock} as a new lock.
+The lock is not initially owned by any thread.
@end deftypefun
@deftypefun void lock_acquire (struct lock *@var{lock})
-Acquires @var{lock} for use by the current thread, first waiting for
+Acquires @var{lock} for the current thread, first waiting for
any current owner to release it if necessary.
@end deftypefun
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).
+wastes CPU time, so use @func{lock_acquire} instead.
@end deftypefun
@deftypefun void lock_release (struct lock *@var{lock})
@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
-@subsection Condition Variables
+There is no function to test whether an arbitrary thread owns a lock,
+because the answer could change before the caller could act on it.
+@end deftypefun
+
+@node Monitors
+@subsection Monitors
+
+A @dfn{monitor} is a higher-level form of synchronization than a
+semaphore or a lock. A monitor consists of data being synchronized,
+plus a lock, called the @dfn{monitor lock}, and one or more
+@dfn{condition variables}. Before it accesses the protected data, a
+thread first acquires the monitor lock. It is then said to be ``in the
+monitor''. While in the monitor, the thread has control over all the
+protected data, which it may freely examine or modify. When access to
+the protected data is complete, it releases the monitor lock.
+
+Condition variables allow code in the monitor to wait for a condition to
+become true. Each condition variable is associated with an abstract
+condition, e.g.@: ``some data has arrived for processing'' or ``over 10
+seconds has passed since the user's last keystroke''. When code in the
+monitor needs to wait for a condition to become true, it ``waits'' on
+the associated condition variable, 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.
+
+The theoretical framework for monitors was laid out by C.@: A.@: R.@:
+Hoare (@bibref{Hoare}). Their practical usage was later elaborated in a
+paper on the Mesa operating system (@bibref{Mesa}).
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.
+Represents a condition variable.
@end deftp
@deftypefun void cond_init (struct condition *@var{cond})
@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.
+
+Sending a signal and waking up from a wait are not an atomic operation.
+Thus, typically @func{cond_wait}'s caller must recheck the condition
+after the wait completes and, if necessary, wait again. See the next
+section for an example.
@end deftypefun
@deftypefun void cond_signal (struct condition *@var{cond}, struct lock *@var{lock})
@subsubsection 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,
+or more
+``producer'' threads write characters and out of which one or more
+``consumer'' threads read characters. To implement this we need,
besides the monitor lock, two condition variables which we will call
@var{not_full} and @var{not_empty}:
@node Memory Barriers
@subsection Memory Barriers
+@c We should try to come up with a better example.
+@c Perhaps something with a linked list?
+
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
For our purposes, we classify interrupts into two broad categories:
@itemize @bullet
+@item
+@dfn{Internal interrupts}, that is, interrupts caused directly by CPU
+instructions. System calls, attempts at invalid memory access
+(@dfn{page faults}), and attempts to divide by zero are some activities
+that cause internal interrupts. 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.
+
@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.
+synchronized with instruction execution. Handling of external interrupts
+can be postponed with @func{intr_disable} and related functions
+(@pxref{Disabling 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
+The CPU treats both classes of interrupts largely the same way,
+so Pintos has common infrastructure to handle both classes.
+The following section describes this
+common infrastructure. The sections after that give the specifics of
external and internal interrupts.
If you haven't already read chapter 3, ``Basic Execution Environment,''
@node Interrupt Infrastructure
@subsection 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
+When an interrupt occurs, the CPU saves
+its most essential state on a stack and jumps to an interrupt
+handler routine. The 80@var{x}86 architecture supports 256
+interrupts, numbered 0 through 255, each with an independent
+handler 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
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
+didn't already push 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
+The main job of @func{intr_handler} is to call the function
+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.
+panics.) It also does some extra processing for external
+interrupts (@pxref{External Interrupt Handling}).
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
+The following types and functions are common to all
interrupts.
@deftp {Type} {void intr_handler_func (struct intr_frame *@var{frame})}
@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
+The stack frame of an interrupt handler, as saved by the CPU, the interrupt
+stubs, and @func{intr_entry}. Its most interesting members are described
below.
@end deftp
@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}.
+Register values in the interrupted thread, pushed 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
@node Internal Interrupt Handling
@subsection 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.''
+Internal interrupts are caused directly by CPU instructions executed by
+the running kernel thread or user process (from project 2 onward). An
+internal interrupt is therefore said to arise in a ``process context.''
-In an internal interrupt, it can make sense to examine the
+In an internal interrupt's handler, 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.
+it. When the interrupt returns, modifications in @struct{intr_frame}
+become changes to the calling thread or process's state. For example,
+the Pintos system call handler returns a value to the user program by
+modifying the saved EAX register (@pxref{System Call Details}).
There are no special restrictions on what an internal interrupt
handler can or can't do. Generally they should run with interrupts
kernel threads. Thus, they do need to synchronize with other threads
on shared data and other resources (@pxref{Synchronization}).
+Internal interrupt handlers can be invoked recursively. For example,
+the system call handler might cause a page fault while attempting to
+read user memory. Deep recursion would risk overflowing the limited
+kernel stack (@pxref{struct thread}), but should be unnecessary.
+
@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{handler} 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).
+If @var{level} is @code{INTR_ON}, external interrupts will be processed
+normally during the interrupt handler's execution, which is normally
+desirable. Specifying @code{INTR_OFF} will cause the CPU to disable
+external interrupts when it invokes the interrupt handler. The effect
+is slightly different from calling @func{intr_disable} inside the
+handler, because that leaves a window of one or more CPU instructions in
+which external interrupts are still enabled. This is important for the
+page fault handler; refer to the comments in @file{userprog/exception.c}
+for details.
+
+@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 with an explicit INT instruction. The value of @var{dpl}
+doesn't affect user processes' ability to invoke the interrupt
+indirectly, e.g.@: an invalid memory reference will cause a page fault
+regardless of @var{dpl}.
@end deftypefun
@node External Interrupt Handling
projects / pintos-anon / blobdiff