Memory management in a lock free queue

Question

We've been looking to use a lock-free queue in our code to reduce lock contention between a single producer and consumer in our current implementation. There are plenty of queue implementations out there, but I haven't been too clear on how to best manage memory management of nodes.

For example, the producer looks like this:

queue.Add( new WorkUnit(...) );

And the consumer looks like:

WorkUnit* unit = queue.RemoveFront();
unit->Execute();
delete unit;

We currently use memory pool for allocation. You'll notice that the producer allocates the memory and the consumer deletes it. Since we're using pools, we need to add another lock to the memory pool to properly protect it. This seems to negate the performance advantage of a lock-free queue in the first place.

So far, I think our options are:

• Implement a lock-free memory pool.
• Dump the memory pool and rely on a threadsafe allocator.

Are there any other options that we can explore? We're trying to avoid implementing a lock-free memory pool, but we may to take that path.

Thanks.

Condor

It changes your semantics, but you could try queueing objects instead of pointers. – Ledford

Answer 1

Only producer shall be able to create objects and destroy them when they aren't needed anymore. Consumer is only able to use objects and mark them as used. That's the point. You don't need to share memory in this case. This is the only way I know of efficient lock free queue implementation.

Read this great article that describes such algorithm in details.

Trina

As Herb Sutter's follow-up clearly shows, that article has so many concurrency errors that it's not even funny; drdobbs.com/cpp/210600279 – Autarch

@Aaron Klotz: Hmm. This article is just an illustration of brilliant handing of memory issue. The question was exactly about this. Sure, we should use atomic iterators (as I remember he uses its own list implementation in the source code attached to the article) and memory barriers to avoid reordering. I agree, it is not a simple topic but well-known problems to be faced with implementing lock-free stuff. – Trina

Even though the original article is flawed, Sutter's follow-up and subsequent implementation does illustrate what I'm looking for. I'll be studying this one a bit more. – Condor

Answer 2

One more possibility is to have a separate memory pool for each thread, so only one thread is ever using a heap, and you can avoid locking for the allocation.

That leaves you with managing a lock-free function to free a block. Fortunately, that's pretty easy to manage: you maintain a linked list of free blocks for each heap. You put the block's own address into (the memory you'll use as) the link field for the linked list, and then do an atomic exchange with the pointer holding the head of the linked list.

Helban

Answer 3

You should look at Intel's TBB. I don't know how much, if anything, it costs for commercial projects, but they already have concurrent queues, concurrent memory allocators, that sort of thing.

Your queue interface also looks seriously dodgy- for example, your RemoveFront() call- what if the queue is empty? The new and delete calls also look quite redundant. Intel's TBB and Microsoft's PPL (included in VS2010) do not suffer these issues.

Simasimah

that's not the actual code, it's just meant to illustrate how the memory allocation works. TBB and PPL aren not valid options. We're stuck coming up with a home grown solution here. – Condor

Answer 4

I am not sure what exactly your requirements are, but if you have scenario where producer creates data and push this data on queue and you have single consumer who takes this data and uses it and then destroys it, you just need tread safe queue or you can make your own single linked list that is tread safe in this scenario.

• create list element
• append data in list element
• change pointer of next element from null to list element (or equivalent in other languages)

Consumer can be implemented in any way, and most linked lists are by default tread safe for this kind of operation (but check that whit implementation)

In this scenario, consumer should free this memory, or it can return it in same way back to producer setting predefined flag. Producer does not need to check all flags (if there are more than like 1000 of them) to find which bucket is free, but this flags can be implemented like tree, enabling log(n) searching for available pool. I am sure this can be done in O(1) time without locking, but have no idea how

Perspex

Answer 5

I had the exact same concern, so I wrote my own lock-free queue (single-producer, single-consumer) that manages the memory allocation for you (it allocates a series of contiguous blocks, sort of like std::vector).

I recently released the code on GitHub. (Also, I posted on my blog about it.)

If you create the node on the stack, enqueue it, then dequeue it to another node on the stack, you won't need to use pointers/manual allocation at all. Additionally, if your node implements move semantics for construction and assignment, it will be automatically moved instead of copied :-)

Valadez