[concurrency-interest] Queue quest
stanimir at riflexo.com
Sun Apr 13 07:21:16 EDT 2014
A classic concurrent Michael & Scott queue where nodes do contain an extra
field 'long counter' should be able to suffice - bounded,
non-constant-space and lock-free (still need to spin to insert on failed
The field is initialized with the value of the tail.counter+1 and the queue
tail cannot drift unlike CLQ implementation. So the queuing routine first
CAS the tail then links the 'next'.
The size of the queue is obviously tail.counter-head.counter.
Due to having only a single consumer the notification mechanism requires
only one padded AtomicReference<Thread> + park/unpark. The only harder part
is making consumers effectively wait on full queue and they may need to
rely on spin + Thread.yield.
I can post a short implementation under CC0 if interested.
On Tue, Apr 8, 2014 at 4:38 PM, √iktor Ҡlang <viktor.klang at gmail.com> wrote:
> Hey everyone,
> I thought I'd throw this question out there before I go all out NIH.
> Does anybody know of an open source (apache 2 compatible) "minimal
> overhead", non-blocking, bounded, non-constant-space (i.e. no ringbuffer or
> preallocated size array) multiple-producer
> single-consumer/multiple-consumer queues in Java/bytecode?
> Concurrency-interest mailing list
> Concurrency-interest at cs.oswego.edu
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the Concurrency-interest