ForkJoinPool은 왜 소유자는 LIFO, 도둑은 FIFO로 작업을 꺼내는가

1. 시작 — "스레드들이 큐 하나를 공유한다"는 오해

CompletableFuture, parallelStream(), 그리고 Java 21의 가상 스레드 캐리어까지 — 이들이 전부 공용 ForkJoinPool 위에서 돈다는 걸 알고 나니, 정작 그 풀 내부에서 "작업 훔치기(work-stealing)"가 자료구조 수준으로 어떻게 굴러가는지는 뭉개고 있었다.

머릿속 그림은 이랬다. "스레드 여러 개가 공유 작업 큐 하나를 두고, 비면 거기서 하나씩 꺼내 실행한다." 그런데 OpenJDK 소스를 따라가 보니 실제 구조는 오히려 정반대에 가까웠다. 공유 큐는 없다. 워커마다 자기 전용 덱(deque)이 따로 있고, 다른 워커는 그걸 "훔쳐야" 병렬이 된다.

이 글은 그 전용 덱의 한 가지 비대칭 — 소유자는 한쪽 끝에서 LIFO, 도둑은 반대쪽 끝에서 FIFO — 가 왜 이렇게 설계됐는지를, 소스를 손으로 따라가며 이해한 대로 정리한 것이다.

2. 핵심 한 문장

워커마다 자기 전용 덱을 두고, 소유자는 한쪽 끝(top)에서 LIFO로 push/pop 하고, 유휴 도둑은 반대쪽 끝(base)에서 FIFO로 훔쳐서, 경합 지점을 "큐가 거의 빌 때의 양 끝 충돌"로만 좁힌 락-프리(lock-free) 스케줄러다.

이 "한쪽 LIFO, 반대쪽 FIFO" 구조는 Arora–Blumofe–Plumb의 work-stealing deque(SPAA 1998)가 원형으로 알려져 있고, Doug Lea의 "A Java Fork/Join Framework"(2000)가 이를 Java로 구현한 것이다.

3. 큐가 하나가 아니다

ForkJoinPool은 공유 작업 큐 하나가 아니라 WorkQueue[] 배열을 가진다. OpenJDK 소스(JDK 17)에 따르면 이 배열은 인덱스로 두 종류를 구분한다.

• 홀수 인덱스 = 워커 스레드 전용 큐. 워커가 fork()한 하위 작업이 여기 쌓인다.
• 짝수 인덱스 = 풀 바깥 스레드가 submit()/execute()로 넣은 작업이 들어가는 submission queue.

즉 워커가 재귀적으로 쪼갠 하위 작업은 자기 큐에만 들어가고, 그걸 다른 스레드가 훔쳐야 비로소 병렬이 된다. 워커 큐 하나(WorkQueue)는 원형 배열 + 두 개의 인덱스로 되어 있다.

       base ──►                    ◄── top
        │                            │
   [ t0 ][ t1 ][ t2 ][ t3 ][ t4 ][    ]
        ▲                        ▲
   도둑이 여기서 poll (FIFO)     소유자가 여기서 push/pop (LIFO)
   (뿌리에 가까운 오래된 작업)    (방금 fork한 최근 작업)

   slot 접근:  array[i & mask]      큐 길이:  top - base

세 가지 연산이 있다.

• push (fork) — 소유자만. array[top & mask] = task; 로 슬롯에 쓴 뒤 top++ 을 release 스토어로 publish 한다. 다른 스레드 눈에 "슬롯 쓰기"가 "top 증가"보다 먼저 보이도록 순서를 강제하는 게 포인트다.
• pop (소유자가 자기 것 실행) — top-1 슬롯을 집는다. 방금 fork한 가장 최근 작업 → LIFO.
• poll (steal) — 도둑은 base 슬롯을 읽고 CAS(base, b, b+1) 로 전진시킨다. 성공한 한 명만 그 작업을 가져간다 → 가장 오래된 작업, FIFO.

소유자는 top만, 도둑은 base만 건드린다. 그래서 큐가 넉넉히 차 있는 동안엔 둘이 서로 다른 인덱스/캐시 라인을 만져 경합이 없다. 충돌은 top - base <= 1, 즉 큐가 거의 비어 마지막 한 개를 소유자와 도둑이 동시에 노릴 때뿐이고, 이때는 소유자의 pop도 CAS로 내려가 승자를 가린다.

4. 왜 이 비대칭인가 (설계의 핵심)

같은 덱을 양쪽 끝에서 다른 규칙으로 꺼내는 게 이상해 보이지만, 세 가지가 맞물린 결과다.

① 소유자 LIFO = 캐시 지역성 + 유한한 메모리. 방금 fork한 하위 작업은 그 데이터가 아직 캐시에 뜨겁고, 부모의 지역 변수도 스택에 살아있다. top에서 최근 것을 먼저 처리하면 재귀가 사실상 깊이 우선(DFS) 으로 풀린다. 순차 실행과 비슷한 순서가 되어, 동시에 살아있는 미완 작업 수가 트리의 폭이 아니라 깊이 수준으로 억제된다.

