Le 07/08/2012 13:00, Invisible a écrit :
> Does anyone know of somewhere I can find a description of how to
> implement a lock-free work queue? I'm curious to see how it's done.


I thinks there might be one in The Art of Multiprocessor Programming.

Most lock-free constructs are using complex code to handle the possible
failure of a conditional write with feedback about the old value. (kind
of instruction (atomic) : if old value is x, then set y; return old value.)

For the writer/adding at the queue, you prepare your chain with your
exclusive new object and try to set it as the last one. If you fails
(the returned old value is not the one you expected), you do it again.
And again. And again...

For the reader/dequeuing, it's kind of the same story. (you have a head
& tail pair to hold the list: if you can "write" the new head, you have
dequeue the element you found at the old head. If you fails, check for
empty and do it again.

Oh, you need to implement it for a bounded queue as an array with read &
write indexes (and modulo to roll over the array ends).

The difficult part in all such algorithms is the "special" write
instruction. You cannot make it lock-free without the support at the
assembly level by the instruction set (at least in NUMA architecture)

Unlimited-size queue are more complex to deal with.

Post a reply to this message