271. 스레드 풀 스케줄링 락 경합 (Work Stealing)

⚠️ 이 문서는 멀티코어 환경에서 여러 스레드가 하나의 작업 대기열(Task Queue)에 동시에 접근하려다 발생하는 심각한 병목 현상을 해결하기 위해, 각 코어마다 전용 대기열을 두고 남의 큐에서 몰래 작업을 훔쳐오는 기발하고 혁신적인 부하 분산 알고리즘인 'Work Stealing(작업 훔치기)'을 다룹니다.

핵심 인사이트 (3줄 요약)

  1. 본질: 멀티 스레드 프로그래밍에서 모든 스레드가 단 하나의 전역 큐(Global Queue)에서 작업을 꺼내가려 하면 '큐 락(Queue Lock)' 경합 때문에 시스템 전체가 느려지는데, Work Stealing은 각 스레드에게 독립적인 로컬 큐를 부여하여 락 경합을 원천적으로 회피하는 아키텍처다.
  2. 가치: 자신의 큐에 일이 다 떨어져서 놀고 있는 잉여 스레드(Thief)가, 바쁘게 일하고 있는 다른 스레드(Victim)의 큐 뒷부분에서 작업을 몰래 훔쳐옴(Steal)으로써, **동기화 오버헤드 없이 완벽한 로드 밸런싱(부하 분산)**을 달성한다.
  3. 융합: Java의 ForkJoinPool, C++의 TBB, Go, Rust의 고루틴 스케줄러 등 현대의 모든 고성능 병렬 처리 프레임워크의 심장부에 기본 탑재되어 매니코어(Many-core) 시대의 성능을 극한으로 끌어올리고 있다.

Ⅰ. 개요 및 병목의 근원 (Context & Necessity)

우리가 흔히 아는 스레드 풀(Thread Pool)의 기본 구조는 단순하다. 중앙에 거대한 '할 일 목록(Global Queue)'이 하나 있고, 100명의 일꾼(Thread)이 달려들어 일을 하나씩 빼간다.

  • 최악의 병목 (Lock Contention):
    • 큐(Queue)는 여러 명이 동시에 빼가면 엉키기 때문에, 누군가 하나 뺄 때마다 전체 큐에 **락(Lock)**을 걸어야 한다.
    • 100개의 코어가 일을 빼가려고 동시에 큐에 달려들면, 1개 코어만 일하고 99개 코어는 락이 풀리길 기다리며 줄을 서서 논다. (배보다 배꼽이 더 큰 동기화 오버헤드)

이 문제를 해결하기 위한 발상의 전환이 "전체 큐를 쪼개서 각 일꾼의 책상(Local Queue)에 나눠주자!" 였다. 각자 자기 책상에서만 일을 빼가면 락을 걸 필요가 없어진다. 그런데 여기서 새로운 문제가 발생한다. "만약 A 일꾼은 책상에 일이 산더미고, B 일꾼은 5분 만에 일을 다 끝내서 놀고 있다면?" 이 불균형을 극적으로 해결한 천재적인 알고리즘이 바로 **Work Stealing (작업 훔치기)**이다.

📢 섹션 요약 비유: 급식소에서 배식구 1개에 100명이 줄을 서면(글로벌 큐) 엄청나게 밀립니다. Work Stealing은 100명의 책상에 도시락을 다 나눠줘서 자기 자리에서 먹게(로컬 큐) 만든 다음, 자기 밥을 일찍 다 먹은 친구가 남의 책상에 쌓여있는 반찬을 뒤에서 몰래 뺏어 먹게(부하 분산) 하는 효율의 극치입니다.

Ⅱ. Work Stealing의 메커니즘 (덱과 훔치기의 미학)

Work Stealing을 완벽하게 구현하기 위해, 큐(Queue) 대신 양쪽에서 다 빼낼 수 있는 덱(Deque, Double-Ended Queue) 자료구조를 사용한다.

1. 정상 작업 모드 (LIFO: 나 혼자 일할 때)

  • 일꾼(스레드)은 자기 책상(로컬 덱)의 **앞쪽(Top)**에서만 일을 넣고 뺀다.
  • 이것은 마치 스택(Stack)과 같아서, 가장 최근에 들어온 일을 가장 먼저 처리(LIFO)한다. CPU 캐시 히트율(Cache Hit Rate)이 극대화되어 엄청나게 빠르며, 자기 혼자 쓰므로 락(Lock)이 아예 필요 없다.

2. 도둑질 모드 (FIFO: 남의 일을 훔칠 때)

  • 일꾼 B가 자기 책상의 일을 다 끝내고 놀게 되었다. (Idle 상태)
  • 놀고 있는 일꾼 B(도둑)는 바쁜 일꾼 A(희생자)의 책상으로 몰래 다가간다.
  • 도둑 B는 희생자 A가 일하고 있는 앞쪽(Top)을 건드리지 않고, 덱의 반대편인 **뒤쪽(Bottom)**에서 오래된 작업을 슬쩍 빼간다. (FIFO)
  • 희생자는 앞쪽에서 놀고, 도둑은 뒤쪽에서 빼가기 때문에 서로 손이 부딪힐 확률(락 경합)이 획기적으로 낮아진다!
