-TEXIS = projects.texi intro.texi threads.texi mlfqs.texi userprog.texi \
-vm.texi filesys.texi references.texi standards.texi doc.texi devel.texi \
-debug.texi
+TEXIS = projects.texi intro.texi tour.texi threads.texi mlfqs.texi \
+userprog.texi vm.texi filesys.texi references.texi standards.texi \
+doc.texi devel.texi debug.texi
all: projects.html projects.info
-@node Debugging Tools, , Project Documentation, Top
+@node Debugging Tools, Development Tools, Project Documentation, Top
@appendix Debugging Tools
Many tools lie at your disposal for debugging Pintos. This appendix
@end menu
@node printf
-@section @code{printf()}
+@section @func{printf}
-Don't underestimate the value of @code{printf()}. The way
-@code{printf()} is implemented in Pintos, you can call it from
+Don't underestimate the value of @func{printf}. The way
+@func{printf} is implemented in Pintos, you can call it from
practically anywhere in the kernel, whether it's in a kernel thread or
an interrupt handler, almost regardless of what locks are held.
-@code{printf()} isn't useful just because it can print data members.
+@func{printf} isn't useful just because it can print data members.
It can also help figure out when and where something goes wrong, even
when the kernel crashes or panics without a useful error message. The
-strategy is to sprinkle calls to @code{print()} with different strings
+strategy is to sprinkle calls to @func{print} with different strings
(e.g.@: @code{"1\n"}, @code{"2\n"}, @dots{}) throughout the pieces of
code you suspect are failing. If you don't even see @code{1} printed,
then something bad happened before that point, if you see @code{1}
but not @code{2}, then something bad happened between those two
points, and so on. Based on what you learn, you can then insert more
-@code{printf()} calls in the new, smaller region of code you suspect.
+@func{printf} calls in the new, smaller region of code you suspect.
Eventually you can narrow the problem down to a single statement.
@node ASSERT
@section @code{DEBUG}
The @code{DEBUG} macro, also defined in @code{<debug.h>}, is a sort of
-conditional @code{printf()}. It takes as its arguments the name of a
-``message class'' and a @code{printf()}-like format string and
+conditional @func{printf}. It takes as its arguments the name of a
+``message class'' and a @func{printf}-like format string and
arguments. The message class is used to filter the messages that are
actually displayed. You select the messages to display on the Pintos
command line using the @option{-d} option. This allows you to easily
When the kernel panics, it prints a ``backtrace,'' that is, a summary
of how your program got where it is, as a list of addresses inside the
functions that were running at the time of the panic. You can also
-insert a call to @code{debug_backtrace()}, prototyped in
+insert a call to @func{debug_backtrace}, prototyped in
@file{<debug.h>}, at any point in your code.
The addresses in a backtrace are listed as raw hexadecimal numbers,
control, load Pintos, and then Pintos will run in the usual way. You
can pause the process at any point with @key{Ctrl+C}. If you want
@command{gdb} to stop when Pintos starts running, set a breakpoint on
-@code{main()} with the command @code{break main} before @samp{c}.
+@func{main} with the command @code{break main} before @samp{c}.
You can read the @command{gdb} manual by typing @code{info gdb} at a
terminal command prompt, or you can view it in Emacs with the command
Of course, to get any good out of this you'll have to actually modify
Bochs. Instructions for doing this are firmly out of the scope of
this document. However, if you want to debug page faults as suggested
-above, a good place to start adding @code{printf()}s is
-@code{BX_CPU_C::dtranslate_linear()} in @file{cpu/paging.cc}.
+above, a good place to start adding @func{printf}s is
+@func{BX_CPU_C::dtranslate_linear} in @file{cpu/paging.cc}.
@node Debugging Tips
@section Tips
the bytes in freed blocks to @t{0xcd}. The two bytes @t{0xcdcd} are
a CPU opcode for ``invoke interrupt @t{0xcd},'' so @code{Interrupt
0xcd (unknown)} is a good sign that you tried to execute code in a
-block freed with @code{free()}.
+block freed with @func{free}.
-@node Development Tools
+@node Development Tools, , Debugging Tools, Top
@appendix Development Tools
Here are some tools that you might find useful while developing code.
+@menu
+* Tags::
+* CVS::
+* VNC::
+@end menu
+
@node Tags
@section Tags
@menu
* README::
-* DESIGNDOC ::
-* TESTCASE ::
+* DESIGNDOC::
+* TESTCASE::
@end menu
@node README
If you added extra credit features to your project, explain them
concisely in the @file{README}. Otherwise, we're likely to miss them.
-@node DESIGNDOC
+@node DESIGNDOC
@section @file{DESIGNDOC}
This file is our primary tool for assessing your design. Therefore,
without sacrificing key design decisions. You should be brief, yet
complete. We don't want to read novels.
-@node TESTCASE
+@node TESTCASE
@section @file{TESTCASE}
The @file{TESTCASE} file should contain all the information about how
Clearly state in your @file{TESTCASE} file what each test is supposed
to test. You should be testing not only the common case, but testing
corner cases. Specify what criteria or issue is being tested. For
-example, in testing @code{thread_join()} you would have specified that
-you test @code{thread_join()} when it is called multiple times on the
+example, in testing @func{thread_join} you would have specified that
+you test @func{thread_join} when it is called multiple times on the
same child thread.
@item
Make your tests as succinct as possible. Most students in the past
-have done a great job with the testing of @code{thread_join()},
+have done a great job with the testing of @func{thread_join},
creating very succinct short tests. We like that.
@item
Note that write-behind makes your filesystem more fragile in the face
of crashes. Therefore, you should implement some manner to
periodically write all cached blocks to disk. If you have
-@code{timer_sleep()} from the first project working, this is an
+@func{timer_sleep} from the first project working, this is an
excellent application for it.
Likewise, read-ahead is only really useful when done asynchronously.
Yes. Implementing @file{.} and @file{..} is extra credit, though.
@item
-@b{Should @code{remove()} also be able to remove directories?}
+@b{Should @func{remove} also be able to remove directories?}
Yes. The @code{remove} system call should handle removal of both
regular files and directories. You may assume that directories can
to read a @code{struct inode}, you'll have to get it either from the
buffer cache or from disk.
-If you look at @code{file_read_at()}, it uses the inode directly
+If you look at @func{file_read_at}, it uses the inode directly
without having first read in that sector from wherever it was in the
storage hierarchy. You are no longer allowed to do this. You will
need to change @code{file_read_at} (and similar functions) so that it
-@node Introduction, Project 1--Threads, Top, Top
+@node Introduction, Pintos Tour, Top, Top
@chapter Introduction
Welcome to Pintos. Pintos is a simple operating system framework for
@end macro
@end ifhtml
+@macro func{name}
+@code{\name\()}
+@end macro
+
+@macro struct{name}
+@code{struct \name\}
+@end macro
+
@titlepage
@title Pintos Projects
@end titlepage
@menu
* Introduction::
+* Pintos Tour::
* Project 1--Threads::
* Project 2--User Programs::
* Project 3--Virtual Memory::
* Coding Standards::
* Project Documentation::
* Debugging Tools::
+* Development Tools::
@end menu
@include intro.texi
+@include tour.texi
@include threads.texi
@include userprog.texi
@include vm.texi
@include standards.texi
@include doc.texi
@include debug.texi
+@include devel.texi
@bye
@itemize @bullet
@item
-Problem 1-2, @code{thread_join()}. Some other code expects
+Problem 1-2, @func{thread_join}. Some other code expects
@code{THREAD_JOIN_IMPLEMENTED} to be defined once you've implemented
this function.
@item <inttypes.h>
@file{<stdint.h>} is useful on its own, but it provides no way to pass
-the types it defines to @code{printf()} and related functions. This
+the types it defines to @func{printf} and related functions. This
header provides macros to help with that. For every
@code{int@var{n}_t} defined by @file{<stdint.h>}, it provides macros
@code{PRId@var{n}} and @code{PRIi@var{n}} for formatting values of
widths, etc.
@item <stdio.h>
-The @file{printf()} function has some new type modifiers for printing
+The @func{printf} function has some new type modifiers for printing
standard types:
@table @samp
@item t
For @code{ptrdiff_t} (e.g.@: @samp{%td}).
@end table
+
+Pintos @func{printf} also implements a nonstandard @samp{'} flag that
+group large numbers with commas to make them easier to read.
@end table
@node Unsafe String Functions
The worst offenders are intentionally not included in the Pintos C
library:
-@table @code
-@item strcpy()
+@table @func
+@item strcpy
When used carelessly this function can overflow the buffer reserved
-for its output string. Use @code{strlcpy()} instead. Refer to
+for its output string. Use @func{strlcpy} instead. Refer to
comments in its source code in @code{lib/string.c} for documentation.
-@item strncpy()
+@item strncpy
This function can leave its destination buffer without a null string
terminator and it has performance problems besides. Again, use
-@code{strlcpy()}.
+@func{strlcpy}.
-@item strcat()
-Same issue as @code{strcpy()}, but substitute @code{strlcat()}.
+@item strcat
+Same issue as @func{strcpy}, but substitute @func{strlcat}.
Again, refer to comments in its source code in @code{lib/string.c} for
documentation.
-@item strncat()
+@item strncat
The meaning of its buffer size argument often leads to problems.
-Again, use @code{strlcat()}.
+Again, use @func{strlcat}.
-@item strtok()
+@item strtok
Uses global data, so it is unsafe in threaded programs such as
-kernels. Use @code{strtok_r()} instead, and see its source code in
+kernels. Use @func{strtok_r} instead, and see its source code in
@code{lib/string.c} for documentation and an example.
-@item sprintf()
-Same issue as @code{strcpy()}. Use @code{snprintf()} instead. Refer
+@item sprintf
+Same issue as @func{strcpy}. Use @func{snprintf} instead. Refer
to comments in @code{lib/stdio.h} for documentation.
-@item vsprintf()
-Same issue as @code{strcpy()}. Use @code{vsnprintf()} instead.
+@item vsprintf
+Same issue as @func{strcpy}. Use @func{vsnprintf} instead.
@end table
If you try to use any of these functions, you should get a hint from
-@node Project 1--Threads, Project 2--User Programs, Introduction, Top
+@node Project 1--Threads, Project 2--User Programs, Pintos Tour, Top
@chapter Project 1: Threads
In this assignment, we give you a minimally functional thread system.
this assignment, with some work in the @file{devices} directory on the
side. Compilation should be done in the @file{threads} directory.
+Before you read the description of this project, you should read all
+of the following sections: @ref{Introduction}, @ref{Threads Tour},
+@ref{Coding Standards}, @ref{Project Documentation}, @ref{Debugging
+Tools}, and @ref{Development Tools}. To complete this project you
+will also need to read @ref{Multilevel Feedback Scheduling}.
+
@menu
* Understanding Threads::
* Project 1 Code::
you haven't already compiled and run the base system, as described in
the introduction (@pxref{Introduction}), you should do so now. You
can read through parts of the source code by hand to see what's going
-on. If you like, you can add calls to @code{printf()} almost
+on. If you like, you can add calls to @func{printf} almost
anywhere, then recompile and run to see what happens and in what
order. You can also run the kernel in a debugger and set breakpoints
at interesting spots, single-step through code and examine data, and
When a thread is created, you are creating a new context to be
scheduled. You provide a function to be run in this context as an
-argument to @code{thread_create()}. The first time the thread is
+argument to @func{thread_create}. The first time the thread is
scheduled and runs, it will start from the beginning of that function
and execute it in the context. When that function returns, that thread
completes. Each thread, therefore, acts like a mini-program running
-inside Pintos, with the function passed to @code{thread_create()}
-acting like @code{main()}.
+inside Pintos, with the function passed to @func{thread_create}
+acting like @func{main}.
At any given time, Pintos is running exactly one thread, with the
others switched out. The scheduler decides which thread to run next
Using the @command{gdb} debugger, slowly trace through a context
switch to see what happens (@pxref{i386-elf-gdb}). You can set a
-breakpoint on the @code{schedule()} function to start out, and then
+breakpoint on the @func{schedule} function to start out, and then
single-step from there. Be sure to keep track of each thread's
address and state, and what procedures are on the call stack for each
thread. You will notice that when one thread calls
-@code{switch_threads()}, another thread starts running, and the first
+@func{switch_threads}, another thread starts running, and the first
thing the new thread does is to return from
-@code{switch_threads()}. We realize this comment will seem cryptic to
+@func{switch_threads}. We realize this comment will seem cryptic to
you at this point, but you will understand threads once you understand
-why the @code{switch_threads()} that gets called is different from the
-@code{switch_threads()} that returns.
+why the @func{switch_threads} that gets called is different from the
+@func{switch_threads} that returns.
@strong{Warning}: In Pintos, each thread is assigned a small,
fixed-size execution stack just under @w{4 kB} in size. The kernel
e.g. @samp{int buf[1000];}. Alternatives to stack allocation include
the page allocator in @file{threads/palloc.c} and the block allocator
in @file{threads/malloc.c}. Note that the page allocator doles out
-@w{4 kB} chunks and that @code{malloc()} has a @w{2 kB} block size
+@w{4 kB} chunks and that @func{malloc} has a @w{2 kB} block size
limit. If you need larger chunks, consider using a linked structure
instead.
or modify it, but it's here in case you're curious.
@item start.S
-Jumps to @code{main()}.
+Jumps to @func{main}.
@item init.c
@itemx init.h
-Kernel initialization, including @code{main()}, the kernel's ``main
-program.'' You should look over @code{main()} at least to see what
+Kernel initialization, including @func{main}, the kernel's ``main
+program.'' You should look over @func{main} at least to see what
gets initialized.
@item thread.c
@item malloc.c
@itemx malloc.h
-A very simple implementation of @code{malloc()} and @code{free()} for
+A very simple implementation of @func{malloc} and @func{free} for
the kernel.
@item interrupt.c
@item vga.c
@itemx vga.h
VGA display driver. Responsible for writing text to the screen.
-You should have no need to look at this code. @code{printf()} will
+You should have no need to look at this code. @func{printf} will
call into the VGA display driver for you, so there's little reason to
call this code yourself.
@item serial.c
@itemx serial.h
-Serial port driver. Again, @code{printf()} calls this code for you,
+Serial port driver. Again, @func{printf} calls this code for you,
so you don't need to do so yourself. Feel free to look through it if
you're curious.
@item kernel/console.c
@itemx kernel/console.h
-Implements @code{printf()} and a few other functions.
+Implements @func{printf} and a few other functions.
@end table
@node Debugging versus Testing
There should be no busy-waiting in any of your solutions to this
assignment. Furthermore, resist the temptation to directly disable
-interrupts in your solution by calling @code{intr_disable()} or
-@code{intr_set_level()}, although you may find doing so to be useful
+interrupts in your solution by calling @func{intr_disable} or
+@func{intr_set_level}, although you may find doing so to be useful
while debugging. Instead, use semaphores, locks and condition
variables to solve synchronization problems. Hint: read the comments
in @file{threads/synch.h} if you're unsure what synchronization
code for the whole quarter. Problem 1-1 (Alarm Clock) could be very
handy, but not strictly required in the future. The upshot of all
this is that you should focus heavily on making sure that your
-implementation of @code{thread_join()} works correctly, since if it's
+implementation of @func{thread_join} works correctly, since if it's
broken, you will need to fix it for future assignments. The other
parts can be turned off in the future if you find you can't make them
work quite right.
@section Problem 1-1: Alarm Clock
Improve the implementation of the timer device defined in
-@file{devices/timer.c} by reimplementing @code{timer_sleep()}.
+@file{devices/timer.c} by reimplementing @func{timer_sleep}.
Threads call @code{timer_sleep(@var{x})} to suspend execution until
time has advanced by at least @w{@var{x} timer ticks}. This is
useful for threads that operate in real-time, for example, for
could potentially be used more profitably by another thread. Your
solution should not busy wait.
-The argument to @code{timer_sleep()} is expressed in timer ticks, not
-in milliseconds or some other unit.
+The argument to @func{timer_sleep} is expressed in timer ticks, not
+in milliseconds or another unit. There are @code{TIMER_FREQ} timer
+ticks per second, where @code{TIMER_FREQ} is a macro defined in
+@code{devices/timer.h}.
@node Problem 1-2 Join
@section Problem 1-2: Join
is already a prototype for it in @file{threads/thread.h}, which you
should not change. This function causes the currently running thread
to block until the thread whose thread id is passed as an argument
-exits. If A is the running thread and B is the argument, then we say
-that ``A joins B'' in this case.
+exits. If @var{A} is the running thread and @var{B} is the argument,
+then we say that ``@var{A} joins @var{B}.''
Incidentally, we don't use @code{struct thread *} as
-@file{thread_join()}'s parameter type because a thread pointer is not
+@func{thread_join}'s parameter type because a thread pointer is not
unique over time. That is, when a thread dies, its memory may be,
whether immediately or much later, reused for another thread. If
thread A over time had two children B and C that were stored at the
-same address, then @code{thread_join(@r{B})} and
-@code{thread_join(@r{C})} would be ambiguous. Introducing a thread id
-or @dfn{tid}, represented by type @code{tid_t}, that is intentionally
-unique over time solves the problem. The provided code uses an
-@code{int} for @code{tid_t}, but you may decide you prefer to use some
-other type.
-
-The model for @code{thread_join()} is the @command{wait} system call
+same address, then @code{thread_join(@var{B})} and
+@code{thread_join(@var{C})} would be ambiguous. Introducing a thread
+id or @dfn{tid}, represented by type @code{tid_t}, that is
+intentionally unique over time solves the problem. The provided code
+uses an @code{int} for @code{tid_t}, but you may decide you prefer to
+use some other type.
+
+The model for @func{thread_join} is the @command{wait} system call
in Unix-like systems. (Try reading the manpages.) That system call
can only be used by a parent process to wait for a child's death. You
-should implement @code{thread_join()} to have the same restriction.
+should implement @func{thread_join} to have the same restriction.
That is, a thread may only join its immediate children.
A thread need not ever be joined. Your solution should properly free
exited at the time of the later joins. Thus, joins on T after the
first should return immediately.
-Calling @code{thread_join()} on an thread that is not the caller's
+Calling @func{thread_join} on an thread that is not the caller's
child should cause the caller to return immediately.
-Consider all the ways a join can occur: nested joins (A joins B when B
-is joined on C), multiple joins (A joins B, then A joins C), and so
-on. Does your join work if @code{thread_join()} is called on a thread
-that has not yet been scheduled for the first time? You should handle
-all of these cases. Write test code that demonstrates the cases your
-join works for. Don't overdo the output volume, please!
+Consider all the ways a join can occur: nested joins (@var{A} joins
+@var{B}, then @var{B} joins @var{C}), multiple joins (@var{A} joins
+@var{B}, then @var{A} joins @var{C}), and so on. Does your join work
+if @func{thread_join} is called on a thread that has not yet been
+scheduled for the first time? You should handle all of these cases.
+Write test code that demonstrates the cases your join works for.
+Don't overdo the output volume, please!
Be careful to program this function correctly. You will need its
functionality for project 2.
-Once you've implemented @code{thread_join()}, define
+Once you've implemented @func{thread_join}, define
@code{THREAD_JOIN_IMPLEMENTED} in @file{constants.h}.
@xref{Conditional Compilation}, for more information.
Implement priority scheduling in Pintos. Priority scheduling is a key
building block for real-time systems. Implement functions
-@code{thread_set_priority()} to set the priority of the running thread
-and @code{thread_get_priority()} to get the running thread's priority.
+@func{thread_set_priority} to set the priority of the running thread
+and @func{thread_get_priority} to get the running thread's priority.
(A thread can examine and modify only its own priority.) There are
already prototypes for these functions in @file{threads/thread.h},
which you should not change.
Thread priority ranges from @code{PRI_MIN} (0) to @code{PRI_MAX} (59).
The initial thread priority is passed as an argument to
-@code{thread_create()}. If there's no reason to choose another
+@func{thread_create}. If there's no reason to choose another
priority, use @code{PRI_DEFAULT} (29). The @code{PRI_} macros are
defined in @file{threads/thread.h}, and you should not change their
values.
One issue with priority scheduling is ``priority inversion'': if a
high priority thread needs to wait for a low priority thread (for
instance, for a lock held by a low priority thread, or in
-@code{thread_join()} for a thread to complete), and a middle priority
+@func{thread_join} for a thread to complete), and a middle priority
thread is on the ready list, then the high priority thread will never
get the CPU because the low priority thread will not get any CPU time.
A partial fix for this problem is to have the waiting thread
donation and inversion can occur. Be sure to handle multiple
donations, in which multiple priorities are donated to a thread. You
must also handle nested donation: given high, medium, and low priority
-threads H, M, and L, respectively, if H is waiting on a lock that M
-holds and M is waiting on a lock that L holds, then both M and L
-should be boosted to H's priority.
+threads @var{H}, @var{M}, and @var{L}, respectively, if @var{H} is
+waiting on a lock that @var{M} holds and @var{M} is waiting on a lock
+that @var{L} holds, then both @var{M} and @var{L} should be boosted to
+@var{H}'s priority.
You only need to implement priority donation when a thread is waiting
for a lock held by a lower-priority thread. You do not need to
As you've discovered, you cannot sleep in an external interrupt
handler. Since many lock, semaphore, and condition variable functions
attempt to sleep, you won't be able to call those in
-@code{timer_interrupt()}. You may still use those that never sleep.
+@func{timer_interrupt}. You may still use those that never sleep.
Having said that, you need to make sure that global data does not get
updated by multiple threads simultaneously executing
-@code{timer_sleep()}. Here are some pieces of information to think
+@func{timer_sleep}. Here are some pieces of information to think
about:
@enumerate a
@item
-Interrupts are turned off while @code{timer_interrupt()} runs. This
-means that @code{timer_interrupt()} will not be interrupted by a
-thread running in @code{timer_sleep()}.
+Interrupts are turned off while @func{timer_interrupt} runs. This
+means that @func{timer_interrupt} will not be interrupted by a
+thread running in @func{timer_sleep}.
@item
-A thread in @code{timer_sleep()}, however, can be interrupted by a
-call to @code{timer_interrupt()}, except when that thread has turned
+A thread in @func{timer_sleep}, however, can be interrupted by a
+call to @func{timer_interrupt}, except when that thread has turned
off interrupts.
@item
list.
@item
-@b{If a thread calls @code{thread_yield()} and then it turns out that
+@b{If a thread calls @func{thread_yield} and then it turns out that
it has higher priority than any other threads, does the high-priority
thread continue running?}
Yes. If there is a single highest-priority thread, it continues
running until it blocks or finishes, even if it calls
-@code{thread_yield()}.
+@func{thread_yield}.
@item
@b{If the highest priority thread is added to the ready to run list it
@end example
This happens because context switches are being invoked by the test
-when it explicitly calls @code{thread_yield()}. However, the time
+when it explicitly calls @func{thread_yield}. However, the time
slice timer is still alive and so, every tick (by default), thread 1
-gets switched out (caused by @code{timer_interrupt()} calling
-@code{intr_yield_on_return()}) before it gets a chance to run its
+gets switched out (caused by @func{timer_interrupt} calling
+@func{intr_yield_on_return}) before it gets a chance to run its
mainline. It is by coincidence that Thread 1 is the one that gets
skipped in our example. If we use a different jitter value, the same
behavior is seen where a thread gets started and switched out
solution must act this way.
@item
-@b{What should @code{thread_get_priority()} return in a thread while
+@b{What should @func{thread_get_priority} return in a thread while
its priority has been increased by a donation?}
The higher (donated) priority.
-@node Pintos Tour
+@node Pintos Tour, Project 1--Threads, Introduction, Top
@chapter A Tour Through Pintos
This chapter is a brief tour through the Pintos code. It covers the
so you may find that you want to read each part as you work on the
corresponding project.
+Hint: try using ``tags'' to follow along with references to function
+and variable names (@pxref{Tags}).
+
+@menu
+* Pintos Loading::
+* Threads Tour::
+@end menu
+
@node Pintos Loading
@section Loading
This section covers the Pintos loader and basic kernel
initialization.
+@menu
+* Pintos Loader::
+* Kernel Initialization::
+@end menu
+
@node Pintos Loader
@subsection The Loader
``linker script'' in @file{threads/kernel.lds.S}, the kernel has
arranged that it begins with the assembly module
@file{threads/start.S}. This assembly module just calls
-@code{main()}, which never returns.
+@func{main}, which never returns.
There's one more trick to the loader: the Pintos kernel command line
is stored in the boot loader. The @command{pintos} program actually
@node Kernel Initialization
@subsection Kernel Initialization
-The kernel proper starts with the @code{main()} function. The
-@code{main()} function is written in C, as will be most of the code we
+The kernel proper starts with the @func{main} function. The
+@func{main} function is written in C, as will be most of the code we
encounter in Pintos from here on out.
-When @code{main()} starts, the system is in a pretty raw state. We're
+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
-ready. Thus, the @code{main()} function consists primarily of calls
-into other Pintos modules' initialization functions, which are
-typically named @code{@var{module}_init()}, where @var{module} is the
-module's name.
+ready. Thus, the @func{main} function consists primarily of calls
+into other Pintos modules' initialization functions. You should
+notice that these are usually named @func{@var{module}_init}, where
+@var{module} is the module's name, @file{@var{module}.c} is the
+module's source code, and @file{@var{module}.h} is the module's
+header.
-First we initialize kernel RAM in @code{ram_init()}. The first step
+First we initialize kernel RAM in @func{ram_init}. The first step
is to clear out the kernel's so-called ``BSS'' segment. The BSS is a
segment that should be initialized to all zeros. In C, whenever you
declare a variable outside a function without providing an
actually required by the ANSI C standard, but it is the case with most
implementations of C on most machines.} Because it's all zeros, the
BSS isn't stored in the image that the loader brought into memory. We
-just use @code{memset()} to zero it out. The other task of
-@code{ram_init()} is to read out the machine's memory size from where
+just use @func{memset} to zero it out. The other task of
+@func{ram_init} is to read out the machine's memory size from where
the loader stored it and put it into the @code{ram_pages} variable for
later use.
+Next, @func{thread_init} initializes the thread system. We will defer
+full discussion to our discussion of Pintos threads below. It is
+called so early in initialization because the console, initialized
+just below, 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}.
+@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
+print a startup message to the console.
+
+@func{main} calls @func{argv_init} to parse the kernel command line.
+This entails reading the command line out of the loader and updating
+global variables appropriately.
+
+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.
+
+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. @func{argv_init} might already have done this (if
+the user specified @option{-rs} on the @command{pintos} command line)
+but calling it a second time is harmless and has no effect.
+
+We initialize the interrupt system in the next set of calls.
+@func{intr_init} sets up the CPU's @dfn{interrupt descriptor table}
+(IDT) to ready it for interrupt handling, then @func{timer_init} and
+@func{kbd_init} prepare us to handle timer interrupts and keyboard
+interrupts, respectively. In 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.
+Interrupt-driven serial port I/O is also possible now, so we use
+@func{serial_init_queue} to switch to that mode.
+
+If the filesystem is compiled in, as it will be in project 2 and
+later, we now initialize the disks with @func{disk_init}, then the
+filesystem with @func{filesys_init}, and run any operations that were
+requested on the kernel command line with @func{fsutil_run}.
+Boot is complete, so we print a message.
+
+For project 1, now we execute @func{test}, which runs whatever test is
+currently compiled into the kernel. For later projects, we will
+instead run a user program and wait for it to complete.
+
+Finally, if @option{-q} was specified on the kernel command line, we
+call @func{power_off} to terminate the machine simulator. Otherwise,
+@func{main} calls @func{thread_exit}, which allows any other running
+threads to continue running.
@node Threads Tour
@section Threads
+
+@menu
+* struct thread::
+@end menu
+
+@node struct thread
+@subsection @struct{thread}
+
+The main Pintos data structure for threads is @struct{thread},
+declared in @file{threads/thread.h}. @struct{thread} has these
+members with the given type:
+
+@table @code
+@item tid_t tid;
+The thread's thread identifier or @dfn{tid}. Every thread must have a
+tid that is unique over the entire lifetime of the kernel. By
+default, @code{tid_t} is a @code{typedef} for @code{int} and each new
+thread receives the numerically next higher tid, starting from 1 for
+the initial process. You can change the type and the numbering scheme
+if you like.
+
+@item enum thread_status status;
+The thread's state, one of these:
+
+@table @code
+@item THREAD_RUNNING
+The thread is running. Exactly one thread is running at a given time.
+@func{thread_current} returns the running thread.
+
+@item THREAD_READY
+The thread is ready to run, but it's not running right now. The
+thread could be selected to run the next time the scheduler is
+invoked. Ready threads are kept in a doubly linked list called
+@code{ready_list}.
+
+@item THREAD_BLOCKED
+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}.
+
+@item THREAD_DYING
+The thread will be destroyed by the scheduler after switching to the
+next thread.
+@end table
+
+@item char name[16];
+The thread's name as a string, or at least the first few characters of
+it.
+
+@item uint8_t *stack;
+Every thread has its own stack to keep track of its state. When the
+thread is running, the CPU's stack pointer register tracks the top of
+the stack and this member is unused. But when the CPU switches to
+another thread, this member saves the thread's stack pointer. No
+other members are needed to save the thread's registers, because the
+other registers that must be saved are saved on the stack.
+
+@item int priority;
+A thread priority, ranging from the lowest possible priority
+@code{PRI_MIN} (0) to the highest possible priority @code{PRI_MAX}
+(59). Pintos as provided ignores thread priorities, but you will
+implement priority scheduling in problem 1-3 (@pxref{Problem 1-3
+Priority Scheduling}).
+
+@item 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 the Pintos doubly linked list ADT.
+
+@item uint32_t *pagedir;
+Only present in project 2 and later.
+
+@item unsigned magic;
+Always set to @code{THREAD_MAGIC}, which is just a random number
+defined in @file{threads/thread.c}, and used to detect stack overflow.
+See below for more information.
+@end table
+
+Every @struct{thread} occupies the beginning of its own page of
+memory. The rest of the page is used for the thread's stack, which
+grows downward from the end of the page. It looks like this:
+
+@example
+ 4 kB +---------------------------------+
+ | kernel stack |
+ | | |
+ | | |
+ | V |
+ | grows downward |
+ | |
+ | |
+ | |
+ | |
+ | |
+ | |
+ | |
+ | |
+ +---------------------------------+
+ | magic |
+ | : |
+ | : |
+ | name |
+ | status |
+ 0 kB +---------------------------------+
+@end example
+
+The upshot of this is twofold. First, @struct{thread} must not be
+allowed to grow too big. If it does, then there will not be enough
+room for the kernel stack. Our base @struct{thread} is only a few
+bytes in size. It probably should stay well under 1 kB.
+
+Second, kernel stacks must not be allowed to grow too large. If a
+stack overflows, it will corrupt the thread state. Thus, kernel
+functions should not allocate large structures or arrays as non-static
+local variables. Use dynamic allocation with @func{malloc} or
+@func{palloc_get_page} instead.
+
+This brings us to the purpose of @struct{thread}'s @code{magic}
+member. If a thread's stack does overflow, then @code{magic} will be
+the first member of @struct{thread} to be overwritten, because it is
+closest to the kernel stack. Thus, some of the thread functions
+(notably @func{thread_current}) check that @code{magic} has the proper
+value.
+
+@node Thread Functions
+@subsection Thread Functions
+
+@file{threads/thread.c} implements several public functions for
+thread support. Let's take a look at some of them:
+
+@deftypefun void thread_init (void)
+Called by @func{main} to initialize the thread system. Its main
+purpose is to create a @struct{thread} for Pintos's initial thread.
+This is possible because the Pintos loader sets up the initial
+thread's stack at the end of a page. Before @func{thread_init} runs,
+@func{thread_current} will fail because the running thread's
+@code{magic} value is incorrect. Lots of functions call
+@func{thread_current} directly or indirectly, including
+@func{lock_acquire} for locking a lock, so @func{thread_init} is
+called early in Pintos initialization.
+@end deftypefun
+
+@deftypefun void thread_start (void)
+Called by @func{main} to start the scheduler. Creates the idle
+thread, that is, the thread that is scheduled when no other thread is
+ready. Then enables interrupts, which enables the scheduler because
+processes are rescheduled in the return path from the timer
+interrupt. FIXME
+@end deftypefun
+
+@deftypefun void thread_tick (void)
+Called by @func{timer_interrupt} on every timer interrupt. Just
+increments counters that keep track of how often various kinds of
+threads run.
+@end deftypefun
+
+@deftypefun void thread_print_stats (void)
+Prints the statistics kept by @func{thread_ticK] to the console.
+Called when Pintos is terminating.
+@end deftypefun
+
+@deftypefun void thread_create (const char *@var{name}, int @var{priority}, @
+ thread_func *@var{func}, void *@var{aux}) Creates and
+starts a new thread named @var{name} with the given @var{priority},
+returning the new thread's tid. The thread executes @var{func},
+passing @var{aux} as the function's single argument.
+
+@func{thread_create} works by allocating a page for the thread's
+@struct{thread} and stack and initializing its members, then setting
+up a set of fake stack frames for it (we'll talk more about this
+later). The thread was initialized in the blocked state, so the final
+action before returning is to unblock it, allowing the new thread to
+be scheduled.
+@end deftypefun
other part of the code for this assignment. We will describe the
relevant parts below. If you are confident in your HW1 code, you can
build on top of it. However, if you wish you can start with a fresh
-copy of the code and re-implement @code{thread_join()}, which is the
+copy of the code and re-implement @func{thread_join}, which is the
only part of project #1 required for this assignment. Your submission
should define @code{THREAD_JOIN_IMPLEMENTED} in @file{constants.h}
(@pxref{Conditional Compilation}).
A simple manager for 80@var{x} page directories and page tables.
Although you probably won't want to modify this code for this project,
you may want to call some of its functions. In particular,
-@code{pagedir_get_page()} may be helpful for accessing user memory.
+@func{pagedir_get_page} may be helpful for accessing user memory.
@item syscall.c
@itemx syscall.h
them slightly differently on 80@var{x}86.} These files handle
exceptions. Currently all exceptions simply print a message and
terminate the process. Some, but not all, solutions to project 2
-require modifying @code{page_fault()} in this file.
+require modifying @func{page_fault} in this file.
@item gdt.c
@itemx gdt.c
Pintos can run normal C programs. In fact, it can run any program you
want, provided it's compiled into the proper file format, and uses
-only the system calls you implement. (For example, @code{malloc()}
+only the system calls you implement. (For example, @func{malloc}
makes use of functionality that isn't provided by any of the syscalls
we require you to support.) The only other limitation is that Pintos
can't run programs using floating point operations, since it doesn't
free to use the entire space of user virtual memory however it
chooses. When the kernel switches from one process to another, it
also switches user virtual address spaces by switching the processor's
-page directory base register (see @code{pagedir_activate() in
+page directory base register (see @func{pagedir_activate in
@file{userprog/pagedir.c}}.
Kernel virtual memory is global. It is always mapped the same way,
User programs can only access user virtual memory. An attempt to
access kernel virtual memory will cause a page fault, handled by
-@code{page_fault()} in @file{userprog/exception.c}, and the process
+@func{page_fault} in @file{userprog/exception.c}, and the process
will be terminated. Kernel threads can access both kernel virtual
memory and, if a user process is running, the user virtual memory of
the running process. However, even in the kernel, an attempt to
@node Problem 2-1 Argument Passing
@section Problem 2-1: Argument Passing
-Currently, @code{process_execute()} does not support passing arguments
+Currently, @func{process_execute} does not support passing arguments
to new processes. UNIX and other operating systems do allow passing
command line arguments to a program, which accesses them via the argc,
argv arguments to main. You must implement this functionality by
-extending @code{process_execute()} so that instead of simply taking a
+extending @func{process_execute} so that instead of simply taking a
program file name, it can take a program name with arguments as a
single string. That is, @code{process_execute("grep foo *.c")} should
be a legal call. @xref{80x86 Calling Convention}, for information on
recommend adding a single lock that controls access to the filesystem
code. You should acquire this lock before calling any functions in
the @file{filesys} directory, and release it afterward. Don't forget
-that @file{process_execute()} also accesses files. @strong{For now, we
+that @func{process_execute} also accesses files. @strong{For now, we
recommend against modifying code in the @file{filesys} directory.}
We have provided you a function for each system call in
@item
@b{Do we need a working project 1 to implement project 2?}
-You may find the code for @code{thread_join()} to be useful in
+You may find the code for @func{thread_join} to be useful in
implementing the join syscall, but besides that, you can use
the original code provided for project 1.
@b{What's the difference between @code{tid_t} and @code{pid_t}?}
A @code{tid_t} identifies a kernel thread, which may have a user
-process running in it (if created with @code{process_execute()}) or not
-(if created with @code{thread_create()}). It is a data type used only
+process running in it (if created with @func{process_execute}) or not
+(if created with @func{thread_create}). It is a data type used only
in the kernel.
A @code{pid_t} identifies a user process. It is used by user
The second method is to ``assume and react'': directly dereference
user pointers, after checking that they point below @code{PHYS_BASE}.
Invalid user pointers will then cause a ``page fault'' that you can
-handle by modifying the code for @code{page_fault()} in
+handle by modifying the code for @func{page_fault} in
@file{userprog/exception.cc}. This technique is normally faster
because it takes advantage of the processor's MMU, so it tends to be
used in real kernels (including Linux).
Each of these functions assumes that the user address has already been
verified to be below @code{PHYS_BASE}. They also assume that you've
-modified @code{page_fault()} so that a page fault in the kernel causes
+modified @func{page_fault} so that a page fault in the kernel causes
@code{eax} to be set to 0 and its former value copied into @code{eip}.
@item
@b{How do I parse all these argument strings?}
You're welcome to use any technique you please, as long as it works.
-If you're lost, look at @code{strtok_r()}, prototyped in
+If you're lost, look at @func{strtok_r}, prototyped in
@file{lib/string.h} and implemented with thorough comments in
@file{lib/string.c}. You can find more about it by looking at the man
page (run @code{man strtok_r} at the prompt).
@enumerate 1
@item
-@b{What should I do with the parameter passed to @code{exit()}?}
+@b{What should I do with the parameter passed to @func{exit}?}
This value, the exit status of the process, must be returned to the
-thread's parent when @code{join()} is called.
+thread's parent when @func{join} is called.
@item
@b{Can I just cast a pointer to a @code{struct file} object to get a
@end menu
@node Argument Passing to main
-@subsection Argument Passing to @code{main()}
+@subsection Argument Passing to @func{main}
-In @code{main()}'s case, there is no caller to prepare the stack
+In @func{main}'s case, there is no caller to prepare the stack
before it runs. Therefore, the kernel needs to do it. Fortunately,
since there's no caller, there are no registers to save, no return
address to deal with, etc. The only difficult detail to take care of,
-after loading the code, is putting the arguments to @code{main()} on
+after loading the code, is putting the arguments to @func{main} on
the stack.
(The above is a small lie: most compilers will emit code where main
isn't strictly speaking the first function. This isn't an important
detail. If you want to look into it more, try disassembling a program
and looking around a bit. However, you can just act as if
-@code{main()} is the very first function called.)
+@func{main} is the very first function called.)
Pintos is written for the 80@var{x}86 architecture. Therefore, we
need to adhere to the 80@var{x}86 calling convention. Basically, you
function's. The program will assume that the stack has been laid out
this way when it begins running.
-So, what are the arguments to @code{main()}? Just two: an @samp{int}
+So, what are the arguments to @func{main}? Just two: an @samp{int}
(@code{argc}) and a @samp{char **} (@code{argv}). @code{argv} is an
array of strings, and @code{argc} is the number of strings in that
array. However, the hard part isn't these two things. The hard part
the @code{argv} array) onto the stack, along with the length of the
argument vector (@code{argc}, 4 in this example). This must also be
done in this order, since @code{argc} is the first argument to
-@code{main()} and therefore is on first (smaller address) on the
+@func{main} and therefore is on first (smaller address) on the
stack. Finally, we push a fake ``return address'' and leave the stack
pointer to point to its location.
the user virtual address space, in the page just below virtual address
@code{PHYS_BASE} (defined in @file{threads/mmu.h}).
-You may find the non-standard @code{hex_dump()} function, declared in
+You may find the non-standard @func{hex_dump} function, declared in
@file{<stdio.h>}, useful for debugging your argument passing code.
Here's what it would show in the above example, given that
@code{PHYS_BASE} is @t{0xc0000000}:
The normal calling convention pushes function arguments on the stack
from right to left and the stack grows downward. Thus, when the
-system call handler @code{syscall_handler()} gets control, the system
+system call handler @func{syscall_handler} gets control, the system
call number is in the 32-bit word at the caller's stack pointer, the
first argument is in the 32-bit word at the next higher address, and
so on. The caller's stack pointer is accessible to
-@code{syscall_handler()} as the @samp{esp} member of the @code{struct
+@func{syscall_handler} as the @samp{esp} member of the @code{struct
intr_frame} passed to it.
Here's an example stack frame for calling a system call numbered 10
process. Whenever the processor needed to look up a translation, it
consulted the page table. As long as the process only accessed
memory that it didn't own, all was well. If the process accessed
-memory it didn't own, it ``page faulted'' and @code{page_fault()}
+memory it didn't own, it ``page faulted'' and @func{page_fault}
terminated the process.
When we implement virtual memory, the rules have to change. A page
idea.
@end itemize
-The page fault handler, @code{page_fault()} in
+The page fault handler, @func{page_fault} in
@file{threads/exception.c}, needs to do roughly the following:
@enumerate 1
use your new page table management code to construct the page tables
only as page faults occur for them.
-You should use the @code{palloc_get_page()} function to get the page
+You should use the @func{palloc_get_page} function to get the page
frames that you use for storing user virtual pages. Be sure to pass
the @code{PAL_USER} flag to this function when you do so, because that
allocates pages from a ``user pool'' separate from the ``kernel pool''
-that other calls to @code{palloc_get_page()} make.
+that other calls to @func{palloc_get_page} make.
There are many possible ways to implement virtual memory. The above
is simply an outline of our suggested implementation.
segments won't change.
There are a few special cases. Look at the loop in
-@code{load_segment()} in @file{userprog/process.c}. Each time
+@func{load_segment} in @file{userprog/process.c}. Each time
around the loop, @code{read_bytes} represents the number of bytes to
read from the executable file and @code{zero_bytes} represents the number
of bytes to initialize to zero following the bytes read. The two
for?}
In simple cases you won't have any need for the @var{aux} parameters.
-In these cases you can just pass a null pointer to @code{hash_init()}
+In these cases you can just pass a null pointer to @func{hash_init}
for @var{aux} and ignore the values passed to the hash function and
comparison functions. (You'll get a compiler warning if you don't use
the @var{aux} parameter, but you can turn that off with the
your design document. Please make sure to justify your decision.
@item
-@b{Why do I need to pass @code{PAL_USER} to @code{palloc_get_page()}
+@b{Why do I need to pass @code{PAL_USER} to @func{palloc_get_page}
when I allocate physical page frames?}
-You can layer some other allocator on top of @code{palloc_get_page()}
+You can layer some other allocator on top of @func{palloc_get_page}
if you like, but it should be the underlying mechanism, directly or
indirectly, for two reasons. First, running out of pages in the user
pool just causes user programs to page, but running out of pages in
projects / pintos-anon / commitdiff