Concurrent Programming Review

Process and Thread

The process is self-contained. It doesn't share the resource with others. A thread is a minimal execution unit, living inside a process. One process may consist of many threads. Threads may share a common resource with each other.

Volatile: Solving the visibility issue between threads.

Each Thread has its own local cache, so the variable defined in a thread won't be visible by another thread. When using Volatile keyword to modify a variable, the OS will push the variable into the shared cache(among the threads), thus it becomes visible to all other threads.

Volatile provides visibilities between isolated threads, however it doesn't provide an atomic protection from multiple step operation(read-modification-write).

Concurrent and Parallel computing 

Concurrent computing task can be decomposed into sub-tasks, which are order-independent.  These sub-tasks are carried out at the same core but different threads. Form an external view, it seems that these tasks are carried out simultaneously, but actually not.

Parallel computing needs parallel computing hardware first, i.e. having more than one core. The computing task is carried out in independent cores simultaneously.  

Mutex

Mutex means mutual exclusion is the way to solve the data race. At any time, only one thread is allowed to access the shared data. 

Data race: 

Simultaneously multiple threads access a common memory location.  The data stored there may be not consistent and being polluted. Ideally,  all steps should be carried out in a single uninterruptible operation, so as to prevent data from pollution. 

Lock: 

Two types of locks, i.e. extrinsic or intrinsic lock.

An extrinsic lock is explicitly declared from Lock interface and its implementations. A critical section is protected by an explicit lock and afterwards, the lock is unlocked.

Synchronization: 

Two types of synchronization, i.e. synchronization method or synchronization statements.

Every Java class or object has an intrinsic lock associated with it. The intrinsic lock must be achieved first, so as to access the synchronized method or statements.

Note: ➀watching out Synchronizing on the class or instance; ➁ don't synchronize on an immutable object, for it generates a new instance after its value being modified.

Atomic variables:

The most commonly used atomic variable classes in Java are AtomicInteger, AtomicLong, AtomicBoolean, and AtomicReference. These classes represent an int, long, boolean and object reference respectively which can be atomically updated.

For instance, AtomicInteger provides a method incrementAndGet(), it is not synchronized, but it offers
atomicity guarantees by using Low-level compare-and-set(CAS) instruction. 

Try Lock:

The tryLock method offers a non-blocking way to acquire the lock(explicit lock), so as to improve performance.

When a thread wants to acquire the lock, but not available, it may go away to carry out some other tasks, rather than being blocked and waiting there. This is the purpose to have 'try lock' method.

Read-write lock:

Instead of locking the resource to both read and write operations equally. A read-write lock is distinguished into a two-part lock, i.e. a read-alone lock and a write-alone lock. By this way, it may improve the performance. By this way, it allows multiple threads to read the shared resources simultaneously, for reading doesn't cause data race. It allows a single thread to write on the shared resource at a moment. This type of lock may be used when the number of reading threads is much bigger than the number of writing thread.

Note: read-write lock may use more resource under the hood.

Liveness

Deadlock:

Resource A and its Lock A; Resource B and its Lock B. Thread A hold Lock A, while Thread b hold Lock B.  Thread A acquires Lock B, while thread B acquires Lock A. 

How to prevent threads from deadlock?
lock priority: multiple threads acquire locks in a fixed order.
lock timeout: if cannot acquire, then quit.

Abandoned lock: 

when one thread acquired the lock, but it fails to unlock it due to exceptions. The lock is therefore abandoned. This may lead to the rest of the threads in stuck.

How to prevent a lock becoming abandoned?

using try-catch block to surround the critical section, and in the 'finally' block unlock the lock.

Starvation:

Starvation happens when a thread is perpetually denied resources due to competition with others. A thread may in starvation because it has a low priority. Or it simply because there are too many concurrent threads.

Livelock: 

Multiple threads are designed to respond to each other so as to solve the conflict.

To solve the livelock, making sure only one thread takes action. It may take use of random selection.

Explicit Lock vs Implicit Lock

Explicit locks, such as those provided by the java.util.concurrent.locks package (e.g., ReentrantLock, ReadWriteLock), offer several advantages over using intrinsic locks provided by synchronized blocks or methods. Some of the key benefits of using explicit locks are:

1. Flexibility: Explicit locks offer more flexibility in terms of lock acquisition and release. You can lock and unlock the lock object at different scopes and in separate blocks of code, which is not possible with synchronized blocks or methods.

2. Fairness: ReentrantLock allows you to specify fairness when creating the lock object. When a lock is fair, it grants access to the longest-waiting thread. Intrinsic locks provided by synchronized blocks or methods do not have a fairness option and may lead to thread starvation in some scenarios.

java
Lock lock = new ReentrantLock(true); // Create a fair lock

3. Try to acquire lock: Explicit locks provide the tryLock() method, which allows a thread to attempt to acquire the lock without waiting indefinitely. This can help avoid deadlocks and improve performance in some cases.

