해설 — 락프리 스택의 ABA 문제

난이도: 상

요약

이 락프리 스택은 고전적인 ABA 문제에 취약하다. Pop이 oldHead를 읽고 oldHead.Next를 떼어내 Interlocked.CompareExchange로 head를 바꾸려는 사이에, 다른 스레드가 그 노드 A를 Pop했다가(혹은 다른 노드 B도 거쳐) 다시 Push하면, head 참조가 A → B → A로 돌아온다. 그러면 첫 스레드의 CAS는 "head가 여전히 A다(같은 참조)"라고 보고 성공하지만, 그 사이 A의 Next는 이미 달라졌을 수 있어 head를 stale한 Next(=이미 빠진 노드)로 덮어쓴다 → 노드 유실, 같은 노드 이중 대여, 리스트 손상. CompareExchange는 참조 동일성(reference identity)만 비교하지 "그동안 안 바뀌었는지"를 모른다. 해법: 버전 카운터(태그)를 묶은 CAS, 또는 노드를 매번 새로 할당해 재사용을 막기 등.

C++판은 같은 ABA지만 노드를 delete하면 use-after-free/이중해제까지 겹친다. C#은 추적 GC 덕분에 use-after-free는 없다(노드가 아직 참조되면 회수 안 됨). 그러나 이 코드처럼 노드를 고정 풀에 재활용하면 같은 참조가 다시 head로 돌아오는 "값 재현(value recurrence)" ABA가 그대로 발생해 리스트 무결성이 깨진다. 즉 C#에서 ABA는 메모리 안전성이 아니라 자료구조 정확성 문제로 나타난다.

핵심 시퀀스: ABA가 터지는 순간

프리리스트 head = A → B → C 라 하자.

1. 스레드 1: Pop 시작. oldHead = A 읽음. next = A.Next = B 읽음(아직 CAS 전).
2. 스레드 1 멈춤(선점).
3. 스레드 2: Pop A (head = B), Pop B (head = C), 그리고 A를 다시 Push (head = A, 단 A.Next = C로 바뀜).
4. 이제 head = A 지만 리스트는 A → C.
5. 스레드 1 재개: CompareExchange(ref _head, next=B, oldHead=A). head가 여전히 A(같은 참조) 라서 성공 → head = B.
6. 하지만 B는 이미 스레드 2가 대여해 쓰고 있는 노드다. 리스트가 깨지고 C가 유실되며 B는 이중 대여된다.

CompareExchange는 5번에서 "참조가 A로 같다"만 확인했을 뿐, 그 사이 두 번의 변경(A→B→...→A)을 감지하지 못한다. 이것이 ABA다.

문제점

(A) n.Next = oldHead 후 참조-CAS만으로 Push (분류: 동시성)

• 증상: Push 자체는 단독으론 맞지만, 노드가 "빠졌다 다시 들어오는" 재순환을 허용해 ABA의 B(되돌아옴)를 만든다.
• 근본원인: head를 참조 값으로만 식별한다. 같은 노드 인스턴스가 재사용되면 "다른 시점인데 같은 참조"가 되어, Pop 측 CAS가 변화를 구분 못 한다. Push 단독 버그는 아니지만 ABA 성립의 한 축. (풀 재사용이 ABA의 전제다.)

(B) oldHead 관측과 CAS 사이의 시간차 (분류: 동시성, 핵심)

• 증상: 관측-결정 사이에 다른 스레드가 노드를 Pop/Push해 head 참조를 원위치시키면, CAS가 오탐 성공.
• 근본원인: "read head → 계산(Next) → CAS"는 원자적 한 덩어리가 아니다. 그 틈에 ABA가 끼어든다. 참조 비교 CAS는 이 틈의 변화를 감지할 수 없다.

(C) Node<T> next = oldHead.Next; — stale Next 역참조 (분류: 동시성/정확성, 가장 위험)

• 증상: oldHead가 그 사이 다른 스레드에 대여돼 Next가 바뀌었다면, 여기서 읽는 next는 stale이다. CAS가 (B)로 성공하면 그 stale 참조가 head가 된다.
• 근본원인: 다른 스레드가 동시에 그 노드의 Next를 만지는데, "내가 보는 동안 이 노드의 Next가 안 바뀐다"는 보장이 없다. C#은 GC라 객체 자체는 살아있어 크래시는 안 나지만, 잘못된 next로 head를 갱신하면 리스트 구조가 손상된다(노드 유실/이중 대여).

Interlocked.CompareExchange는 메모리 배리어(full fence) 의미를 가지므로 이 문제는 메모리 순서(가시성) 문제가 아니라 ABA 문제다. 배리어를 더 강하게 해도 ABA는 안 풀린다.

수정안

방법 1: 버전 태그를 묶은 CAS — ABA 직접 차단

head를 "노드 참조 + 단조 증가 버전"으로 함께 다뤄, 값이 A로 돌아와도 버전이 달라 CAS가 실패하게 한다. C#엔 128비트 CAS가 없으므로, head를 불변 구조체(참조+버전) 로 만들고 Interlocked.CompareExchange<HeadRef>(참조 타입 박스) 또는 인덱스+버전을 long에 패킹한다.

