Re: RCU+SMR

Joe Seigh wrote: 

Way back, I came up with a scheme where you make the queue a lock-free
LIFO stack using compare and swap.  The single reader just grabbed the
entire queue using compare and swap, reversed order making it FIFO
and worked off of that util it was empty and then repeated the whole
process by grabbing the shared LIFO stack again.

Actually, the original was just a doubly linked list with the reader
filling in the back links as needed.  You don't even need to ever
dequeue from the queue anchor if you just leave that last element
on the queue as a place holder.  There's some cache hit to the reader
doing the reverse linking but probably less overall than some complicated
lock-free fifo queue algorithms.   If you had spare hardware threads,
you could have one doing the reverse linking in parallel with the
reader thread and improve latency for the reader thread.

Haven't done that kind of stuff in a while.  Usually, I'm doing single
writer, multiple reader lock-free queues for multi-casting.

--
Joe Seigh

When you get lemons, you make lemonade.
When you get hardware, you make software. .

Relevant Pages

  • Asynchromous interprocess message queue (possible with fifo ?)
    ... I want to program some queue facilities for independent processes ... read end and a write end, numerous reader processes and writer ... My initial idea is to use fifo, since it's first in first out just ...
    (comp.unix.programmer)
  • Re: Thread Checking the Queue data in an infinite loop
    ... Yes Reader will acquire the mutex to access the each data element. ... Your pseudo code of Reader and writer has one problem where the reader ... acquires the Lock to drain the whole queue (i have a mutex which has ... all writer threads write to the IOCP and all consumer threads read from the IOCP. ...
    (microsoft.public.vc.mfc)
  • Re: Circular buffer
    ... >If the writer is consistently faster than the reader, ... > its speed with the reader. ... > single element buffer instead of a queue. ...
    (comp.programming)
  • Re: Circular buffer
    ... >If the writer is consistently faster than the reader, ... > its speed with the reader. ... > single element buffer instead of a queue. ...
    (comp.programming)
  • RE: single-reader/ multiple-writers message queuing
    ... The OS message queues support multiple writes and a single reader. ... - The reader creates the message queue. ... you can have writer threads block until ...
    (microsoft.public.windowsce.app.development)
Loading