Circular lock-free buffer

by

I’ve made a particular study of lock-free data structures in the last couple of years. I’ve read most of the papers in the field (there’s only about fourty or so – although only about ten or fifteen are any real use 🙂

AFAIK, a lock-free circular buffer has not been invented. The problem will be dealing with the complex condition where a reader overtakes a writer or vis-versa.

If you have not spent at least six months studying lock-free data structures, do not attempt to write one yourself. You will get it wrong and it may not be obvious to you that errors exist, until your code fails, after deployment, on new platforms.

I believe however there is a solution to your requirement.

You should pair a lock-free queue with a lock-free free-list.

The free-list will give you pre-allocation and so obviate the (fiscally expensive) requirement for a lock-free allocator; when the free-list is empty, you replicate the behaviour of a circular buffer by instantly dequeuing an element from the queue and using that instead.

(Of course, in a lock-based circular buffer, once the lock is obtained, obtaining an element is very quick – basically just a pointer dereference – but you won’t get that in any lock-free algorithm; they often have to go well out of their way to do things; the overhead of failing a free-list pop followed by a dequeue is on a par with the amount of work any lock-free algorithm will need to be doing).

Michael and Scott developed a really good lock-free queue back in 1996. A link below will give you enough details to track down the PDF of their paper; Michael and Scott, FIFO

A lock-free free-list is the simplest lock-free algorithm and in fact I don’t think I’ve seen an actual paper for it.

More Related Contents:

  1. Lock-free Progress Guarantees in a circular buffer queue
  2. When to use volatile with multi threading?
  3. Concurrency: Atomic and volatile in C++11 memory model
  4. How can I implement ABA counter with c++11 CAS?
  5. Understanding std::hardware_destructive_interference_size and std::hardware_constructive_interference_size
  6. Acquire/release semantics with non-temporal stores on x64
  7. Do I need to protect read access to an STL container in a multithreading environment?
  8. Making a C++ class a Monitor (in the concurrent sense)
  9. Portable Compare And Swap (atomic operations) C/C++ library?
  10. Is it possible to implement lock free map in C++
  11. Is a memory barrier required to read a value that is atomically modified?
  12. Example for boost shared_mutex (multiple reads/one write)?
  13. Rounding up to the nearest multiple of a number
  14. Magic number in boost::hash_combine
  15. Creating all possible k combinations of n items in C++
  16. How do I calculate the week number given a date?
  17. Why is the destructor of a future returned from `std::async` blocking?
  18. Where can I get a “useful” C++ binary search algorithm?
  19. std::vector, thread-safety, multi-threading
  20. How to use SQLite in a multi-threaded application?
  21. Is there any compiler barrier which is equal to asm(“” ::: “memory”) in C++11?
  22. Thread safe implementation of circular buffer
  23. How to atomically update a maximum value?
  24. Can I force cache coherency on a multicore x86 CPU?
  25. Efficiently getting all divisors of a given number
  26. c++, std::atomic, what is std::memory_order and how to use them?
  27. OpenMP: What is the benefit of nesting parallelizations?
  28. Is MAXIMUM_WAIT_OBJECTS really 64?
  29. How to implement a unmanaged thread-safe collection when I get this error: is not supported when compiling with /clr
  30. Calculate mean and standard deviation from a vector of samples in C++ using Boost

Leave a Comment