You may need to write code that acquires more than one lock. This opens up the possibility of deadlock. Consider the following piece of code:

Lock *l1, *l2;

void p () {

l1->Acquire();

l2->Acquire();

code that manipulates data that l1 and l2 protect

l2->Release();

l1->Release();

}

void q() {

l2->Acquire();

l1->Acquire();

code that manipulates data that l1 and l2 protect

l1->Release();

l2->Release();

}

If p and q execute concurrently, consider what may happen. First, p acquires l1 and q acquires l2. Then, p waits to acquire l2 and q waits to acquire l1. How long will they wait? Forever.

This case is called deadlock. What are conditions for deadlock?

• Mutual Exclusion: Only one thread can hold lock at a time.
• Hold and Wait: At least one thread holds a lock and is waiting for another process to release a lock.
• No preemption: Only the process holding the lock can release it.
• Circular Wait: There is a set t₁, …, t_n such that t₁ is waiting for a lock held by t₂, …, t_n is waiting for a lock held by t₁

How can p and q avoid deadlock? Order the locks, and always acquire the locks in that order. Eliminates the circular wait condition.

Occasionally you may need to write code that needs to acquire locks in different orders. Here is what to do in this situation.

• First, most locking abstractions offer an operation that tries to acquire the lock but returns if it cannot. We will call this operation Try Acquire. Use this operation to try to acquire the lock that you need to acquire out of order.
• If the operation succeeds, fine. Once you’ve got the lock, there is no problem.
• If the operation fails, your code will need to release all locks that come after the lock you are trying to acquire. Make sure the associated data structures are in a state where you can release the locks without crashing the system.
• Release all of the locks that come after the lock you are trying to acquire, then reacquire all of the locks in the right order. When the code resumes, bear in mind that the data structures might have changed between the time when you released and reacquired the lock.

Here is an example.

int d1, d2;

// The standard acquisition order for these two locks

// is l1, l2.

Lock *l1, // protects d1

*l2; // protects d2

// Decrements d2, and if the result is 0, increments d1

void increment() {

l2->Acquire();

int t = d2;

t--;

if (t == 0) {

if (l1->TryAcquire()) {

d1++;

} else {

// Any modifications to d2 go here - in this case none

l2->Release();

l1->Acquire();

l2->Acquire();

t = d2;

t--;

// some other thread may have changed d2 - must recheck it

if (t == 0) {

d1++;

}

}

l1->Release();

}

d2 = t;

l2->Release();

}

This example is somewhat contrived, but you will recognize the situation when it occurs.

For preventing a dead lock system can either

• Restrict the way in which processes will request resources to prevent deadlock.
• Require processes to give advance information about which resources they will require, then use algorithms that schedule the processes in a way that avoids deadlock.
• Detect and eliminate deadlock when it occurs