[viraptor]

> ..., atomic-free synchronization algorithms

Actually I'm not sure if it was supposed to be funny or serious. I see the funny "everything-free" list, as well as can imagine that there is some action you can do not atomically (relative to other actions) that gives you synchronisation.

Anyone?

[dkersten]

I'm not quite sure what you mean, but synchronization without atomic operations is possible.

An example of mutual exclusion, without any atomic operations, taken from the book "The art of multiprocessor programming"[1] is (paraphrased) as follows:

Two threads, A and B, want to access some memory. Each thread has a flag.

When thread A wants to access the shared memory:

    Set flag A
    Wait for flag B to become unset
    Access memory
    Unset flag A

When thread B wants to access the shared memory:

    Set flag B
    While flag A is set {
        Unset flag B
        Wait for flag A to become unset
        Set flag B
    }
    Access memory
    Unset flag B

Obviously this isn't a general purpose solution, but rather an easy to understand example demonstrating that atomic operations are not required.

[1] http://www.amazon.com/Art-Multiprocessor-Programming-Maurice...

[tedunangst]

That only works with coherent in order memory operations. Once you add the appropriate memory barriers, it looks a lot more "atomic".

[dkersten]

I chose that example because its easy to understand, obviously in modern processors with out of order execution and whatnot, you would need something a lot more elaborate.

Once you add the appropriate memory barriers, it looks a lot more "atomic"

Well, they force in order memory access. That doesn't look terribly "atomic" to me, but I understand your point.

[dvyukov]

The intention was actually something like "atomic-RMW-free", that is "costly-operation-free". It should also include expensive memory fences, and excessive sharing. I have an explanation of "atomic-free" in the Russian article, but I did not transfer it to the English page on xxx-free. Sorry for any confusion. I think I better just remove it from the main page for now.

[kev009]

The speaker admits his English isn't perfect; probably an error as much of the site seems geared toward lock-free _atomic_ operations.