CAS 재시도와 충돌 비용

CAS는 메모리 값이 예상값과 같을 때만 새 값으로 교체합니다. 비교와 쓰기가 한 원자 연산이므로 다른 스레드가 먼저 값을 바꾸면 현재 시도는 false를 받고 아무것도 쓰지 않습니다. 실패는 예외가 아니라 “읽은 스냅샷이 낡았다”는 정상적인 경쟁 결과입니다.

재시도 루프는 최신값을 다시 읽고 새 후보를 계산한 뒤 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());
    }
}

한 번의 실패를 무시했기 때문에 실제값은 기대보다 작을 수 있습니다. 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());
    }
}

총합은 항상 200,000이고 재시도 수는 환경마다 달라집니다. Thread.onSpinWait은 CPU에 스핀 루프 힌트를 주지만 블로킹으로 전환하지 않습니다. 지속적인 높은 경쟁에서는 재시도 수가 급격히 늘 수 있습니다.

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());
    }
}

성공은 세 번뿐이며 최종 상태는 남은 값 0, 사용 중 3입니다. 성공 후 외부 작업이 필요하면 CAS가 성공한 다음 한 번만 수행합니다. 외부 작업이 실패했을 때 상태를 되돌려야 한다면 단순 CAS보다 별도 보상 프로토콜이 필요합니다.

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

경쟁 특성	CAS 판단	대안
짧은 계산·낮은 충돌	효율적	원자 클래스
긴 계산·높은 충돌	재계산 낭비	Lock
대기 중 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());
    }
}

최종 최대는 27입니다. 21이 18을 본 뒤 27이 먼저 저장하면 21의 CAS가 실패하고, 다시 27을 읽어 더 이상 갱신하지 않습니다.

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

CAS 실패는 낡은 관찰을 감지하는 장치입니다. 실패 반환을 무시하지 말고 최신 상태를 기반으로 연산의 필요성부터 다시 판단합니다. 재시도 함수는 순수하게 유지하고 충돌 지표가 커지면 잠금 전환을 검토합니다.