X-Git-Url: https://pintos-os.org/cgi-bin/gitweb.cgi?p=pintos-anon;a=blobdiff_plain;f=doc%2Fthreads.texi;h=d90b43895396a0ec81c3ff9c4ae91515572522ac;hp=c1fcfff02e7f5495c4201198b847bb75c9f4d4ac;hb=f1f2dc8de9e336d83383692d4478bb14a3dafc11;hpb=98c2fc1ab7d395bb92cf4a57233fe432539d26a9 diff --git a/doc/threads.texi b/doc/threads.texi index c1fcfff..d90b438 100644 --- a/doc/threads.texi +++ b/doc/threads.texi @@ -1,584 +1,856 @@ -@node Project 1--Threads, Project 2--User Programs, Introduction, 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:: -* Multilevel Feedback Scheduling:: +* Project 1 Source Files:: +* Project 1 Synchronization:: +* Development Suggestions:: @end menu @node Understanding Threads -@section 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 read through the source code by hand to see what's -going on. If you like, you can add calls to @code{printf()} almost +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. +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{threads/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 -@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 -@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 MLFQS) 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 -@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 -@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 -@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 -@section Problem 1-4 Advanced Scheduler - -Implement Solaris's multilevel feedback queue scheduler (MLFQS) to +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{Multilevel Feedback Scheduling}, for a detailed description of -the MLFQS requirements. +@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 -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). +@table @b +@item How much code will I need to write? -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). +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. -@node Threads FAQ, Multilevel Feedback Scheduling, Problem 1-4 Advanced Scheduler, Project 1--Threads -@section FAQ +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. -@enumerate 1 -@item General FAQs +@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 -@enumerate 1 -@item -@b{I am adding a new @file{.h} or @file{.c} file. How do I fix the -@file{Makefile}s?}@anchor{Adding c or h Files} +@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. -When you modify the top-level @file{Makefile.build}, the modified +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} when you re-run make. The opposite is +@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. Therefore, you should -prefer to edit @file{Makefile.build} (unless your changes are meant to -be truly temporary). +clean} from the @file{threads} directory. Unless your changes are +truly temporary, you should prefer to edit @file{Makefile.build}. -There is no need to edit the @file{Makefile}s to add a @file{.h} file. +A new @file{.h} file does not require editing the @file{Makefile}s. -@item -@b{If a thread finishes, should its children be terminated immediately, -or should they finish normally?} +@item What does @code{warning: no previous prototype for `@var{func}'} mean? -You should feel free to decide what semantics you think this -should have. You need only provide justification for your -decision. +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{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. +@item What is the interval between timer interrupts? -@item -@b{Where might interrupt-level manipuation be appropriate?} +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 find it necessary in some solutions to the Alarm problem. +We don't recommend changing this value, because any changes are likely +to cause many of the tests to fail. -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 +@item How long is a time slice? -@item Alarm Clock FAQs +There are @code{TIME_SLICE} ticks per time slice. This macro is +declared in @file{threads/thread.c}. The default is 4 ticks. -@enumerate 1 -@item -@b{Why can't I use most synchronization primitives in an interrupt -handler?} +We don't recommend changing this value, because any changes are likely +to cause many of the tests to fail. -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. +@item How do I run the tests? -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: +@xref{Testing}. -@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()}. +@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 +@table @b +@item Doesn't priority scheduling lead to starvation? -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 +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. 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. -Yes. Same scenario as above except L gets blocked waiting on a new -lock when H restores its priority. +@item How does @func{thread_set_priority} affect a thread receiving donations? -@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:} +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. -@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 +@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