Re: Bounded queue with non-blocking producer
Dmitriy Vyukov
wrote:
> I implemented something similar recently. It is a queue that is not
> only non-blocking but doesn't need any compare-exchange operations
> either. Being multi-producer, single consumer, it needs a single
> atomic ++ on the producer side. If there is only one producer too,
> that does not need to be atomic either and it's totally atomic-free as
> well.
>
> An array is used as a ring buffer.
> Integers R and W are indexes into the array, but here's the key: they
> always count forward and don't wrap. So, using R or W must modulo the
> array size when doing the indexing, but advancing is always a single
> increment with no compares etc.
Hi John,
Ah, I see, you effectively merge ABA-counter and element index into
single variable. That's nice trick.
> A flag in the element indicates that it is used or unused, so the
> reader can pause if the record is still being written by the
> producer.
I've implemented something similar for my agent-oriented library.
However, the queue is unbounded (external requirement). It's a linked-
list of fixed-size arrays based. I tried to get the best from both
worlds (linked-list and fixed-size array). On the array level it's
basically the same as you described - I also use "write completed
flag". However, when an array is full, I just link another array.
The problem with "lock-free" queue is that there are just too much of
them :)
Some time ago I had tried to summarize different flavors of queues:
http://origin-software.intel.com/en-us/forums/showpost.php?p=103767
There are more than 100'000 variants! (some of then are senseless, of
course :) )
> So, write "prepare" increments the counter and returns a
> reference to the record to pour stuff into, and "commit" sets the
> flag.
>
> On the read side, "prepare" will return the record, and "commit" will
> clear the flag and then increment the R counter.
>
> I didn't generalize it, but it could certainly be templatized with
> wrapping access calls like you describe.
>
> In my application, it is never full, as the number of records produced
> is limited by other aspects of the program.
But still, how do you handle queue overflow? enqueue() just returns
false? or spins?
> The read code doesn't
> block, but returns failure; it's up to the caller to block or do
> something else.
Well, it's usually application-dependent, but from my experience
consumer usually can not do anything sensible in this situation.
Consumer usually just periodically poll for new elements in this
situation. So, usually it's reasonable to handle such situation
internally.
--
Dmitriy V'jukov