1

I am considering concurrent multi-producer multi-consumer data structure that has two methods: success = try_put(elem) and success = try_get(&elem). I assume that this data structure has a fixed amount of preallocated memory and in case it is full or empty, success boolean flag contains false meaning that the corresponding operation can't be made.

The data structure doesn't enforce any ordering guarantees, so it doesn't matter is it a stack, queue, or something else. Does this data structure has some name in the literature?

Is it possible to make the wait-free implementation of this data structure? Does the presence of constant time atomic operations is required, if yes how they should be used?

Shridhar R Kulkarni
  • 6,653
  • 3
  • 37
  • 57
  • What is _wait-free_? If the same `elem` is accessed by 2 threads, the accesses are serialized. Is this a _wait_? – Reinhard Männer Dec 28 '20 at 14:37
  • @ReinhardMänner I am using definition of wait-free from here https://en.wikipedia.org/wiki/Non-blocking_algorithm –  Jan 04 '21 at 12:30

1 Answers1

4

The data structure could be named depending on how you implement it.

Producer Consumer Reference Name
Multi Single Jiffy: A Fast, Memory Efficient, Wait-Free Multi-Producers Single-Consumer Queue Queue
Multi Multi A scalable multi-producer multi-consumer wait-free ring buffer Ring buffer
Single Multi FFQ: A Fast Single-Producer/Multiple-ConsumerConcurrent FIFO Queue* Concurrent FIFO Queue

* Wait-free interface for producers, Lock-free for consumers

Shridhar R Kulkarni
  • 6,653
  • 3
  • 37
  • 57