-@node Project 1--Threads, Project 2--User Programs, Pintos Tour, Top
+@node Project 1--Threads
@chapter Project 1: Threads
In this assignment, we give you a minimally functional thread system.
Before you read the description of this project, you should read all of
the following sections: @ref{Introduction}, @ref{Coding Standards},
@ref{Debugging Tools}, and @ref{Development Tools}. You should at least
-skim the material in @ref{Threads Tour} and especially
-@ref{Synchronization}. To complete this project you will also need to
-read @ref{4.4BSD Scheduler}.
+skim the material from @ref{Pintos Loading} through @ref{Memory
+Allocation}, especially @ref{Synchronization}. To complete this project
+you will also need to read @ref{4.4BSD Scheduler}.
@menu
* Project 1 Background::
state of the currently running thread and restores the state of the
thread we're switching to.
-Using the @command{gdb} debugger, slowly trace through a context
-switch to see what happens (@pxref{gdb}). You can set a
+Using the GDB debugger, slowly trace through a context
+switch to see what happens (@pxref{GDB}). You can set a
breakpoint on @func{schedule} to start out, and then
-single-step from there.@footnote{@command{gdb} might tell you that
-@func{schedule} doesn't exist, which is arguably a @command{gdb} bug.
+single-step from there.@footnote{GDB might tell you that
+@func{schedule} doesn't exist, which is arguably a GDB bug.
You can work around this by setting the breakpoint by filename and
line number, e.g.@: @code{break thread.c:@var{ln}} where @var{ln} is
the line number of the first declaration in @func{schedule}.} Be sure
@item thread.c
@itemx thread.h
-Basic thread support. Much of your work will take place in these
-files. @file{thread.h} defines @struct{thread}, which you are likely
-to modify in all four projects. See @ref{struct thread} and @ref{Thread
-Support} for more information.
+Basic thread support. Much of your work will take place in these files.
+@file{thread.h} defines @struct{thread}, which you are likely to modify
+in all four projects. See @ref{struct thread} and @ref{Threads} for
+more information.
@item switch.S
@itemx switch.h
Functions for I/O port access. This is mostly used by source code in
the @file{devices} directory that you won't have to touch.
-@item mmu.h
-Functions and macros related to memory management, including page
-directories and page tables. This will be more important to you in
-project 3. For now, you can ignore it.
+@item vaddr.h
+@itemx pte.h
+Functions and macros for working with virtual addresses and page table
+entries. These will be more important to you in project 3. For now,
+you can ignore them.
@item flags.h
Macros that define a few bits in the 80@var{x}86 ``flags'' register.
-Probably of no interest. See @bibref{IA32-v1}, section 3.4.3, for more
-information.
+Probably of no interest. See @bibref{IA32-v1}, section 3.4.3, ``EFLAGS
+Register,'' for more information.
@end table
@menu
@item serial.c
@itemx serial.h
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.
+so you don't need to do so yourself.
+It handles serial input by passing it to the input layer (see below).
@item disk.c
@itemx disk.h
Supports reading and writing sectors on up to 4 IDE disks. This won't
actually be used until project 2.
+@item kbd.c
+@itemx kbd.h
+Keyboard driver. Handles keystrokes passing them to the input layer
+(see below).
+
+@item input.c
+@itemx input.h
+Input layer. Queues input characters passed along by the keyboard or
+serial drivers.
+
@item intq.c
@itemx intq.h
Interrupt queue, for managing a circular queue that both kernel
interrupt handling latency, which can make a machine feel sluggish if
taken too far.
+The synchronization primitives themselves in @file{synch.c} are
+implemented by disabling interrupts. You may need to increase the
+amount of code that runs with interrupts disabled here, but you should
+still try to keep it to a minimum.
+
Disabling interrupts can be useful for debugging, if you want to make
sure that a section of code is not interrupted. You should remove
-debugging code before turning in your project.
+debugging code before turning in your project. (Don't just comment it
+out, because that can make the code difficult to read.)
There should be no busy waiting in your submission. A tight loop that
calls @func{thread_yield} is one form of busy waiting.
to immediately yield the CPU.
Thread priorities range from @code{PRI_MIN} (0) to @code{PRI_MAX} (63).
-Lower numbers correspond to @emph{higher} priorities, so that priority 0
-is the highest priority and priority 63 is the lowest.
+Lower numbers correspond to lower priorities, so that priority 0
+is the lowest priority and priority 63 is the highest.
The initial thread priority is passed as an argument to
@func{thread_create}. If there's no reason to choose another
priority, use @code{PRI_DEFAULT} (31). The @code{PRI_} macros are
thread. You must also handle nested donation: 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.
+priority. If necessary, you may impose a reasonable limit on depth of
+nested priority donation, such as 8 levels.
-You need not implement priority donation when a thread is waiting
-for a lock held by a lower-priority thread. You need not
-implement priority donation for semaphores or condition variables,
-but you are welcome to do so. You do need to implement
+You must implement priority donation for locks. You need not
+implement priority donation for semaphores or condition variables
+(but you are welcome to do so). You do need to implement
priority scheduling in all cases.
Finally, implement the following functions that allow a thread to
donation, returns the higher (donated) priority.
@end deftypefun
+You need not provide any interface to allow a thread to directly modify
+other threads' priorities.
+
The priority scheduler is not used in any later project.
@node Advanced Scheduler
Implement a multilevel feedback queue scheduler similar to the
4.4@acronym{BSD} scheduler to
reduce the average response time for running jobs on your system.
-@xref{4.4BSD Scheduler}, for a detailed description of
-the MLFQS requirements.
+@xref{4.4BSD Scheduler}, for detailed requirements.
-The advanced scheduler builds on the priority scheduler. You should
-have the priority scheduler working, except possibly for priority
-donation, before you start work on the advanced scheduler.
+Like the priority scheduler, the advanced scheduler chooses the thread
+to run based on priorities. However, the advanced scheduler does not do
+priority donation. Thus, we recommend that you have the priority
+scheduler working, except possibly for priority donation, before you
+start work on the advanced scheduler.
-You must write your code so that we can choose a scheduling algorithm
-policy at Pintos startup time. By default, the round-robin scheduler
+You must write your code to allow us to choose a scheduling algorithm
+policy at Pintos startup time. By default, the priority scheduler
must be active, but we must be able to choose the 4.4@acronym{BSD}
scheduler
with the @option{-mlfqs} kernel option. Passing this
option sets @code{enable_mlfqs}, declared in @file{threads/init.h}, to
-true.
+true when the options are parsed by @func{parse_options}, which happens
+midway through @func{main}.
When the 4.4@acronym{BSD} scheduler is enabled, threads no longer
directly control their own priorities. The @var{priority} argument to
@command{diffstat} program. The final row gives total lines inserted
and deleted; a changed line counts as both an insertion and a deletion.
+The reference solution represents just one possible solution. Many
+other solutions are also possible and many of those differ greatly from
+the reference solution. Some excellent solutions may not modify all the
+files modified by the reference solution, and some may modify files not
+modified by the reference solution.
+
@verbatim
devices/timer.c | 42 +++++-
threads/fixed-point.h | 120 ++++++++++++++++++
5 files changed, 440 insertions(+), 29 deletions(-)
@end verbatim
+@file{fixed-point.h} is a new file added by the reference solution.
+
@item How do I update the @file{Makefile}s when I add a new source file?
@anchor{Adding Source Files}
There are @code{TIME_SLICE} ticks per time slice. This macro is
declared in @file{threads/thread.c}. The default is 4 ticks.
-We don't recommend changing this values, because any changes are likely
+We don't recommend changing this value, because any changes are likely
to cause many of the tests to fail.
+
+@item How do I run the tests?
+
+@xref{Testing}.
+
+@item Why do I get a test failure in @func{pass}?
+
+@anchor{The pass function fails}
+You are probably looking at a backtrace that looks something like this:
+
+@example
+0xc0108810: debug_panic (lib/kernel/debug.c:32)
+0xc010a99f: pass (tests/threads/tests.c:93)
+0xc010bdd3: test_mlfqs_load_1 (...threads/mlfqs-load-1.c:33)
+0xc010a8cf: run_test (tests/threads/tests.c:51)
+0xc0100452: run_task (threads/init.c:283)
+0xc0100536: run_actions (threads/init.c:333)
+0xc01000bb: main (threads/init.c:137)
+@end example
+
+This is just confusing output from the @command{backtrace} program. It
+does not actually mean that @func{pass} called @func{debug_panic}. In
+fact, @func{fail} called @func{debug_panic} (via the @func{PANIC}
+macro). GCC knows that @func{debug_panic} does not return, because it
+is declared @code{NO_RETURN} (@pxref{Function and Parameter
+Attributes}), so it doesn't include any code in @func{pass} to take
+control when @func{debug_panic} returns. This means that the return
+address on the stack looks like it is at the beginning of the function
+that happens to follow @func{fail} in memory, which in this case happens
+to be @func{pass}.
+
+@xref{Backtraces}, for more information.
+
+@item How do interrupts get re-enabled in the new thread following @func{schedule}?
+
+Every path into @func{schedule} disables interrupts. They eventually
+get re-enabled by the next thread to be scheduled. Consider the
+possibilities: the new thread is running in @func{switch_thread} (but
+see below), which is called by @func{schedule}, which is called by one
+of a few possible functions:
+
+@itemize @bullet
+@item
+@func{thread_exit}, but we'll never switch back into such a thread, so
+it's uninteresting.
+
+@item
+@func{thread_yield}, which immediately restores the interrupt level upon
+return from @func{schedule}.
+
+@item
+@func{thread_block}, which is called from multiple places:
+
+@itemize @minus
+@item
+@func{sema_down}, which restores the interrupt level before returning.
+
+@item
+@func{idle}, which enables interrupts with an explicit assembly STI
+instruction.
+
+@item
+@func{wait} in @file{devices/intq.c}, whose callers are responsible for
+re-enabling interrupts.
+@end itemize
+@end itemize
+
+There is a special case when a newly created thread runs for the first
+time. Such a thread calls @func{intr_enable} as the first action in
+@func{kernel_thread}, which is at the bottom of the call stack for every
+kernel thread but the first.
@end table
@menu
@item If the highest-priority thread yields, does it continue running?
-Yes. As long as there is a single highest-priority thread, it continues
+Yes. If there is a single highest-priority thread, it continues
running until it blocks or finishes, even if it calls
@func{thread_yield}.
-If there are multiple threads have the same highest priority,
+If multiple threads have the same highest priority,
@func{thread_yield} should switch among them in ``round robin'' order.
@item What happens to the priority of a donating thread?
thus loses the CPU and is moved to the ready queue. Now @var{L}'s
old priority is restored while it is in the ready queue.
+@item Can a thread's priority change while it is blocked?
+
+Yes. While a thread that has acquired lock @var{L} is blocked for any
+reason, its priority can increase by priority donation if a
+higher-priority thread attempts to acquire @var{L}. This case is
+checked by the @code{priority-donate-sema} test.
+
@item Can a thread added to the ready list preempt the processor?
Yes. If a thread added to the ready list has higher priority than the
The highest priority thread should run as soon as it is runnable,
preempting whatever thread is currently running.
+@item How does @func{thread_set_priority} affect a thread receiving donations?
+
+It sets the thread's base priority. The thread's effective priority
+becomes the higher of the newly set priority or the highest donated
+priority. When the donations are released, the thread's priority
+becomes the one set through the function call. This behavior is checked
+by the @code{priority-donate-lower} test.
+
@item Calling @func{printf} in @func{sema_up} or @func{sema_down} reboots!
@anchor{printf Reboots}
It doesn't have to. We won't test priority donation and the advanced
scheduler at the same time.
+
+@item Can I use one queue instead of 64 queues?
+
+Yes. In general, your implementation may differ from the description,
+as long as its behavior is the same.
@end table