Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Lock-free Multi-producer Multi-consumer Queue on Ring Buffer

natsys-lab.blogspot.ru

Post reply on HN
Print view View original

1–10 of 20 posts

Re: Lock-free Multi-producer Multi-consumer Queue on Ring Buffer

#3

Post by NLPsajeeth »

coldcode wrote: post #2

The subject might be interesting but the formatting of the article is horrible. Is it that difficult to remove the line terminators at the end of each line so that you get actual paragraphs?

You may prefer this version of the article which is better formatted but split across multiple pages: http://www.linuxjournal.com/content/lock-free-multi-producer...

Re: Lock-free Multi-producer Multi-consumer Queue on Ring Buffer

#5

Post by colanderman »

Note that "lock-free" doesn't mean "doesn't use mutexes"; it means "at least one consumer/producer will always make progress". (Any algorithm using locks fails this test, as one stubborn consumer/producer can hold up the entire system.) The article doesn't seem to really touch on this property at all (although at first glance the algorithm does appear to be lock-free).

Re: Lock-free Multi-producer Multi-consumer Queue on Ring Buffer

#7

Post by nano_o »

I'm a bit skeptical about the code: it seems that it's using only the atomic fetch-and-add synchronization instruction, and not compare-and-swap. However, I think that whether queues are implementable with only fetch-and-add is an open problem in distributed computing (in technical terms, whether queues are in the Common2 family. See for example Afek et al., "Common2 Extended to Stacks and Unbounded Concurrency".)

Re: Lock-free Multi-producer Multi-consumer Queue on Ring Buffer

#8

Post by eloff »

nano_o wrote: post #7

I'm a bit skeptical about the code: it seems that it's using only the atomic fetch-and-add synchronization instruction, and not compare-and-swap. However, I think that whether queues are implementable with only fetch-and-add is an open problem in distributed computing (in technical terms, whether queues are in the Common2 family. See for example Afek et al., "Common2 Extended to Stacks and Unbounded Concurrency".)

I've seen many queues implemented similarly to this, and it works fine. Every thread that calls fetch and add receives a different result, therefore, wrapping asside, there can only be one thread with access to each slot. If there is only one consumer and one producer you don't need fetch and add at all (that is how fastflow is implemented.) You must check that your slot is populated by either comparing with the other index (producer if your the consumer), which is stupid because that cache line is highly contended. The better way is set a slot to null after you've consumed it, and if your the producer, you first check if the current slot is null before attempting to increment the index. A race condition exists where the slot can be null before incrementing but not afterward (e.g. only one slot free but several producers saw that and incremented.) In reality all that means is the producer can skip slots and the consumer must keep incrementing if it sees a null slot rather than assume an empty queue (can be tempered by checking x slots and then falling back to checking the producer index.) Consumer and producer indexes must be on seperate cache lines and some effort can be made to keep consumer and producer on sperate cache lines in the actual queue. e.g. each slot can be a whole cache line and pop() and push() can be batched to work with 8 elements at a time. In other words OP is a noob and I could write a queue that whoops his hiney (danger: attempt at humor.)

Re: Lock-free Multi-producer Multi-consumer Queue on Ring Buffer

#9

Post by nano_o »

eloff wrote: post #8
nano_o wrote: post #7

I'm a bit skeptical about the code: it seems that it's using only the atomic fetch-and-add synchronization instruction, and not compare-and-swap. However, I think that whether queues are implementable with only fetch-and-add is an open problem in distributed computing (in technical terms, whether queues are in the Common2 family. See for example Afek et al., "Common2 Extended to Stacks and Unbounded Concurrency".)

I've seen many queues implemented similarly to this, and it works fine. Every thread that calls fetch and add receives a different result, therefore, wrapping asside, there can only be one thread with access to each slot. If there is only one consumer and one producer you don't need fetch and add at all (that is how fastflow is implemented.) You must check that your slot is populated by either comparing with the othe…

Ok, so it is relatively easy to obtain a safe implementation and from there you can use a heuristic to prevent a thread from looping forever trying to find an available slot. Would that sum up the issue in practice?

Re: Lock-free Multi-producer Multi-consumer Queue on Ring Buffer

#10

Post by eloff »

nano_o wrote: post #9
eloff wrote: post #8

Earlier quoted context omitted.

I've seen many queues implemented similarly to this, and it works fine. Every thread that calls fetch and add receives a different result, therefore, wrapping asside, there can only be one thread with access to each slot. If there is only one consumer and one producer you don't need fetch and add at all (that is how fastflow is implemented.) You must check that your slot is populated by either comparing with the othe…

Ok, so it is relatively easy to obtain a safe implementation and from there you can use a heuristic to prevent a thread from looping forever trying to find an available slot. Would that sum up the issue in practice?

I'd rephrase that as it's easy to create a safe implementation, but the dangers and biggest payoffs are realized when you don't access both producer and consumer counters in the same thread all the time. cache lines shared between the consumer and producer and written to by at least one of them are the hottest points of contention. With careful design you can get that to zero in the common cases.
Post reply on HN