Latch API in Java : CountDownLatch

Literally, latch means a device for keeping a door or gate closed.  Its meaning is analogous to a gate in Java as well. So if latch (gate) is open, everyone can pass through it but when it's shut, no one is allowed to cross over. With this as background let's go in detail:

It's one of the advanced threading/concurrency concepts of Java. Java provides a Latch API named as  CountDownLatch which got introduced in Java 5 ( java.util.concurrent package). So now on; I will refer Latch and CountDownLatch interchangeably to refer to the same thing. Latch is a synchronizer that can delay the progress of threads until it reaches its terminal state. [A synchronizer is any object that coordinates the control flow of threads based on its state] So it is used to synchronize one or more tasks by forcing them to wait for the completion of a set of operation being performed by other tasks.

CountDownLatch in action

Let me start directly with a simple example to stress on the fundamentals of this API. Below sample program has two tasks (as taskone() and tasktwo()) represented as methods. And I want to make sure that taskone() should get completed before tasktwo(). 

import java.util.concurrent.CountDownLatch;
import java.util.concurrent.TimeUnit;

public class CountDownLatchTest {
 static CountDownLatch latch;

 CountDownLatchTest(final int count) {
  latch = new CountDownLatch(count);
 }

 public void firstTask() {
  Runnable s1 = new Runnable() {
   public void run() {
    try {
         System.out.println("waiting....");
         TimeUnit.SECONDS.sleep(5);
    } catch (InterruptedException e) {
         e.printStackTrace();
    }
    // finish first activity before last line
    latch.countDown();
   }
  };
  Thread t = new Thread(s1);
  t.start();
 }

 public void secondTask() {
  Runnable s2 = new Runnable() {
   public void run() {
    try {
         System.out.println("wait....");
         latch.await();
         // perform task here
         System.out.println("after wait.... done");
    } catch (InterruptedException e1) {
         e1.printStackTrace();
    }
   }
  };
  Thread t = new Thread(s2);
  t.start();
 }

 public static void main(String[] args) throws InterruptedException {
  CountDownLatchTest cdlt = new CountDownLatchTest(1);
  cdlt.secondTask();
  TimeUnit.SECONDS.sleep(5);
  cdlt.firstTask();
 }
}

 Output:

 wait....
waiting....
after wait.... done

Above example shows CountDownLatch attribute getting initialized to a value of 1 through constructor. Two tasks in above example are synchronized though CountDownLatch. Task2 i.e. secondTask() should wait for completion of Task1 i.e. firstTask(). Run above example and notice the sequence in which output appears on the console. 

Please note few important points

1. Any task that calls await() on the object will block until the count reaches zero or it's interrupted by another thread. secondTask() gets blocked after call to await(); evident from output.
2. Call countDown() on the object to reduce the count. The task that call countDown() are not blocked.  This cal signals the end of the task. This method need to be called at the end of the task.
3. As soon as count reaches zero; threads awaiting starts running. 
4. The value of count which is passed during creation of latch object is very important. It should be same as the number of task which needs to be finished first. If count is 5 then first task should be called five times to make sure that count has reduced to 0.
5. You can also use wait and notify mechanism of Java to achieve the same behavior but code will become quite complicated. 
6. One of the disadvantage of CountDownLatch is that its not reusable once count reaches to zero. But Java provides another concurrency API called CyclicBarrier for such cases. 

Usage of CountDownLatch

1. Use this when your current executing thread/main thread needs to wait for the completion of other dependent activities. 
2. Ensure that a service doesn't start until other services on which it depends have not completed.
3. In a multi-player game like RoadRash; wait for all players to get ready to start the race. 

---
do post your comments/questions !!!

Semaphore in Java

Let's start with below problems; before starting on Semaphore.

1. Implement a Database connection pool which will block if no more connection is available instead of failing and handover connection as soon as it's available
2. Implement a thread pool
3. Create a blocking bounded collection
4. Limiting number of http connection to an external site

Note : Bounded puts an upper limit on the size of collection. 

And block(ing) here means that, wait for the collection to become non-empty when retrieving an element, and wait for space to become available when storing an element. 

(One of the) Solution to all above problems is, Semaphore!
Recall that, in normal monitor lock (implicit lock), only one thread can access a resource. So, if you want more than one thread to access a resource at the same time, Semaphore comes into play. Semaphores are used to restrict number of threads which can access a resource or perform a given action at the same time. To achieve this, semaphore maintains a counter which keeps track of the number of resources available.

