オブストラクション・フリーダム（Obstruction-freedom）
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/02/11 05:42 UTC 版)
「Lock-freeとWait-freeアルゴリズム」の記事における「オブストラクション・フリーダム（Obstruction-freedom）」の解説
オブストラクション・フリーダムは、最も弱い自然なノンブロッキング進行保証である。アルゴリズムは、ある時点で、隔離された状態で（つまり、障害となるスレッドをすべて停止させた状態で）、制限されたステップ数だけ実行された単一のスレッドがその処理を完了する場合、オブストラクションフリーと言える。すべてのロックフリー・アルゴリズムはオブストラクションフリーである。 オブストラクションフリーの条件は、部分的に完了した操作を中止し、加えられた変更をロールバックできることだけである。並行支援をやめれば、アルゴリズムがよりシンプルになり、検証も容易となる。システムが継続的にライブロックしないようにすることは、コンテンションマネージャの仕事である。 妨害のないアルゴリズムの中には、データ構造の中に2つの「一貫性マーカー」を使用するものがある。データ構造を読むプロセスは、まず一方の整合性マーカーを読み、次に関連するデータを内部バッファに読み込み、次にもう一方のマーカーを読み、マーカーを比較する。2つのマーカーが同一であれば、データは一貫している。他のプロセスがデータ構造を更新することで読み取りが中断された場合、マーカーが一致しないことがある。このような場合、プロセスは内部バッファのデータを破棄して再試行する。
※この「オブストラクション・フリーダム（Obstruction-freedom）」の解説は、「Lock-freeとWait-freeアルゴリズム」の解説の一部です。
「オブストラクション・フリーダム（Obstruction-freedom）」を含む「Lock-freeとWait-freeアルゴリズム」の記事については、「Lock-freeとWait-freeアルゴリズム」の概要を参照ください。
- オブストラクション・フリーダムのページへのリンク
