CAS(Compare-And-Swap): 논블로킹 동시성 제어의 핵심

멀티스레드 환경에서 공유 자원에 대한 안전한 접근을 보장하는 방법은 크게 두 가지로 나눌 수 있다: 블로킹(blocking) 방식과 논블로킹(non-blocking) 방식이다. 이 글에서는 논블로킹 동시성 제어의 핵심 메커니즘인 CAS(Compare-And-Swap)에 대해 심층적으로 살펴보고자 한다.

CAS란 무엇인가?

CAS(Compare-And-Swap)는 멀티스레드 환경에서 원자적(atomic) 연산을 지원하는 저수준 하드웨어 명령어다. 이름에서 알 수 있듯이, CAS는 두 가지 주요 작업을 수행한다:

1. Compare(비교): 메모리 위치의 현재 값을 예상 값과 비교한다.
2. Swap(교환): 값이 일치하면, 새로운 값으로 교체한다.

이 두 작업은 단일 원자적 연산으로 실행되기 때문에, 다른 스레드의 간섭 없이 안전하게 수행된다.

CAS의 원리

CAS 연산은 보통 세 개의 피연산자를 가진다:

CAS(메모리 위치, 예상 값, 새로운 값)

작동 방식은 다음과 같다:

1. 메모리 위치의 현재 값을 읽는다.
2. 이 값이 예상 값과 일치하는지 확인한다.
3. 일치한다면, 메모리 위치를 새로운 값으로 업데이트한다.
4. 일치하지 않는다면, 업데이트하지 않는다.
5. 연산의 성공 여부를 반환한다.

이 모든 과정은 단일 원자적 연산으로 처리되므로, 다른 스레드가 중간에 값을 변경할 수 없다.

하드웨어 수준의 지원

대부분의 현대 CPU 아키텍처는 CAS 연산을 직접 지원하는 명령어를 제공한다:

• x86/x64: CMPXCHG 명령어
• ARM: LDREX와 STREX 명령어의 조합
• SPARC: CAS 명령어
• MIPS: LL(Load-Linked)와 SC(Store-Conditional) 명령어의 조합

JVM은 이러한 하드웨어 명령어를 추상화하여, 자바 코드에서 Unsafe 클래스의 compareAndSwapInt, compareAndSwapLong, compareAndSwapObject 등의 메서드를 통해 접근할 수 있게 한다.

자바에서의 CAS 활용

자바에서는 직접 CAS 연산을 사용하기보다는 java.util.concurrent.atomic 패키지의 클래스들을 통해 간접적으로 활용한다. 이 패키지는 CAS 연산을 기반으로 구현된 다양한 원자적 클래스들을 제공한다:

• AtomicInteger, AtomicLong, AtomicBoolean
• AtomicReference
• AtomicIntegerArray, AtomicLongArray, AtomicReferenceArray

예제: AtomicInteger를 이용한 카운터 구현

import java.util.concurrent.atomic.AtomicInteger;

public class AtomicCounter {
    private AtomicInteger count = new AtomicInteger(0);
    
    public void increment() {
        count.incrementAndGet(); // 원자적 증가 연산
    }
    
    public int getValue() {
        return count.get();
    }
}

이 코드에서 incrementAndGet() 메서드는 내부적으로 CAS 연산을 사용하여 다음과 같이 동작한다:

// incrementAndGet()의 내부 동작 (의사 코드)
int current;
do {
    current = get();  // 현재 값 읽기
} while (!compareAndSet(current, current + 1));  // CAS 연산으로 업데이트 시도
return current + 1;

compareAndSet 메서드는 CAS 연산의 결과를 반환하며, 실패할 경우 성공할 때까지 재시도한다.

CAS의 내부 구현: 살펴보기

CAS 기반 원자적 연산이 실제로 어떻게 구현되는지 더 자세히 살펴보자. AtomicInteger의 incrementAndGet() 메서드는 다음과 같은 단계로 구현된다:

public final int incrementAndGet() {
    return unsafe.getAndAddInt(this, valueOffset, 1) + 1;
}

여기서 unsafe.getAndAddInt는 다음과 같이 구현되어 있다:

