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