문제 11 — 락프리 자료구조의 안전한 메모리 회수 (Hazard Pointer / RCU / Epoch)

락프리(lock-free) 스택/큐를 구현했다고 하자. CAS 로 노드를 빼내는(pop) 로직 자체는 맞췄는데, "빼낸 노드를 언제 free 해도 되는가" 라는 별개의 문제가 남는다.

다음에 답하라.

1. 문제 정의. 락프리 자료구조에서 한 스레드가 노드를 논리적으로 제거(unlink)한 직후 delete/free 하면 왜 위험한가? 다른 스레드의 관점에서 어떤 일이 벌어질 수 있는지 (use-after-free) 구체적으로 설명하라. 이 "메모리 회수 문제" 가 ABA 문제와 어떻게 다른지 도 구별하라.

2. 단순 해법의 한계. "노드마다 원자적 참조계수를 둔다" 또는 "GC 언어를 쓴다" 는 접근의 장단점은? C++ 에서 shared_ptr 로 락프리 자료구조를 만들 때의 어려움(원자적 shared_ptr 연산 비용, 더블 워드 CAS 등)을 언급하라.

3. 세 가지 대표 기법 — Hazard Pointer, Epoch-Based Reclamation(EBR/QSBR), RCU — 각각이 "안전하게 회수 가능한 시점" 을 어떻게 판단하는지 핵심 아이디어를 설명하고, 읽기 경로 오버헤드/메모리 사용(지연 회수량)/구현 복잡도 측면에서 비교하라.

4. 실무 선택. MMORPG 서버의 읽기 다수·쓰기 소수(read-mostly) 자료구조(예: 존의 엔티티 인덱스, 설정/라우팅 테이블)에 어떤 기법이 적합한가? 왜 그런지 트레이드오프로 설명하라.