CAS (Compare-And-Swap)
CAS(Compare-And-Swap)는 멀티스레드 프로그래밍에서 동기화를 위해 사용되는 원자적 연산이다.
Lock을 사용하지 않고도 여러 스레드가 공유 데이터에 안전하게 접근할 수 있도록 하는 Lock-Free 알고리즘의 핵심 기법이다.
기본 개념
CAS는 세 개의 피연산자를 받는다.
- V (Variable): 업데이트할 메모리 위치
- E (Expected): 기대하는 기존 값
- N (New): 새로운 값
CAS 연산은 다음과 같이 동작한다.
if (V == E) {
V = N;
return true; // 성공
} else {
return false; // 실패
}이 전체 과정이 하나의 원자적 연산으로 수행되어, 중간에 다른 스레드가 끼어들 수 없다.
CAS의 작동 원리
하드웨어 수준의 지원
CAS는 소프트웨어적으로 구현된 것이 아니라 CPU 수준에서 제공하는 원자적 명령어다.
- x86/x64: CMPXCHG (Compare and Exchange) 명령어
- ARM: LDREX/STREX (Load/Store Exclusive) 명령어 쌍
- SPARC: CAS 명령어
- PowerPC: lwarx/stwcx 명령어 쌍
메모리 배리어 (Memory Barrier)
CAS 연산은 메모리 가시성을 보장하기 위해 메모리 배리어를 포함한다.
- 읽기 전: 다른 프로세서의 쓰기 작업이 완료됨을 보장
- 쓰기 후: 현재 쓰기 작업이 다른 프로세서에게 보임을 보장
작동 흐름도
스레드 A 메모리 위치 V (현재 값: 100)
|
|-- 1. V의 값을 읽음 (100)
|
|-- 2. 새로운 값 계산 (101)
|
|-- 3. CAS(V, 100, 101) 시도
| |
| |-- 메모리의 V 값이 여전히 100인가?
| | YES: V를 101로 업데이트 → 성공
| | NO: 다른 스레드가 이미 변경 → 실패, 재시도비슷한 개념
1. TAS (Test-And-Set)
TAS는 가장 단순한 원자적 연산이다.
값을 무조건 true로 설정하고 이전 값을 반환한다.
CAS와의 차이
TAS는 무조건 설정
CAS는 조건이 맞을 때만 설정사용 - 간단한 스핀락(spinlock) 구현
2. FAA (Fetch-And-Add)
FAA는 값을 증가시키고 이전 값을 반환하는 원자적 연산이다.
CAS와의 차이
FAA는 무조건 더하기
CAS는 조건부 업데이트사용 - 카운터 구현에 매우 효율적. Java의 AtomicInteger.getAndAdd()가 내부적으로 사용한다.
ABA 문제
ABA 문제는 다음과 같은 상황에서 발생한다.
시간 스레드 1 메모리 V 스레드 2
t0 V 읽음 (A) A
t1 A V를 B로 변경
t2 B 작업 수행
t3 A V를 다시 A로 변경
t4 CAS(V, A, C) 성공! C
↑ 문제: V가 변하지 않았다고 착각스레드 1은 V의 값이 여전히 A이므로 "변경되지 않았다"고 판단하지만, 실제로는 A → B → A로 변경되었다.
ex) Lock-Free 스택
public class ProblematicStack<T> {
private static class Node<T> {
T item;
Node<T> next;
}
private AtomicReference<Node<T>> head = new AtomicReference<>();
public T pop() {
Node<T> oldHead;
Node<T> newHead;
do {
oldHead = head.get(); // 1. head 읽음 (A)
if (oldHead == null) return null;
newHead = oldHead.next; // 2. A.next 읽음
// 여기서 다른 스레드가:
// - A를 pop
// - B를 pop
// - A를 다시 push (메모리 재사용!)
// 이제 A는 다른 next를 가리킴
} while (!head.compareAndSet(oldHead, newHead)); // 3. 성공하지만 잘못된 상태!
return oldHead.item;
}
}- oldHead.next가 이미 해제된 메모리를 가리킬 수 있음
- 스택이 깨진 상태가 됨
- 메모리 손상 또는 크래시 발생
이러한 위험이 있다.
ABA 문제 해결 방법
버전 스탬프
값과 함께 버전 번호를 저장한다.
값이 A → B → A로 변해도 버전은 1 → 2 → 3으로 계속 증가하므로 변경을 감지할 수 있다.
class VersionedValue {
final Object value;
final int version;
}
// CAS 수행 시
if (current.value == expected.value && current.version == expected.version) {
// 값도 같고 버전도 같음 → 정말 변경되지 않았음!
update(newValue, expected.version + 1);
}이 방법은 구현이 간단하고 효과적이다. 그리고 대부분의 상황에서 잘 동작한다. 단점으로는 버전 번호 오버플로우 가능성 (하지만 int는 21억까지 가능하므로 실제로는 거의 문제 없음)이 있다.
Java는 버전 스탬프 패턴을 위한 전용 클래스(AtomicStampedReference)를 제공한다.
실제 사용 상황
1. 고성능 카운터
웹 서버에서 초당 수만 건의 요청을 카운팅해야 할 때
public class RequestCounter {
private final AtomicLong totalRequests = new AtomicLong(0);
private final AtomicLong activeRequests = new AtomicLong(0);
public void requestStarted() {
totalRequests.incrementAndGet();
activeRequests.incrementAndGet();
}
public void requestCompleted() {
activeRequests.decrementAndGet();
}
}CAS가 적합한 이유
- Lock을 사용하면 모든 요청이 직렬화되어 성능 병목
- CAS는 대부분 1-2번 재시도로 성공
- 3-5배 이상 성능 향상 가능
장단점
| 측면 | CAS | Lock |
|---|---|---|
| 데드락 | 불가능 ✓ | 가능 ✗ |
| 성능 (낮은 경쟁) | 매우 높음 ✓ | 중간 |
| 성능 (높은 경쟁) | 중간 ✗ | 중간 |
| 복잡한 데이터 | 부적합 ✗ | 적합 ✓ |
| CPU 사용 | 높음 ✗ | 낮음 ✓ |
| 메모리 | 효율적 ✓ | Lock 객체 필요 |
| 예측성 | 높음 ✓ | 낮음 |
| 다중 변수 | 불가능 ✗ | 가능 ✓ |
| ABA 문제 | 있음 ✗ | 없음 ✓ |
