Java Deadlock

Leave a comment

April 6, 2014 by huionn

http://docs.oracle.com/javase/tutorial/essential/concurrency/deadlock.html

Alphonse and Gaston are friends, and great believers in courtesy. A strict rule of courtesy is that when you bow to a friend, you must remain bowed until your friend has a chance to return the bow. Unfortunately, this rule does not account for the possibility that two friends might bow to each other at the same time. This example application, Deadlock, models this possibility:

public class Deadlock {
    static class Friend {
        private final String name;
        public Friend(String name) {
            this.name = name;
        }
        public String getName() {
            return this.name;
        }
        public synchronized void bow(Friend bower) {
            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());
        }
    }

    public static void main(String[] args) {
        final Friend alphonse =
            new Friend("Alphonse");
        final Friend gaston =
            new Friend("Gaston");
        new Thread(new Runnable() {
            public void run() { alphonse.bow(gaston); }
        }).start();
        new Thread(new Runnable() {
            public void run() { gaston.bow(alphonse); }
        }).start();
    }
}

I used the code above as an interview question and ask the candidate to provide the solution(s) to the deadlock problem.

The simplest solution is to remove synchronized keyword. However the flow of bow –> bowBack may be broken. In other words, it is possible that both alphonse and gaston initiate the bow, and then both bow back.

A better alternative is to use lock ordering to prevent deadlock while still maintains the flow of bow –> bowBack. In this case, this will happen:

Alphonse: Gaston  has bowed to me!
Gaston: Alphonse has bowed back to me!
Gaston: Alphonse  has bowed to me!
Alphonse: Gaston has bowed back to me!

public class OrderedLock {
  static class Friend {
    private final String name;

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

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

    public void bow(Friend bower) {
      if (System.identityHashCode(this) > System.identityHashCode(bower)) {
        synchronized (this) {
          synchronized (bower) {
            performBow(bower);

          }
        }
      } else {
        synchronized (bower) {
          synchronized (this) {
            performBow(bower);
          }
        }
      }
    }

    private void performBow(Friend bower) {
      System.out.format("%s: %s" + "  has bowed to me!%n", this.name, bower.getName());
      bower.bowBack(this);
    }

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

  public static void main(String[] args) {
    final Friend alphonse = new Friend("Alphonse");
    final Friend gaston = new Friend("Gaston");
    new Thread(new Runnable() {
      public void run() {
        alphonse.bow(gaston);
      }
    }).start();
    new Thread(new Runnable() {
      public void run() {
        gaston.bow(alphonse);
      }
    }).start();
  }
}

The solutions provided in Java tutorial is to use explicit lock (http://docs.oracle.com/javase/tutorial/essential/concurrency/newlocks.html).

public class Safelock {
    static class Friend {
        private final String name;
        private final Lock lock = new ReentrantLock();

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

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

        public boolean impendingBow(Friend bower) {
            Boolean myLock = false;
            Boolean yourLock = false;
            try {
                myLock = lock.tryLock();
                yourLock = bower.lock.tryLock();
            } finally {
                if (! (myLock && yourLock)) {
                    if (myLock) {
                        lock.unlock();
                    }
                    if (yourLock) {
                        bower.lock.unlock();
                    }
                }
            }
            return myLock && yourLock;
        }
            
        public void bow(Friend bower) {
            if (impendingBow(bower)) {
                try {
                    System.out.format("%s: %s has"
                        + " bowed to me!%n", 
                        this.name, bower.getName());
                    bower.bowBack(this);
                } finally {
                    lock.unlock();
                    bower.lock.unlock();
                }
            } else {
                System.out.format("%s: %s started"
                    + " to bow to me, but saw that"
                    + " I was already bowing to"
                    + " him.%n",
                    this.name, bower.getName());
            }
        }

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

    static class BowLoop implements Runnable {
        private Friend bower;
        private Friend bowee;

        public BowLoop(Friend bower, Friend bowee) {
            this.bower = bower;
            this.bowee = bowee;
        }
    
        public void run() {
            Random random = new Random();
            for (;;) {
                try {
                    Thread.sleep(random.nextInt(10));
                } catch (InterruptedException e) {}
                bowee.bow(bower);
            }
        }
    }
            

    public static void main(String[] args) {
        final Friend alphonse =
            new Friend("Alphonse");
        final Friend gaston =
            new Friend("Gaston");
        new Thread(new BowLoop(alphonse, gaston)).start();
        new Thread(new BowLoop(gaston, alphonse)).start();
    }
}

Reading the code, I wonder whether it is possible (at least in theory) that both alphonse and gaston try to bow to each other and both give up at the same time.

My alternative answer is to use ordered locking with explicit lock.

public class OrderedSafelock {
  static class Friend {
    private final String name;
    private final Lock lock = new ReentrantLock();

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

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

    public void bow(Friend bower) {
      Lock l1;
      Lock l2;
      if (System.identityHashCode(this) > System.identityHashCode(bower)) {
        l1 = lock;
        l2 = bower.lock;
      } else {
        l2 = lock;
        l1 = bower.lock;
      }

      if (l1.tryLock()) {
        try {
          if (l2.tryLock()) {
            try {
              System.out.format("%s: %s" + "  has bowed to me!%n", this.name,
                  bower.getName());
              bower.bowBack(this);
            } finally {
              l2.unlock();
            }
          }
        } finally {
          l1.unlock();
        }
      } else {
        System.out.format("%s: %s started" + " to bow to me, but saw that"
            + " I was already bowing to" + " him.%n", this.name, bower.getName());
      }

    }

    public void bowBack(Friend bower) {
      System.out.format("%s: %s" + " has bowed back to me!%n", this.name, bower.getName());
    }
  }
  
  static class BowLoop implements Runnable {
        private Friend bower;
        private Friend bowee;

        public BowLoop(Friend bower, Friend bowee) {
            this.bower = bower;
            this.bowee = bowee;
        }
    
        public void run() {
            Random random = new Random();
            for (;;) {
                try {
                    Thread.sleep(random.nextInt(10));
                } catch (InterruptedException e) {}
                bowee.bow(bower);
            }
        }
    }


  public static void main(String[] args) {
    final Friend alphonse = new Friend("Alphonse");
    final Friend gaston = new Friend("Gaston");
    new Thread(new BowLoop(alphonse, gaston)).start();
    new Thread(new BowLoop(gaston, alphonse)).start();
  }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: