락프리 프로그래밍(lock-free programming)과 CAS란 무엇인가? ABA 문제를 설명하고 언제 사용하는지 설명하라.

Question

IT Interview Practice · Accepted Answer

**락프리 프로그래밍은 뮤텍스 없이 스레드를 조율하며, 원자적 compare-and-swap(CAS) 루프를 사용하여 다른 스레드들이 멈춰도 항상 최소한 하나의 스레드는 진전을 이룹니다.** 어떤 스레드도 락을 쥔 다른 스레드에 의해 블로킹될 수 없습니다.

## CAS

**Compare-and-swap**는 어떤 위치가 여전히 예상한 이전 값을 담고 있을 때만 원자적으로 그 위치를 새 값으로 설정하고, 그렇지 않으면 실패하여 재시도하게 합니다. 락프리 스택, 큐, 카운터 뒤에 있는 기본 요소입니다.

```text
CAS(addr, expected, new):
  if *addr == expected: *addr = new; return true   # atomic, indivisible
  else: return false
```

```java
// Lock-free increment via CAS retry loop
int old, next;
do {
    old  = value.get();
    next = old + 1;
} while (!value.compareAndSet(old, next));  // retry if someone else won
```

## ABA 문제

CAS는 값이 여전히 예상한 것인지만 확인할 뿐, 값이 한 번도 바뀌지 않았는지는 확인하지 않습니다. 당신의 읽기와 CAS 사이에 값이 A → B → A로 변했다면, CAS는 성공하지만 그 아래에서 세상은 이미 바뀌어 있습니다(예: 해제되었다가 재사용된 노드).

```text
Thread 1: read A ............... CAS(A→X) succeeds ✗ (but list changed!)
Thread 2:      pop A, push B, push A again
```

**해결책**: 포인터를 버전 카운터(`AtomicStampedReference`, 태그된 포인터)와 짝지어 A-with-tag-1 ≠ A-with-tag-2가 되게 하거나, 메모리 안전을 위해 해저드 포인터(hazard pointer) / 에폭 회수(epoch reclamation)를 사용하세요.

## 언제 사용하는가

- 락 경합이 지배적인, 뜨겁고 세밀한 공유 상태(카운터, 단일 생산자 큐)나, 스레드가 절대 블로킹되어서는 안 되는 경우(실시간, 시그널 핸들러)에 **사용하세요**.
- 기본 선택으로는 **피하세요**: 제대로 만들기 어렵고, ABA와 메모리 순서 버그를 들이기 쉬우며, 경합이 낮을 때는 좋은 뮤텍스보다 빠르지 않은 경우가 많습니다.

## 왜 중요한가

락프리 구조는 진전 보장을 제공하고 데드락과 우선순위 역전(priority inversion)을 회피하지만, 정확성의 기준이 높습니다. CAS, ABA, 그리고 회수(reclamation) 문제를 아는 것은 당신이 메모리 모델 수준에서 추론할 수 있음을 — 그리고 결정적으로, 언제 그것을 *쓰지 말아야* 하는지 안다는 것을 보여줍니다.

CAS

ABA 문제

언제 사용하는가

왜 중요한가

관련 질문