Java deadlock question

Solution 1:

Consider the following:

• Let Thread1 run() { alphonse.bow(gaston); }
• Let Thread2 run() { gaston.bow(alphonse); }
• Thread1 enters alphonse.bow(gaston);, locking alphonse since bow() is synchronized
• Thread2 enters gaston.bow(alphonse);, locking gaston since bow() is synchronized
• In Thread1, bower.bowBack(this); evaluates to gaston.bowBack(alphonse);
  • Thread1 attempts to obtain the lock for gaston, currently held by Thread2
• In Thread2, bower.bowBack(this); evaluates to alphonse.bowBack(gaston);
  • Thread2 attempts to obtain the lock for alphonse, currently held by Thread1
• each thread is waiting for the other to release a lock, hence deadlock

The problem is that there is excessive synchronized currently. There are many ways to "fix" this; here's an instructive solution:

    public void bow(Friend bower) {
        synchronized (this) {
            System.out.format("%s: %s has bowed to me!%n", 
                    this.name, bower.getName());
        }
        bower.bowBack(this);
    }
    public synchronized void bowBack(Friend bower) {
        System.out.format("%s: %s has bowed back to me!%n",
                this.name, bower.getName());
    }

Now bowBack() is fully synchronized, but bow() is only synchronized partially, using the synchronized(this) statement. This will prevent the deadlock.

Here are quotes from Effective Java 2nd Edition, Item 67: Avoid excessive synchronization

To avoid liveness and safety failures, never cede control to the client within a synchronized method or block. In other words, inside a synchronized region, do not invoke a method designed to be overridden, or provided by a client in the form of a function object. From the perspective of the class with the synchronized region, such methods are alien. The class has no knowledge of what the method does and have no control over it. Depending on what an alien method does, calling it from a synchronized region can cause exceptions, deadlocks, or data corruption.

[...] As a rule, you should do as little work as possible inside synchronized regions. Obtain the lock, examine the shared data, transform it if necessary, and drop the lock.

In essence, bower.bowBack(this) is an attempt to cede control to an alien method, because bowBack() is not a final method in class Friend. Consider the following attempt to fix the problem, for example:

    // attempt to fix: STILL BROKEN!!!

    public synchronized void bow(Friend bower) {
        System.out.format("%s: %s has bowed to me!%n", 
            this.name, bower.getName());
        bower.bowBack(this);
        // ceding control to alien method within synchronized block!
    }
    
    // not a final method, subclasses may @Override
    public void bowBack(Friend bower) {
        System.out.format("%s: %s has bowed back to me!%n",
                this.name, bower.getName());
    }

The above code will not deadlock with the current alphonse/gaston scenario, but since bow() cedes control to a non-final method bowBack(), a subclass can @Override the method in such a way that will cause bow() to deadlock. That is, bowBack() is an alien method to bow(), and thus should NOT have been invoked from within a synchronized region.

References

• JLS 8.4.3.6 synchronized Methods
• JLS 14.19 The synchronized Statement
• JLS 17.1 Locks

See also

• Effective Java 2nd Edition
  • Item 66: Synchronize access to shared mutable data
  • Item 15: Minimize mutability

Solution 2:

Here's how it probably will be executed.

1. Enter alphonse.bow(gaston);, alphonse is now locked due to synchronized keyword
2. Enter gaston.bow(alphonse);, gaston is now locked
3. Can't execute bower.bowBack(this); from first bow method call because gaston (bower) is locked. Wait for lock to be released.
4. Can't execute bower.bowBack(this); from second bow method call because alphonse (bower) is locked. Wait for lock to be released.

Both threads wait for each other to release lock.

Solution 3:

Best way to understand is put below code in bow() before calling bower.bowBack

try {
Thread.sleep(1);
} catch (InterruptedException e) {
e.printStackTrace();
}