[concurrency-interest] Queue quest

Stanimir Simeonoff stanimir at riflexo.com
Sun Apr 13 07:21:16 EDT 2014


Hi

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
CAS).
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.

Stanimir


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?
>
>
>
> --
> Cheers,
>>
> _______________________________________________
> Concurrency-interest mailing list
> Concurrency-interest at cs.oswego.edu
> http://cs.oswego.edu/mailman/listinfo/concurrency-interest
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs.oswego.edu/pipermail/concurrency-interest/attachments/20140413/d35e21a2/attachment.html>


More information about the Concurrency-interest mailing list