문제 13 — 병렬 처리 패턴: Fork-Join·작업 훔치기(work-stealing)·데이터 병렬 vs 작업 병렬

게임 서버의 한 틱(frame) 안에서 AI·물리·관심영역(AoI) 갱신 같은 일을 여러 코어로 펼쳐 처리하는 "잡 시스템(job system)"을 설계한다고 하자. 다음을 설명하라.

1. Fork-Join 모델 — fork(작업을 잘게 나눠 펼침)와 join(결과를 합류·동기화)이 무엇인지, "작업 그래프(의존성 DAG)"로 한 틱을 어떻게 표현하는지 설명하라. join 지점이 왜 동기화 비용·직렬 구간이 되는지도.

2. 작업 훔치기(work-stealing) 스케줄러 — 워커마다 자기 덱(deque)을 두고, 자기 작업은 한쪽 끝에서, 남의 작업은 반대쪽 끝에서 훔치는 구조를 설명하라. 왜 자기 것은 LIFO, 훔치는 건 FIFO 로 꺼내는 게 캐시 지역성·경합 측면에서 유리한가? 중앙 단일 큐(concurrency/problem6 스레드풀)와 비교한 장단점은?

3. 데이터 병렬 vs 작업 병렬 — 같은 연산을 많은 데이터에 적용하는 데이터 병렬(예: 1만 엔티티 이동 적분)과, 서로 다른 작업을 동시에 돌리는 작업 병렬(예: 물리·AI·네트워크 송신)을 구분하라. 각각 어떤 분할(파티셔닝) 전략이 맞는지.

4. 입자도(granularity)와 오버헤드 — 작업을 너무 잘게 쪼개면(과도한 fork) 무엇이 문제이고, 너무 크게 두면 무엇이 문제인가? 적정 청크 크기를 정하는 기준과 "순차 임계값(sequential cutoff)" 개념을 설명하라.

5. 함정 — 잡 시스템에서 (a) 블로킹 I/O 작업을 워커에 올리면 왜 위험한가, (b) 거짓 공유(false sharing)·오버서브스크립션(oversubscription)이 어떻게 확장성을 깎는가, (c) 작업 간 공유 상태 변경의 동기화를 어떻게 최소화하는가(분할 소유·결과 병합)를 논하라.