1

I ve been googling quite a bit for a lock-free queue in C/C++.But most of them must specified maximum number of elements, include boost::lockfree.

Could anyone give me some information about the variable length and multiple producter and multiple consumer lockfree queue?

user2720721
  • 33
  • 1
  • 5
  • The traditional solution is described by Michael-Scott and improved on by Orlarey-Fober-Letz. – Kerrek SB Aug 27 '13 at 09:02
  • This has been asked before and some of the answers here seem still to be valid and maintained: [Is there a production ready lock-free queue or hash implementation in C++](http://stackoverflow.com/questions/1164023/is-there-a-production-ready-lock-free-queue-or-hash-implementation-in-c) – Jens Gustedt Aug 27 '13 at 09:02

1 Answers1

2

The main reason for the maximum length is that once the queue is created, you can't create new objects (without potentially blocking in new or malloc or whatever is used to create the new object).

I'm not sure there is any solution to that. If allocation locks are acceptable, it wouldn't be that hard to make a lock-free queue that is limited by amount of memory available.

boost::lockfree does have reserve(n) and reserve_unsafe(n) that can be used to grow the queue.

Edit in response to comments:

Yes, the real problems start when two producers are trying to add new elements at the same time, because at some level or another, memory allocation will block until the "leading" thread has completed its allocation. This may of course be acceptable in some cases, but generally, the reason for using lock-free queues is to avoid locks, and having a lock down inside the new or malloc isn't still a lock.

If it only happens at relatively rare intervals, it may not be a big deal (depending on the use-case). But if it happens regularly, it will be a problem.

Even with a single producer, there is no guarantee that some other thread isn't calling malloc or new somewhere, causing a "wait" in the "add more to the queued".

I think the only real solution is to create a fixed size queue with a big enough size to deal with any possible workload. If the queue itself holds (smart) pointers/references to objects, that may not take up too much memory above and beyond the objects actually being stored in the queue. After all, if you are storing 1000 elements, you need at least 1000 elements worth of storage, whether the queue is dynamic or fixed size.

Mats Petersson
  • 126,704
  • 14
  • 140
  • 227
  • actually i found a lockfree that is dynamically-sized, but it is single-producer, single consumer.[link](http://moodycamel.com/blog/2013/a-fast-lock-free-queue-for-c++) i guessthat the queue will create new node and resize itself when the num of elements is beyond the high level. – user2720721 Aug 27 '13 at 09:20
  • i look at boost document again. it says "Allocatingmemory from the operating system is not lock-free. This makes it impossible toimplement true dynamically-sized non-blocking data structures." the dynamically-sized queue can resize itself because it is single producter? – user2720721 Aug 27 '13 at 09:31
  • @user2720721: See edit in answer. – Mats Petersson Aug 27 '13 at 10:14
  • thank you very mush,i know what i should do. – user2720721 Aug 28 '13 at 00:44