Add stdio test.
[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. Additionally, you
7 will use at least part of this increased functionality in future
8 assignments.
9
10 You will be working in primarily in the @file{threads} directory for
11 this assignment, with some work in the @file{devices} directory on the
12 side.  Compilation should be done in the @file{threads} directory.
13
14 Before you read the description of this project, you should read all
15 of the following sections: @ref{Introduction}, @ref{Coding Standards},
16 @ref{Project Documentation}, @ref{Debugging Tools}, and
17 @ref{Development Tools}.  You should at least skim the material in
18 @ref{Threads Tour}.  To complete this project you will also need to
19 read @ref{Multilevel Feedback Scheduling}.
20
21 @menu
22 * Understanding Threads::       
23 * Project 1 Code::              
24 * Debugging versus Testing::    
25 * Tips::                        
26 * Problem 1-1 Alarm Clock::     
27 * Problem 1-2 Priority Scheduling::  
28 * Problem 1-3 Advanced Scheduler::  
29 * Threads FAQ::                 
30 @end menu
31
32 @node Understanding Threads
33 @section Understanding Threads
34
35 The first step is to read and understand the initial thread system.
36 Pintos, by default, implements thread creation and thread completion,
37 a simple scheduler to switch between threads, and synchronization
38 primitives (semaphores, locks, and condition variables). 
39
40 However, there's a lot of magic going on in some of this code, so if
41 you haven't already compiled and run the base system, as described in
42 the introduction (@pxref{Introduction}), you should do so now.  You
43 can read through parts of the source code by hand to see what's going
44 on.  If you like, you can add calls to @func{printf} almost
45 anywhere, then recompile and run to see what happens and in what
46 order.  You can also run the kernel in a debugger and set breakpoints
47 at interesting spots, single-step through code and examine data, and
48 so on.  @xref{i386-elf-gdb}, for more information.
49
50 When a thread is created, you are creating a new context to be
51 scheduled. You provide a function to be run in this context as an
52 argument to @func{thread_create}. The first time the thread is
53 scheduled and runs, it will start from the beginning of that function
54 and execute it in the context. When that function returns, that thread
55 completes. Each thread, therefore, acts like a mini-program running
56 inside Pintos, with the function passed to @func{thread_create}
57 acting like @func{main}.
58
59 At any given time, Pintos is running exactly one thread, with the
60 others switched out.  The scheduler decides which thread to run next
61 when it needs to switch between them.  (If no thread is ready to run
62 at any given time, then the special ``idle'' thread runs.)  The
63 synchronization primitives are used to force context switches when one
64 thread needs to wait for another thread to do something.
65
66 The exact mechanics of a context switch are pretty gruesome and have
67 been provided for you in @file{threads/switch.S} (this is 80@var{x}86
68 assembly; don't worry about understanding it).  It involves saving the
69 state of the currently running thread and restoring the state of the
70 thread we're switching to.
71
72 Using the @command{gdb} debugger, slowly trace through a context
73 switch to see what happens (@pxref{i386-elf-gdb}).  You can set a
74 breakpoint on the @func{schedule} function to start out, and then
75 single-step from there.@footnote{@command{gdb} might tell you that
76 @func{schedule} doesn't exist, which is arguably a @command{gdb} bug.
77 You can work around this by setting the breakpoint by filename and
78 line number, e.g.@: @code{break thread.c:@var{ln}} where @var{ln} is
79 the line number of the first declaration in @func{schedule}.}  Be sure
80 to keep track of each thread's address
81 and state, and what procedures are on the call stack for each thread.
82 You will notice that when one thread calls @func{switch_threads},
83 another thread starts running, and the first thing the new thread does
84 is to return from @func{switch_threads}.  We realize this comment will
85 seem cryptic to you at this point, but you will understand threads
86 once you understand why the @func{switch_threads} that gets called is
87 different from the @func{switch_threads} that returns.
88
89 @strong{Warning}: In Pintos, each thread is assigned a small,
90 fixed-size execution stack just under @w{4 kB} in size.  The kernel
91 does try to detect stack overflow, but it cannot always succeed.  You
92 may cause bizarre problems, such as mysterious kernel panics, if you
93 declare large data structures as non-static local variables,
94 e.g. @samp{int buf[1000];}.  Alternatives to stack allocation include
95 the page allocator in @file{threads/palloc.c} and the block allocator
96 in @file{threads/malloc.c}.  Note that the page allocator doles out
97 @w{4 kB} chunks and that @func{malloc} has a @w{2 kB} block size
98 limit.  If you need larger chunks, consider using a linked structure
99 instead.
100
101 @node Project 1 Code
102 @section Code
103
104 Here is a brief overview of the files in the @file{threads}
105 directory.  You will not need to modify most of this code, but the
106 hope is that presenting this overview will give you a start on what
107 code to look at.
108
109 @table @file
110 @item loader.S
111 @itemx loader.h
112 The kernel loader.  Assembles to 512 bytes of code and data that the
113 PC BIOS loads into memory and which in turn loads the kernel into
114 memory, does basic processor initialization, and jumps to the
115 beginning of the kernel.  You should not need to look at this code or
116 modify it.
117
118 @item kernel.lds.S
119 The linker script used to link the kernel.  Sets the load address of
120 the kernel and arranges for @file{start.S} to be at the very beginning
121 of the kernel image.  Again, you should not need to look at this code
122 or modify it, but it's here in case you're curious.
123
124 @item start.S
125 Jumps to @func{main}.
126
127 @item init.c
128 @itemx init.h
129 Kernel initialization, including @func{main}, the kernel's ``main
130 program.''  You should look over @func{main} at least to see what
131 gets initialized.
132
133 @item thread.c
134 @itemx thread.h
135 Basic thread support.  Much of your work will take place in these
136 files.  @file{thread.h} defines @struct{thread}, which you will
137 modify in the first three projects.
138
139 @item switch.S
140 @itemx switch.h
141 Assembly language routine for switching threads.  Already discussed
142 above.
143
144 @item palloc.c
145 @itemx palloc.h
146 Page allocator, which hands out system memory in multiples of 4 kB
147 pages.
148
149 @item malloc.c
150 @itemx malloc.h
151 A very simple implementation of @func{malloc} and @func{free} for
152 the kernel.
153
154 @item interrupt.c
155 @itemx interrupt.h
156 Basic interrupt handling and functions for turning interrupts on and
157 off.
158
159 @item intr-stubs.S
160 @itemx intr-stubs.h
161 Assembly code for low-level interrupt handling.
162
163 @item synch.c
164 @itemx synch.h
165 Basic synchronization primitives: semaphores, locks, and condition
166 variables.  You will need to use these for synchronization through all
167 four projects.
168
169 @item test.c
170 @itemx test.h
171 Test code.  For project 1, you will replace this file with your test
172 cases.
173
174 @item io.h
175 Functions for I/O port access.  This is mostly used by source code in
176 the @file{devices} directory that you won't have to touch.
177
178 @item mmu.h
179 Functions and macros related to memory management, including page
180 directories and page tables.  This will be more important to you in
181 project 3.  For now, you can ignore it.
182 @end table
183
184 @menu
185 * devices code::                
186 * lib files::                   
187 @end menu
188
189 @node devices code
190 @subsection @file{devices} code
191
192 The basic threaded kernel also includes these files in the
193 @file{devices} directory:
194
195 @table @file
196 @item timer.c
197 @itemx timer.h
198 System timer that ticks, by default, 100 times per second.  You will
199 modify this code in Problem 1-1.
200
201 @item vga.c
202 @itemx vga.h
203 VGA display driver.  Responsible for writing text to the screen.
204 You should have no need to look at this code.  @func{printf} will
205 call into the VGA display driver for you, so there's little reason to
206 call this code yourself.
207
208 @item serial.c
209 @itemx serial.h
210 Serial port driver.  Again, @func{printf} calls this code for you,
211 so you don't need to do so yourself.  Feel free to look through it if
212 you're curious.
213
214 @item disk.c
215 @itemx disk.h
216 Supports reading and writing sectors on up to 4 IDE disks.  This won't
217 actually be used until project 2.
218
219 @item intq.c
220 @itemx intq.h
221 Interrupt queue, for managing a circular queue that both kernel
222 threads and interrupt handlers want to access.  Used by the keyboard
223 and serial drivers.
224 @end table
225
226 @node lib files
227 @subsection @file{lib} files
228
229 Finally, @file{lib} and @file{lib/kernel} contain useful library
230 routines.  (@file{lib/user} will be used by user programs, starting in
231 project 2, but it is not part of the kernel.)  Here's a few more
232 details:
233
234 @table @file
235 @item ctype.h
236 @itemx inttypes.h
237 @itemx limits.h
238 @itemx stdarg.h
239 @itemx stdbool.h
240 @itemx stddef.h
241 @itemx stdint.h
242 @itemx stdio.c
243 @itemx stdio.h
244 @itemx stdlib.c
245 @itemx stdlib.h
246 @itemx string.c
247 @itemx string.h
248 Implementation of the standard C library.  @xref{C99}, for information
249 on a few recently introduced pieces of the C library that you might
250 not have encountered before.  @xref{Unsafe String Functions}, for
251 information on what's been intentionally left out for safety.
252
253 @item debug.c
254 @itemx debug.h
255 Functions and macros to aid debugging.  @xref{Debugging Tools}, for
256 more information.
257
258 @item random.c
259 @itemx random.h
260 Pseudo-random number generator.
261
262 @item round.h
263 Macros for rounding.
264
265 @item syscall-nr.h
266 System call numbers.  Not used until project 2.
267
268 @item kernel/list.c
269 @itemx kernel/list.h
270 Doubly linked list implementation.  Used all over the Pintos code, and
271 you'll probably want to use it a few places yourself in project 1.
272
273 @item kernel/bitmap.c
274 @itemx kernel/bitmap.h
275 Bitmap implementation.  You can use this in your code if you like, but
276 you probably won't have any need for project 1.
277
278 @item kernel/hash.c
279 @itemx kernel/hash.h
280 Hash table implementation.  Likely to come in handy for project 3.
281
282 @item kernel/console.c
283 @itemx kernel/console.h
284 Implements @func{printf} and a few other functions.
285 @end table
286
287 @node Debugging versus Testing
288 @section Debugging versus Testing
289
290 When you're debugging code, it's useful to be able to be able to run a
291 program twice and have it do exactly the same thing.  On second and
292 later runs, you can make new observations without having to discard or
293 verify your old observations.  This property is called
294 ``reproducibility.''  The simulator we use, Bochs, can be set up for
295 reproducibility, and that's the way that @command{pintos} invokes it
296 by default.
297
298 Of course, a simulation can only be reproducible from one run to the
299 next if its input is the same each time.  For simulating an entire
300 computer, as we do, this means that every part of the computer must be
301 the same.  For example, you must use the same disks, the same version
302 of Bochs, and you must not hit any keys on the keyboard (because you
303 could not be sure to hit them at exactly the same point each time)
304 during the runs.
305
306 While reproducibility is useful for debugging, it is a problem for
307 testing thread synchronization, an important part of this project.  In
308 particular, when Bochs is set up for reproducibility, timer interrupts
309 will come at perfectly reproducible points, and therefore so will
310 thread switches.  That means that running the same test several times
311 doesn't give you any greater confidence in your code's correctness
312 than does running it only once.
313
314 So, to make your code easier to test, we've added a feature, called
315 ``jitter,'' to Bochs, that makes timer interrupts come at random
316 intervals, but in a perfectly predictable way.  In particular, if you
317 invoke @command{pintos} with the option @option{-j @var{seed}}, timer
318 interrupts will come at irregularly spaced intervals.  Within a single
319 @var{seed} value, execution will still be reproducible, but timer
320 behavior will change as @var{seed} is varied.  Thus, for the highest
321 degree of confidence you should test your code with many seed values.
322
323 On the other hand, when Bochs runs in reproducible mode, timings are not
324 realistic, meaning that a ``one-second'' delay may be much shorter or
325 even much longer than one second.  You can invoke @command{pintos} with
326 a different option, @option{-r}, to make it set up Bochs for realistic
327 timings, in which a one-second delay should take approximately one
328 second of real time.  Simulation in real-time mode is not reproducible,
329 and options @option{-j} and @option{-r} are mutually exclusive.
330
331 @node Tips
332 @section Tips
333
334 @itemize @bullet
335 @item
336 There should be no busy waiting in any of your solutions to this
337 assignment.  We consider a tight loop that calls @func{thread_yield}
338 to be one form of busy waiting.
339
340 @item
341 Proper synchronization is an important part of the solutions to these
342 problems.  It is tempting to synchronize all your code by turning off
343 interrupts with @func{intr_disable} or @func{intr_set_level}, because
344 this eliminates concurrency and thus the possibility for race
345 conditions, but @strong{don't}.  Instead, use semaphores, locks, and
346 condition variables to solve the bulk of your synchronization
347 problems.  Read the tour section on synchronization
348 (@pxref{Synchronization}) or the comments in @file{threads/synch.c} if
349 you're unsure what synchronization primitives may be used in what
350 situations.
351
352 You might run into a few situations where interrupt disabling is the
353 best way to handle synchronization.  If so, you need to explain your
354 rationale in your design documents.  If you're unsure whether a given
355 situation justifies disabling interrupts, talk to the TAs, who can
356 help you decide on the right thing to do.
357
358 Disabling interrupts can be useful for debugging, if you want to make
359 sure that a section of code is not interrupted.  You should remove
360 debugging code before turning in your project.
361
362 @item
363 All parts of this assignment are required if you intend to earn full
364 credit on this project.  Problem 1-1 (Alarm Clock) could be handy for
365 later projects, but it is not strictly required.  Problems 1-2
366 (Priority Scheduling) and 1-3 (Advanced Scheduler) won't be needed for
367 later projects.
368
369 @item
370 Problem 1-3 (MLFQS) builds on the features you implement in Problem
371 1-2.  You should have Problem 1-2 fully working before you begin to
372 tackle Problem 1-3.
373
374 @item
375 In the past, many groups divided the assignment into pieces, then each
376 group member worked on his or her piece until just before the
377 deadline, at which time the group reconvened to combine their code and
378 submit.  @strong{This is a bad idea.  We do not recommend this
379 approach.}  Groups that do this often find that two changes conflict
380 with each other, requiring lots of last-minute debugging.  Some groups
381 who have done this have turned in code that did not even successfully
382 boot.
383
384 Instead, we recommend integrating your team's changes early and often,
385 using a source code control system such as CVS (@pxref{CVS}) or a
386 group collaboration site such as SourceForge (@pxref{SourceForge}).
387 This is less likely to produce surprises, because everyone can see
388 everyone else's code as it is written, instead of just when it is
389 finished.  These systems also make it possible to review changes and,
390 when a change introduces a bug, drop back to working versions of code.
391
392 @item
393 You should expect to run into bugs that you simply don't understand
394 while working on this and subsequent projects.  When you do, go back
395 and reread the appendix on debugging tools, which is filled with
396 useful debugging tips that should help you to get back up to speed
397 (@pxref{Debugging Tools}).  Be sure to read the section on backtraces
398 (@pxref{Backtraces}), which will help you to get the most out of every
399 kernel panic or assertion failure.
400 @end itemize
401
402 @node Problem 1-1 Alarm Clock
403 @section Problem 1-1: Alarm Clock
404
405 Improve the implementation of the timer device defined in
406 @file{devices/timer.c} by reimplementing @func{timer_sleep}.
407 Threads call @code{timer_sleep(@var{x})} to suspend execution until
408 time has advanced by at least @w{@var{x} timer ticks}.  This is
409 useful for threads that operate in real-time, for example, for
410 blinking the cursor once per second.  There is no requirement that
411 threads start running immediately after waking up; just put them on
412 the ready queue after they have waited for approximately the right
413 amount of time.
414
415 A working implementation of this function is provided.  However, the
416 version provided is poor, because it ``busy waits,'' that is, it spins
417 in a tight loop checking the current time until the current time has
418 advanced far enough.  This is undesirable because it wastes time that
419 could potentially be used more profitably by another thread.  Your
420 solution should not busy wait.
421
422 The argument to @func{timer_sleep} is expressed in timer ticks, not in
423 milliseconds or any another unit.  There are @code{TIMER_FREQ} timer
424 ticks per second, where @code{TIMER_FREQ} is a macro defined in
425 @code{devices/timer.h}.
426
427 Separate functions @func{timer_msleep}, @func{timer_usleep}, and
428 @func{timer_nsleep} do exist for sleeping a specific number of
429 milliseconds, microseconds, or nanoseconds, respectively, but these will
430 call @func{timer_sleep} automatically when necessary.  You do not need
431 to modify them.
432
433 If your delays seem too short or too long, reread the explanation of the
434 @option{-r} option to @command{pintos} (@pxref{Debugging versus
435 Testing}).
436
437 @node Problem 1-2 Priority Scheduling
438 @section Problem 1-2: Priority Scheduling
439
440 Implement priority scheduling in Pintos.  Priority scheduling is a key
441 building block for real-time systems.  Implement functions
442 @func{thread_set_priority} to set the priority of the running thread
443 and @func{thread_get_priority} to get the running thread's priority.
444 (This API only allows a thread to examine and modify its own
445 priority.)  There are already prototypes for these functions in
446 @file{threads/thread.h}, which you should not change.
447
448 Thread priority ranges from @code{PRI_MIN} (0) to @code{PRI_MAX} (59).
449 The initial thread priority is passed as an argument to
450 @func{thread_create}.  If there's no reason to choose another
451 priority, use @code{PRI_DEFAULT} (29).  The @code{PRI_} macros are
452 defined in @file{threads/thread.h}, and you should not change their
453 values.
454
455 When a thread is added to the ready list that has a higher priority
456 than the currently running thread, the current thread should
457 immediately yield the processor to the new thread.  Similarly, when
458 threads are waiting for a lock, semaphore or condition variable, the
459 highest priority waiting thread should be woken up first.  A thread
460 may raise or lower its own priority at any time, but lowering its
461 priority such that it no longer has the highest priority must cause it
462 to immediately yield the CPU.
463
464 One issue with priority scheduling is ``priority inversion'': if a
465 high priority thread needs to wait for a low priority thread (for
466 instance, for a lock held by a low priority thread), and a middle priority
467 thread is on the ready list, then the high priority thread will never
468 get the CPU because the low priority thread will not get any CPU time.
469 A partial fix for this problem is to have the waiting thread
470 ``donate'' its priority to the low priority thread while it is holding
471 the lock, then recall the donation once it has acquired the lock.
472 Implement this fix.
473
474 You will need to account for all different orders in which priority
475 donation and inversion can occur.  Be sure to handle multiple
476 donations, in which multiple priorities are donated to a thread.  You
477 must also handle nested donation: given high, medium, and low priority
478 threads @var{H}, @var{M}, and @var{L}, respectively, if @var{H} is
479 waiting on a lock that @var{M} holds and @var{M} is waiting on a lock
480 that @var{L} holds, then both @var{M} and @var{L} should be boosted to
481 @var{H}'s priority.
482
483 You only need to implement priority donation when a thread is waiting
484 for a lock held by a lower-priority thread.  You do not need to
485 implement this fix for semaphores or condition variables
486 although you are welcome to do so.  However, you do need to implement
487 priority scheduling in all cases.
488
489 @node Problem 1-3 Advanced Scheduler
490 @section Problem 1-3: Advanced Scheduler
491
492 Implement Solaris's multilevel feedback queue scheduler (MLFQS) to
493 reduce the average response time for running jobs on your system.
494 @xref{Multilevel Feedback Scheduling}, for a detailed description of
495 the MLFQS requirements.
496
497 Demonstrate that your scheduling algorithm reduces response time
498 relative to the original Pintos scheduling algorithm (round robin) for
499 at least one workload of your own design (i.e.@: in addition to the
500 provided test).
501
502 You must write your code so that we can turn the MLFQS on and off at
503 compile time.  By default, it must be off, but we must be able to turn
504 it on by inserting the line @code{#define MLFQS 1} in
505 @file{constants.h}.  @xref{Conditional Compilation}, for details.
506
507 @node Threads FAQ
508 @section FAQ
509
510 @enumerate 1
511 @item
512 @b{I am adding a new @file{.h} or @file{.c} file.  How do I fix the
513 @file{Makefile}s?}@anchor{Adding c or h Files}
514
515 To add a @file{.c} file, edit the top-level @file{Makefile.build}.
516 You'll want to add your file to variable @samp{@var{dir}_SRC}, where
517 @var{dir} is the directory where you added the file.  For this
518 project, that means you should add it to @code{threads_SRC}, or
519 possibly @code{devices_SRC} if you put in the @file{devices}
520 directory.  Then run @code{make}.  If your new file doesn't get
521 compiled, run @code{make clean} and then try again.
522
523 When you modify the top-level @file{Makefile.build}, the modified
524 version should be automatically copied to
525 @file{threads/build/Makefile} when you re-run make.  The opposite is
526 not true, so any changes will be lost the next time you run @code{make
527 clean} from the @file{threads} directory.  Therefore, you should
528 prefer to edit @file{Makefile.build} (unless your changes are meant to
529 be truly temporary).
530
531 There is no need to edit the @file{Makefile}s to add a @file{.h} file.
532
533 @item
534 @b{How do I write my test cases?}
535
536 Test cases should be replacements for the existing @file{test.c}
537 file.  Put them in a @file{threads/testcases} directory.
538 @xref{TESTCASE}, for more information.
539
540 @item
541 @b{Why can't I disable interrupts?}
542
543 Turning off interrupts should only be done for short amounts of time,
544 or else you end up losing important things such as disk or input
545 events.  Turning off interrupts also increases the interrupt handling
546 latency, which can make a machine feel sluggish if taken too far.
547 Therefore, in general, setting the interrupt level should be used
548 sparingly.  Also, any synchronization problem can be easily solved by
549 turning interrupts off, since while interrupts are off, there is no
550 concurrency, so there's no possibility for race conditions.
551
552 To make sure you understand concurrency well, we are discouraging you
553 from taking this shortcut at all in your solution.  If you are unable
554 to solve a particular synchronization problem with semaphores, locks,
555 or conditions, or think that they are inadequate for a particular
556 reason, you may turn to disabling interrupts.  If you want to do this,
557 we require in your design document a complete justification and
558 scenario (i.e.@: exact sequence of events) to show why interrupt
559 manipulation is the best solution.  If you are unsure, the TAs can
560 help you determine if you are using interrupts too haphazardly.  We
561 want to emphasize that there are only limited cases where this is
562 appropriate.
563
564 You might find @file{devices/intq.h} and its users to be an
565 inspiration or source of rationale.
566
567 @item
568 @b{Where might interrupt-level manipulation be appropriate?}
569
570 You might find it necessary in some solutions to the Alarm problem.
571
572 You might want it at one small point for the priority scheduling
573 problem.  Note that it is not required to use interrupts for these
574 problems.  There are other, equally correct solutions that do not
575 require interrupt manipulation.  However, if you do manipulate
576 interrupts and @strong{correctly and fully document it} in your design
577 document, we will allow limited use of interrupt disabling.
578
579 @item
580 @b{What does ``warning: no previous prototype for `@var{function}''
581 mean?}
582
583 It means that you defined a non-@code{static} function without
584 preceding it by a prototype.  Because non-@code{static} functions are
585 intended for use by other @file{.c} files, for safety they should be
586 prototyped in a header file included before their definition.  To fix
587 the problem, add a prototype in a header file that you include, or, if
588 the function isn't actually used by other @file{.c} files, make it
589 @code{static}.
590 @end enumerate
591
592 @menu
593 * Problem 1-1 Alarm Clock FAQ::  
594 * Problem 1-2 Priority Scheduling FAQ::  
595 * Problem 1-3 Advanced Scheduler FAQ::  
596 @end menu
597
598 @node Problem 1-1 Alarm Clock FAQ
599 @subsection Problem 1-1: Alarm Clock FAQ
600
601 @enumerate 1
602 @item
603 @b{Why can't I use most synchronization primitives in an interrupt
604 handler?}
605
606 As you've discovered, you cannot sleep in an external interrupt
607 handler.  Since many lock, semaphore, and condition variable functions
608 attempt to sleep, you won't be able to call those in
609 @func{timer_interrupt}.  You may still use those that never sleep.
610
611 Having said that, you need to make sure that global data does not get
612 updated by multiple threads simultaneously executing
613 @func{timer_sleep}.  Here are some pieces of information to think
614 about:
615
616 @enumerate a
617 @item
618 Interrupts are turned off while @func{timer_interrupt} runs.  This
619 means that @func{timer_interrupt} will not be interrupted by a
620 thread running in @func{timer_sleep}.
621
622 @item
623 A thread in @func{timer_sleep}, however, can be interrupted by a
624 call to @func{timer_interrupt}, except when that thread has turned
625 off interrupts.
626
627 @item
628 Examples of synchronization mechanisms have been presented in lecture.
629 Going over these examples should help you understand when each type is
630 useful or needed.  @xref{Synchronization}, for specific information
631 about synchronization in Pintos.
632 @end enumerate
633
634 @item
635 @b{What about timer overflow due to the fact that times are defined as
636 integers? Do I need to check for that?}
637
638 Don't worry about the possibility of timer values overflowing.  Timer
639 values are expressed as signed 63-bit numbers, which at 100 ticks per
640 second should be good for almost 2,924,712,087 years.
641
642 @item
643 @b{The test program mostly works but reports a few out-of-order
644 wake ups.  I think it's a problem in the test program.  What gives?}
645 @anchor{Out of Order 1-1}
646
647 This test is inherently full of race conditions.  On a real system it
648 wouldn't work perfectly all the time either.  There are a few ways you
649 can help it work more reliably:
650
651 @itemize @bullet
652 @item
653 Make time slices longer by increasing @code{TIME_SLICE} in
654 @file{timer.c} to a large value, such as 100.
655
656 @item
657 Make the timer tick more slowly by decreasing @code{TIMER_FREQ} in
658 @file{timer.h} to its minimum value of 19.
659 @end itemize
660
661 The former two changes are only desirable for testing problem 1-1 and
662 possibly 1-2.  You should revert them before working on other parts
663 of the project or turn in the project.  We will test problem 1-1 with
664 @code{TIME_SLICE} set to 100 and @code{TIMER_FREQ} set to 19, but we
665 will leave them at their defaults for all the other problems.
666
667 @item
668 @b{Should @file{p1-1.c} be expected to work with the MLFQS turned on?}
669
670 No.  The MLFQS will adjust priorities, changing thread ordering.
671 @end enumerate
672
673 @node Problem 1-2 Priority Scheduling FAQ
674 @subsection Problem 1-2: Priority Scheduling FAQ
675
676 @enumerate 1
677 @item
678 @b{Doesn't the priority scheduling lead to starvation? Or do I have to
679 implement some sort of aging?}
680
681 It is true that strict priority scheduling can lead to starvation
682 because thread may not run if a higher-priority thread is runnable.
683 In this problem, don't worry about starvation or any sort of aging
684 technique.  Problem 4 will introduce a mechanism for dynamically
685 changing thread priorities.
686
687 This sort of scheduling is valuable in real-time systems because it
688 offers the programmer more control over which jobs get processing
689 time.  High priorities are generally reserved for time-critical
690 tasks. It's not ``fair,'' but it addresses other concerns not
691 applicable to a general-purpose operating system.
692
693 @item
694 @b{After a lock has been released, does the program need to switch to
695 the highest priority thread that needs the lock (assuming that its
696 priority is higher than that of the current thread)?}
697
698 When a lock is released, the highest priority thread waiting for that
699 lock should be unblocked and put on the ready to run list.  The
700 scheduler should then run the highest priority thread on the ready
701 list.
702
703 @item
704 @b{If a thread calls @func{thread_yield} and then it turns out that
705 it has higher priority than any other threads, does the high-priority
706 thread continue running?}
707
708 Yes.  If there is a single highest-priority thread, it continues
709 running until it blocks or finishes, even if it calls
710 @func{thread_yield}.
711
712 @item
713 @b{If the highest priority thread is added to the ready to run list it
714 should start execution immediately.  Is it immediate enough if I
715 wait until next timer interrupt occurs?}
716
717 The highest priority thread should run as soon as it is runnable,
718 preempting whatever thread is currently running.
719
720 @item
721 @b{What happens to the priority of the donating thread?  Do the priorities
722 get swapped?}
723
724 No.  Priority donation only changes the priority of the low-priority
725 thread.  The donating thread's priority stays unchanged.  Also note
726 that priorities aren't additive: if thread A (with priority 5) donates
727 to thread B (with priority 3), then B's new priority is 5, not 8.
728
729 @item 
730 @b{Can a thread's priority be changed while it is sitting on the ready
731 queue?}
732
733 Yes.  Consider this case: low-priority thread L currently has a lock
734 that high-priority thread H wants.  H donates its priority to L (the
735 lock holder).  L finishes with the lock, and then loses the CPU and is
736 moved to the ready queue.  Now L's old priority is restored while it
737 is in the ready queue.
738
739 @item
740 @b{Can a thread's priority change while it is sitting on the queue of a
741 semaphore?}
742
743 Yes.  Same scenario as above except L gets blocked waiting on a new
744 lock when H restores its priority.
745
746 @item
747 @b{Why is @file{p1-2.c}'s FIFO test skipping some threads?  I know my
748 scheduler is round-robin'ing them like it's supposed to.   Our output
749 starts out okay, but toward the end it starts getting out of order.}
750
751 The usual problem is that the serial output buffer fills up.  This is
752 causing serial_putc() to block in thread @var{A}, so that thread
753 @var{B} is scheduled.  Thread @var{B} immediately tries to do output
754 of its own and blocks on the serial lock (which is held by thread
755 @var{A}).  Now that we've wasted some time in scheduling and locking,
756 typically some characters have been drained out of the serial buffer
757 by the interrupt handler, so thread @var{A} can continue its output.
758 After it finishes, though, some other thread (not @var{B}) is
759 scheduled, because thread @var{B} was already scheduled while we
760 waited for the buffer to drain.
761
762 There's at least one other possibility.  Context switches are being
763 invoked by the test when it explicitly calls @func{thread_yield}.
764 However, the time slice timer is still alive and so, every tick (by
765 default), a thread gets switched out (caused by @func{timer_interrupt}
766 calling @func{intr_yield_on_return}) before it gets a chance to run
767 @func{printf}, effectively skipping it.  If we use a different jitter
768 value, the same behavior is seen where a thread gets started and
769 switched out completely.
770
771 Normally you can fix these problems using the same techniques
772 suggested on problem 1-1 (@pxref{Out of Order 1-1}).
773
774 @item
775 @b{What happens when a thread is added to the ready list which has
776 higher priority than the currently running thread?}
777
778 The correct behavior is to immediately yield the processor.  Your
779 solution must act this way.
780
781 @item
782 @b{What should @func{thread_get_priority} return in a thread while
783 its priority has been increased by a donation?}
784
785 The higher (donated) priority.
786
787 @item
788 @b{Should @file{p1-2.c} be expected to work with the MLFQS turned on?}
789
790 No.  The MLFQS will adjust priorities, changing thread ordering.
791
792 @item
793 @b{@func{printf} in @func{sema_up} or @func{sema_down} makes the
794 system reboot!}
795
796 Yes.  These functions are called before @func{printf} is ready to go.
797 You could add a global flag initialized to false and set it to true
798 just before the first @func{printf} in @func{main}.  Then modify
799 @func{printf} itself to return immediately if the flag isn't set.
800 @end enumerate
801
802 @node Problem 1-3 Advanced Scheduler FAQ
803 @subsection Problem 1-3: Advanced Scheduler FAQ
804
805 @enumerate 1
806 @item
807 @b{What is the interval between timer interrupts?}
808
809 Timer interrupts occur @code{TIMER_FREQ} times per second.  You can
810 adjust this value by editing @file{devices/timer.h}.  The default is
811 100 Hz.
812
813 You can also adjust the number of timer ticks per time slice by
814 modifying @code{TIME_SLICE} in @file{devices/timer.c}.
815
816 @item
817 @b{Do I have to modify the dispatch table?}
818
819 No, although you are allowed to. It is possible to complete
820 this problem (i.e.@: demonstrate response time improvement)
821 without doing so.
822
823 @item
824 @b{When the scheduler changes the priority of a thread, how does this
825 affect priority donation?}
826
827 Short (official) answer: Don't worry about it. Your priority donation
828 code may assume static priority assignment.
829
830 Longer (unofficial) opinion: If you wish to take this into account,
831 however, your design may end up being ``cleaner.''  You have
832 considerable freedom in what actually takes place. I believe what
833 makes the most sense is for scheduler changes to affect the
834 ``original'' (non-donated) priority.  This change may actually be
835 masked by the donated priority.  Priority changes should only
836 propagate with donations, not ``backwards'' from donees to donors.
837
838 @item
839 @b{What is meant by ``static priority''?}
840
841 Once thread A has donated its priority to thread B, if thread A's
842 priority changes (due to the scheduler) while the donation still
843 exists, you do not have to change thread B's donated priority.
844 However, you are free to do so.
845
846 @item
847 @b{Do I have to make my dispatch table user-configurable?}
848
849 No.  Hard-coding the dispatch table values is fine.
850 @end enumerate