What is the most simple SPSC queue?

[segn]

Hello,

It's a long time when I was constantly working with parallel data structures. I recall one very useful queue. I think it can be defined as Wait-Free SPSC FIFO queue, but I'm unsure if there is more of 1 type of such queue?

Basically I'm looking for implementation of the same queue. In the project, the same principle was used for both thread-thread single-direction communication (typical master thread + # of worker threads; each channel is the SPSC FIFO queue), and for kernel-thread communication.

The second one was quite specific: it was using a reserved shared memory block, used as an C array in a way circular buffer is used (so: FIFO). I wrote the queue, but surprisingly I've lost memory on this :) I cannot tell if there was some index `int first_free_idx', it looks like there should be.

I think that the kernel-shared C-array nicely defines the queue, also its thread-thread variant that was using a FIFO linked-list. Could someone help me finding the queue? When I'll see it, I will now it is it.

Best regards,

segn

[segn]

W dniu czwartek, 13 grudnia 2018 07:54:14 UTC+1 użytkownik segn napisał:

Basically I'm looking for implementation of the same queue. In the project, the same principle was used for both thread-thread single-direction communication (typical master thread + # of worker threads; each channel is the SPSC FIFO queue), and for kernel-thread communication.

The second one was quite specific: it was using a reserved shared memory block, used as an C array in a way circular buffer is used (so: FIFO). I wrote the queue, but surprisingly I've lost memory on this :) I cannot tell if there was some index `int first_free_idx', it looks like there should be.

 

I've found the queue that I've used, I think that many (like me and other's from my team) programmers came up with it on their own, but here it is called Fast-Forward Queue: https://scholar.colorado.edu/cgi/viewcontent.cgi?article=1960&context=csci_techreports

segn

[Dmitry Vyukov]

Hi segn,

There is also something called FastFlow and my version that was faster
than FastFlow in my experiments:
http://www.1024cores.net/home/lock-free-algorithms/queues/fastflow