======= Java Stuffs ========

Sunday, November 15, 2015

Semaphores in Java

A Semaphore is a thread synchronization construct that can be used either to send signal between threads to avoid missed signals, or to guard a critical section like you would with a lock. Java 5 comes with semaphore implementations in the java.util.concurrent package so you don't have to implement your own semaphores.
Still, it can be useful to know the theory behind their implementation and use.

Java 5 comes with a built-in Semaphore so you don't have to implement your own.

Simple SemaphoreHere is a simple Semaphore implementation:

public class Semaphore {
private boolean signal = false;

public synchronized void take() {
    this.signal = true;
    this.notify();
}

public synchronized void release() throws InterruptedException{
    while(!this.signal) wait();
    this.signal = false;
}

}

The take() method sends a signal which is stored internally in the Semaphore.
The release() method waits for a signal. When received the signal flag is cleared again and the release() method exited.

Using a semaphore like this you can avoid missed signals. You will call take() instead of notify() and release() instead of wait(). If the call to take() happens before the call to release() the thread calling release() will still know that take() was called, because the signal is stored internally in the signal variable. This is not the case with wait() and notify().

The names take() and release() may seem a bit odd when using semaphore for signaling. The names origin from the use of semaphores as locks, as explained

Using Semaphores for Signaling

Semaphore semaphore = new Semaphore();
SendingThread sender = new SendingThread(semaphore);
ReceivingThread receiver = new ReceivingThread(semaphore);
receiver.start();
sender.start();

public class SendingThread {
Semaphore semaphore = null;

public SendingThread(Semaphore semaphore){
    this.semaphore = semaphore;
}

public void run(){
    while(true){
      //do something, then signal
      this.semaphore.take();

    }
}
}

public class RecevingThread {
Semaphore semaphore = null;

public ReceivingThread(Semaphore semaphore){
this.semaphore = semaphore;
}

public void run(){
while(true){
this.semaphore.release();
//receive signal, then do something...
    }
}
}

Counting Semaphore
The Semaphore implementation in the previous section does not count the number of signals sent to it by take() method calls. We can change the Semaphore to do so. This is called a counting semaphore.
Here is a simple implementation of a counting semaphore:

public class CountingSemaphore {
private int signals = 0;

public synchronized void take() {
    this.signals++;
    this.notify();
}

public synchronized void release() throws InterruptedException{
    while(this.signals == 0) wait();
    this.signals--;
}

}

Bounded Semaphore
The CoutingSemaphore has no upper bound on how many signals it can store. We can change the semaphore implementation to have an upper bound, like this:

public class BoundedSemaphore {
private int signals = 0;
private int bound   = 0;

public BoundedSemaphore(int upperBound){
    this.bound = upperBound;
}

public synchronized void take() throws InterruptedException{
    while(this.signals == bound) wait();
    this.signals++;
    this.notify();
}

public synchronized void release() throws InterruptedException{
    while(this.signals == 0) wait();
    this.signals--;
    this.notify();
}
}

Notice how the take() method now blocks if the number of signals is equal to the upper bound. Not until a thread has called release() will the thread calling take() be allowed to deliver its signal, if the Bounded Semaphore has reached its upper signal limit.

Using Semaphores as Locks

It is possible to use a bounded semaphore as a lock. To do so, set the upper bound to 1, and have the call to take() and release() guard the critical section. Here is an example:

BoundedSemaphore semaphore = new BoundedSemaphore(1);

...

semaphore.take();

try{
//critical section
} finally {
semaphore.release();
}

In contrast to the signaling use case the methods take() and release() are now called by the same thread. Since only one thread is allowed to take the semaphore, all other threads calling take() will be blocked until release() is called. The call to release() will never block since there has always been a call to take() first.

You can also use a bounded semaphore to limit the number of threads allowed into a section of code. For instance, in the example above, what would happen if you set the limit of the BoundedSemaphore to 5?

5 threads would be allowed to enter the critical section at a time. You would have to make sure though, that the thread operations do not conflict for these 5 threads, or you application will fail.

The relase() method is called from inside a finally-block to make sure it is called even if an exception is thrown from the critical section.

Java 7 features
How to Reset Arraylist In Java
How HashMap Work in Java
Why wait (), notify () and notifyAll () must be called from synchronized block or method in Java
XPath to locate Information in XML
Internals of Garbage Collector
Reference Type in Java
Different Ways to Create Object Class Loaders in Java
Producer Consumer Problem
Why String is Final in Java
Singleton Class using Enum
JSON tutorial
Exceptional Handling in Java

Race Condition in Java