② 도둑 FIFO = 큰 덩어리를 훔친다. base 쪽은 계산 트리에서 뿌리에 가까운, 아직 잘게 안 쪼개진 오래된 작업이다. 도둑이 이걸 훔치면 한 번에 큰 서브트리를 가져가 자기 큐에서 다시 쪼갤 수 있다 → steal 빈도가 낮아진다. steal은 CAS + 캐시 라인 이동을 동반하는 비싼 연산이라, 횟수를 줄이는 것 자체가 이득이다.

③ 경합의 물리적 분리. 흔한 경로(소유자 push/pop)와 드문 경로(steal)를 덱의 반대 끝에 배치함으로써, 자주 일어나는 일과 가끔 일어나는 일이 서로 다른 메모리를 만지게 만든다.

5. fork/join에 대한 두 가지 오해

내가 틀리게 알고 있던 것 두 개를 짚어둔다.

"fork()는 곧 새 스레드에서 즉시 병렬 실행이다." 아니다. fork()는 그냥 자기 큐 top에 push 하는 값싼 연산일 뿐이다. 실제 병렬은 다른 유휴 워커가 그걸 steal 할 때만 생긴다. 아무도 안 훔쳐가면 소유자가 나중에 pop 해서 그냥 순차로 실행한다. fork/join의 오버헤드가 낮은 이유가 여기 있다 — 경합이 없으면 사실상 재귀 호출과 비슷한 비용이다.

"join()은 스레드를 블로킹한다." 대체로 아니다. a.fork(); b.fork(); a.join(); 에서 join()은 그냥 자는 게 아니라, 대상이 아직 안 끝났으면 워커가 능동적으로 일을 돕는다.

1. 대상 작업이 아직 자기 큐 top에 있으면 직접 pop 해서 실행한다(fork 순서상 방금 넣은 것이라 가장 흔한 경우).
2. 아니면 그 작업을 훔쳐간 워커의 큐를 뒤져 그쪽 다른 작업을 대신 실행(helpJoin)하며 전체 진행을 돕는다.

그래서 join 중에도 스레드가 놀지 않는다. 진짜로 막아야 하는 블로킹(ManagedBlocker, I/O)만 풀이 보상 스레드(compensation thread) 를 잠깐 늘려 목표 병렬도를 유지한다.

6. 손으로 따라가 보기

push → steal → pop 시퀀스를 인덱스 이동으로 직접 돌려보면 불변식이 드러난다(mask 생략, 개념 흐름).

// 워커 W1이 세 작업을 fork
push(t0);  // array[0]=t0, top=1   (base=0)
push(t1);  // array[1]=t1, top=2
push(t2);  // array[2]=t2, top=3

// 유휴 워커 W2가 steal 시도: base=0 읽음 → t0, CAS(base,0,1) 성공
//   => W2는 t0(가장 오래된 것)을 가져감.  base=1

// W1이 자기 것 실행: top-1=2 → t2(가장 최근 것) pop.  top=2
//   => LIFO.  큐엔 t1 하나 남음 (base=1, top=2)

// 이제 top-base==1: W1의 pop과 W2의 poll이 t1을 동시에 노리면
//   둘 다 CAS로 내려가 한 명만 성공 → 이중 실행 없음

핵심 불변식은 소유자는 top, 도둑은 base. 정상 구간엔 서로 다른 정수/슬롯을 만지고, 경계(길이 ≤ 1)에서만 CAS로 조정한다. 실제 WorkQueue는 base·top과 배열 참조를 VarHandle(구버전 Unsafe)의 acquire/release·CAS로 접근하고, false sharing을 막으려 필드에 @Contended 패딩을 둔다고 소스에 나온다.

7. 정리

"공유 큐에서 나눠 꺼낸다"가 아니라, "각자 자기 덱을 쌓다가 남는 놈이 남의 것을 훔친다"가 ForkJoinPool의 실제 모델이다.

• 소유자 LIFO(top)는 지역성과 얕은 메모리를, 도둑 FIFO(base)는 큰 덩어리와 저경합을 노린다. 두 끝을 반대로 둔 덕에 흔한 경로와 드문 경로가 안 부딪친다.
• fork()는 push일 뿐 병렬의 약속이 아니고, join()은 블로킹이 아니라 "도와주기"다.

더 파고들 만한 주제: ManagedBlocker와 compensation 스레드가 목표 병렬도를 유지하는 정확한 조건, join 없이 완료 카운트로 트리를 접는 CountedCompleter, 그리고 활성/전체 워커 수를 하나의 long에 팩킹하는 ctl 필드의 park/unpark signal 프로토콜.

참고 자료

• Doug Lea, "A Java Fork/Join Framework" (2000)
• OpenJDK java.util.concurrent.ForkJoinPool / WorkQueue 소스 (JDK 17)
• Arora, Blumofe, Plumb, "Thread Scheduling for Multiprogrammed Multiprocessors" (SPAA 1998)