Explain why it sometimes looks like pass() fails.
[pintos-anon] / doc / threads.texi
1 @node Project 1--Threads, Project 2--User Programs, Pintos Tour, Top
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 in @ref{Threads Tour} and especially
16 @ref{Synchronization}.  To complete this project you will also need to
17 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 @command{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{@command{gdb} might tell you that
83 @func{schedule} doesn't exist, which is arguably a @command{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
141 files.  @file{thread.h} defines @struct{thread}, which you are likely
142 to modify in all four projects.  See @ref{struct thread} and @ref{Thread
143 Support} for 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 mmu.h
182 Functions and macros related to memory management, including page
183 directories and page tables.  This will be more important to you in
184 project 3.  For now, you can ignore it.
185
186 @item flags.h
187 Macros that define a few bits in the 80@var{x}86 ``flags'' register.
188 Probably of no interest.  See @bibref{IA32-v1}, section 3.4.3, for more
189 information.
190 @end table
191
192 @menu
193 * devices code::                
194 * lib files::                   
195 @end menu
196
197 @node devices code
198 @subsubsection @file{devices} code
199
200 The basic threaded kernel also includes these files in the
201 @file{devices} directory:
202
203 @table @file
204 @item timer.c
205 @itemx timer.h
206 System timer that ticks, by default, 100 times per second.  You will
207 modify this code in this project.
208
209 @item vga.c
210 @itemx vga.h
211 VGA display driver.  Responsible for writing text to the screen.
212 You should have no need to look at this code.  @func{printf}
213 calls into the VGA display driver for you, so there's little reason to
214 call this code yourself.
215
216 @item serial.c
217 @itemx serial.h
218 Serial port driver.  Again, @func{printf} calls this code for you,
219 so you don't need to do so yourself.  Feel free to look through it if
220 you're curious.
221
222 @item disk.c
223 @itemx disk.h
224 Supports reading and writing sectors on up to 4 IDE disks.  This won't
225 actually be used until project 2.
226
227 @item intq.c
228 @itemx intq.h
229 Interrupt queue, for managing a circular queue that both kernel
230 threads and interrupt handlers want to access.  Used by the keyboard
231 and serial drivers.
232 @end table
233
234 @node lib files
235 @subsubsection @file{lib} files
236
237 Finally, @file{lib} and @file{lib/kernel} contain useful library
238 routines.  (@file{lib/user} will be used by user programs, starting in
239 project 2, but it is not part of the kernel.)  Here's a few more
240 details:
241
242 @table @file
243 @item ctype.h
244 @itemx inttypes.h
245 @itemx limits.h
246 @itemx stdarg.h
247 @itemx stdbool.h
248 @itemx stddef.h
249 @itemx stdint.h
250 @itemx stdio.c
251 @itemx stdio.h
252 @itemx stdlib.c
253 @itemx stdlib.h
254 @itemx string.c
255 @itemx string.h
256 A subset of the standard C library.  @xref{C99}, for
257 information
258 on a few recently introduced pieces of the C library that you might
259 not have encountered before.  @xref{Unsafe String Functions}, for
260 information on what's been intentionally left out for safety.
261
262 @item debug.c
263 @itemx debug.h
264 Functions and macros to aid debugging.  @xref{Debugging Tools}, for
265 more information.
266
267 @item random.c
268 @itemx random.h
269 Pseudo-random number generator.
270
271 @item round.h
272 Macros for rounding.
273
274 @item syscall-nr.h
275 System call numbers.  Not used until project 2.
276
277 @item kernel/list.c
278 @itemx kernel/list.h
279 Doubly linked list implementation.  Used all over the Pintos code, and
280 you'll probably want to use it a few places yourself in project 1.
281
282 @item kernel/bitmap.c
283 @itemx kernel/bitmap.h
284 Bitmap implementation.  You can use this in your code if you like, but
285 you probably won't have any need for it in project 1.
286
287 @item kernel/hash.c
288 @itemx kernel/hash.h
289 Hash table implementation.  Likely to come in handy for project 3.
290
291 @item kernel/console.c
292 @itemx kernel/console.h
293 @item kernel/stdio.h
294 Implements @func{printf} and a few other functions.
295 @end table
296
297 @node Project 1 Synchronization
298 @subsection Synchronization
299
300 Proper synchronization is an important part of the solutions to these
301 problems.  Any synchronization problem can be easily solved by turning
302 interrupts off: while interrupts are off, there is no concurrency, so
303 there's no possibility for race conditions.  Therefore, it's tempting to
304 solve all synchronization problems this way, but @strong{don't}.
305 Instead, use semaphores, locks, and condition variables to solve the
306 bulk of your synchronization problems.  Read the tour section on
307 synchronization (@pxref{Synchronization}) or the comments in
308 @file{threads/synch.c} if you're unsure what synchronization primitives
309 may be used in what situations.
310
311 In the Pintos projects, the only class of problem best solved by
312 disabling interrupts is coordinating data shared between a kernel thread
313 and an interrupt handler.  Because interrupt handlers can't sleep, they
314 can't acquire locks.  This means that data shared between kernel threads
315 and an interrupt handler must be protected within a kernel thread by
316 turning off interrupts.
317
318 This project only requires accessing a little bit of thread state from
319 interrupt handlers.  For the alarm clock, the timer interrupt needs to
320 wake up sleeping threads.  In the advanced scheduler, the timer
321 interrupt needs to access a few global and per-thread variables.  When
322 you access these variables from kernel threads, you will need to disable
323 interrupts to prevent the timer interrupt from interfering.
324
325 When you do turn off interrupts, take care to do so for the least amount
326 of code possible, or you can end up losing important things such as
327 timer ticks or input events.  Turning off interrupts also increases the
328 interrupt handling latency, which can make a machine feel sluggish if
329 taken too far.
330
331 You may need to add or modify code where interrupts are already
332 disabled, such as in @func{sema_up} or @func{sema_down}.  You should
333 still try to keep this code as short as you can.
334
335 Disabling interrupts can be useful for debugging, if you want to make
336 sure that a section of code is not interrupted.  You should remove
337 debugging code before turning in your project.  (Don't just comment it
338 out, because that can make the code difficult to read.)
339
340 There should be no busy waiting in your submission.  A tight loop that
341 calls @func{thread_yield} is one form of busy waiting.
342
343 @node Development Suggestions
344 @subsection Development Suggestions
345
346 In the past, many groups divided the assignment into pieces, then each
347 group member worked on his or her piece until just before the
348 deadline, at which time the group reconvened to combine their code and
349 submit.  @strong{This is a bad idea.  We do not recommend this
350 approach.}  Groups that do this often find that two changes conflict
351 with each other, requiring lots of last-minute debugging.  Some groups
352 who have done this have turned in code that did not even compile or
353 boot, much less pass any tests.
354
355 Instead, we recommend integrating your team's changes early and often,
356 using a source code control system such as CVS (@pxref{CVS}) or a
357 group collaboration site such as SourceForge (@pxref{SourceForge}).
358 This is less likely to produce surprises, because everyone can see
359 everyone else's code as it is written, instead of just when it is
360 finished.  These systems also make it possible to review changes and,
361 when a change introduces a bug, drop back to working versions of code.
362
363 You should expect to run into bugs that you simply don't understand
364 while working on this and subsequent projects.  When you do,
365 reread the appendix on debugging tools, which is filled with
366 useful debugging tips that should help you to get back up to speed
367 (@pxref{Debugging Tools}).  Be sure to read the section on backtraces
368 (@pxref{Backtraces}), which will help you to get the most out of every
369 kernel panic or assertion failure.
370
371 @node Project 1 Requirements
372 @section Requirements
373
374 @menu
375 * Project 1 Design Document::   
376 * Alarm Clock::                 
377 * Priority Scheduling::         
378 * Advanced Scheduler::          
379 @end menu
380
381 @node Project 1 Design Document
382 @subsection Design Document
383
384 Before you turn in your project, you must copy @uref{threads.tmpl, , the
385 project 1 design document template} into your source tree under the name
386 @file{pintos/src/threads/DESIGNDOC} and fill it in.  We recommend that
387 you read the design document template before you start working on the
388 project.  @xref{Project Documentation}, for a sample design document
389 that goes along with a fictitious project.
390
391 @node Alarm Clock
392 @subsection Alarm Clock
393
394 Reimplement @func{timer_sleep}, defined in @file{devices/timer.c}.
395 Although a working implementation is provided, it ``busy waits,'' that
396 is, it spins in a loop checking the current time and calling
397 @func{thread_yield} until enough time has gone by.  Reimplement it to
398 avoid busy waiting.
399
400 @deftypefun void timer_sleep (int64_t @var{ticks})
401 Suspends execution of the calling thread until time has advanced by at
402 least @w{@var{x} timer ticks}.  Unless the system is otherwise idle, the
403 thread need not wake up after exactly @var{x} ticks.  Just put it on
404 the ready queue after they have waited for the right amount of time.
405
406 @func{timer_sleep} is useful for threads that operate in real-time,
407 e.g.@: for blinking the cursor once per second.
408
409 The argument to @func{timer_sleep} is expressed in timer ticks, not in
410 milliseconds or any another unit.  There are @code{TIMER_FREQ} timer
411 ticks per second, where @code{TIMER_FREQ} is a macro defined in
412 @code{devices/timer.h}.  The default value is 100.  We don't recommend
413 changing this value, because any change is likely to cause many of
414 the tests to fail.
415 @end deftypefun
416
417 Separate functions @func{timer_msleep}, @func{timer_usleep}, and
418 @func{timer_nsleep} do exist for sleeping a specific number of
419 milliseconds, microseconds, or nanoseconds, respectively, but these will
420 call @func{timer_sleep} automatically when necessary.  You do not need
421 to modify them.
422
423 If your delays seem too short or too long, reread the explanation of the
424 @option{-r} option to @command{pintos} (@pxref{Debugging versus
425 Testing}).
426
427 The alarm clock implementation is not needed for later projects,
428 although it could be useful for project 4.
429
430 @node Priority Scheduling
431 @subsection Priority Scheduling
432
433 Implement priority scheduling in Pintos.
434 When a thread is added to the ready list that has a higher priority
435 than the currently running thread, the current thread should
436 immediately yield the processor to the new thread.  Similarly, when
437 threads are waiting for a lock, semaphore, or condition variable, the
438 highest priority waiting thread should be woken up first.  A thread
439 may raise or lower its own priority at any time, but lowering its
440 priority such that it no longer has the highest priority must cause it
441 to immediately yield the CPU.
442
443 Thread priorities range from @code{PRI_MIN} (0) to @code{PRI_MAX} (63).
444 Lower numbers correspond to @emph{higher} priorities, so that priority 0
445 is the highest priority and priority 63 is the lowest.
446 The initial thread priority is passed as an argument to
447 @func{thread_create}.  If there's no reason to choose another
448 priority, use @code{PRI_DEFAULT} (31).  The @code{PRI_} macros are
449 defined in @file{threads/thread.h}, and you should not change their
450 values.
451
452 One issue with priority scheduling is ``priority inversion''.  Consider
453 high, medium, and low priority threads @var{H}, @var{M}, and @var{L},
454 respectively.  If @var{H} needs to wait for @var{L} (for instance, for a
455 lock held by @var{L}), and @var{M} is on the ready list, then @var{H}
456 will never get the CPU because the low priority thread will not get any
457 CPU time.  A partial fix for this problem is for @var{H} to ``donate''
458 its priority to @var{L} while @var{L} is holding the lock, then recall
459 the donation once @var{L} releases (and thus @var{H} acquires) the lock.
460
461 Implement priority donation.  You will need to account for all different
462 situations in which priority donation is required.  Be sure to handle
463 multiple donations, in which multiple priorities are donated to a single
464 thread.  You must also handle nested donation: if @var{H} is waiting on
465 a lock that @var{M} holds and @var{M} is waiting on a lock that @var{L}
466 holds, then both @var{M} and @var{L} should be boosted to @var{H}'s
467 priority.  If necessary, you may impose a reasonable limit on depth of
468 nested priority donation, such as 8 levels.
469
470 You must implement priority donation for locks.  You need not
471 implement priority donation for semaphores or condition variables
472 (but you are welcome to do so).  You do need to implement
473 priority scheduling in all cases.
474
475 Finally, implement the following functions that allow a thread to
476 examine and modify its own priority.  Skeletons for these functions are
477 provided in @file{threads/thread.c}.
478
479 @deftypefun void thread_set_priority (int @var{new_priority})
480 Sets the current thread's priority to @var{new_priority}.  If the
481 current thread no longer has the highest priority, yields.
482 @end deftypefun
483
484 @deftypefun int thread_get_priority (void)
485 Returns the current thread's priority.  In the presence of priority
486 donation, returns the higher (donated) priority.
487 @end deftypefun
488
489 You need not provide any interface to allow a thread to directly modify
490 other threads' priorities.
491
492 The priority scheduler is not used in any later project.
493
494 @node Advanced Scheduler
495 @subsection Advanced Scheduler
496
497 Implement a multilevel feedback queue scheduler similar to the
498 4.4@acronym{BSD} scheduler to
499 reduce the average response time for running jobs on your system.
500 @xref{4.4BSD Scheduler}, for detailed requirements.
501
502 Like the priority scheduler, the advanced scheduler chooses the thread
503 to run based on priorities.  However, the advanced scheduler does not do
504 priority donation.  Thus, we recommend that you have the priority
505 scheduler working, except possibly for priority donation, before you
506 start work on the advanced scheduler.
507
508 You must write your code to allow us to choose a scheduling algorithm
509 policy at Pintos startup time.  By default, the priority scheduler
510 must be active, but we must be able to choose the 4.4@acronym{BSD}
511 scheduler
512 with the @option{-mlfqs} kernel option.  Passing this
513 option sets @code{enable_mlfqs}, declared in @file{threads/init.h}, to
514 true.
515
516 When the 4.4@acronym{BSD} scheduler is enabled, threads no longer
517 directly control their own priorities.  The @var{priority} argument to
518 @func{thread_create} should be ignored, as well as any calls to
519 @func{thread_set_priority}, and @func{thread_get_priority} should return
520 the thread's current priority as set by the scheduler.
521
522 The advanced scheduler is not used in any later project.
523
524 @node Project 1 FAQ
525 @section FAQ
526
527 @table @b
528 @item How much code will I need to write?
529
530 Here's a summary of our reference solution, produced by the
531 @command{diffstat} program.  The final row gives total lines inserted
532 and deleted; a changed line counts as both an insertion and a deletion.
533
534 @verbatim
535  devices/timer.c       |   42 +++++-
536  threads/fixed-point.h |  120 ++++++++++++++++++
537  threads/synch.c       |   88 ++++++++++++-
538  threads/thread.c      |  196 ++++++++++++++++++++++++++----
539  threads/thread.h      |   23 +++
540  5 files changed, 440 insertions(+), 29 deletions(-)
541 @end verbatim
542
543 @item How do I update the @file{Makefile}s when I add a new source file?
544
545 @anchor{Adding Source Files}
546 To add a @file{.c} file, edit the top-level @file{Makefile.build}.
547 Add the new file to variable @samp{@var{dir}_SRC}, where
548 @var{dir} is the directory where you added the file.  For this
549 project, that means you should add it to @code{threads_SRC} or
550 @code{devices_SRC}.  Then run @code{make}.  If your new file
551 doesn't get
552 compiled, run @code{make clean} and then try again.
553
554 When you modify the top-level @file{Makefile.build} and re-run
555 @command{make}, the modified
556 version should be automatically copied to
557 @file{threads/build/Makefile}.  The converse is
558 not true, so any changes will be lost the next time you run @code{make
559 clean} from the @file{threads} directory.  Unless your changes are
560 truly temporary, you should prefer to edit @file{Makefile.build}.
561
562 A new @file{.h} file does not require editing the @file{Makefile}s.
563
564 @item What does @code{warning: no previous prototype for `@var{func}'} mean?
565
566 It means that you defined a non-@code{static} function without
567 preceding it by a prototype.  Because non-@code{static} functions are
568 intended for use by other @file{.c} files, for safety they should be
569 prototyped in a header file included before their definition.  To fix
570 the problem, add a prototype in a header file that you include, or, if
571 the function isn't actually used by other @file{.c} files, make it
572 @code{static}.
573
574 @item What is the interval between timer interrupts?
575
576 Timer interrupts occur @code{TIMER_FREQ} times per second.  You can
577 adjust this value by editing @file{devices/timer.h}.  The default is
578 100 Hz.
579
580 We don't recommend changing this value, because any changes are likely
581 to cause many of the tests to fail.
582
583 @item How long is a time slice?
584
585 There are @code{TIME_SLICE} ticks per time slice.  This macro is
586 declared in @file{threads/thread.c}.  The default is 4 ticks.
587
588 We don't recommend changing this value, because any changes are likely
589 to cause many of the tests to fail.
590
591 @item How do I run the tests?
592
593 @xref{Testing}.
594
595 @item Why do I get a test failure in @func{pass}?
596
597 @anchor{The pass function fails}
598 You are probably looking at a backtrace that looks something like this:
599
600 @example
601 0xc0108810: debug_panic (../../lib/kernel/debug.c:32)
602 0xc010a99f: pass (../../tests/threads/tests.c:93)
603 0xc010bdd3: test_mlfqs_load_1 (../../tests/threads/mlfqs-load-1.c:33)
604 0xc010a8cf: run_test (../../tests/threads/tests.c:51)
605 0xc0100452: run_task (../../threads/init.c:283)
606 0xc0100536: run_actions (../../threads/init.c:333)
607 0xc01000bb: main (../../threads/init.c:137)
608 @end example
609
610 This is just confusing output from the @command{backtrace} program.  It
611 does not actually mean that @func{pass} called @func{debug_panic}.  In
612 fact, @func{fail} called @func{debug_panic} (via the @func{PANIC}
613 macro).  GCC knows that @func{debug_panic} does not return, because it
614 is declared @code{NO_RETURN} (@pxref{Function and Parameter
615 Attributes}), so it doesn't include any code in @func{pass} to take
616 control when @func{debug_panic} returns.  This means that the return
617 address on the stack looks like it is at the beginning of the function
618 that happens to follow @func{fail} in memory, which in this case happens
619 to be @func{pass}.
620
621 @xref{Backtraces}, for more information.
622 @end table
623
624 @menu
625 * Alarm Clock FAQ::             
626 * Priority Scheduling FAQ::     
627 * Advanced Scheduler FAQ::      
628 @end menu
629
630 @node Alarm Clock FAQ
631 @subsection Alarm Clock FAQ
632
633 @table @b
634 @item Do I need to account for timer values overflowing?
635
636 Don't worry about the possibility of timer values overflowing.  Timer
637 values are expressed as signed 64-bit numbers, which at 100 ticks per
638 second should be good for almost 2,924,712,087 years.  By then, we
639 expect Pintos to have been phased out of the CS 140 curriculum.
640 @end table
641
642 @node Priority Scheduling FAQ
643 @subsection Priority Scheduling FAQ
644
645 @table @b
646 @item Doesn't priority scheduling lead to starvation?
647
648 Yes, strict priority scheduling can lead to starvation
649 because a thread will not run if any higher-priority thread is runnable.
650 The advanced scheduler introduces a mechanism for dynamically
651 changing thread priorities.
652
653 Strict priority scheduling is valuable in real-time systems because it
654 offers the programmer more control over which jobs get processing
655 time.  High priorities are generally reserved for time-critical
656 tasks. It's not ``fair,'' but it addresses other concerns not
657 applicable to a general-purpose operating system.
658
659 @item What thread should run after a lock has been released?
660
661 When a lock is released, the highest priority thread waiting for that
662 lock should be unblocked and put on the list of ready threads.  The
663 scheduler should then run the highest priority thread on the ready
664 list.
665
666 @item If the highest-priority thread yields, does it continue running?
667
668 Yes.  As long as there is a single highest-priority thread, it continues
669 running until it blocks or finishes, even if it calls
670 @func{thread_yield}.
671 If multiple threads have the same highest priority,
672 @func{thread_yield} should switch among them in ``round robin'' order.
673
674 @item What happens to the priority of a donating thread?
675
676 Priority donation only changes the priority of the donee
677 thread.  The donor thread's priority is unchanged.  
678 Priority donation is not additive: if thread @var{A} (with priority 5) donates
679 to thread @var{B} (with priority 3), then @var{B}'s new priority is 5, not 8.
680
681 @item Can a thread's priority change while it is on the ready queue?
682
683 Yes.  Consider this case: low-priority thread @var{L} holds a
684 lock that high-priority thread @var{H} wants, so @var{H} donates its
685 priority to @var{L}.  @var{L} releases the lock and
686 thus loses the CPU and is moved to the ready queue.  Now @var{L}'s
687 old priority is restored while it is in the ready queue.
688
689 @item Can a thread added to the ready list preempt the processor?
690
691 Yes.  If a thread added to the ready list has higher priority than the
692 running thread, the correct behavior is to immediately yield the
693 processor.  It is not acceptable to wait for the next timer interrupt.
694 The highest priority thread should run as soon as it is runnable,
695 preempting whatever thread is currently running.
696
697 @item How does @func{thread_set_priority} affect a thread receiving donations?
698
699 It should do something sensible, but no particular behavior is
700 required.  None of the test cases call @func{thread_set_priority} from a
701 thread while it is receiving a priority donation.
702
703 @item Calling @func{printf} in @func{sema_up} or @func{sema_down} reboots!
704
705 @anchor{printf Reboots}
706 Yes.  These functions are called before @func{printf} is ready to go.
707 You could add a global flag initialized to false and set it to true
708 just before the first @func{printf} in @func{main}.  Then modify
709 @func{printf} itself to return immediately if the flag isn't set.
710 @end table
711
712 @node Advanced Scheduler FAQ
713 @subsection Advanced Scheduler FAQ
714
715 @table @b
716 @item How does priority donation interact with the advanced scheduler?
717
718 It doesn't have to.  We won't test priority donation and the advanced
719 scheduler at the same time.
720 @end table