모범답안 — 락 vs lock-free, CAS, ABA 문제, 잡큐/Actor 모델

난이도: 상

핵심 답변

lock-free: 락(상호 배제) 없이, 원자 연산(주로 CAS)만으로 공유 자료구조를 갱신하는 기법. 정의상 시스템 전체로 보면 항상 어떤 스레드는 진전한다(한 스레드가 멈춰도 전체가 막히지 않음 → 데드락/우선순위 역전 면역). 단점: 구현이 매우 어렵고, ABA·메모리 회수(누가 노드를 free하나) 문제, 경합이 심하면 CAS 재시도 폭주로 락보다 느릴 수 있다. "lock-free = 빠름"은 오해다.
CAS: CAS(addr, expected, desired) — *addr가 expected와 같으면 desired로 바꾸고 성공(true), 다르면 아무것도 안 하고 실패. 읽은 값이 그대로 유지됐을 때만 갱신하는 원자 RMW. 실패하면 새 값을 다시 읽어 재시도(CAS 루프).
ABA: 값이 A→B→A로 돌아오면, CAS는 "안 바뀌었다"고 착각해 성공한다. 그러나 그 사이 자료구조 상태(특히 포인터가 가리키던 노드)가 바뀌었을 수 있어, 해제된 노드를 다시 연결하는 등 손상이 난다. 해결: 버전 태그(태그드 포인터)/세대 카운터, hazard pointer, epoch-based reclamation.
잡큐/Actor: 공유 상태를 단일 스레드가 독점하고 다른 스레드는 메시지(잡)만 큐로 전달 → 상태 접근에 동시성이 없어 락이 필요 없다. 동시성 버그를 설계로 제거.

깊이 있는 설명 (메커니즘, 왜)

CAS 루프 예 (lock-free 최대값 갱신)

std::atomic<long> maxHit{0};
void report(long v) {
    long cur = maxHit.load(std::memory_order_relaxed);
    while (v > cur &&
           !maxHit.compare_exchange_weak(cur, v,
                std::memory_order_release, std::memory_order_relaxed)) {
        // 실패하면 cur에 최신값이 다시 담겨 루프 재시도
    }
}

compare_exchange_weak은 실패 시 cur를 현재 값으로 갱신해주므로 루프와 궁합이 좋다(가짜 실패 허용, 루프 안에서 저렴).

ABA가 스택에서 터지는 시나리오

lock-free 스택 pop:

old_top = head;           // A (노드 X를 가리킴)
next = old_top->next;     // X->next 읽음 (노드 Y)
CAS(head, old_top, next); // head가 여전히 X면 Y로 교체

T1이 old_top = X, next = Y까지 읽고 선점됨.
T2가 X pop, Y pop, 그리고 X를 다시 push(메모리 재사용). 이제 head=X지만 X->next는 이전과 다름(예: Z).
T1 재개. CAS는 head가 여전히 X(주소 같음)라 성공. head를 옛 next=Y로 바꾼다. 그러나 Y는 이미 pop되어 해제됐을 수 있다 → 해제된 메모리를 스택 top으로 복원. 손상.

핵심: CAS는 포인터 비트만 비교할 뿐 "그 사이 무슨 일이 있었나"를 모른다. A로 돌아오면 속는다.

ABA 해결책

태그드 포인터(버전 카운터): 포인터 옆에 단조 증가 카운터를 붙여 (ptr, tag)를 한 번에 CAS(double-width CAS, x86-64의 cmpxchg16b). A→B→A여도 tag가 달라 CAS 실패. 가장 흔한 실무 해법.
Hazard pointer: 각 스레드가 "내가 지금 보고 있는 포인터"를 공표하고, 회수자는 공표된 포인터는 free하지 않는다 → 재사용 자체를 막아 ABA·use-after-free 동시 해결.
Epoch/RCU: 읽기 구간을 epoch로 묶고, 모든 스레드가 지나간 뒤에야 회수.
회피: 인덱스 기반 ring buffer(주소 재사용 없음)나, 애초에 lock-free 대신 단일 스레드(Actor)로 가기.

설계 A vs 설계 B (시나리오)

설계 A(필드별 락 + IO 스레드 직접 수정)의 위험:

