Please help me understand this deadlock example

Question

For my programming languages class we have been given a simple Java deadlock example and are asked to solve it. I don't directly want the answer to this problem, I mainly want to know where my understanding is lacking. Here's the code:

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 () {
      //System.out.println(m1.getName() + " about to ping " + m2.getName());
      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();
   }
}

When I execute the above code I believe the following should happen every time (though it doesn't, because sometimes we deadlock):

Girl pings Boy, putting a lock on the ping() method. Girl, inside ping(), tries to call boy.confirm(). Boy's confirm() answers, thus bringing us back to Girl.ping() where it finishes up, takes the lock off of ping(), and Boy's instance does the exact same thing. With all the locks, it seems that the entire program is serialized though thus defeating the purpose of multithreading? Regardless, I normally get the following output

Starting...1
Girl (ping): pinging Boy
Boy (confirm): confirm to Girl
Girl (ping): got confirmation
Boy (ping): pinging Girl
Girl (confirm): confirm to Boy
Boy (ping): got confirmation

However sometimes we get a deadlock and the output becomes:

Girl (ping): pinging Boy
Boy (ping): pinging Girl

I don't understand how we can get in this state though, since it seems we're locking the ping() method when we first go inside, so how could Boy even call ping() if girl is already using it? Is girl trying to call boy.confirm() when Boy is busy calling ping()?

Answer 1

• Thread 1 : start
• Thread 1 : call ping on a, get the monitor on a, execute System.out.println to print Girl (ping): pinging Boy
• Thread 1 : preempted by the VM
• Thread 2 : start
• Thread 2 : call ping on b, get the monitor on b, execute System.out.println to print Boy (ping): pinging Girl
• Thread 2 : call a.confirm, wait on the monitor on a.
• Thread 1 : resume
• Thread 1 : call b.confirm, wait on the monitor on b
• Thread 1 and 2 are now waiting on resources the other thread is holding. deadlock

The thing here is that public synchronized void ping (Monitor p) means a monitor on the instance of the class. two different instances will be totally unrelated when it come to critical sections.

Deadlock often occur when synchronisation mechanisms are acquired in different orders by different threads. To solve this issue (within the context of the exercise) there are two possibilities :

1. Synchronize on the class instance, which is radical

   public void ping (Monitor p) {
     synchronized(Monitor.class) {
   
     }
   }
   

2. Be explicit about the synchronisation order, which is verbose and\or error prone. For instance

    class Runner extends Thread {
       Monitor m1, m2;
       bool m1_first;
       public Runner (Monitor m1, Monitor m2, bool sync_m1_first) { 
          this.m1 = m1;
          this.m1 = m2;
          m1_first = sync_m1_first;
       }
   
       public void run () {
   
          if(m1_first)
          {
              synchronized(m1) {
                  synchronized(m2) {
                      m1.ping(m2);
                  }
              }
          }
          else
          {
              synchronized(m2) {
                  synchronized(m1) {
                      m1.ping(m2);
                  }
              }
          }
       }
    }
    ...
    (new Runner(a, b, true)).start();
    (new Runner(b, a, false)).start();
   

Answer 2

Your ping method is synchronized and takes the lock on this, then it proceeds to call confirm on p, thus attempting to take its lock as well. In steps:

1. "Girl" thread acquires lock on Boy object, enters ping;
2. "Boy" thread acquires lock on Girl object, enters ping;
3. Girl wants to call Boy.confirm, waits for the lock;
4. Boy wants to call Girl.confirm, waits for the lock;
5. Deadlock.