The strength of blockingqueue compared to lock-free concurrentqueue without take()

0
votes

I am a beginner of multi thread programming.

I've been using Concurrent classes in a multi-threaded environment, but suddenly I was curious about using blockingqueue.

I thought Concurrent classes like ConcurrentHashMap use locking.

Recently, I happened to use QUEUE, and I looked at thread-safe queues. So I knew that there were BlockingQueue and linkedConcurrentQueue, and I studied these two queues.

The blockingqueue is thread-safe using locking. This is the typical thread-safe way I was thinking.

Concurrentqueue is processed thread-safe by using an algorithm called CAS. However, I do not know whether the target of this CAS is the queue itself or an element belonging to the queue. Even if multiple threads poll elements in concurrentqueue at the same time, are they polling different elements? Isn't there a case that polls for the same element at a time?

If so, lock-free concurrentqueue looks too good compared to blockingqueue... What is the reason that blockingqueue is still deprecate and alive? (except for take() method)

Are there any articles I would like to study or reference? Thank you!

1
multithreadinglock-free

1 Answers

1
votes

A blocking operation cannot be lock-free (and vice versa). A lock-free operation provides a progress guarantee. Here is the definition from Wikipedia:

An algorithm is lock-free if, when the program threads are run for a sufficiently long time, at least one of the threads makes progress (for some sensible definition of progress).

A thread that is blocked cannot make progress until it is "unblocked". But that usually means that some other thread must have made progress in order to unblock the blocked thread. So the blocked thread depends on some other thread's progress. In a lock-free operation this is not the case - a thread can only be prevented to make progress, if some other thread is instead making progress and thereby interferes with the first thread.

That's why a lock-free queue cannot have a blocking pop operation that blocks in case the queue is empty, waiting for some other thread to push an item. Instead they usually have a tryPop operation that indicates whether it was successful or not.

A (lock-free) Compare-And-Swap (CAS) operation can usually only be performed on a single pointer. It is one of the fundamental operations required by lock-free algorithms. In case of the ConcurrentLinkedQueue (which is an implementation of the queue proposed by Michael and Scott in Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms), the head and tail pointers are updated using CAS operations.

The topic of concurrent programming is quite vast and complex. If you are really interested, I would suggest to start with the excellent book The Art of Multiprocessor Programming.