CAS (Compare-And-Swap)

CAS란?

CAS는 멀티스레드 환경에서 락 없이 동시성을 보장하는 원자적 연산입니다.

기본 동작 원리

CAS 연산은 세 가지의 인자를 사용합니다.

boolean compareAndSwap(메모리주소, 예상값, 새값) {
    if (메모리주소의_현재값 == 예상값) {
        메모리주소의_값 = 새값;
        return true;  // 성공
    } else {
        return false; // 실패
    }
}

• 메모리 주소 == 작업할 메모리 위치(공유 변수)

• 예상하는 값 (expect)

• 새로운 값 (new)

전통적인 Lock과 CAS 방식

// 락 방식: 느리고 데드락 위험
synchronized (object) {
    counter++;  // 다른 스레드들이 블로킹되어 대기
}

// CAS 방식: 빠르고 데드락 없음
AtomicInteger counter = new AtomicInteger();
counter.incrementAndGet();  // 락 없이 안전

CAS의 동시성 처리 방식

int currentValue = 100;

Thread-1: 값 100 읽음 → CAS(100, 200) 업데이트 준비
Thread-2: 값 100 읽음 → CAS(100, 300) 업데이트 준비

// 실제 실행 (CPU 수준):
// 두 스레드가 동시에 currentValue 값을 읽지만..
// T1: Thread-1 먼저 실행 → if(100 == 100) ? YES → 200으로 변경
// T2: Thread-2 나중 실행 → if(200 == 100) ? NO → 실패

핵심: "비교+변경"이 원자적 연산이므로 순서대로 처리됨

HashMap 동시성 문제

// 문제: HashMap + 멀티스레드
Map<String, Object> map = new HashMap<>();

// 여러 스레드가 동시 접근 시:
// 1. 데이터 손실
// 2. 무한 루프 (내부 구조 파괴)
// 3. NullPointerException

// 해결: ConcurrentHashMap (내부적으로 CAS 사용)
Map<String, Object> map = new ConcurrentHashMap<>();

ConcurrentHashMap에서의 활용

CAS + 선택적 락킹

public V put(K key, V value) {
    for (Node[] tab = table;;) {
        if (빈_버킷) {
            // CAS로 원자적 삽입 시도
            if (casTabAt(tab, i, null, newNode)) break;
            else continue;  // 재시도
        }
        else if (충돌_발생) {
            synchronized (첫번째_노드) {
                // 해당 체인에만 락 적용
            }
        }
    }
}

실제로는 버킷이 비어있을 때는 CAS, 충돌 시 해당 체인에만 synchronized 락을 사용 → 부분적 락킹.

ABA 문제

ABA 문제는 값 A가 B로 바뀌었다가 다시 A로 돌아오면, CAS는 최종 값만 보고 변경이 없었다고 착각하여 작업을 수행합니다. 상황에 따라 문제가 안되는 경우도 많습니다. (값이 단순 카운터 같은 경우)

• "상태값 관리"처럼 의미 있는 변화일 때만 심각한 버그로 이어질 수 있습니다.

// ABA 시나리오

// 시나리오 1
String value = "A"

Thread-1: value = A 읽음, CAS 준비 중...
Thread-2: A → B로 변경
Thread-3: B → A로 되돌림
Thread-1: CAS 실행 → A 발견하고 성공 (실제로는 변경되었는데 모름)

// 시나리오 2
AtomicReference<Node> head = new AtomicReference<>(nodeA);

Thread-1: Node current = head.get();  // nodeA 읽음
Thread-2: head.compareAndSet(nodeA, nodeB);  // A→B 변경
Thread-3: head.compareAndSet(nodeB, nodeA);  // B→A 되돌림  
Thread-1: head.compareAndSet(nodeA, nodeC);  // 성공하지만 실제로는 문제!

// Thread-1은 실제로는 변경된 상황을 모르고 계속 재시도

시나리오 1에서 String "A"가 단순한 문자가 아니라 '중요한 상태 값'이라고 하겠습니다

• 예를 들어, "결제 대기중" 이라는 상태를 갖습니다.

