Code with a potential deadlock

Question

// down = acquire the resource
// up = release the resource

typedef int semaphore;
  semaphore resource_1;
  semaphore resource_2;


 void process_A(void) {
    down(&resource_1);
    down(&resource_2);
    use_both_resources();
    up(&resource_2);
    up(&resource_1);
 }

 void process_B(void) {
    down(&resource_2);
    down(&resource_1);
    use_both_resources();
    up(&resource_1);
    up(&resource_2);
 }

Why does this code causes deadlock?

If we change the code of process_B where the both processes ask for the resources in the same order as:

 void process_B(void) {
    down(&resource_1);
    down(&resource_2);
    use_both_resources();
    up(&resource_2);
    up(&resource_1);
 }

Then there is no deadlock.

Why so?

Answer 1

This is a typical deadlock scenario, when you have two threads trying to acquire two locks.

Here's a very nice explanation (search the PDF for "deadlock", or just check out pages 20 and 21). It basically boils down to this:

The slide shows what’s known as a resource graph: a directed graph with two sorts of nodes, representing threads and mutexes (protecting resources). There’s an arc from a mutex to a thread if the thread has that mutex locked. There’s an arc from a thread to a mutex if the thread is waiting to lock that mutex. Clearly, such a graph has a cycle if and only if there is a deadlock.

[Earlier in the document] If thread a obtains mutex 1 and, at about the same time, thread b obtains mutex 2, then if thread a attempts to take mutex 2 and thread b attempts to take mutex 1, we have a deadlock.

Answer 2

A necessary condition for a deadlock is a cycle of resource acquisitions. The first example constructs this a cycle 1->2->1. The second example acquires the resources in a fixed order which makes a cycle and henceforth a deadlock impossible.

Answer 3

Imagine that process A is running and try to get the resource_1 and gets it.

Now, process B takes control and try to get resource_2. And gets it. Now, process B tries to get resource_1 and does not get it, because it belongs to resource A. Then, process B goes to sleep.

Process A gets control again and try to get resource_2, but it belongs to process B. Now he goes to sleep too.

At this point, process A is waiting for resource_2 and process B is waiting for resource_1.

If you change the order, process B will never lock resource_2 unless it gets resource_1 first, the same for process A.

They will never be dead locked.