Comment.

[pintos-anon] / doc / reference.texi

diff --git a/doc/reference.texi b/doc/reference.texi
index 3fe8b68a19d55c08901bef173bc144890450257b..463f728fcdc908ecd65f5f75d117645daee5955d 100644 (file)
--- a/doc/reference.texi
+++ b/doc/reference.texi
@@ -163,7 +163,7 @@ this, but calling it a second time is harmless.
 
 The next block of functions we call initialize the kernel's memory
 system.  @func{palloc_init} sets up the kernel page allocator, which
 
 The next block of functions we call initialize the kernel's memory
 system.  @func{palloc_init} sets up the kernel page allocator, which

-doles out memory one or more pages at a time (@xpref{Page Allocator}).
+doles out memory one or more pages at a time (@pxref{Page Allocator}).

 @func{malloc_init} sets
 up the allocator that handles allocations of arbitrary-size blocks of
 memory (@pxref{Block Allocator}).
 @func{malloc_init} sets
 up the allocator that handles allocations of arbitrary-size blocks of
 memory (@pxref{Block Allocator}).


@@ -230,27 +230,27 @@ grows downward from the end of the page.  It looks like this:
 
 @example
 @group
 
 @example
 @group

-        4 kB +---------------------------------+
-             |          kernel stack           |
-             |                |                |
-             |                |                |
-             |                V                |
-             |         grows downward          |
-             |                                 |
-             |                                 |
-             |                                 |
-             |                                 |
-             |                                 |
-             |                                 |
-             |                                 |
-             |                                 |
-             +---------------------------------+
-             |              magic              |
-             |                :                |
-             |                :                |
-             |              status             |
-             |               tid               |
-        0 kB +---------------------------------+
+                  4 kB +---------------------------------+
+                       |          kernel stack           |
+                       |                |                |
+                       |                |                |
+                       |                V                |
+                       |         grows downward          |
+                       |                                 |
+                       |                                 |
+                       |                                 |
+                       |                                 |
+                       |                                 |
+                       |                                 |
+                       |                                 |
+                       |                                 |
+sizeof (struct thread) +---------------------------------+
+                       |              magic              |
+                       |                :                |
+                       |                :                |
+                       |              status             |
+                       |               tid               |
+                  0 kB +---------------------------------+

 @end group
 @end example
 
 @end group
 @end example
 


@@ -276,6 +276,7 @@ if you like.
 @end deftypecv
 
 @deftypecv {Member} {@struct{thread}} {enum thread_status} status
 @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}
 The thread's state, one of the following:
 
 @defvr {Thread State} @code{THREAD_RUNNING}


@@ -294,7 +295,12 @@ invoked.  Ready threads are kept in a doubly linked list called
 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
 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}.
+call to @func{thread_unblock}.  This is most conveniently done
+indirectly, using one of the Pintos synchronization primitives that
+block and unblock threads automatically (@pxref{Synchronization}).
+
+There is no @i{a priori} way to tell what a blocked thread is waiting
+for, but a backtrace can help (@pxref{Backtraces}).

 @end defvr
 
 @defvr {Thread State} @code{THREAD_DYING}
 @end defvr
 
 @defvr {Thread State} @code{THREAD_DYING}


@@ -332,23 +338,24 @@ priority scheduling in project 1 (@pxref{Priority Scheduling}).
 
 @deftypecv {Member} {@struct{thread}} {@struct{list_elem}} elem
 A ``list element'' used to put the thread into doubly linked lists,
 
 @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.
+either @code{ready_list} (the list of threads ready to run) or a list of
+threads waiting on a semaphore in @func{sema_down}.  It can do double
+duty because a thread waiting on a semaphore is not ready, and vice
+versa.

 @end deftypecv
 
 @deftypecv {Member} {@struct{thread}} {uint32_t *} pagedir
 @end deftypecv
 
 @deftypecv {Member} {@struct{thread}} {uint32_t *} pagedir

-Only present in project 2 and later.
+Only present in project 2 and later.  @xref{Page Tables}.

 @end deftypecv
 
 @deftypecv {Member} {@struct{thread}} {unsigned} magic
 @end deftypecv
 
 @deftypecv {Member} {@struct{thread}} {unsigned} magic

-Always set to @code{THREAD_MAGIC}, which is just a random number defined
+Always set to @code{THREAD_MAGIC}, which is just an arbitrary 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
 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.
+tends to change this value, triggering the assertion.  For greatest
+benefit, as you add members to @struct{thread}, leave @code{magic} at
+the end.

 @end deftypecv
 
 @node Thread Functions
 @end deftypecv
 
 @node Thread Functions


@@ -396,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
 
 @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})}
 
 @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 deftp

+@end deftypefun

 
 @deftypefun void thread_block (void)
 Transitions the running thread from the running state to the blocked
 
 @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}).
 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}).


@@ -417,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
 
 @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
 
 the thread is waiting on becomes available.
 @end deftypefun
 


@@ -450,20 +459,20 @@ time.
 
 @deftypefun int thread_get_priority (void)
 @deftypefunx void thread_set_priority (int @var{new_priority})
 
 @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)
 @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
 
 @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}.
 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}.


@@ -471,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.
 
 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
 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


@@ -486,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.
 
 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
 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


@@ -494,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
 
 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
 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


@@ -531,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,
 @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.
 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.


@@ -540,7 +549,7 @@ synchronization primitives to help out.
 * Disabling Interrupts::        
 * Semaphores::                  
 * Locks::                       
 * Disabling Interrupts::        
 * Semaphores::                  
 * Locks::                       

-* Condition Variables::         
+* Monitors::                    

 * Memory Barriers::             
 @end menu
 
 * Memory Barriers::             
 @end menu
 


@@ -598,12 +607,8 @@ Turns interrupts off.  Returns the previous interrupt state.
 @node Semaphores
 @subsection Semaphores
 
 @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
 
 @itemize @bullet
 @item


@@ -632,6 +637,15 @@ more appropriate.
 
 Semaphores can also be initialized to values larger than 1.  These are
 rarely used.
 
 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})
 @end deftp
 
 @deftypefun void sema_init (struct semaphore *@var{sema}, unsigned @var{value})


@@ -646,17 +660,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},
 
 @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.
 @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
 @end deftypefun
 
 Semaphores are internally built out of disabling interrupt


@@ -668,29 +687,31 @@ implementation in @file{lib/kernel/list.c}.
 @node Locks
 @subsection Locks
 
 @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.
 
 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.
 @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})
 @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
 
 any current owner to release it if necessary.
 @end deftypefun
 


@@ -698,7 +719,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
 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})
 @end deftypefun
 
 @deftypefun void lock_release (struct lock *@var{lock})


@@ -708,37 +729,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.
 @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}
 
 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})
 @end deftp
 
 @deftypefun void cond_init (struct condition *@var{cond})


@@ -750,6 +775,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.
 @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})
 @end deftypefun
 
 @deftypefun void cond_signal (struct condition *@var{cond}, struct lock *@var{lock})


@@ -768,8 +798,9 @@ function.
 @subsubsection Monitor Example
 
 The classical example of a monitor is handling a buffer into which one
 @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}:
 
 besides the monitor lock, two condition variables which we will call
 @var{not_full} and @var{not_empty}:
 


@@ -809,6 +840,9 @@ char get (void) @{
 @node Memory Barriers
 @subsection Memory Barriers
 
 @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
 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