1 @node Project 1--Threads, Project 2--User Programs, Top, 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 the @file{threads} and @file{devices}
11 directories for this assignment. Compilation should be done in the
12 @file{threads} directory.
15 * Understanding Threads::
16 * Debugging versus Testing::
18 * Problem 1-1 Alarm Clock::
20 * Problem 1-3 Priority Scheduling::
21 * Problem 1-4 Advanced Scheduler::
25 @node Understanding Threads, Debugging versus Testing, Project 1--Threads, Project 1--Threads
26 @section Understanding Threads
28 The first step is to read and understand the initial thread system.
29 Pintos, by default, implements thread creation and thread completion,
30 a simple scheduler to switch between threads, and synchronization
31 primitives (semaphores, locks, and condition variables).
32 @c FIXME: base system doesn't do anything. Debugger sucks.
33 However, there's a lot of magic going on in some of this code, so you
34 should compile and run the base system to see a simple test of the
35 code. You should trace the execution using your favorite debugger to
36 get a sense for what's going on.
38 When a thread is created, you are creating a new context to be
39 scheduled. You provide a function to be run in this context as an
40 argument to @code{thread_create()}. The first time the thread is
41 scheduled and runs, it will start from the beginning of that function
42 and execute it in the context. When that function returns, that thread
43 completes. Each thread, therefore, acts like a mini-program running
44 inside Pintos, with the function passed to @code{thread_create()}
45 acting like @code{main()}.
47 At any given time, Pintos is running exactly one thread, with the
48 others switched out. The scheduler decides which thread to run next
49 when it needs to switch between them. (If no thread is ready to run
50 at any given time, then the special ``idle'' thread runs.) The
51 synchronization primitives are used to force context switches when one
52 thread needs to wait for another thread to do something.
54 The exact mechanics of a context switch are pretty gruesome and have
55 been provided for you in @file{switch.S} (this is 80@var{x}86
56 assembly; don't worry about understanding it). It involves saving the
57 state of the currently running thread and restoring the state of the
58 thread we're switching to.
60 Slowly trace through a context switch to see what happens. Be sure to
61 keep track of each thread's address and state, and what procedures are
62 on the call stack for each thread. You will notice that when one
63 thread calls @code{switch_threads()}, another thread starts running,
64 and the first thing the new thread does is to return from
65 @code{switch_threads()}. We realize this comment will seem cryptic to
66 you at this point, but you will understand threads once you understand
67 why the @code{switch_threads()} that gets called is different from the
68 @code{switch_threads()} that returns.
70 @strong{Warning}: In Pintos, each thread is assigned a small,
71 fixed-size execution stack just under @w{4 kB} in size. The kernel
72 does try to detect stack overflow, but it cannot always succeed. You
73 ma cause bizarre problems, such as mysterious kernel panics, if you
74 declare large data structures as non-static local variables,
75 e.g. @samp{int buf[1000];}. Alternatives to stack allocation include
76 the page allocator in @file{threads/palloc.c} and the block allocator
77 in @file{threads/malloc.c}. Note that the page allocator doles out
78 @w{4 kB} chunks and that @code{malloc()} has a @w{2 kB} block size
79 limit. If you need larger chunks, consider using a linked structure
82 @node Debugging versus Testing, Tips, Understanding Threads, Project 1--Threads
83 @section Debugging versus Testing
85 When you're debugging code, it's useful to be able to be able to run a
86 program twice and have it do exactly the same thing. On second and
87 later runs, you can make new observations without having to discard or
88 verify your old observations. This property is called
89 ``reproducibility.'' The simulator we use, Bochs, can be set up for
90 reproducibility. If you use the Bochs configuration files we provide,
91 which specify @samp{ips: @var{n}} where @var{n} is a number of
92 simulated instructions per second, your simulations can be
95 Of course, a simulation can only be reproducible from one run to the
96 next if its input is the same each time. For simulating an entire
97 computer, as we do, this means that every part of the computer must be
98 the same. For example, you must use the same disks, the same version
99 of Bochs, and you must not hit any keys on the keyboard (because you
100 could not be sure to hit them at exactly the same point each time)
103 While reproducibility is useful for debugging, it is a problem for
104 testing thread synchronization, an important part of this project. In
105 particular, when Bochs is set up for reproducibility, timer interrupts
106 will come at perfectly reproducible points, and therefore so will
107 thread switches. That means that running the same test several times
108 doesn't give you any greater confidence in your code's correctness
109 than does running it only once.
111 So, to make your code easier to test, we've added a feature to Bochs
112 that makes timer interrupts come at random intervals, but in a
113 perfectly predictable way. In particular, if you put a line
114 @samp{ips-jitter: @var{seed}}, where @var{seed} is an integer, into
115 your Bochs configuration file, then timer interrupts will come at
116 irregularly spaced intervals. Within a single @var{seed} value,
117 execution will still be reproducible, but timer behavior will change
118 as @var{seed} is varied. Thus, for the highest degree of confidence
119 you should test your code with many seed values.
121 @node Tips, Problem 1-1 Alarm Clock, Debugging versus Testing, Project 1--Threads
124 There should be no busy-waiting in any of your solutions to this
125 assignment. Furthermore, resist the temptation to directly disable
126 interrupts in your solution by calling @code{intr_disable()} or
127 @code{intr_set_level()}, although you may find doing so to be useful
128 while debugging. Instead, use semaphores, locks and condition
129 variables to solve synchronization problems. Hint: read the comments
130 in @file{threads/synch.h} if you're unsure what synchronization
131 primitives may be used in what situations.
133 Given some designs of some problems, there may be one or two instances
134 in which it is appropriate to directly change the interrupt levels
135 instead of relying on the given synchroniztion primitives. This must
136 be justified in your @file{DESIGNDOC} file. If you're not sure you're
139 While all parts of this assignment are required if you intend to earn
140 full credit on this project, keep in mind that Problem 2 (Join) will
141 be needed for future assignments, so you'll want to get this one
142 right. We don't give out solutions, so you're stuck with your Join
143 code for the whole quarter. Problem 1 (Alarm Clock) could be very
144 handy, but not strictly required in the future. The upshot of all
145 this is that you should focus heavily on making sure that your
146 implementation of Join works correctly, since if it's broken, you will
147 need to fix it for future assignments. The other parts can be turned
148 off in the future if you find you can't make them work quite right.
150 Also keep in mind that Problem 4 (the MFQS) builds on the features you
151 implement in Problem 3, so to avoid unnecessary code duplication, it
152 would be a good idea to divide up the work among your team members
153 such that you have Problem 3 fully working before you begin to tackle
156 @node Problem 1-1 Alarm Clock, Problem 1-2 Join, Tips, Project 1--Threads
157 @section Problem 1-2: Alarm Clock
159 Improve the implementation of the timer device defined in
160 @file{devices/timer.c} by reimplementing @code{timer_msleep(0}.
161 Threads call @code{timer_msleep(@var{x})} to suspend execution until
162 time has advanced by at least @w{@var{x} milliseconds}. This is
163 useful for threads that operate in real-time, for example, for
164 blinking the cursor once per second. There is no requirement that
165 threads start running immediately after waking up; just put them on
166 the ready queue after they have waited for approximately the right
169 A working implementation of this function is provided. However, the
170 version provided is poor, because it ``busy waits,'' that is, it spins
171 in a tight loop checking the current time until the current time has
172 advanced far enough. This is undesirable because it wastes time that
173 could potentially be used more profitably by another thread. Your
174 solution should not busy wait.
176 The argument to @code{timer_msleep()} is expressed in milliseconds.
177 You must convert it into timer ticks, rounding up. The code provided
178 does this acceptably; there is no need to change it.
180 @node Problem 1-2 Join, Problem 1-3 Priority Scheduling, Problem 1-1 Alarm Clock, Project 1--Threads
181 @section Problem 1-2: Join
183 Implement @code{thread_join(struct thread *)} in
184 @file{threads/thread.c}. There is already a prototype for it in
185 @file{threads/thread.h}, which you should not change. This function
186 causes the currently running thread to block until thread passed as an
187 argument exits. If A is the running thread and B is the argument,
188 then we say that ``A joins B'' in this case.
190 The model for @code{thread_join()} is the @command{wait} system call
191 in Unix-like systems. (Try reading the manpages.) That system call
192 can only be used by a parent process to wait for a child's death. You
193 should implement @code{thread_join()} to have the same restriction.
194 That is, a thread may only join on its immediate children.
196 A thread need not ever be joined. Your solution should properly free
197 all of a thread's resources, including its @code{struct thread},
198 whether it is ever joined or not, and regardless of whether the child
199 exits before or after its parent. That is, a thread should be freed
200 exactly once in all cases.
202 Joining a given thread is idempotent. That is, joining a thread T
203 multiple times is equivalent to joining it once, because T has already
204 exited at the time of the later joins. Thus, joins on T after the
205 first should return immediately.
207 The behavior of calling @code{thread_join()} on an thread that is not
208 the caller's child is undefined. You need not handle this case
211 Consider all the ways a join can occur: nested joins (A joins B when B
212 is joined on C), multiple joins (A joins B, then A joins C), and so
213 on. Does your join work if @code{thread_join()} is called on a thread
214 that has not yet been scheduled for the first time? You should handle
215 all of these cases. Write test code that demonstrates the cases your
216 join works for. Don't overdo the output volume, please!
218 Be careful to program this function correctly. You will need its
219 functionality for project 2.
221 @node Problem 1-3 Priority Scheduling, Problem 1-4 Advanced Scheduler, Problem 1-2 Join, Project 1--Threads
222 @section Problem 1-3 Priority Scheduling
224 Implement priority scheduling in Pintos. Priority
225 scheduling is a key building block for real-time systems. Implement functions
226 @code{thread_set_priority()} to set the priority of a thread and
227 @code{thread_get_priority()} to get the priority of a thread. There
228 are already prototypes for these functions in @file{threads/thread.h},
229 which you should not change.
231 When a thread is added to the ready list that has a higher priority
232 than the currently running thread, the current thread should
233 immediately yield the processor to the new thread. Similarly, when
234 threads are waiting for a lock, semaphore or condition variable, the
235 highest priority waiting thread should be woken up first. A thread's
236 priority may be set at any time, including while the thread is waiting
237 on a lock, semaphore, or condition variable.
239 One issue with priority scheduling is ``priority inversion'': if a
240 high priority thread needs to wait for a low priority thread (for
241 instance, for a lock held by a low priority thread, or in
242 @code{thread_join()} for a thread to complete), and a middle priority
243 thread is on the ready list, then the high priority thread will never
244 get the CPU because the low priority thread will not get any CPU time.
245 A partial fix for this problem is to have the waiting thread
246 ``donate'' its priority to the low priority thread while it is holding
247 the lock, then recall the donation once it has acquired the lock.
250 You will need to account for all different orders that priority
251 donation and inversion can occur. Be sure to handle multiple
252 donations, in which multiple priorities are donated to a thread. You
253 must also handle nested donation: given high, medium, and low priority
254 threads H, M, and L, respectively, and supposing H is waiting on a
255 lock that M holds and M is waiting on a lock that L holds, both M and
256 L should be boosted to H's priority.
258 You only need to implement priority donation when a thread is waiting
259 for a lock held by a lower-priority thread. You do not need to
260 implement this fix for semaphores, condition variables or joins.
261 However, you do need to implement priority scheduling in all cases.
263 @node Problem 1-4 Advanced Scheduler, Threads FAQ, Problem 1-3 Priority Scheduling, Project 1--Threads
264 @section Problem 1-4 Advanced Scheduler
266 Implement Solaris's multilevel feedback queue scheduler (MFQS), as
267 explained below, to reduce the average response time for running jobs
271 Demonstrate that your scheduling algorithm reduces response time
272 relative to the original Pintos scheduling algorithm (round robin) for
273 at least one workload of your own design (i.e. in addition to the
276 You may assume a static priority for this problem. It is not necessary
277 to ``re-donate'' a thread's priority if it changes (although you are
280 @node Threads FAQ, , Problem 1-4 Advanced Scheduler, Project 1--Threads
288 @b{I am adding a new @file{.h} or @file{.c} file. How do I fix the
291 To add a @file{.c} file, edit the top-level @file{Makefile.build}.
292 You'll want to add your file to variable @samp{@var{dir}_SRC}, where
293 @var{dir} is the directory where you added the file. For this
294 project, that means you should add it to @code{threads_SRC}, or
295 possibly @code{devices_SRC} if you put in the @file{devices}
296 directory. Then run @code{make}. If your new file doesn't get
297 compiled, run @code{make clean} and then try again.
299 There is no need to edit the @file{Makefile}s to add a @file{.h} file.
302 @b{If a thread finishes, should its children be terminated immediately,
303 or should they finish normally?}
305 You should feel free to decide what semantics you think this
306 should have. You need only provide justification for your
310 @b{Why can't I disable interrupts?}
312 Turning off interrupts should only be done for short amounts of time,
313 or else you end up losing important things such as disk or input
314 events. Turning off interrupts also increases the interrupt handling
315 latency, which can make a machine feel sluggish if taken too far.
316 Therefore, in general, setting the interrupt level should be used
317 sparingly. Also, any synchronization problem can be easily solved by
318 turning interrupts off, since while interrupts are off, there is no
319 concurrency, so there's no possibility for race condition.
321 To make sure you understand concurrency well, we are discouraging you
322 from taking this shortcut at all in your solution. If you are unable
323 to solve a particular synchronization problem with semaphores, locks,
324 or conditions, or think that they are inadequate for a particular
325 reason, you may turn to disabling interrupts. If you want to do this,
326 we require in your design document a complete justification and
327 scenario (i.e.@: exact sequence of events) to show why interrupt
328 manipulation is the best solution. If you are unsure, the TAs can
329 help you determine if you are using interrupts too haphazardly. We
330 want to emphasize that there are only limited cases where this is
334 @b{Where might interrupt-level manipuation be appropriate?}
336 You might find it necessary in some solutions to the Alarm problem.
338 You might want it at one small point for the priority scheduling
339 problem. Note that it is not required to use interrupts for these
340 problems. There are other, equally correct solutions that do not
341 require interrupt manipulation. However, if you do manipulate
342 interrupts and @strong{correctly and fully document it} in your design
343 document, we will allow limited use of interrupt disabling.
346 @item Alarm Clock FAQs
350 @b{Why can't I use most synchronization primitives in an interrupt
353 As you've discovered, you cannot sleep in an external interrupt
354 handler. Since many lock, semaphore, and condition variable functions
355 attempt to sleep, you won't be able to call those in
356 @code{timer_interrupt()}. You may still use those that never sleep.
358 Having said that, you need to make sure that global data does not get
359 updated by multiple threads simultaneously executing
360 @code{timer_msleep()}. Here are some pieces of information to think
365 Interrupts are turned off while @code{timer_interrupt()} runs. This
366 means that @code{timer_interrupt()} will not be interrupted by a
367 thread running in @code{timer_msleep()}.
370 A thread in @code{timer_msleep()}, however, can be interrupted by a
371 call to @code{timer_interrupt()}, except when that thread has turned
375 Examples of synchronization mechanisms have been presented in lecture.
376 Going over these examples should help you understand when each type is
381 @b{What about timer overflow due to the fact that times are defined as
382 integers? Do I need to check for that?}
384 Don't worry about the possibility of timer values overflowing. Timer
385 values are expressed as signed 63-bit numbers, which at 100 ticks per
386 second should be good for almost 2,924,712,087 years.
393 @b{Am I correct to assume that once a thread is deleted, it is no
394 longer accessible by the parent (i.e.@: the parent can't call
395 @code{thread_join(child)})?}
397 A parent joining a child that has completed should be handled
398 gracefully and should act as a no-op.
401 @item Priority Scheduling FAQs
405 @b{Doesn't the priority scheduling lead to starvation? Or do I have to
406 implement some sort of aging?}
409 It is true that strict priority scheduling can lead to starvation
410 because thread may not run if a higher-priority thread is runnable.
411 In this problem, don't worry about starvation or any sort of aging
412 technique. Problem 4 will introduce a mechanism for dynamically
413 changing thread priorities.
415 This sort of scheduling is valuable in real-time systems because it
416 offers the programmer more control over which jobs get processing
417 time. High priorities are generally reserved for time-critical
418 tasks. It's not ``fair,'' but it addresses other concerns not
419 applicable to a general-purpose operating system.
422 @b{After a lock has been released, does the program need to switch to
423 the highest priority thread that needs the lock (assuming that its
424 priority is higher than that of the current thread)?}
426 When a lock is released, the highest priority thread waiting for that
427 lock should be unblocked and put on the ready to run list. The
428 scheduler should then run the highest priority thread on the ready
432 @b{If a thread calls @code{thread_yield()} and then it turns out that
433 it has higher priority than any other threads, does the high-priority
434 thread continue running?}
436 Yes. If there is a single highest-priority thread, it continues
437 running until it blocks or finishes, even if it calls
438 @code{thread_yield()}.
441 @b{If the highest priority thread is added to the ready to run list it
442 should start execution immediately. Is it immediate enough if I
443 wait until next timer interrupt occurs?}
445 The highest priority thread should run as soon as it is runnable,
446 preempting whatever thread is currently running.
449 @b{What happens to the priority of the donating thread? Do the priorities
452 No. Priority donation only changes the priority of the low-priority
453 thread. The donating thread's priority stays unchanged. Also note
454 that priorities aren't additive: if thread A (with priority 5) donates
455 to thread B (with priority 3), then B's new priority is 5, not 8.
458 @b{Can a thread's priority be changed while it is sitting on the ready
461 Yes. Consider this case: low-priority thread L currently has a lock
462 that high-priority thread H wants. H donates its priority to L (the
463 lock holder). L finishes with the lock, and then loses the CPU and is
464 moved to the ready queue. Now L's old priority is restored while it
465 is in the ready queue.
468 @b{Can a thread's priority change while it is sitting on the queue of a
471 Yes. Same scenario as above except L gets blocked waiting on a new
472 lock when H restores its priority.
475 @b{Why is pubtest3's FIFO test skipping some threads! I know my scheduler
476 is round-robin'ing them like it's supposed to! Our output is like this:}
490 @noindent @b{which repeats 5 times and then}
500 This happens because context switches are being invoked by the test
501 when it explicitly calls @code{thread_yield()}. However, the time
502 slice timer is still alive and so, every tick (by default), thread 1
503 gets switched out (caused by @code{timer_interrupt()} calling
504 @code{intr_yield_on_return()}) before it gets a chance to run its
505 mainline. It is by coincidence that Thread 1 is the one that gets
506 skipped in our example. If we use a different jitter value, the same
507 behavior is seen where a thread gets started and switched out
510 Solution: Increase the value of @code{TIME_SLICE} in
511 @file{devices/timer.c} to a very high value, such as 10000, to see
512 that the threads will round-robin if they aren't interrupted.
515 @b{What happens when a thread is added to the ready list which has
516 higher priority than the currently running thread?}
518 The correct behavior is to immediately yield the processor. Your
519 solution must act this way.
522 @b{What range of priorities should be supported and what should the
523 default priority of a thread be?}
525 Your implementation should support priorities from 0 through 59 and
526 the default priority of a thread should be 29.
529 @item Advanced Scheduler FAQs
533 @b{What is the interval between timer interrupts?}
535 Timer interrupts occur @code{TIMER_FREQ} times per second. You can
536 adjust this value by editing @file{devices/timer.h}. The default is
540 @b{Do I have to modify the dispatch table?}
542 No, although you are allowed to. It is possible to complete
543 this problem (i.e.@: demonstrate response time improvement)
547 @b{When the scheduler changes the priority of a thread, how does this
548 affect priority donation?}
550 Short (official) answer: Don't worry about it. Your priority donation
551 code may assume static priority assignment.
553 Longer (unofficial) opinion: If you wish to take this into account,
554 however, your design may end up being ``cleaner.'' You have
555 considerable freedom in what actually takes place. I believe what
556 makes the most sense is for scheduler changes to affect the
557 ``original'' (non-donated) priority. This change may actually be
558 masked by the donated priority. Priority changes should only
559 propagate with donations, not ``backwards'' from donees to donors.
562 @b{What is meant by ``static priority''?}
564 Once thread A has donated its priority to thread B, if thread A's
565 priority changes (due to the scheduler) while the donation still
566 exists, you do not have to change thread B's donated priority.
567 However, you are free to do so.
570 @b{Do I have to make my dispatch table user-configurable?}
572 No. Hard-coding the dispatch table values is fine.