public final int getAndAddInt(Object o, long offset, int delta) {
    int v;
    do {
        v = getIntVolatile(o, offset);
    } while (!compareAndSwapInt(o, offset, v, v + delta));
    return v;
}

compareAndSwapInt는 CAS 연산을 수행하는 네이티브 메서드다:

public final native boolean compareAndSwapInt(Object o, long offset, int expected, int x);

이 네이티브 메서드는 JVM에 의해 해당 플랫폼의 하드웨어 CAS 명령어로 변환된다.

CAS vs. synchronized

CAS 기반 동시성 제어와 synchronized 키워드 기반 동시성 제어를 비교해보자:

특성 CAS synchronized

메커니즘	논블로킹	블로킹
실패 시 행동	재시도	대기
컨텍스트 스위칭	없음	있음 (경쟁 시)
데드락 가능성	없음	있음
CPU 사용량	높음 (경쟁 시)	낮음
적합한 상황	짧은 크리티컬 섹션, 낮은 경쟁	긴 크리티컬 섹션, 높은 경쟁

CAS의 장단점

장점

1. 데드락 방지: 락을 사용하지 않으므로 데드락이 발생하지 않는다.
2. 우선순위 역전 문제 없음: 저우선순위 스레드가 락을 보유하여 고우선순위 스레드를 차단하는 문제가 없다.
3. 컨텍스트 스위칭 최소화: 스레드가 차단되지 않으므로 컨텍스트 스위칭이 최소화된다.
4. 확장성 향상: 락 경쟁으로 인한 병목 현상이 줄어든다.

단점

1. ABA 문제: 값이 A→B→A로 변경된 경우, CAS는 변경되지 않았다고 판단할 수 있다.
2. 제한된 크리티컬 섹션: 복잡한 연산을 여러 CAS 연산으로 분해해야 한다.
3. 자원 낭비: 경쟁이 심한 경우 지속적인 재시도로 CPU 자원이 낭비될 수 있다.
4. 라이브락 가능성: 여러 스레드가 서로의 CAS 연산을 계속 방해하는 상황이 발생할 수 있다.

ABA 문제와 해결책

ABA 문제는 CAS의 가장 유명한 문제점으로, 다음과 같은 시나리오에서 발생한다:

1. 스레드 1이 위치 M의 값 A를 읽는다.
2. 스레드 1이 일시 중단된다.
3. 스레드 2가 위치 M의 값을 A에서 B로 변경한다.
4. 스레드 2가 위치 M의 값을 B에서 A로 다시 변경한다.
5. 스레드 1이 재개되어, 위치 M의 값이 여전히 A임을 확인하고 CAS 연산을 성공적으로 수행한다.

스레드 1은 값이 변경되지 않았다고 판단하지만, 실제로는 중간에 값이 변경되었다가 다시 원래 값으로 돌아온 것이다.

해결책: AtomicStampedReference

자바는 ABA 문제를 해결하기 위해 AtomicStampedReference 클래스를 제공한다. 이 클래스는 참조값과 함께 버전 번호(stamp)를 유지하며, CAS 연산 시 참조값과 버전 번호 모두 확인한다.

import java.util.concurrent.atomic.AtomicStampedReference;

public class ABADemo {
    private static AtomicStampedReference<Integer> atomicStampedRef = 
        new AtomicStampedReference<>(100, 0);
    
    public static void main(String[] args) throws InterruptedException {
        // 초기 스탬프 값 획득
        int initialStamp = atomicStampedRef.getStamp();
        Integer initialRef = atomicStampedRef.getReference();
        
        // 첫 번째 CAS 연산
        boolean success = atomicStampedRef.compareAndSet(
            initialRef, 120, initialStamp, initialStamp + 1);
        
        if (success) {
            System.out.println("첫 번째 CAS 성공!");
            System.out.println("새 값: " + atomicStampedRef.getReference());
            System.out.println("새 스탬프: " + atomicStampedRef.getStamp());
        }
        
        // ABA 시나리오 시뮬레이션
        // A → B
        atomicStampedRef.compareAndSet(
            120, 130, atomicStampedRef.getStamp(), atomicStampedRef.getStamp() + 1);
        System.out.println("A → B 변경 후: " + atomicStampedRef.getReference());
        
        // B → A (값은 원래대로 돌아오지만 스탬프는 증가)
        atomicStampedRef.compareAndSet(
            130, 100, atomicStampedRef.getStamp(), atomicStampedRef.getStamp() + 1);
        System.out.println("B → A 변경 후: " + atomicStampedRef.getReference());
        System.out.println("현재 스탬프: " + atomicStampedRef.getStamp());
        
        // 초기 스탬프와 현재 스탬프가 다르므로 CAS 실패
        success = atomicStampedRef.compareAndSet(
            100, 120, initialStamp, initialStamp + 1);
        
        System.out.println("ABA 상황에서 CAS 성공?: " + success);
    }
}

