CAS 재시도와 충돌 비용

CAS는 메모리 값이 예상값과 같을 때만 새 값으로 교체합니다.

비교와 쓰기가 한 원자 연산이므로, 비교 시점의 현재 값이 예상값과 다르면 false를 받고 아무것도 쓰지 않습니다.

이 예제의 CAS 실패는 예외가 아니라 예상값이 더 이상 현재 값과 일치하지 않는 경쟁 결과입니다.

재시도 루프는 최신값을 다시 읽고 새 후보를 계산한 뒤 CAS를 반복합니다.

계산 함수는 여러 번 실행될 수 있으므로 외부 결제나 로그 전송을 포함하면 중복 부수 효과가 생깁니다.

CAS 구간은 짧고 순수한 상태 계산으로 제한합니다.

실패한 CAS를 성공으로 간주한 갱신

bad/OneShotCasIncrement.java

import java.util.concurrent.atomic.AtomicInteger;

public final class OneShotCasIncrement {
    private final AtomicInteger value = new AtomicInteger();

    void increment() {
        int observed = value.get();
        value.compareAndSet(observed, observed + 1);
    }

    public static void main(String[] args) throws InterruptedException {
        OneShotCasIncrement counter = new OneShotCasIncrement();
        Thread[] workers = new Thread[8];
        for (int i = 0; i < workers.length; i++) {
            workers[i] = Thread.ofPlatform().start(() -> {
                for (int n = 0; n < 100_000; n++) {
                    counter.increment();
                }
            });
        }
        for (Thread worker : workers) {
            worker.join();
        }
        System.out.println("expected=800000 actual=" + counter.value.get());
    }
}

이번 실행은 expected=800000, actual=556434를 출력했습니다. 한 번의 CAS 실패를 무시하면 증가가 빠질 수 있지만, 손실이 매 실행에서 반드시 나타나는 것은 아닙니다.

CAS가 원자적이라는 말은 모든 시도가 성공한다는 뜻이 아닙니다.

경쟁에서 진 호출자는 재시도, 포기, 상위 실패 반환 중 하나를 명시적으로 선택해야 합니다.

재시도 알고리즘의 불변식

observed는 한 시점에 읽은 후보 상태이며 교체 전까지 유효하다고 가정하지 않는다.
후보는 observed만으로 순수하게 계산해 같은 입력에 같은 결과를 만든다.
CAS 성공 시 그 교체가 연산의 선형화 지점이 된다.
CAS 실패 시 공유 값을 덮어쓰지 않고 최신 observed를 다시 얻는다.
무한 경쟁 가능성을 운영에서 관찰하려면 실패 횟수와 지연을 계측한다.
계산이 비싸거나 충돌이 잦으면 잠금이 재계산보다 유리할 수 있다.

재시도 횟수를 드러내는 누적기

src/MeasuredCasAccumulator.java

import java.util.concurrent.atomic.AtomicInteger;
import java.util.concurrent.atomic.LongAdder;

public final class MeasuredCasAccumulator {
    private final AtomicInteger total = new AtomicInteger();
    private final LongAdder retries = new LongAdder();

    void add(int delta) {
        if (delta < 0) throw new IllegalArgumentException("delta");
        while (true) {
            int observed = total.get();
            int candidate = Math.addExact(observed, delta);
            if (total.compareAndSet(observed, candidate)) return;
            retries.increment();
            Thread.onSpinWait();
        }
    }

    public static void main(String[] args) throws InterruptedException {
        MeasuredCasAccumulator accumulator = new MeasuredCasAccumulator();
        Thread[] workers = new Thread[4];
        for (int i = 0; i < workers.length; i++) {
            workers[i] = Thread.ofPlatform().start(() -> {
                for (int n = 0; n < 50_000; n++) {
                    accumulator.add(1);
                }
            });
        }
        for (Thread worker : workers) {
            worker.join();
        }
        System.out.println("total=" + accumulator.total.get());
        System.out.println("retries=" + accumulator.retries.sum());
    }
}

CAS 반환 뒤 두 구현이 하는 일을 비교한다
코드 지점	OneShotCasIncrement	MeasuredCasAccumulator
후보 계산	get() 한 번 뒤 observed + 1	반복마다 get() 뒤 Math.addExact(observed, delta)
CAS가 true	증가가 반영되고 메서드 종료	증가가 반영되면 즉시 return
CAS가 false	반환값을 버리고 메서드 종료	retries 증가 · 스핀 힌트 뒤 다음 반복에서 다시 읽음

후보 계산: OneShotCasIncrement: get() 한 번 뒤 observed + 1
MeasuredCasAccumulator: 반복마다 get() 뒤 Math.addExact(observed, delta)
CAS가 true: OneShotCasIncrement: 증가가 반영되고 메서드 종료
MeasuredCasAccumulator: 증가가 반영되면 즉시 return
CAS가 false: OneShotCasIncrement: 반환값을 버리고 메서드 종료
MeasuredCasAccumulator: retries 증가 · 스핀 힌트 뒤 다음 반복에서 다시 읽음

