Pre-requisites – Multi-threading.
What is blocking?
Blocking algorithm allows only one thread at a time to access a shared resource in a multi-threaded environment.
A resource needs to be shared among a huge number of users but only one user is allowed to use it, a user uses a thread to access the shared resource in a multithreaded environment.
Sharing a resource (data) between multiple users with the help of multithreading is the easiest and most inexpensive way but with a cost. Cost is the degradation of performance while updating the data. To read data, multiple users or threads can access the resource parallelly without any degradation of performance.
Our application is used by multiple users parallelly, so it’s running in a multi-threaded environment. To secure from race conditions, we have to use data structures like ArrayList, HashMap, ConcurrentHashMap, ArrayBlockingQueue, etc.
These data structures use blocking algorithms in which a thread from multiple threads in a multi-threaded environment gets a chance to get monitor of data structure. This exclusive monitor only gets through using a lock or synchronization.
If any thread that holds a monitor (lock) of a data structure gets stuck due to any reason then other waiting threads also get blocked. For example, Using ArrayBlockingQueue with the capacity of X values and its full. If any thread tries to put (insert a value), it’s blocked until some thread comes and fetches out the value.
What is a Non-blocking algorithm?
Non-blocking algorithm is a way to achieve concurrency without blocking any thread. Users need to access a shared resource where multiple users are looking for the same.
The non-blocking algorithm is another way of achieving the integrity of data. It means data is handled by only one thread at a single time. So, we don’t need to face race conditions.
To overcome the problems of blocking algorithms, we have data structures introduced in Java 5 that follow non-blocking algorithms and these are AtomicInteger, AtomicLong and ConcurrentLinkedQueue.
Compare and Swap (CAS):
Non-blocking algorithms in Java AtomicLong and AtomicInteger follow compare and swap.
For example, multiple threads want to update a value. Using CAS first checks the old value of the variable if matches then get the access and updates with the new value.
Reference- https://en.wikipedia.org/wiki/Compare-and-swap