Friday, 13 July 2012

Java Interview Questions- Thread & Multi-threading(Part - II)


Q. Write a multi-threaded Java program in which, one thread generates odd numbers and write to a pipe and the second thread generates even numbers and write to another pipe, and a third thread receives the numbers from both the pipes and evaluates if the sum is multiples of 5?

A. In Unix, a pipe (“|”) operator helps you to redirect output from one command to another. PipedReader and PipedWriter classes in java.io package helps you to do the same. It helps you to redirect the read input into writer seamlessly. In Unix, two different processes on different address spaces can communicate using pipe, but in java two threads on the JVM can communicate using Piped ByteStream/CharacterStream within the same process (i.e same address space)


Here is the code snippet. The Writer threads responsible for writing odd and even numbers to the respective pipes.


7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
package multithreading;
import java.io.IOException;
import java.io.PipedWriter;
public class NumberWriter extends Thread {
    private PipedWriter writer;
    private int maxNumber;
    private boolean isEvenNumber;
    public NumberWriter(PipedWriter writer, int maxNumber, boolean isEvenNumber) {
        this.writer = writer;
        this.maxNumber = maxNumber;
        this.isEvenNumber = isEvenNumber;
    }
    public void run() {
        int i = 1;
        while (i <= maxNumber) {
            try {
                if (isEvenNumber && (i % 2) == 0) {
                    writer.write(i);
                } else if (!isEvenNumber && i%2 != 0) {
                    writer.write(i);
                }
                ++i;
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
    }
    public static void main(String[] args) {
        final int MAX_NUM = 10;
        PipedWriter oddNumberWriter = new PipedWriter();
        PipedWriter evenNumberWriter = new PipedWriter();
        NumberWriter oddGen = new NumberWriter(oddNumberWriter, MAX_NUM, false);
        NumberWriter evenGen = new NumberWriter(evenNumberWriter, MAX_NUM, true);
        NumberReceiver receiver = new NumberReceiver(oddNumberWriter, evenNumberWriter);
        oddGen.start();
        evenGen.start();
        receiver.start();
    }
}

The receiver thread that listens to both odd and even number pipes and computes the sum. If the sum is a multiple of 5, it prints the numbers and the sum.


4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
package multithreading;
import java.io.IOException;
import java.io.PipedReader;
import java.io.PipedWriter;
public class NumberReceiver extends Thread {
    private PipedReader oddReader;
    private PipedReader evenReader;
    public NumberReceiver(PipedWriter oddWriter, PipedWriter evenWriter) {
        try {
            this.oddReader = new PipedReader(oddWriter);
            this.evenReader = new PipedReader(evenWriter);
        } catch (IOException e) {
            e.printStackTrace();
        }
    }
    public void run() {
        int odd =0, even=0;
         
        try {
            while (odd != -1) {
                odd = oddReader.read();
                even = evenReader.read();
                 
                if ((odd + even) % 5 == 0) {
                    System.out.println("match found " + odd + " + " + even + " = " + (odd + even));
                }
            }
                
        } catch (IOException e) {
            System.exit(1);
        }
        
         
    }
}


The output will be something like

1
match found 7 + 8 = 15
Q. Can you give some examples of thread racing conditions you had experienced?
A.

1. Declaring variables in JSP pages are not thread-safe. The declared variables in JSP pages end-up as instance variables in the converted Servlets.

<%! Calendar c = Calendar.getInstance(); %>

2. Decalring instance variables in Servlets is not thread safe, as Servlets are inherently multi-threaded and gets accessed by multiple-threads. Same is true for the Action classes in the struts framework.

3. Some of the Java standard library classes like SimpleDateFormat is not thread-safe. Always check the API to see if a particular class is thread-safe. If a particular class or library is not therad-safe, you could do one of three things.

  • Provide your own wrapper class that decorates the third-party library with proper synchronization. This is a typical use of the decorator design pattern.
  • Use an alternative library, which is thread-safe if available. For example, Joda Time Library. 
  • Use it in a thread-safe manner. For example, you could use the SimpleDateFormat class as shown below within a ThreadLocal class. Each thread will have its own instance of the SimpleDateFormat object.
?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class DateFormatTest {
  //anonymous inner class. Each thread will have its own copy
  private final static ThreadLocal<SimpleDateFormat> shortDateFormat =  new ThreadLocal<SimpleDateFormat>() {
            protected SimpleDateFormat initialValue() {
                 return new SimpleDateFormat("dd/MM/yyyy");
             }
  };
    
       
 public Date convert(String strDate)
                     throws ParseException {
  
    //get the SimpleDateFormat instance for this thread and parse the date string 
    Date d = shortDateFormat.get().parse(strDate);
    return d;
  }
}
4. The one that is very popular with the interviewers is writing the singleton classes that are not thread-safe.

Q. Can you have a true singleton class in Java? How would you write a thread-safe singleton class?
A. A singleton class is something for which only one instance exists per class loader. Single instance for a whole application cannot be guaranteed. That is just definition of what a singleton is. The one that is  popular with the interviewers is writing a thread-safe singleton class. For example, the following singleton class is not thread-safe because before a thread creates the Singleton instance, another thread can proceed to the instantiation part of the code -- instance = new Object( );  to create more than one instance of the Singleton object. Even though the code --> instance = new Object( ); appears to be single line, the JVM has to execute a number of internal steps like allocating memory, creating a new object and assigning the newly created object to the referenced variable. Only after the completion of these steps, the condition instance == null will return false.

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//final so that cannot be subclassed
public final class Singleton {
  
    private static Object instance = null;
  
    //private so that it cannot be instantiated from outside this class
    private Singleton() {}
  
    public static Object getInstance() {
        if (instance == null) {
            instance = new Object();
        }
  
        return instance;
    }
}
So, you can make the above code thread-safe in a number of ways.


Option 1: Synchronize the whole method or the block of code. This approach is not efficient as the use of synchronized keyword in a singleton class means that only one thread will be executing the synchronized block at a time and all other threads would be waiting.


Option 2: Eagerly initialize the singleton instance when the class is actually loaded as opposed to initializing it lazily at at run time only when it is accessed.


?
1
2
3
4
5
6
7
8
9
10
11
12
13
//final so that cannot be subclassed
public final class ThreadSafeSingleton {
  
    //eager initialization and instantitiated as soon as the class is loaded by a classloader in the JVM
    private static Object instance = new Object();
  
    //private so that it cannot be instantiated from outside this class
    private Singleton() {}
  
    public static Object getInstance() {
        return instance;
    }
}

Option 3: You can use the "Initialize-On-Demand Holder Class" idiom proposed by Brian Goetz to create a thread-safe lazy-initialized Singleton as shown below by creating an inner class.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
public final class ThreadSafeSingleton {
  
    //private so that it cannot be instantiated from outside this class
    private ThreadSafeSingleton() {}
     
    //static inner class, invoked only when ThreadSafeSingleton.getInstance() is called
    private static class ThreadSafeSingletonHolder {
        private static ThreadSafeSingleton instance = new ThreadSafeSingleton();
    }
  
    public static Object getInstance() {
        return ThreadSafeSingletonHolder.instance;
    }
}

Option 4: is to create a per thread singleton as discussed earlier with the ThreadLocal class for the SimpledateFormat.



Q. Explain how you would get thread-safety issues due to non-atomic operations with a code example?
A. The code snippets below demonstrates non-atomic operations producing incorrect results with code. The program below uses a shared Counter object, that is shared between three concurrent users (i.e. three threads). The Counter object is responsible for incrementing the counter.

Firstly, the Counter class. The counted values are stored in a HashMap by name (i.e. thread name) as the key for later retrieval


3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
import java.util.HashMap;
import java.util.Map;
public class Counter {
 //shared variable or resource
 private Integer count = Integer.valueOf(0);
  
 private Map<String, Integer> userToNumber = new HashMap<String, Integer>(10);
 public void  increment() {
  try {
   count = count + 1;   //increment the counter
   Thread.sleep(50);    // to imitate other operations and to make the racing condion to occur more often for the demo
   Thread thread = Thread.currentThread();
   userToNumber.put(thread.getName(), count);
  } catch (InterruptedException e) {
   e.printStackTrace();
  }
 }
  
  
 public Integer getCount(String name) {
  return userToNumber.get(name);
 }
  
}


Next, the Runnable task where each thread will be entering and executing concurrently.

3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class CountingTask implements Runnable {
  
  
 private Counter counter;
 public CountingTask(Counter counter) {
  super();
  this.counter = counter;
 }
 @Override
 public void run() {
  counter.increment();
  Thread thread = Thread.currentThread();
  System.out.println(thread.getName() + " value is " + counter.getCount(thread.getName()));
   
 }
}


Finally, the Manager class that creates 3 new threads from the main thread.
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public class CountingManager {
  
 public static void main(String[] args) throws InterruptedException {
   
  Counter counter = new Counter(); // create an instance of the Counter
  CountingTask task = new CountingTask(counter); // pass the counter to the runnable CountingTask
   
  //Create 10 user threads (non-daemon) from the main thread that share the counter object 
  Thread thread1 = new Thread(task, "User-1");
  Thread thread2 = new Thread(task, "User-2");
  Thread thread3 = new Thread(task, "User-3");
   
   
  //start the threads
  thread1.start();
  thread2.start();
  thread3.start();
   
   
  //observe the racing conditions in the output
   
 }
}

To see the racing condition, inspect the output of the above code

1
2
3
User-3 value is 3
User-1 value is 3
User-2 value is 3


All three threads or users get assigned the same value of 3 due to racing conditions. We are expecting to see three different count values to be assigned from 1 to 3. What happened here is that when the first thread incremented the count from 0 to 1 and entered into the sleep(50) block, the second and third threads incremented the counts from 1 to 2 and 2 to 3 respectively. This shows that the 2 operations -- the operation that increments the thread and the operation that stores the incremented value in a HashMap are not atomic, and produces incorrect results due to racing conditions.

Q. How will you fix the above racing issue?
A. This can be fixed a number of ways.

Option 1: Method level synchronization. This is the simplest. As you can see, the increment() method is synchronized, so that the other threads must wait for the thread that already has the lock to execute that method.

4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
import java.util.HashMap;
import java.util.Map;
public class Counter {
 //shared variable or resource
 private Integer count = Integer.valueOf(0);
  
 private Map<String, Integer> userToNumber = new HashMap<String, Integer>(10);
 public synchronized void  increment() {
  try {
   count = count + 1;
   Thread.sleep(50);
   Thread thread = Thread.currentThread();
   userToNumber.put(thread.getName(), count);
  } catch (InterruptedException e) {
   e.printStackTrace();
  }
 }
  
  
 public Integer getCount(String name) {
  return userToNumber.get(name);
 }
  
}

Option 2: Even though the Option 1 is simple, it locks the entire method and can adversely impact performance for long running methods as each thread has to execute the entire method one at a time. So, the Option 1 can be improved by providing block level lock. Lock only those operations that are acting on the shared resource and making it non-atomic.


The code below uses an Object, which has its own lock to ensure that two threads cannot execute both the Operation 1 and 2 at the same time because there is only one lock.

4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
import java.util.HashMap;
import java.util.Map;
public class Counter {
 //shared variable or resource
 private Integer count = Integer.valueOf(0);
  
 private Map<String, Integer> userToNumber = new HashMap<String, Integer>(10);
  
 private Object mutex = new Object();   // a lock
 public void  increment() {
  try {
   synchronized(mutex) {
     count = count + 1;                         //operation 1
     Thread.sleep(50);
     Thread thread = Thread.currentThread();
     userToNumber.put(thread.getName(), count); //operation 2
   }
   // there could be other operations here that uses the shared resource as read only
    
  } catch (InterruptedException e) {
   e.printStackTrace();
  }
 }
  
 public Integer getCount(String name) {
  return userToNumber.get(name);
 }
  
}

Option 3: This is a very trivial, but practical example. The Java 5 introduced locks and locks are better than using just objects for more flexible locking scenarios where Locks can be used in place of synchronized blocks. Locks offer more flexibility than synchronized blocks in that a thread can unlock multiple locks it holds in a different order than the locks were obtained. Here is the code that replaces synchronized with a reentrant lock. Synchronized blocks in Java are reentrant, which means if a Java thread enters a synchronized block of code, and thereby take the lock on the object the block is synchronized on, the thread can enter other Java code blocks synchronized on the same lock object.

For example, here is the demo of reentrant lock.
1
2
3
4
5
6
7
8
9
10
public class Reentrant{
  public synchronized method1(){
    method2();    //calls another synchronized method on the same object
  }
  public synchronized method2(){
    //do something
  }
}


Here is the Option 3 example using a ReentrantLock.

7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
import java.util.HashMap;
import java.util.Map;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;
public class Counter {
 // shared variable or resource
 private Integer count = Integer.valueOf(0);
 private Map<String, Integer> userToNumber = new HashMap<String, Integer>(10);
 private Lock mutex = new ReentrantLock(); // a lock
 public void increment() {
  try {
   mutex.lock();
   try {
    count = count + 1;
    Thread.sleep(50);
    Thread thread = Thread.currentThread();
    userToNumber.put(thread.getName(), count);
   } finally {
    mutex.unlock(); // finally block is executed even if an
        // exception is thrown
   }
  } catch (InterruptedException e) {
   e.printStackTrace();
  } finally {
  }
 }
 public Integer getCount(String name) {
  return userToNumber.get(name);
 }
}

Note that the locks are unlocked in a finally block as it is executed even if an exception is thrown.

The output for the above 3 options will be something like shown below. The order cannot be guaranteed. But you will get unique numbers assigned for each user.


1
2
3
User-1 value is 1
User-3 value is 2
User-2 value is 3


Q. The following code snippet changes the Counter class to maintain individual counting as in each user counter will be incremented starting from 1. So, the Counter will no longer be the shared resource. The CountingTask class is also modified to loop through each user 2 times as shown below. Is there anything wrong with the code shown below?



The Counter class with individual counts


5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
import java.util.HashMap;
import java.util.Map;
public class Counter {
 private Map<String, Integer> userToNumber = new HashMap<String, Integer>(10);
 public void increment() {
  Thread thread = Thread.currentThread();
  if (!userToNumber.containsKey(thread.getName())) {
   userToNumber.put(thread.getName(), Integer.valueOf(1));  //op1
  } else {
   Integer count = userToNumber.get(thread.getName());
   if (count != null) {
    ++count; // op2: increment it
    userToNumber.put(thread.getName(), count); //op3
   }
  }
 }
 public Integer getCount(String name) {
  return userToNumber.get(name);
 }
}

The counting task that repeats twice for each user
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class CountingTask implements Runnable {
 private Counter counter;
 public CountingTask(Counter counter) {
  super();
  this.counter = counter;
 }
 @Override
 public void run() {
  for (int i = 0; i < 2; i++) {
   counter.increment();
   Thread thread = Thread.currentThread();
   System.out.println(thread.getName() + " value is "
     + counter.getCount(thread.getName()));
  }
 }
}


A. If each user will be accessed by only one thread, then the above code is thread-safe because each user will be operating on his/her data. So, only one thread will access the map entry for User-1, and so on. But, what happens if User-3 has two threads created as shown below.

The Thread 3 and 4 are User 3. In this scenario, the above code is not thread safe, and it needs to be made atomic with one of the three options discussed above. It can be quite dangerous to assume that one user will be accessed only by one thread. What if in the future, additional threads are added to improve performance per user?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public class CountingManager {
  
 public static void main(String[] args) throws InterruptedException {
   
  Counter counter = new Counter(); // create an instance of the Counter
  CountingTask task = new CountingTask(counter); // pass the counter to the runnable CountingTask
   
  //Create 10 user threads (non-daemon) from the main thread that share the counter object 
  Thread thread1 = new Thread(task, "User-1");
  Thread thread2 = new Thread(task, "User-2");
  Thread thread3 = new Thread(task, "User-3"); //user 3
  Thread thread4 = new Thread(task, "User-3"); //User 3
   
   
  //start the threads
  thread1.start();
  thread2.start();
  thread3.start();
  thread4.start();
   
   
  //observe the racing conditions in the output
   
 }
}

If you don't perform the operations 1 to 3 atomically (i.e. as a unit), you will get an out put like

1
2
3
4
5
6
7
8
User-1 value is 1
User-1 value is 2
User-3 value is 2
User-3 value is 3
User-3 value is 2
User-3 value is 4
User-2 value is 1
User-2 value is 2

As you can see, the User-3 has the value 2 repeated twice and value 1 is missing. If you apply the one of the options outlined above, you will get an output like

1
2
3
4
5
6
7
8
User-1 value is 1
User-1 value is 2
User-3 value is 1
User-3 value is 2
User-2 value is 1
User-2 value is 2
User-3 value is 3
User-3 value is 4
Hence, the operations 1-3 need to be made atomic if accessed concurrently by multiple threads. Those three operations are

1. storing the initial value
2. incrementing the counter
3. storing the incremented value 

Posted by at
Labels:

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)