In this tutorial we'll see what is Non-blocking algorithm and which data structures in Java are non-blocking.
In a multi-threading application if you use a lock or synchronization only one thread at any given time can get hold to the monitor and enter the critical section, all other threads wait for the lock to get free. Same way, if any data structure has to be used in a multi-threaded environment then it has to use some concurrent algorithm, if that concurrent algorithm allows only one thread at any given time and block all the others then that algorithm is a blocking algorithm. Examples- Synchronized ArrayList or HashMap, implementations of BlockingQueue interface like ArrayBlockingQueue or LinkedBlockingQueue use that kind of lock-based algorithm thus run the risk of blocking the threads (may be for ever).
If a thread holding the lock is waiting for some resource like I/O or delayed due to some other fault then other waiting threads will not make any progress. For example, If you are using an ArrayBlockingQueue, which is a bounded blocking queue, with capacity as 10. In that case if queue is full and another thread comes to put (using put() method) a value then the thread is blocked until some other thread takes (using take() method) a value out.
Non-blocking algorithm
To prevent the problems as stated above non-blocking algorithm based classes/data structures are introduced in Java starting Java 5. Some of the examples are atomic operation supporting classes like AtomicInteger, AtomicLong and Concurrent collection like ConcurrentLinkedQueue in Java.
An algorithm is called non-blocking if it doesn't block threads in such a way that only one thread has access to the data structure and all the other threads are waiting. Same way failure of any thread in a non-blocking algorithm doesn't mean failure or suspension of other threads.
Compare-And-Swap
Implementation of non-blocking data structures in Java like atomic variables or ConcurrentLinkedQueue use an atomic read-modify-write kind of instruction based on compare-and-swap.
Reference- https://en.wikipedia.org/wiki/Compare-and-swap
According to the description from "Java Concurrency in Practice" by Brian Goetz. CAS has three operands
- A memory location M on which to operate
- Expected old value OV
- New value NV
CAS will match the expected old value OV to the value stored at the memory location M, if both match then only CAS will update the memory location M to the new value NV, otherwise it does nothing. In either case, it returns the value currently in M. The variant of Compare-and-swap called compare-and-set returns a boolean value indicating success/failure of the operation. In Java classes like AtomicInteger compare-and-set method is provided.
When multiple threads attempt to update the same variable simultaneously using CAS, one of those threads wins and updates the variable's value, and the rest lose. But the losers are not punished by suspension, as they could be if they failed to acquire a lock; instead, they are told that they didn't win the race this time but can try again.
Because a thread that loses a CAS is not blocked, it can decide whether it wants to
- try again,
- take some other recovery action, or
- do nothing
As example- At memory location M current value stored is 5, CAS is called by one thread with expected old value as 5 and new value as 6. At the same time another thread tries to change the value at M by passing 6 as old value and 7 as new value.
In that case first thread will succeed in changing the value stored at M to 6 whereas the other thread will report failure as matching for it will fail.
So the point is that threads are not blocked they may fail to get the desired result and may have to call CAS in a loop to get the result, which will result in more CPU cycles but no blocking/failure of threads because one of the thread has acquired lock and not releasing it.
That's all for this topic Non-Blocking Algorithms in Java. If you have any doubt or any suggestions to make please drop a comment. Thanks!
Related Topics
You may also like-