Concurrency

CONCURRENCY                      

1. BLOCKING QUEUE : Interface
2. ARRAY BQ :Data structure to hold thread elements
3. LINKED BQ: used 
4. SYNCHRNOUS BQ: Hold only 1 data at a time
5. CYCLIC BARRIER: 
6. SEMAPHORE :
7. RENTRANT LOCK
8. FORK AND JOIN CALL 
9. PRODUCER CONSUMER
10. ATOMIC BOOLEAN 
11. ATOMIC INTEGER
12. ATOMIC LONG 
13. ATOMIC REFERENCE
14. READ WRITE LOCK
15. EXCHANGER : COMMUNICATION BETWEEN THREADS
16. COUNTDOWNLATCH:
17. CONCURRENTLINKEDQUEUE
18. DELAY BQ

JAVA UTIL CONCURRENCY     API

EXECUTER SERVICE

public interface ExecutorService extends Executor

An Executor that provides methods to manage termination and methods that can produce a Future for tracking progress of one or more asynchronous tasks.

An ExecutorService can be shut down, which will cause it to reject new tasks. 

1)shutdown(): method will allow previously submitted tasks to execute before

2)shutdownNow(): method prevents waiting tasks from starting and attempts to stop currently executing tasks.

Why terminate ?

 An unused ExecutorService should be shut down to allow reclamation of its resources.

3)submit(): Method submit extends base method Executor.execute(java.lang.Runnable) by creating and returning a Future that can be used to cancel execution and/or wait for completion. 4) invokeAny and invokeAll: perform the most commonly useful forms of bulk execution, executing a collection of tasks and then waiting for at least one, or all, to complete. (Class ExecutorCompletionService can be used to write customized variants of these methods.)

The Executors class provides factory methods for the executor services provided in this package.

ExecutorService executorService = Executors.newFixedThreadPool(10);

ExecutorService executorService = Executors.newFixedThreadPool(10);

executorService.execute(new Runnable() {   

 public void run() {      

  System.out.println("Asynchronous task");  

  }

}

Future future = executorService.submit(new Callable(){ 

   public Object call() throws Exception {

               System.out.println("Asynchronous Callable");       

               return "Callable Result";   

 }

 });

 System.out.println("future.get() = " + future.get());

execute(Runnable)

submit(Runnable)

submit(Callable)

invokeAny(...)  // you can pass collection of callables

invokeAll(...)

Interrupting Executor Tasks

import java.util.concurrent.TimeUnit;

public class MyWorker implements Runnable {
  private final int sleepTime;
  public MyWorker(final int sleepTime) {
    this.sleepTime = sleepTime;
  }
  @Override
  public void run() {
    final long startTime = System.nanoTime();
    try {
      Thread.sleep(TimeUnit.SECONDS.toMillis(sleepTime));
      Util.printLog("Finished");
    } catch (final InterruptedException e) {
      Thread.currentThread().interrupt();
    }
  }
}

Future

 boolean cancel(boolean mayInterruptIfRunning)

Attempts to cancel execution of this task.

boolean get()

Waits if necessary for the computation to complete, and then retrieves its result.

V get(long timeout, TimeUnit unit)

Waits if necessary for at most the given time for the computation to complete, and then retrieves its result, if available.

V get(long timeout,
    TimeUnit unit)
      throws InterruptedException,
             ExecutionException,
             TimeoutException

Waits if necessary for at most the given time for the computation to complete, and then retrieves its result, if available.

V isCancelled()

Returns true if this task was cancelled before it completed normally.

boolean isDone()

Returns true if this task completed.

https://www.youtube.com/watch?v=lnbWFV4b7M4
http://geekrai.blogspot.in/2013/07/executor-framework-in-java.html
http://www.vogella.com/tutorials/JavaConcurrency/article.html

RACE CONDITION

A bunch of threads running for shared resources| critical section | Can be avoided by lock or synchronization

CONCURRENT MAP

The ConcurrentHashMap is very similar to the java.util.HashTable class, except that 
1)offers better concurrency than HashTable does. 
2)Does not lock the Map while you are reading from it. 
3)Additionally, ConcurrentHashMap does not lock the entire Map when writing to it. It only locks the part of the Map that is being written to, internally.

