Solving The Producer Consumer Problem in Java

Producer and Consumer solves one of the standard multithreaded ( or concurrency) problem via inter process communication mechanism. Let's try to understand the problem first -

Problem

There are two mutually exclusive processes ( or rather say threads ); one produces something (i.e Producer) and the other one consumes the same (i.e. Consumer). And to handle these two activities it uses a fixed sized buffer or queue. And both work independently. So, obviously there is a problem due to fixed size of the buffer; Producer can't keep adding for forever and similarly consumer can't keep taking endlessly. So how will you ensure that producer doesn't add data in queue if it's full; and consumer doesn't remove data if it's empty.
Also, there could be multiple producers and consumers.

Here is Wikipedia link on same.This is also known as Bounded-Buffer problem.

Solution

If the buffer is full producer can't add more items and if buffer is empty consumer can't take items from it. So to synchronize these two processes; block the producer when buffer is full and similarly block the consumer when the buffer is empty.

This can be solved using Semaphore and Monitor technique. Java also provides a Queue API which supports these features; BlockingQueue.

I am not covering more details on the methods provided by BlockingQueue. You can find that out from the Java doc page. So better take an example BlockingQueue to understand it in detail.

package queue;

import java.util.concurrent.ArrayBlockingQueue;
import java.util.concurrent.BlockingQueue;
import java.util.concurrent.TimeUnit;

/**
 * Blocking queue with 2 publishers and 1 subscriber
 * @author Sid
 *
 */
public class BlockingQueueDemo {
 private BlockingQueue<String> queue;
 private volatile static int count = 0;

 public BlockingQueueDemo(int size) {
  queue = new ArrayBlockingQueue<>(size);
 }

 public Runnable publisher1() {
  return new Runnable() {
   public void run() {
    while (!Thread.interrupted()) {
     try {
      // blocks if queue is full
      queue.put("p1:" + count++);
     } catch (InterruptedException e) {
      e.printStackTrace();
     }
    }
   }
  };
 }

 public Runnable publisher2() {
  return new Runnable() {
   public void run() {
    while (!Thread.interrupted()) {
     try {
      // blocks if queue is full
      queue.put("p2:" + count++);
      TimeUnit.MILLISECONDS.sleep(5);
     } catch (InterruptedException e) {
      e.printStackTrace();
     }
    }
   }
  };
 }

 public Runnable subscriber1() {
  return new Runnable() {
   public void run() {
    while (!Thread.interrupted()) {
     try {
      // blocks until queue is empty
      System.out.println("Element: "+queue.take() + " ;Size: "+ queue.size());
     } catch (InterruptedException e) {
      e.printStackTrace();
     }
    }
   }
  };

 }

 public static void main(String[] args) {
  BlockingQueueDemo bqd = new BlockingQueueDemo(100);

  // though subscriber starts first; but waits until some element has been
  // put in the queue
  Thread sub = new Thread(bqd.subscriber1());
  sub.start();

  // start publisher
  Runnable p1 = bqd.publisher1();
  Runnable p2 = bqd.publisher2();
  Thread tp1 = new Thread(p1);
  Thread tp2 = new Thread(p2);
  tp1.start();
  tp2.start();

  try {
   TimeUnit.SECONDS.sleep(1);
  } catch (InterruptedException e) {
   e.printStackTrace();
  }
  tp1.interrupt();
  tp2.interrupt();
  sub.interrupt();
  System.out.println(" elements in queue :" + bqd.queue.size());
 }

}

In wait/notify post, I have provided a simplistic implementation of blocking queue.

---
keep coding !

Chain of Responsibility Design Pattern

Raise ticket for IT/HR related issues rather than talking directly to a specific person. Follow process !

Chain of Responsibility (i.e. COR) is a behavioral design pattern which allows an object to send request without knowing who is going to handle the request. The request is sent to a list of receivers or handlers in a chain, where each object can either handle or pass it on to the next. So, it loosely couples sender and receiver (similar to command pattern).

Intent (as put in Gang of four book)

Avoid coupling the sender of a request to its receivers by giving more than one object a chance to handle the request. Chain the receiving objects and pass the request along the chain until an object handles it.

Pattern abstracts the pool of receivers(analogous to pool of threads), so all receivers need to agree to an (communication) interface i.e. Handler.  All subclass of Handler need to agree to the interface of Handler. If a concrete handler can't process a request, then it passes it down to next handler or successor in the chain.

