[JVM] CAS(Compare-And-Swap) 연산과 락 프리 동시성 제어

왜 값 하나 바꾸는 데도 동시성 제어가 필요한가

여러 스레드가 같은 값을 동시에 읽고 쓰면 결과가 실행 순서에 따라 달라진다. 이를 경쟁 상태(Race Condition)라 부른다. 두 스레드가 동시에 카운터를 1씩 올리는 코드에서도 순서가 겹치면 값 하나가 그대로 사라진다. 원인은 counter++ 한 줄이 실제로는 세 단계라는 데 있다. 값을 읽고(read), 1을 더하고(modify), 다시 쓴다(write). 이 세 단계는 하나로 묶이지 않는다. 스레드 A가 읽은 직후 스레드 B도 같은 값을 읽으면, 두 스레드는 서로 모른 채 같은 값에 1을 더하고 나중에 쓴 쪽이 앞의 결과를 덮어쓴다. 이 문제를 락 없이 해결하는 연산이 CAS다.

문제	정의	예시
경쟁 상태	실행 순서에 따라 결과가 달라지는 상황	두 스레드가 동시에 counter++ 실행
원자성 붕괴	read-modify-write가 하나로 묶이지 않는 것	counter++가 세 단계로 풀림
가시성 문제	한 스레드의 쓰기가 다른 스레드에 안 보이는 것	volatile 없는 플래그를 계속 옛 값으로 읽음

동시성 제어 연산의 종류와 비교

원자성을 보장하는 방법은 두 갈래다. 아예 끼어들지 못하게 막는 방식(뮤텍스 계열)과, 끼어들어도 충돌이 감지되면 다시 시도하는 방식(락 프리 계열)이다.

도구	블로킹 여부	컨텍스트 스위칭 비용	경합 시 특성	적용 범위
synchronized / 뮤텍스	블로킹	발생	대기열에 쌓여 처리량이 완만히 저하	임계 구역 전체
ReentrantLock	블로킹(타임아웃 가능)	발생	synchronized와 유사, 제어가 더 세밀	synchronized와 동일
volatile	논블로킹	없음	원자성 자체가 없음	단일 변수의 가시성 전파
CAS(AtomicInteger 등)	논블로킹	없음	경합이 심하면 재시도가 누적	단일 변수의 원자적 갱신
트랜잭셔널 메모리	논블로킹	없음, 롤백 비용 발생	충돌 시 전체 롤백 후 재시도	여러 변수를 한 트랜잭션으로 묶을 때

CAS는 이 중 논블로킹 계열의 대표다. HikariCP와 Connection Pool의 커넥션 풀도 이 방식으로 상태를 관리한다.

CAS의 원리

CAS는 비교(compare)와 교체(swap)를 하나로 묶은 연산이다. 메모리 값이 기대한 값과 같을 때만 새 값으로 바꾸고, 다르면 아무것도 하지 않는다. 이 둘 사이에는 어떤 스레드도 끼어들 수 없다. 두 스레드가 같은 카운터를 두고 경쟁하면 다음과 같다.

Thread A가 먼저 counter=10을 읽고 CAS(10, 11)로 성공한다. 뒤늦게 같은 값을 들고 있던 Thread B가 CAS(10, 11)를 시도하면 메모리는 이미 11이라 실패한다. Thread B는 예외를 받는 대신 최신 값 11을 다시 읽어 CAS(11, 12)로 재시도해 성공한다. 실패해도 예외를 던지지 않고 다시 시도하는 이 동작을 스핀(spin)이라 부른다.

비교와 교체를 쪼갤 수 없게 만드는 건 하드웨어다. x86과 ARM은 방식이 다르지만(x86은 명령어 하나로 묶고, ARM은 두 명령어 사이의 끼어듦을 감시한다) 결론은 같다. 다른 코어가 끼어들면 그 사실이 반드시 드러난다. 자바의 AtomicInteger.compareAndSet() 호출도 결국 이 CPU 명령어 한 개로 치환되며, Unsafe와 VarHandle을 거쳐 JIT(Just-In-Time) 컴파일러가 그 호출을 바꿔치기하는 경로는 다음 다이어그램이 보여준다.

실패한 CAS는 최신 값을 다시 읽어 같은 시도를 반복한다. AtomicInteger.updateAndGet()(JDK 21)이 이 패턴을 보여준다.

