Lock-freeとWait-freeアルゴリズム
Wait-freedom(ウェイトフリーダム)は、システム全体のスループット保証とスタベーション防止を組み合わせた、最強のノンブロッキング進行保証である。アルゴリズムはすべての操作に、その操作が完了するまでにアルゴリズムが取るステップ数の制限がある場合、ウェイトフリーとなる。この特性は、リアルタイムシステムにとって重要であり、性能コストが高すぎない限り、常にあった方が良いものである。
1980年代には、すべてのアルゴリズムがウェイトフリーで実装できることが示され、ユニバーサルコンストラクションと呼ばれるシリアルコードからの変換が数多く実証されている。しかし結果として得られる性能は、一般的にはナイーブなブロッキング設計にさえも及ばない。その後、いくつかの論文でユニバーサルコンストラクションの性能が改善されたが、それでも性能はブロッキングデザインを大きく下回っている。
ウェイトフリーなアルゴリズムを作ることの難しさについては、いくつかの論文で研究されている。例えば、広く利用されているアトミックな条件付きプリミティブであるCASやLL/SCでは、多くの一般的なデータ構造に対して、スレッド数に応じてメモリコストが線形に増加することなく、スタベーションのない実装を行うことができないことが示されている。
ロックフリーは、個々のスレッドがスターブする(飢える)ことを許容するが、システム全体のスループットを保証する。アルゴリズムがロックフリーであるとは、プログラムのスレッドを十分に長い時間実行したときに、少なくとも1つのスレッドが進歩することを意味する(進歩の定義が適切である場合)。待ち時間のないアルゴリズムはすべてロックフリーである。
特に、1つのスレッドが中断された場合、ロックフリーアルゴリズムは、残りのスレッドがまだ進行できることを保証する。したがって、もし2つのスレッドが同じミューテックスロックやスピンロックを争うことができるなら、そのアルゴリズムはロックフリーではない。(ロックを保持している1つのスレッドをサスペンドすると、2つ目のスレッドがブロックしてしまう)。
あるプロセッサによる無限回の操作が、有限回のステップで成功する場合、アルゴリズムはロックフリーとなる。例えばN個のプロセッサがある操作を実行しようとしている場合、N個のプロセスのうち、あるものは有限のステップ数で操作を終えることに成功し、他のものは失敗して失敗時に再試行する可能性がある。