Sunday, May 19, 2013

Java Concurrency Part 4

This is the fourth part of the tutorial, and this link goes to the previous post java concurrency part 3

Thread Deadlock

Deadlock happen when two threads are blocked waiting for an object's lock that each thread posses. Neither can run until the other gives up its lock, so they will wait forever or blocked indefinitely.

Example
 public class Deadlock extends Thread {  
           Resource a;  
           Resource b;  
           public Deadlock(Resource a, Resource b,String name) {  
                super(name);  
                this.a = a;  
                this.b = b;  
           }  
           public void run(){  
                synchronized(a) {  
                       try {                           
                          Thread.sleep(10000);  
                     } catch (InterruptedException e) {  
                          e.printStackTrace();  
                     }  
                     synchronized(b) {  
                     }  
                     System.out.println("Thread " + this.getName() + " has ended");       
                }  
           }  
      }  
      ..........  
      Resource a = new Resource();  
      Resource b = new Resource();  
      Deadlock d1 = new Deadlock(a, b, "one");  
      Deadlock d2 = new Deadlock(b, a, "two");  
      d1.start();  
      d2.start();  
      ..........  

In the previous example no message is print to console because the threads never reached the System.out.println() sentence, both threads stay forever waiting in the second synchronized() sentence.

What happens is that the first thread “d1” acquires the “a” Resource lock and the second thread “d2” acquires the “b” resource lock, then both threads sleep for 10 seconds, the sleeping time is for giving time to each thread to run and acquire the lock, then after waking up the deadlock situation is set, each thread will try to get the resource the other thread posses, “d1” will try to acquire “b” and “d2” will try to acquire “a”.

One way to avoid the deadlock situation is to use Locks and obtain the lock using tryLock() method

Thread interaction

Threads can communicate to other threads about their status of an event. The Java API provides two ways to enable this communication.
  1. The helper methods (wait(), notify(), notifyAll()) of the Object class.
  2. The java.util.concurrent.locks.Condition interface.
Using these mechanisms a thread can put itself into a state of waiting until some other thread wakes it if there is a reason to come back from the waiting state.

A thread has to call the wait(), notify(), notifyAll() on an object from a synchronized context or an IllegalMonitorStateException will arise. The thread must synchronize the instance of the object in which is calling the helper methods.

Example:
 public class Calculator extends Thread {  
      private Operation op; 
 
      public void run() {  
            synchronize(op) {  
                  op.wait();  
            }  
      }  
}  

There is an overloaded version of wait that waits for an amount of time, so the thread waits until it is notified or the specified time elapsed.

When the wait() method is invoked on an object, the thread executing that code gives up the the object's lock, however when notify() or notifyAll() are invoked on an object the thread doesn't give up the lock, the lock is released until the synchronized code where the notify() or notifyAll() are used completes.

A common example of thread interaction is the consumer-producer, in this type program two threads interact sending messages between them through a “monitor”. The producer thread as its name says generates messages for the consumer, on the other hand the consumer thread waits for the messages
generated by the producer.

Example:
 public class MessageBox {  
      private String message;  
      private boolean empty = true;  
      public synchronized String take() {  
           //Wait until message is available.  
           while(empty){  
                try {  
                     wait();  
                } catch (InterruptedException e) {  
                     e.printStackTrace();  
                }                 
           }  
           empty=true;  
           notifyAll();  
           return message;  
      }  
      public synchronized void put(String message){  
           //Wait until message has been retrieved.  
           while(!empty) {  
                try {  
                     wait();  
                } catch (InterruptedException e) {  
                     e.printStackTrace();  
                }  
           }  
           empty = false;  
           this.message = message;  
           notifyAll();  
      }  
 }  
 public class Producer extends Thread {  
      private MessageBox mb;  
      public Producer(MessageBox mb) {  
           this.mb = mb;  
      }  
      public void run() {  
           String [] messages = {"Hello", "world", "end"};  
           for (String msg:messages) {  
                mb.put(msg);  
           }  
      }       
 }  
 public class Consumer extends Thread {  
      private MessageBox mb;  
      public Consumer(MessageBox mb) {  
           this.mb = mb;  
      }  
      public void run() {  
           String message = "";  
           while (!message.equalsIgnoreCase("end")) {  
                message = mb.take();  
                System.out.print(message + " ");  
           }  
      }  
 }  
 ..............  
 MessageBox mb = new MessageBox();   
 Consumer consumer = new Consumer(mb);  
 Producer producer = new Producer(mb);  
 consumer.start();  
 producer.start();  
 ..............  