1. Thread-1 (결제 처리 스레드): "상태가 '결제 대기중'(A)이네. 그럼 이제부터 복잡한 결제 로직을 처리하고, 끝나면 '결제 완료'(C)로 바꿔야지." 라고 생각하고 결제 로직을 처리하기 시작합니다.

2. 중간 과정:

   • Thread-2 (사용자): 결제를 취소합니다. 상태가 **'결제 취소'(B)**로 바뀝니다.

   • Thread-3 (시스템): 취소된 건을 보고 관련 데이터를 정리한 후, 다시 동일한 주문 번호로 상품을 담아 '결제 대기중'(A) 상태로 만듭니다. (예: 장바구니에 다시 담기)

3. Thread-1의 치명적 실수:

   • 복잡한 결제 로직을 다 처리한 Thread-1이 돌아옵니다.

   • 상태를 확인하니 여전히 '결제 대기중'(A) 입니다.

   • Thread-1은 "아무도 취소 안 했네!" 라고 착각하고, 이미 취소되었던 옛날 주문 정보에 대해 '결제 완료'(C) 처리를 해버립니다.

결론: Thread-1은 사용자가 취소했던 주문을 강제로 결제 완료시켜 버리는 심각한 버그를 일으켰습니다.

해결책: 버전(Version) 또는 스탬프(Stamp)를 함께 사용하는 것입니다. 값을 비교할 때 값과 버전을 동시에 비교하는 방식입니다.

• 초기 상태: (값: A, 버전: 1)

• Thread-2가 A를 B로 변경: (값: B, 버전: 2)

• Thread-3이 B를 다시 A로 변경: (값: A, 버전: 3)

• 이후 Thread-1이 CAS 시도: 현재 값(A)은 예상 값(A)과 같지만, 현재 버전(3)이 예상 버전(1)과 다르므로 실패합니다.

• Java에서는 이를 구현한 AtomicStampedReference 클래스를 제공합니다.

CAS 특징

1. 락 프리 (Lock-Free)

• SW락을 사용하지 않습니다.

  • synchronized, ReentrantLock 등 불필요

  • 락으로 인해 성능 저하나 데드락 등의 문제가 발생할 수 있지만, 락 프리 알고리즘은 락을 사용하지 않고 원자적 연산을 활용해 여러 스레드 간의 동기화를 수행합니다.

• 하드웨어 원자성

  • CPU 명령 수준에서 원자성을 보장합니다.

• 즉시 결과 반환

  • 성공/실패를 즉시 반환합니다. (대기시간 0)

1. 하드웨어 수준 구현

# x86-64의 실제 CAS 명령어
CMPXCHG [memory_location], new_value
# 단일 CPU 사이클에서 완료 (중간에 끼어들 수 없음)

1. 스핀을 이용한 낙관적 락 패턴

스핀 락이란?

• 락(Lock) 자체를 획득하기 위해 반복적으로 재시도하며 CPU를 소모하는 방식의 락입니다. 락이 해제될 때까지 계속 재시도하는 방식으로 구현되어 있습니다.

// CAS의 일반적인 사용 패턴
public void increment() {
    int current, next;
    do {
        current = getValue();
        next = current + 1;
        
     // 공유 변수의 값을 바꾸려다 실패했을 때만 루프   
    } while (!compareAndSet(current, next));
}

CAS 재시도 루프는 락을 획득하는 것이 아니라, 데이터 업데이트 자체가 실패했을 때 재시도하는 것입니다.

락이 없으므로 "낙관적"이며, 실패 시 재시도를 위해서 "스핀"을 사용합니다.

구분	스핀 락	CAS 재시도 루프
목적	임계 구역(자원 접근) 자체를 선점하기 위해 락 변수를 확보	특정 데이터 값을 기대하는 값으로 원자적으로 교체
루프 조건	락 변수가 비어있을 때까지 계속 CAS 시도 (락이 해제되길 기다림)	CAS 실패(값 충돌) 시에만 다시 CAS 시도 (데이터 경쟁 시 재시도)
예시	while (!CAS(lock, 0, 1)) {} (락 변수 확보용)	do { current = get(); } while (!CAS(current, current+1)); (Atomic counter 증가, LinkedList head 교체 등)

