Discussion Notes for 10/11-13

We discussed the solutions to the deadlock problem. Points to take away from the discussion:

We went over the conditions for a deadlock:

limited resources where each resource requires mutually exclusive access
no-preemption
circular wait
hold&wait

In part (a), you solved the problem by attacking the "circular wait" condition. Locks were the resources in our example. To prevent circular wait, locks had to be acquired in order (ascending or decending order).
Part (b) was somewhat tricky. You had to come up with a solution that attacked the "hold&wait" condition: never hold a resource and wait for some other resource to be avaiable.

We went over this incorrect solution:

thread_lock(global);
thread_lock(locks[id1]);
thread_lock(locks[id2]);
thread_unlock(global);
<transfer money>
thread_lock(global);
thread_unlock(locks[id1]);
thread_unlock(locks[id2]);
thread_unlock(global);

Consider the following example
Thread 1
1. thread_lock(global);
2. thread_lock(locks[1]);
3. thread_lock(locks[2]);
4. thread_unlock(global);

Thread 2
5. thread_lock(global);
6. thread_lock(locks[3]);
7. thread_lock(locks[2]); // Thread 2 will block here
... Thread 2 is still holding the "global" lock.

Thread 1
cannot release locks[2]
because it cannot acquire the
"global" lock

One possible solution to keep the mutual exclusion lock (global) through out the transfer

thread_lock(global);
thread_lock(locks[id1]);
thread_lock(locks[id2]);
thread_unlock(global);
<transfer money>
thread_lock(global);
thread_unlock(locks[id1]);
thread_unlock(locks[id2]);
thread_unlock(global);

This serializes all requests: transfers between two un-related accounts cannot happen concurrently. BAD.

Another solution (raised during the discussion) proposes to unlock individual locks without holding the global lock. This solution removes the deadlock, but once again it hurts the concurrency. As soon as two interfering transfers occur (1 to 2 and 2 to 3), all other un-related transfers block (5 to 7) because the 2nd thread (2 to 3) is waiting for lock 2 but holds the global lock. BAD.
We went over a solution that implements "trylock". The idea is that you want to check if a thread can get the lock and if it cannot, then wait on a condition variable.