해설 — Interlocked.CompareExchange 기반 락프리 갱신과 ABA

난이도: 상

요약

CAS 루프는 "현재 값을 읽고(observed), 원하는 값을 계산하고, 읽은 값이 그대로일 때만 원자적으로 교체"하는 낙관적 갱신이다. 교체가 실패하면(그 사이 남이 바꿈) 다시 읽어 재시도한다. 락은 없지만 경합 시 재시도가 있으므로 lock-free(전체 진행 보장)이지 wait-free(개별 진행 보장)는 아니다. Pop 은 ABA 취약점이 있다.

핵심 개념

Interlocked.CompareExchange(ref loc, newVal, comparand) = 원자적으로 "loc == comparand 면 loc = newVal", 반환값은 항상 연산 직전의 loc(옛 값). 반환값 == comparand 면 성공, 아니면 실패(누가 먼저 바꿈).
하드웨어 CAS(x86 lock cmpxchg) 1개 명령으로 비교+교체가 불가분.

단계별 내부 동작

UpdatePeak 의 CAS 루프 — observed 를 읽고 후보가 더 크면 CAS 로 교체 시도. 다른 스레드가 그 사이 _peak 을 바꿨다면 CAS 반환값 ≠ observed → 루프가 최신 값으로 다시 읽어 재검사·재시도. 이렇게 "load→비교→store" 의 check-then-act 를 한 원자 연산(CAS) 으로 좁혀 잠금 없이 조건부 최댓값을 안전하게 갱신한다. (Interlocked.Read 는 64비트를 32비트 플랫폼에서도 찢김 없이 읽기 위함.)
메모리 순서 — Interlocked 연산은 full barrier(획득+해제) 로, 그 전후 메모리 접근의 재정렬을 막고 다른 코어에 가시성을 보장한다. 단순 volatile 읽기는 읽기 시점의 최신값 관측은 돕지만 "읽고→비교→쓰기"를 원자적으로 묶지 못한다. 두 스레드가 같은 값을 읽고 각자 쓰면 갱신 유실(lost update)이 나므로, 조건부 갱신엔 CAS 가 필수다.
Pop 의 ABA — CAS 는 "값이 같은가"만 보지 "그 사이 바뀌었다 되돌아왔는가"는 모른다. 재현:
- 스택 A -> B -> C. 스레드 T1 이 Pop: old = A, old.Next = B 를 읽고 CAS 직전에 선점됨.
- 스레드 T2 가 Pop A(head=B), Pop B(head=C), 그리고 다시 Push A(head=A, 이때 A.Next = C). 이제 스택은 A -> C.
- T1 재개: CAS(_head, old.Next(=B), old(=A)) — head 가 다시 A 라 성공 → _head = B. 그러나 B 는 이미 제거된(재사용/GC 후보) 노드라 스택이 손상 (이미 pop 된 B 가 되살아나고 C 가 유실). 값은 A 로 "같아" 보였지만 그 사이 구조가 바뀐 것이 ABA.
- .NET 은 GC 덕에 노드 메모리 재사용으로 인한 use-after-free 는 없지만, 논리적 ABA(같은 참조가 제거됐다 다시 push)로 자료구조가 깨진다.
lock-free vs wait-free — 이 코드는 lock-free: 최소 한 스레드는 항상 진행(누군가의 CAS 는 성공)하지만, 특정 스레드는 무한히 재시도할 수 있어 개별 진행 보장(wait-free)은 아니다.

해결(ABA)

버전 태그: (pointer, counter) 를 함께 CAS(태그드 포인터/Interlocked 128비트, 또는 인덱스+세대). push/pop 마다 counter 증가 → 되돌아와도 태그가 달라 CAS 실패.
해저드 포인터/에폭 기반 회수로 재사용 시점 통제.
실무에선 대개 ConcurrentStack<T>(내부적으로 이 문제를 처리) 사용이 정답.

흔한 오해·함정

CAS 반환값을 "성공 여부(bool)"로 오해 → 실제로는 옛 값. != comparand 로 판정.
"GC 언어라 ABA 없음" → 메모리 안전은 확보되나 논리적 ABA 는 여전히 발생.
Interlocked 를 volatile 로 대체 가능하다는 오해(원자 RMW 를 못 함).

면접 포인트

CAS 루프가 lost update 를 막는 원리와 반환값 의미.
Interlocked 의 배리어 의미(왜 volatile 로 대체 불가).
ABA 의 정확한 인터리빙과 태그드 포인터/세대/해저드 포인터 해법.