@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
@subsection 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.
+External interrupts are caused by events outside the CPU.
They are asynchronous, so they can be invoked at any time that
interrupts have not been disabled. We say that an external interrupt
runs in an ``interrupt context.''
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 slept, it would effectively put that
-thread to sleep too until the interrupt handler resumed control and
-returned.
-
-Because an external interrupt runs with interrupts disabled, it
+Only one external interrupt may be processed at a time. Neither
+internal nor external interrupt may nest within an external interrupt
+handler. Thus, an external interrupt's handler must run with interrupts
+disabled (@pxref{Disabling Interrupts}).
+
+An external interrupt handler must not sleep or yield, which rules out
+calling @func{lock_acquire}, @func{thread_yield}, and many other
+functions. Sleeping in interrupt context would effectively put the
+interrupted thread to sleep, too, until the interrupt handler was again
+scheduled and returned. This would be unfair to the unlucky thread, and
+it would deadlock if the handler were waiting for the sleeping thread
+to, e.g., release a lock.
+
+An external interrupt handler
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.
+they can. Anything that require much CPU time should instead run in a
+kernel thread, possibly one that the interrupt triggers using a
+synchronization primitive.
-External interrupts are also special because they are controlled by a
+External interrupts 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.
+@func{pic_end_of_interrupt}, which properly signals the PICs.
-The following additional functions are related to external
+The following functions relate to external
interrupts.
@deftypefun void intr_register_ext (uint8_t @var{vec}, intr_handler_func *@var{handler}, const char *@var{name})
@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
+false. Mainly used in functions that might sleep
or that otherwise should not be called from interrupt context, in this
form:
@example
@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.
+called just before the interrupt returns. Used
+in the timer interrupt handler when a thread's time slice expires, to
+cause a new thread to be scheduled.
@end deftypefun
@node Memory Allocation
projects / pintos-anon / blobdiff