Concurrency and parallel computing

Sequential vs Parallel Computing

Sequential computing

• Series are instructions are performed in a sequential fashion
• One instruction is performed after the other

Parallel Computing

• Series of instruction are performed in parallel to one another
• Mostly faster
• Difficult to implement and processes needs to coordinate with one another

Flynn’s taxonomy

The crux of parallel processing are CPUs. Based on the number of instruction and data streams that can be processed simultaneously, computing systems are classified into four major categories:

In the shared memory model (tightly coupled multiprocessor systems), all the PEs are connected to a single global memory and they all have access to it. The communication between PEs in this model takes place through the shared memory, modification of the data stored in the global memory by one PE is visible to all other PEs.

In Distributed memory machines (loosely coupled multiprocessor systems) all PEs have a local memory. The communication between PEs in this model takes place through the interconnection network (the inter process communication channel, or IPC). The network connecting PEs can be configured to tree, mesh or in accordance with the requirement.

Process vs Threads

Life Cycle of a Thread

1) New

The thread is in new state if you create an instance of Thread class but before the invocation of start() method.

2) Runnable

The thread is in runnable state after invocation of start() method, but the thread scheduler has not selected it to be the running thread.

3) Running

The thread is in running state if the thread scheduler has selected it.

4) Non-Runnable (Blocked)

This is the state when the thread is still alive, but is currently not eligible to run.

5) Terminated

A thread is in terminated or dead state when its run() method exits.

How to Create a Java Thread

Java lets you create a thread one of two ways:

• By implementing the Runnableinterface.
• By extending the Thread.

Let’s look at how both ways help in implementing the Java thread.

Runnable Interface

The easiest way to create a thread is to create a class that implements the Runnable interface.

To implement Runnable interface, a class need only implement a single method called run( ), which is declared like this:

public void run( )

Inside run( ), we will define the code that constitutes the new thread. Example:

public class MyClass implements Runnable {
      public void run(){
           System.out.println(“MyClass running”);
       } 
 }

To execute the run() method by a thread, pass an instance of MyClass to a Thread in its constructor (A constructor in Java is a block of code similar to a method that’s called when an instance of an object is created). Here is how that is done:

Thread t1 = new Thread(new MyClass ());
t1.start();

When the thread is started it will call the run() method of the MyClass instance instead of executing its own run() method. The above example would print out the text “MyClass running “.

Extending Java Thread

The second way to create a thread is to create a new class that extends Thread, then override the run() method and then to create an instance of that class. The run() method is what is executed by the thread after you call start(). Here is an example of creating a Java Thread subclass:

public class MyClass extends Thread {
      public void run(){
             System.out.println(“MyClass running”);
      }
}

To create and start the above thread:

MyClass t1 = new MyClass ();
T1.start();

When the run() method executes it will print out the text “ MyClass running “.

So far, we have been using only two threads: the main thread and one child thread. However, our program can affect as many threads as it needs. Let’s see how we can create multiple threads.

DAEMON THREAD

The Java runtime environment takes advantage of a special type of thread for background tasks. It’s called a daemon thread, where the daemon is pronounced “demon.” These support threads manage behind-the-screen tasks like garbage collection.

Daemon threads are special because if the only threads running in the VM are daemon threads, the Java runtime will shut down or exit.

Data Race

We know threads share a common memory space and when they both are trying to alter the same memory space . According to the Java Memory Model (JMM), an execution is said to contain a data race if it contains at least two conflicting accesses (reads of or writes to the same variable) that are not ordered by a happens-before (HB) relationship (two accesses to the same variable are said to be conflicting if at least one of the accesses is a write)

• Data Race is caused when multiple threads share the same variable
• At least one of them is writing
• No synchronisation

Atomic Operations

Set of instructions must be performed in as a single unit of work . Generally threads that are altering critical sections (data that is shared across threads) should be handled as a atomic operations

A critical section or critical region is part of a program that accesses a shared resource, such as a data structure memory, or an external device, and it may not operate correctly, if multiple threads concurrently access it. The critical section needs to be protected so that it only allows one thread or process to execute in it at a time.

Locks

Whenever you want to alter any critical section the thread acquires the locks does its operations and releases the locks . As only one thread can have possession of the lock at a time, so it can be used to prevent multiple threads from simultaneously accessing a shared resource,

Other Ways of handling race conditions

1. Make use of atomic variables
2. Makes use of synchronised methods or blocks : Java Objects inherently has locks associated with the objects

Types of Locks

1. ReentrantLock class implements the Lock interface. It offers the same concurrency and memory semantics, as the implicit monitor lock accessed using synchronized methods and statements, with extended capabilities. One Thread at a time (tryLock() method Whether lock is available or not )

Sometimes threads only want to read and not write any information in that case having locks is not a nice technique . Read-Write Lock comes into picture when:

1. Shared Read : Multiple threads who wants to read it simultaneously to lock it

2. Exclusive Write : only tread at a time to write on a shared resource

• Diners Philosophers Problem

Consider there are five philosophers sitting around a circular dining table. The dining table has five chopsticks and a bowl of rice in the middle as shown in the below figure.

At any instant either philosopher is thinking or eating When a philosopher wants to eat, he uses two chopsticks — one from their left and one from their right. When a philosopher wants to think, he keeps down both chopsticks at their original place.

When a philosopher wants to eat the rice, he will wait for the chopstick at his left and picks up that chopstick. Then he waits for the right chopstick to be available, and then picks it too. After eating, he puts both the chopsticks down.

But if all five philosophers are hungry simultaneously, and each of them pickup one chopstick, then a deadlock situation occurs because they will be waiting for another chopstick forever.

Deadlocks

Deadlocks are a set of blocked processes each holding a resource and waiting to acquire a resource held by another process.

Solve a deadlocks:

1. Prioritizing the locks : Lets see our example . However Lock ordering may not always be feasible as you may not know before time what locks are needed
2. Timeout on locking attempts. If a thread is not able to successfully acquire all of the locks it needs within a certain amount of time it will back up, free all of the locks that it did take, and then wait for a random amount of time before trying again to give other threads a chance to take the locks they need.

Starvation

If a thread is not granted CPU time because other threads grab it all, it is called “starvation”. The thread is “starved to death” because other threads are allowed the CPU time instead of it. The solution to starvation is called “fairness” — that all threads are fairly granted a chance to execute.

Causes of Starvation in Java

The following three common causes can lead to starvation of threads in Java:

1. Threads with high priority swallow all CPU time from threads with lower priority.
2. Threads are blocked indefinately waiting to enter a synchronized block, because other threads are constantly allowed access before it.
3. Threads waiting on an object (called wait() on it) remain waiting indefinitely because other threads are constantly awakened instead of it.