X-Git-Url: https://pintos-os.org/cgi-bin/gitweb.cgi?a=blobdiff_plain;f=doc%2Fthreads.texi;h=fbd8ac33e5c751add91b795952ffeb308fc46a79;hb=7a48d9a0ac4176681da03e878061b0c59e5bade4;hp=7a048e7e8af35a8332e9d2bc4cd8d7b554b3cd5a;hpb=40140f51bb6c6bf0191145497a5db115083fe3af;p=pintos-anon diff --git a/doc/threads.texi b/doc/threads.texi index 7a048e7..fbd8ac3 100644 --- a/doc/threads.texi +++ b/doc/threads.texi @@ -13,6 +13,7 @@ side. Compilation should be done in the @file{threads} directory. @menu * Understanding Threads:: +* Project 1 Code:: * Debugging versus Testing:: * Tips:: * Problem 1-1 Alarm Clock:: @@ -20,7 +21,6 @@ side. Compilation should be done in the @file{threads} directory. * Problem 1-3 Priority Scheduling:: * Problem 1-4 Advanced Scheduler:: * Threads FAQ:: -* Multilevel Feedback Scheduling:: @end menu @node Understanding Threads @@ -30,13 +30,16 @@ The first step is to read and understand the initial thread system. Pintos, by default, 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 + +However, there's a lot of magic going on in some of this code, so 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 by hand to see what's going +on. If you like, you can add calls to @code{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. @xref{i386-elf-gdb}, for more information. 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 @@ -59,16 +62,19 @@ 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 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 + +Using the @command{gdb} debugger, slowly trace through a context +switch to see what happens (@pxref{i386-elf-gdb}). You can set a +breakpoint on the @code{schedule()} function to start out, and then +single-step from there. 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. +@code{switch_threads()} that returns. @c FIXME @strong{Warning}: In Pintos, each thread is assigned a small, fixed-size execution stack just under @w{4 kB} in size. The kernel @@ -82,6 +88,94 @@ in @file{threads/malloc.c}. Note that the page allocator doles out limit. If you need larger chunks, consider using a linked structure instead. +@node Project 1 Code +@section Code + +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. 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. 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 @code{main()}. + +@item init.c +@itemx init.h +Kernel initialization, including @code{main()}, the kernel's ``main +program.'' You should look over @code{main()} at least to see what +gets initialized. + +@item thread.c +@itemx thread.h +Basic thread support. Much of your work will take place in these +files. @file{thread.h} defines @code{struct thread}, which you will +modify in the first three projects. + +@item switch.S +@itemx switch.h +Assembly language routine for switching threads. Already discussed +above. + +@item palloc.c +@itemx palloc.h +Page allocator, which hands out system memory one 4 kB page at a time. + +@item paging.c +@itemx paging.h +Initializes the kernel page table. FIXME + +@item malloc.c +@itemx malloc.h +A very simple implementation of @code{malloc()} and @code{free()} for +the kernel. The largest block that can be allocated is 2 kB. + +@item interrupt.c +@itemx interrupt.h +Basic interrupt handling and functions for turning interrupts on and +off. + +@item intr-stubs.pl +@itemx intr-stubs.h +A Perl program that outputs assembly for low-level interrupt handling. + +@item synch.c +@itemx synch.h +Basic synchronization primitives: semaphores, locks, and condition +variables. You will need to use these for synchronization through all +four projects. + +@item test.c +@itemx test.h +Test code. For project 1, you will replace this file with your test +cases. + +@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 mmu.h +Functions and macros related to memory management, including page +directories and page tables. This will be more important to you in +project 3. For now, you can ignore it. +@end table + +FIXME devices and lib directories? + @node Debugging versus Testing @section Debugging versus Testing @@ -111,6 +205,7 @@ 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. +FIXME 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 @@ -140,24 +235,25 @@ 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 +full credit on this project, keep in mind that Problem 1-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 +code for the whole quarter. Problem 1-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. +implementation of @code{thread_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 +Also keep in mind that Problem 1-4 (the MLFQS) builds on the features you +implement in Problem 1-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. +such that you have Problem 1-3 fully working before you begin to tackle +Problem 1-4. @node Problem 1-1 Alarm Clock -@section Problem 1-2: Alarm Clock +@section Problem 1-1: Alarm Clock Improve the implementation of the timer device defined in @file{devices/timer.c} by reimplementing @code{timer_sleep()}. @@ -182,18 +278,30 @@ 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. +Implement @code{thread_join(tid_t)} 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 the thread whose thread id is 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. + +Incidentally, we don't use @code{struct thread *} as +@file{thread_join()}'s parameter type because a thread pointer is not +unique over time. That is, when a thread dies, its memory may be, +whether immediately or much later, reused for another thread. If +thread A over time had two children B and C that were stored at the +same address, then @code{thread_join(@r{B})} and +@code{thread_join(@r{C})} would be ambiguous. Introducing a thread id +or @dfn{tid}, represented by type @code{tid_t}, that is intentionally +unique over time solves the problem. The provided code uses an +@code{int} for @code{tid_t}, but you may decide you prefer to use some +other type. 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. +That is, a thread may only join 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}, @@ -206,9 +314,8 @@ 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. +Calling @code{thread_join()} on an thread that is not the caller's +child should cause the caller to return immediately. 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 @@ -221,15 +328,23 @@ 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}, +@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 the running thread +and @code{thread_get_priority()} to get the running thread's priority. +(A thread can examine and modify only its own priority.) There are +already prototypes for these functions in @file{threads/thread.h}, which you should not change. +Thread priority ranges from @code{PRI_MIN} (0) to @code{PRI_MAX} (59). +The initial thread priority is passed as an argument to +@code{thread_create()}. If there's no reason to choose another +priority, use @code{PRI_DEFAULT} (29). The @code{PRI_} macros are +defined in @file{threads/thread.h}, and you should not change their +values. + 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 @@ -253,17 +368,17 @@ 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. +threads H, M, and L, respectively, if H is waiting on a lock that M +holds and M is waiting on a lock that L holds, then 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 +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 +@section Problem 1-4: Advanced Scheduler Implement Solaris's multilevel feedback queue scheduler (MLFQS) to reduce the average response time for running jobs on your system. @@ -272,14 +387,19 @@ the MLFQS requirements. 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 +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, Multilevel Feedback Scheduling, Problem 1-4 Advanced Scheduler, Project 1--Threads +You must write your code so that we can turn the MLFQS on and off at +compile time. By default, it must be off, but we must be able to turn +it on by inserting the line @code{#define MLFQS 1} in +@file{constants.h}. @xref{Conditional Compilation}, for details. + +@node Threads FAQ @section FAQ @enumerate 1 @@ -308,6 +428,13 @@ be truly temporary). There is no need to edit the @file{Makefile}s to add a @file{.h} file. +@item +@b{How do I write my test cases?} + +Test cases should be replacements for the existing @file{test.c} +file. Put them in a @file{threads/testcases} directory. +@xref{TESTCASE}, for more information. + @item @b{If a thread finishes, should its children be terminated immediately, or should they finish normally?} @@ -340,8 +467,11 @@ help you determine if you are using interrupts too haphazardly. We want to emphasize that there are only limited cases where this is appropriate. +You might find @file{devices/intq.h} and its users to be an +inspiration or source of rationale. + @item -@b{Where might interrupt-level manipuation be appropriate?} +@b{Where might interrupt-level manipulation be appropriate?} You might find it necessary in some solutions to the Alarm problem. @@ -415,7 +545,6 @@ gracefully and should act as a no-op. @b{Doesn't the priority scheduling lead to starvation? Or do I have to implement some sort of aging?} - 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 @@ -529,11 +658,10 @@ The correct behavior is to immediately yield the processor. Your solution must act this way. @item -@b{What range of priorities should be supported and what should the -default priority of a thread be?} +@b{What should @code{thread_get_priority()} return in a thread while +its priority has been increased by a donation?} -Your implementation should support priorities from 0 through 59 and -the default priority of a thread should be 29. +The higher (donated) priority. @end enumerate @item Advanced Scheduler FAQs @@ -546,6 +674,9 @@ 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 can also adjust the number of timer ticks per time slice by +modifying @code{TIME_SLICE} in @file{devices/timer.c}. + @item @b{Do I have to modify the dispatch table?} @@ -582,5 +713,3 @@ However, you are free to do so. No. Hard-coding the dispatch table values is fine. @end enumerate @end enumerate - -@include mlfqs.texi