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 @subsubsection @file{lib} files
254 Finally, @file{lib} and @file{lib/kernel} contain useful library
255 routines. (@file{lib/user} will be used by user programs, starting in
256 project 2, but it is not part of the kernel.) Here's a few more
273 A subset of the standard C library. @xref{C99}, for
275 on a few recently introduced pieces of the C library that you might
276 not have encountered before. @xref{Unsafe String Functions}, for
277 information on what's been intentionally left out for safety.
281 Functions and macros to aid debugging. @xref{Debugging Tools}, for
286 Pseudo-random number generator. The actual sequence of random values
287 will not vary from one Pintos run to another, unless you do one of
288 three things: specify a new random seed value on the @option{-rs}
289 kernel command-line option on each run, or use a simulator other than
290 Bochs, or specify the @option{-r} option to @command{pintos}.
296 System call numbers. Not used until project 2.
300 Doubly linked list implementation. Used all over the Pintos code, and
301 you'll probably want to use it a few places yourself in project 1.
303 @item kernel/bitmap.c
304 @itemx kernel/bitmap.h
305 Bitmap implementation. You can use this in your code if you like, but
306 you probably won't have any need for it in project 1.
310 Hash table implementation. Likely to come in handy for project 3.
312 @item kernel/console.c
313 @itemx kernel/console.h
315 Implements @func{printf} and a few other functions.
318 @node Project 1 Synchronization
319 @subsection Synchronization
321 Proper synchronization is an important part of the solutions to these
322 problems. Any synchronization problem can be easily solved by turning
323 interrupts off: while interrupts are off, there is no concurrency, so
324 there's no possibility for race conditions. Therefore, it's tempting to
325 solve all synchronization problems this way, but @strong{don't}.
326 Instead, use semaphores, locks, and condition variables to solve the
327 bulk of your synchronization problems. Read the tour section on
328 synchronization (@pxref{Synchronization}) or the comments in
329 @file{threads/synch.c} if you're unsure what synchronization primitives
330 may be used in what situations.
332 In the Pintos projects, the only class of problem best solved by
333 disabling interrupts is coordinating data shared between a kernel thread
334 and an interrupt handler. Because interrupt handlers can't sleep, they
335 can't acquire locks. This means that data shared between kernel threads
336 and an interrupt handler must be protected within a kernel thread by
337 turning off interrupts.
339 This project only requires accessing a little bit of thread state from
340 interrupt handlers. For the alarm clock, the timer interrupt needs to
341 wake up sleeping threads. In the advanced scheduler, the timer
342 interrupt needs to access a few global and per-thread variables. When
343 you access these variables from kernel threads, you will need to disable
344 interrupts to prevent the timer interrupt from interfering.
346 When you do turn off interrupts, take care to do so for the least amount
347 of code possible, or you can end up losing important things such as
348 timer ticks or input events. Turning off interrupts also increases the
349 interrupt handling latency, which can make a machine feel sluggish if
352 The synchronization primitives themselves in @file{synch.c} are
353 implemented by disabling interrupts. You may need to increase the
354 amount of code that runs with interrupts disabled here, but you should
355 still try to keep it to a minimum.
357 Disabling interrupts can be useful for debugging, if you want to make
358 sure that a section of code is not interrupted. You should remove
359 debugging code before turning in your project. (Don't just comment it
360 out, because that can make the code difficult to read.)
362 There should be no busy waiting in your submission. A tight loop that
363 calls @func{thread_yield} is one form of busy waiting.
365 @node Development Suggestions
366 @subsection Development Suggestions
368 In the past, many groups divided the assignment into pieces, then each
369 group member worked on his or her piece until just before the
370 deadline, at which time the group reconvened to combine their code and
371 submit. @strong{This is a bad idea. We do not recommend this
372 approach.} Groups that do this often find that two changes conflict
373 with each other, requiring lots of last-minute debugging. Some groups
374 who have done this have turned in code that did not even compile or
375 boot, much less pass any tests.
379 You should expect to run into bugs that you simply don't understand
380 while working on this and subsequent projects. When you do,
381 reread the appendix on debugging tools, which is filled with
382 useful debugging tips that should help you to get back up to speed
383 (@pxref{Debugging Tools}). Be sure to read the section on backtraces
384 (@pxref{Backtraces}), which will help you to get the most out of every
385 kernel panic or assertion failure.
387 @node Project 1 Requirements
388 @section Requirements
391 * Project 1 Design Document::
393 * Priority Scheduling::
394 * Advanced Scheduler::
397 @node Project 1 Design Document
398 @subsection Design Document
400 Before you turn in your project, you must copy @uref{threads.tmpl, , the
401 project 1 design document template} into your source tree under the name
402 @file{pintos/src/threads/DESIGNDOC} and fill it in. We recommend that
403 you read the design document template before you start working on the
404 project. @xref{Project Documentation}, for a sample design document
405 that goes along with a fictitious project.
408 @subsection Alarm Clock
410 Reimplement @func{timer_sleep}, defined in @file{devices/timer.c}.
411 Although a working implementation is provided, it ``busy waits,'' that
412 is, it spins in a loop checking the current time and calling
413 @func{thread_yield} until enough time has gone by. Reimplement it to
416 @deftypefun void timer_sleep (int64_t @var{ticks})
417 Suspends execution of the calling thread until time has advanced by at
418 least @w{@var{x} timer ticks}. Unless the system is otherwise idle, the
419 thread need not wake up after exactly @var{x} ticks. Just put it on
420 the ready queue after they have waited for the right amount of time.
422 @func{timer_sleep} is useful for threads that operate in real-time,
423 e.g.@: for blinking the cursor once per second.
425 The argument to @func{timer_sleep} is expressed in timer ticks, not in
426 milliseconds or any another unit. There are @code{TIMER_FREQ} timer
427 ticks per second, where @code{TIMER_FREQ} is a macro defined in
428 @code{devices/timer.h}. The default value is 100. We don't recommend
429 changing this value, because any change is likely to cause many of
433 Separate functions @func{timer_msleep}, @func{timer_usleep}, and
434 @func{timer_nsleep} do exist for sleeping a specific number of
435 milliseconds, microseconds, or nanoseconds, respectively, but these will
436 call @func{timer_sleep} automatically when necessary. You do not need
439 If your delays seem too short or too long, reread the explanation of the
440 @option{-r} option to @command{pintos} (@pxref{Debugging versus
443 The alarm clock implementation is not needed for later projects,
444 although it could be useful for project 4.
446 @node Priority Scheduling
447 @subsection Priority Scheduling
449 Implement priority scheduling in Pintos.
450 When a thread is added to the ready list that has a higher priority
451 than the currently running thread, the current thread should
452 immediately yield the processor to the new thread. Similarly, when
453 threads are waiting for a lock, semaphore, or condition variable, the
454 highest priority waiting thread should be awakened first. A thread
455 may raise or lower its own priority at any time, but lowering its
456 priority such that it no longer has the highest priority must cause it
457 to immediately yield the CPU.
459 Thread priorities range from @code{PRI_MIN} (0) to @code{PRI_MAX} (63).
460 Lower numbers correspond to lower priorities, so that priority 0
461 is the lowest priority and priority 63 is the highest.
462 The initial thread priority is passed as an argument to
463 @func{thread_create}. If there's no reason to choose another
464 priority, use @code{PRI_DEFAULT} (31). The @code{PRI_} macros are
465 defined in @file{threads/thread.h}, and you should not change their
468 One issue with priority scheduling is ``priority inversion''. Consider
469 high, medium, and low priority threads @var{H}, @var{M}, and @var{L},
470 respectively. If @var{H} needs to wait for @var{L} (for instance, for a
471 lock held by @var{L}), and @var{M} is on the ready list, then @var{H}
472 will never get the CPU because the low priority thread will not get any
473 CPU time. A partial fix for this problem is for @var{H} to ``donate''
474 its priority to @var{L} while @var{L} is holding the lock, then recall
475 the donation once @var{L} releases (and thus @var{H} acquires) the lock.
477 Implement priority donation. You will need to account for all different
478 situations in which priority donation is required. Be sure to handle
479 multiple donations, in which multiple priorities are donated to a single
480 thread. You must also handle nested donation: if @var{H} is waiting on
481 a lock that @var{M} holds and @var{M} is waiting on a lock that @var{L}
482 holds, then both @var{M} and @var{L} should be boosted to @var{H}'s
483 priority. If necessary, you may impose a reasonable limit on depth of
484 nested priority donation, such as 8 levels.
486 You must implement priority donation for locks. You need not
487 implement priority donation for the other Pintos synchronization
488 constructs. You do need to implement priority scheduling in all
491 Finally, implement the following functions that allow a thread to
492 examine and modify its own priority. Skeletons for these functions are
493 provided in @file{threads/thread.c}.
495 @deftypefun void thread_set_priority (int @var{new_priority})
496 Sets the current thread's priority to @var{new_priority}. If the
497 current thread no longer has the highest priority, yields.
500 @deftypefun int thread_get_priority (void)
501 Returns the current thread's priority. In the presence of priority
502 donation, returns the higher (donated) priority.
505 You need not provide any interface to allow a thread to directly modify
506 other threads' priorities.
508 The priority scheduler is not used in any later project.
510 @node Advanced Scheduler
511 @subsection Advanced Scheduler
513 Implement a multilevel feedback queue scheduler similar to the
514 4.4@acronym{BSD} scheduler to
515 reduce the average response time for running jobs on your system.
516 @xref{4.4BSD Scheduler}, for detailed requirements.
518 Like the priority scheduler, the advanced scheduler chooses the thread
519 to run based on priorities. However, the advanced scheduler does not do
520 priority donation. Thus, we recommend that you have the priority
521 scheduler working, except possibly for priority donation, before you
522 start work on the advanced scheduler.
524 You must write your code to allow us to choose a scheduling algorithm
525 policy at Pintos startup time. By default, the priority scheduler
526 must be active, but we must be able to choose the 4.4@acronym{BSD}
528 with the @option{-mlfqs} kernel option. Passing this
529 option sets @code{thread_mlfqs}, declared in @file{threads/thread.h}, to
530 true when the options are parsed by @func{parse_options}, which happens
531 early in @func{main}.
533 When the 4.4@acronym{BSD} scheduler is enabled, threads no longer
534 directly control their own priorities. The @var{priority} argument to
535 @func{thread_create} should be ignored, as well as any calls to
536 @func{thread_set_priority}, and @func{thread_get_priority} should return
537 the thread's current priority as set by the scheduler.
539 The advanced scheduler is not used in any later project.
545 @item How much code will I need to write?
547 Here's a summary of our reference solution, produced by the
548 @command{diffstat} program. The final row gives total lines inserted
549 and deleted; a changed line counts as both an insertion and a deletion.
551 The reference solution represents just one possible solution. Many
552 other solutions are also possible and many of those differ greatly from
553 the reference solution. Some excellent solutions may not modify all the
554 files modified by the reference solution, and some may modify files not
555 modified by the reference solution.
558 devices/timer.c | 42 +++++-
559 threads/fixed-point.h | 120 ++++++++++++++++++
560 threads/synch.c | 88 ++++++++++++-
561 threads/thread.c | 196 ++++++++++++++++++++++++++----
562 threads/thread.h | 23 +++
563 5 files changed, 440 insertions(+), 29 deletions(-)
566 @file{fixed-point.h} is a new file added by the reference solution.
568 @item How do I update the @file{Makefile}s when I add a new source file?
570 @anchor{Adding Source Files}
571 To add a @file{.c} file, edit the top-level @file{Makefile.build}.
572 Add the new file to variable @samp{@var{dir}_SRC}, where
573 @var{dir} is the directory where you added the file. For this
574 project, that means you should add it to @code{threads_SRC} or
575 @code{devices_SRC}. Then run @code{make}. If your new file
577 compiled, run @code{make clean} and then try again.
579 When you modify the top-level @file{Makefile.build} and re-run
580 @command{make}, the modified
581 version should be automatically copied to
582 @file{threads/build/Makefile}. The converse is
583 not true, so any changes will be lost the next time you run @code{make
584 clean} from the @file{threads} directory. Unless your changes are
585 truly temporary, you should prefer to edit @file{Makefile.build}.
587 A new @file{.h} file does not require editing the @file{Makefile}s.
589 @item What does @code{warning: no previous prototype for `@var{func}'} mean?
591 It means that you defined a non-@code{static} function without
592 preceding it by a prototype. Because non-@code{static} functions are
593 intended for use by other @file{.c} files, for safety they should be
594 prototyped in a header file included before their definition. To fix
595 the problem, add a prototype in a header file that you include, or, if
596 the function isn't actually used by other @file{.c} files, make it
599 @item What is the interval between timer interrupts?
601 Timer interrupts occur @code{TIMER_FREQ} times per second. You can
602 adjust this value by editing @file{devices/timer.h}. The default is
605 We don't recommend changing this value, because any changes are likely
606 to cause many of the tests to fail.
608 @item How long is a time slice?
610 There are @code{TIME_SLICE} ticks per time slice. This macro is
611 declared in @file{threads/thread.c}. The default is 4 ticks.
613 We don't recommend changing this value, because any changes are likely
614 to cause many of the tests to fail.
616 @item How do I run the tests?
620 @item Why do I get a test failure in @func{pass}?
622 @anchor{The pass function fails}
623 You are probably looking at a backtrace that looks something like this:
626 0xc0108810: debug_panic (lib/kernel/debug.c:32)
627 0xc010a99f: pass (tests/threads/tests.c:93)
628 0xc010bdd3: test_mlfqs_load_1 (...threads/mlfqs-load-1.c:33)
629 0xc010a8cf: run_test (tests/threads/tests.c:51)
630 0xc0100452: run_task (threads/init.c:283)
631 0xc0100536: run_actions (threads/init.c:333)
632 0xc01000bb: main (threads/init.c:137)
635 This is just confusing output from the @command{backtrace} program. It
636 does not actually mean that @func{pass} called @func{debug_panic}. In
637 fact, @func{fail} called @func{debug_panic} (via the @func{PANIC}
638 macro). GCC knows that @func{debug_panic} does not return, because it
639 is declared @code{NO_RETURN} (@pxref{Function and Parameter
640 Attributes}), so it doesn't include any code in @func{fail} to take
641 control when @func{debug_panic} returns. This means that the return
642 address on the stack looks like it is at the beginning of the function
643 that happens to follow @func{fail} in memory, which in this case happens
646 @xref{Backtraces}, for more information.
648 @item How do interrupts get re-enabled in the new thread following @func{schedule}?
650 Every path into @func{schedule} disables interrupts. They eventually
651 get re-enabled by the next thread to be scheduled. Consider the
652 possibilities: the new thread is running in @func{switch_thread} (but
653 see below), which is called by @func{schedule}, which is called by one
654 of a few possible functions:
658 @func{thread_exit}, but we'll never switch back into such a thread, so
662 @func{thread_yield}, which immediately restores the interrupt level upon
663 return from @func{schedule}.
666 @func{thread_block}, which is called from multiple places:
670 @func{sema_down}, which restores the interrupt level before returning.
673 @func{idle}, which enables interrupts with an explicit assembly STI
677 @func{wait} in @file{devices/intq.c}, whose callers are responsible for
678 re-enabling interrupts.
682 There is a special case when a newly created thread runs for the first
683 time. Such a thread calls @func{intr_enable} as the first action in
684 @func{kernel_thread}, which is at the bottom of the call stack for every
685 kernel thread but the first.
690 * Priority Scheduling FAQ::
691 * Advanced Scheduler FAQ::
694 @node Alarm Clock FAQ
695 @subsection Alarm Clock FAQ
698 @item Do I need to account for timer values overflowing?
700 Don't worry about the possibility of timer values overflowing. Timer
701 values are expressed as signed 64-bit numbers, which at 100 ticks per
702 second should be good for almost 2,924,712,087 years. By then, we
703 expect Pintos to have been phased out of the @value{coursenumber} curriculum.
706 @node Priority Scheduling FAQ
707 @subsection Priority Scheduling FAQ
710 @item Doesn't priority scheduling lead to starvation?
712 Yes, strict priority scheduling can lead to starvation
713 because a thread will not run if any higher-priority thread is runnable.
714 The advanced scheduler introduces a mechanism for dynamically
715 changing thread priorities.
717 Strict priority scheduling is valuable in real-time systems because it
718 offers the programmer more control over which jobs get processing
719 time. High priorities are generally reserved for time-critical
720 tasks. It's not ``fair,'' but it addresses other concerns not
721 applicable to a general-purpose operating system.
723 @item What thread should run after a lock has been released?
725 When a lock is released, the highest priority thread waiting for that
726 lock should be unblocked and put on the list of ready threads. The
727 scheduler should then run the highest priority thread on the ready
730 @item If the highest-priority thread yields, does it continue running?
732 Yes. If there is a single highest-priority thread, it continues
733 running until it blocks or finishes, even if it calls
735 If multiple threads have the same highest priority,
736 @func{thread_yield} should switch among them in ``round robin'' order.
738 @item What happens to the priority of a donating thread?
740 Priority donation only changes the priority of the donee
741 thread. The donor thread's priority is unchanged.
742 Priority donation is not additive: if thread @var{A} (with priority 5) donates
743 to thread @var{B} (with priority 3), then @var{B}'s new priority is 5, not 8.
745 @item Can a thread's priority change while it is on the ready queue?
747 Yes. Consider a ready, low-priority thread @var{L} that holds a lock.
748 High-priority thread @var{H} attempts to acquire the lock and blocks,
749 thereby donating its priority to ready thread @var{L}.
751 @item Can a thread's priority change while it is blocked?
753 Yes. While a thread that has acquired lock @var{L} is blocked for any
754 reason, its priority can increase by priority donation if a
755 higher-priority thread attempts to acquire @var{L}. This case is
756 checked by the @code{priority-donate-sema} test.
758 @item Can a thread added to the ready list preempt the processor?
760 Yes. If a thread added to the ready list has higher priority than the
761 running thread, the correct behavior is to immediately yield the
762 processor. It is not acceptable to wait for the next timer interrupt.
763 The highest priority thread should run as soon as it is runnable,
764 preempting whatever thread is currently running.
766 @item How does @func{thread_set_priority} affect a thread receiving donations?
768 It sets the thread's base priority. The thread's effective priority
769 becomes the higher of the newly set priority or the highest donated
770 priority. When the donations are released, the thread's priority
771 becomes the one set through the function call. This behavior is checked
772 by the @code{priority-donate-lower} test.
775 @node Advanced Scheduler FAQ
776 @subsection Advanced Scheduler FAQ
779 @item How does priority donation interact with the advanced scheduler?
781 It doesn't have to. We won't test priority donation and the advanced
782 scheduler at the same time.
784 @item Can I use one queue instead of 64 queues?
786 Yes. In general, your implementation may differ from the description,
787 as long as its behavior is the same.
789 @item Some scheduler tests fail and I don't understand why. Help!
791 If your implementation mysteriously fails some of the advanced
792 scheduler tests, try the following:
796 Read the source files for the tests that you're failing, to make sure
797 that you understand what's going on. Each one has a comment at the
798 top that explains its purpose and expected results.
801 Double-check your fixed-point arithmetic routines and your use of them
802 in the scheduler routines.
805 Consider how much work your implementation does in the timer
806 interrupt. If the timer interrupt handler takes too long, then it
807 will take away most of a timer tick from the thread that the timer
808 interrupt preempted. When it returns control to that thread, it
809 therefore won't get to do much work before the next timer interrupt
810 arrives. That thread will therefore get blamed for a lot more CPU
811 time than it actually got a chance to use. This raises the
812 interrupted thread's recent CPU count, thereby lowering its priority.
813 It can cause scheduling decisions to change. It also raises the load