작업 훔치기 스케줄러 (Work-Stealing)

CPU 코어가 8개인데 일감이 한 워커에게만 몰려 있으면 나머지 7개는 논다. 그렇다고 큐 하나를 모두가 붙잡으면 그 잠금(lock)이 병목이 된다. 작업 훔치기는 워커마다 자기 덱(deque)을 두고, 주인은 한쪽 끝(아래)에서 넣고 빼며, 일이 떨어진 워커는 다른 워커의 반대쪽 끝(위)에서 작업을 훔쳐 온다. 잠금 경쟁은 거의 없고, 부하는 저절로 고르게 퍼진다. Java ForkJoinPool, Go 런타임, Rust Rayon, Tokio가 모두 이 방식이다.

스케줄러 시뮬레이터

실행 중인 워커 훔치기 시도 유휴(놀고 있음) 덱에 쌓인 작업 위쪽 끝 = 도둑이 훔치는 곳, 아래쪽 끝 = 주인이 넣고 빼는 곳

작업 훔치기 ON (끄면 전역 큐 1개 + 잠금 경쟁)

워커(스레드) 수 4

작업이 하위 작업으로 갈라질 확률 55%

스텝

완료 작업

처리율(작업/스텝)

0.00

훔치기 횟수

유휴 스텝 합

모든 초기 작업이 W0 한 명에게 쌓여 있습니다. 한 스텝 또는 자동 재생으로 나머지 워커가 일감을 훔쳐 균형을 맞추는 과정을 지켜보세요.

워커별 완료 작업 수 — 부하가 고르게 퍼지는가

훔치기 ON: 막대 높이가 금방 비슷해진다 — 놀던 워커가 스스로 일감을 가져가 부하가 균형을 이룬다. 훔치기 OFF(전역 큐): 완료 수는 비슷할 수 있어도, 한 번에 한 워커만 큐 잠금을 잡으므로 처리율이 낮고 유휴 스텝이 폭증한다. 두 모드를 번갈아 실행해 처리율과 유휴 스텝 수치를 비교해 보라.

왜 주인은 아래(LIFO), 도둑은 위(FIFO)에서 가져갈까

동작	덱의 어느 끝	이유
주인이 push / pop	아래쪽(tail) — LIFO	방금 만든 하위 작업을 바로 실행 → 데이터가 캐시에 뜨거울 때 처리. 스택처럼 지역성이 좋다. 게다가 자기 끝만 만지므로 대부분 잠금 없이 처리(단일 소유자).
도둑이 steal	위쪽(head) — FIFO	가장 오래된 = 대체로 가장 큰 작업을 가져온다 → 한 번 훔치면 한동안 자급자족, 훔치기 빈도 ↓. 주인이 만지는 끝과 반대쪽이라 충돌이 거의 없다(양끝 lock-free 덱).

즉 같은 덱이라도 양 끝이 서로 다른 정책으로 동작한다. 주인과 도둑이 물리적으로 떨어진 끝을 쓰기 때문에 경쟁 구간이 덱에 원소가 1개 남았을 때로 좁혀지고, 그때만 CAS로 조정한다.

전역 큐 1개의 문제

잠금 병목: 8코어가 동시에 queue.pop()을 노려도 한 번에 하나만 통과. 나머지는 대기.
캐시 핑퐁: 큐 머리 부분 캐시 라인이 코어 사이를 계속 오간다(false sharing).
지역성 상실: 내가 만든 하위 작업을 남이 가져가 처리 → 캐시 미스.
장점: 구현이 단순하고, 부하는 자동으로 고르게 나뉜다(코어 수가 적으면 충분).

작업 훔치기의 이점

거의 무잠금: 평소엔 각자 자기 덱만 → 경쟁 없음. 훔칠 때만 원자적 연산.
자동 부하 분산: 노는 워커가 스스로 일감을 찾아간다(중앙 조정자 불필요).
지역성: 방금 만든 하위 작업은 대개 그 워커가 계속 처리.
이론 보장: 재귀 분할(fork-join) 작업에서 기대 실행 시간 ≈ T₁/P + O(T∞) (Cilk).

워커 루프 (의사코드)

# 워커마다 자기 소유의 양끝 덱(deque)을 하나씩 가진다
class Worker:
    deque = Deque()                 # 아래(bottom)=주인, 위(top)=도둑

    def run(self, pool):
        while pool.running:
            task = self.deque.pop_bottom()      # LIFO, 대개 lock-free
            if task is None:
                task = self.steal_from_random_victim(pool)   # 남의 덱 위에서
            if task is None:
                pool.on_idle(self); continue       # 잠깐 쉬거나 park
            for child in task.execute():        # 작업이 하위 작업을 fork
                self.deque.push_bottom(child)  # 내가 만든 건 내가 먼저

    def steal_from_random_victim(self, pool):
        v = random.choice(pool.workers)      # 무작위 피해자
        return v.deque.steal_top()          # FIFO, 실패하면 None

실제 구현(Chase-Lev 덱)은 push_bottom/pop_bottom은 원자적 스토어만, steal_top은 CAS 한 번으로 처리해 주인 경로를 거의 공짜로 만든다.

실제로 어디에 쓰이나

런타임	작업 훔치기로 하는 일
Java ForkJoinPool / parallelStream	재귀 분할 작업을 코어에 분배. `CompletableFuture` 기본 풀.
Go 런타임 (GMP)	P마다 로컬 런큐 + 전역 런큐. 빈 P는 다른 P의 런큐 절반을 훔침.
Rust: Rayon / Tokio	Rayon은 데이터 병렬 `par_iter`, Tokio는 async 태스크 멀티스레드 스케줄러.
Cilk / OpenMP tasks	작업 훔치기 스케줄링의 원조. `cilk_spawn` / `#pragma omp task`.
.NET TPL / TBB (C++)	`Task.Run`, `parallel_for` 등 병렬 라이브러리의 기반.