Fail Fast Vs Fail Safe Iterator In Java

Difference between Fail fast and fail safe iterator  or  Fail fast vs Fail Safe iterator is one of those questions which are  used to test your knowledge about the topic Concurrency.
Before we discuss in detail about fail safe iterator and fail fast iterator in addition to  their comparison , we should understand the termConcurrent Modification .

What is Concurrent Modification ?

When one or more thread is iterating over the collection, in between, one thread changes the structure of the collection (either adding the element to the collection or by deleting the element in the collection or by updating the value at particular position in the collection) is known as Concurrent Modification

Difference between Fail Fast iterator and Fail Safe iterator

Fail fast Iterator

Fail fast iterator while iterating through the collection , instantly throws Concurrent Modification Exception if there is structural modification  of the collection . Thus, in the face of concurrent modification, the iterator fails quickly and cleanly, rather than risking arbitrary, non-deterministic behavior at an undetermined time in the future. 

Fail-fast iterator can throw ConcurrentModificationException in two scenarios :

Single Threaded Environment
  
After the creation of the iterator , structure is modified at any time by any method other than iterator's own remove method. 
  
Multiple Threaded Environment 

 If one thread is modifying the structure of the collection while other thread is iterating over it .


According to  Oracle docs , the fail-fast behavior of an iterator cannot be guaranteed as it is, generally speaking, impossible to make any hard guarantees in the presence of unsynchronized concurrent modification. Fail-fast iterators throw ConcurrentModificationException on a best-effort basis. Therefore, it would be wrong to write a program that depended on this exception for its correctness: the fail-fast behavior of iterators should be used only to detect bugs. 


Interviewer : How  Fail  Fast Iterator  come to know that the internal structure is modified ?

Iterator read internal data structure (object array) directly . The internal data structure(i.e object array) should not be modified while iterating through the collection. To ensure this it maintains an internal  flag "mods" .Iterator checks the "mods" flagwhenever it gets the next value (using hasNext() method and next() method). Value ofmods flag changes whenever there is an structural modification. Thus indicating iterator to throw ConcurrentModificationException.


Fail Safe Iterator :

Fail Safe Iterator makes copy of the internal data structure (object array) and iterates over the copied data structure.Any structural modification done to the iterator affects the copied data structure.  So , original data structure remains  structurally unchanged .Hence , no ConcurrentModificationException throws by the fail safe iterator.

Two  issues associated with Fail Safe Iterator are :

1. Overhead of maintaining the copied data structure i.e memory.

2.  Fail safe iterator does not guarantee that the data being read is the data currently in the original data structure. 

According to Oracle docs , fail safe iterator is ordinarily too costly, but may be more efficient than alternatives when traversal operations vastly outnumber mutations, and is useful when you cannot or don’t want to synchronize traversals, yet need to preclude interference among concurrent threads. The "snapshot" style iterator method uses a reference to the state of the array at the point that the iterator was created. This array never changes during the lifetime of the iterator, so interference is impossible and the iterator is guaranteed not to throw ConcurrentModificationException.The iterator will not reflect additions, removals, or changes to the list since the iterator was created. Element-changing operations on iterators themselves (remove(), set(), and add()) are not supported. These methods throw UnsupportedOperationException.



Example of Fail Fast Iterator and Fail Safe Iterator

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;

public class FailFastExample
{
    
    
    public static void main(String[] args)
    {
        Map<String,String> premiumPhone = new HashMap<String,String>();
        premiumPhone.put("Apple", "iPhone");
        premiumPhone.put("HTC", "HTC one");
        premiumPhone.put("Samsung","S5");
        
        Iterator iterator = premiumPhone.keySet().iterator();
        
        while (iterator.hasNext())
        {
            System.out.println(premiumPhone.get(iterator.next()));
            premiumPhone.put("Sony", "Xperia Z");
        }
        
    }
    
}

Output :

iPhone 