When a thread requests access to resource, semaphore checks the variable count, and if it's less than total count, then grants access and subsequently reduces the available count. If count is equal to maximum allowed count then it asks thread to wait. If resource count is one (0/1 or on/off) then its called as Binary Semaphore, otherwise its called as counting semaphore.

Semaphore got introduced into standard Java library in version 5.

Limit Number of Http Connections

Below example show how can you limit the number of http connection in your system.

import java.io.IOException;
import java.net.URL;
import java.net.URLConnection;
import java.util.concurrent.Semaphore;

/**
 * Limit Maximum number of URL connection allowed through Counting Semaphore
 * @author Sid
 *
 */
class UrlConnectionManager {
 private final Semaphore semaphore;
 private final int DEFAULT_ALLOWEED = 10;

 UrlConnectionManager(int maxConcurrentRequests) {
  semaphore = new Semaphore(maxConcurrentRequests);
 }
 
 UrlConnectionManager() {
  semaphore = new Semaphore(DEFAULT_ALLOWEED);
 }

 public URLConnection acquire(URL url) throws InterruptedException,
   IOException {
  semaphore.acquire();
  return url.openConnection();

 }

 public void release(URLConnection conn) {
  try {
   // clean up activity if required
  } finally {
   semaphore.release();
  }
 }
}

In above example; semphore maintains a set of permits or pass. Method, semaphore.acquire(), blocks if necessary until permit is available and then takes it. And each semaphore.release() adds/returns a permit. Semaphore is like a gatekeeper which keeps track of number of visitors allowed in a building.

Blocking Bounded LinkedList

You can also use semaphore to turn any collection into blocking bounded collection. Let's see how to do the same for LinkedList. Assume that, only add and remove operations are allowed. Below class provides main method to test it. Note that, at most 5 add operations are allowed.

import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.concurrent.Semaphore;
import java.util.concurrent.TimeUnit;

/**
 * Minimilistic Bounded List  
 * @author Sid
 *
 */
public class BoundedLinkedList<T> {
 private List<T> list;
 private Semaphore semaphore;

 public BoundedLinkedList(final int bound) {
  list = Collections.synchronizedList(new LinkedList<T>());
  semaphore = new Semaphore(bound);
 }

 public void add(T o) throws InterruptedException {
  semaphore.acquire();
  list.add(o);
  System.out.println(" Added element :"+ o);
 }
 
 public void remove(T o) {
  if (list.contains(o)) {
   list.remove(o);
   semaphore.release();
   System.out.println(" Removed element :"+ o);
  }
 }
 
 /**
  * Test Method
  * Adds 6 elements; then waits for 5 seconds; removes one element
  */
 public static void main(String[] args){
     final BoundedLinkedList<Integer> bll = new BoundedLinkedList<>(5);
  new Thread(new Runnable(){
   public void run(){
    for(int i = 1; i <= 6; i++)
     try {
      bll.add(i);
     } catch (InterruptedException e) {
      e.printStackTrace();
     }
   }
  }).start();
  
  try {
   TimeUnit.SECONDS.sleep(5);
  } catch (InterruptedException e) {
   e.printStackTrace();
  } 
  
  bll.remove(3);
 }

}

Output
 Added element :1
 Added element :2
 Added element :3
 Added element :4
 Added element :5
 Removed element :3
 Added element :6

Important points to remember

1. You should be very careful to make sure that you are releasing after acquire. You can miss it due to programming error or any exception. 
2. Long held lock can cause starvation 
3. Method, release doesn't have to be called by the same thread which called acquire. This is an important property that we don't have with normal mutex in Java.
4. You can increase number of permits at runtime (you should be careful though). This is because number of permits in a semaphore is not fixed, and call to release will always increase the number of permits, even if no corresponding acquire call was made. 

---
keep coding !!!

Implementing Single Linked List in Java

Before I start, let me caution you that this post is not about LinkedList [Java Doc] API of Java. LinkedList API of Java is a specialized implementation of doubly linked list. This post talks in general about linked data structures (i.e. linked list) and implementation of single linked list in Java.

Definition