java
if (lock.tryLock()) {
    try {
        // Perform the operation
    } finally {
        lock.unlock();
    }
} else {
    // Handle the lock not being acquired
}

4. Interruptible lock acquisition: With explicit locks, you can use the lockInterruptibly() method, which allows a thread to be interrupted while waiting to acquire the lock. Intrinsic locks do not support this functionality.

java
try {
    lock.lockInterruptibly();
    try {
        // Perform the operation
    } finally {
        lock.unlock();
    }
} catch (InterruptedException e) {
    // Handle the interruption
}

5. Separate read and write locks: The ReadWriteLock interface provides separate locks for read and write operations, allowing multiple threads to read shared data simultaneously while still providing exclusive access for write operations. This can lead to better performance in scenarios with more reads than writes.

java
ReadWriteLock rwLock = new ReentrantReadWriteLock();
Lock readLock = rwLock.readLock();
Lock writeLock = rwLock.writeLock();

While explicit locks offer several advantages, they also require more careful handling and can be more error-prone due to the need for manual lock management. When choosing between explicit locks and intrinsic locks, consider the specific use case, the complexity of the code, and the required functionality. 

Optimistic Lock, Concurrent timestamp

Optimistic concurrency control (OCC) is a concurrency control method applied to transactional systems such as relational database management systems and software transactional memory. OCC assumes that multiple transactions can frequently complete without interfering with each other. While running, transactions use data resources without acquiring locks on those resources. Before committing, each transaction verifies that no other transaction has modified the data it has read. If the check reveals conflicting modifications, the committing transaction rolls back and can be restarted.[1] Optimistic concurrency control was first proposed by H. T. Kung and John T. Robinson.[2]

Setting a time-stamp in a table as a column to store the entry recorded moment; in a transaction, the values are read along with the timestamp, and after operations on these values, at the moment write back newly modified values, the transaction needs to compare the previous timestamp with the current ones recorded at the Current-timestamp cell, if they are the same, then the data is consistent until now; otherwise, the transaction needs to roll back and repeating the previous the process. 

Thread Pool

Thread pool is a solution to limit the number of threads in usage, and so as to avoid the lower performance and system crash due to resource exhaustion.  

A thread pool is a group of pre-instantiated, idle threads that stand ready to be given work. Using a thread pool gives a better performance than creating a new thread for each task. It uses existing thread first, only having no existing available, then creating a new thread.

ExecutorService extends Executor

ScheduleExecutorService extends ExecutorService

ExecutorService manages to submit tasks much better than Executor. It accepts both Runnable and Callable.

ScheduleExecutorService manages to submit tasks and run in planned time slices.

ExecutorService offer APIs 

'IsTerminated()': testing if all submitted tasks having been accomplished.

'IsShutDown()': testing if the executor is shut down. 

'shutDownNow' means that attempting to halt active running threads, and stop picking up tasks from the queue, and returning un-implemented tasks in a collection. 'shutDownNow' is more like shutting down at once.

'shutDown' means executing previously accepted tasks, but no more task accepted; if you do add one after it; it won't give a compiling error, but a run-time exception, i.e. java.util.concurrent.RejectedExecutionException

Through ExecutorSerive, the client may submit Runnable or callable to the thread pool.

Executor consists of a queue and a pool.

Pool types: fixed-sized, single thread, scheduled thread pool, cached thread pool

The 'Executors' is a factory, where a client achieve a specific type of thread pool.

       ExecutorService es = Executors.newCachedThreadPool();

        es.execute(new PrintChar(10, 'a'));
        es.execute(new PrintNum(10, 66));
        es.execute(new PrintNum(10, 20));
        es.shutdown();

Threads

Concept of Thread 

The thread is a lightweight process, making good use of multiple cores and slices of CPU time, running several tasks simultaneously. 

Difference Between Process and Thread: 
Different processes cannot share a common memory space(variables and data object), but threads share variables (static and instance) and data objects.

The above leads to the major issue due to concurrent modification on shared variables and data objects, i.e. how to safeguard shared data and read them out consistently.

Defining a Task

Declaring a new runnable class by implementing a runnable interface, 

class DataSaver implements Runnable{
@override
public void run(){......}
}

Thread is allowed to be extended to run an expected task in this thread; however, this will mix the thread and task together. So this pattern is not suggested.

class UploadFile extends thread{
@override
public void run(){ .....}
}

Thread implements the Runnable interface. So a thread is runnable, which can be contained in a thread, and being put in a JVM.

 //creating a new thread instance.
Thread t = new Thread(new UploadFile());

//executing a thread
t.start();

End of Thread
When run() has been accomplished, then the thread is at the end of execution. Don't use the deprecated method stop() to stop a thread run(). 

When stopping a thread, just point the thread to null.

Thread Life Cycle