• 스핀 락은 “락을 얻기 위해” 반복. (락 성공하면 이후 임계 구역 진입)

• CAS 루프는 “데이터 업데이트 자체”를 성공할 때까지 반복.

즉, 둘 다 Busy-wait이지만 무엇을 얻기 위해 반복하는가(락 or 데이터 값)가 다른 점이 핵심입니다 .

1. 장점:

• 락 프리로 데드락 없음

• 낮은 경합 시 높은 성능 가능성

• 즉시 응답 (대기 시간이 없음)

1. 단점:

// 극단적인 경우
while (!compareAndSet(expected, newValue)) {
    // 실패시 즉시 재시도
    // CPU가 100% 사용되면서 계속 루프
    // 다른 작업들이 CPU를 사용하지 못함
}

• 높은 경합 시 CPU 부하

• ABA 문제 가능성

CAS와 락(synchronized) 비교

두 방식의 '기다림' 방식은 다릅니다. 즉, 블로킹(Blocking) vs 논블로킹(Non-Blocking) 관점에서 바라볼 수 있습니다.

synchronized의 동작 방식: "대기실에서 호출을 기다리기"

synchronized는 블로킹 방식입니다.

1. Thread-A가 식당(임계 영역)에 들어갑니다. 문을 잠급니다.

2. Thread-B가 도착했지만, 문이 잠겨있어 들어갈 수 없습니다.

3. Thread-B는 운영체제(OS)에 의해 '대기실(Waiting Queue)'로 보내집니다.

4. 대기실에 있는 동안 Thread-B는 잠을 자는 것과 같아서 CPU를 전혀 사용하지 않습니다. (상태: Blocked)

   1. 즉, 대기 중에는 CPU를 사용하지 않습니다.

5. Thread-A가 식사를 마치고 나가면, OS가 대기실에 있는 Thread-B를 깨워서 안으로 들여보냅니다.

이 과정에서 스레드를 재우고 깨우는 컨텍스트 스위칭(Context Switching) 비용이 발생합니다.

CAS의 동작 방식: "카운터 앞에서 계속 물어보기"

CAS는 논 블로킹 방식이며, 바쁜 대기(Busy Waiting)을 합니다.

1. Thread-A가 카운터에서 주문을 변경하고 있습니다.

2. Thread-B도 주문을 변경하려고 시도했지만, Thread-A 때문에 실패합니다.

3. Thread-B는 대기실로 가지 않습니다. 대신, 카운터 앞에서 "이제 됐나요? 이제 됐나요?"라고 1초도 쉬지 않고 계속 물어봅니다.

4. 계속 물어보는 동안 Thread-B는 깨어있는 상태로 CPU를 100% 사용합니다. (상태: Running)

5. Thread-A의 작업이 끝나는 순간, Thread-B는 바로 다음 시도에서 성공합니다.

이것을 스핀 웨이트(Spin Wait)라고 부릅니다. 스레드가 멈추지 않고 제자리에서 뱅글뱅글 돌면서(spin) 계속 시도하기 때문입니다.

구분	synchronized (블로킹)	CAS (논블로킹, 스핀)
스레드 상태	대기(Blocked) 상태로 전환됨	실행(Running) 상태를 유지함
CPU 사용	대기 중 CPU를 사용하지 않음	재시도 중 CPU를 계속 사용함
OS 개입	OS가 직접 스레드를 재우고 깨움	OS 개입 없이 스스로 계속 시도함

'재시도를 위해 기다린다'는 현상은 같아 보이지만 그 방식이 근본적으로 다릅니다.

락은 CPU를 놓아주고 쉬는 것이고, CAS는 CPU를 붙잡고 계속 시도하는 것입니다.

Refer

https://blog.hexabrain.net/403

https://curiousjinan.tistory.com/entry/java-concurrent-hash-map-cas