Fober et al Lock-Free FIFO Queue: multiple consumers and producers?

Question

Hi,

I was wondering if the fifo queue presented in Fober et al's paper http://nedko.arnaudov.name/soft/L17_Fober.pdf was a multiple consumer and produce fifo queue. If not, which is the best documented multiple consumer and producer FIFO queue?

Thanks

Answer 1

I don't know the "Fober queue" but have already written lock-free FIFOs as ring buffers. What is possible relatively easily is a "inter-lock free" queue which means that readers do not block writers and vice versa but multiple readers must be serialized and multple writers must be too. So it is not exactly lock-free but still there is no locking/blocking between the readers and writers.

Maybe there are even better approaches that allow even less locking but maybe this will already help you.

Answer 2

I haven't read the paper but I am making a big assumption here: The paper uses the CAS (compare and swap) technique to achieve the concurrency.

Lock free does not mean block free. The use of CAS will stall other threads, but at least one thread will be moving 'forwards' at all times.

Multiple producers all write to the same queue - that isn't a problem. The trickiness is the multiple consumers. If every consumer must access the data then I would implement that by multiple queues and the data would fall through to the next queue after being processed in one. If you mean multiple consumers via threads then that would work on the above method

Answer 3

yes. read section '3.1 Linearizability' the pop operation assumes that concurrent dequeue might happen. This means that multiple threads will be able to consume the queue.