1 @node Project 1--Threads
2 @chapter Project 1: Threads
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.
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.
12 Before you read the description of this project, you should read all of
13 the following sections: @ref{Introduction}, @ref{Coding Standards},
14 @ref{Debugging Tools}, and @ref{Development Tools}. You should at least
15 skim the material from @ref{Pintos Loading} through @ref{Memory
16 Allocation}, especially @ref{Synchronization}. To complete this project
17 you will also need to read @ref{4.4BSD Scheduler}.
20 * Project 1 Background::
21 * Project 1 Requirements::
25 @node Project 1 Background
30 * Understanding Threads::
31 * Project 1 Source Files::
32 * Project 1 Synchronization::
33 * Development Suggestions::
36 @node Understanding Threads
37 @subsection Understanding Threads
39 The first step is to read and understand the code for the initial thread
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 optimization
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
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}.
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
70 Synchronization primitives can force context switches when one
71 thread needs to wait for another thread to do something.
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.
79 Using the GDB debugger, slowly trace through a context
80 switch to see what happens (@pxref{GDB}). You can set a
81 breakpoint on @func{schedule} to start out, and then
82 single-step from there.@footnote{GDB might tell you that
83 @func{schedule} doesn't exist, which is arguably a GDB bug.
84 You can work around this by setting the breakpoint by filename and
85 line number, e.g.@: @code{break thread.c:@var{ln}} where @var{ln} is
86 the line number of the first declaration in @func{schedule}.} Be sure
87 to keep track of each thread's address
88 and state, and what procedures are on the call stack for each thread.
89 You will notice that when one thread calls @func{switch_threads},
90 another thread starts running, and the first thing the new thread does
91 is to return from @func{switch_threads}. You will understand the thread
92 system once you understand why and how the @func{switch_threads} that
93 gets called is different from the @func{switch_threads} that returns.
94 @xref{Thread Switching}, for more information.
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}).
104 @node Project 1 Source Files
105 @subsection Source Files
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
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.
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.
129 Jumps to @func{main}.
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.
140 Basic thread support. Much of your work will take place in these files.
141 @file{thread.h} defines @struct{thread}, which you are likely to modify
142 in all four projects. See @ref{struct thread} and @ref{Threads} for
147 Assembly language routine for switching threads. Already discussed
148 above. @xref{Thread Functions}, for more information.
152 Page allocator, which hands out system memory in multiples of 4 kB
153 pages. @xref{Page Allocator}, for more information.
157 A simple implementation of @func{malloc} and @func{free} for
158 the kernel. @xref{Block Allocator}, for more information.
162 Basic interrupt handling and functions for turning interrupts on and
163 off. @xref{Interrupt Handling}, for more information.
167 Assembly code for low-level interrupt handling. @xref{Interrupt
168 Infrastructure}, for more information.
172 Basic synchronization primitives: semaphores, locks, condition
173 variables, and optimization barriers. You will need to use these for
174 synchronization in all
175 four projects. @xref{Synchronization}, for more information.
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.
183 Functions and macros for working with virtual addresses and page table
184 entries. These will be more important to you in project 3. For now,
188 Macros that define a few bits in the 80@var{x}86 ``flags'' register.
189 Probably of no interest. See @bibref{IA32-v1}, section 3.4.3, ``EFLAGS
190 Register,'' for more information.
199 @subsubsection @file{devices} code
201 The basic threaded kernel also includes these files in the
202 @file{devices} directory:
207 System timer that ticks, by default, 100 times per second. You will
208 modify this code in this project.
212 VGA display driver. Responsible for writing text to the screen.
213 You should have no need to look at this code. @func{printf}
214 calls into the VGA display driver for you, so there's little reason to
215 call this code yourself.
219 Serial port driver. Again, @func{printf} calls this code for you,
220 so you don't need to do so yourself.
221 It handles serial input by passing it to the input layer (see below).
225 Supports reading and writing sectors on up to 4 IDE disks. This won't
226 actually be used until project 2.
230 Keyboard driver. Handles keystrokes passing them to the input layer
235 Input layer. Queues input characters passed along by the keyboard or
240 Interrupt queue, for managing a circular queue that both kernel
241 threads and interrupt handlers want to access. Used by the keyboard
246 @subsubsection @file{lib} files
248 Finally, @file{lib} and @file{lib/kernel} contain useful library
249 routines. (@file{lib/user} will be used by user programs, starting in
250 project 2, but it is not part of the kernel.) Here's a few more
267 A subset of the standard C library. @xref{C99}, for
269 on a few recently introduced pieces of the C library that you might
270 not have encountered before. @xref{Unsafe String Functions}, for
271 information on what's been intentionally left out for safety.
275 Functions and macros to aid debugging. @xref{Debugging Tools}, for
280 Pseudo-random number generator.
286 System call numbers. Not used until project 2.
290 Doubly linked list implementation. Used all over the Pintos code, and
291 you'll probably want to use it a few places yourself in project 1.
293 @item kernel/bitmap.c
294 @itemx kernel/bitmap.h
295 Bitmap implementation. You can use this in your code if you like, but
296 you probably won't have any need for it in project 1.
300 Hash table implementation. Likely to come in handy for project 3.
302 @item kernel/console.c
303 @itemx kernel/console.h
305 Implements @func{printf} and a few other functions.
308 @node Project 1 Synchronization
309 @subsection Synchronization
311 Proper synchronization is an important part of the solutions to these
312 problems. Any synchronization problem can be easily solved by turning
313 interrupts off: while interrupts are off, there is no concurrency, so
314 there's no possibility for race conditions. Therefore, it's tempting to
315 solve all synchronization problems this way, but @strong{don't}.
316 Instead, use semaphores, locks, and condition variables to solve the
317 bulk of your synchronization problems. Read the tour section on
318 synchronization (@pxref{Synchronization}) or the comments in
319 @file{threads/synch.c} if you're unsure what synchronization primitives
320 may be used in what situations.
322 In the Pintos projects, the only class of problem best solved by
323 disabling interrupts is coordinating data shared between a kernel thread
324 and an interrupt handler. Because interrupt handlers can't sleep, they
325 can't acquire locks. This means that data shared between kernel threads
326 and an interrupt handler must be protected within a kernel thread by
327 turning off interrupts.
329 This project only requires accessing a little bit of thread state from
330 interrupt handlers. For the alarm clock, the timer interrupt needs to
331 wake up sleeping threads. In the advanced scheduler, the timer
332 interrupt needs to access a few global and per-thread variables. When
333 you access these variables from kernel threads, you will need to disable
334 interrupts to prevent the timer interrupt from interfering.
336 When you do turn off interrupts, take care to do so for the least amount
337 of code possible, or you can end up losing important things such as
338 timer ticks or input events. Turning off interrupts also increases the
339 interrupt handling latency, which can make a machine feel sluggish if
342 The synchronization primitives themselves in @file{synch.c} are
343 implemented by disabling interrupts. You may need to increase the
344 amount of code that runs with interrupts disabled here, but you should
345 still try to keep it to a minimum.
347 Disabling interrupts can be useful for debugging, if you want to make
348 sure that a section of code is not interrupted. You should remove
349 debugging code before turning in your project. (Don't just comment it
350 out, because that can make the code difficult to read.)
352 There should be no busy waiting in your submission. A tight loop that
353 calls @func{thread_yield} is one form of busy waiting.
355 @node Development Suggestions
356 @subsection Development Suggestions
358 In the past, many groups divided the assignment into pieces, then each
359 group member worked on his or her piece until just before the
360 deadline, at which time the group reconvened to combine their code and
361 submit. @strong{This is a bad idea. We do not recommend this
362 approach.} Groups that do this often find that two changes conflict
363 with each other, requiring lots of last-minute debugging. Some groups
364 who have done this have turned in code that did not even compile or
365 boot, much less pass any tests.
367 Instead, we recommend integrating your team's changes early and often,
368 using a source code control system such as CVS (@pxref{CVS}) or a
369 group collaboration site such as SourceForge (@pxref{SourceForge}).
370 This is less likely to produce surprises, because everyone can see
371 everyone else's code as it is written, instead of just when it is
372 finished. These systems also make it possible to review changes and,
373 when a change introduces a bug, drop back to working versions of code.
375 You should expect to run into bugs that you simply don't understand
376 while working on this and subsequent projects. When you do,
377 reread the appendix on debugging tools, which is filled with
378 useful debugging tips that should help you to get back up to speed
379 (@pxref{Debugging Tools}). Be sure to read the section on backtraces
380 (@pxref{Backtraces}), which will help you to get the most out of every
381 kernel panic or assertion failure.
383 @node Project 1 Requirements
384 @section Requirements
387 * Project 1 Design Document::
389 * Priority Scheduling::
390 * Advanced Scheduler::
393 @node Project 1 Design Document
394 @subsection Design Document
396 Before you turn in your project, you must copy @uref{threads.tmpl, , the
397 project 1 design document template} into your source tree under the name
398 @file{pintos/src/threads/DESIGNDOC} and fill it in. We recommend that
399 you read the design document template before you start working on the
400 project. @xref{Project Documentation}, for a sample design document
401 that goes along with a fictitious project.
404 @subsection Alarm Clock
406 Reimplement @func{timer_sleep}, defined in @file{devices/timer.c}.
407 Although a working implementation is provided, it ``busy waits,'' that
408 is, it spins in a loop checking the current time and calling
409 @func{thread_yield} until enough time has gone by. Reimplement it to
412 @deftypefun void timer_sleep (int64_t @var{ticks})
413 Suspends execution of the calling thread until time has advanced by at
414 least @w{@var{x} timer ticks}. Unless the system is otherwise idle, the
415 thread need not wake up after exactly @var{x} ticks. Just put it on
416 the ready queue after they have waited for the right amount of time.
418 @func{timer_sleep} is useful for threads that operate in real-time,
419 e.g.@: for blinking the cursor once per second.
421 The argument to @func{timer_sleep} is expressed in timer ticks, not in
422 milliseconds or any another unit. There are @code{TIMER_FREQ} timer
423 ticks per second, where @code{TIMER_FREQ} is a macro defined in
424 @code{devices/timer.h}. The default value is 100. We don't recommend
425 changing this value, because any change is likely to cause many of
429 Separate functions @func{timer_msleep}, @func{timer_usleep}, and
430 @func{timer_nsleep} do exist for sleeping a specific number of
431 milliseconds, microseconds, or nanoseconds, respectively, but these will
432 call @func{timer_sleep} automatically when necessary. You do not need
435 If your delays seem too short or too long, reread the explanation of the
436 @option{-r} option to @command{pintos} (@pxref{Debugging versus
439 The alarm clock implementation is not needed for later projects,
440 although it could be useful for project 4.
442 @node Priority Scheduling
443 @subsection Priority Scheduling
445 Implement priority scheduling in Pintos.
446 When a thread is added to the ready list that has a higher priority
447 than the currently running thread, the current thread should
448 immediately yield the processor to the new thread. Similarly, when
449 threads are waiting for a lock, semaphore, or condition variable, the
450 highest priority waiting thread should be awakened first. A thread
451 may raise or lower its own priority at any time, but lowering its
452 priority such that it no longer has the highest priority must cause it
453 to immediately yield the CPU.
455 Thread priorities range from @code{PRI_MIN} (0) to @code{PRI_MAX} (63).
456 Lower numbers correspond to lower priorities, so that priority 0
457 is the lowest priority and priority 63 is the highest.
458 The initial thread priority is passed as an argument to
459 @func{thread_create}. If there's no reason to choose another
460 priority, use @code{PRI_DEFAULT} (31). The @code{PRI_} macros are
461 defined in @file{threads/thread.h}, and you should not change their
464 One issue with priority scheduling is ``priority inversion''. Consider
465 high, medium, and low priority threads @var{H}, @var{M}, and @var{L},
466 respectively. If @var{H} needs to wait for @var{L} (for instance, for a
467 lock held by @var{L}), and @var{M} is on the ready list, then @var{H}
468 will never get the CPU because the low priority thread will not get any
469 CPU time. A partial fix for this problem is for @var{H} to ``donate''
470 its priority to @var{L} while @var{L} is holding the lock, then recall
471 the donation once @var{L} releases (and thus @var{H} acquires) the lock.
473 Implement priority donation. You will need to account for all different
474 situations in which priority donation is required. Be sure to handle
475 multiple donations, in which multiple priorities are donated to a single
476 thread. You must also handle nested donation: if @var{H} is waiting on
477 a lock that @var{M} holds and @var{M} is waiting on a lock that @var{L}
478 holds, then both @var{M} and @var{L} should be boosted to @var{H}'s
479 priority. If necessary, you may impose a reasonable limit on depth of
480 nested priority donation, such as 8 levels.
482 You must implement priority donation for locks. You need not
483 implement priority donation for semaphores or condition variables
484 (but you are welcome to do so). You do need to implement
485 priority scheduling in all cases.
487 Finally, implement the following functions that allow a thread to
488 examine and modify its own priority. Skeletons for these functions are
489 provided in @file{threads/thread.c}.
491 @deftypefun void thread_set_priority (int @var{new_priority})
492 Sets the current thread's priority to @var{new_priority}. If the
493 current thread no longer has the highest priority, yields.
496 @deftypefun int thread_get_priority (void)
497 Returns the current thread's priority. In the presence of priority
498 donation, returns the higher (donated) priority.
501 You need not provide any interface to allow a thread to directly modify
502 other threads' priorities.
504 The priority scheduler is not used in any later project.
506 @node Advanced Scheduler
507 @subsection Advanced Scheduler
509 Implement a multilevel feedback queue scheduler similar to the
510 4.4@acronym{BSD} scheduler to
511 reduce the average response time for running jobs on your system.
512 @xref{4.4BSD Scheduler}, for detailed requirements.
514 Like the priority scheduler, the advanced scheduler chooses the thread
515 to run based on priorities. However, the advanced scheduler does not do
516 priority donation. Thus, we recommend that you have the priority
517 scheduler working, except possibly for priority donation, before you
518 start work on the advanced scheduler.
520 You must write your code to allow us to choose a scheduling algorithm
521 policy at Pintos startup time. By default, the priority scheduler
522 must be active, but we must be able to choose the 4.4@acronym{BSD}
524 with the @option{-mlfqs} kernel option. Passing this
525 option sets @code{thread_mlfqs}, declared in @file{threads/thread.h}, to
526 true when the options are parsed by @func{parse_options}, which happens
527 midway through @func{main}.
529 When the 4.4@acronym{BSD} scheduler is enabled, threads no longer
530 directly control their own priorities. The @var{priority} argument to
531 @func{thread_create} should be ignored, as well as any calls to
532 @func{thread_set_priority}, and @func{thread_get_priority} should return
533 the thread's current priority as set by the scheduler.
535 The advanced scheduler is not used in any later project.
541 @item How much code will I need to write?
543 Here's a summary of our reference solution, produced by the
544 @command{diffstat} program. The final row gives total lines inserted
545 and deleted; a changed line counts as both an insertion and a deletion.
547 The reference solution represents just one possible solution. Many
548 other solutions are also possible and many of those differ greatly from
549 the reference solution. Some excellent solutions may not modify all the
550 files modified by the reference solution, and some may modify files not
551 modified by the reference solution.
554 devices/timer.c | 42 +++++-
555 threads/fixed-point.h | 120 ++++++++++++++++++
556 threads/synch.c | 88 ++++++++++++-
557 threads/thread.c | 196 ++++++++++++++++++++++++++----
558 threads/thread.h | 23 +++
559 5 files changed, 440 insertions(+), 29 deletions(-)
562 @file{fixed-point.h} is a new file added by the reference solution.
564 @item How do I update the @file{Makefile}s when I add a new source file?
566 @anchor{Adding Source Files}
567 To add a @file{.c} file, edit the top-level @file{Makefile.build}.
568 Add the new file to variable @samp{@var{dir}_SRC}, where
569 @var{dir} is the directory where you added the file. For this
570 project, that means you should add it to @code{threads_SRC} or
571 @code{devices_SRC}. Then run @code{make}. If your new file
573 compiled, run @code{make clean} and then try again.
575 When you modify the top-level @file{Makefile.build} and re-run
576 @command{make}, the modified
577 version should be automatically copied to
578 @file{threads/build/Makefile}. The converse is
579 not true, so any changes will be lost the next time you run @code{make
580 clean} from the @file{threads} directory. Unless your changes are
581 truly temporary, you should prefer to edit @file{Makefile.build}.
583 A new @file{.h} file does not require editing the @file{Makefile}s.
585 @item What does @code{warning: no previous prototype for `@var{func}'} mean?
587 It means that you defined a non-@code{static} function without
588 preceding it by a prototype. Because non-@code{static} functions are
589 intended for use by other @file{.c} files, for safety they should be
590 prototyped in a header file included before their definition. To fix
591 the problem, add a prototype in a header file that you include, or, if
592 the function isn't actually used by other @file{.c} files, make it
595 @item What is the interval between timer interrupts?
597 Timer interrupts occur @code{TIMER_FREQ} times per second. You can
598 adjust this value by editing @file{devices/timer.h}. The default is
601 We don't recommend changing this value, because any changes are likely
602 to cause many of the tests to fail.
604 @item How long is a time slice?
606 There are @code{TIME_SLICE} ticks per time slice. This macro is
607 declared in @file{threads/thread.c}. The default is 4 ticks.
609 We don't recommend changing this value, because any changes are likely
610 to cause many of the tests to fail.
612 @item How do I run the tests?
616 @item Why do I get a test failure in @func{pass}?
618 @anchor{The pass function fails}
619 You are probably looking at a backtrace that looks something like this:
622 0xc0108810: debug_panic (lib/kernel/debug.c:32)
623 0xc010a99f: pass (tests/threads/tests.c:93)
624 0xc010bdd3: test_mlfqs_load_1 (...threads/mlfqs-load-1.c:33)
625 0xc010a8cf: run_test (tests/threads/tests.c:51)
626 0xc0100452: run_task (threads/init.c:283)
627 0xc0100536: run_actions (threads/init.c:333)
628 0xc01000bb: main (threads/init.c:137)
631 This is just confusing output from the @command{backtrace} program. It
632 does not actually mean that @func{pass} called @func{debug_panic}. In
633 fact, @func{fail} called @func{debug_panic} (via the @func{PANIC}
634 macro). GCC knows that @func{debug_panic} does not return, because it
635 is declared @code{NO_RETURN} (@pxref{Function and Parameter
636 Attributes}), so it doesn't include any code in @func{pass} to take
637 control when @func{debug_panic} returns. This means that the return
638 address on the stack looks like it is at the beginning of the function
639 that happens to follow @func{fail} in memory, which in this case happens
642 @xref{Backtraces}, for more information.
644 @item How do interrupts get re-enabled in the new thread following @func{schedule}?
646 Every path into @func{schedule} disables interrupts. They eventually
647 get re-enabled by the next thread to be scheduled. Consider the
648 possibilities: the new thread is running in @func{switch_thread} (but
649 see below), which is called by @func{schedule}, which is called by one
650 of a few possible functions:
654 @func{thread_exit}, but we'll never switch back into such a thread, so
658 @func{thread_yield}, which immediately restores the interrupt level upon
659 return from @func{schedule}.
662 @func{thread_block}, which is called from multiple places:
666 @func{sema_down}, which restores the interrupt level before returning.
669 @func{idle}, which enables interrupts with an explicit assembly STI
673 @func{wait} in @file{devices/intq.c}, whose callers are responsible for
674 re-enabling interrupts.
678 There is a special case when a newly created thread runs for the first
679 time. Such a thread calls @func{intr_enable} as the first action in
680 @func{kernel_thread}, which is at the bottom of the call stack for every
681 kernel thread but the first.
686 * Priority Scheduling FAQ::
687 * Advanced Scheduler FAQ::
690 @node Alarm Clock FAQ
691 @subsection Alarm Clock FAQ
694 @item Do I need to account for timer values overflowing?
696 Don't worry about the possibility of timer values overflowing. Timer
697 values are expressed as signed 64-bit numbers, which at 100 ticks per
698 second should be good for almost 2,924,712,087 years. By then, we
699 expect Pintos to have been phased out of the CS 140 curriculum.
702 @node Priority Scheduling FAQ
703 @subsection Priority Scheduling FAQ
706 @item Doesn't priority scheduling lead to starvation?
708 Yes, strict priority scheduling can lead to starvation
709 because a thread will not run if any higher-priority thread is runnable.
710 The advanced scheduler introduces a mechanism for dynamically
711 changing thread priorities.
713 Strict priority scheduling is valuable in real-time systems because it
714 offers the programmer more control over which jobs get processing
715 time. High priorities are generally reserved for time-critical
716 tasks. It's not ``fair,'' but it addresses other concerns not
717 applicable to a general-purpose operating system.
719 @item What thread should run after a lock has been released?
721 When a lock is released, the highest priority thread waiting for that
722 lock should be unblocked and put on the list of ready threads. The
723 scheduler should then run the highest priority thread on the ready
726 @item If the highest-priority thread yields, does it continue running?
728 Yes. If there is a single highest-priority thread, it continues
729 running until it blocks or finishes, even if it calls
731 If multiple threads have the same highest priority,
732 @func{thread_yield} should switch among them in ``round robin'' order.
734 @item What happens to the priority of a donating thread?
736 Priority donation only changes the priority of the donee
737 thread. The donor thread's priority is unchanged.
738 Priority donation is not additive: if thread @var{A} (with priority 5) donates
739 to thread @var{B} (with priority 3), then @var{B}'s new priority is 5, not 8.
741 @item Can a thread's priority change while it is on the ready queue?
743 Yes. Consider this case: low-priority thread @var{L} holds a
744 lock that high-priority thread @var{H} wants, so @var{H} donates its
745 priority to @var{L}. @var{L} releases the lock and
746 thus loses the CPU and is moved to the ready queue. Now @var{L}'s
747 old priority is restored while it is in the ready queue.
749 @item Can a thread's priority change while it is blocked?
751 Yes. While a thread that has acquired lock @var{L} is blocked for any
752 reason, its priority can increase by priority donation if a
753 higher-priority thread attempts to acquire @var{L}. This case is
754 checked by the @code{priority-donate-sema} test.
756 @item Can a thread added to the ready list preempt the processor?
758 Yes. If a thread added to the ready list has higher priority than the
759 running thread, the correct behavior is to immediately yield the
760 processor. It is not acceptable to wait for the next timer interrupt.
761 The highest priority thread should run as soon as it is runnable,
762 preempting whatever thread is currently running.
764 @item How does @func{thread_set_priority} affect a thread receiving donations?
766 It sets the thread's base priority. The thread's effective priority
767 becomes the higher of the newly set priority or the highest donated
768 priority. When the donations are released, the thread's priority
769 becomes the one set through the function call. This behavior is checked
770 by the @code{priority-donate-lower} test.
772 @item Calling @func{printf} in @func{sema_up} or @func{sema_down} reboots!
774 @anchor{printf Reboots}
775 Yes. These functions are called before @func{printf} is ready to go.
776 You could add a global flag initialized to false and set it to true
777 just before the first @func{printf} in @func{main}. Then modify
778 @func{printf} itself to return immediately if the flag isn't set.
781 @node Advanced Scheduler FAQ
782 @subsection Advanced Scheduler FAQ
785 @item How does priority donation interact with the advanced scheduler?
787 It doesn't have to. We won't test priority donation and the advanced
788 scheduler at the same time.
790 @item Can I use one queue instead of 64 queues?
792 Yes. In general, your implementation may differ from the description,
793 as long as its behavior is the same.
795 @item Some scheduler tests fail and I don't understand why. Help!
797 If your implementation mysteriously fails some of the advanced
798 scheduler tests, try the following:
802 Read the source files for the tests that you're failing, to make sure
803 that you understand what's going on. Each one has a comment at the
804 top that explains its purpose and expected results.
807 Double-check your fixed-point arithmetic routines and your use of them
808 in the scheduler routines.
811 Consider how much work your implementation does in the timer
812 interrupt. If the timer interrupt handler takes too long, then it
813 will take away most of a timer tick from the thread that the timer
814 interrupt preempted. When it returns control to that thread, it
815 therefore won't get to do much work before the next timer interrupt
816 arrives. That thread will therefore get blamed for a lot more CPU
817 time than it actually got a chance to use. This raises the
818 interrupted thread's recent CPU count, thereby lowering its priority.
819 It can cause scheduling decisions to change. It also raises the load