Where is the deadlock in this example?

Question

I am currently reading a section on concurrency in The Well-Grounded Java Developer book and this particular code sample demonstrating block concurrency should deadlock, but as far as I can see it does not. Here's the code:

public class MicroBlogNode implements SimpleMicroBlogNode {

    private final String ident;

    public MicroBlogNode(String ident_){
        ident = ident_;
    }

    public String getIdent(){
        return ident;
    }

    public static Update getUpdate(String _name){
        return new Update(_name);
    }

    public synchronized void propagateUpdate(Update upd_, MicroBlogNode backup_){
        System.out.println(ident + ": received: " + upd_.getUpdateText() + " ; backup: " + backup_.getIdent());
        backup_.confirmUpdate(this, upd_);
    }

    public synchronized void confirmUpdate(MicroBlogNode other_, Update update_){
        System.out.println(ident + ": received confirm: " + update_.getUpdateText() + " from " + other_.getIdent() + "\n");
    }

    public static void main(String[] args) {
        final MicroBlogNode local = new MicroBlogNode("localhost");
        final MicroBlogNode other = new MicroBlogNode("remotehost");
        final Update first = getUpdate("1");
        final Update second = getUpdate("2");

        new Thread(new Runnable() {
            public void run() {
                local.propagateUpdate(first, other);
            }
        }).start();

        new Thread(new Runnable() {
            public void run() {
                other.propagateUpdate(second, local);
            }
        }).start();
    }
}

When I run it I get the following output:

localhost: received: 1 ; backup: remotehost
remotehost: received confirm: 1 from localhost

remotehost: received: 2 ; backup: localhost
localhost: received confirm: 2 from remotehost

The book says that if you run the code, you’ll normally see an example of a deadlock—both threads will report receiving the update, but neither will confirm receiving the update for which they’re the backup thread. The reason for this is that each thread requires the other to release the lock it holds before the confirmation method can progress.

As far as I can see this is not the case - each thread confirms receiving the update for which they are the backup thread.

Thanks in advance.

Answer 1

The deadlock is happening when you have your local calling a threaded operation on confirmUpdate when other is attempting to make the same call. Hence, the deadlock happens following this order of operations

1. Local locks itself by calling propagateUpdate due to the declaration that it is synchronized (see Synchronized Member Function in Java)
2. 'Other' locks itself by calling propagateUpdate
3. Local attempts to acquire the lock on Other to call confirmUpdate but can't since Other has already been locked in the other thread.
4. Other attempts to do the same thing and fails for the same reason.

If it's actually working, it's probably because it's happening so fast. Run it a few more times. Thread issue never work when you want them to work.

Answer 2

This looks like timing. Your output is showing that the localhost thread has completed before the remotehost (other) thread has started.

Try putting a Thread.sleep(1000) in the propogateUpdate method after the System.out

public synchronized void propagateUpdate(Update upd_, MicroBlogNode backup_){
    System.out.println(ident + ": received: " + upd_.getUpdateText() + " ; backup: " + backup_.getIdent());
    Thread.sleep(1000);
    backup_.confirmUpdate(this, upd_);
}

This should force a deadlock.