Assuming you go with the mainstream lab, you will be building on your work from lab 2, in which you implemented locks and condition variables in Nachos. In this lab you will add the ability to detect deadlocks and even recover from them. Your system only needs to detect deadlocks formed using just locks, you needn't worry about deadlocks involving semaphores or a mix of semaphores and locks.
The first thing to do is to add another operation to the
Lock class, namely
TryToAcquire. It should
Acquire except that rather than returning
void, i.e., no value, it returns a
which should be true if the lock was successfully acquired (possibly
after waiting for another thread to release it), and false if the lock
was not acquired because waiting for it would have formed a deadlock.
Acquire method should be rewritten to simply do the
ASSERT(TryToAcquire());I.e., it should leave all the real work to
TryToAcquire, and if it receives the bad news that a deadlock was detected, then it should halt Nachos's execution completely with the assertion failure. Note that to implement this deadlock detection, you may need to make other changes, for example keeping track in the
Threadobjects for blocked threads of which
Lockthey are waiting for.
At this point you should have a system that does deadlock detection,
but has no recovery mechanism other than causing the whole Nachos
system to bomb out. The first test you do should be that a
non-deadlocking system still works as before; the prime number sieve
from lab 2 would be a fine test for this. Next you should modify what
ThreadTest procedure (in
such that a deadlock results, and verify that the deadlock is detected
Acquire duly aborts
Nachos. (Your modified code should still be using
Acquire, not (directly)
order to make the deadlock actually happen, you may need to insert
currentThread->Yield(); into your threads at appropriate
points (as well as the more substantive changes to make the deadlock
possible), so that the two threads executions are appropriately
interleaved. The debugging output may help you make sure that you
understand what is happening.
Now you are ready to make a more sophisticated test program that uses
TryToAcquire to detect a deadlock, but then recovers
itself from it in a more sophisticated manner. In particular, set up
two threads that each need two locks, let's say A and B. One thread
should acquire A, then try to acquire B, while the other acquires B,
then tries to acquire A. However, in each thread if the attempt to
acquire the second lock fails (due to deadlock detection), the thread
should recover by releasing the lock it already holds, yielding, and
then starting the process over. Use debugging output to ensure that
indeed the deadlock situation is being detected and recovered from.
As before, you may need to put in some strategically placed yields to
make the deadlock actually occur.
Instructor: Max Hailperin