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.

Post a reply to this message

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

On 07/08/2012 01:42 PM, Le_Forgeron wrote:
> 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.

This one?

http://tinyurl.com/cfklrg2

> 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)

So that's, what, a CAS instruction or something?

Post a reply to this message

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

On 07/08/2012 04:55 PM, Warp wrote:
> 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.

I had thought this, but I didn't manage to find anything. (Other than 
several Wikipedia pages saying that "algorithms exist to do this".)

> AFAIK lock-free algorithms cannot be implemented without proper hardware
> support.

Yeah, I figured that would be the case.

Post a reply to this message

Le 07/08/2012 14:48, Invisible nous fit lire :
> On 07/08/2012 01:42 PM, Le_Forgeron wrote:
>> 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.
> 
> This one?
> 
> http://tinyurl.com/cfklrg2
> 
>> 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)
> 
> So that's, what, a CAS instruction or something?

Yes & Yes.

Post a reply to this message

On 8/7/2012 5:42, Le_Forgeron wrote:
> 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)

Not true. Look up Lamport's bakery algorithm. (Wikipedia has a good write-up.)

-- 
Darren New, San Diego CA, USA (PST)
   "Oh no! We're out of code juice!"
   "Don't panic. There's beans and filters
    in the cabinet."

Post a reply to this message

On 8/7/2012 8:55, Warp wrote:

> AFAIK lock-free algorithms cannot be implemented without proper hardware

Lamport actually surprised a lot of people when he came up with the bakery 
algorithm.

-- 
Darren New, San Diego CA, USA (PST)
   "Oh no! We're out of code juice!"
   "Don't panic. There's beans and filters
    in the cabinet."

Post a reply to this message

On 10/08/2012 12:48 AM, Darren New wrote:
> On 8/7/2012 5:42, Le_Forgeron wrote:
>> 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)
>
> Not true. Look up Lamport's bakery algorithm. (Wikipedia has a good
> write-up.)

Why must all algorithms do to with multithreading have food in their names?

First the dining philosophers, and now this?

Post a reply to this message

Le 10/08/2012 01:48, Darren New a écrit :
> On 8/7/2012 5:42, Le_Forgeron wrote:
>> 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)
> 
> Not true. Look up Lamport's bakery algorithm. (Wikipedia has a good
> write-up.)
> 


The backery is lock free, but need either static threads or a global
registry (list, whatever) of all active threads. You cannot protect such
registry with backery (deadly recursion).
(

Other inherent issue is unlimited number: on rollover with an actual
implementation, you're stuck.

Post a reply to this message