A thread life cycle contains states, i.e. NEW, RUNNABLE, TERMINATED, WAITING, TIMED-WAITING, BLOCKED, where RUNNABLE consists of two states, i.e. READY, and RUNNING. 

NEW:  a thread is created, but not started yet.

RUNNABLE:(READY or RUNNING) a thread is executed in JVM

BLOCKED: a thread is blocked and waiting for a monitor lock.

WAITING: a thread waiting for another thread to perform a particular action. 

TIMED_WAITING: a thread waiting for another to perform a particular action for a specified time.

TERMINATED: a thread's run method having been accomplished;

Thread Scheduler:
It depends upon the underlying OS. Scheduler decides when to pick up a thread and make it running in JVM, but not a developer. So a thread running may feel like randomly.

When a thread start() method is called, it moves a thread from NEW to RUNNABLE_READY. The underlying scheduler moves a thread from READY to RUNNING, vice versa. Even we set a thread as the highest priority, it won't guarantee to make it running at once. The thread scheduler may ignore the thread that having the highest priority. In some sense, threads run randomly. When a thread runs out a sliced time of CPU, the thread scheduler may suspend this thread until a next time slice available.

Thread Static Methods:
Yield(): it is not guaranteed. It makes a current thread to give up its CPU time.
Sleep(): it is guaranteed to move the current thread from RUNNING to READY for a specific period.

currentThread(): get current thread. 

Thread Instance Methods:
Join():  making invoker's thread waiting the invoked thread until it accomplishes run body, thus invoker proceed to accomplish its own. Join() throws unchecked InterruptedException.

interrupt(): making invoker to ask the invoked thread to terminate. 

Object Instance Methods:
Wait(): pause Object's execution and wait for another object, i.e. moving to the READY state
Notify(): waking up one waiting thread back to RUNNABLE.
NotifyAll(): waking up all waiting threads back to RUNNABLE.

wait(), notify, and notifyAll() must be called in a synchronized method or code block; or an IllegalMonitorStateException will be thrown.

How to Protect Data and Object Shared by Thread
Unlike the regular process, threads are lightweight processes. They share certain memory areas. When multiple threads access common data variable or objects, we need to consider how to keep their states consistent. You may protect your shared data by (1) restrict it accessible only to one thread at one moment; (2) make objects immutable  (3) declaring volatile variables.

How an object is protected? 
Using a keyword 'synchronized' to achieve an object's lock. Each Java object is associated with a monitor, which can be a lock or unlocked by a thread. And, only one thread can hold its lock. By this way, the object can be read or write by one thread, so that the data cannot be polluted.  When this thread carried out a read or write, it releases the lock. Other threads, therefore, may acquire the lock and access the data object.

In JAVA, a 'synchronized' keyword can be used to modify a method or a statement block.
A 'synchronized' instance method refers to the lock of the class instance.
A 'synchronized' static method refers to the lock of the class.
Using the 'synchronized' method may reduce performance, for several static methods share a common instance or class lock.

Or: instead of using a synchronized method, using a synchronized block within a method. It may avoid the performance issue due to the 'synchronized' method. Synchronized blocks may refer to their own instance locks. So they won't have performance issues due to sharing a common lock like using synchronized methods.

How to make an object immutable? 
An immutable data object cannot result in inconsistency, for it cannot be modified externally.
(1) making a class final, so that it cannot be extended and added extra methods to modify fields.
(2) making fields private and final, so that once it is initialized then it cannot be modified later on.
(3) removing all setters.
(4) return a cloned protected field, thus its existing value cannot be modified via its exposed reference
(5) if immutable class hold a mutable class; using a cloned copy of the class from the constructor.
(6) making methods final, thus no method can be overridden.  so that, an existing protected field cannot be modified in overriding methods.

What are volatile variables?
All writes to the volatile variables will be written back to main memory immediately.  All reads to the volatile variables will be directly read from main memory, rather than local CPU caches.

The 'Volatile' keyword has a limitation: the variable must have no dependency on its previous state. in a short, it must be atomic. For example, if the variable x = x+1, the Volatile keyword won't work. In my understanding, it works when only need to share a flag variable or just value, like a boolean variable, or a number.

What is atomicity or atomic?
We often use this term atomic.  Atomicity, it means an indivisible unit, like a transaction. it may keep data consistent. All operations on a data object or variable in the memory are carried out in an enclosed and un-interweaved process. Just like you are seating in an enclosed space alone and accomplish all your homework without any interruption.

What is a happens-before relationship? 
it means A must happens before B.

What is deadlock?
Deadlock is a situation, where Thread A is allocated resource R1; meanwhile, thread B is allocated resource R2.

In order to continue their own transaction respectively, thread A asks for R2 and simultaneously thread B asks for R1.

On such a situation, both threads will wait for each other forever.

What is Livelock?
Both thread A and thread B asking for the same lock at the same time. This is exactly like the case when we both call each other at the same via phone, so cannot make the call.