A race condition is a special condition that may occur inside a critical section. A critical section is a section of code that is executed by multiple threads and where the sequence of execution for the threads makes a difference in the result of the concurrent execution of the critical section.

When the result of multiple threads executing a critical section may differ depending on the sequence in which the threads execute, the critical section is said to contain a race condition. The term race condition stems from the metaphor that the threads are racing through the critical section, and that the result of that race impacts the result of executing the critical section.

Critical Sections

Running more than one thread inside the same application does not by itself cause problems. The problems arise when multiple threads access the same resources. For instance the same memory (variables, arrays, or objects), systems (databases, web services etc.) or files.
In fact, problems only arise if one or more of the threads write to these resources. It is safe to let multiple threads read the same resources, as long as the resources do not change.
Here is a critical section Java code example that may fail if executed by multiple threads simultaneously:

 public class Counter {

     protected long count = 0;

     public void add(long value){
         this.count = this.count + value;
     }
  }

Imagine if two threads, A and B, are executing the add method on the same instance of the Counter class. There is no way to know when the operating system switches between the two threads. The code in the add() method is not executed as a single atomic instruction by the Java virtual machine. Rather it is executed as a set of smaller instructions, similar to this:

Read this.count from memory into register.
Add value to register.
Write register to memory.

Observe what happens with the following mixed execution of threads A and B:

this.count = 0;

   A:  Reads this.count into a register (0)
   B:  Reads this.count into a register (0)
   B:  Adds value 2 to register
   B:  Writes register value (2) back to memory. this.count now equals 2
   A:  Adds value 3 to register
   A:  Writes register value (3) back to memory. this.count now equals 3

The two threads wanted to add the values 2 and 3 to the counter. Thus the value should have been 5 after the two threads complete execution. However, since the execution of the two threads is interleaved, the result ends up being different.
In the execution sequence example listed above, both threads read the value 0 from memory. Then they add their i ndividual values, 2 and 3, to the value, and write the result back to memory. Instead of 5, the value left in this.count will be the value written by the last thread to write its value. In the above case it is thread A, but it could as well have been thread B.

Race Conditions in Critical Sections

The code in the add() method in the example earlier contains a critical section. When multiple threads execute this critical section, race conditions occur.
More formally, the situation where two threads compete for the same resource, where the sequence in which the resource is accessed is significant, is called race conditions. A code section that leads to race conditions is called a critical section.

Preventing Race Conditions

To prevent race conditions from occurring you must make sure that the critical section is executed as an atomic instruction. That means that once a single thread is executing it, no other threads can execute it until the first thread has left the critical section.
Race conditions can be avoided by proper thread synchronization in critical sections. Thread synchronization can be achieved using a synchronized block of Java code. Thread synchronization can also be achieved using other synchronization constructs like locks or atomic variables like java.util.concurrent.atomic.AtomicInteger

Critical Section Throughput

For smaller critical sections making the whole critical section a synchronized block may work. But, for larger critical sections it may be beneficial to break the critical section into smaller critical sections, to allow multiple threads to execute each a smaller critical section. This may decrease contention on the shared resource, and thus increase throughput of the total critical section.
Here is a very simplified Java code example to show what I mean:

public class TwoSums {
    
    private int sum1 = 0;
    private int sum2 = 0;
    
    public void add(int val1, int val2){
        synchronized(this){
            this.sum1 += val1;   
            this.sum2 += val2;
        }
    }
}

Notice how the add() method adds values to two different sum member variables. To prevent race conditions the summing is executed inside a Java synchronized block. With this implementation only a single thread can ever execute the summing at the same time.
However, since the two sum variables are independent of each other, you could split their summing up into two separate synchronized blocks, like this:

public class TwoSums {
    
    private int sum1 = 0;
    private int sum2 = 0;
    
    public void add(int val1, int val2){
        synchronized(this){
            this.sum1 += val1;   
        }
        synchronized(this){
            this.sum2 += val2;
        }
    }
}

Now two threads can execute the add() method at the same time. One thread inside the first synchronized block, and another thread inside the second synchronized block. This way threads will have to wait less for each other to execute the add() method.

How would you improve performance of a Java application?

Pool valuable system resources like threads, database connections, socket connections etc. Emphasize on reuse of threads from a pool of threads. Creating new threads and discarding them after use can adversely affect performance. Also consider using multi-threading in your single-threaded applications where possible to enhance performance. Optimize the pool sizes based on system and application specifications and requirements. Having too many threads in a pool also can result in performance and scalability problems due to consumption of memory stacks (i.e. each thread has its own stack. Refer Q34, Q42 in Java section) and CPU context switching (i.e. switching between threads as opposed to doing real computation.).

