Is there a bounded lock-free blocking queue?

user_3234979 0
Viewed 1657

Currently we have LinkedBlockingQueue and ConcurrentLinkedQueue.

LinkedBlockingQueue can be bounded, but it uses locks.

ConcurrentLinkedQueue doesn't use locks, but it is not bounded. And it is doesn't block which makes it hard to poll.

Obviously I can't have a queue that both blocks and is lock-free (wait-free or non-blocking or something else). I don't ask for academical definitions.

Does anyone know a queue implementation that is mostly lock-free (doesn't use a lock in the hot path), blocks when empty (no need to busy waiting), and is bounded (blocking when full)? Off-heap solution is welcome as well.

I heard about LMAX Disruptor, but it doesn't look like a queue at all.

I am happy to know non-general solutions too (Single-Producer-Single-Consumer, SPMC, MPSC)

If there are no known implementations, I am also happy to know possible algorithms.

concurrency java
1 Answers

The lock-free data structures use atomic reads and writes (e.g. compare-and-swap) to eliminate the need for locks. Naturally, these data structures never blocks.

What you describe is a queue that uses lock-free mechanisms for non-blocking calls, e.g. remove() with non-empty queue, while uses lock to block for e.g. remove() on empty queue.

As you might realize this is not possible to implement. If, for example, you were to after a pop operation, see if the queue was in fact empty and then proceed to block, by the time you block, the queue might already have one or more items inserted by another thread.

user_3634370
Related