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}).
@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 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 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}
@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
-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
-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
-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
@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
@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
projects / pintos-anon / blobdiff