문제 20 — 논블로킹 진행 보장(progress guarantees): wait-free · lock-free · obstruction-free

멀티코어 게임 서버에서 "논블로킹(non-blocking)" 자료구조를 논할 때, 단순히 "락을 안 쓴다"를 넘어 진행 보장(progress guarantee) 의 등급을 구분해야 한다. 다음을 설명하라.

1. 정의와 위계: wait-free, lock-free, obstruction-free 를 각각 정의하고, 이들 사이의 포함 관계(무엇이 무엇을 함의하는지)를 설명하라. 또한 "blocking(락 기반)" 이 진행 보장 관점에서 어디에 위치하는지도 밝혀라.

2. 왜 lock-free 가 데드락·우선순위 역전·호위(convoy)에 강한가: 락 기반 설계가 스레드 중단(선점·페이지 폴트·크래시) 시 어떤 문제를 겪는지와, lock-free 가 이를 어떻게 회피하는지 대비하라. 반대로 lock-free 가 여전히 겪을 수 있는 문제(라이브락·기아·재시도 폭증)는 무엇인가.

3. CAS 재시도 루프의 등급: 전형적인 while(!CAS(...)) { 재시도 } 루프가 왜 대체로 lock-free 이지만 wait-free 는 아닌지, 그리고 이를 wait-free 로 끌어올리는 기법(예: 도움 주기 helping, fetch-and-add 기반 설계)의 아이디어를 설명하라.

4. 게임 서버 적용 판단: 실시간 틱 루프·매치메이킹·통계 집계·잡 큐 등에서 wait-free/lock-free/락 기반 중 무엇을 택할지, 지연 분포(꼬리 지연 tail latency)·처리량·구현 복잡도·검증 비용 관점에서 트레이드오프를 논하라. "락을 무조건 피하는 것이 최선인가?"에 답하라.

(모범답안은 answer.md 참고.)