락 없이 안전하게 — 락-프리 자료구조는 어떻게 동작할까?

뮤텍스 락은 단순하고 강력하지만 본질적으로 블로킹이에요. 한 스레드가 락을 쥔 채 스케줄에서 밀리거나(preempt), 페이지 폴트가 나거나, 심지어 죽으면 그 락을 기다리는 모든 스레드가 함께 멈춰요. 락 하나의 장애가 시스템 전체 진행을 막는 셈이죠. 락-프리는 "어떤 스레드가 어느 순간 멈춰도, 시스템 전체는 계속 전진한다"를 목표로 합니다.

락-프리의 심장은 CAS(Compare-And-Swap)예요. "이 메모리가 내가 본 값(expected)이 맞으면 새 값으로 바꾸고, 아니면 실패를 알려라"를 원자적으로 수행하는 CPU 명령(CMPXCHG)이죠. 자바에선 AtomicInteger.compareAndSet(expect, update) 같은 형태로 노출돼요.

AtomicInteger v = new AtomicInteger(0);

// "지금 값이 0이면 1로 바꿔" — 성공하면 true
boolean ok = v.compareAndSet(0, 1);

// 락-프리 증가의 전형: 읽고 → 계산 → CAS, 실패하면 재시도
int cur, next;
do {
    cur  = v.get();
    next = cur + 1;
} while (!v.compareAndSet(cur, next)); // 경합에서 밀리면 다시 시도

해결의 핵심은 값에 버전(스탬프)을 붙여 "값+버전"을 함께 비교하는 거예요. 값이 A로 돌아와도 버전은 증가했으니 CAS가 옛 스냅샷을 거부합니다. 자바는 AtomicStampedReference<V>(int 스탬프)와 AtomicMarkableReference<V>(boolean 마크)를 제공해요.

// 참조 + int 스탬프를 한 번에 CAS → ABA 차단
AtomicStampedReference<Node> ref =
        new AtomicStampedReference<>(head, 0);

int[] stampHolder = new int[1];
Node cur = ref.get(stampHolder);      // 값과 스탬프를 함께 스냅샷
int  stamp = stampHolder[0];

// 값이 cur이고 && 스탬프도 그대로일 때만 성공. 성공 시 스탬프 +1
boolean ok = ref.compareAndSet(cur, next, stamp, stamp + 1);

Treiber 스택(1986)은 락-프리 자료구조의 "Hello World"예요. 단일 연결 리스트의 head 포인터 하나만 CAS로 갈아끼우면 push/pop이 됩니다. push는 새 노드의 next를 현재 head로 걸어두고 head를 새 노드로 CAS, pop은 head를 head.next로 CAS하죠.

class TreiberStack<E> {
    static final class Node<E> {
        final E item; Node<E> next;
        Node(E item){ this.item = item; }
    }
    private final AtomicReference<Node<E>> head = new AtomicReference<>();

    void push(E item) {
        Node<E> n = new Node<>(item);
        Node<E> cur;
        do {
            cur = head.get();
            n.next = cur;                         // 새 노드를 현재 head 위에 얹고
        } while (!head.compareAndSet(cur, n));     // head를 n으로 교체 (실패 시 재시도)
    }

    E pop() {
        Node<E> cur, next;
        do {
            cur = head.get();
            if (cur == null) return null;          // 비어 있음
            next = cur.next;
        } while (!head.compareAndSet(cur, next));   // head를 next로 교체
        return cur.item;
    }
}

큐는 스택보다 어려워요. 양 끝(head=dequeue, tail=enqueue)을 각각 갱신해야 하니까요. Michael & Scott(1996) 큐는 더미(sentinel) 노드를 두고, enqueue를 두 번의 CAS로 나눠 우아하게 해결합니다.

핵심 통찰은 tail이 "뒤처질(lagging)" 수 있다는 걸 정상으로 허용하는 거예요. ①에서 next 연결에는 성공했지만 ②의 tail 전진 전에 스레드가 멈춰도 큐는 일관성 있는 중간 상태에 있어요. 다른 스레드가 tail.next != null인 걸 발견하면, 자기 일을 하기 전에 남의 tail을 대신 전진시켜(helping) 줍니다. 어느 한 스레드가 멈춰도 전체는 전진하는 락-프리의 전형이에요.

// Michael-Scott enqueue의 뼈대 (개념 코드)
void enqueue(E item) {
    Node<E> n = new Node<>(item);
    while (true) {
        Node<E> last = tail.get();
        Node<E> next = last.next.get();
        if (last == tail.get()) {                 // tail이 그대로인지 재확인
            if (next == null) {                    // 진짜 마지막이면
                if (last.next.compareAndSet(null, n)) {  // ① next 연결
                    tail.compareAndSet(last, n);          // ② tail 전진(실패해도 OK)
                    return;
                }
            } else {
                tail.compareAndSet(last, next);    // 남이 뒤처뜨린 tail을 도와서 전진
            }
        }
    }
}

여기까지 읽고 "멋지다, 직접 만들어봐야지"라는 마음이 들 수 있어요. 하지만 실무의 정답은 대개 "직접 만들지 마라"입니다. 락-프리 자료구조는 메모리 순서·ABA·재시도·false sharing이 얽혀 정확히 짜기가 극도로 어렵고 테스트도 힘들어요. Doug Lea가 수년간 다듬은 java.util.concurrent를 쓰세요.