ロックフリーダム（Lock-freedom）
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/02/11 05:42 UTC 版)
「Lock-freeとWait-freeアルゴリズム」の記事における「ロックフリーダム（Lock-freedom）」の解説
ロックフリーは、個々のスレッドがスターブする（飢える）ことを許容するが、システム全体のスループットを保証する。アルゴリズムがロックフリーであるとは、プログラムのスレッドを十分に長い時間実行したときに、少なくとも1つのスレッドが進歩することを意味する（進歩の定義が適切である場合）。待ち時間のないアルゴリズムはすべてロックフリーである。 特に、1つのスレッドが中断された場合、ロックフリーアルゴリズムは、残りのスレッドがまだ進行できることを保証する。したがって、もし2つのスレッドが同じミューテックスロックやスピンロックを争うことができるなら、そのアルゴリズムはロックフリーではない。(ロックを保持している1つのスレッドをサスペンドすると、2つ目のスレッドがブロックしてしまう)。 あるプロセッサによる無限回の操作が、有限回のステップで成功する場合、アルゴリズムはロックフリーとなる。例えばN個のプロセッサがある操作を実行しようとしている場合、N個のプロセスのうち、あるものは有限のステップ数で操作を終えることに成功し、他のものは失敗して失敗時に再試行する可能性がある。wait-freeとlock-freeの違いは、各プロセスによるwait-free操作は、他のプロセッサに関係なく、有限ステップで成功することが保証されている点である。 一般的にロックフリーのアルゴリズムは「自分の操作の完了」「妨害された操作の補助」「妨害された操作の中止」「待機」の4つのフェーズで実行できる。自身の操作の完了は、補助と中止が同時に発生する可能性があるため複雑になるが、常に完了までの最速の道のりである。 障害が発生したときに、いつアシストするか、中止するか、待つかを決めるのは、コンテンションマネージャーの責任である。これは非常に単純なもの（優先度の高い操作を支援し、優先度の低い操作を中止する）もあれば、より最適化してスループットを向上させたり、優先度の高い操作のレイテンシを下げたりするものもある。 正しいコンカレントアシスタンスは、一般的にロックフリーアルゴリズムの中で最も複雑な部分であり、実行するのに非常にコストがかかることが多い。アシストするスレッドが遅くなるだけでなく、共有メモリの仕組みのおかげで、アシストされるスレッドがまだ実行されている場合、そのスレッドも遅くなる。
※この「ロックフリーダム（Lock-freedom）」の解説は、「Lock-freeとWait-freeアルゴリズム」の解説の一部です。
「ロックフリーダム（Lock-freedom）」を含む「Lock-freeとWait-freeアルゴリズム」の記事については、「Lock-freeとWait-freeアルゴリズム」の概要を参照ください。
- ロックフリーダムのページへのリンク
