Lock-freeとWait-freeアルゴリズムとは、共有データにロックをかけて保護するアルゴリズムとは違い、複数のスレッドが同時並行的に、ある対象データを壊すことなしに読み書きすることを可能にするアルゴリズムである。Lock-free とはスレッドがロックしないことを意味しており、全てのステップにおいてシステムが必ず進行する。通常ロックを所有するスレッドは、コンテキストスイッチが発生した時点で、全体の進行を阻止することがあるので、Lock-free ではミューテックスやセマフォといった、排他制御のためのプリミティブが使われていないということになる。Wait-free とは、他のスレッドの動作に関係なく、スレッドがいかなる操作も有限のステップで操作を完了させられることを指す。Wait-free なアルゴリズムは Lock-free である。マルチスレッドプログラミングにおいて古典的な手法は、共有リソースにアクセスするときはロックをかけることである。ミューテックスやセマフォといった排他制御はソースコードのある領域( クリティカルセクション)を同時に実行しないようにし、それゆえ、共有メモリの構造を破壊しないようにする。もし、他のスレッドが事前に獲得したロックをあるスレッドが獲得しようとするときは、ロックが解放されるまでスレッドの動作は停止する。スレッドが停止することは多くの理由で望ましくない。まず、スレッドがブロックされている間は、何も出来ない。そして、スレッドが優先順位の高い処理やリアルタイム処理を行っているならば、そのスレッドを停止することは望ましくない。また、複数のリソースにロックをかけることは、デッドロック、ライブロック、優先順位の逆転を起こすことがある。さらに、ロックを使うには、並列処理の機会を減らす粒度の荒い( = クリティカルセクションが長い )ロックを選択するか、バグを生みやすく注意して設計しないといけない粒度の細かいロックを選択するかというトレードオフ問題を生む。Wait-free のデータ構造を使ったプログラムを書くには、ミューテックスを使って書いてあるアルゴリズムを Wait-free のアルゴリズムに書き直すよりも、Wait-free のデータ構造の研究者が書いたスタック、キュー、セット、マップを使った方が望ましい。例えば、Java 5以降では、java.util.concurrentパッケージに Wait-free のデータ構造のクラスが入っている。Wait-free のデータ構造を使うことで、スレッド間で非同期にデータをやりとりするプログラムが書きやすくなる。例えば、銀行口座への預金プログラムを作るとする。それぞれのスレッドをATMとする。預金預け入れをするには、現在の預金残高を読み出し、預入金額を足し算し、新しい預金残高を書き込むという処理が必要である。ロック方式のやり方の場合、1つ目のATMが預金をするとき、ほかのATMが同時に預金残高を変更しないよう、ロックをかける。さもないと、同時に処理してしまうと、最終的な預金残高に不整合が起きうる。この処理を Lock-free にするには、すべての預入要求を管理するスレッドを作り、そこに、Wait-free のキューを作り、ATMはそのキューに対して非同期にロックをかけることなく預入要求を入れ、預入要求を管理するスレッドはキューから順次取り出し、預金残高を更新する。このやり方の方が、わざわざ Lock-free の預金アルゴリズムを作るよりも、プログラミングは楽である。さらに、この手法は、キューがWait-freeであるので、Lock-free なだけでなく、Wait-freeでもある。預金残高の書き換え処理をn並列で行いたいなら、n個Wait-freeキューを作り、口座番号をnで割った余りでどのキューに入れるか決めるという方法で対応できる。Lock-free や Wait-free アルゴリズムを作るには、CPUが専用のアトミックな命令を提供し、それを使う必要がある。最も重要なのは、コンペア・アンド・スワップ（"Compare and swap

出典:wikipedia