practically speaking, the loader has to be written in assembly
language.
-Pintos' loader first initializes the CPU. The first important part of
+The Pintos loader first initializes the CPU. The first important part of
this is to enable the A20 line, that is, the CPU's address line
-numbered 20. For historical reasons, PCs start out with this address
+numbered 20. For historical reasons, PCs boot with this address
line fixed at 0, which means that attempts to access memory beyond the
first 1 MB (2 raised to the 20th power) will fail. Pintos wants to
access more memory than this, so we have to enable it.
After the page table is initialized, we load the CPU's control
registers to turn on protected mode and paging, and then we set up the
-segment registers. We aren't equipped to handle interrupts in
-protected mode yet, so we disable interrupts.
+segment registers. We aren't yet equipped to handle interrupts in
+protected mode, so we disable interrupts.
Finally it's time to load the kernel from disk. We use a simple but
inflexible method to do this: we program the IDE disk
Then we jump to the start of the compiled kernel image. Using the
``linker script'' in @file{threads/kernel.lds.S}, the kernel has
-arranged that it begins with the assembly module
+arranged to begin with the assembly module
@file{threads/start.S}. This assembly module just calls
@func{main}, which never returns.
There's one more trick: the Pintos kernel command line
-is stored in the boot loader. The @command{pintos} program actually
-modifies the boot loader on disk each time it runs the kernel, putting
+is in stored the boot loader. The @command{pintos} program actually
+modifies a copy of the boot loader on disk each time it runs the kernel,
+putting
in whatever command line arguments the user supplies to the kernel,
and then the kernel at boot time reads those arguments out of the boot
-loader in memory. This is something of a nasty hack, but it is simple
+loader in memory. This is not an elegant solution, but it is simple
and effective.
@node Kernel Initialization
encounter in Pintos from here on out.
When @func{main} starts, the system is in a pretty raw state. We're
-in protected mode with paging enabled, but hardly anything else is
+in 32-bit protected mode with paging enabled, but hardly anything else is
ready. Thus, the @func{main} function consists primarily of calls
into other Pintos modules' initialization functions.
These are usually named @func{@var{module}_init}, where
just afterward, tries to use locks, and locks in turn require there to be a
running thread.
-Then we initialize the console so that we can use @func{printf}.
+Then we initialize the console so that @func{printf} will work.
@func{main} calls @func{vga_init}, which initializes the VGA text
display and clears the screen. It also calls @func{serial_init_poll}
to initialize the first serial port in ``polling mode,'' that is,
where the kernel busy-waits for the port to be ready for each
-character to be output. (We use polling mode until we're ready to set
-up interrupts later.) Finally we initialize the console device and
+character to be output. (We use polling mode until we're ready to enable
+interrupts, later.) Finally we initialize the console device and
print a startup message to the console.
@func{main} calls @func{read_command_line} to break the kernel command
line into arguments, then @func{parse_options} to read any options at
-the beginning of the command line. (Executing actions specified on the
-command line happens later.)
+the beginning of the command line. (Actions specified on the
+command line execute later.)
+
+@func{main} calls @func{random_init} to initialize the kernel random
+number generator. If the user specified @option{-rs} on the
+@command{pintos} command line, @func{parse_options} already did
+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
-doles out memory one or more pages at a time. @func{malloc_init} sets
-up the allocator that handles odd-sized allocations.
-@func{paging_init} sets up a page table for the kernel.
+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{paging_init} sets up a page table for the kernel (@pxref{Page
+Table}).
In projects 2 and later, @func{main} also calls @func{tss_init} and
-@func{gdt_init}, but we'll talk about those later.
-
-@func{main} calls @func{random_init} to initialize the kernel random
-number generator. If the user specified @option{-rs} on the
-@command{pintos} command line, @func{parse_options} has already done
-this, but calling it a second time is harmless and has no effect.
+@func{gdt_init}.
-We initialize the interrupt system in the next set of calls.
+The next set of calls initializes the interrupt system.
@func{intr_init} sets up the CPU's @dfn{interrupt descriptor table}
(IDT) to ready it for interrupt handling (@pxref{Interrupt
Infrastructure}), then @func{timer_init} and @func{kbd_init} prepare for
projects 2 and later, we also prepare to handle interrupts caused by
user programs using @func{exception_init} and @func{syscall_init}.
-Now that interrupts are set up, we can start preemptively scheduling
-threads with @func{thread_start}, which also enables interrupts.
+Now that interrupts are set up, we can start the scheduler
+with @func{thread_start}, which creates the idle thread and enables
+interrupts.
With interrupts enabled, interrupt-driven serial port I/O becomes
possible, so we use
@func{serial_init_queue} to switch to that mode. Finally,
@func{timer_calibrate} calibrates the timer for accurate short delays.
If the file system is compiled in, as it will starting in project 2, we
-now initialize the disks with @func{disk_init}, then the
+initialize the disks with @func{disk_init}, then the
file system with @func{filesys_init}.
Boot is complete, so we print a message.
@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}:
You do not need to understand the PTE format to do the Pintos
projects, unless you wish to incorporate the page table into your
-segment table (@pxref{Managing the Segment Table}).
+supplemental page table (@pxref{Managing the Supplemental Page Table}).
The actual format of a page table entry is summarized below. For
complete information, refer to section 3.7, ``Page Translation Using
projects / pintos-anon / blobdiff