ConcurrentNavigableMap

• headMap(): 
• tailMap() 
•  subMap()   
•   desendingKeySet()   
•   desendingMap()
•  navigableKeySet()

  headMap()

The headMap(T toKey) method returns a view of the map containing the keys which are strictly less than the given key

ConcurrentNavigableMap map = new ConcurrentSkipListMap(); 

map.put("1", "one");

map.put("2", "two");

map.put("3", "three");

ConcurrentNavigableMap headMap = map.headMap("2");

//strictly less than

ConcurrentNavigableMap tailMap = map.tailMap("2");

//strictly greater than

ConcurrentNavigableMap subMap = map.subMap("2", "3");

//strictly submap

http://www.codejava.net/java-core/concurrency/java-concurrent-collection-concurrenthashmap-examples

BLOCKING QUEUE  Data structure to hold thread elements

1) BLOCKING QUEUE :  Data structure to hold thread elements

2) ARRAY BLOCKING QUEUE: 

Throws Exception Special Value Blocks Times Out insert Add Offer Put offer Remove remove Poll take poll Examine Element Peek

3) DELAY QUEUE    :  ELEMENTS IS OBTAINED WITH A DELAY

• PUT
• TAKE

4)LINKED BLOCKING QUEUE   : STORED IN LINKED DATA STRUCTURE

5) PRIORITY BLOCKING QUEUE   : Data is stored according to priority

6) SYNCHRONOUS QUEUE  :    The SynchronousQueue is a queue that can only contain a single element internally. A thread inserting an element into the queue is blocked until another thread takes that element from the queue

7) BLOCKING DEQUE : The BlockingDeque interface extends the BlockingQueue interface. That means that you can use a BlockingDeque as a BlockingQueue.

Throws Exception	Special Value	Blocks	TimesOut
INSERT	addFirst	offerFirst	putFirst	offerFirst
REMOVE	removeFirst	pollFirst	takeFirst	pollFIrst
EXAMINE	getFirst	peekFirst

	Throws Exception	Special Value	Blocks	TimesOut
INSERT	addLast	offerLast	putLast	offerLast
REMOVE	removeLast	pollLast	takeLast	pollLast
EXAMINE	getLast	getLast

8) LINKEDBLOCKING DEQUE

LOCKING MECHANISMS

A Lock is, however, more flexible and more sophisticated than a synchronized block.

The main differences between a Lock and a synchronized block are:

     A synchronized block makes no guarantees about the sequence in which threads waiting to entering it are granted access.

Lock lock = new ReentrantLock();  lock.lock();  //critical section  lock.unlock();

     You cannot pass any parameters to the entry of a synchronized block. Thus, having a timeout trying to get access to a synchronized block is not possible.

     The synchronized block must be fully contained within a single method. A Lock can have it's calls to lock() and unlock() in separate methods.

•          lock()
•      lockInterruptibly()
•      tryLock()
•      tryLock(long timeout, TimeUnit timeUnit)
•      unlock()

ReentrantReadWriteLock

ReadWriteLock readWriteLock = new ReentrantReadWriteLock();

readWriteLock.readLock().lock();

    // multiple readers can enter this section

    // if not locked for writing, and not writers waiting

    // to lock for writing.

readWriteLock.readLock().unlock();

readWriteLock.writeLock().lock();

    // only one writer can enter this section,

    // and only if no threads are currently reading.

readWriteLock.writeLock().unlock();

There are two types of locks

• Re enterant lock 
• Read Write Lock

RentrantLock
https://www.youtube.com/watch?v=-XipPj3tUu0


ReadWriteLock/RentrantReadWriteLock

package com.jcg.examples;


import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReadWriteLock;
import java.util.concurrent.locks.ReentrantReadWriteLock;


public class ThreadSafeArrayList
{
 private final ReadWriteLock readWriteLock = new ReentrantReadWriteLock(); 
 private final Lock readLock = readWriteLock.readLock();
 private final Lock writeLock = readWriteLock.writeLock();
 private final List list = new ArrayList<>();
 
