@item loader.S
@itemx loader.h
The kernel loader. Assembles to 512 bytes of code and data that the
-PC BIOS loads into memory and which in turn loads the kernel into
-memory, does basic processor initialization, and jumps to the
-beginning of the kernel. @xref{Pintos Loader}, for details. You should
-not need to look at this code or modify it.
+PC BIOS loads into memory and which in turn finds the kernel on disk,
+loads it into memory, and jumps to @func{start} in @file{start.S}.
+@xref{Pintos Loader}, for details. You should not need to look at
+this code or modify it.
+
+@item start.S
+Does basic setup needed for memory protection and 32-bit
+operation on 80@var{x}86 CPUs. Unlike the loader, this code is
+actually part of the kernel. @xref{Low-Level Kernel Initialization},
+for details.
@item kernel.lds.S
The linker script used to link the kernel. Sets the load address of
-the kernel and arranges for @file{start.S} to be at the very beginning
+the kernel and arranges for @file{start.S} to be near the beginning
of the kernel image. @xref{Pintos Loader}, for details. Again, you
should not need to look at this code
or modify it, but it's here in case you're curious.
-@item start.S
-Jumps to @func{main}.
-
@item init.c
@itemx init.h
Kernel initialization, including @func{main}, the kernel's ``main
program.'' You should look over @func{main} at least to see what
gets initialized. You might want to add your own initialization code
-here. @xref{Kernel Initialization}, for details.
+here. @xref{High-Level Kernel Initialization}, for details.
@item thread.c
@itemx thread.h
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 block.c
+@itemx block.h
+An abstraction layer for @dfn{block devices}, that is, random-access,
+disk-like devices that are organized as arrays of fixed-size blocks.
+Out of the box, Pintos supports two types of block devices: IDE disks
+and partitions. Block devices, regardless of type, won't actually be
+used until project 2.
+
+@item ide.c
+@itemx ide.h
+Supports reading and writing sectors on up to 4 IDE disks.
+
+@item partition.c
+@itemx partition.h
+Understands the structure of partitions on disks, allowing a single
+disk to be carved up into multiple regions (partitions) for
+independent use.
@item kbd.c
@itemx kbd.h
Interrupt queue, for managing a circular queue that both kernel
threads and interrupt handlers want to access. Used by the keyboard
and serial drivers.
+
+@item rtc.c
+@itemx rtc.h
+Real-time clock driver, to enable the kernel to determine the current
+date and time. By default, this is only used by @file{thread/init.c}
+to choose an initial seed for the random number generator.
+
+@item speaker.c
+@itemx speaker.h
+Driver that can produce tones on the PC speaker.
+
+@item pit.c
+@itemx pit.h
+Code to configure the 8254 Programmable Interrupt Timer. This code is
+used by both @file{devices/timer.c} and @file{devices/speaker.c}
+because each device uses one of the PIT's output channel.
@end table
@node lib files
@item random.c
@itemx random.h
-Pseudo-random number generator.
+Pseudo-random number generator. The actual sequence of random values
+will not vary from one Pintos run to another, unless you do one of
+three things: specify a new random seed value on the @option{-rs}
+kernel command-line option on each run, or use a simulator other than
+Bochs, or specify the @option{-r} option to @command{pintos}.
@item round.h
Macros for rounding.
who have done this have turned in code that did not even compile or
boot, much less pass any tests.
-Instead, we recommend integrating your team's changes early and often,
-using a source code control system such as CVS (@pxref{CVS}) or a
-group collaboration site such as SourceForge (@pxref{SourceForge}).
-This is less likely to produce surprises, because everyone can see
-everyone else's code as it is written, instead of just when it is
-finished. These systems also make it possible to review changes and,
-when a change introduces a bug, drop back to working versions of code.
+@localcvspolicy{}
You should expect to run into bugs that you simply don't understand
while working on this and subsequent projects. When you do,
nested priority donation, such as 8 levels.
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.
+implement priority donation for the other Pintos synchronization
+constructs. You do need to implement priority scheduling in all
+cases.
Finally, implement the following functions that allow a thread to
examine and modify its own priority. Skeletons for these functions are
with the @option{-mlfqs} kernel option. Passing this
option sets @code{thread_mlfqs}, declared in @file{threads/thread.h}, to
true when the options are parsed by @func{parse_options}, which happens
-midway through @func{main}.
+early in @func{main}.
When the 4.4@acronym{BSD} scheduler is enabled, threads no longer
directly control their own priorities. The @var{priority} argument to
@xref{Testing}.
+@item Should I try running the tests with jitter?
+
+Using the jitter feature in Bochs (@pxref{Debugging versus Testing})
+is a great way to discover bugs that are timing dependent. However,
+the following tests are known to
+fail with jitter even if your code is correct: @code{alarm-priority},
+@code{alarm-simultaneous},
+@code{mlfqs-recent-1}, @code{mlfqs-fair-2}, @code{mlfqs-fair-20},
+@code{mlfqs-nice-2}, @code{mlfqs-nice-10}, and @code{priority-fifo}.
+The behavior of these tests can sometimes vary based on timing (e.g.,
+if a timer interrupt arrives at an inconvenient time).
+
@item Why do I get a test failure in @func{pass}?
@anchor{The pass function fails}
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
+Attributes}), so it doesn't include any code in @func{fail} 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
Don't worry about the possibility of timer values overflowing. Timer
values are expressed as signed 64-bit numbers, which at 100 ticks per
second should be good for almost 2,924,712,087 years. By then, we
-expect Pintos to have been phased out of the CS 140 curriculum.
+expect Pintos to have been phased out of the Computer Science curriculum.
@end table
@node Priority Scheduling FAQ
@item Can a thread's priority change while it is on the ready queue?
-Yes. Consider this case: low-priority thread @var{L} holds a
-lock that high-priority thread @var{H} wants, so @var{H} donates its
-priority to @var{L}. @var{L} releases the lock and
-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.
+Yes. Consider a ready, low-priority thread @var{L} that holds a lock.
+High-priority thread @var{H} attempts to acquire the lock and blocks,
+thereby donating its priority to ready thread @var{L}.
@item Can a thread's priority change while it is blocked?
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 Doubled test names in output make them fail.
+
+Suppose you are seeing output in which some test names are doubled,
+like this:
+
+@example
+(alarm-priority) begin
+(alarm-priority) (alarm-priority) Thread priority 30 woke up.
+Thread priority 29 woke up.
+(alarm-priority) Thread priority 28 woke up.
+@end example
-@anchor{printf Reboots}
-Yes. These functions are called before @func{printf} is ready to go.
-You could add a global flag initialized to false and set it to true
-just before the first @func{printf} in @func{main}. Then modify
-@func{printf} itself to return immediately if the flag isn't set.
+What is happening is that output from two threads is being
+interleaved. That is, one thread is printing @code{"(alarm-priority)
+Thread priority 29 woke up.\n"} and another thread is printing
+@code{"(alarm-priority) Thread priority 30 woke up.\n"}, but the first
+thread is being preempted by the second in the middle of its output.
+
+This problem indicates a bug in your priority scheduler. After all, a
+thread with priority 29 should not be able to run while a thread with
+priority 30 has work to do.
+
+Normally, the implementation of the @code{printf()} function in the
+Pintos kernel attempts to prevent such interleaved output by acquiring
+a console lock during the duration of the @code{printf} call and
+releasing it afterwards. However, the output of the test name,
+e.g., @code{(alarm-priority)}, and the message following it is output
+using two calls to @code{printf}, resulting in the console lock being
+acquired and released twice.
@end table
@node Advanced Scheduler FAQ
Yes. In general, your implementation may differ from the description,
as long as its behavior is the same.
+
+@item Some scheduler tests fail and I don't understand why. Help!
+
+If your implementation mysteriously fails some of the advanced
+scheduler tests, try the following:
+
+@itemize
+@item
+Read the source files for the tests that you're failing, to make sure
+that you understand what's going on. Each one has a comment at the
+top that explains its purpose and expected results.
+
+@item
+Double-check your fixed-point arithmetic routines and your use of them
+in the scheduler routines.
+
+@item
+Consider how much work your implementation does in the timer
+interrupt. If the timer interrupt handler takes too long, then it
+will take away most of a timer tick from the thread that the timer
+interrupt preempted. When it returns control to that thread, it
+therefore won't get to do much work before the next timer interrupt
+arrives. That thread will therefore get blamed for a lot more CPU
+time than it actually got a chance to use. This raises the
+interrupted thread's recent CPU count, thereby lowering its priority.
+It can cause scheduling decisions to change. It also raises the load
+average.
+@end itemize
@end table
projects / pintos-anon / blobdiff