Lock-freeとWait-freeアルゴリズム
オブストラクション・フリーダムは、最も弱い自然なノンブロッキング進行保証である。アルゴリズムは、ある時点で、隔離された状態で(つまり、障害となるスレッドをすべて停止させた状態で)、制限されたステップ数だけ実行された単一のスレッドがその処理を完了する場合、オブストラクションフリーと言える。すべてのロックフリー・アルゴリズムはオブストラクションフリーである。
オブストラクションフリーの条件は、部分的に完了した操作を中止し、加えられた変更をロールバックできることだけである。並行支援をやめれば、アルゴリズムがよりシンプルになり、検証も容易となる。システムが継続的にライブロックしないようにすることは、コンテンションマネージャの仕事である。
妨害のないアルゴリズムの中には、データ構造の中に2つの「一貫性マーカー」を使用するものがある。データ構造を読むプロセスは、まず一方の整合性マーカーを読み、次に関連するデータを内部バッファに読み込み、次にもう一方のマーカーを読み、マーカーを比較する。2つのマーカーが同一であれば、データは一貫している。他のプロセスがデータ構造を更新することで読み取りが中断された場合、マーカーが一致しないことがある。このような場合、プロセスは内部バッファのデータを破棄して再試行する。
例えば、銀行口座への預金プログラムを作るとする。それぞれのスレッドをATMとする。預金預け入れをするには、現在の預金残高を読み出し、預入金額を足し算し、新しい預金残高を書き込むという処理が必要である。ロック方式のやり方の場合、1つ目のATMが預金をするとき、ほかのATMが同時に預金残高を変更しないよう、ロックをかける。さもないと、同時に処理してしまうと、最終的な預金残高に不整合が起きうる。この処理を Lock-free にするには、すべての預入要求を管理するスレッドを作り、そこに、Wait-free のキューを作り、ATMはそのキューに対して非同期にロックをかけることなく預入要求を入れ、預入要求を管理するスレッドはキューから順次取り出し、預金残高を更新する。このやり方の方が、わざわざ Lock-free の預金アルゴリズムを作るよりも、プログラミングは楽である。さらに、この手法は、キューがWait-freeであるので、Lock-free なだけでなく、Wait-freeでもある。預金残高の書き換え処理をn並列で行いたいなら、n個Wait-freeキューを作り、口座番号をnで割った余りでどのキューに入れるか決めるという方法で対応できる。
一部の例外を除き、ノンブロッキング・アルゴリズムでは、ハードウェアが提供しなければならないアトミックなリード・モディファイ・ライトのプリミティブを使用している。クリティカルセクションは、ほとんどの場合、これらのプリミティブに対する標準的なインターフェースを使って実装されている(一般的なケースでは、これらのプリミティブを使って実装されていても、クリティカルセクションはブロック化される)。1990年代には、すべてのノンブロッキングアルゴリズムは、許容できる性能を得るために、基本的なプリミティブを用いて「ネイティブ」に記述する必要があった。しかしソフトウェア・トランザクショナル・メモリでは、効率的なノンブロッキング・コードを書くための標準的な抽象化が約束されている。
またスタック、キュー、セット、ハッシュテーブルなどの基本的なデータ構造の提供についても多くの研究がなされている。これらは、プログラムが非同期にスレッド間で簡単にデータを交換することを可能にする。