Java における CAS の詳細解説

CAS（Compare-And-Swap）の概要

CAS は、メモリ上の値が期待値と一致するかどうかを比較し、一致した場合に新しい値に更新するという原子操作です。CAS はロックを使わないので、高負荷環境でのパフォーマンスが優れています。

Java における CAS の実装

Java では、CAS 操作は主に `Unsafe` クラスを介して実装されます。このクラスはハードウェアレベルの原子操作を提供します。以下は、`AtomicInteger` クラスの簡易的な実装例です。


public class AtomicInteger implements java.io.Serializable {
    private static final Unsafe unsafe = Unsafe.getUnsafe();
    private static final long valueOffset;

    static {
        try {
            valueOffset = unsafe.objectFieldOffset(AtomicInteger.class.getDeclaredField("value"));
        } catch (Exception ex) {
            throw new Error(ex);
        }
    }

    private volatile int value;

    public final int get() {
        return value;
    }

    public final int getAndIncrement() {
        return unsafe.getAndAddInt(this, valueOffset, 1);
    }

    public final boolean compareAndSet(int expect, int update) {
        return unsafe.compareAndSwapInt(this, valueOffset, expect, update);
    }
}

OS および CPU レベルでの CAS 実装

OS レベル

OS は、ハードウェアが提供する原子命令を用いて CAS 操作を実現します。一般的な命令には x86 アーキテクチャの `CMPXCHG` と ARM アーキテクチャの `LL/SC` があります。

CPU レベル

CPU は特定のアセンブリ命令を使って CAS を実装します。これらの命令は比較と交換を一連の原子操作で行い、マルチコア環境でのスレッドセーフを確保します。

x86 アーキテクチャ：


; CMPXCHG 命令の例
mov eax, [value]    ; メモリの値を eax レジスタに読み込む
mov ebx, new_value  ; 新しい値を ebx レジスタに読み込む
lock cmpxchg [address], ebx  ; 比較と交換

ARM アーキテクチャ：


; LDREX と STREX 命令の例
ldrex r0, [address]  ; アドレスの値を r0 レジスタに読み込む
cmp r0, expected     ; r0 と期待値を比較
strex r1, new_value, [address]  ; 比較が成功した場合、新しい値を保存

MESI キャッシュ一貫性プロトコル

MESI は、マルチコアプロセッサシステムでキャッシュ内のデータの一貫性を保証するためのプロトコルです。MESI は以下の 4 種類の状態を持ちます。

Modified（M）：キャッシュラインが変更され、メインメモリとは非同期であり、そのデータは唯一のキャッシュに保持されています。
Exclusive（E）：キャッシュラインが変更されておらず、メインメモリと同期しており、そのデータは唯一のキャッシュに保持されています。
Shared（S）：キャッシュラインが変更されておらず、メインメモリと同期しており、複数のキャッシュに保持される可能性があります。
Invalid（I）：キャッシュラインが無効であり、有効なデータを含んでいません。

CAS と MESI の組み合わせ

多コアプロセッサシステムでは、CAS 操作は MESI プロトコルによってデータの一貫性が保証されます。一つのプロセッサが CAS 操作を行う際、MESI プロトコルは他のプロセッサのキャッシュが古いデータを持つことを防ぎ、CAS 操作の原子性と正確性を確保します。

CAS の利点

非ブロッキング：CAS はロックを使用しないため、スレッドがロックを待つ必要がなく、プログラムのスループットが向上します。
原子性：CAS 操作自体は原子的であり、データの一貫性を確保し、データ競合やダートリードなどの問題を防ぎます。
柔軟性：CAS は様々な複雑な並列データ構造の実装に使用でき、高い柔軟性和拡張性を提供します。

CAS の制限

ABA 問題：CAS は値が変わったかどうかだけをチェックするため、ABA 問題が発生する可能性があります。
スピンコスト：CAS 操作が失敗した場合、通常はスピン（忙しい待ち）により再試行します。長時間のスピンは CPU リソースを浪費し、特に高負荷環境ではパフォーマンス低下につながります。
単一の共有変数への適用：CAS は通常、単一の共有変数に対する原子操作にしか適用できません。複数の共有変数を扱う複合操作では、CAS は原子性を保証できない場合があります。

ABA 問題の解決方法

バージョン番号：バージョン番号を導入し、変数を更新するたびにバージョン番号も更新することで ABA 問題を回避できます。例えば、`AtomicStampedReference` クラスを使用します。


AtomicStampedReference<String> atomicStampedReference = new AtomicStampedReference<>("initial", 0);
int[] stampHolder = new int[1];
String value = atomicStampedReference.get(stampHolder);
atomicStampedReference.compareAndSet("initial", "updated", stampHolder[0], stampHolder[0] + 1);

複雑なデータ構造：`AtomicMarkableReference` などのマーク付き参照タイプを使用すると、ABA 問題を緩和できます。


AtomicMarkableReference<String> atomicMarkableReference = new AtomicMarkableReference<>("initial", false);
boolean[] markHolder = new boolean[1];
String value = atomicMarkableReference.get(markHolder);
atomicMarkableReference.compareAndSet("initial", "updated", false, true);

CAS と volatile の関係

CAS と volatile はしばしば一緒に使用されます。CAS は操作の原子性を保証し、volatile は可視性と順序性を保証します。

volatile：
- volatile 修飾子は、変数の可視性と順序性を保証します。変数の変更は他のスレッドに即座に反映され、命令の再配置最適化が禁止されます。
- volatile 修飾された変数は、常にメモリから読み取られます。

まとめ

CAS は Java の並列プログラミングにおいて重要なツールであり、ロックを使用せずに効率的な並列制御を実現します。しかし、ABA 問題やスピンコストなどの制限もあります。これらの問題はバージョン番号や複雑なデータ構造を導入することで解決または軽減できます。CAS は原子性を提供し、volatile は可視性と順序性を保証します。両者を組み合わせることで、効率的なロックフリーの並列制御が可能になります。

タグ: Java cas Compare-And-Swap AtomicInteger unsafe

7月18日 16:20 投稿

異端開発室