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}. To complete this project you will also need to
19 read @ref{Multilevel Feedback Scheduling}.
22 * Understanding Threads::
24 * Debugging versus Testing::
26 * Problem 1-1 Alarm Clock::
28 * Problem 1-3 Priority Scheduling::
29 * Problem 1-4 Advanced Scheduler::
33 @node Understanding Threads
34 @section Understanding Threads
36 The first step is to read and understand the initial thread system.
37 Pintos, by default, implements thread creation and thread completion,
38 a simple scheduler to switch between threads, and synchronization
39 primitives (semaphores, locks, and condition variables).
41 However, there's a lot of magic going on in some of this code, so if
42 you haven't already compiled and run the base system, as described in
43 the introduction (@pxref{Introduction}), you should do so now. You
44 can read through parts of the source code by hand to see what's going
45 on. If you like, you can add calls to @func{printf} almost
46 anywhere, then recompile and run to see what happens and in what
47 order. You can also run the kernel in a debugger and set breakpoints
48 at interesting spots, single-step through code and examine data, and
49 so on. @xref{i386-elf-gdb}, for more information.
51 When a thread is created, you are creating a new context to be
52 scheduled. You provide a function to be run in this context as an
53 argument to @func{thread_create}. The first time the thread is
54 scheduled and runs, it will start from the beginning of that function
55 and execute it in the context. When that function returns, that thread
56 completes. Each thread, therefore, acts like a mini-program running
57 inside Pintos, with the function passed to @func{thread_create}
58 acting like @func{main}.
60 At any given time, Pintos is running exactly one thread, with the
61 others switched out. The scheduler decides which thread to run next
62 when it needs to switch between them. (If no thread is ready to run
63 at any given time, then the special ``idle'' thread runs.) The
64 synchronization primitives are used to force context switches when one
65 thread needs to wait for another thread to do something.
67 The exact mechanics of a context switch are pretty gruesome and have
68 been provided for you in @file{threads/switch.S} (this is 80@var{x}86
69 assembly; don't worry about understanding it). It involves saving the
70 state of the currently running thread and restoring the state of the
71 thread we're switching to.
73 Using the @command{gdb} debugger, slowly trace through a context
74 switch to see what happens (@pxref{i386-elf-gdb}). You can set a
75 breakpoint on the @func{schedule} function to start out, and then
76 single-step from there.@footnote{@command{gdb} might tell you that
77 @func{schedule} doesn't exist, which is arguably a @command{gdb} bug.
78 You can work around this by setting the breakpoint by filename and
79 line number, e.g.@: @code{break thread.c:@var{ln}} where @var{ln} is
80 the line number of the first declaration in @func{schedule}.
81 Alternatively you can recompile with optimization turned off, by
82 removing @samp{-O3} from the @code{CFLAGS} line in
83 @file{Make.config}.} Be sure to keep track of each thread's address
84 and state, and what procedures are on the call stack for each thread.
85 You will notice that when one thread calls @func{switch_threads},
86 another thread starts running, and the first thing the new thread does
87 is to return from @func{switch_threads}. We realize this comment will
88 seem cryptic to you at this point, but you will understand threads
89 once you understand why the @func{switch_threads} that gets called is
90 different from the @func{switch_threads} that returns.
92 @strong{Warning}: In Pintos, each thread is assigned a small,
93 fixed-size execution stack just under @w{4 kB} in size. The kernel
94 does try to detect stack overflow, but it cannot always succeed. You
95 may cause bizarre problems, such as mysterious kernel panics, if you
96 declare large data structures as non-static local variables,
97 e.g. @samp{int buf[1000];}. Alternatives to stack allocation include
98 the page allocator in @file{threads/palloc.c} and the block allocator
99 in @file{threads/malloc.c}. Note that the page allocator doles out
100 @w{4 kB} chunks and that @func{malloc} has a @w{2 kB} block size
101 limit. If you need larger chunks, consider using a linked structure
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. You should not need to look at this code or
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. Again, you should not need to look at this code
125 or modify it, but it's here in case you're curious.
128 Jumps to @func{main}.
132 Kernel initialization, including @func{main}, the kernel's ``main
133 program.'' You should look over @func{main} at least to see what
138 Basic thread support. Much of your work will take place in these
139 files. @file{thread.h} defines @struct{thread}, which you will
140 modify in the first three projects.
144 Assembly language routine for switching threads. Already discussed
149 Page allocator, which hands out system memory in multiples of 4 kB
154 A very simple implementation of @func{malloc} and @func{free} for
159 Basic interrupt handling and functions for turning interrupts on and
164 A Perl program that outputs assembly for low-level interrupt handling.
168 Basic synchronization primitives: semaphores, locks, and condition
169 variables. You will need to use these for synchronization through all
174 Test code. For project 1, you will replace this file with your test
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.
182 Functions and macros related to memory management, including page
183 directories and page tables. This will be more important to you in
184 project 3. For now, you can ignore it.
193 @subsection @file{devices} code
195 The basic threaded kernel also includes these files in the
196 @file{devices} directory:
201 System timer that ticks, by default, 100 times per second. You will
202 modify this code in Problem 1-1.
206 VGA display driver. Responsible for writing text to the screen.
207 You should have no need to look at this code. @func{printf} will
208 call into the VGA display driver for you, so there's little reason to
209 call this code yourself.
213 Serial port driver. Again, @func{printf} calls this code for you,
214 so you don't need to do so yourself. Feel free to look through it if
219 Supports reading and writing sectors on up to 4 IDE disks. This won't
220 actually be used until project 2.
224 Interrupt queue, for managing a circular queue that both kernel
225 threads and interrupt handlers want to access. Used by the keyboard
230 @subsection @file{lib} files
232 Finally, @file{lib} and @file{lib/kernel} contain useful library
233 routines. (@file{lib/user} will be used by user programs, starting in
234 project 2, but it is not part of the kernel.) Here's a few more
251 Implementation of the standard C library. @xref{C99}, for information
252 on a few recently introduced pieces of the C library that you might
253 not have encountered before. @xref{Unsafe String Functions}, for
254 information on what's been intentionally left out for safety.
258 Functions and macros to aid debugging. @xref{Debugging Tools}, for
263 Pseudo-random number generator.
269 System call numbers. Not used until project 2.
273 Doubly linked list implementation. Used all over the Pintos code, and
274 you'll probably want to use it a few places yourself in project 1.
276 @item kernel/bitmap.c
277 @itemx kernel/bitmap.h
278 Bitmap implementation. You can use this in your code if you like, but
279 you probably won't have any need for project 1.
283 Hash table implementation. Likely to come in handy for project 3.
285 @item kernel/console.c
286 @itemx kernel/console.h
287 Implements @func{printf} and a few other functions.
290 @node Debugging versus Testing
291 @section Debugging versus Testing
293 When you're debugging code, it's useful to be able to be able to run a
294 program twice and have it do exactly the same thing. On second and
295 later runs, you can make new observations without having to discard or
296 verify your old observations. This property is called
297 ``reproducibility.'' The simulator we use, Bochs, can be set up for
298 reproducibility, and that's the way that @command{pintos} invokes it
301 Of course, a simulation can only be reproducible from one run to the
302 next if its input is the same each time. For simulating an entire
303 computer, as we do, this means that every part of the computer must be
304 the same. For example, you must use the same disks, the same version
305 of Bochs, and you must not hit any keys on the keyboard (because you
306 could not be sure to hit them at exactly the same point each time)
309 While reproducibility is useful for debugging, it is a problem for
310 testing thread synchronization, an important part of this project. In
311 particular, when Bochs is set up for reproducibility, timer interrupts
312 will come at perfectly reproducible points, and therefore so will
313 thread switches. That means that running the same test several times
314 doesn't give you any greater confidence in your code's correctness
315 than does running it only once.
317 So, to make your code easier to test, we've added a feature, called
318 ``jitter,'' to Bochs, that makes timer interrupts come at random
319 intervals, but in a perfectly predictable way. In particular, if you
320 invoke @command{pintos} with the option @option{-j @var{seed}}, timer
321 interrupts will come at irregularly spaced intervals. Within a single
322 @var{seed} value, execution will still be reproducible, but timer
323 behavior will change as @var{seed} is varied. Thus, for the highest
324 degree of confidence you should test your code with many seed values.
326 On the other hand, when Bochs runs in reproducible mode, timings are not
327 realistic, meaning that a ``one-second'' delay may be much shorter or
328 even much longer than one second. You can invoke @command{pintos} with
329 a different option, @option{-r}, to make it set up Bochs for realistic
330 timings, in which a one-second delay should take approximately one
331 second of real time. Simulation in real-time mode is not reproducible,
332 and options @option{-j} and @option{-r} are mutually exclusive.
337 There should be no busy-waiting in any of your solutions to this
338 assignment. Furthermore, resist the temptation to directly disable
339 interrupts in your solution by calling @func{intr_disable} or
340 @func{intr_set_level}, although you may find doing so to be useful
341 while debugging. Instead, use semaphores, locks and condition
342 variables to solve synchronization problems. Hint: read the comments
343 in @file{threads/synch.h} if you're unsure what synchronization
344 primitives may be used in what situations.
346 Given some designs of some problems, there may be one or two instances
347 in which it is appropriate to directly change the interrupt levels
348 instead of relying on the given synchroniztion primitives. This must
349 be justified in your @file{DESIGNDOC} file. If you're not sure you're
352 While all parts of this assignment are required if you intend to earn
353 full credit on this project, keep in mind that Problem 1-2 (Join) will
354 be needed for future assignments, so you'll want to get this one
355 right. We don't give out solutions, so you're stuck with your Join
356 code for the whole quarter. Problem 1-1 (Alarm Clock) could be very
357 handy, but not strictly required in the future. The upshot of all
358 this is that you should focus heavily on making sure that your
359 implementation of @func{thread_join} works correctly, since if it's
360 broken, you will need to fix it for future assignments. The other
361 parts can be turned off in the future if you find you can't make them
364 Also keep in mind that Problem 1-4 (the MLFQS) builds on the features you
365 implement in Problem 1-3, so to avoid unnecessary code duplication, it
366 would be a good idea to divide up the work among your team members
367 such that you have Problem 1-3 fully working before you begin to tackle
370 @node Problem 1-1 Alarm Clock
371 @section Problem 1-1: Alarm Clock
373 Improve the implementation of the timer device defined in
374 @file{devices/timer.c} by reimplementing @func{timer_sleep}.
375 Threads call @code{timer_sleep(@var{x})} to suspend execution until
376 time has advanced by at least @w{@var{x} timer ticks}. This is
377 useful for threads that operate in real-time, for example, for
378 blinking the cursor once per second. There is no requirement that
379 threads start running immediately after waking up; just put them on
380 the ready queue after they have waited for approximately the right
383 A working implementation of this function is provided. However, the
384 version provided is poor, because it ``busy waits,'' that is, it spins
385 in a tight loop checking the current time until the current time has
386 advanced far enough. This is undesirable because it wastes time that
387 could potentially be used more profitably by another thread. Your
388 solution should not busy wait.
390 The argument to @func{timer_sleep} is expressed in timer ticks, not
391 in milliseconds or another unit. There are @code{TIMER_FREQ} timer
392 ticks per second, where @code{TIMER_FREQ} is a macro defined in
393 @code{devices/timer.h}.
395 If your delays seem too short or too long, reread the explanation of the
396 @option{-r} option to @command{pintos} (@pxref{Debugging versus
399 @node Problem 1-2 Join
400 @section Problem 1-2: Join
402 Implement @code{thread_join(tid_t)} in @file{threads/thread.c}. There
403 is already a prototype for it in @file{threads/thread.h}, which you
404 should not change. This function causes the currently running thread
405 to block until the thread whose thread id is passed as an argument
406 exits. If @var{A} is the running thread and @var{B} is the argument,
407 then we say that ``@var{A} joins @var{B}.''
409 Incidentally, we don't use @code{struct thread *} as
410 @func{thread_join}'s parameter type because a thread pointer is not
411 unique over time. That is, when a thread dies, its memory may be,
412 whether immediately or much later, reused for another thread. If
413 thread A over time had two children B and C that were stored at the
414 same address, then @code{thread_join(@var{B})} and
415 @code{thread_join(@var{C})} would be ambiguous. Introducing a thread
416 id or @dfn{tid}, represented by type @code{tid_t}, that is
417 intentionally unique over time solves the problem. The provided code
418 uses an @code{int} for @code{tid_t}, but you may decide you prefer to
421 The model for @func{thread_join} is the @command{wait} system call
422 in Unix-like systems. (Try reading the manpages.) That system call
423 can only be used by a parent process to wait for a child's death. You
424 should implement @func{thread_join} to have the same restriction.
425 That is, a thread may only join its immediate children.
427 A thread need not ever be joined. Your solution should properly free
428 all of a thread's resources, including its @struct{thread},
429 whether it is ever joined or not, and regardless of whether the child
430 exits before or after its parent. That is, a thread should be freed
431 exactly once in all cases.
433 Joining a given thread is idempotent. That is, joining a thread T
434 multiple times is equivalent to joining it once, because T has already
435 exited at the time of the later joins. Thus, joins on T after the
436 first should return immediately.
438 Calling @func{thread_join} on an thread that is not the caller's
439 child should cause the caller to return immediately.
441 Consider all the ways a join can occur: nested joins (@var{A} joins
442 @var{B}, then @var{B} joins @var{C}), multiple joins (@var{A} joins
443 @var{B}, then @var{A} joins @var{C}), and so on. Does your join work
444 if @func{thread_join} is called on a thread that has not yet been
445 scheduled for the first time? You should handle all of these cases.
446 Write test code that demonstrates the cases your join works for.
447 Don't overdo the output volume, please!
449 Be careful to program this function correctly. You will need its
450 functionality for project 2.
452 Once you've implemented @func{thread_join}, define
453 @code{THREAD_JOIN_IMPLEMENTED} in @file{constants.h}.
454 @xref{Conditional Compilation}, for more information.
456 @node Problem 1-3 Priority Scheduling
457 @section Problem 1-3: Priority Scheduling
459 Implement priority scheduling in Pintos. Priority scheduling is a key
460 building block for real-time systems. Implement functions
461 @func{thread_set_priority} to set the priority of the running thread
462 and @func{thread_get_priority} to get the running thread's priority.
463 (This API only allows a thread to examine and modify its own
464 priority.) There are already prototypes for these functions in
465 @file{threads/thread.h}, which you should not change.
467 Thread priority ranges from @code{PRI_MIN} (0) to @code{PRI_MAX} (59).
468 The initial thread priority is passed as an argument to
469 @func{thread_create}. If there's no reason to choose another
470 priority, use @code{PRI_DEFAULT} (29). The @code{PRI_} macros are
471 defined in @file{threads/thread.h}, and you should not change their
474 When a thread is added to the ready list that has a higher priority
475 than the currently running thread, the current thread should
476 immediately yield the processor to the new thread. Similarly, when
477 threads are waiting for a lock, semaphore or condition variable, the
478 highest priority waiting thread should be woken up first. A thread
479 may set its priority at any time.
481 One issue with priority scheduling is ``priority inversion'': if a
482 high priority thread needs to wait for a low priority thread (for
483 instance, for a lock held by a low priority thread, or in
484 @func{thread_join} for a thread to complete), and a middle priority
485 thread is on the ready list, then the high priority thread will never
486 get the CPU because the low priority thread will not get any CPU time.
487 A partial fix for this problem is to have the waiting thread
488 ``donate'' its priority to the low priority thread while it is holding
489 the lock, then recall the donation once it has acquired the lock.
492 You will need to account for all different orders that priority
493 donation and inversion can occur. Be sure to handle multiple
494 donations, in which multiple priorities are donated to a thread. You
495 must also handle nested donation: given high, medium, and low priority
496 threads @var{H}, @var{M}, and @var{L}, respectively, if @var{H} is
497 waiting on a lock that @var{M} holds and @var{M} is waiting on a lock
498 that @var{L} holds, then both @var{M} and @var{L} should be boosted to
501 You only need to implement priority donation when a thread is waiting
502 for a lock held by a lower-priority thread. You do not need to
503 implement this fix for semaphores, condition variables, or joins,
504 although you are welcome to do so. However, you do need to implement
505 priority scheduling in all cases.
507 You may assume a static priority for priority donation, that is, it is
508 not necessary to ``re-donate'' a thread's priority if it changes
509 (although you are free to do so).
511 @node Problem 1-4 Advanced Scheduler
512 @section Problem 1-4: Advanced Scheduler
514 Implement Solaris's multilevel feedback queue scheduler (MLFQS) to
515 reduce the average response time for running jobs on your system.
516 @xref{Multilevel Feedback Scheduling}, for a detailed description of
517 the MLFQS requirements.
519 Demonstrate that your scheduling algorithm reduces response time
520 relative to the original Pintos scheduling algorithm (round robin) for
521 at least one workload of your own design (i.e.@: in addition to the
524 You must write your code so that we can turn the MLFQS on and off at
525 compile time. By default, it must be off, but we must be able to turn
526 it on by inserting the line @code{#define MLFQS 1} in
527 @file{constants.h}. @xref{Conditional Compilation}, for details.
534 @b{I am adding a new @file{.h} or @file{.c} file. How do I fix the
535 @file{Makefile}s?}@anchor{Adding c or h Files}
537 To add a @file{.c} file, edit the top-level @file{Makefile.build}.
538 You'll want to add your file to variable @samp{@var{dir}_SRC}, where
539 @var{dir} is the directory where you added the file. For this
540 project, that means you should add it to @code{threads_SRC}, or
541 possibly @code{devices_SRC} if you put in the @file{devices}
542 directory. Then run @code{make}. If your new file doesn't get
543 compiled, run @code{make clean} and then try again.
545 When you modify the top-level @file{Makefile.build}, the modified
546 version should be automatically copied to
547 @file{threads/build/Makefile} when you re-run make. The opposite is
548 not true, so any changes will be lost the next time you run @code{make
549 clean} from the @file{threads} directory. Therefore, you should
550 prefer to edit @file{Makefile.build} (unless your changes are meant to
553 There is no need to edit the @file{Makefile}s to add a @file{.h} file.
556 @b{How do I write my test cases?}
558 Test cases should be replacements for the existing @file{test.c}
559 file. Put them in a @file{threads/testcases} directory.
560 @xref{TESTCASE}, for more information.
563 @b{Why can't I disable interrupts?}
565 Turning off interrupts should only be done for short amounts of time,
566 or else you end up losing important things such as disk or input
567 events. Turning off interrupts also increases the interrupt handling
568 latency, which can make a machine feel sluggish if taken too far.
569 Therefore, in general, setting the interrupt level should be used
570 sparingly. Also, any synchronization problem can be easily solved by
571 turning interrupts off, since while interrupts are off, there is no
572 concurrency, so there's no possibility for race condition.
574 To make sure you understand concurrency well, we are discouraging you
575 from taking this shortcut at all in your solution. If you are unable
576 to solve a particular synchronization problem with semaphores, locks,
577 or conditions, or think that they are inadequate for a particular
578 reason, you may turn to disabling interrupts. If you want to do this,
579 we require in your design document a complete justification and
580 scenario (i.e.@: exact sequence of events) to show why interrupt
581 manipulation is the best solution. If you are unsure, the TAs can
582 help you determine if you are using interrupts too haphazardly. We
583 want to emphasize that there are only limited cases where this is
586 You might find @file{devices/intq.h} and its users to be an
587 inspiration or source of rationale.
590 @b{Where might interrupt-level manipulation be appropriate?}
592 You might find it necessary in some solutions to the Alarm problem.
594 You might want it at one small point for the priority scheduling
595 problem. Note that it is not required to use interrupts for these
596 problems. There are other, equally correct solutions that do not
597 require interrupt manipulation. However, if you do manipulate
598 interrupts and @strong{correctly and fully document it} in your design
599 document, we will allow limited use of interrupt disabling.
602 @b{What does ``warning: no previous prototype for `@var{function}''
605 It means that you defined a non-@code{static} function without
606 preceding it by a prototype. Because non-@code{static} functions are
607 intended for use by other @file{.c} files, for safety they should be
608 prototyped in a header file included before their definition. To fix
609 the problem, add a prototype in a header file that you include, or, if
610 the function isn't actually used by other @file{.c} files, make it
615 * Problem 1-1 Alarm Clock FAQ::
616 * Problem 1-2 Join FAQ::
617 * Problem 1-3 Priority Scheduling FAQ::
618 * Problem 1-4 Advanced Scheduler FAQ::
621 @node Problem 1-1 Alarm Clock FAQ
622 @subsection Problem 1-1: Alarm Clock FAQ
626 @b{Why can't I use most synchronization primitives in an interrupt
629 As you've discovered, you cannot sleep in an external interrupt
630 handler. Since many lock, semaphore, and condition variable functions
631 attempt to sleep, you won't be able to call those in
632 @func{timer_interrupt}. You may still use those that never sleep.
634 Having said that, you need to make sure that global data does not get
635 updated by multiple threads simultaneously executing
636 @func{timer_sleep}. Here are some pieces of information to think
641 Interrupts are turned off while @func{timer_interrupt} runs. This
642 means that @func{timer_interrupt} will not be interrupted by a
643 thread running in @func{timer_sleep}.
646 A thread in @func{timer_sleep}, however, can be interrupted by a
647 call to @func{timer_interrupt}, except when that thread has turned
651 Examples of synchronization mechanisms have been presented in lecture.
652 Going over these examples should help you understand when each type is
657 @b{What about timer overflow due to the fact that times are defined as
658 integers? Do I need to check for that?}
660 Don't worry about the possibility of timer values overflowing. Timer
661 values are expressed as signed 63-bit numbers, which at 100 ticks per
662 second should be good for almost 2,924,712,087 years.
665 @b{The test program mostly works but reports a few out-of-order
666 wake ups. I think it's a problem in the test program. What gives?}
667 @anchor{Out of Order 1-1}
669 This test is inherently full of race conditions. On a real system it
670 wouldn't work perfectly all the time either. However, you can help it
675 Make time slices longer by increasing @code{TIME_SLICE} in
676 @file{timer.c} to a large value, such as 100.
679 Make the timer tick more slowly by decreasing @code{TIMER_FREQ} in
680 @file{timer.h} to its minimum value of 19.
683 Increase the serial output speed to the maximum of 115,200 bps by
684 modifying the call to @func{set_serial} in @func{serial_init_poll} in
685 @file{devices/serial.c}.
688 The former two changes are only desirable for testing problem 1-1 and
689 possibly 1-3. You should revert them before working on other parts
690 of the project or turn in the project. The latter is harmless, so you
691 can retain it or revert it at your option.
694 @b{Should @file{p1-1.c} be expected to work with the MLFQS turned on?}
696 No. The MLFQS will adjust priorities, changing thread ordering.
699 @node Problem 1-2 Join FAQ
700 @subsection Problem 1-2: Join FAQ
704 @b{Am I correct to assume that once a thread is deleted, it is no
705 longer accessible by the parent (i.e.@: the parent can't call
706 @code{thread_join(child)})?}
708 A parent joining a child that has completed should be handled
709 gracefully and should act as a no-op.
712 @node Problem 1-3 Priority Scheduling FAQ
713 @subsection Problem 1-3: Priority Scheduling FAQ
717 @b{Doesn't the priority scheduling lead to starvation? Or do I have to
718 implement some sort of aging?}
720 It is true that strict priority scheduling can lead to starvation
721 because thread may not run if a higher-priority thread is runnable.
722 In this problem, don't worry about starvation or any sort of aging
723 technique. Problem 4 will introduce a mechanism for dynamically
724 changing thread priorities.
726 This sort of scheduling is valuable in real-time systems because it
727 offers the programmer more control over which jobs get processing
728 time. High priorities are generally reserved for time-critical
729 tasks. It's not ``fair,'' but it addresses other concerns not
730 applicable to a general-purpose operating system.
733 @b{After a lock has been released, does the program need to switch to
734 the highest priority thread that needs the lock (assuming that its
735 priority is higher than that of the current thread)?}
737 When a lock is released, the highest priority thread waiting for that
738 lock should be unblocked and put on the ready to run list. The
739 scheduler should then run the highest priority thread on the ready
743 @b{If a thread calls @func{thread_yield} and then it turns out that
744 it has higher priority than any other threads, does the high-priority
745 thread continue running?}
747 Yes. If there is a single highest-priority thread, it continues
748 running until it blocks or finishes, even if it calls
752 @b{If the highest priority thread is added to the ready to run list it
753 should start execution immediately. Is it immediate enough if I
754 wait until next timer interrupt occurs?}
756 The highest priority thread should run as soon as it is runnable,
757 preempting whatever thread is currently running.
760 @b{What happens to the priority of the donating thread? Do the priorities
763 No. Priority donation only changes the priority of the low-priority
764 thread. The donating thread's priority stays unchanged. Also note
765 that priorities aren't additive: if thread A (with priority 5) donates
766 to thread B (with priority 3), then B's new priority is 5, not 8.
769 @b{Can a thread's priority be changed while it is sitting on the ready
772 Yes. Consider this case: low-priority thread L currently has a lock
773 that high-priority thread H wants. H donates its priority to L (the
774 lock holder). L finishes with the lock, and then loses the CPU and is
775 moved to the ready queue. Now L's old priority is restored while it
776 is in the ready queue.
779 @b{Can a thread's priority change while it is sitting on the queue of a
782 Yes. Same scenario as above except L gets blocked waiting on a new
783 lock when H restores its priority.
786 @b{Why is @file{p1-3.c}'s FIFO test skipping some threads? I know my
787 scheduler is round-robin'ing them like it's supposed to. Our output
788 starts out okay, but toward the end it starts getting out of order.}
790 The usual problem is that the serial output buffer fills up. This is
791 causing serial_putc() to block in thread @var{A}, so that thread
792 @var{B} is scheduled. Thread @var{B} immediately tries to do output
793 of its own and blocks on the serial lock (which is held by thread
794 @var{A}). Now that we've wasted some time in scheduling and locking,
795 typically some characters have been drained out of the serial buffer
796 by the interrupt handler, so thread @var{A} can continue its output.
797 After it finishes, though, some other thread (not @var{B}) is
798 scheduled, because thread @var{B} was already scheduled while we
799 waited for the buffer to drain.
801 There's at least one other possibility. Context switches are being
802 invoked by the test when it explicitly calls @func{thread_yield}.
803 However, the time slice timer is still alive and so, every tick (by
804 default), a thread gets switched out (caused by @func{timer_interrupt}
805 calling @func{intr_yield_on_return}) before it gets a chance to run
806 @func{printf}, effectively skipping it. If we use a different jitter
807 value, the same behavior is seen where a thread gets started and
808 switched out completely.
810 Normally you can fix these problems using the same techniques
811 suggested on problem 1-1 (@pxref{Out of Order 1-1}).
814 @b{What happens when a thread is added to the ready list which has
815 higher priority than the currently running thread?}
817 The correct behavior is to immediately yield the processor. Your
818 solution must act this way.
821 @b{What should @func{thread_get_priority} return in a thread while
822 its priority has been increased by a donation?}
824 The higher (donated) priority.
827 @b{Should @file{p1-3.c} be expected to work with the MLFQS turned on?}
829 No. The MLFQS will adjust priorities, changing thread ordering.
832 @b{@func{printf} in @func{sema_up} or @func{sema_down} makes the
835 Yes. These functions are called before @func{printf} is ready to go.
836 You could add a global flag initialized to false and set it to true
837 just before the first @func{printf} in @func{main}. Then modify
838 @func{printf} itself to return immediately if the flag isn't set.
841 @node Problem 1-4 Advanced Scheduler FAQ
842 @subsection Problem 1-4: Advanced Scheduler FAQ
846 @b{What is the interval between timer interrupts?}
848 Timer interrupts occur @code{TIMER_FREQ} times per second. You can
849 adjust this value by editing @file{devices/timer.h}. The default is
852 You can also adjust the number of timer ticks per time slice by
853 modifying @code{TIME_SLICE} in @file{devices/timer.c}.
856 @b{Do I have to modify the dispatch table?}
858 No, although you are allowed to. It is possible to complete
859 this problem (i.e.@: demonstrate response time improvement)
863 @b{When the scheduler changes the priority of a thread, how does this
864 affect priority donation?}
866 Short (official) answer: Don't worry about it. Your priority donation
867 code may assume static priority assignment.
869 Longer (unofficial) opinion: If you wish to take this into account,
870 however, your design may end up being ``cleaner.'' You have
871 considerable freedom in what actually takes place. I believe what
872 makes the most sense is for scheduler changes to affect the
873 ``original'' (non-donated) priority. This change may actually be
874 masked by the donated priority. Priority changes should only
875 propagate with donations, not ``backwards'' from donees to donors.
878 @b{What is meant by ``static priority''?}
880 Once thread A has donated its priority to thread B, if thread A's
881 priority changes (due to the scheduler) while the donation still
882 exists, you do not have to change thread B's donated priority.
883 However, you are free to do so.
886 @b{Do I have to make my dispatch table user-configurable?}
888 No. Hard-coding the dispatch table values is fine.