비교-교환 (Compare-And-Swap)

1. CAS 명령이 하는 일

CAS는 아래 세 단계를 중간에 누구도 끼어들 수 없게(원자적으로) 한 번에 처리합니다.

# 하드웨어가 원자적으로 실행 — 이 블록은 쪼개지지 않는다
def CAS(addr, expected, new):
    if memory[addr] == expected:     # 내가 본 값이 그대로인가?
        memory[addr] = new             # 그렇다 → 바꾼다
        return True                   # 성공
    return False                      # 누가 먼저 바꿨다 → 실패, 아무것도 안 함

x86에서는 LOCK CMPXCHG, ARM에서는 LDREX/STREX(로드-링크/스토어-조건부) 명령 쌍이 이 역할을 합니다. C++ std::atomic::compare_exchange_weak, Java AtomicInteger, Go atomic.CompareAndSwap, Rust AtomicUsize 가 모두 이 명령으로 구현됩니다.

2. CAS 재시도 루프 — 락-프리의 심장

CAS 한 번은 실패할 수 있습니다. 그래서 성공할 때까지 반복합니다: ① 현재 값을 읽고 ② 원하는 새 값을 계산하고 ③ CAS로 바꿔 본다. ③이 실패하면 그 사이 누군가 값을 바꾼 것이므로 ①부터 다시 합니다.

# 원자적 증가 (잠금 없이)
def atomic_inc(counter):
    while True:
        cur = counter.load()          # ① 읽기
        nxt = cur + 1               # ② 계산
        if counter.CAS(cur, nxt):     # ③ 교환 시도
            return nxt                 #    성공하면 탈출
        # 실패 → 다른 스레드가 먼저 바꿈 → 루프 처음으로

3. 직접 돌려 보기 — 카운터 경쟁

여러 스레드가 공유 카운터를 각각 목표 횟수만큼 올립니다. 각 스레드는 값을 읽고(READ), +1을 교환 시도(CAS) 합니다. 그 사이 다른 스레드가 값을 바꿔 놨으면 CAS가 실패(RETRY) 하고 다시 읽습니다. 원자적 CAS 체크를 끄면 CAS가 검사 없이 무조건 덮어써서 갱신 유실이 발생합니다.

원자적 검사를 켜면 실제 값은 항상 기대값과 일치합니다. 다만 스레드가 많고 충돌이 잦을수록 재시도 횟수가 늘어납니다(경합, contention). 검사를 끄면 두 스레드가 같은 cur를 읽고 똑같이 cur+1을 써서 한 번의 증가가 통째로 사라집니다 — 이것이 갱신 유실입니다.

4. ABA 문제 — CAS의 함정

CAS는 "값이 expected와 같은가"만 봅니다. 그런데 값이 A → B → A 로 돌아왔다면? CAS는 "안 변했다"고 착각하고 성공합니다. 실제로는 그 사이 세상이 바뀌었는데도요. 락-프리 스택에서 특히 위험합니다.

ABA 막기

5. 락 vs 락-프리

진행 보장의 강도는 wait-free(모든 스레드가 유한 스텝 내 완료) > lock-free(전체 중 최소 하나는 항상 전진) > obstruction-free(혼자 남으면 완료) 순입니다. 대부분의 실전 자료구조는 lock-free를 목표로 합니다.