What exactly is non-blocking synchronization?.

[persres]

What is non-blocking synchronization?. What is lock free and wait free
algorithm? Can someone please explain?

[Anthony Williams]

persres <per...@googlemail.com> writes:

> What is non-blocking synchronization?. What is lock free and wait free
> algorithm? Can someone please explain?

I posted some definitions on my blog. I hope you find them useful.

http://www.justsoftwaresolutions.co.uk/threading/non_blocking_lock_free_and_wait_free.html

Anthony
--
Author of C++ Concurrency in Action http://www.stdthread.co.uk/book/
just::thread C++0x thread library http://www.stdthread.co.uk
Just Software Solutions Ltd http://www.justsoftwaresolutions.co.uk
15 Carrallack Mews, St Just, Cornwall, TR19 7UL, UK. Company No. 5478976

[Dmitriy Vyukov]

On Jan 25, 2:51 pm, Anthony Williams <anthony....@gmail.com> wrote:

> persres <pers...@googlemail.com> writes:
> > What is non-blocking synchronization?. What is lock free and wait free
> > algorithm? Can someone please explain?
>
> I posted some definitions on my blog. I hope you find them useful.
>

> http://www.justsoftwaresolutions.co.uk/threading/non_blocking_lock_fr...

Hi Anthony,

I am not sure about the following paragraph:
> This may then mean that the data structure is now in an inconsistent state,
> and other threads cannot perform any operations on the data structure until the operation
> is complete. These threads must then continually check the state of the data structure
> in what is called a busy-wait or spin-wait. Such waits are not blocking

Term lock-free is usually used to describe system-wide forward
progress guarantees. And if the thread is killed and left a data
structure in still inconsistent state... well, forward progress is
completely busted. What I am missing?

--
Dmitriy V'jukov

[Anthony Williams]

Dmitriy Vyukov <dvy...@gmail.com> writes:

Many of the algorithms that I've seen leave the data structure busted if
a thread is killed mid-way through an operation. I'd still call them
lock-free: there's no explicit locks.

I'll see if I can dig out an example.

[frege]

On Jan 25, 8:12 am, Dmitriy Vyukov <dvyu...@gmail.com> wrote:
> I am not sure about the following paragraph:
>
> > This may then mean that the data structure is now in an inconsistent state,
> > and other threads cannot perform any operations on the data structure until the operation
> > is complete. These threads must then continually check the state of the data structure
> > in what is called a busy-wait  or spin-wait. Such waits are not blocking
>
> Term lock-free is usually used to describe system-wide forward
> progress guarantees. And if the thread is killed and left a data
> structure in still inconsistent state... well, forward progress is
> completely busted. What I am missing?
>

I agree. Although I don't think of it as a thread being killed, but
while the 'winning' thread is suspended, no other thread is making
progress, so it is the same idea. ie suspended indefinitely vs killed
== same thing.

CAS-RMW-loops*** are lock-free because you *know* that if the CAS
failed and had to loop, then some other thread must have made progress
(ie updated the target address).

Spin-looks are NOT lock-free because you might be spinning while
another thread is just suspended - ie you do NOT know that someone
made progress.

At least that's how I've always interpreted it.

*** by CAS-RMW-loops, I mean those that re-read the target and
recalculate their desired value on every loop - ie atomic_increment
using CAS. A spin-loop might be a CAS-loop, but it doesn't re-read
and re-calculate - it just keeps hoping for "was 0, set to 1".

Tony

[Anthony Williams]

Dmitriy Vyukov <dvy...@gmail.com> writes:

Consider an SPSC queue that uses two stacks: one for pushing, one for
popping. The push stack is reversed to become the pop stack when the pop
stack is empty. If the pop thread is killed mid-reverse then you lose
all the data that has not yet been transferred. I would argue that this
is wait-free, since the push and pop threads do not have to wait for
each other, and either can make progress. However, it is not robust
against the pop thread being terminated: if you substitute a separate
wait thread then your FIFO order is hosed.

I'll think of better wording.

[Chris M. Thomasson]

"persres" <per...@googlemail.com> wrote in message
news:29f7d3d3-1f36-4826...@n4g2000yqf.googlegroups.com...

> What is non-blocking synchronization?. What is lock free and wait free
> algorithm? Can someone please explain?

I would classify lock-free as having to deal with the possibility of a
failure condition that denotes forward progress "has occurred" and the
operation should be tried again (e.g., failed CAS-loop means another thread
has finished, or is successfully progressing through the algorithm.)

Wait-free basically defines true forward progress in and of itself because
there is no looping on a shared failure condition. All the threads just
progress through the algorithm at their own time. Nothing holds anything
back such that every thread can make successful progression regardless of
any other threads actions.

That is a high-level brief description of wait-free progression. It does not
deal with actual architecture concerns. For instance, an atomic
fetch-and-add operation on the x86-32/64 is loopless in software. You just
execute the instruction and the hardware does it's thing. However, on
systems with LL/SC (e.g., PPC) you have to manually build the damn
fetch-and-add instruction in software. Yes, a loop is required!

;^(...