concurrency - ロックフリーと障害物フリーの違いは何ですか？

Question

私はTransactionalMemory（TM）について読んでいますが、読んでいる論文の1つに[ 1 ]と書かれています。

実際、過去10年間でSTM研究を再活性化したのは、障害物のないDSTMとロックのないFSTMの2つの非ブロッキングアルゴリズムでした。

ロックは障害物を意味するという印象を受けました。どうやら、私は間違っていた...

「ロックフリー」と「障害物フリー」という用語の違いは何ですか？

Answer 1

Herlihy＆ShavitのThe Art OfMultiprocessorProgrammingからの定義は次のとおりです。

すべての呼び出しが有限のステップ数で実行を終了することが保証されている場合、メソッドは待機なしです。

メソッドの呼び出しが有限のステップ数で終了することが無限に頻繁にあることが保証されている場合、メソッドはロックフリーです。

メソッドは、その後の任意の時点から分離して実行され、有限のステップ数で終了する場合、障害物はありません（他のスレッドがステップを実行しない場合、メソッド呼び出しは分離して実行されます）。

すべての待機フリーメソッドはロックフリーであり、すべてのロックフリーメソッドは障害物フリーです。