 public void set(E o)
 {
  writeLock.lock();
  try
  {
   list.add(o);
   System.out.println("Adding element by thread"+Thread.currentThread().getName());
         }
  finally
  {
   writeLock.unlock();
  }
 }
 
 public E get(int i)
 {
  readLock.lock();
  try
  {
                        System.out.println("Printing elements by thread"+Thread.currentThread().getName());
   return list.get(i);
  }
  finally
  {
   readLock.unlock();
  }
 }
      public static void main(String[] args)
      {
           ThreadSafeArrayList threadSafeArrayList = new ThreadSafeArrayList<>();
           threadSafeArrayList.set("1");
           threadSafeArrayList.set("2");
           threadSafeArrayList.set("3");

          System.out.println("Printing the First Element : "+threadSafeArrayList.get(1));
      }
}

________________________________________________________________________


ATOMIC BOOLEAN

AtomicBoolean atomicBoolean = new AtomicBoolean();

boolean value = atomicBoolean.get();

atomicBoolean.set(false);

boolean oldValue = atomicBoolean.getAndSet(false);

boolean expectedValue = true; 

boolean newValue      = false;  

boolean wasNewValueSet = atomicBoolean.compareAndSet(expectedValue, newValue);

COMPARE AND SWAP|

AtomicBoolean atomicBoolean = new AtomicBoolean();

Getting the AtomicBoolean's Value

boolean value = atomicBoolean.get();

Setting the AtomicBoolean's Value

atomicBoolean.set(false);

Swapping the AtomicBoolean's Value. HERE OLD VALUE WILL BECOME TRUE AND NEW VALUE WILL BECOME FALSE

AtomicBoolean atomicBoolean = new AtomicBoolean(true);
boolean oldValue = atomicBoolean.getAndSet(false);

Compare and Set AtomicBoolean's Value  :he method compareAndSet() allows you to compare the current value of the AtomicBoolean to an expected value, and 

IF { [current value is equal to the expected value, 

a new value can be set on the AtomicBoolean. ]

}ELSE{

The compareAndSet() method is atomic, so only a single thread can execute it at the same time. Thus, the compareAndSet() method can be used to implemented simple synchronizers like locks.

}

AtomicBoolean atomicBoolean = new AtomicBoolean(true);

boolean expectedValue = true;
boolean newValue      = false;

boolean wasNewValueSet = atomicBoolean.compareAndSet(
    expectedValue, newValue);

ATOMIC INTEGER

AtomicInteger atomicInteger = new AtomicInteger();

atomicInteger.get();

atomicInteger.set(234);

AtomicInteger atomicInteger = new AtomicInteger(123);  

int expectedValue = 123; int newValue      = 234;

atomicInteger.compareAndSet(expectedValue, newValue);

addAndGet()
getAndAdd()
getAndIncrement()
incrementAndGet()
decrementAndGet()
getAndDecrement()



ATOMIC INTEGER/Long IS  THE NEW VOLATILE




The AtomicInteger class provides you with a int variable which can be read and written atomically, and which also contains advanced atomic operations like compareAndSet().




The AtomicInteger class is located in the java.util.concurrent.atomic package, so the full class name is java.util.concurrent.atomic.AtomicInteger . This text describes the version of AtomicInteger found in Java 8, but the first version was added in Java 5.




AtomicInteger atomicInteger = new AtomicInteger(123);
int theValue = atomicInteger.get();

int theValue = atomicInteger.set(234);



int expectedValue = 123;
int newValue      = 234;
atomicInteger.compareAndSet(expectedValue, newValue);

AtomicInteger atomicInteger = new AtomicInteger();
System.out.println(atomicInteger.getAndAdd(10));
System.out.println(atomicInteger.addAndGet(10));

decrementAndGet()

getAndDecrement()


























SYNCHORNIZERS







EXCHANGER : 



java.util.concurrent.Exchanger class represents a kind of rendezvous point where two threads can exchange objects









SEMAPHORE : As semaphore typically has two uses:







To guard a critical section against entry by more than N threads at a time.

To send signals between two threads.







acquire():For each call to acquire() a permit is taken by the calling thread.
release()  :For each call to release() a permit is returned to the semaphore. 
availablePermits()
acquireUninterruptibly()
drainPermits()
hasQueuedThreads()
getQueuedThreads()
tryAcquire()








     