Minimize network overheads by retrieving several related items simultaneously in one remote invocation if possible. Remote method invocations involve a network round-trip, marshaling and unmarshaling of parameters, which can cause huge performance problems if the remote interface is poorly designed.

Most applications need to retrieve data from and save/update data into one or more databases. Database calls are remote calls over the network. In general data should be lazily loaded (i.e. load only when required as opposed to pre-loading from the database with a view that it can be used later) from a database to conserve memory but there are use cases (i.e. need to make several database calls) where eagerly loading data and caching can improve performance by minimizing network trips to the database. Data can be eagerly loaded with a help of SQL scripts with complex joins or stored procedures and cached using third party frameworks or building your own framework.

Now the Question arises How would you refresh your cache?
Following strategies can be used:

1. Timed cache strategy where the cache can be replenished periodically (i.e. every 30 minutes, every hour etc). This is a simple strategy applicable when it is acceptable to show dirty data at times and also the data in the database does not change very frequently.

2. Dirty check strategy where your application is the only one which can mutate (i.e. modify) the data in the database. You can set a “isDirty” flag to true when the data is modified in the database through your application and consequently your cache can be refreshed based on the “isDirty” flag.

How would you refresh your cache if your database is shared by more than one application?
You could use one of the following strategies:

1. Database triggers: You could use database triggers to communicate between applications sharing the same database and write pollers which polls the database periodically to determine when the cache should be refreshed.

2. XML messaging :- To communicate between other applications sharing the same database or separate databases to determine when the cache should be refreshed.

Shallow cloning vs Deep cloning of objects?

The default behavior of an object’s clone() method automatically yields a shallow copy. So to achieve a deep copy the classes must be edited or adjusted.

Shallow copy: If a shallow copy is performed on obj-1 as shown in fig-2 then it is copied but its contained objects are not. The contained objects Obj-1 and Obj-2 are affected by changes to cloned Obj-2. Java supports shallow cloning of objects by default when a class implements the java.lang.Cloneable interface.

Deep copy: If a deep copy is performed on obj-1 as shown in fig-3 then not only obj-1 has been copied but the objects contained within it have been copied as well. Serialization can be used to achieve deep cloning. Deep cloning through serialization is faster to develop and easier to maintain but carries a performance overhead.

For example invoking clone() method on a collection like HashMap, List etc returns a shallow copy of HashMap, List, instances. This means if you clone a HashMap, the map instance is cloned but the keys and values themselves are not cloned. If you want a deep copy then a simple method is to serialize the HashMap to a ByteArrayOutputSream and then deserialize it. This creates a deep copy but does require that all keys and values in the HashMap are Serializable. Main advantage of this approach is that it will deep copy any arbitrary object graph.you can provide a static factory method to deep copy.

Example: to deep copy a list of Car objects.

public static List deepCopy(List listCars) {
List copiedList = new ArrayList(10);
for (Object object : listCars) { //JDK 1.5 for each loop
Car original = (Car)object;
Car carCopied = new Car(); //instantiate a new Car object
carCopied.setColor((original.getColor()));
copiedList.add(carCopied);
}
return copiedList;
}

Static vs. Dynamic class loading?

Static class loading

Classes are statically loaded with Java’s “new” operator.

class MyClass {
public static void main(String args[]) {
Car c = new Car();
}
}

Dynamic loading is a technique for programmatically invoking the functions of a class loader at run time. Let us look at how to load classes dynamically.

Class.forName (String className); //static method which returns a Class.The above static method returns the class object associated with the class name.

The string className can be supplied dynamically at run time. Unlike the static loading, the dynamic loading will decide whether to load the class Car or the class Jeep at runtime based on a properties file and/or other runtime conditions. Once the class is dynamically loaded the following method returns an instance of the loaded class. It’s just like creating a class object with no arguments.

class.newInstance (); //A non-static method, which creates an instance of a
//class (i.e. creates an object).

Jeep myJeep = null ; //myClassName should be read from a .properties file or a Constants class.
// stay away from hard coding values in your program. CO
String myClassName = "au.com.Jeep" ;
Class vehicleClass = Class.forName(myClassName) ;
myJeep = (Jeep) vehicleClass.newInstance();
myJeep.setFuelCapacity(50);

======= Java Stuffs ========

Sunday, November 15, 2015

Semaphores in Java

Read More

Race Condition in Java

Critical Sections

Race Conditions in Critical Sections

Preventing Race Conditions

Critical Section Throughput

Read More

How would you improve performance of a Java application?

Read More

Shallow cloning vs Deep cloning of objects?

Read More

Static vs. Dynamic class loading?

Read More

Blog Archive