I've found several implementations for single producer-single consumer, but none for multiple producer-single consumer.
Does a lock-free queue for "multiple producers-single consumer" exist for Delphi?
views:
1571answers:
4+1. Note that an alternative to this has to be implemented if the applications need to work on pre-XP Windows systems. Note also that there's no easy way to have the consumer block on an empty queue.
mghie
2009-07-05 13:52:58
The SList functions generate a stack, not a queue.
Rob Kennedy
2009-07-05 17:56:42
@Rob Kennedy: Not entirely true, if the consumer uses InterlockedFlushSList() instead of InterlockedPopEntrySList() it is free to process the list items in both directions.
mghie
2009-07-05 19:34:05
Adisak
2010-09-30 02:59:50
+1
A:
http://svn.berlios.de/svnroot/repos/dzchart/utilities/dzLib/trunk/lockfree/
@Daniele Teti:
The reader must wait for all writers who still have access to the old queue to exit the Enqueue method. Since the first thing the reader does in the Dequeue method is providing a new queue for new writers which enter Enqueue it should not take long for all writers that have a reference to the old queue to exit Enqueue. But you are right: It is lock free only for the writers but might still require the reader thread to wait for some writers to exit Enqueue.
dummzeuch
2009-07-05 18:47:10
I'm tring this list but... code comments are strange for a "LockFree" list:" // Unfortunately it is possible that other threads still hold a // reference to the old queue. // To be 100% sure we need to wait until the ActiveWriters count // drops to 0 // If there currently are writers, we wait for the event // which will be set by the first writer that decrements // ActiveWriters to 0. If there aren't, no need to wait."This seems like a kind of "wait" sinchronization... I'm wrong?(I'm found this comments inside function TMultiWriteSingleReadLockFreeQueue.Dequeue)
Daniele Teti
2009-07-06 12:47:48
+2
A:
Lock-free queue from the OmniThreadLibrary supports multiple producers. You can use it separately from the threading library (i.e. you can use OtlContainers unit in any other framework).
As the Daniele pointed below, there are two queues in the OmniThreadLibrary. The one in the OtlContainers supports multiple producers and multiple consumers while the "smarter" version in OtlComm (which is just a wrapper for the simpler version) is only single producer/single consumer.
Documentation is still a big problem of the OmniThreadLibrary project :(. Some information on the queue can be found here .
gabr
2009-07-05 19:36:04
Really? I used your List but in the source code the is a "sad" comment for me..."{:Lock-free, single writer, single reader ring buffer. } IOmniQueue = interface ['{AE6454A2-CDB4-43EE-9F1B-5A7307593EE9}']"You say that OmniQueue is MULTI producers, Single consumer enabled?
Daniele Teti
2009-07-05 21:48:31
Sorry, my mistake. "High-level" queue in OtlComm is single producer/single consumer. "Low-level" queue in OtlContainers is multiple producer/multiple consumers. So you have to use the simpler variant of the queue object if you want to use multiple producers.I fixed the text above to refer to the correct unit name.
gabr
2009-07-06 07:10:03
+1
A:
For a multiple-producer / single-consumer Queue/FIFO, you can easily make one LockFree using SLIST or a trivial Lock Free LIFO stack. What you do is have a second "private" stack for the consumer (which can also be done as a SLIST for simplicity or any other stack model you choose). The consumer pops items off the private stack. Whenever the private LIFO is exhasted, you do a Flush rather than Pop off the shared concurrent SLIST (grabbing the entire SLIST chain) and then walk the Flushed list in-order pushing items onto the private stack.
That works for single-producer / single-consumer and for multiple-producer / single-consumer.
However, it does not work for multiple-producer / multiple-consumer cases.
Adisak
2009-10-09 16:11:24