Wait-free queue implementation in C++

Question

Is it possible to implement a Concurrent Queue which is completely wait-free and can support simultaneously multiple writers and readers?I know I can use mutexes or an existing library, but I really want to implement it myself.Any ideas?

Answer 1

You can find a wait-free queue for multiple enqueuers and dequeuers here, but as @David Schwartz said this will not be necessarily faster just for being wait-free. This is another paper about wait-free queue. On the references of these papers you also can find other proposed queues based on arrays, that means they have a limited capacity, but they are faster than those based on lists.

If you are looking for a practical solution Michael and Scott's Lock-Free queue is probably a good alternative.

If you want to learn more and give it a try yourself, Here you can find a good resume of the possible alternatives and there are a few code examples.