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 Real-time clock driver, to enable the kernel to determine the current
247 date and time. By default, this is only used by @file{thread/init.c}
248 to choose an initial seed for the random number generator.
252 Driver that can produce tones on the PC speaker.
256 Code to configure the 8254 Programmable Interrupt Timer. This code is
257 used by both @file{devices/timer.c} and @file{devices/speaker.c}
258 because each device uses one of the PIT's output channel.
262 @subsubsection @file{lib} files
264 Finally, @file{lib} and @file{lib/kernel} contain useful library
265 routines. (@file{lib/user} will be used by user programs, starting in
266 project 2, but it is not part of the kernel.) Here's a few more
283 A subset of the standard C library. @xref{C99}, for
285 on a few recently introduced pieces of the C library that you might
286 not have encountered before. @xref{Unsafe String Functions}, for
287 information on what's been intentionally left out for safety.
291 Functions and macros to aid debugging. @xref{Debugging Tools}, for
296 Pseudo-random number generator. The actual sequence of random values
297 will not vary from one Pintos run to another, unless you do one of
298 three things: specify a new random seed value on the @option{-rs}
299 kernel command-line option on each run, or use a simulator other than
300 Bochs, or specify the @option{-r} option to @command{pintos}.
306 System call numbers. Not used until project 2.
310 Doubly linked list implementation. Used all over the Pintos code, and
311 you'll probably want to use it a few places yourself in project 1.
313 @item kernel/bitmap.c
314 @itemx kernel/bitmap.h
315 Bitmap implementation. You can use this in your code if you like, but
316 you probably won't have any need for it in project 1.
320 Hash table implementation. Likely to come in handy for project 3.
322 @item kernel/console.c
323 @itemx kernel/console.h
325 Implements @func{printf} and a few other functions.
328 @node Project 1 Synchronization
329 @subsection Synchronization
331 Proper synchronization is an important part of the solutions to these
332 problems. Any synchronization problem can be easily solved by turning
333 interrupts off: while interrupts are off, there is no concurrency, so
334 there's no possibility for race conditions. Therefore, it's tempting to
335 solve all synchronization problems this way, but @strong{don't}.
336 Instead, use semaphores, locks, and condition variables to solve the
337 bulk of your synchronization problems. Read the tour section on
338 synchronization (@pxref{Synchronization}) or the comments in
339 @file{threads/synch.c} if you're unsure what synchronization primitives
340 may be used in what situations.
342 In the Pintos projects, the only class of problem best solved by
343 disabling interrupts is coordinating data shared between a kernel thread
344 and an interrupt handler. Because interrupt handlers can't sleep, they
345 can't acquire locks. This means that data shared between kernel threads
346 and an interrupt handler must be protected within a kernel thread by
347 turning off interrupts.
349 This project only requires accessing a little bit of thread state from
350 interrupt handlers. For the alarm clock, the timer interrupt needs to
351 wake up sleeping threads. In the advanced scheduler, the timer
352 interrupt needs to access a few global and per-thread variables. When
353 you access these variables from kernel threads, you will need to disable
354 interrupts to prevent the timer interrupt from interfering.
356 When you do turn off interrupts, take care to do so for the least amount
357 of code possible, or you can end up losing important things such as
358 timer ticks or input events. Turning off interrupts also increases the
359 interrupt handling latency, which can make a machine feel sluggish if
362 The synchronization primitives themselves in @file{synch.c} are
363 implemented by disabling interrupts. You may need to increase the
364 amount of code that runs with interrupts disabled here, but you should
365 still try to keep it to a minimum.
367 Disabling interrupts can be useful for debugging, if you want to make
368 sure that a section of code is not interrupted. You should remove
369 debugging code before turning in your project. (Don't just comment it
370 out, because that can make the code difficult to read.)
372 There should be no busy waiting in your submission. A tight loop that
373 calls @func{thread_yield} is one form of busy waiting.
375 @node Development Suggestions
376 @subsection Development Suggestions
378 In the past, many groups divided the assignment into pieces, then each
379 group member worked on his or her piece until just before the
380 deadline, at which time the group reconvened to combine their code and
381 submit. @strong{This is a bad idea. We do not recommend this
382 approach.} Groups that do this often find that two changes conflict
383 with each other, requiring lots of last-minute debugging. Some groups
384 who have done this have turned in code that did not even compile or
385 boot, much less pass any tests.
389 You should expect to run into bugs that you simply don't understand
390 while working on this and subsequent projects. When you do,
391 reread the appendix on debugging tools, which is filled with
392 useful debugging tips that should help you to get back up to speed
393 (@pxref{Debugging Tools}). Be sure to read the section on backtraces
394 (@pxref{Backtraces}), which will help you to get the most out of every
395 kernel panic or assertion failure.
397 @node Project 1 Requirements
398 @section Requirements
401 * Project 1 Design Document::
403 * Priority Scheduling::
404 * Advanced Scheduler::
407 @node Project 1 Design Document
408 @subsection Design Document
410 Before you turn in your project, you must copy @uref{threads.tmpl, , the
411 project 1 design document template} into your source tree under the name
412 @file{pintos/src/threads/DESIGNDOC} and fill it in. We recommend that
413 you read the design document template before you start working on the
414 project. @xref{Project Documentation}, for a sample design document
415 that goes along with a fictitious project.
418 @subsection Alarm Clock
420 Reimplement @func{timer_sleep}, defined in @file{devices/timer.c}.
421 Although a working implementation is provided, it ``busy waits,'' that
422 is, it spins in a loop checking the current time and calling
423 @func{thread_yield} until enough time has gone by. Reimplement it to
426 @deftypefun void timer_sleep (int64_t @var{ticks})
427 Suspends execution of the calling thread until time has advanced by at
428 least @w{@var{x} timer ticks}. Unless the system is otherwise idle, the
429 thread need not wake up after exactly @var{x} ticks. Just put it on
430 the ready queue after they have waited for the right amount of time.
432 @func{timer_sleep} is useful for threads that operate in real-time,
433 e.g.@: for blinking the cursor once per second.
435 The argument to @func{timer_sleep} is expressed in timer ticks, not in
436 milliseconds or any another unit. There are @code{TIMER_FREQ} timer
437 ticks per second, where @code{TIMER_FREQ} is a macro defined in
438 @code{devices/timer.h}. The default value is 100. We don't recommend
439 changing this value, because any change is likely to cause many of
443 Separate functions @func{timer_msleep}, @func{timer_usleep}, and
444 @func{timer_nsleep} do exist for sleeping a specific number of
445 milliseconds, microseconds, or nanoseconds, respectively, but these will
446 call @func{timer_sleep} automatically when necessary. You do not need
449 If your delays seem too short or too long, reread the explanation of the
450 @option{-r} option to @command{pintos} (@pxref{Debugging versus
453 The alarm clock implementation is not needed for later projects,
454 although it could be useful for project 4.
456 @node Priority Scheduling
457 @subsection Priority Scheduling
459 Implement priority scheduling in Pintos.
460 When a thread is added to the ready list that has a higher priority
461 than the currently running thread, the current thread should
462 immediately yield the processor to the new thread. Similarly, when
463 threads are waiting for a lock, semaphore, or condition variable, the
464 highest priority waiting thread should be awakened first. A thread
465 may raise or lower its own priority at any time, but lowering its
466 priority such that it no longer has the highest priority must cause it
467 to immediately yield the CPU.
469 Thread priorities range from @code{PRI_MIN} (0) to @code{PRI_MAX} (63).
470 Lower numbers correspond to lower priorities, so that priority 0
471 is the lowest priority and priority 63 is the highest.
472 The initial thread priority is passed as an argument to
473 @func{thread_create}. If there's no reason to choose another
474 priority, use @code{PRI_DEFAULT} (31). The @code{PRI_} macros are
475 defined in @file{threads/thread.h}, and you should not change their
478 One issue with priority scheduling is ``priority inversion''. Consider
479 high, medium, and low priority threads @var{H}, @var{M}, and @var{L},
480 respectively. If @var{H} needs to wait for @var{L} (for instance, for a
481 lock held by @var{L}), and @var{M} is on the ready list, then @var{H}
482 will never get the CPU because the low priority thread will not get any
483 CPU time. A partial fix for this problem is for @var{H} to ``donate''
484 its priority to @var{L} while @var{L} is holding the lock, then recall
485 the donation once @var{L} releases (and thus @var{H} acquires) the lock.
487 Implement priority donation. You will need to account for all different
488 situations in which priority donation is required. Be sure to handle
489 multiple donations, in which multiple priorities are donated to a single
490 thread. You must also handle nested donation: if @var{H} is waiting on
491 a lock that @var{M} holds and @var{M} is waiting on a lock that @var{L}
492 holds, then both @var{M} and @var{L} should be boosted to @var{H}'s
493 priority. If necessary, you may impose a reasonable limit on depth of
494 nested priority donation, such as 8 levels.
496 You must implement priority donation for locks. You need not
497 implement priority donation for the other Pintos synchronization
498 constructs. You do need to implement priority scheduling in all
501 Finally, implement the following functions that allow a thread to
502 examine and modify its own priority. Skeletons for these functions are
503 provided in @file{threads/thread.c}.
505 @deftypefun void thread_set_priority (int @var{new_priority})
506 Sets the current thread's priority to @var{new_priority}. If the
507 current thread no longer has the highest priority, yields.
510 @deftypefun int thread_get_priority (void)
511 Returns the current thread's priority. In the presence of priority
512 donation, returns the higher (donated) priority.
515 You need not provide any interface to allow a thread to directly modify
516 other threads' priorities.
518 The priority scheduler is not used in any later project.
520 @node Advanced Scheduler
521 @subsection Advanced Scheduler
523 Implement a multilevel feedback queue scheduler similar to the
524 4.4@acronym{BSD} scheduler to
525 reduce the average response time for running jobs on your system.
526 @xref{4.4BSD Scheduler}, for detailed requirements.
528 Like the priority scheduler, the advanced scheduler chooses the thread
529 to run based on priorities. However, the advanced scheduler does not do
530 priority donation. Thus, we recommend that you have the priority
531 scheduler working, except possibly for priority donation, before you
532 start work on the advanced scheduler.
534 You must write your code to allow us to choose a scheduling algorithm
535 policy at Pintos startup time. By default, the priority scheduler
536 must be active, but we must be able to choose the 4.4@acronym{BSD}
538 with the @option{-mlfqs} kernel option. Passing this
539 option sets @code{thread_mlfqs}, declared in @file{threads/thread.h}, to
540 true when the options are parsed by @func{parse_options}, which happens
541 early in @func{main}.
543 When the 4.4@acronym{BSD} scheduler is enabled, threads no longer
544 directly control their own priorities. The @var{priority} argument to
545 @func{thread_create} should be ignored, as well as any calls to
546 @func{thread_set_priority}, and @func{thread_get_priority} should return
547 the thread's current priority as set by the scheduler.
549 The advanced scheduler is not used in any later project.
555 @item How much code will I need to write?
557 Here's a summary of our reference solution, produced by the
558 @command{diffstat} program. The final row gives total lines inserted
559 and deleted; a changed line counts as both an insertion and a deletion.
561 The reference solution represents just one possible solution. Many
562 other solutions are also possible and many of those differ greatly from
563 the reference solution. Some excellent solutions may not modify all the
564 files modified by the reference solution, and some may modify files not
565 modified by the reference solution.
568 devices/timer.c | 42 +++++-
569 threads/fixed-point.h | 120 ++++++++++++++++++
570 threads/synch.c | 88 ++++++++++++-
571 threads/thread.c | 196 ++++++++++++++++++++++++++----
572 threads/thread.h | 23 +++
573 5 files changed, 440 insertions(+), 29 deletions(-)
576 @file{fixed-point.h} is a new file added by the reference solution.
578 @item How do I update the @file{Makefile}s when I add a new source file?
580 @anchor{Adding Source Files}
581 To add a @file{.c} file, edit the top-level @file{Makefile.build}.
582 Add the new file to variable @samp{@var{dir}_SRC}, where
583 @var{dir} is the directory where you added the file. For this
584 project, that means you should add it to @code{threads_SRC} or
585 @code{devices_SRC}. Then run @code{make}. If your new file
587 compiled, run @code{make clean} and then try again.
589 When you modify the top-level @file{Makefile.build} and re-run
590 @command{make}, the modified
591 version should be automatically copied to
592 @file{threads/build/Makefile}. The converse is
593 not true, so any changes will be lost the next time you run @code{make
594 clean} from the @file{threads} directory. Unless your changes are
595 truly temporary, you should prefer to edit @file{Makefile.build}.
597 A new @file{.h} file does not require editing the @file{Makefile}s.
599 @item What does @code{warning: no previous prototype for `@var{func}'} mean?
601 It means that you defined a non-@code{static} function without
602 preceding it by a prototype. Because non-@code{static} functions are
603 intended for use by other @file{.c} files, for safety they should be
604 prototyped in a header file included before their definition. To fix
605 the problem, add a prototype in a header file that you include, or, if
606 the function isn't actually used by other @file{.c} files, make it
609 @item What is the interval between timer interrupts?
611 Timer interrupts occur @code{TIMER_FREQ} times per second. You can
612 adjust this value by editing @file{devices/timer.h}. The default is
615 We don't recommend changing this value, because any changes are likely
616 to cause many of the tests to fail.
618 @item How long is a time slice?
620 There are @code{TIME_SLICE} ticks per time slice. This macro is
621 declared in @file{threads/thread.c}. The default is 4 ticks.
623 We don't recommend changing this value, because any changes are likely
624 to cause many of the tests to fail.
626 @item How do I run the tests?
630 @item Why do I get a test failure in @func{pass}?
632 @anchor{The pass function fails}
633 You are probably looking at a backtrace that looks something like this:
636 0xc0108810: debug_panic (lib/kernel/debug.c:32)
637 0xc010a99f: pass (tests/threads/tests.c:93)
638 0xc010bdd3: test_mlfqs_load_1 (...threads/mlfqs-load-1.c:33)
639 0xc010a8cf: run_test (tests/threads/tests.c:51)
640 0xc0100452: run_task (threads/init.c:283)
641 0xc0100536: run_actions (threads/init.c:333)
642 0xc01000bb: main (threads/init.c:137)
645 This is just confusing output from the @command{backtrace} program. It
646 does not actually mean that @func{pass} called @func{debug_panic}. In
647 fact, @func{fail} called @func{debug_panic} (via the @func{PANIC}
648 macro). GCC knows that @func{debug_panic} does not return, because it
649 is declared @code{NO_RETURN} (@pxref{Function and Parameter
650 Attributes}), so it doesn't include any code in @func{fail} to take
651 control when @func{debug_panic} returns. This means that the return
652 address on the stack looks like it is at the beginning of the function
653 that happens to follow @func{fail} in memory, which in this case happens
656 @xref{Backtraces}, for more information.
658 @item How do interrupts get re-enabled in the new thread following @func{schedule}?
660 Every path into @func{schedule} disables interrupts. They eventually
661 get re-enabled by the next thread to be scheduled. Consider the
662 possibilities: the new thread is running in @func{switch_thread} (but
663 see below), which is called by @func{schedule}, which is called by one
664 of a few possible functions:
668 @func{thread_exit}, but we'll never switch back into such a thread, so
672 @func{thread_yield}, which immediately restores the interrupt level upon
673 return from @func{schedule}.
676 @func{thread_block}, which is called from multiple places:
680 @func{sema_down}, which restores the interrupt level before returning.
683 @func{idle}, which enables interrupts with an explicit assembly STI
687 @func{wait} in @file{devices/intq.c}, whose callers are responsible for
688 re-enabling interrupts.
692 There is a special case when a newly created thread runs for the first
693 time. Such a thread calls @func{intr_enable} as the first action in
694 @func{kernel_thread}, which is at the bottom of the call stack for every
695 kernel thread but the first.
700 * Priority Scheduling FAQ::
701 * Advanced Scheduler FAQ::
704 @node Alarm Clock FAQ
705 @subsection Alarm Clock FAQ
708 @item Do I need to account for timer values overflowing?
710 Don't worry about the possibility of timer values overflowing. Timer
711 values are expressed as signed 64-bit numbers, which at 100 ticks per
712 second should be good for almost 2,924,712,087 years. By then, we
713 expect Pintos to have been phased out of the @value{coursenumber} curriculum.
716 @node Priority Scheduling FAQ
717 @subsection Priority Scheduling FAQ
720 @item Doesn't priority scheduling lead to starvation?
722 Yes, strict priority scheduling can lead to starvation
723 because a thread will not run if any higher-priority thread is runnable.
724 The advanced scheduler introduces a mechanism for dynamically
725 changing thread priorities.
727 Strict priority scheduling is valuable in real-time systems because it
728 offers the programmer more control over which jobs get processing
729 time. High priorities are generally reserved for time-critical
730 tasks. It's not ``fair,'' but it addresses other concerns not
731 applicable to a general-purpose operating system.
733 @item What thread should run after a lock has been released?
735 When a lock is released, the highest priority thread waiting for that
736 lock should be unblocked and put on the list of ready threads. The
737 scheduler should then run the highest priority thread on the ready
740 @item If the highest-priority thread yields, does it continue running?
742 Yes. If there is a single highest-priority thread, it continues
743 running until it blocks or finishes, even if it calls
745 If multiple threads have the same highest priority,
746 @func{thread_yield} should switch among them in ``round robin'' order.
748 @item What happens to the priority of a donating thread?
750 Priority donation only changes the priority of the donee
751 thread. The donor thread's priority is unchanged.
752 Priority donation is not additive: if thread @var{A} (with priority 5) donates
753 to thread @var{B} (with priority 3), then @var{B}'s new priority is 5, not 8.
755 @item Can a thread's priority change while it is on the ready queue?
757 Yes. Consider a ready, low-priority thread @var{L} that holds a lock.
758 High-priority thread @var{H} attempts to acquire the lock and blocks,
759 thereby donating its priority to ready thread @var{L}.
761 @item Can a thread's priority change while it is blocked?
763 Yes. While a thread that has acquired lock @var{L} is blocked for any
764 reason, its priority can increase by priority donation if a
765 higher-priority thread attempts to acquire @var{L}. This case is
766 checked by the @code{priority-donate-sema} test.
768 @item Can a thread added to the ready list preempt the processor?
770 Yes. If a thread added to the ready list has higher priority than the
771 running thread, the correct behavior is to immediately yield the
772 processor. It is not acceptable to wait for the next timer interrupt.
773 The highest priority thread should run as soon as it is runnable,
774 preempting whatever thread is currently running.
776 @item How does @func{thread_set_priority} affect a thread receiving donations?
778 It sets the thread's base priority. The thread's effective priority
779 becomes the higher of the newly set priority or the highest donated
780 priority. When the donations are released, the thread's priority
781 becomes the one set through the function call. This behavior is checked
782 by the @code{priority-donate-lower} test.
784 @item Doubled test names in output make them fail.
786 Suppose you are seeing output in which some test names are doubled,
790 (alarm-priority) begin
791 (alarm-priority) (alarm-priority) Thread priority 30 woke up.
792 Thread priority 29 woke up.
793 (alarm-priority) Thread priority 28 woke up.
796 What is happening is that output from two threads is being
797 interleaved. That is, one thread is printing @code{"(alarm-priority)
798 Thread priority 29 woke up.\n"} and another thread is printing
799 @code{"(alarm-priority) Thread priority 30 woke up.\n"}, but the first
800 thread is being preempted by the second in the middle of its output.
802 This problem indicates a bug in your priority scheduler. After all, a
803 thread with priority 29 should not be able to run while a thread with
804 priority 30 has work to do.
806 Normally, the implementation of the @code{printf()} function in the
807 Pintos kernel attempts to prevent such interleaved output by acquiring
808 a console lock during the duration of the @code{printf} call and
809 releasing it afterwards. However, the output of the test name,
810 e.g., @code{(alarm-priority)}, and the message following it is output
811 using two calls to @code{printf}, resulting in the console lock being
812 acquired and released twice.
815 @node Advanced Scheduler FAQ
816 @subsection Advanced Scheduler FAQ
819 @item How does priority donation interact with the advanced scheduler?
821 It doesn't have to. We won't test priority donation and the advanced
822 scheduler at the same time.
824 @item Can I use one queue instead of 64 queues?
826 Yes. In general, your implementation may differ from the description,
827 as long as its behavior is the same.
829 @item Some scheduler tests fail and I don't understand why. Help!
831 If your implementation mysteriously fails some of the advanced
832 scheduler tests, try the following:
836 Read the source files for the tests that you're failing, to make sure
837 that you understand what's going on. Each one has a comment at the
838 top that explains its purpose and expected results.
841 Double-check your fixed-point arithmetic routines and your use of them
842 in the scheduler routines.
845 Consider how much work your implementation does in the timer
846 interrupt. If the timer interrupt handler takes too long, then it
847 will take away most of a timer tick from the thread that the timer
848 interrupt preempted. When it returns control to that thread, it
849 therefore won't get to do much work before the next timer interrupt
850 arrives. That thread will therefore get blamed for a lot more CPU
851 time than it actually got a chance to use. This raises the
852 interrupted thread's recent CPU count, thereby lowering its priority.
853 It can cause scheduling decisions to change. It also raises the load