What is the most simple SPSC queue?

90 views
Skip to first unread message

segn

unread,
Dec 13, 2018, 1:54:14 AM12/13/18
to Scalable Synchronization Algorithms
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

unread,
Dec 28, 2018, 4:57:50 AM12/28/18
to Scalable Synchronization Algorithms


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

unread,
Dec 28, 2018, 7:28:19 AM12/28/18
to lock...@googlegroups.com
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
Reply all
Reply to author
Forward
0 new messages