데드락: 여러 필드 락을 잡는 순서가 핸들러마다 달라지면 순환 대기. 락이 잘게 많을수록 순서 관리가 지옥.
경합/오버헤드: 같은 룸의 4명 패킷이 동시에 락을 두드려 직렬화 + 락 진입/이탈/캐시 라인 핑퐁 비용. 잘게 쪼갠 락은 획득 비용이 누적.
일관성 깨짐: "HP 깎고 + 사망 처리 + 드랍 생성"이 한 트랜잭션이어야 하는데 필드별 락이면 중간 상태가 다른 스레드에 노출. 멀티 필드 불변식을 지키려면 결국 큰 락이 필요해져 세분화 의미가 사라짐.

설계 B(단일 스레드 룸/Actor)가 막는 방식:

룸 상태를 워커 스레드 1개만 만지므로 동시 접근이 0 → race condition·데드락·가시성 문제 원천 소멸. 룸 상태에 락이 필요 없다.
IO 스레드와 워커 사이의 큐 경계에서만 동기화(MPSC 큐의 enqueue). 핸들러는 평범한 단일 스레드 코드처럼 짜면 됨 → 버그 적고 추론 쉬움.
멀티 필드 불변식도 한 잡 안에서 순차 실행되니 자연히 보장.

응용/실무 연결 (게임서버에서)

표준 구조: IO 스레드(N개) → 룸별 MPSC 잡큐 → 룸 워커(1개)가 틱마다 큐 비우고 로직 실행. 이게 사실상 Actor 모델. 룸 간에는 상태 공유가 없으니 룸들은 서로 독립적으로 병렬 실행된다.
코어 확장: 룸이 단일 스레드여도 룸이 많으면 룸들을 여러 워커 스레드/스레드풀에 분산해 코어를 다 쓴다. 즉 "룸 내부는 직렬, 룸 사이는 병렬". 한 룸이 한 코어를 다 못 채우면 여러 룸을 한 워커에 묶어 라운드로빈 처리.
lock-free는 큐 경계에만: 룸 내부는 단일 스레드라 lock-free가 필요 없고, IO→룸 잡큐 같은 MPSC 지점에만 검증된 lock-free 큐를 쓴다. 직접 lock-free 자료구조를 만들기보다 검증된 라이브러리(예: moodycamel, .NET Channel/ConcurrentQueue)를 쓰는 게 안전.

흔한 오답·함정

"lock-free는 락이 전혀 없다" → 하드웨어 원자 명령(lock cmpxchg)을 쓴다. "OS 수준 블로킹 락이 없다"는 의미. 또 wait-free(모든 스레드가 유한 단계 보장)와 lock-free(전체 진전 보장)는 다르다.
"lock-free가 항상 빠르다" → 경합이 높으면 CAS 재시도가 폭증해 락보다 느릴 수 있다. 측정이 답.
"ABA는 포인터에서만" → 값 의미가 순환하는 모든 CAS에서 가능. 인덱스/시퀀스에도 발생. 태그/세대로 방어.
"단일 스레드 룸은 멀티코어를 못 쓴다" → 룸 단위로 병렬화하면 코어를 다 쓴다. 단일 스레드인 건 룸 하나의 내부일 뿐.
"Actor 모델이면 동기화가 0" → 큐 경계의 enqueue/dequeue, 그리고 룸 간 메시지 전달에는 여전히 동기화가 있다. 다만 상태 공유 동기화가 사라진다.

꼬리질문 대비

Q: lock-free에서 "누가 노드를 free하나"가 왜 어려운가? A: 어떤 스레드가 노드를 pop해 해제하려는 순간, 다른 스레드가 그 노드를 막 읽고 있을 수 있다(use-after-free). 언제 안전하게 회수할지가 핵심 난제이며 hazard pointer/epoch/RCU가 이를 푼다. GC 언어(C#)는 GC가 이 문제를 상당 부분 가려준다.
Q: 단일 스레드 룸에서 한 잡이 오래 걸리면(무거운 AI 계산) 어떻게 하나? A: 룸 틱이 밀려 같은 룸의 다른 플레이어 처리가 지연된다. 무거운 작업은 별도 워커풀에 비동기로 던지고 결과만 잡으로 돌려받거나(룸 상태는 결과 적용 시점에만 만짐), 계산을 틱에 분할(time-slice)한다.
Q: MPSC 큐와 SPSC 큐의 차이, 룸 잡큐는 어느 쪽? A: SPSC는 생산자/소비자 각 1개라 가장 단순·빠름(인덱스 두 개 + acquire/release). 룸 잡큐는 여러 IO 스레드가 넣고 룸 워커 1개가 빼므로 MPSC다. enqueue 측에 CAS 기반 동기화가 필요하다.

4. 락 vs lock-free, CAS, ABA 문제, 잡큐/Actor 모델