1 @node Project 1--Threads, Project 2--User Programs, Pintos Tour, Top
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. Additionally, you
7 will use at least part of this increased functionality in future
10 You will be working in primarily in the @file{threads} directory for
11 this assignment, with some work in the @file{devices} directory on the
12 side. Compilation should be done in the @file{threads} directory.
14 Before you read the description of this project, you should read all
15 of the following sections: @ref{Introduction}, @ref{Coding Standards},
16 @ref{Project Documentation}, @ref{Debugging Tools}, and
17 @ref{Development Tools}. You should at least skim the material in
18 @ref{Threads Tour}, but there's no need to fret over the details. To
19 complete this project you will also need to read @ref{Multilevel
23 * Understanding Threads::
25 * Debugging versus Testing::
27 * Problem 1-1 Alarm Clock::
29 * Problem 1-3 Priority Scheduling::
30 * Problem 1-4 Advanced Scheduler::
34 @node Understanding Threads
35 @section Understanding Threads
37 The first step is to read and understand the initial thread system.
38 Pintos, by default, implements thread creation and thread completion,
39 a simple scheduler to switch between threads, and synchronization
40 primitives (semaphores, locks, and condition variables).
42 However, there's a lot of magic going on in some of this code, so if
43 you haven't already compiled and run the base system, as described in
44 the introduction (@pxref{Introduction}), you should do so now. You
45 can read through parts of the source code by hand to see what's going
46 on. If you like, you can add calls to @func{printf} almost
47 anywhere, then recompile and run to see what happens and in what
48 order. You can also run the kernel in a debugger and set breakpoints
49 at interesting spots, single-step through code and examine data, and
50 so on. @xref{i386-elf-gdb}, for more information.
52 When a thread is created, you are creating a new context to be
53 scheduled. You provide a function to be run in this context as an
54 argument to @func{thread_create}. The first time the thread is
55 scheduled and runs, it will start from the beginning of that function
56 and execute it in the context. When that function returns, that thread
57 completes. Each thread, therefore, acts like a mini-program running
58 inside Pintos, with the function passed to @func{thread_create}
59 acting like @func{main}.
61 At any given time, Pintos is running exactly one thread, with the
62 others switched out. The scheduler decides which thread to run next
63 when it needs to switch between them. (If no thread is ready to run
64 at any given time, then the special ``idle'' thread runs.) The
65 synchronization primitives are used to force context switches when one
66 thread needs to wait for another thread to do something.
68 The exact mechanics of a context switch are pretty gruesome and have
69 been provided for you in @file{threads/switch.S} (this is 80@var{x}86
70 assembly; don't worry about understanding it). It involves saving the
71 state of the currently running thread and restoring the state of the
72 thread we're switching to.
74 Using the @command{gdb} debugger, slowly trace through a context
75 switch to see what happens (@pxref{i386-elf-gdb}). You can set a
76 breakpoint on the @func{schedule} function to start out, and then
77 single-step from there. Be sure to keep track of each thread's
78 address and state, and what procedures are on the call stack for each
79 thread. You will notice that when one thread calls
80 @func{switch_threads}, another thread starts running, and the first
81 thing the new thread does is to return from
82 @func{switch_threads}. We realize this comment will seem cryptic to
83 you at this point, but you will understand threads once you understand
84 why the @func{switch_threads} that gets called is different from the
85 @func{switch_threads} that returns.
87 @strong{Warning}: In Pintos, each thread is assigned a small,
88 fixed-size execution stack just under @w{4 kB} in size. The kernel
89 does try to detect stack overflow, but it cannot always succeed. You
90 may cause bizarre problems, such as mysterious kernel panics, if you
91 declare large data structures as non-static local variables,
92 e.g. @samp{int buf[1000];}. Alternatives to stack allocation include
93 the page allocator in @file{threads/palloc.c} and the block allocator
94 in @file{threads/malloc.c}. Note that the page allocator doles out
95 @w{4 kB} chunks and that @func{malloc} has a @w{2 kB} block size
96 limit. If you need larger chunks, consider using a linked structure
102 Here is a brief overview of the files in the @file{threads}
103 directory. You will not need to modify most of this code, but the
104 hope is that presenting this overview will give you a start on what
110 The kernel loader. Assembles to 512 bytes of code and data that the
111 PC BIOS loads into memory and which in turn loads the kernel into
112 memory, does basic processor initialization, and jumps to the
113 beginning of the kernel. You should not need to look at this code or
117 The linker script used to link the kernel. Sets the load address of
118 the kernel and arranges for @file{start.S} to be at the very beginning
119 of the kernel image. Again, you should not need to look at this code
120 or modify it, but it's here in case you're curious.
123 Jumps to @func{main}.
127 Kernel initialization, including @func{main}, the kernel's ``main
128 program.'' You should look over @func{main} at least to see what
133 Basic thread support. Much of your work will take place in these
134 files. @file{thread.h} defines @code{struct thread}, which you will
135 modify in the first three projects.
139 Assembly language routine for switching threads. Already discussed
144 Page allocator, which hands out system memory in multiples of 4 kB
149 A very simple implementation of @func{malloc} and @func{free} for
154 Basic interrupt handling and functions for turning interrupts on and
159 A Perl program that outputs assembly for low-level interrupt handling.
163 Basic synchronization primitives: semaphores, locks, and condition
164 variables. You will need to use these for synchronization through all
169 Test code. For project 1, you will replace this file with your test
173 Functions for I/O port access. This is mostly used by source code in
174 the @file{devices} directory that you won't have to touch.
177 Functions and macros related to memory management, including page
178 directories and page tables. This will be more important to you in
179 project 3. For now, you can ignore it.
188 @subsection @file{devices} code
190 The basic threaded kernel also includes these files in the
191 @file{devices} directory:
196 System timer that ticks, by default, 100 times per second. You will
197 modify this code in Problem 1-1.
201 VGA display driver. Responsible for writing text to the screen.
202 You should have no need to look at this code. @func{printf} will
203 call into the VGA display driver for you, so there's little reason to
204 call this code yourself.
208 Serial port driver. Again, @func{printf} calls this code for you,
209 so you don't need to do so yourself. Feel free to look through it if
214 Supports reading and writing sectors on up to 4 IDE disks. This won't
215 actually be used until project 2.
219 Interrupt queue, for managing a circular queue that both kernel
220 threads and interrupt handlers want to access. Used by the keyboard
225 @subsection @file{lib} files
227 Finally, @file{lib} and @file{lib/kernel} contain useful library
228 routines. (@file{lib/user} will be used by user programs, starting in
229 project 2, but it is not part of the kernel.) Here's a few more
246 Implementation of the standard C library. @xref{C99}, for information
247 on a few recently introduced pieces of the C library that you might
248 not have encountered before. @xref{Unsafe String Functions}, for
249 information on what's been intentionally left out for safety.
253 Functions and macros to aid debugging. @xref{Debugging Tools}, for
258 Pseudo-random number generator.
264 System call numbers. Not used until project 2.
268 Doubly linked list implementation. Used all over the Pintos code, and
269 you'll probably want to use it a few places yourself in project 1.
271 @item kernel/bitmap.c
272 @itemx kernel/bitmap.h
273 Bitmap implementation. You can use this in your code if you like, but
274 you probably won't have any need for project 1.
278 Hash table implementation. Likely to come in handy for project 3.
280 @item kernel/console.c
281 @itemx kernel/console.h
282 Implements @func{printf} and a few other functions.
285 @node Debugging versus Testing
286 @section Debugging versus Testing
288 When you're debugging code, it's useful to be able to be able to run a
289 program twice and have it do exactly the same thing. On second and
290 later runs, you can make new observations without having to discard or
291 verify your old observations. This property is called
292 ``reproducibility.'' The simulator we use, Bochs, can be set up for
293 reproducibility, and that's the way that @command{pintos} invokes it.
295 Of course, a simulation can only be reproducible from one run to the
296 next if its input is the same each time. For simulating an entire
297 computer, as we do, this means that every part of the computer must be
298 the same. For example, you must use the same disks, the same version
299 of Bochs, and you must not hit any keys on the keyboard (because you
300 could not be sure to hit them at exactly the same point each time)
303 While reproducibility is useful for debugging, it is a problem for
304 testing thread synchronization, an important part of this project. In
305 particular, when Bochs is set up for reproducibility, timer interrupts
306 will come at perfectly reproducible points, and therefore so will
307 thread switches. That means that running the same test several times
308 doesn't give you any greater confidence in your code's correctness
309 than does running it only once.
311 So, to make your code easier to test, we've added a feature to Bochs
312 that makes timer interrupts come at random intervals, but in a
313 perfectly predictable way. In particular, if you invoke
314 @command{pintos} with the option @option{-j @var{seed}}, timer
315 interrupts will come at irregularly spaced intervals. Within a single
316 @var{seed} value, execution will still be reproducible, but timer
317 behavior will change as @var{seed} is varied. Thus, for the highest
318 degree of confidence you should test your code with many seed values.
323 There should be no busy-waiting in any of your solutions to this
324 assignment. Furthermore, resist the temptation to directly disable
325 interrupts in your solution by calling @func{intr_disable} or
326 @func{intr_set_level}, although you may find doing so to be useful
327 while debugging. Instead, use semaphores, locks and condition
328 variables to solve synchronization problems. Hint: read the comments
329 in @file{threads/synch.h} if you're unsure what synchronization
330 primitives may be used in what situations.
332 Given some designs of some problems, there may be one or two instances
333 in which it is appropriate to directly change the interrupt levels
334 instead of relying on the given synchroniztion primitives. This must
335 be justified in your @file{DESIGNDOC} file. If you're not sure you're
338 While all parts of this assignment are required if you intend to earn
339 full credit on this project, keep in mind that Problem 1-2 (Join) will
340 be needed for future assignments, so you'll want to get this one
341 right. We don't give out solutions, so you're stuck with your Join
342 code for the whole quarter. Problem 1-1 (Alarm Clock) could be very
343 handy, but not strictly required in the future. The upshot of all
344 this is that you should focus heavily on making sure that your
345 implementation of @func{thread_join} works correctly, since if it's
346 broken, you will need to fix it for future assignments. The other
347 parts can be turned off in the future if you find you can't make them
350 Also keep in mind that Problem 1-4 (the MLFQS) builds on the features you
351 implement in Problem 1-3, so to avoid unnecessary code duplication, it
352 would be a good idea to divide up the work among your team members
353 such that you have Problem 1-3 fully working before you begin to tackle
356 @node Problem 1-1 Alarm Clock
357 @section Problem 1-1: Alarm Clock
359 Improve the implementation of the timer device defined in
360 @file{devices/timer.c} by reimplementing @func{timer_sleep}.
361 Threads call @code{timer_sleep(@var{x})} to suspend execution until
362 time has advanced by at least @w{@var{x} timer ticks}. This is
363 useful for threads that operate in real-time, for example, for
364 blinking the cursor once per second. There is no requirement that
365 threads start running immediately after waking up; just put them on
366 the ready queue after they have waited for approximately the right
369 A working implementation of this function is provided. However, the
370 version provided is poor, because it ``busy waits,'' that is, it spins
371 in a tight loop checking the current time until the current time has
372 advanced far enough. This is undesirable because it wastes time that
373 could potentially be used more profitably by another thread. Your
374 solution should not busy wait.
376 The argument to @func{timer_sleep} is expressed in timer ticks, not
377 in milliseconds or another unit. There are @code{TIMER_FREQ} timer
378 ticks per second, where @code{TIMER_FREQ} is a macro defined in
379 @code{devices/timer.h}.
381 @node Problem 1-2 Join
382 @section Problem 1-2: Join
384 Implement @code{thread_join(tid_t)} in @file{threads/thread.c}. There
385 is already a prototype for it in @file{threads/thread.h}, which you
386 should not change. This function causes the currently running thread
387 to block until the thread whose thread id is passed as an argument
388 exits. If @var{A} is the running thread and @var{B} is the argument,
389 then we say that ``@var{A} joins @var{B}.''
391 Incidentally, we don't use @code{struct thread *} as
392 @func{thread_join}'s parameter type because a thread pointer is not
393 unique over time. That is, when a thread dies, its memory may be,
394 whether immediately or much later, reused for another thread. If
395 thread A over time had two children B and C that were stored at the
396 same address, then @code{thread_join(@var{B})} and
397 @code{thread_join(@var{C})} would be ambiguous. Introducing a thread
398 id or @dfn{tid}, represented by type @code{tid_t}, that is
399 intentionally unique over time solves the problem. The provided code
400 uses an @code{int} for @code{tid_t}, but you may decide you prefer to
403 The model for @func{thread_join} is the @command{wait} system call
404 in Unix-like systems. (Try reading the manpages.) That system call
405 can only be used by a parent process to wait for a child's death. You
406 should implement @func{thread_join} to have the same restriction.
407 That is, a thread may only join its immediate children.
409 A thread need not ever be joined. Your solution should properly free
410 all of a thread's resources, including its @code{struct thread},
411 whether it is ever joined or not, and regardless of whether the child
412 exits before or after its parent. That is, a thread should be freed
413 exactly once in all cases.
415 Joining a given thread is idempotent. That is, joining a thread T
416 multiple times is equivalent to joining it once, because T has already
417 exited at the time of the later joins. Thus, joins on T after the
418 first should return immediately.
420 Calling @func{thread_join} on an thread that is not the caller's
421 child should cause the caller to return immediately.
423 Consider all the ways a join can occur: nested joins (@var{A} joins
424 @var{B}, then @var{B} joins @var{C}), multiple joins (@var{A} joins
425 @var{B}, then @var{A} joins @var{C}), and so on. Does your join work
426 if @func{thread_join} is called on a thread that has not yet been
427 scheduled for the first time? You should handle all of these cases.
428 Write test code that demonstrates the cases your join works for.
429 Don't overdo the output volume, please!
431 Be careful to program this function correctly. You will need its
432 functionality for project 2.
434 Once you've implemented @func{thread_join}, define
435 @code{THREAD_JOIN_IMPLEMENTED} in @file{constants.h}.
436 @xref{Conditional Compilation}, for more information.
438 @node Problem 1-3 Priority Scheduling
439 @section Problem 1-3: Priority Scheduling
441 Implement priority scheduling in Pintos. Priority scheduling is a key
442 building block for real-time systems. Implement functions
443 @func{thread_set_priority} to set the priority of the running thread
444 and @func{thread_get_priority} to get the running thread's priority.
445 (A thread can examine and modify only its own priority.) There are
446 already prototypes for these functions in @file{threads/thread.h},
447 which you should not change.
449 Thread priority ranges from @code{PRI_MIN} (0) to @code{PRI_MAX} (59).
450 The initial thread priority is passed as an argument to
451 @func{thread_create}. If there's no reason to choose another
452 priority, use @code{PRI_DEFAULT} (29). The @code{PRI_} macros are
453 defined in @file{threads/thread.h}, and you should not change their
456 When a thread is added to the ready list that has a higher priority
457 than the currently running thread, the current thread should
458 immediately yield the processor to the new thread. Similarly, when
459 threads are waiting for a lock, semaphore or condition variable, the
460 highest priority waiting thread should be woken up first. A thread's
461 priority may be set at any time, including while the thread is waiting
462 on a lock, semaphore, or condition variable.
464 One issue with priority scheduling is ``priority inversion'': if a
465 high priority thread needs to wait for a low priority thread (for
466 instance, for a lock held by a low priority thread, or in
467 @func{thread_join} for a thread to complete), and a middle priority
468 thread is on the ready list, then the high priority thread will never
469 get the CPU because the low priority thread will not get any CPU time.
470 A partial fix for this problem is to have the waiting thread
471 ``donate'' its priority to the low priority thread while it is holding
472 the lock, then recall the donation once it has acquired the lock.
475 You will need to account for all different orders that priority
476 donation and inversion can occur. Be sure to handle multiple
477 donations, in which multiple priorities are donated to a thread. You
478 must also handle nested donation: given high, medium, and low priority
479 threads @var{H}, @var{M}, and @var{L}, respectively, if @var{H} is
480 waiting on a lock that @var{M} holds and @var{M} is waiting on a lock
481 that @var{L} holds, then both @var{M} and @var{L} should be boosted to
484 You only need to implement priority donation when a thread is waiting
485 for a lock held by a lower-priority thread. You do not need to
486 implement this fix for semaphores, condition variables or joins.
487 However, you do need to implement priority scheduling in all cases.
489 @node Problem 1-4 Advanced Scheduler
490 @section Problem 1-4: Advanced Scheduler
492 Implement Solaris's multilevel feedback queue scheduler (MLFQS) to
493 reduce the average response time for running jobs on your system.
494 @xref{Multilevel Feedback Scheduling}, for a detailed description of
495 the MLFQS requirements.
497 Demonstrate that your scheduling algorithm reduces response time
498 relative to the original Pintos scheduling algorithm (round robin) for
499 at least one workload of your own design (i.e.@: in addition to the
502 You may assume a static priority for this problem. It is not necessary
503 to ``re-donate'' a thread's priority if it changes (although you are
506 You must write your code so that we can turn the MLFQS on and off at
507 compile time. By default, it must be off, but we must be able to turn
508 it on by inserting the line @code{#define MLFQS 1} in
509 @file{constants.h}. @xref{Conditional Compilation}, for details.
516 @b{I am adding a new @file{.h} or @file{.c} file. How do I fix the
517 @file{Makefile}s?}@anchor{Adding c or h Files}
519 To add a @file{.c} file, edit the top-level @file{Makefile.build}.
520 You'll want to add your file to variable @samp{@var{dir}_SRC}, where
521 @var{dir} is the directory where you added the file. For this
522 project, that means you should add it to @code{threads_SRC}, or
523 possibly @code{devices_SRC} if you put in the @file{devices}
524 directory. Then run @code{make}. If your new file doesn't get
525 compiled, run @code{make clean} and then try again.
527 When you modify the top-level @file{Makefile.build}, the modified
528 version should be automatically copied to
529 @file{threads/build/Makefile} when you re-run make. The opposite is
530 not true, so any changes will be lost the next time you run @code{make
531 clean} from the @file{threads} directory. Therefore, you should
532 prefer to edit @file{Makefile.build} (unless your changes are meant to
535 There is no need to edit the @file{Makefile}s to add a @file{.h} file.
538 @b{How do I write my test cases?}
540 Test cases should be replacements for the existing @file{test.c}
541 file. Put them in a @file{threads/testcases} directory.
542 @xref{TESTCASE}, for more information.
545 @b{Why can't I disable interrupts?}
547 Turning off interrupts should only be done for short amounts of time,
548 or else you end up losing important things such as disk or input
549 events. Turning off interrupts also increases the interrupt handling
550 latency, which can make a machine feel sluggish if taken too far.
551 Therefore, in general, setting the interrupt level should be used
552 sparingly. Also, any synchronization problem can be easily solved by
553 turning interrupts off, since while interrupts are off, there is no
554 concurrency, so there's no possibility for race condition.
556 To make sure you understand concurrency well, we are discouraging you
557 from taking this shortcut at all in your solution. If you are unable
558 to solve a particular synchronization problem with semaphores, locks,
559 or conditions, or think that they are inadequate for a particular
560 reason, you may turn to disabling interrupts. If you want to do this,
561 we require in your design document a complete justification and
562 scenario (i.e.@: exact sequence of events) to show why interrupt
563 manipulation is the best solution. If you are unsure, the TAs can
564 help you determine if you are using interrupts too haphazardly. We
565 want to emphasize that there are only limited cases where this is
568 You might find @file{devices/intq.h} and its users to be an
569 inspiration or source of rationale.
572 @b{Where might interrupt-level manipulation be appropriate?}
574 You might find it necessary in some solutions to the Alarm problem.
576 You might want it at one small point for the priority scheduling
577 problem. Note that it is not required to use interrupts for these
578 problems. There are other, equally correct solutions that do not
579 require interrupt manipulation. However, if you do manipulate
580 interrupts and @strong{correctly and fully document it} in your design
581 document, we will allow limited use of interrupt disabling.
584 @b{What does ``warning: no previous prototype for `@var{function}''
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
597 * Problem 1-1 Alarm Clock FAQ::
598 * Problem 1-2 Join FAQ::
599 * Problem 1-3 Priority Scheduling FAQ::
600 * Problem 1-4 Advanced Scheduler FAQ::
603 @node Problem 1-1 Alarm Clock FAQ
604 @subsection Problem 1-1: Alarm Clock FAQ
608 @b{Why can't I use most synchronization primitives in an interrupt
611 As you've discovered, you cannot sleep in an external interrupt
612 handler. Since many lock, semaphore, and condition variable functions
613 attempt to sleep, you won't be able to call those in
614 @func{timer_interrupt}. You may still use those that never sleep.
616 Having said that, you need to make sure that global data does not get
617 updated by multiple threads simultaneously executing
618 @func{timer_sleep}. Here are some pieces of information to think
623 Interrupts are turned off while @func{timer_interrupt} runs. This
624 means that @func{timer_interrupt} will not be interrupted by a
625 thread running in @func{timer_sleep}.
628 A thread in @func{timer_sleep}, however, can be interrupted by a
629 call to @func{timer_interrupt}, except when that thread has turned
633 Examples of synchronization mechanisms have been presented in lecture.
634 Going over these examples should help you understand when each type is
639 @b{What about timer overflow due to the fact that times are defined as
640 integers? Do I need to check for that?}
642 Don't worry about the possibility of timer values overflowing. Timer
643 values are expressed as signed 63-bit numbers, which at 100 ticks per
644 second should be good for almost 2,924,712,087 years.
647 @node Problem 1-2 Join FAQ
648 @subsection Problem 1-2: Join FAQ
652 @b{Am I correct to assume that once a thread is deleted, it is no
653 longer accessible by the parent (i.e.@: the parent can't call
654 @code{thread_join(child)})?}
656 A parent joining a child that has completed should be handled
657 gracefully and should act as a no-op.
660 @node Problem 1-3 Priority Scheduling FAQ
661 @subsection Problem 1-3: Priority Scheduling FAQ
665 @b{Doesn't the priority scheduling lead to starvation? Or do I have to
666 implement some sort of aging?}
668 It is true that strict priority scheduling can lead to starvation
669 because thread may not run if a higher-priority thread is runnable.
670 In this problem, don't worry about starvation or any sort of aging
671 technique. Problem 4 will introduce a mechanism for dynamically
672 changing thread priorities.
674 This sort of scheduling is valuable in real-time systems because it
675 offers the programmer more control over which jobs get processing
676 time. High priorities are generally reserved for time-critical
677 tasks. It's not ``fair,'' but it addresses other concerns not
678 applicable to a general-purpose operating system.
681 @b{After a lock has been released, does the program need to switch to
682 the highest priority thread that needs the lock (assuming that its
683 priority is higher than that of the current thread)?}
685 When a lock is released, the highest priority thread waiting for that
686 lock should be unblocked and put on the ready to run list. The
687 scheduler should then run the highest priority thread on the ready
691 @b{If a thread calls @func{thread_yield} and then it turns out that
692 it has higher priority than any other threads, does the high-priority
693 thread continue running?}
695 Yes. If there is a single highest-priority thread, it continues
696 running until it blocks or finishes, even if it calls
700 @b{If the highest priority thread is added to the ready to run list it
701 should start execution immediately. Is it immediate enough if I
702 wait until next timer interrupt occurs?}
704 The highest priority thread should run as soon as it is runnable,
705 preempting whatever thread is currently running.
708 @b{What happens to the priority of the donating thread? Do the priorities
711 No. Priority donation only changes the priority of the low-priority
712 thread. The donating thread's priority stays unchanged. Also note
713 that priorities aren't additive: if thread A (with priority 5) donates
714 to thread B (with priority 3), then B's new priority is 5, not 8.
717 @b{Can a thread's priority be changed while it is sitting on the ready
720 Yes. Consider this case: low-priority thread L currently has a lock
721 that high-priority thread H wants. H donates its priority to L (the
722 lock holder). L finishes with the lock, and then loses the CPU and is
723 moved to the ready queue. Now L's old priority is restored while it
724 is in the ready queue.
727 @b{Can a thread's priority change while it is sitting on the queue of a
730 Yes. Same scenario as above except L gets blocked waiting on a new
731 lock when H restores its priority.
734 @b{Why is pubtest3's FIFO test skipping some threads! I know my scheduler
735 is round-robin'ing them like it's supposed to! Our output is like this:}
749 @noindent @b{which repeats 5 times and then}
759 This happens because context switches are being invoked by the test
760 when it explicitly calls @func{thread_yield}. However, the time
761 slice timer is still alive and so, every tick (by default), thread 1
762 gets switched out (caused by @func{timer_interrupt} calling
763 @func{intr_yield_on_return}) before it gets a chance to run its
764 mainline. It is by coincidence that Thread 1 is the one that gets
765 skipped in our example. If we use a different jitter value, the same
766 behavior is seen where a thread gets started and switched out
769 Solution: Increase the value of @code{TIME_SLICE} in
770 @file{devices/timer.c} to a very high value, such as 10000, to see
771 that the threads will round-robin if they aren't interrupted.
774 @b{What happens when a thread is added to the ready list which has
775 higher priority than the currently running thread?}
777 The correct behavior is to immediately yield the processor. Your
778 solution must act this way.
781 @b{What should @func{thread_get_priority} return in a thread while
782 its priority has been increased by a donation?}
784 The higher (donated) priority.
787 @node Problem 1-4 Advanced Scheduler FAQ
788 @subsection Problem 1-4: Advanced Scheduler FAQ
792 @b{What is the interval between timer interrupts?}
794 Timer interrupts occur @code{TIMER_FREQ} times per second. You can
795 adjust this value by editing @file{devices/timer.h}. The default is
798 You can also adjust the number of timer ticks per time slice by
799 modifying @code{TIME_SLICE} in @file{devices/timer.c}.
802 @b{Do I have to modify the dispatch table?}
804 No, although you are allowed to. It is possible to complete
805 this problem (i.e.@: demonstrate response time improvement)
809 @b{When the scheduler changes the priority of a thread, how does this
810 affect priority donation?}
812 Short (official) answer: Don't worry about it. Your priority donation
813 code may assume static priority assignment.
815 Longer (unofficial) opinion: If you wish to take this into account,
816 however, your design may end up being ``cleaner.'' You have
817 considerable freedom in what actually takes place. I believe what
818 makes the most sense is for scheduler changes to affect the
819 ``original'' (non-donated) priority. This change may actually be
820 masked by the donated priority. Priority changes should only
821 propagate with donations, not ``backwards'' from donees to donors.
824 @b{What is meant by ``static priority''?}
826 Once thread A has donated its priority to thread B, if thread A's
827 priority changes (due to the scheduler) while the donation still
828 exists, you do not have to change thread B's donated priority.
829 However, you are free to do so.
832 @b{Do I have to make my dispatch table user-configurable?}
834 No. Hard-coding the dispatch table values is fine.