CODEWITHSUNDEEP
concurrencyterminologylock-free
Nathan Fellman
Nathan Fellman

Reputation: 127578

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"?

Upvotes: 17

Views: 5354

Answers (1)

Binil Thomas
Binil Thomas

Reputation: 13799

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.

Upvotes: 6

Related Questions