Exception in thread "main" java.util.ConcurrentModificationException
        at java.util.HashMap$HashIterator.nextEntry(Unknown Source)
        at java.util.HashMap$KeyIterator.next(Unknown Source)
        at FailFastExample.main(FailFastExample.java:20)

Fail Safe Iterator Example :

import java.util.concurrent.ConcurrentHashMap;
import java.util.Iterator;


public class FailSafeExample
{
    
    
    public static void main(String[] args)
    {
        ConcurrentHashMap<String,String> premiumPhone = 

                               new ConcurrentHashMap<String,String>();
        premiumPhone.put("Apple", "iPhone");
        premiumPhone.put("HTC", "HTC one");
        premiumPhone.put("Samsung","S5");
        
        Iterator iterator = premiumPhone.keySet().iterator();
        
        while (iterator.hasNext())
        {
            System.out.println(premiumPhone.get(iterator.next()));
            premiumPhone.put("Sony", "Xperia Z");
        }
        
    }
    
}

Output :

S5
HTC one
iPhone

Recap : Difference between Fail Fast Iterator and Fail Safe Iterator 

	Fail Fast Iterator	Fail Safe Iterator
Throw ConcurrentModification Exception	Yes	No
Clone object	No	Yes
Memory Overhead	No	Yes
Examples	HashMap,Vector,ArrayList,HashSet	CopyOnWriteArrayList, ConcurrentHashMap

Java Concurrency

Most of these features are implemented in the new java.util.concurrent packages. 

There are also new concurrent data structures in the Java Collections Framework.

Lock objects support locking idioms that simplify many concurrent applications.

Executors define a high-level API for launching and managing threads. Executor implementations provided by 

java.util.concurrent provide thread pool management suitable for large-scale applications.

Concurrent collections make it easier to manage large collections of data, 

and can greatly reduce the need for synchronization.

Atomic variables have features that minimize synchronization and help avoid memory consistency errors.

ThreadLocalRandom (in JDK 7) provides efficient generation of pseudorandom numbers from multiple threads.

Detailed post on java interview preparation.

Java consumer - producer implementation.

1. What is Synchronized Methods ?

   The Java programming language provides two basic synchronization idioms: synchronized methods and 

   synchronized statements. The more complex of the two, synchronized statements, are described in the next section. 

   This section is about synchronized methods.

To make a method synchronized, simply add the synchronized keyword to its declaration:

public class SynchronizedCounter {

    private int c = 0;

    public synchronized void increment() {

       c++;

    }

    public void decrement() {

       synchronized(this){

        c--;

       }

    }

    public synchronized int value() {

       return c;

   }

}

If count is an instance of SynchronizedCounter, then making these methods synchronized has two effects:

• First, it is not possible for two invocations of synchronized methods on the same object to interleave. 

When one thread is executing a synchronized method for an object, all other threads that invoke synchronized methods 

for the same object block (suspend execution) until the first thread is done with the object.

• Second, when a synchronized method exits, it automatically establishes a happens-before relationship with any 

subsequent invocation of a synchronized method for the same object. This guarantees that changes to the state of 

the object are visible to all threads.

   Note that constructors cannot be synchronized — using the synchronized keyword with a constructor is a syntax error.

   Synchronizing constructors doesn't make sense, because only the thread that creates an object should have

   access to it while it is being constructed.

2. What is Intrinsic Locks and Synchronization ?

   Synchronization is built around an internal entity known as the intrinsic lock or monitor lock. 

   (The API specification often refers to this entity simply as a "monitor.") Intrinsic locks play a role in 

   both aspects of synchronization: enforcing exclusive access to an object's state and establishing happens-before

   relationships that are essential to visibility.

  Every object has an intrinsic lock associated with it. By convention, a thread that needs exclusive and consistent 

  access to an object's fields has to acquire the object's intrinsic lock before accessing them, and then release the 

  intrinsic lock when it's done with them. A thread is said to own the intrinsic lock between the time it has acquired 

  the lock and released the lock. As long as a thread owns an intrinsic lock, no other thread can acquire the same lock.

  The other thread will block when it attempts to acquire the lock.

  When a thread releases an intrinsic lock, a happens-before relationship is established between that action and any 

  subsequent acquistion of the same lock.