Handler is an abstract class in example shown below. We could implement Handler as interface as well by making getSuccessor() method also abstract. In this case, implementation will have to be provided by concrete handlers.

Generated with ObjectAid UML - Eclipse plugin

package cor.pattern;

/**
 * Base handler class
 *
 */
public abstract class Handler {
 protected Handler successor;
 
 public Handler getSuccessor() {
  return successor;
 }

 public abstract void handleRequest(Request request);
}

package cor.pattern;

/**
 * first handler
 *
 */
public class ConcreteHandler1 extends Handler {

 @Override
 public void handleRequest(Request request) {
  System.out.println("inside handler 1");
  if(request.getState().startsWith("one")){
   
   //handle request
   
  }else{
   super.successor.handleRequest(request);
  }
 }

}

package cor.pattern;
/**
 * 2nd handler
 *
 */
public class ConcreteHandler2 extends Handler {

 @Override
 public void handleRequest(Request request) {
  System.out.println("inside handler 2");

  if (request.getState().startsWith("two")) {

   // handle request

  } else {
   super.successor.handleRequest(request);
  }
 }
}

package cor.pattern;

/**
 * Request object
 *
 */
public class Request {
 private String state;

 public Request(String state) {
  this.state = state;
 }

 public String getState() {
  return state;
 }
}

public static void main(String[] args){
  Request r = new Request("two, requestParam");
  
  Handler h1 = new ConcreteHandler1();
  Handler h2 = new ConcreteHandler2();
  
  h1.successor = h2;
  h1.handleRequest(r);
 }

*Ignore poor abstraction/encapsulation in above classes.


COR Limitations

• Only one object in the chain handles the request
• There is no default handler; some of the request might go unhandled 

 

Practical Implementation

Practically it will be more beneficial to relax one condition from COR intent - ".. Chain the receiving objects and pass the request along the chain until an object handles it".

So above limitation can be relaxed to allow more than one object to handle a request. So each handler can handle a request, pass it to the successor or can do both. Servlet filters are COR implementations which allow more than one filters to intercept and process the HTTP request. Servlet filters are very handy in providing security, logging, or performing some common operations on each request. So http request can get handled by more than one filter (or handler).

Benefits of COR

• Sender and receivers are loosely coupled
• The chain of handlers can be modified dynamically, independent of sender and request.
• Sender is oblivious of number of receivers/handlers

References

• http://c2.com/cgi/wiki?ChainOfResponsibilityPattern 
• http://www.oracle.com/technetwork/java/filters-137243.html
• http://alvinalexander.com/java/java-chain-of-responsibility-design-pattern-in-java-examples

----------
do post your feedback !!!

Command Design Pattern

One of my friends requested me to write a post on Command design pattern. I replied, your wish is my Command!

