-@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.
@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.
-You may need to add or modify code where interrupts are already
-disabled, such as in @func{sema_up} or @func{sema_down}. You should
-still try to keep this code as short as you can.
+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
than the currently running thread, the current thread should
immediately yield the processor to the new thread. Similarly, when
threads are waiting for a lock, semaphore, or condition variable, the
-highest priority waiting thread should be woken up first. A thread
+highest priority waiting thread should be awakened first. A thread
may raise or lower its own priority at any time, but lowering its
priority such that it no longer has the highest priority must cause it
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
scheduler
with the @option{-mlfqs} kernel option. Passing this
option sets @code{enable_mlfqs}, declared in @file{threads/init.h}, to
-true, when the options are parsed by @func{parse_options}, which happens
-through midway through @func{main}.
+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
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}
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 (../../tests/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)
+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
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 multiple threads have the same highest priority,
Priority donation only changes the priority of the donee
thread. The donor thread's priority is unchanged.
-Priority donation is not additive: if thread @var{A} (with priority 3) donates
-to thread @var{B} (with priority 5), then @var{B}'s new priority is 3, not 8.
+Priority donation is not additive: if thread @var{A} (with priority 5) donates
+to thread @var{B} (with priority 3), then @var{B}'s new priority is 5, not 8.
@item Can a thread's priority change while it is on the ready queue?
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
@item How does @func{thread_set_priority} affect a thread receiving donations?
-It should do something sensible, but no particular behavior is
-required. None of the test cases call @func{thread_set_priority} from a
-thread while it is receiving a priority donation.
+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!
@item Can I use one queue instead of 64 queues?
-Yes, that's fine. It's easiest to describe the algorithm in terms of 64
-separate queues, but that doesn't mean you have to implement it that
-way.
-
-If you use a single queue, it should probably be sorted.
+Yes. In general, your implementation may differ from the description,
+as long as its behavior is the same.
@end table
projects / pintos-anon / blobdiff