3. What is Reentrant Synchronization ?
  Recall that a thread cannot acquire a lock owned by another thread. But a thread can acquire a lock
  that it already owns. Allowing a thread to acquire the same lock more than once enables reentrant
  synchronization. This describes a situation where synchronized code, directly or indirectly, invokes
  a method that also contains synchronized code, and both sets of code use the same lock. Without
  reentrant synchronization, synchronized code would have to take many additional precautions to
  avoid having a thread cause itself to block.

4. What is Deadlock ?
  Deadlock describes a situation where two or more threads are blocked forever, waiting for each other.
  In below example method m1 and m2 both are taking lock of Integer and String class in different order
  and blocking each other for ever.
  This deadlock can be solved by putting same order of lock for Integer and String class in method m1 and m2.

package com.learning.thread;
public class Blocking {
void m1() {
System.out.println(" m1 :");
synchronized (Blocking.class) {
try {
Thread.sleep(10000);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
synchronized (String.class) {
}
}
void m2() {
System.out.println(" m2 :");
synchronized (String.class) {
try {
Thread.sleep(10000);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
synchronized (Blocking.class) {
}
}
public static void main(String[] args) {
Blocking b1 = new Blocking();
b1.m1();
b1.m2();
}
}

5. What is Starvation and Livelock ?
Starvation
Starvation describes a situation where a thread is unable to gain regular access to shared resources
 and is unable to make progress. This happens when shared resources are made unavailable for long
 periods by "greedy" threads. For example, suppose an object provides a synchronized method that often takes
 a long time to return. If one thread invokes this method frequently, other threads that also need frequent
 synchronized access to the same object will often be blocked.
Livelock
A thread often acts in response to the action of another thread. If the other thread's action is also
a response to the action of another thread, then livelock may result. As with deadlock, livelocked threads
are unable to make further progress. However, the threads are not blocked — they are simply too busy responding
 to each other to resume work. This is comparable to two people attempting to pass each other in a corridor:
 Alphonse moves to his left to let Gaston pass, while Gaston moves to his right to let Alphonse pass.
 Seeing that they are still blocking each other, Alphone moves to his right, while Gaston moves to his left.
 They're still blocking each other, so...

6. What is Immutable Objects ?
An object is considered immutable if its state cannot change after it is constructed. Maximum reliance
on immutable objects is widely accepted as a sound strategy for creating simple, reliable code.
Immutable objects are particularly useful in concurrent applications. Since they cannot change state,
they cannot be corrupted by thread interference or observed in an inconsistent state.
Programmers are often reluctant to employ immutable objects, because they worry about the cost of creating
a new object as opposed to updating an object in place. The impact of object creation is often overestimated,
and can be offset by some of the efficiencies associated with immutable objects. These include decreased
overhead due to garbage collection, and the elimination of code needed to protect mutable objects from corruption.
The following subsections take a class whose instances are mutable and derives a class with immutable instances
from it. In so doing, they give general rules for this kind of conversion and demonstrate some of the advantages
of immutable objects.



7. What should be Strategy for Defining Immutable Objects ?
The following rules define a simple strategy for creating immutable objects. Not all classes documented as "immutable" follow these rules. This does not necessarily mean the creators of these classes were sloppy — they may have good reason for believing that instances of their classes never change after construction. However, such strategies require sophisticated analysis and are not for beginners.
1. Don't provide "setter" methods — methods that modify fields or objects referred to by fields.
2. Make all fields final and private.
3. Don't allow subclasses to override methods. The simplest way to do this is to declare the class as final. A more sophisticated approach is to make the constructor private and construct instances in factory methods.
4. If the instance fields include references to mutable objects, don't allow those objects to be changed:
5. Don't provide methods that modify the mutable objects.
6. Don't share references to the mutable objects. Never store references to external, mutable objects passed to the constructor; if necessary, create copies, and store references to the copies. Similarly, create copies of your internal mutable objects when necessary to avoid returning the originals in your methods.

8. What are High Level Concurrency Objects ?
So far, this we have focused on the low-level APIs that have been part of the Java platform from the very beginning. These APIs are adequate for very basic tasks, but higher-level building blocks are needed for more advanced tasks. This is especially true for massively concurrent applications that fully exploit today's multiprocessor and multi-core systems.
In this section we'll look at some of the high-level concurrency features introduced with version 5.0 of the Java platform. Most of these features are implemented in the new java.util.concurrent packages. There are also new concurrent data structures in the Java Collections Framework.
• Lock objects support locking idioms that simplify many concurrent applications.
• Executors define a high-level API for launching and managing threads. Executor implementations provided by java.util.concurrent provide thread pool management suitable for large-scale applications.
• Concurrent collections make it easier to manage large collections of data, and can greatly reduce the need for synchronization.
• Atomic variables have features that minimize synchronization and help avoid memory consistency errors.
• ThreadLocalRandom (in JDK 7) provides efficient generation of pseudorandom numbers from multiple threads

9. What is Executors ?
In large-scale applications, it makes sense to separate thread management and creation from the rest of the application. Objects that encapsulate these functions are known as executors. The following subsections describe executors in detail.
• Executor Interfaces define the three executor object types.
• Thread Pools are the most common kind of executor implementation.
• Fork/Join is a framework (new in JDK 7) for taking advantage of multiple processors.
Executor Interfaces
The java.util.concurrent package defines three executor interfaces:
• Executor, a simple interface that supports launching new tasks.
• ExecutorService, a subinterface of Executor, which adds features that help manage the lifecycle, both of the individual tasks and of the executor itself.
• ScheduledExecutorService, a subinterface of ExecutorService, supports future and/or periodic execution of tasks.
Typically, variables that refer to executor objects are declared as one of these three interface types, not with an executor class type.

Below is the example of ExecutorService using cachedThreadPool. This is using Callable instance, which does the task and return the result to calling programme.

import java.util.concurrent.Callable;
import java.util.concurrent.ExecutionException;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.Future;

public class ThreadWithResultExample {
 static ExecutorService exec = Executors.newCachedThreadPool();
 public static void main(String...strings){
  Future result = exec.submit(new Worker());
  try {
  System.out.println(result.get());
 } catch (InterruptedException e) {
  e.printStackTrace();
 } catch (ExecutionException e) {
  e.printStackTrace();
 }
  exec.shutdown();
 }
}

class Worker implements Callable {
 @Override
 public String call() throws Exception {
  return (String) "result";
 }

10. What is Thread Pools ?
Most of the executor implementations in java.util.concurrent use thread pools, which consist of worker threads. This kind of thread exists separately from the Runnable and Callable tasks it executes and is often used to execute multiple tasks.Using worker threads minimizes the overhead due to thread creation. Thread objects use a significant amount of memory, and in a large-scale application, allocating and deallocating many thread objects creates a significant memory management overhead.One common type of thread pool is the fixed thread pool. This type of pool always has a specified number of threads running; if a thread is somehow terminated while it is still in use, it is automatically replaced with a new thread. Tasks are submitted to the pool via an internal queue, which holds extra tasks whenever there are more active tasks than threads.
  An important advantage of the fixed thread pool is that applications using it degrade gracefully. To understand this, consider a web server application where each HTTP request is handled by a separate thread. If the application simply creates a new thread for every new HTTP request, and the system receives more requests than it can handle immediately, the application will suddenly stop responding to all requests when the overhead of all those threads exceed the capacity of the system. With a limit on the number of the threads that can be created, the application will not be servicing HTTP requests as quickly as they come in, but it will be servicing them as quickly as the system can sustain.
  A simple way to create an executor that uses a fixed thread pool is to invoke the newFixedThreadPool factory method in java.util.concurrent.ExecutorsThis class also provides the following factory methods:
•  The newCachedThreadPool method creates an executor with an expandable thread pool. This executor is suitable for applications that launch many short-lived tasks.
•  The newSingleThreadExecutor method creates an executor that executes a single task at a time.
•  Several factory methods are ScheduledExecutorService versions of the above executors.
If none of the executors provided by the above factory methods meet your needs, constructing instances of java.util.concurrent.ThreadPoolExecutor or java.util.concurrent.ScheduledThreadPoolExecutor will give you additional options.

11. What is Fork/Join ?
New in the Java SE 7 release, the fork/join framework is an implementation of the ExecutorService interface that helps you take advantage of multiple processors. It is designed for work that can be broken into smaller pieces recursively. The goal is to use all the available processing power to make your application wicked fast.
As with any ExecutorService, the fork/join framework distributes tasks to worker threads in a thread pool. The fork/join framework is distinct because it uses a work-stealing algorithm. Worker threads that run out of things to do can steal tasks from other threads that are still busy.
The center of the fork/join framework is the ForkJoinPool class, an extension of AbstractExecutorService. ForkJoinPool implements the core work-stealing algorithm and can execute ForkJoinTasks.
Basic Use

Using the fork/join framework is simple. The first step is to write some code that performs a segment of the work. Your code should look similar to this:
if (my portion of the work is small enough)
     do the work directly
else
     split my work into two pieces
invoke the two pieces and wait for the results

Wrap this code as a ForkJoinTask subclass, typically as one of its more specialized types RecursiveTask(which can return a result) or RecursiveAction.
After your ForkJoinTask is ready, create one that represents all the work to be done and pass it to the invoke() method of a ForkJoinPool instance.

12. What is Concurrent Collections ?
The java.util.concurrent package includes a number of additions to the Java Collections Framework. These are most easily categorized by the collection interfaces provided:
• BlockingQueue defines a first-in-first-out data structure that blocks or times out when you attempt to add to a full queue, or retrieve from an empty queue.
• ConcurrentMap is a subinterface of java.util.Map that defines useful atomic operations. These operations remove or replace a key-value pair only if the key is present, or add a key-value pair only if the key is absent. Making these operations atomic helps avoid synchronization. The standard general-purpose implementation of ConcurrentMap is ConcurrentHashMap, which is a concurrent analog of HashMap.
• ConcurrentNavigableMap is a subinterface of ConcurrentMap that supports approximate matches. The standard general-purpose implementation of ConcurrentNavigableMap is ConcurrentSkipListMap, which is a concurrent analog of TreeMap.
    All of these collections help avoid Memory Consistency Errors by defining a happens-before relationship between an operation that adds an object to the collection with subsequent operations that access or remove that object.
package com.learning.thread;
import java.util.concurrent.ArrayBlockingQueue;
public class MyArrayBlockingQueue {
ArrayBlockingQueue<String> abq = new ArrayBlockingQueue<String>(10,true);//Size 10 and fair policy
String getData(){
return abq.poll();
}
void setData(String e){
abq.add(e);
}
public static void main(String...strings){
final MyArrayBlockingQueue queue = new MyArrayBlockingQueue();
for(String s: queue.abq){
System.out.println(s);
}
// Data producer
new Thread(
new Runnable(){
@Override
public void run() {
for(int i = 0; i<10; i++){
queue.setData( String.valueOf(i));
}
}
}
).start();
// Consumer
new Thread(
new Runnable(){
@Override
public void run() {
for(int i = 0; i<10; i++){
System.out.println(queue.getData());
}
}
}
).start();
}
}
view rawarrayBlocking.java hosted with ❤ by GitHub
13. Can you pass a Thread object to Executor.execute? Would such an invocation make sense? Why or why not ?
Thread implements the Runnable interface, so you can pass an instance of Thread to Executor.execute. However it doesn't make sense to use Thread objects this way. If the object is directly instantiated from Thread, its run method doesn't do anything. You can define a subclass of Thread with a useful run method — but such a class would implement features that the executor would not use.