In the pevious example the MessageBox class acts as a monitor, if you don't know what a monitor is check this http://en.wikipedia.org/wiki/Monitor_(synchronization), this class makes the consumer to wait if there is no message to read and notifies it when a message arrive. It is the same for the producer, it makes it to wait if producer wants to send a message and the last message set hasn't been read and notifies it when the message has s been read.

So, the MessageBox through its methods wait(), notify(), notifyAll() makes easier the interaction between the consumer and producer threads, it is important to notice that this methods are used with condition loops, this way is safer to use this methods and avoid deadlock situations.

The java.util.concurrent.locks.Condition interface provides similar functionality to the helper methods of the Object class.

Conditions are associated with locks, the conditions allow threads to have control of a lock and check whether a condition is true or not and, if it's false, suspends the thread until another thread wakes them up.

The java API says this about the Condition interface: Condition factors out the Object monitor methods (wait, notify and notifyAll) into distinct objects to give the effect of having multiple wait-sets per object, by combining them with the use of arbitrary Lock implementations. Where a Lock replaces the use of synchronized methods and statements, a Condition replaces the use of the Object monitor methods.

All conditions are associated to a lock and to obtain a Condition instance for a particular Lock instance use its newCondition() method.

                        Lock lock = new ReentrantLock();
                        Condition condition = lock.newCondition();

Condition interface has the await(), signal(), signalAll() and its behavior is just the same as the wait(), notify(), notifyAll() of Object class. These methods must be in a block of code that begins with a call to the lock() method of a Lock object and ends with an unlock() method on the same object, or an IllegalMonitorStateException exception will arise.

          lock.lock();//Gets the lock  
               try {  
                   condition.await();             
            } catch (InterruptedException e) {  
                 e.printStackTrace();  
            } finally {  
                 lock.unlock();//releases the lock  
           }  

In order to implement the consumer-producer example with conditions, we only have to change the MessageBox class, the one that acts as monitor, remove the synchronized keywords for a Lock with a Condition, and change the helper methods of the Object class for the ones of the condition.

 public class MessageBox {  
      private String message;  
      private boolean empty = true;  
      private Lock lock = new ReentrantLock();  
      private Condition condition = lock.newCondition();  
      public String take() {  
           //Wait until message is available.  
           lock.lock();  
           while(empty){                 
                try {  
                     condition.await();  
                } catch (InterruptedException e) {  
                     e.printStackTrace();  
                }            
           }  
           empty=true;  
           condition.signalAll();  
           lock.unlock();  
           return message;  
      }  
      public void put(String message){  
           //Wait until message has been retrieved.  
           lock.lock();  
           while(!empty) {  
                try {  
                     condition.await();  
                } catch (InterruptedException e) {  
                     e.printStackTrace();  
                }                 
           }  
           empty = false;  
           this.message = message;  
           condition.signalAll();  
           lock.unlock();  
      }  
 }  

In the example above the await() method of the Condition acts like the wait() of the Object class and signalAll() acts like the notifyAll(), and the behavior should be the same.

Go to part 5

6 comments:

  1. The code for MessageBox is not correct.
    When you print what both consumer and producer do, you can see that consumer consumes an item which is not even produced yet, so I'm guessing the synchronization along with conditions is not correct

    ReplyDelete
    Replies
    1. The consumer starts reading and if no message is available then it should wait, but if the "empty" flag of the MessageBox class is not initialized or set to false, which is the deafult value for a boolean type then it will read an empty message.

      Sometimes the little details provoke big bugs!

      Delete
  2. Even the first example with the Deadlock class has issues inside.
    I've created this class with String as a replacement class instead of the Resource placeholder and as a result both threads ended without deadlock occurring.

    ReplyDelete
    Replies
    1. Well you should know that strings behave differently since they reside in a pool, and the JVM doesn't create two instances of the same string unless you use a reference to it.

      So if you use the same string then you are using one object, go on and create an empty class and use it as resource and try it again, it should work! ;)

      And keep it in mind that the code is forcing the deadlock, that's why the sleep() sentence is in the code, and deadlocks happen randomly.

      Delete
    2. You are right about the String, good to know that.
      Thanks

      Delete