X-Git-Url: https://pintos-os.org/cgi-bin/gitweb.cgi?a=blobdiff_plain;f=doc%2Fthreads.texi;h=706f76b7f035e5b7c0e17755dc5c7750aed4d34d;hb=4dbef14e57eebfd86079fcc2185adc33e72e2d8b;hp=0bc1534eb9c207e8166da68c8da37d2bc288a405;hpb=f2ee772aec0cf12c132cdc3cbcfe36e4382335af;p=pintos-anon diff --git a/doc/threads.texi b/doc/threads.texi index 0bc1534..706f76b 100644 --- a/doc/threads.texi +++ b/doc/threads.texi @@ -1,4 +1,4 @@ -@node Project 1--Threads, Project 2--User Programs, Pintos Tour, Top +@node Project 1--Threads @chapter Project 1: Threads In this assignment, we give you a minimally functional thread system. @@ -12,9 +12,9 @@ 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 in @ref{Threads Tour} and especially -@ref{Synchronization}. To complete this project you will also need to -read @ref{4.4BSD Scheduler}. +skim the material from @ref{Pintos Loading} through @ref{Memory +Allocation}, especially @ref{Synchronization}. To complete this project +you will also need to read @ref{4.4BSD Scheduler}. @menu * Project 1 Background:: @@ -76,11 +76,11 @@ 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. -Using the @command{gdb} debugger, slowly trace through a context -switch to see what happens (@pxref{gdb}). You can set a +Using the GDB debugger, slowly trace through a context +switch to see what happens (@pxref{GDB}). You can set a breakpoint on @func{schedule} to start out, and then -single-step from there.@footnote{@command{gdb} might tell you that -@func{schedule} doesn't exist, which is arguably a @command{gdb} bug. +single-step from there.@footnote{GDB might tell you that +@func{schedule} doesn't exist, which is arguably a GDB bug. You can work around this by setting the breakpoint by filename and line number, e.g.@: @code{break thread.c:@var{ln}} where @var{ln} is the line number of the first declaration in @func{schedule}.} Be sure @@ -137,10 +137,10 @@ 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{Thread -Support} for more information. +Basic thread support. Much of your work will take place in these files. +@file{thread.h} defines @struct{thread}, which you are likely to modify +in all four projects. See @ref{struct thread} and @ref{Threads} for +more information. @item switch.S @itemx switch.h @@ -178,15 +178,16 @@ four projects. @xref{Synchronization}, for more information. Functions for I/O port access. This is mostly used by source code in the @file{devices} directory that you won't have to touch. -@item mmu.h -Functions and macros related to memory management, including page -directories and page tables. This will be more important to you in -project 3. For now, you can ignore it. +@item vaddr.h +@itemx pte.h +Functions and macros for working with virtual addresses and page table +entries. These will be more important to you in project 3. For now, +you can ignore them. @item flags.h Macros that define a few bits in the 80@var{x}86 ``flags'' register. -Probably of no interest. See @bibref{IA32-v1}, section 3.4.3, for more -information. +Probably of no interest. See @bibref{IA32-v1}, section 3.4.3, ``EFLAGS +Register,'' for more information. @end table @menu @@ -216,14 +217,24 @@ 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. Feel free to look through it if -you're curious. +so you don't need to do so yourself. +It handles serial input by passing it to the input layer (see below). @item disk.c @itemx disk.h Supports reading and writing sectors on up to 4 IDE disks. This won't actually be used until project 2. +@item kbd.c +@itemx kbd.h +Keyboard driver. Handles keystrokes passing them to the input layer +(see below). + +@item input.c +@itemx input.h +Input layer. Queues input characters passed along by the keyboard or +serial drivers. + @item intq.c @itemx intq.h Interrupt queue, for managing a circular queue that both kernel @@ -328,9 +339,10 @@ 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. -You may need to add or modify code where interrupts are already -disabled, such as in @func{sema_up} or @func{sema_down}. You should -still try to keep this code as short as you can. +The synchronization primitives themselves in @file{synch.c} are +implemented by disabling interrupts. You may need to increase the +amount of code that runs with interrupts disabled here, but you should +still try to keep it to a minimum. Disabling interrupts can be useful for debugging, if you want to make sure that a section of code is not interrupted. You should remove @@ -441,8 +453,8 @@ priority such that it no longer has the highest priority must cause it to immediately yield the CPU. Thread priorities range from @code{PRI_MIN} (0) to @code{PRI_MAX} (63). -Lower numbers correspond to @emph{higher} priorities, so that priority 0 -is the highest priority and priority 63 is the lowest. +Lower numbers correspond to lower priorities, so that priority 0 +is the lowest priority and priority 63 is the highest. The initial thread priority is passed as an argument to @func{thread_create}. If there's no reason to choose another priority, use @code{PRI_DEFAULT} (31). The @code{PRI_} macros are @@ -511,7 +523,8 @@ 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{enable_mlfqs}, declared in @file{threads/init.h}, to -true. +true when the options are parsed by @func{parse_options}, which happens +midway through @func{main}. When the 4.4@acronym{BSD} scheduler is enabled, threads no longer directly control their own priorities. The @var{priority} argument to @@ -531,6 +544,12 @@ 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 ++++++++++++++++++ @@ -540,6 +559,8 @@ and deleted; a changed line counts as both an insertion and a deletion. 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} @@ -598,13 +619,13 @@ to cause many of the tests to fail. You are probably looking at a backtrace that looks something like this: @example -0xc0108810: debug_panic (../../lib/kernel/debug.c:32) -0xc010a99f: pass (../../tests/threads/tests.c:93) -0xc010bdd3: test_mlfqs_load_1 (../../tests/threads/mlfqs-load-1.c:33) -0xc010a8cf: run_test (../../tests/threads/tests.c:51) -0xc0100452: run_task (../../threads/init.c:283) -0xc0100536: run_actions (../../threads/init.c:333) -0xc01000bb: main (../../threads/init.c:137) +0xc0108810: debug_panic (lib/kernel/debug.c:32) +0xc010a99f: pass (tests/threads/tests.c:93) +0xc010bdd3: test_mlfqs_load_1 (...threads/mlfqs-load-1.c:33) +0xc010a8cf: run_test (tests/threads/tests.c:51) +0xc0100452: run_task (threads/init.c:283) +0xc0100536: run_actions (threads/init.c:333) +0xc01000bb: main (threads/init.c:137) @end example This is just confusing output from the @command{backtrace} program. It @@ -665,7 +686,7 @@ list. @item If the highest-priority thread yields, does it continue running? -Yes. As long as there is a single highest-priority thread, it continues +Yes. If there is a single highest-priority thread, it continues running until it blocks or finishes, even if it calls @func{thread_yield}. If multiple threads have the same highest priority, @@ -686,6 +707,13 @@ priority to @var{L}. @var{L} releases the lock and thus loses the CPU and is moved to the ready queue. Now @var{L}'s old priority is restored while it is in the ready queue. +@item Can a thread's priority change while it is blocked? + +Yes. While a thread that has acquired lock @var{L} is blocked for any +reason, its priority can increase by priority donation if a +higher-priority thread attempts to acquire @var{L}. This case is +checked by the @code{priority-donate-sema} test. + @item Can a thread added to the ready list preempt the processor? Yes. If a thread added to the ready list has higher priority than the @@ -696,9 +724,11 @@ preempting whatever thread is currently running. @item How does @func{thread_set_priority} affect a thread receiving donations? -It should do something sensible, but no particular behavior is -required. None of the test cases call @func{thread_set_priority} from a -thread while it is receiving a priority donation. +It sets the thread's base priority. The thread's effective priority +becomes the higher of the newly set priority or the highest donated +priority. When the donations are released, the thread's priority +becomes the one set through the function call. This behavior is checked +by the @code{priority-donate-lower} test. @item Calling @func{printf} in @func{sema_up} or @func{sema_down} reboots! @@ -720,7 +750,6 @@ scheduler at the same time. @item Can I use one queue instead of 64 queues? -Yes, that's fine. It's easiest to describe the algorithm in terms of 64 -separate queues, but that may not be the best implementation. If you -use a single queue, it should probably be sorted. +Yes. In general, your implementation may differ from the description, +as long as its behavior is the same. @end table