Add test that compiles the examples.
[pintos-anon] / doc / threads.texi
1 @node Project 1--Threads
2 @chapter Project 1: Threads
3
4 In this assignment, we give you a minimally functional thread system.
5 Your job is to extend the functionality of this system to gain a
6 better understanding of synchronization problems.
7
8 You will be working primarily in the @file{threads} directory for
9 this assignment, with some work in the @file{devices} directory on the
10 side.  Compilation should be done in the @file{threads} directory.
11
12 Before you read the description of this project, you should read all of
13 the following sections: @ref{Introduction}, @ref{Coding Standards},
14 @ref{Debugging Tools}, and @ref{Development Tools}.  You should at least
15 skim the material from @ref{Pintos Loading} through @ref{Memory
16 Allocation}, especially @ref{Synchronization}.  To complete this project
17 you will also need to read @ref{4.4BSD Scheduler}.
18
19 @menu
20 * Project 1 Background::        
21 * Project 1 Requirements::      
22 * Project 1 FAQ::               
23 @end menu
24
25 @node Project 1 Background
26 @section Background
27
28
29 @menu
30 * Understanding Threads::       
31 * Project 1 Source Files::      
32 * Project 1 Synchronization::   
33 * Development Suggestions::     
34 @end menu
35
36 @node Understanding Threads
37 @subsection Understanding Threads
38
39 The first step is to read and understand the code for the initial thread
40 system.
41 Pintos already implements thread creation and thread completion,
42 a simple scheduler to switch between threads, and synchronization
43 primitives (semaphores, locks, condition variables, and memory
44 barriers).
45
46 Some of this code might seem slightly mysterious.  If
47 you haven't already compiled and run the base system, as described in
48 the introduction (@pxref{Introduction}), you should do so now.  You
49 can read through parts of the source code to see what's going
50 on.  If you like, you can add calls to @func{printf} almost
51 anywhere, then recompile and run to see what happens and in what
52 order.  You can also run the kernel in a debugger and set breakpoints
53 at interesting spots, single-step through code and examine data, and
54 so on.
55
56 When a thread is created, you are creating a new context to be
57 scheduled.  You provide a function to be run in this context as an
58 argument to @func{thread_create}.  The first time the thread is
59 scheduled and runs, it starts from the beginning of that function
60 and executes in that context.  When the function returns, the thread
61 terminates.  Each thread, therefore, acts like a mini-program running
62 inside Pintos, with the function passed to @func{thread_create}
63 acting like @func{main}.
64
65 At any given time, exactly one thread runs and the rest, if any,
66 become inactive.  The scheduler decides which thread to
67 run next.  (If no thread is ready to run
68 at any given time, then the special ``idle'' thread, implemented in
69 @func{idle}, runs.)
70 Synchronization primitives can force context switches when one
71 thread needs to wait for another thread to do something.
72
73 The mechanics of a context switch are
74 in @file{threads/switch.S}, which is 80@var{x}86
75 assembly code.  (You don't have to understand it.)  It saves the
76 state of the currently running thread and restores the state of the
77 thread we're switching to.
78
79 Using the GDB debugger, slowly trace through a context
80 switch to see what happens (@pxref{GDB}).  You can set a
81 breakpoint on @func{schedule} to start out, and then
82 single-step from there.@footnote{GDB might tell you that
83 @func{schedule} doesn't exist, which is arguably a GDB bug.
84 You can work around this by setting the breakpoint by filename and
85 line number, e.g.@: @code{break thread.c:@var{ln}} where @var{ln} is
86 the line number of the first declaration in @func{schedule}.}  Be sure
87 to keep track of each thread's address
88 and state, and what procedures are on the call stack for each thread.
89 You will notice that when one thread calls @func{switch_threads},
90 another thread starts running, and the first thing the new thread does
91 is to return from @func{switch_threads}.  You will understand the thread
92 system once you understand why and how the @func{switch_threads} that
93 gets called is different from the @func{switch_threads} that returns.
94 @xref{Thread Switching}, for more information.
95
96 @strong{Warning}: In Pintos, each thread is assigned a small,
97 fixed-size execution stack just under @w{4 kB} in size.  The kernel
98 tries to detect stack overflow, but it cannot do so perfectly.  You
99 may cause bizarre problems, such as mysterious kernel panics, if you
100 declare large data structures as non-static local variables,
101 e.g. @samp{int buf[1000];}.  Alternatives to stack allocation include
102 the page allocator and the block allocator (@pxref{Memory Allocation}).
103
104 @node Project 1 Source Files
105 @subsection Source Files
106
107 Here is a brief overview of the files in the @file{threads}
108 directory.  You will not need to modify most of this code, but the
109 hope is that presenting this overview will give you a start on what
110 code to look at.
111
112 @table @file
113 @item loader.S
114 @itemx loader.h
115 The kernel loader.  Assembles to 512 bytes of code and data that the
116 PC BIOS loads into memory and which in turn loads the kernel into
117 memory, does basic processor initialization, and jumps to the
118 beginning of the kernel.  @xref{Pintos Loader}, for details. You should
119 not need to look at this code or modify it.
120
121 @item kernel.lds.S
122 The linker script used to link the kernel.  Sets the load address of
123 the kernel and arranges for @file{start.S} to be at the very beginning
124 of the kernel image.  @xref{Pintos Loader}, for details. Again, you
125 should not need to look at this code
126 or modify it, but it's here in case you're curious.
127
128 @item start.S
129 Jumps to @func{main}.
130
131 @item init.c
132 @itemx init.h
133 Kernel initialization, including @func{main}, the kernel's ``main
134 program.''  You should look over @func{main} at least to see what
135 gets initialized.  You might want to add your own initialization code
136 here.  @xref{Kernel Initialization}, for details.
137
138 @item thread.c
139 @itemx thread.h
140 Basic thread support.  Much of your work will take place in these files.
141 @file{thread.h} defines @struct{thread}, which you are likely to modify
142 in all four projects.  See @ref{struct thread} and @ref{Threads} for
143 more information.
144
145 @item switch.S
146 @itemx switch.h
147 Assembly language routine for switching threads.  Already discussed
148 above.  @xref{Thread Functions}, for more information.
149
150 @item palloc.c
151 @itemx palloc.h
152 Page allocator, which hands out system memory in multiples of 4 kB
153 pages.  @xref{Page Allocator}, for more information.
154
155 @item malloc.c
156 @itemx malloc.h
157 A simple implementation of @func{malloc} and @func{free} for
158 the kernel.  @xref{Block Allocator}, for more information.
159
160 @item interrupt.c
161 @itemx interrupt.h
162 Basic interrupt handling and functions for turning interrupts on and
163 off.  @xref{Interrupt Handling}, for more information.
164
165 @item intr-stubs.S
166 @itemx intr-stubs.h
167 Assembly code for low-level interrupt handling.  @xref{Interrupt
168 Infrastructure}, for more information.
169
170 @item synch.c
171 @itemx synch.h
172 Basic synchronization primitives: semaphores, locks, condition
173 variables, and memory barriers.  You will need to use these for
174 synchronization in all
175 four projects.  @xref{Synchronization}, for more information.
176
177 @item io.h
178 Functions for I/O port access.  This is mostly used by source code in
179 the @file{devices} directory that you won't have to touch.
180
181 @item vaddr.h
182 @itemx pte.h
183 Functions and macros for working with virtual addresses and page table
184 entries.  These will be more important to you in project 3.  For now,
185 you can ignore them.
186
187 @item flags.h
188 Macros that define a few bits in the 80@var{x}86 ``flags'' register.
189 Probably of no interest.  See @bibref{IA32-v1}, section 3.4.3, ``EFLAGS
190 Register,'' for more information.
191 @end table
192
193 @menu
194 * devices code::                
195 * lib files::                   
196 @end menu
197
198 @node devices code
199 @subsubsection @file{devices} code
200
201 The basic threaded kernel also includes these files in the
202 @file{devices} directory:
203
204 @table @file
205 @item timer.c
206 @itemx timer.h
207 System timer that ticks, by default, 100 times per second.  You will
208 modify this code in this project.
209
210 @item vga.c
211 @itemx vga.h
212 VGA display driver.  Responsible for writing text to the screen.
213 You should have no need to look at this code.  @func{printf}
214 calls into the VGA display driver for you, so there's little reason to
215 call this code yourself.
216
217 @item serial.c
218 @itemx serial.h
219 Serial port driver.  Again, @func{printf} calls this code for you,
220 so you don't need to do so yourself.  Feel free to look through it if
221 you're curious.
222
223 @item disk.c
224 @itemx disk.h
225 Supports reading and writing sectors on up to 4 IDE disks.  This won't
226 actually be used until project 2.
227
228 @item intq.c
229 @itemx intq.h
230 Interrupt queue, for managing a circular queue that both kernel
231 threads and interrupt handlers want to access.  Used by the keyboard
232 and serial drivers.
233 @end table
234
235 @node lib files
236 @subsubsection @file{lib} files
237
238 Finally, @file{lib} and @file{lib/kernel} contain useful library
239 routines.  (@file{lib/user} will be used by user programs, starting in
240 project 2, but it is not part of the kernel.)  Here's a few more
241 details:
242
243 @table @file
244 @item ctype.h
245 @itemx inttypes.h
246 @itemx limits.h
247 @itemx stdarg.h
248 @itemx stdbool.h
249 @itemx stddef.h
250 @itemx stdint.h
251 @itemx stdio.c
252 @itemx stdio.h
253 @itemx stdlib.c
254 @itemx stdlib.h
255 @itemx string.c
256 @itemx string.h
257 A subset of the standard C library.  @xref{C99}, for
258 information
259 on a few recently introduced pieces of the C library that you might
260 not have encountered before.  @xref{Unsafe String Functions}, for
261 information on what's been intentionally left out for safety.
262
263 @item debug.c
264 @itemx debug.h
265 Functions and macros to aid debugging.  @xref{Debugging Tools}, for
266 more information.
267
268 @item random.c
269 @itemx random.h
270 Pseudo-random number generator.
271
272 @item round.h
273 Macros for rounding.
274
275 @item syscall-nr.h
276 System call numbers.  Not used until project 2.
277
278 @item kernel/list.c
279 @itemx kernel/list.h
280 Doubly linked list implementation.  Used all over the Pintos code, and
281 you'll probably want to use it a few places yourself in project 1.
282
283 @item kernel/bitmap.c
284 @itemx kernel/bitmap.h
285 Bitmap implementation.  You can use this in your code if you like, but
286 you probably won't have any need for it in project 1.
287
288 @item kernel/hash.c
289 @itemx kernel/hash.h
290 Hash table implementation.  Likely to come in handy for project 3.
291
292 @item kernel/console.c
293 @itemx kernel/console.h
294 @item kernel/stdio.h
295 Implements @func{printf} and a few other functions.
296 @end table
297
298 @node Project 1 Synchronization
299 @subsection Synchronization
300
301 Proper synchronization is an important part of the solutions to these
302 problems.  Any synchronization problem can be easily solved by turning
303 interrupts off: while interrupts are off, there is no concurrency, so
304 there's no possibility for race conditions.  Therefore, it's tempting to
305 solve all synchronization problems this way, but @strong{don't}.
306 Instead, use semaphores, locks, and condition variables to solve the
307 bulk of your synchronization problems.  Read the tour section on
308 synchronization (@pxref{Synchronization}) or the comments in
309 @file{threads/synch.c} if you're unsure what synchronization primitives
310 may be used in what situations.
311
312 In the Pintos projects, the only class of problem best solved by
313 disabling interrupts is coordinating data shared between a kernel thread
314 and an interrupt handler.  Because interrupt handlers can't sleep, they
315 can't acquire locks.  This means that data shared between kernel threads
316 and an interrupt handler must be protected within a kernel thread by
317 turning off interrupts.
318
319 This project only requires accessing a little bit of thread state from
320 interrupt handlers.  For the alarm clock, the timer interrupt needs to
321 wake up sleeping threads.  In the advanced scheduler, the timer
322 interrupt needs to access a few global and per-thread variables.  When
323 you access these variables from kernel threads, you will need to disable
324 interrupts to prevent the timer interrupt from interfering.
325
326 When you do turn off interrupts, take care to do so for the least amount
327 of code possible, or you can end up losing important things such as
328 timer ticks or input events.  Turning off interrupts also increases the
329 interrupt handling latency, which can make a machine feel sluggish if
330 taken too far.
331
332 The synchronization primitives themselves in @file{synch.c} are
333 implemented by disabling interrupts.  You may need to increase the
334 amount of code that runs with interrupts disabled here, but you should
335 still try to keep it to a minimum.
336
337 Disabling interrupts can be useful for debugging, if you want to make
338 sure that a section of code is not interrupted.  You should remove
339 debugging code before turning in your project.  (Don't just comment it
340 out, because that can make the code difficult to read.)
341
342 There should be no busy waiting in your submission.  A tight loop that
343 calls @func{thread_yield} is one form of busy waiting.
344
345 @node Development Suggestions
346 @subsection Development Suggestions
347
348 In the past, many groups divided the assignment into pieces, then each
349 group member worked on his or her piece until just before the
350 deadline, at which time the group reconvened to combine their code and
351 submit.  @strong{This is a bad idea.  We do not recommend this
352 approach.}  Groups that do this often find that two changes conflict
353 with each other, requiring lots of last-minute debugging.  Some groups
354 who have done this have turned in code that did not even compile or
355 boot, much less pass any tests.
356
357 Instead, we recommend integrating your team's changes early and often,
358 using a source code control system such as CVS (@pxref{CVS}) or a
359 group collaboration site such as SourceForge (@pxref{SourceForge}).
360 This is less likely to produce surprises, because everyone can see
361 everyone else's code as it is written, instead of just when it is
362 finished.  These systems also make it possible to review changes and,
363 when a change introduces a bug, drop back to working versions of code.
364
365 You should expect to run into bugs that you simply don't understand
366 while working on this and subsequent projects.  When you do,
367 reread the appendix on debugging tools, which is filled with
368 useful debugging tips that should help you to get back up to speed
369 (@pxref{Debugging Tools}).  Be sure to read the section on backtraces
370 (@pxref{Backtraces}), which will help you to get the most out of every
371 kernel panic or assertion failure.
372
373 @node Project 1 Requirements
374 @section Requirements
375
376 @menu
377 * Project 1 Design Document::   
378 * Alarm Clock::                 
379 * Priority Scheduling::         
380 * Advanced Scheduler::          
381 @end menu
382
383 @node Project 1 Design Document
384 @subsection Design Document
385
386 Before you turn in your project, you must copy @uref{threads.tmpl, , the
387 project 1 design document template} into your source tree under the name
388 @file{pintos/src/threads/DESIGNDOC} and fill it in.  We recommend that
389 you read the design document template before you start working on the
390 project.  @xref{Project Documentation}, for a sample design document
391 that goes along with a fictitious project.
392
393 @node Alarm Clock
394 @subsection Alarm Clock
395
396 Reimplement @func{timer_sleep}, defined in @file{devices/timer.c}.
397 Although a working implementation is provided, it ``busy waits,'' that
398 is, it spins in a loop checking the current time and calling
399 @func{thread_yield} until enough time has gone by.  Reimplement it to
400 avoid busy waiting.
401
402 @deftypefun void timer_sleep (int64_t @var{ticks})
403 Suspends execution of the calling thread until time has advanced by at
404 least @w{@var{x} timer ticks}.  Unless the system is otherwise idle, the
405 thread need not wake up after exactly @var{x} ticks.  Just put it on
406 the ready queue after they have waited for the right amount of time.
407
408 @func{timer_sleep} is useful for threads that operate in real-time,
409 e.g.@: for blinking the cursor once per second.
410
411 The argument to @func{timer_sleep} is expressed in timer ticks, not in
412 milliseconds or any another unit.  There are @code{TIMER_FREQ} timer
413 ticks per second, where @code{TIMER_FREQ} is a macro defined in
414 @code{devices/timer.h}.  The default value is 100.  We don't recommend
415 changing this value, because any change is likely to cause many of
416 the tests to fail.
417 @end deftypefun
418
419 Separate functions @func{timer_msleep}, @func{timer_usleep}, and
420 @func{timer_nsleep} do exist for sleeping a specific number of
421 milliseconds, microseconds, or nanoseconds, respectively, but these will
422 call @func{timer_sleep} automatically when necessary.  You do not need
423 to modify them.
424
425 If your delays seem too short or too long, reread the explanation of the
426 @option{-r} option to @command{pintos} (@pxref{Debugging versus
427 Testing}).
428
429 The alarm clock implementation is not needed for later projects,
430 although it could be useful for project 4.
431
432 @node Priority Scheduling
433 @subsection Priority Scheduling
434
435 Implement priority scheduling in Pintos.
436 When a thread is added to the ready list that has a higher priority
437 than the currently running thread, the current thread should
438 immediately yield the processor to the new thread.  Similarly, when
439 threads are waiting for a lock, semaphore, or condition variable, the
440 highest priority waiting thread should be woken up first.  A thread
441 may raise or lower its own priority at any time, but lowering its
442 priority such that it no longer has the highest priority must cause it
443 to immediately yield the CPU.
444
445 Thread priorities range from @code{PRI_MIN} (0) to @code{PRI_MAX} (63).
446 Lower numbers correspond to lower priorities, so that priority 0
447 is the lowest priority and priority 63 is the highest.
448 The initial thread priority is passed as an argument to
449 @func{thread_create}.  If there's no reason to choose another
450 priority, use @code{PRI_DEFAULT} (31).  The @code{PRI_} macros are
451 defined in @file{threads/thread.h}, and you should not change their
452 values.
453
454 One issue with priority scheduling is ``priority inversion''.  Consider
455 high, medium, and low priority threads @var{H}, @var{M}, and @var{L},
456 respectively.  If @var{H} needs to wait for @var{L} (for instance, for a
457 lock held by @var{L}), and @var{M} is on the ready list, then @var{H}
458 will never get the CPU because the low priority thread will not get any
459 CPU time.  A partial fix for this problem is for @var{H} to ``donate''
460 its priority to @var{L} while @var{L} is holding the lock, then recall
461 the donation once @var{L} releases (and thus @var{H} acquires) the lock.
462
463 Implement priority donation.  You will need to account for all different
464 situations in which priority donation is required.  Be sure to handle
465 multiple donations, in which multiple priorities are donated to a single
466 thread.  You must also handle nested donation: if @var{H} is waiting on
467 a lock that @var{M} holds and @var{M} is waiting on a lock that @var{L}
468 holds, then both @var{M} and @var{L} should be boosted to @var{H}'s
469 priority.  If necessary, you may impose a reasonable limit on depth of
470 nested priority donation, such as 8 levels.
471
472 You must implement priority donation for locks.  You need not
473 implement priority donation for semaphores or condition variables
474 (but you are welcome to do so).  You do need to implement
475 priority scheduling in all cases.
476
477 Finally, implement the following functions that allow a thread to
478 examine and modify its own priority.  Skeletons for these functions are
479 provided in @file{threads/thread.c}.
480
481 @deftypefun void thread_set_priority (int @var{new_priority})
482 Sets the current thread's priority to @var{new_priority}.  If the
483 current thread no longer has the highest priority, yields.
484 @end deftypefun
485
486 @deftypefun int thread_get_priority (void)
487 Returns the current thread's priority.  In the presence of priority
488 donation, returns the higher (donated) priority.
489 @end deftypefun
490
491 You need not provide any interface to allow a thread to directly modify
492 other threads' priorities.
493
494 The priority scheduler is not used in any later project.
495
496 @node Advanced Scheduler
497 @subsection Advanced Scheduler
498
499 Implement a multilevel feedback queue scheduler similar to the
500 4.4@acronym{BSD} scheduler to
501 reduce the average response time for running jobs on your system.
502 @xref{4.4BSD Scheduler}, for detailed requirements.
503
504 Like the priority scheduler, the advanced scheduler chooses the thread
505 to run based on priorities.  However, the advanced scheduler does not do
506 priority donation.  Thus, we recommend that you have the priority
507 scheduler working, except possibly for priority donation, before you
508 start work on the advanced scheduler.
509
510 You must write your code to allow us to choose a scheduling algorithm
511 policy at Pintos startup time.  By default, the priority scheduler
512 must be active, but we must be able to choose the 4.4@acronym{BSD}
513 scheduler
514 with the @option{-mlfqs} kernel option.  Passing this
515 option sets @code{enable_mlfqs}, declared in @file{threads/init.h}, to
516 true when the options are parsed by @func{parse_options}, which happens
517 midway through @func{main}.
518
519 When the 4.4@acronym{BSD} scheduler is enabled, threads no longer
520 directly control their own priorities.  The @var{priority} argument to
521 @func{thread_create} should be ignored, as well as any calls to
522 @func{thread_set_priority}, and @func{thread_get_priority} should return
523 the thread's current priority as set by the scheduler.
524
525 The advanced scheduler is not used in any later project.
526
527 @node Project 1 FAQ
528 @section FAQ
529
530 @table @b
531 @item How much code will I need to write?
532
533 Here's a summary of our reference solution, produced by the
534 @command{diffstat} program.  The final row gives total lines inserted
535 and deleted; a changed line counts as both an insertion and a deletion.
536
537 The reference solution represents just one possible solution.  Many
538 other solutions are also possible and many of those differ greatly from
539 the reference solution.  Some excellent solutions may not modify all the
540 files modified by the reference solution, and some may modify files not
541 modified by the reference solution.
542
543 @verbatim
544  devices/timer.c       |   42 +++++-
545  threads/fixed-point.h |  120 ++++++++++++++++++
546  threads/synch.c       |   88 ++++++++++++-
547  threads/thread.c      |  196 ++++++++++++++++++++++++++----
548  threads/thread.h      |   23 +++
549  5 files changed, 440 insertions(+), 29 deletions(-)
550 @end verbatim
551
552 @file{fixed-point.h} is a new file added by the reference solution.
553
554 @item How do I update the @file{Makefile}s when I add a new source file?
555
556 @anchor{Adding Source Files}
557 To add a @file{.c} file, edit the top-level @file{Makefile.build}.
558 Add the new file to variable @samp{@var{dir}_SRC}, where
559 @var{dir} is the directory where you added the file.  For this
560 project, that means you should add it to @code{threads_SRC} or
561 @code{devices_SRC}.  Then run @code{make}.  If your new file
562 doesn't get
563 compiled, run @code{make clean} and then try again.
564
565 When you modify the top-level @file{Makefile.build} and re-run
566 @command{make}, the modified
567 version should be automatically copied to
568 @file{threads/build/Makefile}.  The converse is
569 not true, so any changes will be lost the next time you run @code{make
570 clean} from the @file{threads} directory.  Unless your changes are
571 truly temporary, you should prefer to edit @file{Makefile.build}.
572
573 A new @file{.h} file does not require editing the @file{Makefile}s.
574
575 @item What does @code{warning: no previous prototype for `@var{func}'} mean?
576
577 It means that you defined a non-@code{static} function without
578 preceding it by a prototype.  Because non-@code{static} functions are
579 intended for use by other @file{.c} files, for safety they should be
580 prototyped in a header file included before their definition.  To fix
581 the problem, add a prototype in a header file that you include, or, if
582 the function isn't actually used by other @file{.c} files, make it
583 @code{static}.
584
585 @item What is the interval between timer interrupts?
586
587 Timer interrupts occur @code{TIMER_FREQ} times per second.  You can
588 adjust this value by editing @file{devices/timer.h}.  The default is
589 100 Hz.
590
591 We don't recommend changing this value, because any changes are likely
592 to cause many of the tests to fail.
593
594 @item How long is a time slice?
595
596 There are @code{TIME_SLICE} ticks per time slice.  This macro is
597 declared in @file{threads/thread.c}.  The default is 4 ticks.
598
599 We don't recommend changing this value, because any changes are likely
600 to cause many of the tests to fail.
601
602 @item How do I run the tests?
603
604 @xref{Testing}.
605
606 @item Why do I get a test failure in @func{pass}?
607
608 @anchor{The pass function fails}
609 You are probably looking at a backtrace that looks something like this:
610
611 @example
612 0xc0108810: debug_panic (lib/kernel/debug.c:32)
613 0xc010a99f: pass (tests/threads/tests.c:93)
614 0xc010bdd3: test_mlfqs_load_1 (...threads/mlfqs-load-1.c:33)
615 0xc010a8cf: run_test (tests/threads/tests.c:51)
616 0xc0100452: run_task (threads/init.c:283)
617 0xc0100536: run_actions (threads/init.c:333)
618 0xc01000bb: main (threads/init.c:137)
619 @end example
620
621 This is just confusing output from the @command{backtrace} program.  It
622 does not actually mean that @func{pass} called @func{debug_panic}.  In
623 fact, @func{fail} called @func{debug_panic} (via the @func{PANIC}
624 macro).  GCC knows that @func{debug_panic} does not return, because it
625 is declared @code{NO_RETURN} (@pxref{Function and Parameter
626 Attributes}), so it doesn't include any code in @func{pass} to take
627 control when @func{debug_panic} returns.  This means that the return
628 address on the stack looks like it is at the beginning of the function
629 that happens to follow @func{fail} in memory, which in this case happens
630 to be @func{pass}.
631
632 @xref{Backtraces}, for more information.
633 @end table
634
635 @menu
636 * Alarm Clock FAQ::             
637 * Priority Scheduling FAQ::     
638 * Advanced Scheduler FAQ::      
639 @end menu
640
641 @node Alarm Clock FAQ
642 @subsection Alarm Clock FAQ
643
644 @table @b
645 @item Do I need to account for timer values overflowing?
646
647 Don't worry about the possibility of timer values overflowing.  Timer
648 values are expressed as signed 64-bit numbers, which at 100 ticks per
649 second should be good for almost 2,924,712,087 years.  By then, we
650 expect Pintos to have been phased out of the CS 140 curriculum.
651 @end table
652
653 @node Priority Scheduling FAQ
654 @subsection Priority Scheduling FAQ
655
656 @table @b
657 @item Doesn't priority scheduling lead to starvation?
658
659 Yes, strict priority scheduling can lead to starvation
660 because a thread will not run if any higher-priority thread is runnable.
661 The advanced scheduler introduces a mechanism for dynamically
662 changing thread priorities.
663
664 Strict priority scheduling is valuable in real-time systems because it
665 offers the programmer more control over which jobs get processing
666 time.  High priorities are generally reserved for time-critical
667 tasks. It's not ``fair,'' but it addresses other concerns not
668 applicable to a general-purpose operating system.
669
670 @item What thread should run after a lock has been released?
671
672 When a lock is released, the highest priority thread waiting for that
673 lock should be unblocked and put on the list of ready threads.  The
674 scheduler should then run the highest priority thread on the ready
675 list.
676
677 @item If the highest-priority thread yields, does it continue running?
678
679 Yes.  If there is a single highest-priority thread, it continues
680 running until it blocks or finishes, even if it calls
681 @func{thread_yield}.
682 If multiple threads have the same highest priority,
683 @func{thread_yield} should switch among them in ``round robin'' order.
684
685 @item What happens to the priority of a donating thread?
686
687 Priority donation only changes the priority of the donee
688 thread.  The donor thread's priority is unchanged.  
689 Priority donation is not additive: if thread @var{A} (with priority 5) donates
690 to thread @var{B} (with priority 3), then @var{B}'s new priority is 5, not 8.
691
692 @item Can a thread's priority change while it is on the ready queue?
693
694 Yes.  Consider this case: low-priority thread @var{L} holds a
695 lock that high-priority thread @var{H} wants, so @var{H} donates its
696 priority to @var{L}.  @var{L} releases the lock and
697 thus loses the CPU and is moved to the ready queue.  Now @var{L}'s
698 old priority is restored while it is in the ready queue.
699
700 @item Can a thread's priority change while it is blocked?
701
702 Yes.  While a thread that has acquired lock @var{L} is blocked for any
703 reason, its priority can increase by priority donation if a
704 higher-priority thread attempts to acquire @var{L}.  This case is
705 checked by the @code{priority-donate-sema} test.
706
707 @item Can a thread added to the ready list preempt the processor?
708
709 Yes.  If a thread added to the ready list has higher priority than the
710 running thread, the correct behavior is to immediately yield the
711 processor.  It is not acceptable to wait for the next timer interrupt.
712 The highest priority thread should run as soon as it is runnable,
713 preempting whatever thread is currently running.
714
715 @item How does @func{thread_set_priority} affect a thread receiving donations?
716
717 It sets the thread's base priority.  The thread's effective priority
718 becomes the higher of the newly set priority or the highest donated
719 priority.  When the donations are released, the thread's priority
720 becomes the one set through the function call.  This behavior is checked
721 by the @code{priority-donate-lower} test.
722
723 @item Calling @func{printf} in @func{sema_up} or @func{sema_down} reboots!
724
725 @anchor{printf Reboots}
726 Yes.  These functions are called before @func{printf} is ready to go.
727 You could add a global flag initialized to false and set it to true
728 just before the first @func{printf} in @func{main}.  Then modify
729 @func{printf} itself to return immediately if the flag isn't set.
730 @end table
731
732 @node Advanced Scheduler FAQ
733 @subsection Advanced Scheduler FAQ
734
735 @table @b
736 @item How does priority donation interact with the advanced scheduler?
737
738 It doesn't have to.  We won't test priority donation and the advanced
739 scheduler at the same time.
740
741 @item Can I use one queue instead of 64 queues?
742
743 Yes.  In general, your implementation may differ from the description,
744 as long as its behavior is the same.
745 @end table