Linked data structures are composed of distinct chunks of memory; and these chunks are bounded/linked through pointers. These memory chunks are referred as nodes. As nodes are not stored in contiguous memory so adding or removing individual nodes is quite easier (unlike an array). But one drawback is that random access to node is not possible. 

typedef struct node {
         item_type item;  //data stored in node
         struct list *next;  //points to successor 
}node;

In C language; *p denotes the item that is pointed to by pointer p, and &x denotes the address (i.e. pointer) of a particular variable x. A special null value is used to denote the termination of the list. 

C pointers are similar to Java references; as both of them point to something.

Let's cover them in detail

C pointers:
    int var = 20; 
    int *ip;   //pointer to an integer
    ip = &var;  //store address of var in pointer ip

Java references:
     Integer x = new Integer(20);  //x is reference to Integer

Usually, Java references are implemented as pointers in C; but specification doesn't say it explicitly. Java reference should be just an abstraction on C pointers (i.e. references in Java will be implemented using C pointers). I am not going to stress if both are same or not; it's debatable!

Implementation

Below is custom single linked list implementation in Java. I have just provided add and print method.

package algo;  
   
 /**  
  * Generic single linked list implementation with generics  
  *   
  * @author Siddheshwar   
  */  
 public class SingleLinkedList<E> {  
      Node<E> start; // points to the head or first node  
   
      /**  
       * Node class    
       */  
      private class Node<E> {  
           E data;  
           Node<E> next;  
   
           public Node(E data, Node<E> next) {  
                this.data = data;  
                this.next = next;  
           }  
   
           public E getData() {  
                return data;  
           }  
   
           public Node<E> getNext() {  
                return next;  
           }  
   
           public void setNext(Node<E> next) {  
                this.next = next;  
           }  
      }  
   
      public void add(E d) { // add at the end of list  
           if (start == null) {  
                start = new Node<E>(d, null);  
           } else {  
                Node<E> tmp = start;  
                while (tmp.next != null) {  
                     tmp = tmp.next;  
                }  
                tmp.setNext(new Node<E>(d, null));  
           }  
      }  
   
      public void print() {  
           Node<E> current = start;  
           System.out.print(" values in link-list are :");  
           while (current != null) {  
                System.out.print(current.getData() + "--> ");  
                current = current.getNext();  
           }  
           System.out.println("null");  
      }  
   
      public static void main(String[] args) {  
           SingleLinkedList<String> sll = new SingleLinkedList<>();  
           sll.add("abc");  
           sll.add("def");  
           sll.print();  
      }  
 } 

Output : 
values in link-list are :abc--> def--> null

Complexity of common operations 

1.  Insert/Update/delete at end of list: O(n) . Need to traverse whole list.  
2.  Insert at the beginning/head of the list : O(1)
3.  Find the size of list : O(n). But it can be achieved in O(1) if you keep track of the count in a separate attribute (increment its value on each addition and decrement on each deletion).

References from Java

1. LinkedList  [Java Doc] : Doubly linked list implementation of the List and Deque interfaces.
2. LinkedHashMap [Java Doc] : Hash table and linked list implementation of the Map interface, with predictable iteration order. This implementation differs from HashMap in that it maintains a doubly-linked list running through all of its entries. Linked list defines the iteration ordering, which is normally the order in which keys were inserted into the map.
3. LinkedHashSet [Java Doc] : Hash table and linked list implementation of the Set interface, with predictable iteration order.

Related Post :Implementing Doubly linked list in Java

Algorithm Analysis and Big Oh Notation

In mathematics and computer science, an algorithm is a step-by-step procedure for calculation. Algorithms are used for calculation, data processing, and automated reasoning. - Wikipedia

Algorithms are independent of programming language as well as platform on which it run. Algorithm analysis is mainly about the resources like computational time, storage,  computer hardware, bandwidth etc. But usually measuring computational time is most important.  

Computational time or run time of algorithm is computed by counting up the number of steps an algorithm takes on a given problem instance. But defining a unified model to calculate run time of an algorithm is quite complicated.

Let's take a case of multiplying two numbers vs adding two numbers. Multiplying two numbers takes more time than adding two numbers on most processors. So addition and multiplication will not take same number of steps. Let's make things more simpler by analyzing addition of two numbers on two modern languages like C and Java. Even in this case addition of two numbers will not take exactly same number of steps. So this proves exact analysis of algorithms is going to be much more complicated as it will depend on factors like processors, languages, different versions of the same language and even on how smart the algorithm developer is etc.

