-@node Project 1--Threads, Project 2--User Programs, Top, Top
+@node Project 1--Threads
@chapter Project 1: Threads
In this assignment, we give you a minimally functional thread system.
Your job is to extend the functionality of this system to gain a
-better understanding of synchronization problems. Additionally, you
-will use at least part of this increased functionality in future
-assignments.
+better understanding of synchronization problems.
-You will be working in primarily in the @file{threads} directory for
+You will be working primarily in the @file{threads} directory for
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{Coding Standards},
+@ref{Debugging Tools}, and @ref{Development Tools}. You should at least
+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::
+* Project 1 Requirements::
+* Project 1 FAQ::
+@end menu
+
+@node Project 1 Background
+@section Background
+
+
@menu
* Understanding Threads::
-* Debugging versus Testing::
-* Tips::
-* Problem 1-1 Alarm Clock::
-* Problem 1-2 Join::
-* Problem 1-3 Priority Scheduling::
-* Problem 1-4 Advanced Scheduler::
-* Threads FAQ::
+* Project 1 Source Files::
+* Project 1 Synchronization::
+* Development Suggestions::
@end menu
-@node Understanding Threads, Debugging versus Testing, Project 1--Threads, Project 1--Threads
-@section Understanding Threads
+@node Understanding Threads
+@subsection Understanding Threads
-The first step is to read and understand the initial thread system.
-Pintos, by default, implements thread creation and thread completion,
+The first step is to read and understand the code for the initial thread
+system.
+Pintos already implements thread creation and thread completion,
a simple scheduler to switch between threads, and synchronization
-primitives (semaphores, locks, and condition variables).
-@c FIXME: base system doesn't do anything. Debugger sucks.
-However, there's a lot of magic going on in some of this code, so you
-should compile and run the base system to see a simple test of the
-code. You should trace the execution using your favorite debugger to
-get a sense for what's going on.
+primitives (semaphores, locks, condition variables, and optimization
+barriers).
+
+Some of this code might seem slightly mysterious. If
+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 to see what's going
+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
+so on.
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
-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()}.
-
-At any given time, Pintos is running exactly one thread, with the
-others switched out. The scheduler decides which thread to run next
-when it needs to switch between them. (If no thread is ready to run
-at any given time, then the special ``idle'' thread runs.) The
-synchronization primitives are used to force context switches when one
+scheduled. You provide a function to be run in this context as an
+argument to @func{thread_create}. The first time the thread is
+scheduled and runs, it starts from the beginning of that function
+and executes in that context. When the function returns, the thread
+terminates. Each thread, therefore, acts like a mini-program running
+inside Pintos, with the function passed to @func{thread_create}
+acting like @func{main}.
+
+At any given time, exactly one thread runs and the rest, if any,
+become inactive. The scheduler decides which thread to
+run next. (If no thread is ready to run
+at any given time, then the special ``idle'' thread, implemented in
+@func{idle}, runs.)
+Synchronization primitives can force context switches when one
thread needs to wait for another thread to do something.
-The exact mechanics of a context switch are pretty gruesome and have
-been provided for you in @file{switch.S} (this is 80@var{x}86
-assembly; don't worry about understanding it). It involves saving the
-state of the currently running thread and restoring the state of the
+The mechanics of a context switch are
+in @file{threads/switch.S}, which is 80@var{x}86
+assembly code. (You don't have to understand it.) It saves the
+state of the currently running thread and restores the state of the
thread we're switching to.
-@c FIXME
-Slowly trace through a context switch to see what happens. 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 thing the new thread does is to return from
-@code{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.
+
+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{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
+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 @func{switch_threads},
+another thread starts running, and the first thing the new thread does
+is to return from @func{switch_threads}. You will understand the thread
+system once you understand why and how the @func{switch_threads} that
+gets called is different from the @func{switch_threads} that returns.
+@xref{Thread Switching}, for more information.
@strong{Warning}: In Pintos, each thread is assigned a small,
fixed-size execution stack just under @w{4 kB} in size. The kernel
-does try to detect stack overflow, but it cannot always succeed. You
-ma cause bizarre problems, such as mysterious kernel panics, if you
+tries to detect stack overflow, but it cannot do so perfectly. You
+may cause bizarre problems, such as mysterious kernel panics, if you
declare large data structures as non-static local variables,
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
-limit. If you need larger chunks, consider using a linked structure
-instead.
-
-@node Debugging versus Testing, Tips, Understanding Threads, Project 1--Threads
-@section Debugging versus Testing
-
-When you're debugging code, it's useful to be able to be able to run a
-program twice and have it do exactly the same thing. On second and
-later runs, you can make new observations without having to discard or
-verify your old observations. This property is called
-``reproducibility.'' The simulator we use, Bochs, can be set up for
-reproducibility. If you use the Bochs configuration files we provide,
-which specify @samp{ips: @var{n}} where @var{n} is a number of
-simulated instructions per second, your simulations can be
-reproducible.
-
-Of course, a simulation can only be reproducible from one run to the
-next if its input is the same each time. For simulating an entire
-computer, as we do, this means that every part of the computer must be
-the same. For example, you must use the same disks, the same version
-of Bochs, and you must not hit any keys on the keyboard (because you
-could not be sure to hit them at exactly the same point each time)
-during the runs.
-
-While reproducibility is useful for debugging, it is a problem for
-testing thread synchronization, an important part of this project. In
-particular, when Bochs is set up for reproducibility, timer interrupts
-will come at perfectly reproducible points, and therefore so will
-thread switches. That means that running the same test several times
-doesn't give you any greater confidence in your code's correctness
-than does running it only once.
-
-So, to make your code easier to test, we've added a feature to Bochs
-that makes timer interrupts come at random intervals, but in a
-perfectly predictable way. In particular, if you put a line
-@samp{ips-jitter: @var{seed}}, where @var{seed} is an integer, into
-your Bochs configuration file, then timer interrupts will come at
-irregularly spaced intervals. Within a single @var{seed} value,
-execution will still be reproducible, but timer behavior will change
-as @var{seed} is varied. Thus, for the highest degree of confidence
-you should test your code with many seed values.
-
-@node Tips, Problem 1-1 Alarm Clock, Debugging versus Testing, Project 1--Threads
-@section Tips
-
-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
-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
-primitives may be used in what situations.
-
-Given some designs of some problems, there may be one or two instances
-in which it is appropriate to directly change the interrupt levels
-instead of relying on the given synchroniztion primitives. This must
-be justified in your @file{DESIGNDOC} file. If you're not sure you're
-justified, ask!
-
-While all parts of this assignment are required if you intend to earn
-full credit on this project, keep in mind that Problem 2 (Join) will
-be needed for future assignments, so you'll want to get this one
-right. We don't give out solutions, so you're stuck with your Join
-code for the whole quarter. Problem 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 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.
-
-Also keep in mind that Problem 4 (the MFQS) builds on the features you
-implement in Problem 3, so to avoid unnecessary code duplication, it
-would be a good idea to divide up the work among your team members
-such that you have Problem 3 fully working before you begin to tackle
-Problem 4.
-
-@node Problem 1-1 Alarm Clock, Problem 1-2 Join, Tips, Project 1--Threads
-@section Problem 1-2: Alarm Clock
-
-Improve the implementation of the timer device defined in
-@file{devices/timer.c} by reimplementing @code{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
-blinking the cursor once per second. There is no requirement that
-threads start running immediately after waking up; just put them on
-the ready queue after they have waited for approximately the right
-amount of time.
-
-A working implementation of this function is provided. However, the
-version provided is poor, because it ``busy waits,'' that is, it spins
-in a tight loop checking the current time until the current time has
-advanced far enough. This is undesirable because it wastes time that
-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.
-
-@node Problem 1-2 Join, Problem 1-3 Priority Scheduling, Problem 1-1 Alarm Clock, Project 1--Threads
-@section Problem 1-2: Join
-
-Implement @code{thread_join(struct thread *)} in
-@file{threads/thread.c}. There 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 thread 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.
-
-The model for @code{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.
-That is, a thread may only join on its immediate children.
-
-A thread need not ever be joined. Your solution should properly free
-all of a thread's resources, including its @code{struct thread},
-whether it is ever joined or not, and regardless of whether the child
-exits before or after its parent. That is, a thread should be freed
-exactly once in all cases.
-
-Joining a given thread is idempotent. That is, joining a thread T
-multiple times is equivalent to joining it once, because T has already
-exited at the time of the later joins. Thus, joins on T after the
-first should return immediately.
-
-The behavior of calling @code{thread_join()} on an thread that is not
-the caller's child is undefined. You need not handle this case
-gracefully.
-
-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!
-
-Be careful to program this function correctly. You will need its
-functionality for project 2.
-
-@node Problem 1-3 Priority Scheduling, Problem 1-4 Advanced Scheduler, Problem 1-2 Join, Project 1--Threads
-@section Problem 1-3 Priority Scheduling
-
-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 a thread and
-@code{thread_get_priority()} to get the priority of a thread. There
-are already prototypes for these functions in @file{threads/thread.h},
-which you should not change.
+the page allocator and the block allocator (@pxref{Memory Allocation}).
+
+@node Project 1 Source Files
+@subsection Source Files
+
+Here is a brief overview of the files in the @file{threads}
+directory. You will not need to modify most of this code, but the
+hope is that presenting this overview will give you a start on what
+code to look at.
+
+@table @file
+@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.
+
+@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
+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.
+
+@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{Threads} for
+more information.
+
+@item switch.S
+@itemx switch.h
+Assembly language routine for switching threads. Already discussed
+above. @xref{Thread Functions}, for more information.
+
+@item palloc.c
+@itemx palloc.h
+Page allocator, which hands out system memory in multiples of 4 kB
+pages. @xref{Page Allocator}, for more information.
+
+@item malloc.c
+@itemx malloc.h
+A simple implementation of @func{malloc} and @func{free} for
+the kernel. @xref{Block Allocator}, for more information.
+
+@item interrupt.c
+@itemx interrupt.h
+Basic interrupt handling and functions for turning interrupts on and
+off. @xref{Interrupt Handling}, for more information.
+
+@item intr-stubs.S
+@itemx intr-stubs.h
+Assembly code for low-level interrupt handling. @xref{Interrupt
+Infrastructure}, for more information.
+
+@item synch.c
+@itemx synch.h
+Basic synchronization primitives: semaphores, locks, condition
+variables, and optimization barriers. You will need to use these for
+synchronization in all
+four projects. @xref{Synchronization}, for more information.
+
+@item io.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 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, ``EFLAGS
+Register,'' for more information.
+@end table
+
+@menu
+* devices code::
+* lib files::
+@end menu
+
+@node devices code
+@subsubsection @file{devices} code
+
+The basic threaded kernel also includes these files in the
+@file{devices} directory:
+
+@table @file
+@item timer.c
+@itemx timer.h
+System timer that ticks, by default, 100 times per second. You will
+modify this code in this project.
+
+@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. @func{printf}
+calls 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, @func{printf} calls this code for you,
+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
+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
+@subsubsection @file{lib} files
+
+Finally, @file{lib} and @file{lib/kernel} contain useful library
+routines. (@file{lib/user} will be used by user programs, starting in
+project 2, but it is not part of the kernel.) Here's a few more
+details:
+
+@table @file
+@item ctype.h
+@itemx inttypes.h
+@itemx limits.h
+@itemx stdarg.h
+@itemx stdbool.h
+@itemx stddef.h
+@itemx stdint.h
+@itemx stdio.c
+@itemx stdio.h
+@itemx stdlib.c
+@itemx stdlib.h
+@itemx string.c
+@itemx string.h
+A subset of the standard C library. @xref{C99}, for
+information
+on a few recently introduced pieces of the C library that you might
+not have encountered before. @xref{Unsafe String Functions}, for
+information on what's been intentionally left out for safety.
+
+@item debug.c
+@itemx debug.h
+Functions and macros to aid debugging. @xref{Debugging Tools}, for
+more information.
+
+@item random.c
+@itemx random.h
+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.
+
+@item syscall-nr.h
+System call numbers. Not used until project 2.
+
+@item kernel/list.c
+@itemx kernel/list.h
+Doubly linked list implementation. Used all over the Pintos code, and
+you'll probably want to use it a few places yourself in project 1.
+
+@item kernel/bitmap.c
+@itemx kernel/bitmap.h
+Bitmap implementation. You can use this in your code if you like, but
+you probably won't have any need for it in project 1.
+
+@item kernel/hash.c
+@itemx kernel/hash.h
+Hash table implementation. Likely to come in handy for project 3.
+
+@item kernel/console.c
+@itemx kernel/console.h
+@item kernel/stdio.h
+Implements @func{printf} and a few other functions.
+@end table
+
+@node Project 1 Synchronization
+@subsection Synchronization
+
+Proper synchronization is an important part of the solutions to these
+problems. Any synchronization problem can be easily solved by turning
+interrupts off: while interrupts are off, there is no concurrency, so
+there's no possibility for race conditions. Therefore, it's tempting to
+solve all synchronization problems this way, but @strong{don't}.
+Instead, use semaphores, locks, and condition variables to solve the
+bulk of your synchronization problems. Read the tour section on
+synchronization (@pxref{Synchronization}) or the comments in
+@file{threads/synch.c} if you're unsure what synchronization primitives
+may be used in what situations.
+
+In the Pintos projects, the only class of problem best solved by
+disabling interrupts is coordinating data shared between a kernel thread
+and an interrupt handler. Because interrupt handlers can't sleep, they
+can't acquire locks. This means that data shared between kernel threads
+and an interrupt handler must be protected within a kernel thread by
+turning off interrupts.
+
+This project only requires accessing a little bit of thread state from
+interrupt handlers. For the alarm clock, the timer interrupt needs to
+wake up sleeping threads. In the advanced scheduler, the timer
+interrupt needs to access a few global and per-thread variables. When
+you access these variables from kernel threads, you will need to disable
+interrupts to prevent the timer interrupt from interfering.
+
+When you do turn off interrupts, take care to do so for the least amount
+of code possible, or you can end up losing important things such as
+timer ticks or input events. Turning off interrupts also increases the
+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. (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.
+
+@node Development Suggestions
+@subsection Development Suggestions
+
+In the past, many groups divided the assignment into pieces, then each
+group member worked on his or her piece until just before the
+deadline, at which time the group reconvened to combine their code and
+submit. @strong{This is a bad idea. We do not recommend this
+approach.} Groups that do this often find that two changes conflict
+with each other, requiring lots of last-minute debugging. Some groups
+who have done this have turned in code that did not even compile or
+boot, much less pass any tests.
+
+@localcvspolicy{}
+
+You should expect to run into bugs that you simply don't understand
+while working on this and subsequent projects. When you do,
+reread the appendix on debugging tools, which is filled with
+useful debugging tips that should help you to get back up to speed
+(@pxref{Debugging Tools}). Be sure to read the section on backtraces
+(@pxref{Backtraces}), which will help you to get the most out of every
+kernel panic or assertion failure.
+
+@node Project 1 Requirements
+@section Requirements
+
+@menu
+* Project 1 Design Document::
+* Alarm Clock::
+* Priority Scheduling::
+* Advanced Scheduler::
+@end menu
+@node Project 1 Design Document
+@subsection Design Document
+
+Before you turn in your project, you must copy @uref{threads.tmpl, , the
+project 1 design document template} into your source tree under the name
+@file{pintos/src/threads/DESIGNDOC} and fill it in. We recommend that
+you read the design document template before you start working on the
+project. @xref{Project Documentation}, for a sample design document
+that goes along with a fictitious project.
+
+@node Alarm Clock
+@subsection Alarm Clock
+
+Reimplement @func{timer_sleep}, defined in @file{devices/timer.c}.
+Although a working implementation is provided, it ``busy waits,'' that
+is, it spins in a loop checking the current time and calling
+@func{thread_yield} until enough time has gone by. Reimplement it to
+avoid busy waiting.
+
+@deftypefun void timer_sleep (int64_t @var{ticks})
+Suspends execution of the calling thread until time has advanced by at
+least @w{@var{x} timer ticks}. Unless the system is otherwise idle, the
+thread need not wake up after exactly @var{x} ticks. Just put it on
+the ready queue after they have waited for the right amount of time.
+
+@func{timer_sleep} is useful for threads that operate in real-time,
+e.g.@: for blinking the cursor once per second.
+
+The argument to @func{timer_sleep} is expressed in timer ticks, not in
+milliseconds or any another unit. There are @code{TIMER_FREQ} timer
+ticks per second, where @code{TIMER_FREQ} is a macro defined in
+@code{devices/timer.h}. The default value is 100. We don't recommend
+changing this value, because any change is likely to cause many of
+the tests to fail.
+@end deftypefun
+
+Separate functions @func{timer_msleep}, @func{timer_usleep}, and
+@func{timer_nsleep} do exist for sleeping a specific number of
+milliseconds, microseconds, or nanoseconds, respectively, but these will
+call @func{timer_sleep} automatically when necessary. You do not need
+to modify them.
+
+If your delays seem too short or too long, reread the explanation of the
+@option{-r} option to @command{pintos} (@pxref{Debugging versus
+Testing}).
+
+The alarm clock implementation is not needed for later projects,
+although it could be useful for project 4.
+
+@node Priority Scheduling
+@subsection Priority Scheduling
+
+Implement priority scheduling in Pintos.
When a thread is added to the ready list that has a higher priority
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's
-priority may be set at any time, including while the thread is waiting
-on a lock, semaphore, or condition variable.
-
-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
-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
-``donate'' its priority to the low priority thread while it is holding
-the lock, then recall the donation once it has acquired the lock.
-Implement this fix.
-
-You will need to account for all different orders that priority
-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, and supposing H is waiting on a
-lock that M holds and M is waiting on a lock that L holds, both M and
-L should be boosted to 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
-implement this fix for semaphores, condition variables or joins.
-However, you do need to implement priority scheduling in all cases.
-
-@node Problem 1-4 Advanced Scheduler, Threads FAQ, Problem 1-3 Priority Scheduling, Project 1--Threads
-@section Problem 1-4 Advanced Scheduler
-
-Implement Solaris's multilevel feedback queue scheduler (MFQS), as
-explained below, to reduce the average response time for running jobs
-on your system.
-@c FIXME need link
-
-Demonstrate that your scheduling algorithm reduces response time
-relative to the original Pintos scheduling algorithm (round robin) for
-at least one workload of your own design (i.e. in addition to the
-provided test).
-
-You may assume a static priority for this problem. It is not necessary
-to ``re-donate'' a thread's priority if it changes (although you are
-free to do so).
-
-@node Threads FAQ, , Problem 1-4 Advanced Scheduler, Project 1--Threads
+threads are waiting for a lock, semaphore, or condition variable, the
+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 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
+defined in @file{threads/thread.h}, and you should not change their
+values.
+
+One issue with priority scheduling is ``priority inversion''. Consider
+high, medium, and low priority threads @var{H}, @var{M}, and @var{L},
+respectively. If @var{H} needs to wait for @var{L} (for instance, for a
+lock held by @var{L}), and @var{M} is on the ready list, then @var{H}
+will never get the CPU because the low priority thread will not get any
+CPU time. A partial fix for this problem is for @var{H} to ``donate''
+its priority to @var{L} while @var{L} is holding the lock, then recall
+the donation once @var{L} releases (and thus @var{H} acquires) the lock.
+
+Implement priority donation. You will need to account for all different
+situations in which priority donation is required. Be sure to handle
+multiple donations, in which multiple priorities are donated to a single
+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. If necessary, you may impose a reasonable limit on depth of
+nested priority donation, such as 8 levels.
+
+You must implement priority donation for locks. You need not
+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
+provided in @file{threads/thread.c}.
+
+@deftypefun void thread_set_priority (int @var{new_priority})
+Sets the current thread's priority to @var{new_priority}. If the
+current thread no longer has the highest priority, yields.
+@end deftypefun
+
+@deftypefun int thread_get_priority (void)
+Returns the current thread's priority. In the presence of priority
+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
+@subsection 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 detailed requirements.
+
+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 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{thread_mlfqs}, declared in @file{threads/thread.h}, to
+true when the options are parsed by @func{parse_options}, which happens
+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
+@func{thread_create} should be ignored, as well as any calls to
+@func{thread_set_priority}, and @func{thread_get_priority} should return
+the thread's current priority as set by the scheduler.
+
+The advanced scheduler is not used in any later project.
+
+@node Project 1 FAQ
@section FAQ
-@enumerate 1
-@item General FAQs
+@table @b
+@item How much code will I need to write?
-@enumerate 1
-@item
-@b{I am adding a new @file{.h} or @file{.c} file. How do I fix the
-@file{Makefile}s?}
+Here's a summary of our reference solution, produced by the
+@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 ++++++++++++++++++
+ threads/synch.c | 88 ++++++++++++-
+ threads/thread.c | 196 ++++++++++++++++++++++++++----
+ threads/thread.h | 23 +++
+ 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}
To add a @file{.c} file, edit the top-level @file{Makefile.build}.
-You'll want to add your file to variable @samp{@var{dir}_SRC}, where
+Add the new file to variable @samp{@var{dir}_SRC}, where
@var{dir} is the directory where you added the file. For this
-project, that means you should add it to @code{threads_SRC}, or
-possibly @code{devices_SRC} if you put in the @file{devices}
-directory. Then run @code{make}. If your new file doesn't get
+project, that means you should add it to @code{threads_SRC} or
+@code{devices_SRC}. Then run @code{make}. If your new file
+doesn't get
compiled, run @code{make clean} and then try again.
-There is no need to edit the @file{Makefile}s to add a @file{.h} file.
+When you modify the top-level @file{Makefile.build} and re-run
+@command{make}, the modified
+version should be automatically copied to
+@file{threads/build/Makefile}. The converse is
+not true, so any changes will be lost the next time you run @code{make
+clean} from the @file{threads} directory. Unless your changes are
+truly temporary, you should prefer to edit @file{Makefile.build}.
-@item
-@b{If a thread finishes, should its children be terminated immediately,
-or should they finish normally?}
+A new @file{.h} file does not require editing the @file{Makefile}s.
-You should feel free to decide what semantics you think this
-should have. You need only provide justification for your
-decision.
+@item What does @code{warning: no previous prototype for `@var{func}'} mean?
-@item
-@b{Why can't I disable interrupts?}
-
-Turning off interrupts should only be done for short amounts of time,
-or else you end up losing important things such as disk or input
-events. Turning off interrupts also increases the interrupt handling
-latency, which can make a machine feel sluggish if taken too far.
-Therefore, in general, setting the interrupt level should be used
-sparingly. Also, any synchronization problem can be easily solved by
-turning interrupts off, since while interrupts are off, there is no
-concurrency, so there's no possibility for race condition.
-
-To make sure you understand concurrency well, we are discouraging you
-from taking this shortcut at all in your solution. If you are unable
-to solve a particular synchronization problem with semaphores, locks,
-or conditions, or think that they are inadequate for a particular
-reason, you may turn to disabling interrupts. If you want to do this,
-we require in your design document a complete justification and
-scenario (i.e.@: exact sequence of events) to show why interrupt
-manipulation is the best solution. If you are unsure, the TAs can
-help you determine if you are using interrupts too haphazardly. We
-want to emphasize that there are only limited cases where this is
-appropriate.
+It means that you defined a non-@code{static} function without
+preceding it by a prototype. Because non-@code{static} functions are
+intended for use by other @file{.c} files, for safety they should be
+prototyped in a header file included before their definition. To fix
+the problem, add a prototype in a header file that you include, or, if
+the function isn't actually used by other @file{.c} files, make it
+@code{static}.
-@item
-@b{Where might interrupt-level manipuation be appropriate?}
+@item What is the interval between timer interrupts?
-You might find it necessary in some solutions to the Alarm problem.
+Timer interrupts occur @code{TIMER_FREQ} times per second. You can
+adjust this value by editing @file{devices/timer.h}. The default is
+100 Hz.
-You might want it at one small point for the priority scheduling
-problem. Note that it is not required to use interrupts for these
-problems. There are other, equally correct solutions that do not
-require interrupt manipulation. However, if you do manipulate
-interrupts and @strong{correctly and fully document it} in your design
-document, we will allow limited use of interrupt disabling.
-@end enumerate
+We don't recommend changing this value, because any changes are likely
+to cause many of the tests to fail.
-@item Alarm Clock FAQs
+@item How long is a time slice?
-@enumerate 1
-@item
-@b{Why can't I use most synchronization primitives in an interrupt
-handler?}
+There are @code{TIME_SLICE} ticks per time slice. This macro is
+declared in @file{threads/thread.c}. The default is 4 ticks.
-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.
+We don't recommend changing this value, because any changes are likely
+to cause many of the tests to fail.
-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
-about:
+@item How do I run the tests?
-@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()}.
+@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{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
+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
-A thread in @code{timer_sleep()}, however, can be interrupted by a
-call to @code{timer_interrupt()}, except when that thread has turned
-off interrupts.
+@func{thread_exit}, but we'll never switch back into such a thread, so
+it's uninteresting.
@item
-Examples of synchronization mechanisms have been presented in lecture.
-Going over these examples should help you understand when each type is
-useful or needed.
-@end enumerate
+@func{thread_yield}, which immediately restores the interrupt level upon
+return from @func{schedule}.
@item
-@b{What about timer overflow due to the fact that times are defined as
-integers? Do I need to check for that?}
+@func{thread_block}, which is called from multiple places:
-Don't worry about the possibility of timer values overflowing. Timer
-values are expressed as signed 63-bit numbers, which at 100 ticks per
-second should be good for almost 2,924,712,087 years.
-@end enumerate
+@itemize @minus
+@item
+@func{sema_down}, which restores the interrupt level before returning.
-@item Join FAQs
+@item
+@func{idle}, which enables interrupts with an explicit assembly STI
+instruction.
-@enumerate 1
@item
-@b{Am I correct to assume that once a thread is deleted, it is no
-longer accessible by the parent (i.e.@: the parent can't call
-@code{thread_join(child)})?}
+@func{wait} in @file{devices/intq.c}, whose callers are responsible for
+re-enabling interrupts.
+@end itemize
+@end itemize
-A parent joining a child that has completed should be handled
-gracefully and should act as a no-op.
-@end enumerate
+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
-@item Priority Scheduling FAQs
+@menu
+* Alarm Clock FAQ::
+* Priority Scheduling FAQ::
+* Advanced Scheduler FAQ::
+@end menu
-@enumerate 1
-@item
-@b{Doesn't the priority scheduling lead to starvation? Or do I have to
-implement some sort of aging?}
+@node Alarm Clock FAQ
+@subsection Alarm Clock FAQ
+
+@table @b
+@item Do I need to account for timer values overflowing?
+
+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 @value{coursenumber} curriculum.
+@end table
+@node Priority Scheduling FAQ
+@subsection Priority Scheduling FAQ
-It is true that strict priority scheduling can lead to starvation
-because thread may not run if a higher-priority thread is runnable.
-In this problem, don't worry about starvation or any sort of aging
-technique. Problem 4 will introduce a mechanism for dynamically
+@table @b
+@item Doesn't priority scheduling lead to starvation?
+
+Yes, strict priority scheduling can lead to starvation
+because a thread will not run if any higher-priority thread is runnable.
+The advanced scheduler introduces a mechanism for dynamically
changing thread priorities.
-This sort of scheduling is valuable in real-time systems because it
+Strict priority scheduling is valuable in real-time systems because it
offers the programmer more control over which jobs get processing
time. High priorities are generally reserved for time-critical
tasks. It's not ``fair,'' but it addresses other concerns not
applicable to a general-purpose operating system.
-@item
-@b{After a lock has been released, does the program need to switch to
-the highest priority thread that needs the lock (assuming that its
-priority is higher than that of the current thread)?}
+@item What thread should run after a lock has been released?
When a lock is released, the highest priority thread waiting for that
-lock should be unblocked and put on the ready to run list. The
+lock should be unblocked and put on the list of ready threads. The
scheduler should then run the highest priority thread on the ready
list.
-@item
-@b{If a thread calls @code{thread_yield()} and then it turns out that
-it has higher priority than any other threads, does the high-priority
-thread continue running?}
+@item If the highest-priority thread yields, does it 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}.
+If multiple threads have the same highest priority,
+@func{thread_yield} should switch among them in ``round robin'' order.
-@item
-@b{If the highest priority thread is added to the ready to run list it
-should start execution immediately. Is it immediate enough if I
-wait until next timer interrupt occurs?}
+@item What happens to the priority of a donating thread?
-The highest priority thread should run as soon as it is runnable,
-preempting whatever thread is currently running.
+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 5) donates
+to thread @var{B} (with priority 3), then @var{B}'s new priority is 5, not 8.
-@item
-@b{What happens to the priority of the donating thread? Do the priorities
-get swapped?}
+@item Can a thread's priority change while it is on the ready queue?
-No. Priority donation only changes the priority of the low-priority
-thread. The donating thread's priority stays unchanged. Also note
-that priorities aren't additive: if thread A (with priority 5) donates
-to thread B (with priority 3), then B's new priority is 5, not 8.
+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
-@b{Can a thread's priority be changed while it is sitting on the ready
-queue?}
+@item Can a thread's priority change while it is blocked?
-Yes. Consider this case: low-priority thread L currently has a lock
-that high-priority thread H wants. H donates its priority to L (the
-lock holder). L finishes with the lock, and then loses the CPU and is
-moved to the ready queue. Now L's old priority is restored while it
-is in the ready queue.
+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
-@b{Can a thread's priority change while it is sitting on the queue of a
-semaphore?}
+@item Can a thread added to the ready list preempt the processor?
-Yes. Same scenario as above except L gets blocked waiting on a new
-lock when H restores its priority.
+Yes. If a thread added to the ready list has higher priority than the
+running thread, the correct behavior is to immediately yield the
+processor. It is not acceptable to wait for the next timer interrupt.
+The highest priority thread should run as soon as it is runnable,
+preempting whatever thread is currently running.
-@item
-@b{Why is pubtest3's FIFO test skipping some threads! I know my scheduler
-is round-robin'ing them like it's supposed to! Our output is like this:}
+@item How does @func{thread_set_priority} affect a thread receiving donations?
-@example
-Thread 0 goes.
-Thread 2 goes.
-Thread 3 goes.
-Thread 4 goes.
-Thread 0 goes.
-Thread 1 goes.
-Thread 2 goes.
-Thread 3 goes.
-Thread 4 goes.
-@end example
+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 Doubled test names in output make them fail.
-@noindent @b{which repeats 5 times and then}
+Suppose you are seeing output in which some test names are doubled,
+like this:
@example
-Thread 1 goes.
-Thread 1 goes.
-Thread 1 goes.
-Thread 1 goes.
-Thread 1 goes.
+(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
-This happens because context switches are being invoked by the test
-when it explicitly calls @code{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
-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
-completely.
+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.
-Solution: Increase the value of @code{TIME_SLICE} in
-@file{devices/timer.c} to a very high value, such as 10000, to see
-that the threads will round-robin if they aren't interrupted.
+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.
-@item
-@b{What happens when a thread is added to the ready list which has
-higher priority than the currently running thread?}
+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
-The correct behavior is to immediately yield the processor. Your
-solution must act this way.
+@node Advanced Scheduler FAQ
+@subsection Advanced Scheduler FAQ
-@item
-@b{What range of priorities should be supported and what should the
-default priority of a thread be?}
+@table @b
+@item How does priority donation interact with the advanced scheduler?
-Your implementation should support priorities from 0 through 59 and
-the default priority of a thread should be 29.
-@end enumerate
+It doesn't have to. We won't test priority donation and the advanced
+scheduler at the same time.
-@item Advanced Scheduler FAQs
+@item Can I use one queue instead of 64 queues?
-@enumerate 1
-@item
-@b{What is the interval between timer interrupts?}
+Yes. In general, your implementation may differ from the description,
+as long as its behavior is the same.
-Timer interrupts occur @code{TIMER_FREQ} times per second. You can
-adjust this value by editing @file{devices/timer.h}. The default is
-100 Hz.
-
-@item
-@b{Do I have to modify the dispatch table?}
+@item Some scheduler tests fail and I don't understand why. Help!
-No, although you are allowed to. It is possible to complete
-this problem (i.e.@: demonstrate response time improvement)
-without doing so.
+If your implementation mysteriously fails some of the advanced
+scheduler tests, try the following:
+@itemize
@item
-@b{When the scheduler changes the priority of a thread, how does this
-affect priority donation?}
-
-Short (official) answer: Don't worry about it. Your priority donation
-code may assume static priority assignment.
-
-Longer (unofficial) opinion: If you wish to take this into account,
-however, your design may end up being ``cleaner.'' You have
-considerable freedom in what actually takes place. I believe what
-makes the most sense is for scheduler changes to affect the
-``original'' (non-donated) priority. This change may actually be
-masked by the donated priority. Priority changes should only
-propagate with donations, not ``backwards'' from donees to donors.
+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
-@b{What is meant by ``static priority''?}
-
-Once thread A has donated its priority to thread B, if thread A's
-priority changes (due to the scheduler) while the donation still
-exists, you do not have to change thread B's donated priority.
-However, you are free to do so.
+Double-check your fixed-point arithmetic routines and your use of them
+in the scheduler routines.
@item
-@b{Do I have to make my dispatch table user-configurable?}
-
-No. Hard-coding the dispatch table values is fine.
-@end enumerate
-@end enumerate
+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