Multithreading

Good link with a plan

👍Small code snippets for many Java concurrent features

• Who is responsible for CPU sharing? => Scheduler.

  • Reasons for scheduler to pause a thread:

    • CPU should be shared equally among threads

    • Thread is waiting for data

    • Thread is waiting for another thread

Concurrent vs Parallel

• parallel - computational systems (input is known in advance)

• concurrent - event handling systems (input is unknown)

• concurrency is dealing with inevitable timing-related conflicts, parallelism is avoiding unnecessary conflicts

• computational code, as opposed to event handling code, can be made virtually bug-free rather easily, using either automated debugging tools or static guarantees.

How is "concurrent" different from "parallel" in this example?

• Concurrent present-dealing: who gets what depends on who got there first.

• Parallel present-dealing is not like that: each present is labeled, so you know who gets what.

• In the concurrent case, a queue is necessary – that's how you avoid two kids fighting over a present/two tasks corrupting a shared data structure.

• In the parallel case, a queue is not necessary. No matter who gets where first, they all end up with the right present.

• Concurrent - конкуренция. Parallel - нет конкуренции, non-intersecting, non-conflicting.

Computation vs event handling

With event handling systems such as vending machines, telephony, web servers and banks, concurrency is inherent to the problem – you must resolve inevitable conflicts between unpredictable requests. Parallelism is a part of the solution - it speeds things up, but the root of the problem is concurrency.

With computational systems such as gift boxes, graphics, computer vision and scientific computing, concurrency is not a part of the problem – you compute an output from inputs known in advance, without any external events. Parallelism is where the problems start – it speeds things up, but it can introduce bugs.

Parallelism bugs: easy to pinpoint vs impossible to define

Even if you can't read the labels, knowing that they exist is enough. If two kids fight over a box, then something is wrong and you call an adult who can read the labels.

If you're an automated debugging tool, and you don't know which task is supposed to process which data, it's enough to know that a task shouldn't access data modified by another task. If that happens, you tell the programmer, so that he properly assigns data to tasks without conflicts.

In event handling systems, a responsible adult must be much more knowledgeable to maintain discipline.

To be sure, there still is a weaker, but universal rule which always applies: you can't touch anything if someone is already busy with it. You must wait your turn in a queue. An adult can make sure this rule is followed, which is better than nothing.

How to write correct concurrent code

• Check for race conditions

  • they occur on fields (not variables / parameters)

  • 2 threads are reading / writing a given field

• Check for happens-before link

  • are read/write volatile?

  • are they synchronised?

  • if not, there is probably a bug

• Synchronised or volatile?

  • synchronised = atomicity

  • volatile = visibility

Synchronisation

Good overview of monitor

Locks are reentrant.

Variants of locks:

• Intrinsic lock for static method

// in case of public static method Singleton.class will be a lock (synchronization object)
public static synchronized Singleton getInstance() {
    ...
}

• Intrinsic lock for instance method

// in case of public method the instance of the class will be a lock (synchronization object)
public synchronized String getName() {
    ...
}

Above intrinsic locks are different:

• Acquiring the instance lock only blocks other threads from invoking a synchronized instance method; it does not block other threads from invoking an un-synchronized method, nor does it block them from invoking a static synchronized method.

• Similarly, acquiring the static lock only blocks other threads from invoking a static synchronized method; it does not block other threads from invoking an un-synchronized method, nor does it block them from invoking a synchronized instance method.

// Best option
// special object is used as lock. Always encapsulate it.
public class Person {
    private final Object key = new Object();
    
    public String init() {
        synchronized(key) {
            ...
        }
    }
}

Lock reentrancy

Synchronized blocks are reentrant in nature i.e if a thread has lock on the monitor object and if another synchronized block requires to have the lock on the same monitor object then thread can enter that code block.

public class Test{

public synchronized foo(){
    //do something
    bar();
  }

  public synchronized bar(){
    //do some more
  }
}

Another example:

public class Resource {
	public void doSomething(){
		//do some operation, DB read, write etc
	}	
	public void doLogging(){
		//logging, no need for thread safety
	}
}

