コンペア・アンド・スワップ
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/02/11 05:42 UTC 版)
「Lock-freeとWait-freeアルゴリズム」の記事における「コンペア・アンド・スワップ」の解説
Lock-free や Wait-free アルゴリズムを作るには、CPUが専用のアトミックな命令を提供し、それを使う必要がある。最も重要なのは、コンペア・アンド・スワップ（Compare and Swap, CASと省略する）である。Java では、java.util.concurrent.atomicパッケージ内のクラスに、compareAndSetメソッドとして存在する。これは、メモリアドレス、古い値、新しい値の3つを使う。もし、メモリアドレスに保存したある値が、指定された古い値ならば、それを新しい値に置き換え、そうでない場合は、何もしない。そして、この処理が成功したかどうかをプログラムに返す。CPUはこれをアトミックに実装する必要がある。現在[いつ?]のIntelプロセッサにはこの機能がある。この機能は、メモリからデータを読み出し、変更し、書き戻すという処理を、他のスレッドがその間に同時に変更を行っていない場合にのみ行う、というアルゴリズムを可能にする。 例えば、先ほどの銀行口座の例で、別なアルゴリズムを見てみる。ATMは現在の値を読み出し、加算し、書き込む、という3ステップにおいて、3ステップ目をコンペア・アンド・スワップを使って行う。この3ステップの間に他のスレッドが値を書き換えなければ、3ステップ目のコンペア・アンド・スワップは成功する。しかし、この3ステップにおいて預金処理が同時並行で起これば、1ステップ目の読み出した金額と、3ステップ目の書き込みで「比較して交換」を使って読んだ金額が一致しないため、失敗し、ATMは1ステップ目からやり直す。全てのATMは成功するまでこの3ステップを繰り返す。このアルゴリズムは Lock-free ではあるが、Wait-free ではない。なぜなら、他のATMが預金することにより、自分のATMが何度も挑戦する必要があるからである。 Wait-Free Synchronization (1993) では、コンペア・アンド・スワップがなぜ、Wait-freeにおいて必要か証明している。
※この「コンペア・アンド・スワップ」の解説は、「Lock-freeとWait-freeアルゴリズム」の解説の一部です。
「コンペア・アンド・スワップ」を含む「Lock-freeとWait-freeアルゴリズム」の記事については、「Lock-freeとWait-freeアルゴリズム」の概要を参照ください。
固有名詞の分類
| 排他制御 |
直列化可能性 複数粒度ロック コンペア・アンド・スワップ リード・コピー・アップデート コミットメント順序付け |
Weblioに収録されているすべての辞書からコンペア・アンド・スワップを検索する場合は、下記のリンクをクリックしてください。
全ての辞書からコンペア・アンド・スワップ
を検索
- コンペア・アンド・スワップのページへのリンク