CYCLIC BARRIER : synchronization mechanism that can synchronize threads progressing through some algorithm. In other words, it is a barrier that all threads must wait at, until all threads reach it, before any of the threads can continue






“concurrency construct that allows one or more threads to wait for a given set of operations to complete.”






COUNTDOWNLATCH     : CountDownLatch latch = new CountDownLatch(3);










Synchronizer which allows one Thread  to wait for one or more Threads before starts processing. 



1:  package com.tvidushi.concurrency.synchronizers;  
2:  import java.util.concurrent.CountDownLatch;  
3:  public class CountDownLatchExample {  
4:    public static void main(String args[]) {  
5:      CountDownLatch latch = new CountDownLatch(6);  
6:      Thread th1 = new Thread(new Sample( 10000, latch));  
7:      Thread th2 = new Thread(new Sample(10000, latch));  
8:      Thread th3 = new Thread(new Sample( 10000, latch));  
9:      Thread th4 = new Thread(new Sample( 10000, latch));  
10:      Thread th5 = new Thread(new Sample(10000, latch));  
11:      Thread th6 = new Thread(new Sample(100, latch));  
12:      th1.start();   
13:      th2.start();   
14:      th3.start();  
15:      th4.start();   
16:      th5.start();   
17:      th6.start();  
18:      try{  
19:            log("before threads started :"+System.currentTimeMillis());  
20:        latch.await();   
21:        log("After threads threads started "+System.currentTimeMillis());  
22:      }catch(InterruptedException ie){  
23:        ie.printStackTrace();  
24:      }  
25:    }  
26:    private static void log(String log) {  
27:           System.out.println(log);  
28:    }  
29:    static class Sample implements Runnable{  
30:      int time;  
31:      CountDownLatch latch;  
32:      public Sample( int time, CountDownLatch latch){  
33:        this.time = time;  
34:        this.latch = latch;  
35:      }  
36:      @Override  
37:      public void run() {  
38:        try {  
39:          Thread.sleep(time);  
40:         log(Thread.currentThread()+" started ");  
41:        } catch (InterruptedException ex) {  
42:        }  
43:        /*  
44:          Decrements the count of the latch, releasing all waiting threads if the count reaches zero.  
45:                          If the current count is greater than zero then it is decremented. If the new count is zero then all waiting   
46:                          threads are re-enabled for thread scheduling purposes.  
47:                          If the current count equals zero then nothing happens.  
48:                          */  
49:        latch.countDown();  
50:      }  
51:    } 










































































 package com.tvidushi.concurrency.synchronizers;  
 /*  
  *   
  * Difference between a CyclicBarrier and a CountDownLatch  
 A CountDownLatch can be used only once in a program(until it’s count reaches 0).  
 A CyclicBarrier can be used again and again once all the threads in a barriers is released.  
  *   
  * */  
 import java.util.concurrent.CyclicBarrier;  
 public class CyclicBarrierExample {  
   public static void main(String args[]) {  
     CyclicBarrier cyclicBarrier = new CyclicBarrier(3);  
     /**  
      * Step 1 instantiate  
      * 1) new CyclicBarrier(3)  
      * Creates a new CyclicBarrier that will trip when the given number of parties (threads) are waiting upon it,   
      * and does not perform a predefined action when the barrier is tripped.  
             Parameters:  
             parties the number of threads that must invoke await before the barrier is tripped  
                     Throws:  
                     IllegalArgumentException - if parties is less than 1  
      *   
      * use this when you same thread to be invoked n number of times  
      * new CyclicBarrier(3, new Sample())  
      *   
      *   
      * Step 2   
      *   
      */  
     new Thread(new Sample()).start();;  
     Thread th2 = new Thread(()->{  
          log(Thread.currentThread()+"------ started");  
     });  
     Thread th3 = new Thread(()->{  
          log(Thread.currentThread()+" ----- started");  
     });  
      log("before threads started :"+System.currentTimeMillis());  
           if(cyclicBarrier.isBroken()){  
                 th2.start();   
              th3.start();  
           }  
       log("After threads threads started "+System.currentTimeMillis());  
   }  
   private static void log(String log) {  
         System.out.println(log);  
    }  
   static class Sample implements Runnable{         
     @Override  
     public void run() {  
       try {  
                 Thread.sleep(1000);   
        log(Thread.currentThread()+" started ");  
       } catch (InterruptedException e) {  
       }  
     }  
   }} 

FORK AND JOIN CALL

      Tasks can keep splitting their work into smaller subtasks for as long as it makes to split up the task.When a task has split itself up into subtasks, the task waits until the subtasks have finished executing.

  These two types of tasks are represented by the

RecursiveAction :breaks up work in smaller sections that can be executed by independent threads or CPUS  doenst return any thing

import java.util.concurrent.RecursiveAction;  

public class MyRecursiveAction extends RecursiveAction {

1.   RecursiveTask : Recursive task returns result

import java.util.concurrent.RecursiveTask;           

public class MyRecursiveTask extends RecursiveTask {

--------------------------------------------------------------------------------

Concurrency Control Algorithms

In progress Blog

Array Based Queuing Locks

Banker's algorithm  : The Banker's algorithm, sometimes referred to as the detection algorithm, is a resource allocation and deadlock avoidance algorithm developed by Edsger Dijkstra that tests for safety by simulating the allocation of predetermined maximum possible amounts of all resources, and then makes an "s-state" check to test for possible deadlock conditions for all other pending activities, before deciding whether allocation should be allowed to continue.

• When a new process enters a system, it must declare the maximum number of instances of each resource type that it may ever claim; 
• clearly, that number may not exceed the total number of resources in the system. 
• Also, when a process gets all its requested resources it must return them in a finite amount of time.

Mutual Exclusion Algorithms

Dekker's algorithm

Peterson's algorithm     : Peterson's algorithm (or Peterson's solution) is a concurrent programming algorithm for mutual exclusion that allows two or more processes to share a single-use resource without conflict, using only shared memory for communication. 

Lamport's bakery algorithm

Lamport's bakery algorithm is one of many mutual exclusion algorithms designed to prevent concurrentthreads entering critical sections of code concurrently to eliminate the risk of data corruption.

Eisenberg & McGuire algorithm  : The Eisenberg & McGuire algorithm is an algorithm for solving the critical sections problem, a general version of the dining philosophers problem. 

Lamport's distributed mutual exclusion algorithm : Lamport's Distributed Mutual Exclusion Algorithm is a contention-based algorithm for mutual exclusion on a distributed system

Maekawa's algorithm : Maekawa's algorithm is an algorithm for mutual exclusion on a distributed system. The basis of this algorithm is a quorum like approach where any one site needs only to seek permissions from a subset of other sites.

Multiversion Concurrency Control

is a concurrency control method commonly used by database management systems to provide concurrent access to the database and in programming languages to implement transactional memory.^[1]

List of databases using multiversion concurrency control

• List of databases using MVCC

Non-blocking algorithm

• Wait-Freedom
• Lock Freedom
• Obstruction Freedom         

Raymond's algorithm

• Spinlock     : A  spinlock is a lock which causes a thread trying to acquire it to simply wait in a loop ("spin") while repeatedly checking if the lock is available. Since the thread remains active but is not performing a useful task, the use of such a lock is a kind of busy waiting. Once acquired, spinlocks will usually be held until they are explicitly released, although in some implementations they may be automatically released if the thread being waited on (that which holds the lock) blocks, or "goes to sleep".
• Ticket lock   :In computer science, a ticket lock is a synchronization mechanism, or locking algorithm, that is a type of spinlock that uses "tickets" to control which thread of execution is allowed to enter a critical section.

Timestamp-based concurrency control

In computer science, a timestamp-based concurrency control algorithm is a non-lock concurrency control method. It is used in some databases to safely handle transactions, using timestamps.

--------------------------------------------------------------------------------

UNDERSTANDING CONCURRENCY APPLICATION POINT OF VIEW

https://fizalihsan.github.io/technology/java-concurrency.html#check-then-act

http://divan.github.io/posts/go_concurrency_visualize/
https://www.youtube.com/watch?v=KyuFeiG3Y60