Lock-freeとWait-freeアルゴリズム
wait-freeとlock-freeの違いは、各プロセスによるwait-free操作は、他のプロセッサに関係なく、有限ステップで成功することが保証されている点である。
一般的にロックフリーのアルゴリズムは「自分の操作の完了」「妨害された操作の補助」「妨害された操作の中止」「待機」の4つのフェーズで実行できる。自身の操作の完了は、補助と中止が同時に発生する可能性があるため複雑になるが、常に完了までの最速の道のりである。
障害が発生したときに、いつアシストするか、中止するか、待つかを決めるのは、コンテンションマネージャーの責任である。これは非常に単純なもの(優先度の高い操作を支援し、優先度の低い操作を中止する)もあれば、より最適化してスループットを向上させたり、優先度の高い操作のレイテンシを下げたりするものもある。
正しいコンカレントアシスタンスは、一般的にロックフリーアルゴリズムの中で最も複雑な部分であり、実行するのに非常にコストがかかることが多い。アシストするスレッドが遅くなるだけでなく、共有メモリの仕組みのおかげで、アシストされるスレッドがまだ実行されている場合、そのスレッドも遅くなる。