So lock-freedom is when you have the guarantee that the whole system makes progress although some threads might starve. So an implementation based on CAS would give this guarantee.
Then obstruction-freedom is when one thread is guaranteed to complete if all the other threads are suspended.
Can you give a simple example of an obstruction-free algorithm which is not lock-free?
Thanks!
I recommend reading the paper that introduced the term - the primary author, Herlihy, kicked off this whole business when he introduced the concept of wait-freedom 25ish years ago.
The core difference between lock-freedom and obstruction-freedom is that the latter doesn't guarantee progress if two or more threads are running (but does if only one is running).
The meat of the paper gives you want you want, an example of a dequeue that is obstruction-free but not lock-free.
To make it even simpler, I'll just describe an array-based stack which operates in the same way, and is obstruction-free but not lock free.
Imagine a stack implemented on top of an array, such that the zero or more elements of the stack are stored consecutively at the beginning of the array, followed by "null" elements in all remaining positions. Each element of the stack is stored as a tuple: (val, seq), where val is the user-provided value and seq is a sequence number which is key to the algorithm (and also avoids the ABA problem1).
To push an element onto the stack, you first locate the last element in the stack (position A[k-1]) which is directly before the first null element (at position A[k]). You try increment, using CAS, the sequence number of the A[k-1] (the element doesn't change) and if successful, you try to simultaneously replace the value the null element at position A[k] and increment its sequence number. If either CAS fails you retry.
The pop algorithm is similar, but handles the elements in the reverse order (incrementing the sequence number of the fist null element, then trying to make the last element null and incrementing its sequence number).
The correctness of this structure is described in more detail in the paper above, but basically by successfully incrementing the A[k-1]th element you ensure that at that moment it is still the last element in the list, and you inform any concurrently racing push operations that you "get the next shot" by causing their initial CAS to fail. If the second CAS succeeds you successfully added an element.
Note that a concurrent push and pop operation can cause each other to fail, indefinitely. The push thread increments A[k-1] and the pop increments A[k], and then each fails as they see the increment of the other. Rinse and repeat. This is an example of livelock.
Note that the problem goes away if only one thread is running, which is the key observation in obstruction-freedom.
1 ... it also avoids "wraparound" problems in the full version of the dequeue, but I don't think that happens in the case of the stack.
I'm not sure it's possible to give a simple example. Simple things are usually wait-free (e.g. the reader side of RCU) or lock-free (e.g. CAS retry loops where livelock isn't possible), or not even obstruction-free.
See Lock-free Progress Guarantees for an analysis of a lockless multi-writer multi-reader queue where a writer that sleeps in mid operation can block the whole queue, even though it's high performance / low contention and useful in practice.
I think being obstruction-free without being lock-free is only possible if threads can cancel partially-complete operations by other threads. (And thus handle the case of having their own operations cancelled when they wake back up). I might be mistaken; maybe there are other ways an algo can be non-blocking but not lock-free.
This isn't what I would consider simple, but https://en.wikipedia.org/wiki/Non-blocking_algorithm says:
Some obstruction-free algorithms use a pair of "consistency markers" in the data structure. Processes reading the data structure first read one consistency marker, then read the relevant data into an internal buffer, then read the other marker, and then compare the markers. The data is consistent if the two markers are identical. Markers may be non-identical when the read is interrupted by another process updating the data structure. In such a case, the process discards the data in the internal buffer and tries again.
This could livelock if the backoff algorithm for contention isn't good. With too many threads hammering on it, they could just continually cancel each other before anything got done. This is what makes it not lock-free.
