How to implement a lock free shared memory queue？

[小菜]

How to implement a lock free shared memory queue？

[Haddock]

I'm not exactly sure whether I understand what you are looking for. If I get you right it would be helpful to look at class TransferQueue in Java8. It is entirely based on CAS and has very good throughput.

[Péter Szilágyi]

Hello,

The basic building block would be inserting and removing elements lock freely in a single array, then you could work your way to circular buffers and perhaps automatically scaling buffers.

You need to maintain 2 indexes: one for the latest read (past tense) position, one for the latest written position. When you want to add a new element to the queue, you atomically increment the writer index, and you got your position where to insert the new thing. To read an element, you atomically increment the reader, and read whatever there is (if you passed the writer index (load read index first, then write index), then you decrement the reader and retry until you succeed).

This is a spin-lock solution, so it will probably kill your CPU if the producers/consumers are not of the same speed (also Go will hog your thread). To prevent resource exhaustion, you'll need to add some mechanism to back off after some failed read attempts, and either sleep a bit, or desirably fall back to a lock.

Of course, for every added feature, you code will get significantly more complicated :) But it's a nice concurrency exercise :D

Cheers,

  Peter

--
You received this message because you are subscribed to the Google Groups "golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Dmitry Vyukov]

On Wed, Jan 28, 2015 at 11:40 AM, Péter Szilágyi <pet...@gmail.com> wrote:
> Hello,
>
> The basic building block would be inserting and removing elements lock
> freely in a single array, then you could work your way to circular buffers
> and perhaps automatically scaling buffers.
>
> You need to maintain 2 indexes: one for the latest read (past tense)
> position, one for the latest written position. When you want to add a new
> element to the queue, you atomically increment the writer index, and you got
> your position where to insert the new thing.

And what if writer has incremented write pos but has not yet written
the data (or worse partially written it)? Reader thinks that the slot
is already ready to be consumed and reads partially overwritten
garbage...

[Péter Szilágyi]

Hmm, indeed, nice catch :), then you'll need two watermarks, a low for the safe to read positions and a hi for the safe to write positions.  And things get further complicated :) It's still a nice thought experiment (p.s. I'm sure there are other issues too, so yes, it's not a trivial thing to do, but my post was rather meant as a starting point, definitely not a solution) :)

[Dmitry Vyukov]

On Wed, Jan 28, 2015 at 11:50 AM, Péter Szilágyi <pet...@gmail.com> wrote:
> Hmm, indeed, nice catch :), then you'll need two watermarks, a low for the
> safe to read positions and a hi for the safe to write positions. And things

Even if you get it right (newer writer can finish writing ahead of an
old writer!), it is not lock-free anymore. If a writer is terminated
in the middle of write operation, then the queue becomes broken.