Deadlock between Cooperating objects

Question

While going through the Java Concurrency in Practice I came across the below code Deadlock, which demonstrated how a deadlock can occur between cooperating objects. If one thread calls getImage() and at the same time another calls setLocation() it can lead to deadlock due to lock ordering. To solve this we use Open calls No Deadlock below . My doubt is inside setLocation()in No Deadlock why are we doing synchronized(this) again inside the already synchronized method ? Isn't the synchronized method already synchronized on this? How are we preventing the deadlock using the 2nd example?

DeadLock

class Taxi {
        @GuardedBy("this")
        private Point location, destination;
        private final Dispatcher dispatcher;

        public Taxi(Dispatcher dispatcher) {
            this.dispatcher = dispatcher;
        }

        public synchronized Point getLocation() {
            return location;
        }

        public synchronized void setLocation(Point location) {
            this.location = location;
            if (location.equals(destination))
                dispatcher.notifyAvailable(this);
        }
    }

    class Dispatcher {
        @GuardedBy("this")
        private final Set<Taxi> taxis;
        @GuardedBy("this")
        private final Set<Taxi> availableTaxis;

        public Dispatcher() {
            taxis = new HashSet<Taxi>();
            availableTaxis = new HashSet<Taxi>();
        }

        public synchronized void notifyAvailable(Taxi taxi) {
            availableTaxis.add(taxi);
        }

        public synchronized Image getImage() {
            Image image = new Image();
            for (Taxi t : taxis)
                image.drawMarker(t.getLocation());
            return image;
        }
    }

No Deadlock

class Taxi {
        @GuardedBy("this")
        private Point location, destination;
        private final Dispatcher dispatcher;

        public synchronized Point getLocation() {
            return location;
        }

        public synchronized void setLocation(Point location) {
            boolean reachedDestination;
            synchronized (this) {
                this.location = location;
                reachedDestination = location.equals(destination);
            }
            if (reachedDestination)
                dispatcher.notifyAvailable(this);
        }
    }

    class Dispatcher {
        @GuardedBy("this")
        private final Set<Taxi> taxis;
        @GuardedBy("this")
        private final Set<Taxi> availableTaxis;

        public synchronized void notifyAvailable(Taxi taxi) {
            availableTaxis.add(taxi);
        }

        public Image getImage() {
            Set<Taxi> copy;
            synchronized (this) {
                copy = new HashSet<Taxi>(taxis);
            }
            Image image = new Image();
            for (Taxi t : copy)
                image.drawMarker(t.getLocation());
            return image;
        }
    }

Answer 1

The Taxi.setLocation method in the "No Deadlock" code listing shouldn't be synchronized.

The online errata page reads:

p.214 In Listing 10.6, Taxi.setLocation should not be a synchronized method. (The synchronized block in its body is correct, however.) (Fixed in 6th printing.)

In the deadlock-prone code, when a thread calls Taxi.setLocation, it first acquires the Taxi lock. And while holding the Taxi lock, it proceeds to get the Dispatcher lock.

Taxi.setLocation

┌----lock Taxi
|  ┌-lock Dispatcher
│  |
|  └-unlock Dispatcher
└----unlock Taxi

This pattern is similar to the LeftRightDeadlock example with nested lock acquisition.

// Warning: deadlock-prone!
public void leftRight() {
  synchronized (left) {
    synchronized (right) {
      doSomething()
    }
  }
}

In the revised version, note the Taxi lock is released before acquiring the Dispatcher lock.

Taxi.setLocation

┌----lock Taxi
└----unlock Taxi

┌----lock Dispatcher
└----unlock Dispatcher

Answer 2

There is no deadlock in second because getImage not synchronized, so when calling getLocation no lock is held. You're right about the synchronized(this) inside setLocation, it serves no purpose.