1 PROJECT 1 GRADING ADVICE
2 ========================
4 This file contains advice for grading project 1. General advice for
5 Pintos grading is in README, which you should read first.
10 Most students solve this problem with a linked list of sleeping
11 threads and a timer interrupt handler that wakes up sleeping threads
12 at the appropriate time. Details that distinguish solutions include:
14 - List ordering: Good solutions order the list of threads by
17 - Time left vs. wake-up time: Good solutions store the wake-up
18 time in the list, instead of the number of ticks remaining.
20 - Interrupt efficiency: Good solutions that order the list by
21 wake-up time and store wake-up times (see above two items),
22 only need their timer interrupt to examine as many items in
23 the list as are actually waking up on this tick (plus one).
24 Otherwise, every sleeping thread must be examined (and
27 - Allocation: Good solutions put the fields needed for
28 sleeping in struct thread (or, possibly, in local
29 variables). Dynamic allocation is another possibility, but
30 malloc() failure must be dealt with; it is unacceptable to
31 busy-wait or fail to wait if malloc() fails. A third
32 possibility is a static array of list elements, but that
33 puts a fixed limit on the number of simultaneously sleeping
34 threads, which is also unacceptable.
36 - Synchronization: Most solutions manipulate the list with
37 interrupts disabled to protect against the interrupt
38 handler. Other solutions are possible but most of them are
39 incorrect--watch out for missing optimization barriers (see the
40 Optimization Barriers section in the reference guide) or bad
41 assumptions of atomicity when there is none.
43 In most solutions only the list insertion (typically a
44 single call to list_insert_ordered()) needs to be protected
45 by disabling interrupts.
47 - Wake-up precision: Good solutions wake up sleeping threads
48 at exactly the tick they should (although the timer
49 interrupt might be processed a little late due to disabled
50 interrupts). Some solutions deal with synchronization by
51 delaying a wake-up that should occur during a call to
52 timer_sleep() until the following timer tick, which is
55 - Wake-one vs. wake-all: Good solutions wake up all the
56 threads that are scheduled to wake up at a particular timer
57 tick. Bad solutions only wake up one thread and delay
58 waking the next until the following timer tick.
62 Usually this includes a structure or, as in the sample solution,
63 new members in struct thread:
66 int64_t wakeup_time; /* Time to wake this thread up. */
67 struct list_elem timer_elem; /* Element in wait_list. */
68 struct semaphore timer_sema; /* Semaphore. */
70 Typically there is a global list of sleeping threads also:
72 /* Threads waiting in timer_sleep(). */
73 static struct list wait_list;
77 Usually, timer_sleep() initializes a data structure (or struct
78 thread members) and, with interrupts disabled, inserts it in the
79 correct position on the global list. Then it goes to sleep by
82 On each tick, the timer interrupt handler checks the front of the
83 list. If it is ready to wake up, it pops it off the list, ups its
84 semaphore, and checks the next one. If it's not ready, then none
85 of the others can be ready, either, so it's done.
89 Ordering the list by time of wake-up and storing wake-up times
90 instead of ticks remaining, typically. (Some students don't
91 realize that the latter is an optimization, because it is so
92 obvious; that's fine, as long as they mention the first part.)
96 Typically only the global list itself is shared with other
97 threads, and the list elements are private, so that disabling
98 interrupts to insert into the list is sufficient.
100 If the group introduces additional synchronization, such as a
101 semaphore, make sure that it is actually needed.
105 Typically, disabling interrupts around the list insertion protects
106 against races against the timer interrupt.
110 A good discussion will mention some of the features on the list of
111 distinguishing characteristics above.
113 It is insufficient to compare against "solutions" that do not
114 satisfy the terms of the assignment, such as against the supplied
115 code that busy-waits.
120 Priority scheduling by itself is a simple exercise. Priority donation
121 is more difficult. Many groups do not seem to completely grasp the
122 structure of priority donation. Some properties of priority donation
123 that you may find useful while grading:
125 - A thread can only directly donate its priority to at most
126 one donee thread at a time, because donation only occurs
127 when a thread is blocked waiting for a lock, and a thread
128 can only block waiting for a single lock at a time.
130 This property means that each thread can keep track of its
131 donee, if any, with a single pointer in struct thread.
133 - A thread can receive donations from any number of threads,
134 because any number of threads can wait on a lock. The
135 donors may be waiting for a single lock or multiple locks.
137 These first two properties, taken together, mean that if a
138 thread keeps a "struct list" of its donor threads, a single
139 list_elem in "struct thread" in the donor is sufficient,
140 because the donor cannot be donating (directly) to more than
143 - Donations can nest to form a tree, but circularity is
144 impossible as long as no deadlock in the locking structure
145 exists. Deadlock would itself be a bug, so there is no need
146 to worry about circularity in donations.
150 The sample solution has essentially a minimal set of additions to
153 /* Scheduler data. */
154 int priority; /* Priority, including donations. */
155 int normal_priority; /* Priority, without donations. */
156 struct list donors; /* Threads donating priority to us. */
157 struct list_elem donor_elem; /* Element in donors list. */
158 struct thread *donee; /* Thread we're donating to. */
159 struct lock *want_lock; /* Lock we're waiting to acquire. */
161 The sample solution redefines the "priority" member to include
162 priority donations and adds a second "normal_priority" member that
163 does not include donations. An alternative might be to
164 recalculate the donated priority whenever it is needed, but this
165 is often, so a good rationale would be required.
167 Some submissions omit the list of donors and attempt to record
168 pre-donation priority in the "struct lock" whose ownership causes
169 the donation. These submissions typically just restore the
170 original priority when the lock is released. But this is
171 insufficient. Consider a thread of priority 3 that owns locks A
172 and B and that receives a donation of priority 5 via A, then
173 priority 8 via B. If it releases A first, then its priority will
174 be restored to 3, even though it should be 5. Deduct points for
175 such an implementation.
177 A common mistake is dynamically allocating the list of donations.
178 It is unacceptable to fail to maintain the required semantics if
179 malloc() fails. Failing to check malloc() for failure is also
180 unacceptable (see the OVERALL section).
182 A global list of donations is not necessary. Deduct points if one
185 Most solutions add an element to struct semaphore_elem also, used
186 in cond_signal() to find the highest-priority waiting thread to
188 struct thread *thread; /* Thread. */
189 If the students don't mention such an addition, check whether they
190 made one. If so, deduct a few points for failing to mention it.
191 If not, read the answer to B3 carefully and make sure that they
192 actually handle condition variables properly.
196 The minimum ASCII art requirement here includes three threads and
197 two locks, e.g. for the sample solution:
199 /--------------------------\
201 /------------------------\ |
202 Thread H V Thread M V | Thread L |
203 +-------------+ +-------------+ | +----------------+ |
204 |priority = 8 | |priority = 8 | | |priority = 8 | |
205 |norm_pri = 8 | |norm_pri = 5 | | |norm_pri = 3 | |
206 |donors = {} | |donors = {H} |-/ |donors = {M} |-/
207 |donee = M |---->|donee = L |---->|donee = null |
208 |want_lock = A|--\ |want_lock = B|--\ |want_lock = null|
209 +-------------+ | +-------------+ | +----------------+
211 | Lock A V | | V Lock B |
212 | +-------------+ | | +-------------+ |
213 | |holder = M |-/ | |holder = L |-/
214 | |waiters = {H}|-\ | |waiters = {M}|-\
215 | +-------------+ | | +-------------+ |
217 \------------------/ \------------------/
219 Some explanatory text must also be included.
223 The answer must describe what happens for each kind of
224 synchronization primitive.
226 For semaphores, typically sema_up() selects the highest-priority
227 thread on the wait list, instead of the one that has been waiting
230 Locks are implemented in terms of semaphores so no extra work is
231 typically needed (but the submission must say this).
233 Condition variables need the same kind of change as semaphores.
235 One minor issue is the ordering of the ready_list and other lists
236 (such as semaphore lists) that keep track of threads waiting for
237 various events. It makes sense to maintain these in sorted order,
238 but threads' priorities can change while they waiting on lists,
239 which would require their positions to be adjusted (see the FAQ
240 for this problem). In practice it may be easier to simply search
241 the lists for maximum or minimum elements when required, as done
242 in the sample solution.
246 The expected answer is that lock_acquire() determines the holder
247 of the lock (lock->holder), if any, and then donate the current
248 thread's priority to it. The answer must mention how the priority
249 donation cascades through to nested donations.
251 There is a race in lock_acquire() between checking for the lock's
252 holder and "down"ing the semaphore. The obvious way to fix this
253 is by disabling interrupts before checking the holder and keeping
254 them off until after sema_down() returns. You will check the code
255 for this by hand (see below).
259 The expected answer is that lock_release() returns the donations
260 to the threads waiting for the lock, releases the semaphore, and
261 recomputes the current thread's priority.
263 Take a closer look if the answer says something about "restoring",
264 or similar, a previous priority instead of recomputing it. This
265 probably indicates that the implementation is buggy: it will fail
266 in the same way described in the last paragraph of B1 (above).
267 Deduct points for such an implementation.
271 The expected answer is that thread_set_priority() needs to
272 recompute the priority based on the highest donated priority and
273 the new base priority (see the FAQ for this problem for details).
274 However, the donated priorities can change during the computation
275 (e.g. a new donation can occur when another thread attempts to
276 take a lock owned by this thread).
278 A lock cannot easily be used to avoid this race, because
279 lock_acquire() would need to take it before making a new
280 donation, and that would cause lock_acquire() to call itself. The
281 problem is probably solvable, but it is more straightforward to
282 simply disable interrupts.
284 Sometimes students identify other races in this function. That is
285 acceptable, as long as it is a genuine race and they describe it
290 The issue mentioned in the final paragraph of B3 above may come up
293 Check the submitted code, by hand, for the following:
295 1. When sema_up() unblocks a thread with a higher priority than the
296 running thread, it yields to it, but *not* if it unblocks a thread
297 with priority equal to or lower than the running thread.
299 2. When sema_up() does not unblock a thread, it does not yield.
301 3. Race condition between priority donation, which is probably
302 implemented in lock_acquire(), and "down"ing the underlying
303 semaphore, in sema_down(). This likely requires disabling
304 interrupts in lock_acquire(), as done in the sample solution.
306 4. Race condition between release of donated priorities, which is
307 probably implemented in lock_release(), and "up"ing the underlying
308 semaphore, in sema_up(). This likely requires disabling
309 interrupts in lock_release(), as done in the sample solution.
316 Most groups create a list of all threads so that they can update
317 recent_cpu in all of them during a timer interrupt, e.g.:
319 /* List of all threads. */
320 static struct list all_threads_list;
322 Some new "struct thread" members also make sense:
324 int nice; /* Niceness. */
325 fixed_point_t recent_cpu; /* Recent amount of CPU time. */
326 struct list_elem all_elem; /* all_threads list element. */
328 Typically the load average is maintained as a global variable,
331 static fixed_point_t load_avg; /* Load average. */
333 Most groups choose to abstract fixed-point numbers to some extent,
334 and so there is probably an associated type definition, e.g.:
336 /* A fixed-point number. */
345 The first two rows are unambiguous and must be filled in just as
348 timer recent_cpu priority thread
349 ticks A B C A B C to run
350 ----- -- -- -- -- -- -- ------
354 From this point on, the answers will vary because A and B both
355 have equal priority (61) and there is no clearly stated rule on
356 which to choose. Some form of round-robin should be used, and on
357 C3 students must describe how they chose to do it. The following
358 answers give priority to the thread that has run least recently:
366 32 16 12 4 59 58 58 C
367 36 16 12 8 59 58 57 A
369 Don't feel obligated to check every entry. However, please do
370 "spot checks" on at least these rules of thumb:
372 - Within each row, the recent_cpu values must sum to the
373 number of timer ticks.
375 - Only one priority value changes from one row to the next,
376 decreasing by 1 for the thread that was chosen on the
379 - A runs more than B, which runs more than C.
383 - It's possible there are more ambiguities than this one, but
384 that's the one that most students notice.
386 - There is no need for non-integers or rounding in the table.
387 recent_cpu is only reduced based on load_avg every 100
388 ticks, and the table is not that long. (It's possible that
389 some group could choose to reduce recent_cpu in some single
390 row on the assumption that the 100th tick happens there, but
391 no group has actually done that yet.)
395 This is the first quarter we've used this question, so I'm not
396 sure what kind of answers to expect. Please use your judgment in
401 Many groups comment on their choice between a single queue and an
402 array of 64 queues here. Good reasons for either choice include:
404 - Scanning a 64-queue array may waste time if there aren't any
405 high-priority processes. (A good implementation could use a
406 bit vector to avoid scanning empty queues, but this may not
407 be obvious to students.)
409 - A single queue has to be kept sorted, or it has to be
410 searched for the maximum-priority element, but there's no
411 such cost if there are 64 queues--we can just "push" and
414 - A single queue is more flexible if PRI_MIN or PRI_MAX is
415 changed, especially if PRI_MIN is changed to be nonzero or
416 if the range between PRI_MIN and PRI_MAX becomes much
419 If they don't mention this choice, then they should talk about
420 some other important choice.
422 Make sure that each group mentions in their answer at least one
423 advantage and one disadvantage of their design choices.
427 Generally the "right" answer here is that the group designed some
428 kind of abstraction for fixed-point math. If they didn't, then a
429 good justification is needed.
431 Check the submitted code, by hand, for the following:
433 1. That the code that updates the load average, recent_cpu, and
434 thread priorities once per second is readable. It is probably in
435 thread_tick() in thread.c. Look at the code that uses the
436 fixed-point math, in particular, and try to figure out how it
437 implements the formulas for load_avg and updating recent_cpu. As
438 an example, the core of the code in the reference solution is
439 pretty straightforward:
441 /* Update load average. */
442 load_avg = fix_add (fix_mul (fix_frac (59, 60), load_avg),
443 fix_mul (fix_frac (1, 60), fix_int (ready_threads)));
445 /* Update recent_cpu. First, calculate some constants: */
446 fixed_point_t twice_load = fix_scale (load_avg, 2);
447 fixed_point_t twice_load_plus_1 = fix_add (twice_load, fix_int (1));
448 fixed_point_t load_factor = fix_div (twice_load, twice_load_plus_1);
450 /* Then, for each thread: */
451 t->recent_cpu = fix_add (fix_mul (load_factor, t->recent_cpu),
454 If you can't understand how their code does its calculations, take
455 off a lot of points. If you can't understand *easily*, take off a
458 2. That the timer interrupt does *not* update every thread's priority
459 on every fourth timer tick. The 4.4BSD scheduler specification
460 says that priority is "recalculated once every fourth clock tick,
461 for every thread," but clearly the students should realize that
462 only the *running* thread's recent_cpu, and therefore priority,
463 will actually change.
465 This code is probably also in thread_tick() in thread.c.
467 3. For a race condition in thread_get_recent_cpu() or
468 thread_get_load_avg(). Generally these need to be protected by
469 disabling interrupts, because they are updated in the timer
470 interrupt. A call to barrier() would be acceptable, too.