Non-blocking algorithms in the context of concurrency are algorithms that allows threads to access shared state (or otherwise collaborate or communicate) without blocking the threads involved. In more general terms, an algorithm is said to be non-blocking if the suspension of one thread cannot lead to the suspension of other threads involved in the algorithm.
Blocking Concurrency Algorithms
A blocking concurrency algorithm is an algorithm which either:
- A: Performs the action requested by the thread - OR
- B: Blocks the thread until the action can be performed safely
Many types of algorithms and concurrent data structures are blocking. For instance, the different implementations of thejava.util.concurrent.BlockingQueueinterface are all blocking data structures. If a thread attempts to insert an element into aBlockingQueueand the queue does not have space, the inserting thread is blocked (suspended) until theBlockingQueuehas space for the new element.
Non-blocking Concurrency Algorithms
A non-blocking concurrency algorithm is an algorithm which either:
- A: Performs the action requested by the thread - OR
- B: Notifies the requesting thread that the action could not be performed
Java contains several non-blocking data structures too. TheAtomicBoolean,AtomicInteger,AtomicLongandAtomicReferenceare all examples of non-blocking data structures.
Non-blocking vs Blocking Algorithms
The main difference between blocking and non-blocking algorithms lies in the second step of their behaviour as described in the above two sections. In other words, the difference lies in what the blocking and non-blocking algorithms do when the requested action cannot be performed:
Blocking algorithms block the thread until the requested action can be performed. Non-blocking algorithms notify the thread requesting the action that the action cannot be performed.
Volatile variables are non-blocking.