// Usage of above class
public class SynchronizedLockExample implements Runnable{
	private Resource resource;
	
	public SynchronizedLockExample(Resource r){
		this.resource = r;
	}
	
	@Override
	public void run() {
		synchronized (resource) {
			resource.doSomething();
		}
		resource.doLogging();
	}
}

Now let’s see how we can use java Lock API and rewrite above program without using synchronized keyword. We will use ReentrantLock in java (this is also called unstructured lock. And lock obtained by synchronized keyword is a structured lock).

// Some code
import java.util.concurrent.TimeUnit;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;

public class ConcurrencyLockExample implements Runnable{

	private Resource resource;
	private Lock lock;
	
	public ConcurrencyLockExample(Resource r){
		this.resource = r;
		this.lock = new ReentrantLock();
	}
	
	@Override
	public void run() {
		try {
			if (lock.tryLock(10, TimeUnit.SECONDS)) {
				resource.doSomething();
			}
		} catch (InterruptedException e) {
			e.printStackTrace();
		} finally {
			//release lock
			lock.unlock();
		}
		resource.doLogging();
	}

}

As you can see, I am using tryLock() method to make sure my thread waits only for definite time and if it’s not getting the lock on object, it’s just logging and exiting. Another important point to note is the use of try-finally block to make sure lock is released even if doSomething() method call throws any exception.

👍Guava Striped Lock - compromise between having a global lock for all instances of the class (too much memory) - and having a one global lock (sequential processing of instances) - the idea is to have a set of Locks for all instances

synchronized	Java Lock
thread might end up waiting indefinitely for the lock	use tryLock() to make sure thread waits for specific time only
code is much cleaner and easy to maintain whereas	forced to have try-finally block to make sure Lock is released
	more flexible control of locking
	We can create different conditions for Lock and different thread can await() for different conditions.
	we can implement fairness: It makes sure that the longest waiting thread is given access to the lock.

ReentrantReadWriteLock

if (write lock if free) {
    MULTIPLE threads can acquire READ lock
}
if (read AND write locks are free) {
    ONE thread can aquire WRITE lock
}

Reentrant lock with condition

The Condition class provides the ability for a thread to wait for some condition to occur while executing the critical section.

This can occur when a thread acquires the access to the critical section but doesn't have the necessary condition to perform its operation. For example, a reader thread can get access to the lock of a shared queue that still doesn't have any data to consume.

Traditionally Java provides wait(), notify() and notifyAll() methods for thread intercommunication.

Conditions have similar mechanisms, but we can also specify multiple conditions:

Example of Condition usage

public class ReentrantLockWithCondition {

    Stack<String> stack = new Stack<>();
    int CAPACITY = 5;

    ReentrantLock lock = new ReentrantLock();
    Condition stackEmptyCondition = lock.newCondition();
    Condition stackFullCondition = lock.newCondition();

    public void pushToStack(String item){
        try {
            lock.lock();
            while(stack.size() == CAPACITY) {
                stackFullCondition.await();
            }
            stack.push(item);
            stackEmptyCondition.signalAll();
        } finally {
            lock.unlock();
        }
    }

    public String popFromStack() {
        try {
            lock.lock();
            while(stack.size() == 0) {
                stackEmptyCondition.await();
            }
            return stack.pop();
        } finally {
            stackFullCondition.signalAll();
            lock.unlock();
        }
    }
}

Visibility

A variable is said visible

If the writes made on it are visible

All the synchronized writes are visible

💡Visibility means "a read should return the value set by the last write".

A happens before link exists between all 💡 synchronized or volatile write operations and all 💡 synchronized or volatile read operations that follow.

// happens before link is established
int index;
void synchronized increment() {
    index++;
}
void synchronized print() {
    System.out.println(index);
}

// happens before link is established
volatile int index;
void increment() {
    index++;
}
void print() {
    System.out.println(index);
}

All shared variables should be accessed in a synchronized or a volatile way

Very good explanation of happens before by Jenkov

Good basics of Java memory model by Jenkov

False sharing

the content is HERE