1 @node Project 1--Threads, Project 2--User Programs, Introduction, 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.
15 * Understanding Threads::
17 * Debugging versus Testing::
19 * Problem 1-1 Alarm Clock::
21 * Problem 1-3 Priority Scheduling::
22 * Problem 1-4 Advanced Scheduler::
26 @node Understanding Threads
27 @section Understanding Threads
29 The first step is to read and understand the initial thread system.
30 Pintos, by default, implements thread creation and thread completion,
31 a simple scheduler to switch between threads, and synchronization
32 primitives (semaphores, locks, and condition variables).
34 However, there's a lot of magic going on in some of this code, so if
35 you haven't already compiled and run the base system, as described in
36 the introduction (@pxref{Introduction}), you should do so now. You
37 can read through parts of the source code by hand to see what's going
38 on. If you like, you can add calls to @code{printf()} almost
39 anywhere, then recompile and run to see what happens and in what
40 order. You can also run the kernel in a debugger and set breakpoints
41 at interesting spots, single-step through code and examine data, and
42 so on. @xref{i386-elf-gdb}, for more information.
44 When a thread is created, you are creating a new context to be
45 scheduled. You provide a function to be run in this context as an
46 argument to @code{thread_create()}. The first time the thread is
47 scheduled and runs, it will start from the beginning of that function
48 and execute it in the context. When that function returns, that thread
49 completes. Each thread, therefore, acts like a mini-program running
50 inside Pintos, with the function passed to @code{thread_create()}
51 acting like @code{main()}.
53 At any given time, Pintos is running exactly one thread, with the
54 others switched out. The scheduler decides which thread to run next
55 when it needs to switch between them. (If no thread is ready to run
56 at any given time, then the special ``idle'' thread runs.) The
57 synchronization primitives are used to force context switches when one
58 thread needs to wait for another thread to do something.
60 The exact mechanics of a context switch are pretty gruesome and have
61 been provided for you in @file{threads/switch.S} (this is 80@var{x}86
62 assembly; don't worry about understanding it). It involves saving the
63 state of the currently running thread and restoring the state of the
64 thread we're switching to.
66 Using the @command{gdb} debugger, slowly trace through a context
67 switch to see what happens (@pxref{i386-elf-gdb}). You can set a
68 breakpoint on the @code{schedule()} function to start out, and then
69 single-step from there. Be sure to keep track of each thread's
70 address and state, and what procedures are on the call stack for each
71 thread. You will notice that when one thread calls
72 @code{switch_threads()}, another thread starts running, and the first
73 thing the new thread does is to return from
74 @code{switch_threads()}. We realize this comment will seem cryptic to
75 you at this point, but you will understand threads once you understand
76 why the @code{switch_threads()} that gets called is different from the
77 @code{switch_threads()} that returns. @c FIXME
79 @strong{Warning}: In Pintos, each thread is assigned a small,
80 fixed-size execution stack just under @w{4 kB} in size. The kernel
81 does try to detect stack overflow, but it cannot always succeed. You
82 ma cause bizarre problems, such as mysterious kernel panics, if you
83 declare large data structures as non-static local variables,
84 e.g. @samp{int buf[1000];}. Alternatives to stack allocation include
85 the page allocator in @file{threads/palloc.c} and the block allocator
86 in @file{threads/malloc.c}. Note that the page allocator doles out
87 @w{4 kB} chunks and that @code{malloc()} has a @w{2 kB} block size
88 limit. If you need larger chunks, consider using a linked structure
94 Here is a brief overview of the files in the @file{threads}
95 directory. You will not need to modify most of this code, but the
96 hope is that presenting this overview will give you a start on what
102 The kernel loader. Assembles to 512 bytes of code and data that the
103 PC BIOS loads into memory and which in turn loads the kernel into
104 memory, does basic processor initialization, and jumps to the
105 beginning of the kernel. You should not need to look at this code or
109 The linker script used to link the kernel. Sets the load address of
110 the kernel and arranges for @file{start.S} to be at the very beginning
111 of the kernel image. Again, you should not need to look at this code
112 or modify it, but it's here in case you're curious.
115 Jumps to @code{main()}.
119 Kernel initialization, including @code{main()}, the kernel's ``main
120 program.'' You should look over @code{main()} at least to see what
125 Basic thread support. Much of your work will take place in these
126 files. @file{thread.h} defines @code{struct thread}, which you will
127 modify in the first three projects.
131 Assembly language routine for switching threads. Already discussed
136 Page allocator, which hands out system memory one 4 kB page at a time.
140 Initializes the kernel page table. FIXME
144 A very simple implementation of @code{malloc()} and @code{free()} for
145 the kernel. The largest block that can be allocated is 2 kB.
149 Basic interrupt handling and functions for turning interrupts on and
154 A Perl program that outputs assembly for low-level interrupt handling.
158 Basic synchronization primitives: semaphores, locks, and condition
159 variables. You will need to use these for synchronization through all
164 Test code. For project 1, you will replace this file with your test
168 Functions for I/O port access. This is mostly used by source code in
169 the @file{devices} directory that you won't have to touch.
172 Functions and macros related to memory management, including page
173 directories and page tables. This will be more important to you in
174 project 3. For now, you can ignore it.
177 FIXME devices and lib directories?
179 @node Debugging versus Testing
180 @section Debugging versus Testing
182 When you're debugging code, it's useful to be able to be able to run a
183 program twice and have it do exactly the same thing. On second and
184 later runs, you can make new observations without having to discard or
185 verify your old observations. This property is called
186 ``reproducibility.'' The simulator we use, Bochs, can be set up for
187 reproducibility. If you use the Bochs configuration files we provide,
188 which specify @samp{ips: @var{n}} where @var{n} is a number of
189 simulated instructions per second, your simulations can be
192 Of course, a simulation can only be reproducible from one run to the
193 next if its input is the same each time. For simulating an entire
194 computer, as we do, this means that every part of the computer must be
195 the same. For example, you must use the same disks, the same version
196 of Bochs, and you must not hit any keys on the keyboard (because you
197 could not be sure to hit them at exactly the same point each time)
200 While reproducibility is useful for debugging, it is a problem for
201 testing thread synchronization, an important part of this project. In
202 particular, when Bochs is set up for reproducibility, timer interrupts
203 will come at perfectly reproducible points, and therefore so will
204 thread switches. That means that running the same test several times
205 doesn't give you any greater confidence in your code's correctness
206 than does running it only once.
209 So, to make your code easier to test, we've added a feature to Bochs
210 that makes timer interrupts come at random intervals, but in a
211 perfectly predictable way. In particular, if you put a line
212 @samp{ips-jitter: @var{seed}}, where @var{seed} is an integer, into
213 your Bochs configuration file, then timer interrupts will come at
214 irregularly spaced intervals. Within a single @var{seed} value,
215 execution will still be reproducible, but timer behavior will change
216 as @var{seed} is varied. Thus, for the highest degree of confidence
217 you should test your code with many seed values.
222 There should be no busy-waiting in any of your solutions to this
223 assignment. Furthermore, resist the temptation to directly disable
224 interrupts in your solution by calling @code{intr_disable()} or
225 @code{intr_set_level()}, although you may find doing so to be useful
226 while debugging. Instead, use semaphores, locks and condition
227 variables to solve synchronization problems. Hint: read the comments
228 in @file{threads/synch.h} if you're unsure what synchronization
229 primitives may be used in what situations.
231 Given some designs of some problems, there may be one or two instances
232 in which it is appropriate to directly change the interrupt levels
233 instead of relying on the given synchroniztion primitives. This must
234 be justified in your @file{DESIGNDOC} file. If you're not sure you're
237 While all parts of this assignment are required if you intend to earn
238 full credit on this project, keep in mind that Problem 1-2 (Join) will
239 be needed for future assignments, so you'll want to get this one
240 right. We don't give out solutions, so you're stuck with your Join
241 code for the whole quarter. Problem 1-1 (Alarm Clock) could be very
242 handy, but not strictly required in the future. The upshot of all
243 this is that you should focus heavily on making sure that your
244 implementation of @code{thread_join()} works correctly, since if it's
245 broken, you will need to fix it for future assignments. The other
246 parts can be turned off in the future if you find you can't make them
249 Also keep in mind that Problem 1-4 (the MLFQS) builds on the features you
250 implement in Problem 1-3, so to avoid unnecessary code duplication, it
251 would be a good idea to divide up the work among your team members
252 such that you have Problem 1-3 fully working before you begin to tackle
255 @node Problem 1-1 Alarm Clock
256 @section Problem 1-1: Alarm Clock
258 Improve the implementation of the timer device defined in
259 @file{devices/timer.c} by reimplementing @code{timer_sleep()}.
260 Threads call @code{timer_sleep(@var{x})} to suspend execution until
261 time has advanced by at least @w{@var{x} timer ticks}. This is
262 useful for threads that operate in real-time, for example, for
263 blinking the cursor once per second. There is no requirement that
264 threads start running immediately after waking up; just put them on
265 the ready queue after they have waited for approximately the right
268 A working implementation of this function is provided. However, the
269 version provided is poor, because it ``busy waits,'' that is, it spins
270 in a tight loop checking the current time until the current time has
271 advanced far enough. This is undesirable because it wastes time that
272 could potentially be used more profitably by another thread. Your
273 solution should not busy wait.
275 The argument to @code{timer_sleep()} is expressed in timer ticks, not
276 in milliseconds or some other unit.
278 @node Problem 1-2 Join
279 @section Problem 1-2: Join
281 Implement @code{thread_join(tid_t)} in @file{threads/thread.c}. There
282 is already a prototype for it in @file{threads/thread.h}, which you
283 should not change. This function causes the currently running thread
284 to block until the thread whose thread id is passed as an argument
285 exits. If A is the running thread and B is the argument, then we say
286 that ``A joins B'' in this case.
288 Incidentally, we don't use @code{struct thread *} as
289 @file{thread_join()}'s parameter type because a thread pointer is not
290 unique over time. That is, when a thread dies, its memory may be,
291 whether immediately or much later, reused for another thread. If
292 thread A over time had two children B and C that were stored at the
293 same address, then @code{thread_join(@r{B})} and
294 @code{thread_join(@r{C})} would be ambiguous. Introducing a thread id
295 or @dfn{tid}, represented by type @code{tid_t}, that is intentionally
296 unique over time solves the problem. The provided code uses an
297 @code{int} for @code{tid_t}, but you may decide you prefer to use some
300 The model for @code{thread_join()} is the @command{wait} system call
301 in Unix-like systems. (Try reading the manpages.) That system call
302 can only be used by a parent process to wait for a child's death. You
303 should implement @code{thread_join()} to have the same restriction.
304 That is, a thread may only join its immediate children.
306 A thread need not ever be joined. Your solution should properly free
307 all of a thread's resources, including its @code{struct thread},
308 whether it is ever joined or not, and regardless of whether the child
309 exits before or after its parent. That is, a thread should be freed
310 exactly once in all cases.
312 Joining a given thread is idempotent. That is, joining a thread T
313 multiple times is equivalent to joining it once, because T has already
314 exited at the time of the later joins. Thus, joins on T after the
315 first should return immediately.
317 Calling @code{thread_join()} on an thread that is not the caller's
318 child should cause the caller to return immediately.
320 Consider all the ways a join can occur: nested joins (A joins B when B
321 is joined on C), multiple joins (A joins B, then A joins C), and so
322 on. Does your join work if @code{thread_join()} is called on a thread
323 that has not yet been scheduled for the first time? You should handle
324 all of these cases. Write test code that demonstrates the cases your
325 join works for. Don't overdo the output volume, please!
327 Be careful to program this function correctly. You will need its
328 functionality for project 2.
330 @node Problem 1-3 Priority Scheduling
331 @section Problem 1-3: Priority Scheduling
333 Implement priority scheduling in Pintos. Priority scheduling is a key
334 building block for real-time systems. Implement functions
335 @code{thread_set_priority()} to set the priority of the running thread
336 and @code{thread_get_priority()} to get the running thread's priority.
337 (A thread can examine and modify only its own priority.) There are
338 already prototypes for these functions in @file{threads/thread.h},
339 which you should not change.
341 Thread priority ranges from @code{PRI_MIN} (0) to @code{PRI_MAX} (59).
342 The initial thread priority is passed as an argument to
343 @code{thread_create()}. If there's no reason to choose another
344 priority, use @code{PRI_DEFAULT} (29). The @code{PRI_} macros are
345 defined in @file{threads/thread.h}, and you should not change their
348 When a thread is added to the ready list that has a higher priority
349 than the currently running thread, the current thread should
350 immediately yield the processor to the new thread. Similarly, when
351 threads are waiting for a lock, semaphore or condition variable, the
352 highest priority waiting thread should be woken up first. A thread's
353 priority may be set at any time, including while the thread is waiting
354 on a lock, semaphore, or condition variable.
356 One issue with priority scheduling is ``priority inversion'': if a
357 high priority thread needs to wait for a low priority thread (for
358 instance, for a lock held by a low priority thread, or in
359 @code{thread_join()} for a thread to complete), and a middle priority
360 thread is on the ready list, then the high priority thread will never
361 get the CPU because the low priority thread will not get any CPU time.
362 A partial fix for this problem is to have the waiting thread
363 ``donate'' its priority to the low priority thread while it is holding
364 the lock, then recall the donation once it has acquired the lock.
367 You will need to account for all different orders that priority
368 donation and inversion can occur. Be sure to handle multiple
369 donations, in which multiple priorities are donated to a thread. You
370 must also handle nested donation: given high, medium, and low priority
371 threads H, M, and L, respectively, if H is waiting on a lock that M
372 holds and M is waiting on a lock that L holds, then both M and L
373 should be boosted to H's priority.
375 You only need to implement priority donation when a thread is waiting
376 for a lock held by a lower-priority thread. You do not need to
377 implement this fix for semaphores, condition variables or joins.
378 However, you do need to implement priority scheduling in all cases.
380 @node Problem 1-4 Advanced Scheduler
381 @section Problem 1-4: Advanced Scheduler
383 Implement Solaris's multilevel feedback queue scheduler (MLFQS) to
384 reduce the average response time for running jobs on your system.
385 @xref{Multilevel Feedback Scheduling}, for a detailed description of
386 the MLFQS requirements.
388 Demonstrate that your scheduling algorithm reduces response time
389 relative to the original Pintos scheduling algorithm (round robin) for
390 at least one workload of your own design (i.e.@: in addition to the
393 You may assume a static priority for this problem. It is not necessary
394 to ``re-donate'' a thread's priority if it changes (although you are
397 You must write your code so that we can turn the MLFQS on and off at
398 compile time. By default, it must be off, but we must be able to turn
399 it on by inserting the line @code{#define MLFQS 1} in
400 @file{constants.h}. @xref{Conditional Compilation}, for details.
410 @b{I am adding a new @file{.h} or @file{.c} file. How do I fix the
411 @file{Makefile}s?}@anchor{Adding c or h Files}
413 To add a @file{.c} file, edit the top-level @file{Makefile.build}.
414 You'll want to add your file to variable @samp{@var{dir}_SRC}, where
415 @var{dir} is the directory where you added the file. For this
416 project, that means you should add it to @code{threads_SRC}, or
417 possibly @code{devices_SRC} if you put in the @file{devices}
418 directory. Then run @code{make}. If your new file doesn't get
419 compiled, run @code{make clean} and then try again.
421 When you modify the top-level @file{Makefile.build}, the modified
422 version should be automatically copied to
423 @file{threads/build/Makefile} when you re-run make. The opposite is
424 not true, so any changes will be lost the next time you run @code{make
425 clean} from the @file{threads} directory. Therefore, you should
426 prefer to edit @file{Makefile.build} (unless your changes are meant to
429 There is no need to edit the @file{Makefile}s to add a @file{.h} file.
432 @b{How do I write my test cases?}
434 Test cases should be replacements for the existing @file{test.c}
435 file. Put them in a @file{threads/testcases} directory.
436 @xref{TESTCASE}, for more information.
439 @b{If a thread finishes, should its children be terminated immediately,
440 or should they finish normally?}
442 You should feel free to decide what semantics you think this
443 should have. You need only provide justification for your
447 @b{Why can't I disable interrupts?}
449 Turning off interrupts should only be done for short amounts of time,
450 or else you end up losing important things such as disk or input
451 events. Turning off interrupts also increases the interrupt handling
452 latency, which can make a machine feel sluggish if taken too far.
453 Therefore, in general, setting the interrupt level should be used
454 sparingly. Also, any synchronization problem can be easily solved by
455 turning interrupts off, since while interrupts are off, there is no
456 concurrency, so there's no possibility for race condition.
458 To make sure you understand concurrency well, we are discouraging you
459 from taking this shortcut at all in your solution. If you are unable
460 to solve a particular synchronization problem with semaphores, locks,
461 or conditions, or think that they are inadequate for a particular
462 reason, you may turn to disabling interrupts. If you want to do this,
463 we require in your design document a complete justification and
464 scenario (i.e.@: exact sequence of events) to show why interrupt
465 manipulation is the best solution. If you are unsure, the TAs can
466 help you determine if you are using interrupts too haphazardly. We
467 want to emphasize that there are only limited cases where this is
470 You might find @file{devices/intq.h} and its users to be an
471 inspiration or source of rationale.
474 @b{Where might interrupt-level manipulation be appropriate?}
476 You might find it necessary in some solutions to the Alarm problem.
478 You might want it at one small point for the priority scheduling
479 problem. Note that it is not required to use interrupts for these
480 problems. There are other, equally correct solutions that do not
481 require interrupt manipulation. However, if you do manipulate
482 interrupts and @strong{correctly and fully document it} in your design
483 document, we will allow limited use of interrupt disabling.
486 @item Alarm Clock FAQs
490 @b{Why can't I use most synchronization primitives in an interrupt
493 As you've discovered, you cannot sleep in an external interrupt
494 handler. Since many lock, semaphore, and condition variable functions
495 attempt to sleep, you won't be able to call those in
496 @code{timer_interrupt()}. You may still use those that never sleep.
498 Having said that, you need to make sure that global data does not get
499 updated by multiple threads simultaneously executing
500 @code{timer_sleep()}. Here are some pieces of information to think
505 Interrupts are turned off while @code{timer_interrupt()} runs. This
506 means that @code{timer_interrupt()} will not be interrupted by a
507 thread running in @code{timer_sleep()}.
510 A thread in @code{timer_sleep()}, however, can be interrupted by a
511 call to @code{timer_interrupt()}, except when that thread has turned
515 Examples of synchronization mechanisms have been presented in lecture.
516 Going over these examples should help you understand when each type is
521 @b{What about timer overflow due to the fact that times are defined as
522 integers? Do I need to check for that?}
524 Don't worry about the possibility of timer values overflowing. Timer
525 values are expressed as signed 63-bit numbers, which at 100 ticks per
526 second should be good for almost 2,924,712,087 years.
533 @b{Am I correct to assume that once a thread is deleted, it is no
534 longer accessible by the parent (i.e.@: the parent can't call
535 @code{thread_join(child)})?}
537 A parent joining a child that has completed should be handled
538 gracefully and should act as a no-op.
541 @item Priority Scheduling FAQs
545 @b{Doesn't the priority scheduling lead to starvation? Or do I have to
546 implement some sort of aging?}
548 It is true that strict priority scheduling can lead to starvation
549 because thread may not run if a higher-priority thread is runnable.
550 In this problem, don't worry about starvation or any sort of aging
551 technique. Problem 4 will introduce a mechanism for dynamically
552 changing thread priorities.
554 This sort of scheduling is valuable in real-time systems because it
555 offers the programmer more control over which jobs get processing
556 time. High priorities are generally reserved for time-critical
557 tasks. It's not ``fair,'' but it addresses other concerns not
558 applicable to a general-purpose operating system.
561 @b{After a lock has been released, does the program need to switch to
562 the highest priority thread that needs the lock (assuming that its
563 priority is higher than that of the current thread)?}
565 When a lock is released, the highest priority thread waiting for that
566 lock should be unblocked and put on the ready to run list. The
567 scheduler should then run the highest priority thread on the ready
571 @b{If a thread calls @code{thread_yield()} and then it turns out that
572 it has higher priority than any other threads, does the high-priority
573 thread continue running?}
575 Yes. If there is a single highest-priority thread, it continues
576 running until it blocks or finishes, even if it calls
577 @code{thread_yield()}.
580 @b{If the highest priority thread is added to the ready to run list it
581 should start execution immediately. Is it immediate enough if I
582 wait until next timer interrupt occurs?}
584 The highest priority thread should run as soon as it is runnable,
585 preempting whatever thread is currently running.
588 @b{What happens to the priority of the donating thread? Do the priorities
591 No. Priority donation only changes the priority of the low-priority
592 thread. The donating thread's priority stays unchanged. Also note
593 that priorities aren't additive: if thread A (with priority 5) donates
594 to thread B (with priority 3), then B's new priority is 5, not 8.
597 @b{Can a thread's priority be changed while it is sitting on the ready
600 Yes. Consider this case: low-priority thread L currently has a lock
601 that high-priority thread H wants. H donates its priority to L (the
602 lock holder). L finishes with the lock, and then loses the CPU and is
603 moved to the ready queue. Now L's old priority is restored while it
604 is in the ready queue.
607 @b{Can a thread's priority change while it is sitting on the queue of a
610 Yes. Same scenario as above except L gets blocked waiting on a new
611 lock when H restores its priority.
614 @b{Why is pubtest3's FIFO test skipping some threads! I know my scheduler
615 is round-robin'ing them like it's supposed to! Our output is like this:}
629 @noindent @b{which repeats 5 times and then}
639 This happens because context switches are being invoked by the test
640 when it explicitly calls @code{thread_yield()}. However, the time
641 slice timer is still alive and so, every tick (by default), thread 1
642 gets switched out (caused by @code{timer_interrupt()} calling
643 @code{intr_yield_on_return()}) before it gets a chance to run its
644 mainline. It is by coincidence that Thread 1 is the one that gets
645 skipped in our example. If we use a different jitter value, the same
646 behavior is seen where a thread gets started and switched out
649 Solution: Increase the value of @code{TIME_SLICE} in
650 @file{devices/timer.c} to a very high value, such as 10000, to see
651 that the threads will round-robin if they aren't interrupted.
654 @b{What happens when a thread is added to the ready list which has
655 higher priority than the currently running thread?}
657 The correct behavior is to immediately yield the processor. Your
658 solution must act this way.
661 @b{What should @code{thread_get_priority()} return in a thread while
662 its priority has been increased by a donation?}
664 The higher (donated) priority.
667 @item Advanced Scheduler FAQs
671 @b{What is the interval between timer interrupts?}
673 Timer interrupts occur @code{TIMER_FREQ} times per second. You can
674 adjust this value by editing @file{devices/timer.h}. The default is
677 You can also adjust the number of timer ticks per time slice by
678 modifying @code{TIME_SLICE} in @file{devices/timer.c}.
681 @b{Do I have to modify the dispatch table?}
683 No, although you are allowed to. It is possible to complete
684 this problem (i.e.@: demonstrate response time improvement)
688 @b{When the scheduler changes the priority of a thread, how does this
689 affect priority donation?}
691 Short (official) answer: Don't worry about it. Your priority donation
692 code may assume static priority assignment.
694 Longer (unofficial) opinion: If you wish to take this into account,
695 however, your design may end up being ``cleaner.'' You have
696 considerable freedom in what actually takes place. I believe what
697 makes the most sense is for scheduler changes to affect the
698 ``original'' (non-donated) priority. This change may actually be
699 masked by the donated priority. Priority changes should only
700 propagate with donations, not ``backwards'' from donees to donors.
703 @b{What is meant by ``static priority''?}
705 Once thread A has donated its priority to thread B, if thread A's
706 priority changes (due to the scheduler) while the donation still
707 exists, you do not have to change thread B's donated priority.
708 However, you are free to do so.
711 @b{Do I have to make my dispatch table user-configurable?}
713 No. Hard-coding the dispatch table values is fine.