이 예제에서 값은 A→B→A로 변경되었지만, 스탬프 값은 계속 증가하므로 초기 스탬프 값으로는 CAS 연산이 실패한다.

실전 사례: 논블로킹 스택 구현

CAS 연산을 활용하여 간단한 논블로킹 스택을 구현해보자:

import java.util.concurrent.atomic.AtomicReference;

public class NonBlockingStack<T> {
    private static class Node<T> {
        final T value;
        Node<T> next;
        
        Node(T value) {
            this.value = value;
        }
    }
    
    private AtomicReference<Node<T>> head = new AtomicReference<>(null);
    
    public void push(T value) {
        Node<T> newHead = new Node<>(value);
        Node<T> oldHead;
        do {
            oldHead = head.get();
            newHead.next = oldHead;
        } while (!head.compareAndSet(oldHead, newHead));
    }
    
    public T pop() {
        Node<T> oldHead;
        Node<T> newHead;
        do {
            oldHead = head.get();
            if (oldHead == null) {
                return null;  // 스택이 비어있음
            }
            newHead = oldHead.next;
        } while (!head.compareAndSet(oldHead, newHead));
        return oldHead.value;
    }
}

이 구현에서 push와 pop 메서드는 모두 CAS 연산을 사용하여 스택의 head를 원자적으로 업데이트한다. 만약 다른 스레드가 중간에 head를 변경하면, CAS 연산이 실패하고 다시 시도한다.

CAS 기반 Java API 구현 사례

자바의 java.util.concurrent 패키지에는 CAS 연산을 기반으로 구현된 다양한 클래스들이 있다:

1. ConcurrentHashMap: 내부 버킷에 대한 업데이트에 CAS 연산 사용
2. ConcurrentLinkedQueue: 논블로킹 큐 구현에 CAS 연산 사용
3. LongAdder: 높은 경쟁 상황에서도 효율적인 카운터를 위해 CAS 사용
4. Semaphore, CountDownLatch: 내부 상태 관리에 CAS 연산 사용

성능 고려사항

CAS 연산은 낮은 경쟁 상황에서는 synchronized보다 훨씬 빠르지만, 높은 경쟁 상황에서는 지속적인 재시도로 인해 성능이 저하될 수 있다. 따라서 경쟁 수준에 따라 적절한 동시성 제어 메커니즘을 선택해야 한다:

• 낮은 경쟁, 짧은 크리티컬 섹션: CAS 기반 원자적 연산 (ex: AtomicInteger)
• 높은 경쟁, 짧은 크리티컬 섹션: 경쟁 완화 기법 적용 (ex: LongAdder)
• 높은 경쟁, 긴 크리티컬 섹션: 락 기반 동기화 (ex: synchronized, ReentrantLock)

결론

CAS(Compare-And-Swap)는 현대 동시성 프로그래밍의 핵심 구성 요소로, 높은 성능의 논블로킹 알고리즘을 구현하는 데 필수적이다. 자바에서는 java.util.concurrent.atomic 패키지를 통해 CAS 기반 연산을 쉽게 사용할 수 있다.

CAS는 데드락 위험 없이 원자적 연산을 제공하지만, ABA 문제와 같은 고유한 문제점도 가지고 있다. 따라서 CAS를 사용할 때는 이러한 문제점을 이해하고 적절한 해결책을 적용하는 것이 중요하다.

동시성 프로그래밍에서는 항상 그렇듯이, 동시성 제어 메커니즘의 장단점을 이해하고 상황에 맞는 적절한 도구를 선택하는 것이 성공적인 멀티스레드 애플리케이션 개발의 핵심이다.