┌───────────────────────────────────────────────────────────────────────────────────┐
│           Work Stealing (작업 훔치기)의 Deque(덱) 기반 동기화 회피 시각화         │
├───────────────────────────────────────────────────────────────────────────────────┤
│                                                                                   │
│     [ 바쁜 스레드 A의 책상 (Local Deque) ]                                        │
│                                                                                   │
│ 스레드 A (주인) ──▶ (Top)  [ 작업 5 ]   (← A는 가장 최근 일부터 뺌)               │
│                        [ 작업 4 ]                                                 │
│                        [ 작업 3 ]                                                 │
│                        [ 작업 2 ]                                                 │
│ 잉여 스레드 B (도둑) ──▶ (Bottom)[ 작업 1 ]   (← B는 뒤에서 오래된 일부터 훔침!)  │
│                                                                                   │
│ ★ 핵심: 주인은 Top에서, 도둑은 Bottom에서 빼가기 때문에 서로 영역이               │
│         겹치지 않아 락(Lock)을 걸 필요가 거의 없다!                               │
└───────────────────────────────────────────────────────────────────────────────────┘

[다이어그램 해설] 왜 하필 도둑은 가장 오래된 작업(Bottom)을 훔쳐갈까? 분할 정복(Divide & Conquer) 알고리즘에서 가장 오래된 작업(Bottom)일수록 쪼개지지 않은 엄청나게 큰 덩어리의 작업일 확률이 높기 때문이다. 도둑이 이 큰 덩어리를 훔쳐 가서 자기 책상에서 잘게 쪼개어 처리하면 전체 시스템의 로드 밸런싱 효율이 폭발적으로 상승한다.

Ⅲ. Java의 Fork/Join 프레임워크와 실무 적용

Work Stealing 알고리즘을 가장 널리 유행시킨 것은 Java 7에 도입된 **ForkJoinPool**이다.

  • Fork (쪼개기): 큰 작업을 작은 작업으로 계속 쪼개서 자기 로컬 덱의 Top에 푸시(Push)한다.
  • Join (합치기): 쪼개진 작업들의 결과가 나오면 병합한다.
  • 일반적인 스레드 풀(ExecutorService)은 네트워크 I/O처럼 오래 기다리는 작업에 적합하지만, 수억 개의 데이터를 정렬하거나 이미지 픽셀을 변환하는 것 같은 CPU 집약적인 거대 연산을 할 때는 글로벌 큐 락 때문에 엄청 느려진다.
  • 이때 개발자가 ForkJoinPool을 적용하면, 각 코어가 100% 쉬지 않고 남의 일을 훔쳐 가며 계산을 때려 부수므로 다중 코어의 성능을 극한까지 끌어올릴 수 있다.

Ⅳ. 결론

"남의 밥그릇을 훔치는 것이, 시스템 전체를 살찌우는 가장 빠른 길이다." Work Stealing(작업 훔치기) 알고리즘은 중앙 집중화된 락(Lock) 제어가 병렬성의 가장 큰 적임을 깨달은 컴퓨터 공학의 눈부신 통찰이다. 각자 독립된 환경에서 자유를 누리되, 누군가 노는 순간이 발생하면 동기화 충돌을 최소화하는 방향으로 부하를 재분배하는 이 우아한 분산 아키텍처는, 코어 개수가 수십 수백 개로 늘어나는 현대 클라우드 및 분산 컴퓨팅 환경에서 성능을 지탱하는 핵심 척추로 자리 잡았다.

📌 관련 개념 맵

  • 전제되는 문제점: 스레드 풀 락 경합 (Thread Pool Lock Contention), 로드 불균형
  • 핵심 자료구조: 덱 (Deque - Double Ended Queue)
  • 대표적 구현체: Java ForkJoinPool, Go 언어의 Goroutine 스케줄러, C++ TBB
  • 응용 분야: 병렬 정렬, 행렬 곱셈, 분할 정복(Divide and Conquer) 알고리즘 병렬화

👶 어린이를 위한 3줄 비유 설명

  1. 10명이 김밥을 마는데, 김밥 재료가 가운데 한 통에만 있으면 재료를 꺼낼 때마다 서로 손이 부딪히고 엄청 기다려야 해요 (글로벌 큐 락).
  2. 그래서 각자 자기 책상에 재료를 다 나눠주고 혼자서 빨리빨리 만들게 했죠. 그런데 내 책상에 재료가 먼저 다 떨어져서 놀게 되면 어떡하죠?
  3. 놀고 있는 사람이, 일이 엄청 많이 남은 옆 친구 책상 뒤로 몰래 다가가서 김밥 재료를 슬쩍 훔쳐 와서(Work Stealing) 자기 자리에서 만듭니다! 서로 부딪히지 않고 엄청 빨리 김밥 1,000줄을 완성할 수 있어요.