Command design pattern is a behavioral pattern and is also known as an action or transaction pattern.   It decouples the object that invokes the operation from the one having the knowledge to perform it. The invoker/requester and the receiver/doer are loosely coupled. Invoker object only knows how to issue/invoke the request (It doesn't know how the request will be carried out). Receiver (at the receiving end ;-) ) knows how to carry out a task/operation. Command objects connect these two pieces(invoker and receiver); let's refer this tri-chemistry as iCr.

                    Invoker --> {Command} --> Receiver

Intent (as put in Gang of four)

Encapsulates a request as an object, thereby letting you parameterize clients with different requests, queue or log requests, and support undoable operations.

Command DP encapsulate a request as an object and pass it to an invoker, wherein the invoker does not knows how to service the request but uses the encapsulated command to perform an action. It takes an operation and its arguments and wraps them up in an object to be executed, logged, etc.

Invoker issues a request by calling execute method on the command. Then, concrete command invokes operation on its receiver to carry out a request. Below diagram shows sequence of events.

Ref : Gang of four design pattern

Implementation

Let's cover briefly the actors or components involved in this pattern.

• Command: Defines an interface for executing an operation
• Concrete Command: Binds a specific command to receiver
• Invoker: Invokes or initiates command (stores concrete command object)
• Receiver: Actual object which performs operation 
• Client: Creates concrete command and sets corresponding receiver 

Clearly understanding role of all above is incredibly important. Instead of taking specific example and then illustrating this pattern, let's stick with above names itself. If the relationship among them is clear; visualizing a real example won't be difficult.

package command.pattern;

/**
 * Command or action class; usually just has single method 
 */
public interface Command {
 public void execute();
}

package command.pattern;

/**
 * Specific command implementation. There will be one class for each command 

 * like LightOnCommand, LightOffCommand, UndoCommand etc. 
 * 

 * Encapsulates the receiver.
 */
public class ConcreteCommand implements Command {
 private Receiver rec;

 public ConcreteCommand(Receiver rec) {
  this.rec = rec;
 }

 @Override
 public void execute() {
  rec.performTask();
 }

}

package command.pattern;

/**
 * Class responsible of doing the real work : turn on a light, cook food or
 * anything for you
 */
public class Receiver {
 public void performTask() {
  System.out.println("inside receiver");
  // do the assigned work
 }

}

package command.pattern;

/**
 * Takes instance of command and calls execute method to perform the work
 * Invoker doesn't know how the work will be done
 */
public class Invoker {
 private Command command;

 public void setCommand(Command com) {
  this.command = com;
 }

 public void performRequest() {
  command.execute();
 }

}

package command.pattern;

/**
 * Client class which connects the dots
 */
public class Client {
 public static void main(String[] args) {
  Command command = new ConcreteCommand(new Receiver());

  Invoker invoker = new Invoker();
  invoker.setCommand(command);
  invoker.performRequest();
 }
}

MVC framework, Struts uses command pattern to service HTTP requests. Struts provides a Servlet known as Action Servlet, which handles HTTP request and then invokes an application specific action. As a developer we don't need to bother about how things work under the hood. We just need to know how to map an HTTP request to a Struts action and how to implement that action. Similarly, Swing framework also uses this pattern to handle UI events on buttons and menu items. 

Undo/Redo support

As the intent of the pattern clearly explains, this pattern can be used for undo or redo operations as well. To support it, the Command will have to maintain the state . For undo, application will have to store the command that was executed last. This way application can store any amount of past actions and call those command in reverse direction to achieve multiple undo commands. Similarly, keep calling in forward direction to achieve redo. If list of all past actions/commands are stored, then it can be used for logging as well when the system crash.

                       --------------------------> redo

        { command1, command2, command3, .... ....commandn}
                     <------------------------------- undo
         

Below class shows a command which supports undo operation. The Command interface has to provide abstract undo() method along with execute().

                                                     

package command.pattern;

/**
 * Command to turn on light
 */
public class LightOnCommand implements Command {
 Light light;

 public LightOnCommand(Light light) {
  this.light = light;
 }

 @Override
 public void execute() {
  light.on();
 }

 @Override
 public void undo() {
  light.off();
 }
}

----
pattern..pattern...pattern !!!

Check if a number is palindrome

A Palindrome number is a number which remains the same when its digits are reversed.

         if (number == reverse(number)){
            //number is palindrome
        } 

121, 1, 22 etc are palindrome numbers. In this post, I have discussed how to reverse a number. But, there could be an issue with the approach. Let's take below case:

In Java highest integer is, i.e. Integer.MAX_VALUE = 2147483647
Now, what if you try to reverse above number?

Reversed (i.e. 7463847412 ) number can't fit in an integer and hence it will overflow. One alternative is; store the value in a long and then reverse it. This approach will work but it's not a very cleaner and cooler way.
Let's figure out a different approach?

Algorithm

We can apply the more fundamental approach of comparing the first and last digits and if they are equal move to second and second last digits and so on. Keep doing it until the comparison fails or the number reduces to a single digit. This approach is followed to check if a string is palindrome. This approach doesn't have space overhead ( except two temporary variables to get left most and the right most digit). 

         number = 121   

         leftMostDigit = 1

         rightMostDigit = 1

         leftMostDigit == rightMostDigit

         so number = 2 

Implementation

Recursive implementation in Java. Each recursive call trims the right most and left most digit of the number.

          So 12321 will become 232 in the second call.

     /**  
       * Recursive method to check if a number is palindrome  
       *   
       * @param number  
       * @return true/false  
       */  
      public static boolean isPalindrome(int number){  
           System.out.println(" number is :"+ number);  
           if(number < 0){  
                isPalindrome(-number);  
           }  
           if(number < 10){  
                return true; //single letter number is always palindrome  
           }  
           int rightMostDigit = number % 10;  
           int leftMostDigit = number;  
           int factor = 1;  
           while(leftMostDigit >= 10 ){  
                leftMostDigit = leftMostDigit / 10;  
                factor = factor * 10;  
           }  
           if(leftMostDigit != rightMostDigit){  
                return false;                 
           }  
           number = number % factor; //remove left most number  
           number = number / 10; // remove right most number  
           return isPalindrome(number);  
      }  

--

keep coding !!!