[raphlinus]

I like the terminology that Dmitry Vyukov uses[0], where "wait-free" means that any individual thread is guaranteed to make progress, and "lock-free" means that some thread is guaranteed to make progress. There's also the weaker guarantee "obstruction-free" where livelock is a possibility.

[0] http://www.1024cores.net/home/lock-free-algorithms/introduct...

[dbaupp]

(It's worth noting that those are the standard terms for each of those concepts: https://en.wikipedia.org/wiki/Non-blocking_algorithm )

[stcredzero]

Couldn't there be an even stronger requirement like "obstruction-free"? I could imagine code that is "obstruction free" but which severely slows down execution for itself or other threads.

[raphlinus]

These are theoretical concepts. If there's a bound on the slowdown, it's lock-free. If there's no bound, it's obstruction free.

These theoretical concepts might or might not be that relevant for real-world applications. For example, in real-time audio (the main domain of interest to me for lock-free techniques), what you really care about is that the audio rendering thread will produce one buffer worth of sound before the hardware finishes outputting the previous buffer. This sounds like a match for "wait-free", but it depends on the details. If the non-audio thread can cause a 100x slowdown (but no more) that would technically be wait-free, but you'd miss your buffer, and so it's not acceptable. Another system might use mutexes, but be carefully engineered so that the locks are never held for more than 100µs (say, using locks designed to handle priority inversion), and thus reliably meet the needs even if it's not technically anything like lock-free.

But, as with anything, these concepts are useful tools, and I _love_ lock-free algorithms for audio.

[dbaupp]

Obstruction-free is the weakest requirement, so your use of "even stronger" confuses me.

In any case, in practice wait-free has this property a bit: getting the guarantee of all threads making progress in finite time generally requires in them executing slower individually, on average, e.g. one common strategy is for thread A help thread B finish its work, because thread A needs that result.

[stcredzero]

Executing a little slower would be fine. Executing two orders of magnitude slower can be almost as useless as being obstructed.