Question

Why is this java code reaching a deadlock and how to I fix it without serializing the code (i.e. I don't want to do not have the Girl authenticate the Boy then have the Boy authenticate the Girl)? import java.applet.*; import javax.swing.*; import java.awt.*; import java.awt.event.*; // Attempt at a simple handshake. Girl pings Boy, gets confirmation. // Then Boy pings girl, get confirmation. class Monitor { String name; public Monitor (String name) { this.name = name; } public String getName() { return this.name; } // Girl thread invokes ping, asks Boy to confirm. But Boy invokes ping, // and asks Girl to confirm. Neither Boy nor Girl can give time to their // confirm call because they are stuck in ping. Hence the handshake // cannot be completed. public synchronized void ping (Monitor p) { System.out.println(this.name + " (ping): pinging " + p.getName()); p.confirm(this); System.out.println(this.name + " (ping): got confirmation"); } public synchronized void confirm (Monitor p) { System.out.println(this.name+" (confirm): confirm to "+p.getName()); } } class Runner extends Thread { Monitor m1, m2; public Runner (Monitor m1, Monitor m2) { this.m1 = m1; this.m2 = m2; } public void run () { m1.ping(m2); } } public class DeadLock { public static void main (String args[]) { int i=1; System.out.println("Starting..."+(i++)); Monitor a = new Monitor("Girl"); Monitor b = new Monitor("Boy"); (new Runner(a, b)).start(); (new Runner(b, a)).start(); } }

Answer 1

Some detail before I answer your questions:

This piece of code will not alway get stuck into the deadlock. It will only happen when both Threads tries to execute ping() method at the very same instance(sounds bizarre).

Two threads have been started immediately one after another and so it is easy to assume that they will always execute ping() method simultaneously(Boy and girl Monitor both), but that wont always be the case, one thread will seldom complete execution of method ping() before the other starts as it has very small footprint. And so in that case the code will run as expected.

So why in some cases it gets stuck into deadlock?
The reason is the use of synchronized keyword in method syntax. A synchronized method gets lock on the current object('this') before starting the execution of the method. What does that mean exactly?

public synchronized void ping(Monitor p) {

...
}

is essentially,

public void ping(Monitor p) {

        synchronized (this) {
        ......

        }

}

Which means that when m1.ping(m2) is called from Thread1 the ping() method will get hold of the lock on 'this' object(which would be m1 in this case). So, consequently no other synchronized method of 'this(m1)'s can be called until ping() releases the lock on 'this'(on m1). Now, ping() is also calling a synchronized method from within itself, albeit, some other objects(m2)'s confirm() method. Same rule would apply there also. ping() method of 'this' (m1) would want to execute m2's confirm(), BUT what if some other thread(Thread2) is doing the same with m2, i.e. calling the ping() method of m2, so holding the lock on m2. Which means m1('this') will have to wait until m2's ping() releases lock on it. BUT m2's ping() wont be able to do it as m1's confirm() cant be executed from there within as m1's ping() already has a lock on m1, ergo a deadlock.

To prevent this,

Remove dependancy of 'this' as a single lock to call both the methods of single object. What does that mean? Create two different objects that holds lock on both methods respectively. This will make sure that no two thread can execute ping() simultaneously(while same applies for confirm()), but they will not hold each other's execution(ping() and confirm() of same object can be called independently from different thread). here's the implementation.

public class Monitor {
    String name;
    final Object pingLock = new Object();
    final Object confirmationLock = new Object();

    public Monitor(String name) {
        this.name = name;
    }

    public String getName() {
        return this.name;
    }

    public void ping(Monitor p) {
        synchronized (pingLock) {
            System.out.println(this.name + " (ping): pinging " + p.getName());
            p.confirm(this);
            System.out.println(this.name + " (ping): got confirmation");
        }
    }

    public void confirm(Monitor p) {
        synchronized (confirmationLock) {
            System.out.println(this.name + " (confirm): confirm to " + p.getName());
        }
    }
}