How to solve this deadlock

Question

I have two threads. The two threads must invoke send() (and then receive()) OR receive(), but there is a nice deadlock with this code. Is there a way to solve this problem?

    public class C 
    {
        public static void main(String[] args) 
        {
            Z z1=new Z();
            Z z2=new Z();
            z1.setZ(z2);
            z2.setZ(z1);
            z1.start();
            z2.start();
        }
    }

    class Z extends Thread
    {
        Z z;
        Object lock=new Object();

        public void setZ(Z zz)
        {
            z=zz;
        }

        public void run()
        {
            new Thread()
            {
                public void run()
                {
                    z.send();
                }
            }.start();
            new Thread()
            {
                public void run()
                {
                    z.send();
                }
            }.start();
        }

        public void send()
        {
            synchronized(lock)
            {
                System.out.println("[Z] Send");
                z.receive();
            }
        }

        public void receive()
        {
            synchronized(lock)
            {
                System.out.println("[Z] Receive");
            }
        }
    }

Answer 1

It's quite obvious where the deadlock here is.

z1 spawns two new threads; let's call those T1 and T2. It also creates an instance of Object called lock, let's call this L1. z2 does the same; let's call the threads T3 and T4 and the lock L2.

Now, let's assume*, T1 starts first.

1. T1 calls the send method on the Z instance z2.
2. This method causes T1 to acquire the lock L2 then print out "[Z] Send". The method then calls the receive method on the z1 instance.
3. The receive method on the z1 instance causes T1 to acquire the lock L1, then print out "[Z] Receive".
4. T1 releases the lock L1 then exits the receive method on z1.
5. T1 releases the lock L2 then exits the send method on z2.

Now, let's say that in between steps 2 and 3, T3 is starts and does the following:

1. T3 calls the send method on the Z instance z1.
2. This method causes T3 to acquire the lock L1 then print out "[Z] Send". The method then calls the receive method on the z2 instance.
3. The receive method on the z2 instance causes T3 to try to acquire the lock L2...
4. L2 is already held by T1 and has not been released. So T3 waits.

Switch back to T1, step 3 now becomes this:

3. The receive method on the z1 instance causes T1 to try to acquire the lock L1.
4. L1 is already held by T3 and has not been released. So T1 waits.

Context switch to T3, L2 is still held by T1, T3 waits. Context switch to T1, L1 is still held by T3, T1 waits.

...and so on.

This is the explanation of where the deadlock may occur. To solve it, you may want to move the call to z.receive() outside of the synchronized block in send, so that the lock in the current instance gets released before calling the received method of the other instance:

    public void send()
    {
        synchronized(lock)
        {
            System.out.println("[Z] Send");
        }
        z.receive();
    }

EDIT

If the lock is meant to protect all instances from executing concurrently, then you can use one lock shared across all threads, thus:

class Z extends Thread
{
    static final Object lock=new Object();
    ...
}

Now we only have one lock instance, let's call it L0 and take another look at how the steps above would run:

1. T1 calls the send method on the Z instance z2.
2. This method causes T1 to acquire the lock L0 then print out "[Z] Send". The method then calls the receive method on the z1 instance.
3. The receive method on the z1 instance causes T1 to again acquire the lock L0; because it already holds this lock, it can continue. It prints out "[Z] Receive".
4. T1 exits the receive method on z1.
5. T1 releases the lock L0 then exits the send method on z2.

Again, let's say that in between steps 2 and 3, T3 is starts and does the following:

1. T3 calls the send method on the Z instance z1.
2. This method causes T3 to try to acquire the lock L0.
3. L0 is already held by T1 and has not been released. So T3 waits.

This time step 3 in T1 is unaffected. This means that it can still continue and eventually release the lock L0, which will eventually let T3 acquire that lock and itself continue.

No more deadlock.

__

*Thread start order is never guaranteed to be the same as the order in which the start() methods are called, but in this case, there is a risk of deadlock in all possible scenarios.

Answer 2

The simplest approach, which only requires one line change, is to use a static class level lock instead of a non-static lock.

   private static Object lock=new Object();

First of all, let's look at the root of the problem: In this example, dead lock happens since the two Z instances are holding locks on each other (shared resources), and both are waiting for other’s resource to complete its task. And, none is able to leave the lock on resource it is holding.

Since the lock is non-static, each instance of z will have its own lock, thus allowing the two z instances to acquire the instance level lock together when calling send(), which leads to deadlock, since calling receive() requires lock on the an already locked object.

This can be solved by using a static/class level lock. By synchronizing on a static lock you will synchronize the entire class methods and attributes (as opposed to instance methods and attributes). In other word, all instances of Z class will share that locked-on object, thus no two instances will be able to lock on that object simultaneously.

Once you make the lock object static, the program will be able to function as follows:

1. when z1 starts the runnable task, it will acquire the class level lock and send();
2. z2 attempts to send(), but z1 already holds the lock, so it waits for z1 to release the lock;
3. Since z1 holds the lock on Z class, it is able to receive().
4. Only when z1 finishes all its work, can z2 starts to acquire the lock on Z class and proceed with sending and receiving.

PS: Should you need more explanations, please check the following link for more details on the differences: Difference between static and non-static lock