X-Git-Url: https://pintos-os.org/cgi-bin/gitweb.cgi?a=blobdiff_plain;f=doc%2Freference.texi;h=d9ceb292f593d1be8c5087bb0163c59fc63c35d0;hb=c10f76f48723b2af78d774d11149032655f1a05c;hp=6a59745583e96e4689d5d0e0018facd465027853;hpb=97b529a42b33117350c5323477739c2493043e5a;p=pintos-anon diff --git a/doc/reference.texi b/doc/reference.texi index 6a59745..d9ceb29 100644 --- a/doc/reference.texi +++ b/doc/reference.texi @@ -276,6 +276,7 @@ if you like. @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} @@ -402,20 +403,21 @@ Creates and starts a new thread named @var{name} with the given @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}). @@ -423,8 +425,9 @@ 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 @@ -456,20 +459,20 @@ time. @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}. @@ -477,7 +480,7 @@ 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. -@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 @@ -492,7 +495,7 @@ 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 +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 @@ -500,7 +503,7 @@ 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 +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 @@ -537,7 +540,7 @@ interrupts and calls the thread's function (the function passed to @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. @@ -546,7 +549,7 @@ synchronization primitives to help out. * Disabling Interrupts:: * Semaphores:: * Locks:: -* Condition Variables:: +* Monitors:: * Memory Barriers:: @end menu @@ -576,6 +579,11 @@ 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}). +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}. @@ -604,12 +612,8 @@ Turns interrupts off. Returns the previous interrupt state. @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 @@ -638,6 +642,15 @@ more appropriate. 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}) @@ -652,17 +665,22 @@ its value to become positive and then decrementing it by one. @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 @@ -674,29 +692,31 @@ implementation in @file{lib/kernel/list.c}. @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 @@ -704,7 +724,7 @@ any current owner to release it if necessary. 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}) @@ -714,37 +734,41 @@ Releases @var{lock}, which the current thread must own. @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}) @@ -756,6 +780,11 @@ 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. + +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}) @@ -774,8 +803,9 @@ function. @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}: @@ -815,6 +845,9 @@ char get (void) @{ @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 @@ -911,30 +944,29 @@ 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{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,'' @@ -951,11 +983,11 @@ also want to skim chapter 5, ``Interrupt and Exception Handling,'' in @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 @@ -966,20 +998,20 @@ 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 +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})} @@ -989,8 +1021,8 @@ 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 +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 @@ -1004,7 +1036,7 @@ below. @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 @@ -1035,17 +1067,16 @@ Returns the name of the interrupt numbered @var{vec}, or @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 @@ -1053,21 +1084,33 @@ 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}). +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