가장 깔끔한 길은 인덱스 기반 + (index, tag)를 64비트 long에 패킹해 일반 Interlocked.CompareExchange(ref long, ...)로 처리하는 것이다(아래 더 나은 설계 2번).

참조를 유지해야 하면 head 상태를 불변 클래스로 감싸 교체한다:

using System.Threading;

public sealed class LockFreeStack<T>
{
    // head 상태: 최상위 노드 + 버전. 불변 객체를 통째로 교체한다.
    private sealed class State { public Node<T> Head; public long Tag; }
    private State _state = new State { Head = null, Tag = 0 };

    public void Push(Node<T> n)
    {
        State cur, next;
        do
        {
            cur = Volatile.Read(ref _state);
            n.Next = cur.Head;
            next = new State { Head = n, Tag = cur.Tag + 1 };   // 버전 증가
        }
        while (Interlocked.CompareExchange(ref _state, next, cur) != cur);
    }

    public Node<T> Pop()
    {
        State cur, next;
        Node<T> head;
        do
        {
            cur = Volatile.Read(ref _state);
            head = cur.Head;
            if (head == null) return null;
            next = new State { Head = head.Next, Tag = cur.Tag + 1 };
        }
        while (Interlocked.CompareExchange(ref _state, next, cur) != cur);
        return head;                                            // 성공
    }
}

State를 매번 새로 할당하므로 CAS가 비교하는 참조가 절대 재현되지 않아 ABA가 사라진다(버전까지 더하면 이중 방어). 트레이드오프: 매 연산마다 State 객체 할당 → GC 압박. 핫패스엔 부담.

방법 2: 인덱스 + 태그 패킹 (할당 0, 권장 — 풀 전용)

노드를 고정 배열로 두고, head를 (int index, int tag)로 하나의 long에 패킹한다. Interlocked.CompareExchange(ref long head, ...)로 ABA(태그)까지 막으며 객체 할당이 0이다.

// head_ 의 상위 32비트 = tag(버전), 하위 32비트 = node index (-1 = null)
long packed = ((long)(tag + 1) << 32) | (uint)nodeIndex;

값이 같은 인덱스로 돌아와도 태그가 달라 CAS가 실패한다. 게임서버 오브젝트 풀에 잘 맞는다. 트레이드오프: 최대 노드 수 32비트로 제한, 인덱스↔객체 매핑 배열 필요.

방법 3: 검증된 동시성 컬렉션

직접 짜지 말고 System.Collections.Concurrent.ConcurrentStack<T>(내부적으로 ABA에 안전한 락프리 구현)나 ConcurrentBag<T>/ObjectPool<T>(MS.Extensions.ObjectPool)를 쓴다. 가장 안전하고 검증됨.

더 나은 설계

1. 검증된 라이브러리 사용(권장): ConcurrentStack<T>, ConcurrentBag<T>, Microsoft.Extensions.ObjectPool. 직접 락프리는 ABA·가시성이 얽혀 버그 표면이 넓다.

2. 풀 전용이면 인덱스 기반 + 고정 배열: 위 방법 2처럼 (index, tag)를 64비트에 패킹하면 일반 Interlocked로 ABA까지 막고 할당 0. 게임서버 핫패스 오브젝트 풀의 정석. 트레이드오프: 최대 노드 수 고정.

3. 경합이 낮으면 그냥 락: Push/Pop이 아주 짧으면 lock/스핀락이 락프리보다 단순하고 충분히 빠를 수 있다. "락프리=항상 빠름"은 오해. 트레이드오프: 고경합에서 확장성 저하.

4. GC가 ABA를 일부 가려준다는 함정: C#은 GC라 노드를 free하지 않아 use-after-free는 없지만, 풀 재사용 시 ABA에 의한 리스트 손상은 그대로다. "GC가 있으니 락프리가 안전하다"는 잘못된 결론. 노드를 재사용하지 않고 매번 새로 할당하면 참조 재현이 없어 ABA가 사라지지만(방법 1 변형), 그건 풀의 목적(할당 절감)과 모순된다.

면접 포인트

1. ABA 문제를 정의하고, 락프리 스택에서 터지는 정확한 인터리빙을 단계별로 설명하라. Interlocked.CompareExchange가 왜 ABA를 막지 못하는가(참조 동일성만 비교)?
2. C++의 ABA(use-after-free 동반)와 C#의 ABA(GC로 메모리 안전, 그러나 리스트 손상)의 차이는? GC가 ABA를 "완전히" 막아주지 못하는 이유는?
3. ABA 해결 기법(버전 태그 묶은 CAS, 인덱스+태그 패킹, 검증된 동시성 컬렉션)의 차이와 트레이드오프는? 태그 비트가 좁으면 무슨 문제가 생기나(랩어라운드)? C#에서 128비트 CAS 부재를 어떻게 우회하나?