Saturday, March 21, 2015

Deadlock

Chip and Dale must save Zipper and beat Fat Cat then but they cannot decide who is responsible for saving Zipper and who is responsible for beating their enemy.


public class Deadlock {
  
 public void init() {
  
  RescueRangers chip = new RescueRangers();
  RescueRangers dale = new RescueRangers();
  chip.setMate(dale);
  dale.setMate(chip);
  
  Thread t1 = new Thread(chip, "Chip");
  Thread t2 = new Thread(dale, "Dale");
  t1.start();  
  t2.start();
 }  
 
 class RescueRangers implements Runnable {
  
  private RescueRangers mate;
  
  public void setMate(RescueRangers mate) {
   this.mate = mate;
  }
  
  public synchronized void saveZipper() {
   System.out.println("Saving Zipper " + Thread.currentThread().getName());
   mate.attackFatCat();   
  }
  
  public synchronized void attackFatCat() {
   System.out.println("Attack Fat Cat " + Thread.currentThread().getName());   
  }
  
  public void run() {
   saveZipper();
  }
 } 
}


Once you launch this code you will see that Chip and Dale cannot attack Fat Cat because they are stuck saving Zipper – it is Fat Cat’s trap.

Output:
Saving Zipper Chip
Saving Zipper Dale

Chip and Dale wait for each other saving Zipper, neither can proceed attacking Fat Cat until the other does first, so both are stuck.


Technical explanation of the deadlock sample: Chip captures the monitor so the Dale does into saveZipper() method (object Chip and object Dale has its monitors captured). As long as Chip’s thread started its job first Chip’s thread calls for Dale (mate) to execute method attackFatCat which requires capturing the monitor because of its synchronized context. However, Dale already captured the monitor on method saveZipper and cannot capture the new monitor until it’s not released.
Starting both threads with a little pause may solve the deadlock problem


Thread t1 = new Thread(chip, "Chip");
Thread t2 = new Thread(dale, "Dale");
t1.start();
Thread.sleep(1);  
t2.start();

Output
Saving Zipper Chip
Attack Fat Cat Chip
Saving Zipper Dale
Attack Fat Cat Dale


Dale didn’t get enough time to capture the lock on savingZipper() and Chip saved zipper first and made Dale to attack Fat Cat. 

Getting attackFatCat method out of synchronized context also helps to resolve the deadlock in our sample.  In that case Dale doesn’t have to capture the new lock if the lock is already captured on saveZipper(). Just remove ‘synchronized’ from attackFatCat() method signature.



public void attackFatCat() {
    System.out.println("Attack Fat Cat " + Thread.currentThread().getName());   
} 

Output;
Saving Zipper Chip
Saving Zipper Dale
Attack Fat Cat Chip
Attack Fat Cat Dale

Since Java 1.5 we got improved locking mechanism: java.util.concurrent.locks.ReentrantLock 
ReentrantLock class provides improved lock mechanism. With that lock we can check whether the block of code has been already locked by some thread, get the number of locks in a wait set, acquire the lock if it’s not held by other thread with the given waiting time and many more.
Take a look on ReentrantLock usage in our sample:



public class DeadLockReentrant {

 public void init() {

  RescueRangers chip = new RescueRangers();
  RescueRangers dale = new RescueRangers();
  chip.setMate(dale);
  dale.setMate(chip);

  Thread t1 = new Thread(chip, "Chip");
  Thread t2 = new Thread(dale, "Dale");
  t1.start();
  t2.start();
 }

 class RescueRangers implements Runnable {

  private ReentrantLock rlock = new ReentrantLock();

  private RescueRangers mate;

  public void setMate(RescueRangers mate) {
   this.mate = mate;
  }

  public void saveZipper() {
   rlock.lock();
   System.out.println("Saving Zipper "
     + Thread.currentThread().getName());
   mate.attackFatCat(this);
   rlock.unlock();

  }

  public void attackFatCat(RescueRangers rr) {
   try {
    if (rlock.tryLock(1000, TimeUnit.MILLISECONDS)) {

     System.out.println("Attack Fat Cat "
       + Thread.currentThread().getName());
     rlock.unlock();
    }
   } catch (InterruptedException e) {
    // TODO Auto-generated catch block
    e.printStackTrace();
   }
  }

  public void run() {
   saveZipper();

  }
 }
}

Output;
Saving Zipper Chip
Saving Zipper Dale

Our code produces the same output as for deadlock sample; however the application is not stuck because of ReentrantLock usage. There is a timeout defined for entering the section of code which has already been locked by other thread. When the time expired and lock has not been released thread ignores the lock-protected section and continues its instructions execution after ReentrantLock section.

You might think that ReentrantLock is a panacea in the world of java concurrency and code marked with synchronized is useless, but actually it is not true. Synchronized blocks are well optimized for cases when only a single thread accesses your block of code, unlike ReentrantLock which always uses the locking algorithm which is very good for a sufficient thread contention (many threads want to capture the single monitor) but shows worse performance for a single thread.

Benchmark ‘synchronized vs ReentrantLock’ http://4.bp.blogspot.com/-VVlWLZtFbLs/TtKXAF_k5cI/AAAAAAAAAyk/xaqPkbHlzyg/s640/concurrency_performance.png

Recommendations about using ReentrantLock vs Synchronized from oracle.com:
https://blogs.oracle.com/dave/entry/java_util_concurrent_reentrantlock_vs
Informative article about ReentrantLock vs Synchronized from javaspecialist [RUS] http://www.javaspecialist.ru/2011/11/synchronized-vs-reentrantlock.html


No comments:

Post a Comment