Compare and Swap

Compare and Swap(CAS)は,並列アルゴリズムを設計する際に用いられる技術である.

マルチスレッド環境とマルチコア環境では、各CPUはメインメモリで変数値を参照するのではなく、各CPUのキャッシュ領域でメモリ値を参照します.
メインメモリに格納されている値とCPUキャッシュに格納されている値が異なる場合があります.(これを可視性の問題と呼びます.)
CASアルゴリズムを使用しています現在書き込まれている値がメインメモリに格納されている値と一致する場合は、新しい値に置き換えられます.一致しない場合は、失敗して再試行されます.
これにより、CPUキャッシュで無効な値を参照する可視性の問題を解決することができる.

適用

2つのスレッドがJavaのsynchronized blockに同時にアクセスしようとすると、1つはsynchronized block、1つのblockにアクセスできます.
この場合,ブロックスレッドのコストが高い.

public class ProblematicLock {

    private volatile boolean locked = false;

    public synchronized void lock() {

        while(this.locked) {
            // busy wait - until this.locked == false
        }

        this.locked = true;
    }

    public void unlock() {
        this.locked = false;
    }

}

また、ブロックされたスレッドがいつブロックを解除するかを確保することはできません.
これは、ブロック解放を制御するためのオペレーティングシステムまたはオペレーティングシステムに依存する.下図のように時間を無駄にする可能性があります.

CompareとSwapアルゴリズムは同期ブロックに取って代わることができ,コストの高い問題を解決することができる.
CPUが一度に1つのスレッドしか処理していないことを確認します.したがって、スレッドをブロックまたは無効にする操作を処理する必要はありません.
これにより、スレッドが実行を待つ時間が短縮されます.次の図に示すように、アクセス可能になるまでCompare and Swapを実行します.

Java 5から,原子クラスはCPUレベルでCompareとswapの機能を提供する.

AtomicBoolean

AtomicInteger

AtomicLong

AtomicReference

AtomicStampedReference

AtomicIntegerArray

AtomicLongArray

AtomicReferenceArray

高価な同期ブロックではなくAtomicクラスを使用してCompare and swapを実装します.

public class CompareAndSwapLock {

    private AtomicBoolean locked = new AtomicBoolean(false);

    public void unlock() {
        this.locked.set(false);
    }

    public void lock() {
        while(!this.locked.compareAndSet(false, true)) {
            // 성공할때까지 무한루프
        }
    }
}

ソース

https://jenkov.com/tutorials/java-concurrency/compare-and-swap.html#compare-and-swap-for-check-then-act-cases

https://javaplant.tistory.com/23