You only need to implement priority donation when a thread is waiting
for a lock held by a lower-priority thread. You do not need to
-implement this fix for semaphores, condition variables or joins.
-However, you do need to implement priority scheduling in all cases.
+implement this fix for semaphores, condition variables, or joins,
+although you are welcome to do so. However, you do need to implement
+priority scheduling in all cases.
+
+You may assume a static priority for priority donation, that is, it is
+not necessary to ``re-donate'' a thread's priority if it changes
+(although you are free to do so).
@node Problem 1-4 Advanced Scheduler
@section Problem 1-4: Advanced Scheduler
at least one workload of your own design (i.e.@: in addition to the
provided test).
-You may assume a static priority for this problem. It is not necessary
-to ``re-donate'' a thread's priority if it changes (although you are
-free to do so).
-
You must write your code so that we can turn the MLFQS on and off at
compile time. By default, it must be off, but we must be able to turn
it on by inserting the line @code{#define MLFQS 1} in
@item
@b{The test program mostly works but reports a few out-of-order
wake ups. I think it's a problem in the test program. What gives?}
+@anchor{Out of Order 1-1}
This test is inherently full of race conditions. On a real system it
wouldn't work perfectly all the time either. However, you can help it
@file{devices/serial.c}.
@end itemize
-The former two changes are only desirable for testing problem 1-1. You
-should revert them before working on other parts of the project or turn
-in the project. The latter is harmless, so you can retain it or revert
-it at your option.
+The former two changes are only desirable for testing problem 1-1 and
+possibly 1-3. You should revert them before working on other parts
+of the project or turn in the project. The latter is harmless, so you
+can retain it or revert it at your option.
+
+@item
+@b{Should @file{p1-1.c} be expected to work with the MLFQS turned on?}
+
+No. The MLFQS will adjust priorities, changing thread ordering.
@end enumerate
@node Problem 1-2 Join FAQ
lock when H restores its priority.
@item
-@b{Why is pubtest3's FIFO test skipping some threads! I know my scheduler
-is round-robin'ing them like it's supposed to! Our output is like this:}
-
-@example
-Thread 0 goes.
-Thread 2 goes.
-Thread 3 goes.
-Thread 4 goes.
-Thread 0 goes.
-Thread 1 goes.
-Thread 2 goes.
-Thread 3 goes.
-Thread 4 goes.
-@end example
-
-@noindent @b{which repeats 5 times and then}
-
-@example
-Thread 1 goes.
-Thread 1 goes.
-Thread 1 goes.
-Thread 1 goes.
-Thread 1 goes.
-@end example
-
-This happens because context switches are being invoked by the test
-when it explicitly calls @func{thread_yield}. However, the time
-slice timer is still alive and so, every tick (by default), thread 1
-gets switched out (caused by @func{timer_interrupt} calling
-@func{intr_yield_on_return}) before it gets a chance to run its
-mainline. It is by coincidence that Thread 1 is the one that gets
-skipped in our example. If we use a different jitter value, the same
-behavior is seen where a thread gets started and switched out
-completely.
-
-Solution: Increase the value of @code{TIME_SLICE} in
-@file{devices/timer.c} to a very high value, such as 10000, to see
-that the threads will round-robin if they aren't interrupted.
+@b{Why is @file{p1-3.c}'s FIFO test skipping some threads? I know my
+scheduler is round-robin'ing them like it's supposed to. Our output
+starts out okay, but toward the end it starts getting out of order.}
+
+The usual problem is that the serial output buffer fills up. This is
+causing serial_putc() to block in thread @var{A}, so that thread
+@var{B} is scheduled. Thread @var{B} immediately tries to do output
+of its own and blocks on the serial lock (which is held by thread
+@var{A}). Now that we've wasted some time in scheduling and locking,
+typically some characters have been drained out of the serial buffer
+by the interrupt handler, so thread @var{A} can continue its output.
+After it finishes, though, some other thread (not @var{B}) is
+scheduled, because thread @var{B} was already scheduled while we
+waited for the buffer to drain.
+
+There's at least one other possibility. Context switches are being
+invoked by the test when it explicitly calls @func{thread_yield}.
+However, the time slice timer is still alive and so, every tick (by
+default), a thread gets switched out (caused by @func{timer_interrupt}
+calling @func{intr_yield_on_return}) before it gets a chance to run
+@func{printf}, effectively skipping it. If we use a different jitter
+value, the same behavior is seen where a thread gets started and
+switched out completely.
+
+Normally you can fix these problems using the same techniques
+suggested on problem 1-1 (@pxref{Out of Order 1-1}).
@item
@b{What happens when a thread is added to the ready list which has
its priority has been increased by a donation?}
The higher (donated) priority.
+
+@item
+@b{Should @file{p1-3.c} be expected to work with the MLFQS turned on?}
+
+No. The MLFQS will adjust priorities, changing thread ordering.
+
+@item
+@b{@func{printf} in @func{sema_up} or @func{sema_down} makes the
+system reboot!}
+
+Yes. These functions are called before @func{printf} is ready to go.
+You could add a global flag initialized to false and set it to true
+just before the first @func{printf} in @func{main}. Then modify
+@func{printf} itself to return immediately if the flag isn't set.
@end enumerate
@node Problem 1-4 Advanced Scheduler FAQ
projects / pintos-anon / blobdiff