To make things much more easier and reliable; RAM Model of Computation plays a vital role. These assumptions make analysis of algorithm easier without missing important aspects. Some of the basic assumptions of RAM model are:

1. Mathematical and logical operations like +,-,*,=, floor, ceiling, if  etc take one time stamp.
2. Number of time a loop runs depends on the number of iterations. So Loop is not considered a simple operation and its composition of many single-step operations.
3. Memory access like load,store,copy of an item requires one unit of time  (independent of the source like disk or cache) 

So with this model, adding and multiplying two numbers is going to take same unit of time. And even adding two numbers will have same complexity on any platform and language.

 So RAM model captures essential behavior of computers. And its useful and simple to work with.

Complexity

Using RAM model, number of steps an algorithm takes can be counted by executing it. But complexity also depends on the nature/variation of input data set. Sorting an already sorted integer array will take far lesser number of steps compared with a unsorted array. So you need to provide all possible data set to find out the run time complexity. This brings in the notion of best, worst, and average-case complexity of algorithms.

1. The worst-case complexity : maximum number of steps taken in any instance of size n.
2. The best-case complexity : minimum number of steps taken in any instance of size n.
3. The average-case complexity : average number of steps taken over all instances of size n.

Average-case and best-case are very subjective and difficult to calculate. The meaning of best and average depends on so many factors. So its better to avoid all such complexities associated with best and average case; and consider only worst-case. 

( O ) Big-Oh Notation 

 f(n) = 53n^2 + 654n - logn

Performing precise worst-case analysis on above function will be a daunting task. But above equation tells that "time grows quadratically with n". So it is much easier to talk in terms of upper and lower bounds of time-complexity. Big Oh simplifies our analysis by ignoring levels of details that do not impact our comparison of algorithm. So Big Oh analysis of below two functions are same:

     f(n) = 5n;

     and g(n) = n;

So constant factors like 5 in above case are ignored when comparing two algorithms. Let's take a look at the formal definition of Big Oh notation :

1. f(n) = O(g(n))  means c.g(n) is an upper bound on f(n). Thus there exists some constants c such that f(n) is always <= c.g(n) for large n  {Big Oh Notation}
2. f(n) = Ω(g(n)) means c.g(n) is a lower bound of f(n). Thus there exists some constants c such that f(n) is always >= c.g(n)   {Omega Notation}
3. f(n) = Ɵ(g(n)) means c1.g(n) is an upper bound on f(n) and c2.g(n) is a lower bound on f(n). Thus there exists constants c1 and c2 such that f(n) <= c1.g(n) and f(n) >= c2.g(n)  {Theta Notation}

The Big Oh notation enables us to ignore details and focus on the big picture. So it doesn't care if one sorting algorithm sorts 3 times faster than the other. It's more about which algorithm sorts faster when your input size is like 10,000 items.  When we say "the running time is O(n^2)," we mean that there is a function f(n) that is O(n^2) such that for any value of n, no matter what particular input of size n is chosen, the running time on that input is bounded from above by the value of f(n). Equivalently, we mean that the worst-case running time is O(n^2). Big oh is used to describe the asymptotic behavior of an algorithm, that is rate of growth. It is also an upper bound which might not be tight.

Compare Efficiency of Algorithms : Big Oh notation  &  worst-case analysis.

Big Oh Big picture

• Constant functions 

          f(n) =1 

          Multiplying two numbers, printing "Hello World",  adding/averaging two numbers,
          accessing an array element with index.  

• Logarithmic functions

          f(n) = logn

          Finding an item in BST, looking for a name in a address book. Grows faster than constant function

• Linear functions

          f(n) = n

          Looking each item once ( twice, 10 times) in a list/array, counting number of items in a linked list

• Superlinear functions

          f(n) = nlgn

          Quicksort, mergesort, heapsort. Grows little faster than than linear

• Quadratic functions

          f(n) = n ^ 2

          Bubble sort, selection sort. Cost of looking at most or all pairs of items in an n-element universe

• Cubic functions

          f(n) = n^3

          Iterate through all triplets of items in a list

• Exponential functions

          f(n) = c^n    {c>1}

          Iterating all subsets of n items

