Search code examples
concurrencyterminologylock-free

What is the difference between lock-free and obstruction-free?

I am reading up on Transactional Memory (TM), and one of the papers I'm reading says[1]:

Indeed, it was two nonblocking algorithms, the obstruction-free DSTM and lock-free FSTM that reinvigorated STM research in the past decade.

I was under the impression that lock implied obstruction. Apparently, I was wrong...

What is the difference between the terms "lock-free" and "obstruction-free"?

Solution

  • Here are the definitions from Herlihy & Shavit's The Art Of Multiprocessor Programing.

    A method is wait-free if it guarantees that every call finishes its execution in a finite number of steps.

    A method is lock-free if it guarantees that infinitely often some method call finishes in a finite number of steps.

    A method is obstruction-free if, from any point after which it executes in isolation, it finishes in a finite number of steps (method call executes in isolation if no other threads take steps).

    All wait-free methods are lock-free, and all lock-free methods are obstruction-free.