public final int updateAndGet(IntUnaryOperator updateFunction) {
    int prev = get(), next = 0;
    for (boolean haveNext = false;;) {
        if (!haveNext)
            next = updateFunction.applyAsInt(prev);
        if (weakCompareAndSetVolatile(prev, next))
            return next;
        haveNext = (prev == (prev = get()));
    }
}

CAS가 실패하면 최신 값을 다시 읽고, 값이 바뀌지 않았다면 이미 계산해둔 next를 재사용해 함수를 다시 호출하지 않는다.

실제로 배타성은 존재하는데 x86의 LOCK 접두어라는 이름부터가 그렇고 캐시 라인 하나를 배타적으로 붙잡는다는 점은 존재한다. 다만 어떤 스레드가 임의의 시점에 멈추더라도 나머지 스레드가 계속 전진할 수 있기에 락 프리다. CAS는 락을 쥔 스레드가 선점이나 페이지 폴트(필요한 메모리가 아직 없어 처리가 멈추는 것)로 그 상태에서 그대로 멈추는 알고리즘이 아니다. CAS는 명령어 하나의 중간을 OS가 자를 수 없어 배타성을 쥔 채 잠드는 경우 자체가 없고, 그 배타성은 반드시 풀린다. 다만 전체가 전진한다고 모든 스레드가 전진하는 것은 아니어서, 특정 스레드만 재시도를 반복하다 굶을 수 있다. CAS는 락 프리이지, 개별 스레드까지 유한한 시도 안에 끝남을 보장하는 웨이트 프리(wait-free)는 아니다.

CAS의 장점과 단점

CAS는 락을 아예 잡지 않아 데드락이 원천적으로 불가능하고, 대기 스레드가 BLOCKED로 전환되지 않아 컨텍스트 스위칭 비용도 없다. 임계 구역이 짧을수록 synchronized보다 압도적으로 빠르다. 하지만 경합이 심해지면 반전된다. CAS가 성공하려면 쓰려는 코어가 캐시 라인 소유권을 가져오고 다른 코어의 사본을 무효화해야 한다. 이 소유권이 경합 중에 코어 사이를 계속 오가면 캐시 라인 핑퐁이라는 비용이 발생한다.

스핀은 실패할 때마다 다시 시도하므로, 락이었다면 스레드가 잠들어 있을 시간에 CAS는 CPU 사이클이 돌아간다. 캐시 라인 핑퐁까지 겹치면 처리량이 락보다 나빠질 수 있다. CAS는 하나의 변수에 대해서만 원자성을 보장하지만 대기 순서를 보장하지 않으니 기아(starvation)가 발생할 수 있다. CAS는 값이 같은지만 비교하므로, 값이 A에서 B를 거쳐 다시 A로 돌아오면 그 사이의 변화를 감지하지 못하고 통과시킨다. 이를 ABA 문제라 부른다. 락 프리 스택에서 흔한데, 다른 스레드가 최상단 원소를 pop했다가 다시 push하면 top이 이미 스택에서 빠진 노드를 가리키게 되어 스택이 깨질 수 있다.

해법은 값과 함께 변경 횟수(stamp)를 비교하는 것이다. AtomicStampedReference(JDK 21)는 참조와 정수 스탬프를 한 쌍으로 묶어 둘 다 일치할 때만 CAS를 성공시킨다.

public boolean compareAndSet(V expectedReference, V newReference,
                              int expectedStamp, int newStamp) {
    Pair<V> current = pair;
    return
        expectedReference == current.reference &&
        expectedStamp == current.stamp &&
        ((newReference == current.reference &&
          newStamp == current.stamp) ||
         casPair(current, Pair.of(newReference, newStamp)));
}

언제 써야 하는가

상황	선택	이유
임계 구역이 짧고 경합이 낮음	CAS(AtomicInteger, AtomicReference)	명령어 수준에서 끝난다
임계 구역이 길거나 경합이 극심함	synchronized 또는 ReentrantLock	스핀 대신 대기 스레드를 재운다
카운터 하나에 쓰기가 몰림	LongAdder(스트라이핑)	CAS 경합을 여러 슬롯으로 분산한다
여러 필드를 한 번에 일관되게 바꿔야 함	락 또는 불변 객체 통째 교체	CAS는 한 워드만 원자적이다