• Factorial functions

         f(n) = n!
         Generate all permutations or ordering, Travelling salesman problem brute-force way. Functions like n!  

         n!   >>  2^n   >>   n^3    >>   n^2    >>    nlogn     >>    n    >>    logn    >>   1                             

References:

• Big Oh cheat sheet : link
• http://discrete.gr/complexity/

JVM Architecture

Java Virtual Machine (JVM) runs/executes java's compiled file(.class). Its job is to load class files and then execute the bytecode contained inside it. Below diagram shows the life cycle of a java program.
More details about bytecode on this post.

Java Virtual Machine is called virtual because it is an abstract computer (or machine) defined by specification. The implementation of the specification is also known as JVM. JVM in general could mean specification, implementation or instance. Let's cover these aspects in detail:

JVM Specification: [link]

JVM specification is template for implementing JVM tool. Specification defines certain features every JVM must have but leaves many choices to the designer of each implementation. It's the specification which says, how your JVM should behave? Like, if JVM runs out of memory, it should throw out an appropriate error. Also, JVM specification is different from the Java specification (Java specification controls the language; JVM specification controls the tool which executes programs)

JVM implementation

Specification is an abstract thing; it gets converted into a product after implementation. When you install JVM in your computer/laptop, we refer to a particular JVM implementation: Windows JVM for 32 bit machine, windows JVM for 64 bit machine, JVM for Mac OSX etc . JVM specification is flexible enough to allow implementation to be either completely in software or to a varying degree in hardware .

JVM instance

This is one of the most confusing aspect. JVM instance comes into picture when you run your Java application. Runtime instance job is, to run a Java application( i.e. java className). So when application gets launched runtime instance gets life and when application completes, the instance dies. Your application could be as small as a class which just prints "Hello World" or it could be as complicated as a distributed application (.war or .ear) which runs 24/7, until the world stops. So, if you start 3 applications at the same time using same JVM (implementation); it means that you have 3 JVM instances. Each Java application runs inside its own JVM.

Each Java application runs inside a run-time instance of some concrete implementation of the abstract specification of the JVM.

Architecture

JVM consists of two major subsystems and memory areas defined in specification. 

source : artima.com

Class Loader Subsystem

This subsystem, loads class files from both the program and Java API. As per specification, only those files which are needed are loaded. It loads types (classes and interfaces) using fully qualified name. After loading, it parses information about type( from the binary data contained in the class file), and then places this type information into the method area. And as the program runs, JVM places all the created objects on the heap.

This post talks class loading and unloading in detail.

Execution Engine Subsystem
Execution engine executes bytecode instructions contained in the loaded classes. This component of JVM can have some aspect implemented as hardware. JVM can support multiple execution techniques:

 1. bytecode interpreter : Interprets the byte code, one at a time.
 2. just-in-time compiler: faster than interpreter but  requires more memory.  Bytecodes of the method
 are compiled to native machine code when method is invoked for the first time. Also machine code      
     is cached so that it can be reused on the subsequent calls.
 3. adaptive optimizer: In this technique, JVM starts by interpreting the bytecodes but monitors the
     activity of the running program and identifies the most heavily used areas of code. As program
     runs, the virtual machine compiles to native machine code and optimizes only those heavily used
     areas of code. The rest of the bytecode is interpreted.

Runtime Data Areas

When a program runs, JVM organizes the memory it needs to execute a program into several runtime  data areas. Specification of data area is quite abstract to let it get implemented on a wide variety of computers and devices. Each instance of the JVM has one method area and one heap. These areas are shared by all threads running inside the virtual machine. Each running thread has its own PC (program counter) register and Java Stack. If thread is executing a Java  method (not a native method), the value of the PC register tells the next instruction to execute. Java stack stores the state of Java method invocation(not native invocation) for the thread. The state of a Java method invocation includes its local variables, the parameters with which it was invoked, its return value (if any), and intermediate calculations. The state of native method invocation is stored in an implementation dependent way in native method stacks, as well as in registers or other implementation dependent memory areas. 

Reference:
http://www.artima.com/insidejvm/ed2/jvm5.html 
http://www.artima.com/insidejvm/ed2/jvmP.html
http://kkarthikeyanblog.wordpress.com/2012/08/23/helloworld-in-jvms-view-how-java-program-executed-internally-in-jvm/ 

Related Post : Understanding Java Bytecode  Class Loading and unloading in JVM