6 ms·
Writing Lock-Free Code: A Corrected Queue
- nkron 14y agoThe follow up article in case anyone wanted to read it: http://www.drdobbs.com/parallel/writing-a-generalized-concurrent-queue/211601363 http://www.drdobbs.com/parallel/writing-a-generalized-concur...
- abcd_f 14y agoAs a single page - http://www.drdobbs.com/article/print?articleId=211601363&siteSectionName=parallel http://www.drdobbs.com/article/print?articleId=211601363&...
- chj 14y agoSometimes the producer has to insert something in the middle of the queue, is it possible to make this queue lock free?
- ams6110 14y agoIt's not really a queue then, is it?
- spenczar5 14y agoSure it is. Priority queues are a common example of this behavior, and they're still queues. chj's question is interesting. It's not obvious how to build a lock-free code in the original article's framework if you aren't representing your queue as a list, but many queues are not represented this way. If you need this 'insert in the middle of the queue' operation, you probably aren't representing your queue as with a linked list since insertion will be inefficient - chances are you're using a heap.
- NeutronBoy 14y agoYou could maintain separate queues for each priority, and always process them from the top down.
- chj 14y agoOK, now I guess event queue can also be lock free. Use one lock free queue as the article described for incoming events from the producer, and another queue with the event sorted by the consumer.
- chj 14y agoThis sounds great for priority queues. But how about an event queue, where every event has a time tag?
- tantaman 14y agoJava's ConcurrentLinkedQueue is lock free and supports any number of readers and writers. For those that are interested: http://fuseyism.com/classpath/doc/java/util/concurrent/ConcurrentLinkedQueue-source.html http://fuseyism.com/classpath/doc/java/util/concurrent/Concu... And the original research: http://www.cs.rochester.edu/u/michael/PODC96.html http://www.cs.rochester.edu/u/michael/PODC96.html
- rdtsc 14y agoI have used this library http://www.liblfds.org/ http://www.liblfds.org/ for lock-free data structures successfully. Only used the queue but it also has a linked-list (logical deletion only), stack and a ring buffer. There is another library others are using but can't remember the name currently.
- sbahra 14y agoPlease note that the code in this article is broken. It lacks proper use of atomics, memory barriers, let alone compiler barriers. You can find a similar and correct queue at http://concurrencykit.org http://concurrencykit.org (ck_fifo.h). The liblfds queue is very heavy-weight for a simple SPSC workload and is also lacking in correctness. If you're looking for a learning resource, I suggest looking at http://www.rdrop.com/users/paulmck/perfbook/ http://www.rdrop.com/users/paulmck/perfbook/ and http://1024cores.net http://1024cores.net
- frankzinger 14y agoCare to point us to a link explaining why the code in the article is incorrect? And I am sure it would help many people if you would post the link in a comment under the source article as well. I would love to hear what the author has to say too.
- sbahra 14y agoYou could also compare it to ck_fifo_spsc in the above link (look at include/ck_fifo.h).
- frankzinger 14y agoHaha, good one! Seriously, what exactly is wrong with Sutter's implementation? I am truly interested because I respect him a lot.
- sbahra 14y agoYou asked for a link to an explanation, I do not have a link to the explanation. I'm not sure what you found funny about referring you to a 30/50-line piece of source-code with an implementation for your own comparison. Also, people make mistakes, what does your respect for the author have to do with anything? Regardless, I will elaborate. General issues: "If you don't yet have ordered atomic variables yet on your language and platform, you can emulate them by using ordinary but aligned variables whose reads and writes are guaranteed to be naturally atomic, and enforce ordering by using either platform-specific ordered API calls (such as Win32's InterlockedCompareExchange for compare-and-swap) or platform-specific explicit memory fences/barriers (for example, Linux mb)." This is incorrect. A lot of memory models in languages provide no such guarantees, even of aligned variables (this includes C, even with volatile variables). This not only applies to regular loads/stores but even to RMW. Produce/Consume function: We store to last->next and then to last. If we assume total store ordering, insertion itself is fine. However, it should be made clear that an explicit store fence is needed after updating the next pointer. The article gives the impression (due to statement above) that this algorithm is suitable for other languages. In the consumer, we also need an explicit load fence. If the atomic is completely serializing, we are fine but in other languages even with aligned variables, these semantics are incorrect. The "trim" functionality is broken as it makes no use of safe memory reclamation. It is fine to re-use nodes (assuming you don't have a concurrent lock-free traversal going on) but you need to be careful with destruction. Assume consumer is at some time T where divider != last (but divider = first). Let us say consumer is at result = divider->next->value. Pause execution of consumer after it has acquired divider->next. Producer enqueues another node and sees that first != divider (yet consumer has an earlier snapshot of divider), so it trims first. Consumer is now active again and dereferences the earlier snapshot it had of divider->next to get to value, but now this yields undefined behavior (crash or worse).
- deleted 14y ago[deleted]