Invisible <voi### [at] devnull> wrote:
> 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.

Have you tried a google search. I didn't, but I'm pretty sure that there
should be plenty of material out there.

AFAIK lock-free algorithms cannot be implemented without proper hardware
support (for algorithms that usually require locks, that is; of course
there are algorithms that don't need locking simply because they operate
on completely independent data and do not depend on each other).

In modern Intel processors there are some machine code instructions for
precisely this kind of thing, the first one of them being Compare-And-Swap.
I think that other similar instructions have been added later. Their idea
is that they do two things in such a way that the hardware *guarantees*
that no interruption will happen between those two things, and no other
processor/core can get "in-between" them to mess things up. Or if we use
a more technical term: The two things are guaranteed to be executed
atomically.

One such atomic operation supported by modern processors is fetch-and-add,
which I think is the easiest way of implementing a lock-free queue (or at
least to add to the queue in a thread-safe way; reading/popping things from
the queue is probably a bit more complicated).

Several threads can safely add things to the queue with a fetch-and-add
instruction: They simply read the current next index of the queue, and
at the same time increment it. Now they can write to that location without
having to worry about other threads getting the same index.

Reading from the queue is probably not that simple (because you have to
check that there are elements in the queue and you must not read an element
while another thread is writing it). This can probably be implemented using
compare-and-swap, or other similar techniques.

-- 
                                                          - Warp

Post a reply to this message