한 번의 CAS가 자동으로 재시도하는 것은 아닙니다. retries는 실패한 CAS 횟수이며, CPU 사용량이나 경과 시간을 측정한 값은 아닙니다.

이번 출력은 total=200000, retries=47870입니다. 원문이 정상 완료하고 모든 join이 반환하면 총합은 200,000이며, 재시도 수는 스케줄에 따라 달라지고 0일 수도 있습니다.

Thread.onSpinWait은 스핀 루프에 대한 힌트입니다. 락 획득이나 양보를 보장하지 않으며, 이 반복에는 park나 조건 대기가 없습니다.

지속적인 높은 경쟁에서는 재시도 수가 급격히 늘 수 있습니다.

CAS 함수에 부수 효과를 넣지 않는 업데이트

src/AtomicQuota.java

import java.util.concurrent.atomic.AtomicReference;

public final class AtomicQuota {
    record Quota(int remaining, int used) {
        Quota {
            if (remaining < 0 || used < 0) throw new IllegalArgumentException();
        }
    }

    private final AtomicReference<Quota> state =
            new AtomicReference<>(new Quota(3, 0));

    boolean tryAcquire() {
        while (true) {
            Quota observed = state.get();
            if (observed.remaining() == 0) return false;
            Quota candidate = new Quota(observed.remaining() - 1, observed.used() + 1);
            if (state.compareAndSet(observed, candidate)) return true;
        }
    }

    Quota snapshot() { return state.get(); }

    public static void main(String[] args) throws InterruptedException {
        AtomicQuota quota = new AtomicQuota();
        Thread[] callers = new Thread[5];
        for (int i = 0; i < callers.length; i++) {
            callers[i] = Thread.ofPlatform().start(() -> System.out.println(quota.tryAcquire()));
        }
        for (Thread caller : callers) {
            caller.join();
        }
        System.out.println(quota.snapshot());
    }
}

이번 실행은 true 세 개와 false 두 개 뒤 Quota[remaining=0, used=3]을 출력했습니다. 각 호출 결과의 출력 순서는 고정되어 있지 않습니다.

외부 작업이 필요하면 성공한 호출의 CAS 재시도 루프 밖에서 수행합니다. 이 예제에는 그런 작업이 없으며, 이 분리만으로 장애를 넘어선 정확히 한 번 처리를 보장하지는 않습니다.

외부 작업이 실패했을 때 상태를 되돌려야 한다면 단순 CAS보다 별도 보상 프로토콜이 필요합니다.

충돌률과 부수 효과로 CAS 적용 판단

경쟁 특성	CAS 판단	대안
짧은 계산·낮은 충돌	적용 후보	원자 클래스
긴 계산·높은 충돌	재계산 낭비	Lock
경합이 많은 통계 누적	정확한 개별 갱신값이 필요 없다면 검토	LongAdder · 동시 sum은 원자 스냅샷 아님
대기 중 CPU 절약 필요	스핀 부적합	조건 대기
외부 부수 효과 포함	재실행 위험	잠금과 명시적 단계

연습 문제

여러 스레드가 측정값을 제출합니다.

현재 최대보다 큰 값만 저장하고, 교체 성공 여부를 반환하세요.

낮은 값은 재시도 없이 거부하고 경쟁으로 실패했을 때만 최신값을 읽어 다시 판단합니다.

정답과 해설

exercise/AtomicMaximumSolution.java

import java.util.concurrent.atomic.AtomicInteger;

public final class AtomicMaximumSolution {
    private final AtomicInteger maximum = new AtomicInteger(Integer.MIN_VALUE);

    boolean record(int candidate) {
        while (true) {
            int observed = maximum.get();
            if (candidate <= observed) return false;
            if (maximum.compareAndSet(observed, candidate)) return true;
        }
    }

    public static void main(String[] args) throws InterruptedException {
        AtomicMaximumSolution values = new AtomicMaximumSolution();
        Thread a = Thread.ofPlatform().start(() -> values.record(18));
        Thread b = Thread.ofPlatform().start(() -> values.record(27));
        Thread c = Thread.ofPlatform().start(() -> values.record(21));
        a.join();
        b.join();
        c.join();
        System.out.println("max=" + values.maximum.get());
    }
}

이번 최종 출력은 max=27입니다.

가능한 순서의 한 예로, 21을 제출한 호출이 18을 읽은 뒤 27이 먼저 저장되면 CAS는 실패합니다. 다음 반복은 27을 읽고 false를 반환합니다. main은 이 순서를 강제하거나 record의 반환값을 출력하지 않습니다.

재시도 루프를 승인하는 조건

CAS 실패는 낡은 관찰을 감지하는 장치입니다.

실패 반환을 무시하지 말고 최신 상태를 기반으로 연산의 필요성부터 다시 판단합니다.

재시도 함수는 순수하게 유지하고 충돌 지표가 커지면 잠금 전환을 검토합니다.