1

Assume a producer-consumer scenario. I have used a lock-free implementation of a fixed-capacity queue, so that:

  1. The number of items that can be held in the queue is limited.
  2. Producers/consumers can push/pop items to/from the queue directly without holding any lock.

Now, I'm considering how to synchronize the producers and consumers, so that producers are not busy try-pushing to a full queue, and consumers are not busy try-popping from an empty queue.

I thought about condition variable at first. But it seems to destroy the whole purpose of using a lock-free queue implementation.

Is polling (with interval) the only sensible way to go with a lock-free queue?

Peter Cordes
  • 328,167
  • 45
  • 605
  • 847
Lingxi
  • 14,579
  • 2
  • 37
  • 93
  • Capacitated is not a word. I think you mean "fixed capacity". – Peter Cordes Mar 14 '18 at 12:23
  • 1
    Most real implementations optimistically try the lock-free way for a few iterations of busy waiting before using a fall-back mechanism like going to sleep. And probably setting an atomic flag so the first producer to push something will know to wake up a consumer. See https://stackoverflow.com/questions/45907210/lock-free-progress-guarantees for links to (and discussion about) a real-world implementation (liblfds) of a multi-producer multi-consumer lock-free queue with a power-of-2 fixed capacity. I haven't looked at its full/empty backoff code, but it's sophisticated. – Peter Cordes Mar 14 '18 at 12:27
  • @PeterCordes Thanks for the hint. Now I know where to look into :) – Lingxi Mar 14 '18 at 12:56

0 Answers0