rarely used.
Semaphores were invented by Edsger Dijkstra and first used in the THE
-operating system (@bibref{THE}).
+operating system (@bibref{Dijkstra}).
Pintos' semaphore type and operations are declared in
@file{threads/synch.h}.
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}).
+paper on the Mesa operating system (@bibref{Lampson}).
Condition variable types and functions are declared in
@file{threads/synch.h}.
@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
The page allocator divides the memory it allocates into two pools,
called the kernel and user pools. By default, each pool gets half of
-system memory, but this can be changed with a kernel command line
+system memory, but this can be changed with the @option{-ul} kernel
+command line
option (@pxref{Why PAL_USER?}). An allocation request draws from one
pool or the other. If one pool becomes empty, the other may still
have free pages. The user pool should be used for allocating memory
for @var{n} consecutive bits set to
false, indicating that those pages are free, and then sets those bits
to true to mark them as used. This is a ``first fit'' allocation
-strategy.
+strategy (@pxref{Wilson}).
The page allocator is subject to fragmentation. That is, it may not
be possible to allocate @var{n} contiguous pages even though @var{n}
or more pages are free, because the free pages are separated by used
pages. In fact, in pathological cases it may be impossible to
-allocate 2 contiguous pages even though @var{n} / 2 pages are free!
+allocate 2 contiguous pages even though half of the pool's pages are free.
Single-page requests can't fail due to fragmentation, so
-it is best to limit, as much as possible, the need for multiple
-contiguous pages.
+requests for multiple contiguous pages should be limited as much as
+possible.
Pages may not be allocated from interrupt context, but they may be
freed.
Page allocator types and functions are described below.
-@deftp {Type} {enum palloc_flags}
-A set of flags that describe how to allocate pages. These flags may
-be combined in any combination.
-@end deftp
+@deftypefun {void *} palloc_get_page (enum palloc_flags @var{flags})
+@deftypefunx {void *} palloc_get_multiple (enum palloc_flags @var{flags}, size_t @var{page_cnt})
+Obtains and returns one page, or @var{page_cnt} contiguous pages,
+respectively. Returns a null pointer if the pages cannot be allocated.
+
+The @var{flags} argument may be any combination of the following flags:
@defvr {Page Allocator Flag} @code{PAL_ASSERT}
If the pages cannot be allocated, panic the kernel. This is only
Obtain the pages from the user pool. If not set, pages are allocated
from the kernel pool.
@end defvr
-
-@deftypefun {void *} palloc_get_page (enum palloc_flags @var{flags})
-Obtains and returns a single page, allocating it in the manner specified by
-@var{flags}. Returns a null pointer if no pages are
-free.
-@end deftypefun
-
-@deftypefun {void *} palloc_get_multiple (enum palloc_flags @var{flags}, size_t @var{page_cnt})
-Obtains @var{page_cnt} contiguous free pages, allocating them in the
-manner specified by @var{flags}, and returns them. Returns a null
-pointer if no pages are free.
@end deftypefun
@deftypefun void palloc_free_page (void *@var{page})
-Frees @var{page}, which must have been obtained using
+@deftypefunx void palloc_free_multiple (void *@var{pages}, size_t @var{page_cnt})
+Frees one page, or @var{page_cnt} contiguous pages, respectively,
+starting at @var{pages}. All of the pages must have been obtained using
@func{palloc_get_page} or @func{palloc_get_multiple}.
@end deftypefun
-@deftypefun void palloc_free_multiple (void *@var{pages}, size_t @var{page_cnt})
-Frees the @var{page_cnt} contiguous pages starting at @var{pages}.
-All of the pages must have been obtained using @func{palloc_get_page}
-or @func{palloc_get_multiple}.
-@end deftypefun
-
@node Block Allocator
@subsection Block Allocator
described in the previous section. Blocks returned by the block
allocator are obtained from the kernel pool.
-The block allocator uses two different strategies for allocating
-memory. The first of these applies to ``small'' blocks, those 1 kB or
-smaller (one
-fourth of the page size). These allocations are rounded up to the
+The block allocator uses two different strategies for allocating memory.
+The first strategy applies to blocks that are 1 kB or smaller
+(one-fourth of the page size). These allocations are rounded up to the
nearest power of 2, or 16 bytes, whichever is larger. Then they are
-grouped into a page used only for allocations of the smae
-size.
+grouped into a page used only for allocations of that size.
-The second strategy applies to allocating ``large'' blocks, those larger
-than 1 kB.
+The second strategy applies to blocks larger than 1 kB.
These allocations (plus a small amount of overhead) are rounded up to
the nearest page in size, and then the block allocator requests that
number of contiguous pages from the page allocator.
unimportant in an instructional system like Pintos.
As long as a page can be obtained from the page allocator, small
-allocations always succeed. Most small allocations will not require a
-new page from the page allocator at all. However, large allocations
+allocations always succeed. Most small allocations do not require a
+new page from the page allocator at all, because they are satisfied
+using part of a page already allocated. However, large allocations
always require calling into the page allocator, and any allocation
that needs more than one contiguous page can fail due to fragmentation,
as already discussed in the previous section. Thus, you should
minimize the number of large allocations in your code, especially
those over approximately 4 kB each.
-The interface to the block allocator is through the standard C library
-functions @func{malloc}, @func{calloc}, and @func{free}.
-
When a block is freed, all of its bytes are cleared to @t{0xcc}, as
a debugging aid (@pxref{Debugging Tips}).
The block allocator may not be called from interrupt context.
+The block allocator functions are described below. Their interfaces are
+the same as the standard C library functions of the same names.
+
+@deftypefun {void *} malloc (size_t @var{size})
+Obtains and returns a new block, from the kernel pool, at least
+@var{size} bytes long. Returns a null pointer if @var{size} is zero or
+if memory is not available.
+@end deftypefun
+
+@deftypefun {void *} calloc (size_t @var{a}, size_t @var{b})
+Obtains a returns a new block, from the kernel pool, at least
+@code{@var{a} * @var{b}} bytes long. The block's contents will be
+cleared to zeros. Returns a null pointer if @var{a} or @var{b} is zero
+or if insufficient memory is available.
+@end deftypefun
+
+@deftypefun {void *} realloc (void *@var{block}, size_t @var{new_size})
+Attempts to resize @var{block} to @var{new_size} bytes, possibly moving
+it in the process. If successful, returns the new block, in which case
+the old block must no longer be accessed. On failure, returns a null
+pointer, and the old block remains valid.
+
+A call with @var{block} null is equivalent to @func{malloc}. A call
+with @var{new_size} zero is equivalent to @func{free}.
+@end deftypefun
+
+@deftypefun void free (void *@var{block})
+Frees @var{block}, which must have been previously returned by
+@func{malloc}, @func{calloc}, or @func{realloc} (and not yet freed).
+@end deftypefun
+
@node Virtual Addresses
@section Virtual Addresses
projects / pintos-anon / blobdiff