Skip to content

The multi-producer-single-consumer ring buffer is not lock-free (so not wait-free) #20

Closed

Description

@namniav

The used algorithm can be reduced to

producer:
    pos = write_cursor.fetch_add(num);
    write_data(blocks[pos].data)                    #1
    blocks[pos].status.store(ready, release)

consumer:
    pos = read_cursor.load(relaxed)
    if blocks[pos].status.load(acquire) == ready:   #2
        read_data(blocks[pos].data)
        blocks[pos].status.store(free, release)
        

Consumer and producers rely on a flag(status) indicating whether data is ready. If a producer is suspended at #1, then the consumer is blocked at #2, waiting the producer to finish writing. No further data from other producers can be consumed. When the ring buffer become full, all other producers are blocked by the consumer which is blocked by the suspended producer. No thread can make progress until the suspended producer finish writing.

Activity

  1. locked and limited conversation to collaborators on Sep 18, 2024
  2. converted this issue into a discussion #21 on Sep 18, 2024
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions