해설 — 논블로킹 진행 보장: wait-free · lock-free · obstruction-free

난이도: 상

1. 정의와 위계

진행 보장은 "시스템/스레드가 유한 시간 안에 앞으로 나아가는가"를 형식화한다. 강한 것부터:

wait-free (대기 없음): 모든 스레드가 유한한 자기 단계 수 안에 자신의 연산을 완료한다. 다른 스레드의 속도·중단과 무관하게 개별 스레드의 완료가 보장된다. 가장 강함 → 꼬리 지연 상한이 존재.
lock-free (락 없음): 어떤 스레드는 유한 단계 안에 진행한다. 즉 시스템 전체로는 항상 누군가 전진하지만, 특정 스레드는 무한히 재시도하며 굶을 수 있다(기아 가능). 데드락은 불가능.
obstruction-free (방해 없음): 한 스레드가 다른 스레드의 방해 없이 홀로 실행되면 유한 단계 안에 완료한다. 경합이 있으면 서로 방해해 아무도 진행 못 할 수 있다(라이브락 가능). 가장 약한 논블로킹.

위계: wait-free ⊂ lock-free ⊂ obstruction-free (강함이 약함을 함의). wait-free 이면 lock-free 이고, lock-free 이면 obstruction-free 다. 역은 성립하지 않는다.

blocking(락 기반) 은 이 위계 바깥이다: 락을 쥔 스레드가 중단되면 다른 스레드는 무기한 대기할 수 있어 "시스템 전체의 진행"조차 보장되지 않는다. 논블로킹의 핵심 차별점이 바로 이 지점이다.

2. lock-free 가 강한 이유 vs 여전한 약점

락 기반의 취약점: 락을 쥔 스레드가 선점되거나(스케줄러), 페이지 폴트로 멈추거나, 심지어 크래시하면 그 락을 기다리는 모든 스레드가 정지한다.

우선순위 역전: 저우선순위 스레드가 락을 쥔 채 선점되면, 그 락을 기다리는 고우선순위 스레드가 저우선순위에 발목 잡힌다.
락 호위(lock convoy): 경합이 심하면 스레드들이 락 앞에 줄서 처리량이 급락.
데드락: 락 획득 순서가 어긋나면 상호 대기.

lock-free 의 이점: 공유 상태를 CAS 같은 원자적 read-modify-write 로 갱신하므로, 한 스레드가 아무 곳에서 멈춰도 다른 스레드는 계속 진행한다. 락을 쥔 채 죽는 상황 자체가 없어 데드락·우선순위 역전·호위가 원천 차단된다.

lock-free 의 남은 약점:

기아(starvation): 운 나쁜 스레드가 CAS 에 계속 실패해 무한 재시도할 수 있다(시스템은 진행하지만 그 스레드는 못 함). wait-free 만이 이를 막는다.
라이브락: obstruction-free 수준 설계에서는 서로 재시도만 반복.
재시도 폭증·경합 비용: 코어가 많고 경합이 크면 CAS 실패·캐시 라인 핑퐁으로 성능이 오히려 락보다 나빠질 수 있다.
ABA·안전한 메모리 회수: lock-free 는 해제 시점 판단이 어려워 hazard pointer/RCU/epoch 같은 별도 기법이 필요(별도 문제 참고).

3. CAS 재시도 루프의 등급과 wait-free 로의 승격

전형적 패턴:

do {
    old = load(head);
    new = f(old);
} while (!CAS(head, old, new));

이 루프는 대개 lock-free: CAS 가 실패한다는 것은 다른 스레드의 CAS 가 성공(전진)했다는 뜻이므로, 시스템 전체는 항상 누군가 진행한다.
하지만 wait-free 는 아니다: 특정 스레드는 매번 남에게 밀려 무한 재시도할 수 있어 개별 완료의 상한이 없다.

wait-free 로 끌어올리기:

도움 주기(helping): 각 스레드가 자신의 연산을 공용 디스크립터에 게시하고, 앞선 스레드가 다른 스레드의 미완 연산을 대신 완료(help)해준다. 그러면 어떤 스레드도 무한히 밀리지 않아 유한 상한이 생긴다(구현 복잡·상수 비용 큼).
fetch-and-add 기반 설계: CAS 재시도 대신 fetch_add 같은 무조건 성공하는 원자 연산으로 인덱스를 확보하면(예: 링버퍼 티켓), 재시도가 없어 자연히 wait-free 인 구간을 만들 수 있다. 많은 고성능 큐가 이 아이디어를 쓴다.
트레이드오프: wait-free 는 최악 지연 상한을 주지만, helping 오버헤드로 평균 처리량이 낮아지는 경우가 많다.

4. 게임 서버 적용 판단

틱 루프(단일/소수 소유 스레드): 애초에 공유를 줄여(스레드별 파티션, 더블 버퍼 원자 스왑) 동기화를 없애는 것이 최선. 논블로킹 등급을 따질 자원 자체를 줄인다.
잡 큐/이벤트 큐: 경합이 큰 핫 경로면 lock-free MPMC 큐(또는 fetch-add 기반)가 꼬리 지연을 낮춘다. 다만 검증·메모리 회수 비용이 크므로 검증된 라이브러리를 쓴다.
통계 집계·카운터: fetch_add 기반(사실상 wait-free 한 갱신) 또는 스레드-로컬 누적 후 병합이 단순·빠름.
매치메이킹·복잡한 트랜잭션: 불변식이 여러 자원에 걸치면 lock-free 로 정확히 구현하기가 극히 어렵다 → 락 또는 단일 소유 스레드가 더 안전·현실적.

"락을 무조건 피하는 것이 최선인가?" — 아니다. 경합이 낮으면 잘 만든 뮤텍스가 lock-free 보다 단순하고 빠르며, 최악 지연도 실용 범위다. lock-free 는 (1) 경합이 크고 (2) 스레드 중단 내성이 필요하며 (3) 꼬리 지연 상한이 중요할 때 값어치를 한다. 구현·검증 비용(TSan·모델 체킹·ABA 대응)이 크므로, "측정 → 병목 확인 → 필요한 곳에만" 도입하는 것이 원칙이다.

면접 포인트