Menu
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"?
813
Obstruction-freedom is the weakest natural non-blocking progress guarantee. An algorithm is obstruction-free if at any point, a single thread executed in isolation (i.e., with all obstructing threads suspended) for a bounded number of steps will complete its operation. All lock-free algorithms are obstruction-free.
Intuitively, lock-free means that some process is always guaranteed to make progress by completing its operations within a finite number of system steps, while wait-free means that each process completes its operations within a finite number of its own steps.
At its essence, lock-free is a property used to describe some code, without saying too much about how that code was actually written. Basically, if some part of your program satisfies the following conditions, then that part can rightfully be considered lock-free.
A task (thread) is non-blocking when it doesn't cause other tasks (threads) to wait until the task is finished.
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.
83
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
