🧵 Розділ 9 · Питання #16

Що таке ForkJoinPool

Його головна архітектурна відмінність від стандартного ThreadPoolExecutor полягає в алгоритмі крадіжки роботи (Work-Stealing):

🧵 Багатопоточність 📄 Вихідний Markdown

🟢 Junior Level

Коротка відповідь для співбесіди (30 секунд)

ForkJoinPool — це спеціалізована реалізація інтерфейсу ExecutorService, що з’явилася в Java 7 та оптимізована для паралельного виконання задач за принципом «Розділяй і володарюй» (Divide and Conquer).

Його головна архітектурна відмінність від стандартного ThreadPoolExecutor полягає в алгоритмі крадіжки роботи (Work-Stealing):

  • У звичайному пулі всі потоки конкурують за одну спільну чергу задач.
  • У ForkJoinPool кожен робочий потік має власну двосторонню чергу (Deque). Якщо один потік завершив свої підзадачі раніше за інших, він не простоює, а «краде» підзадачі з черги сусіднього зайнятого потоку.

ForkJoinPool є базовим обчислювальним рушієм для Parallel Streams (Stream.parallel()) та асинхронних ланцюжків CompletableFuture за замовчуванням.

Основні класи та методи

Базовою одиницею роботи є абстрактний клас ForkJoinTask<V>, що має дві основні реалізації:

  1. RecursiveTask<V>: для задач, що повертають результат (обчислення суми, пошук, агрегація).
  2. RecursiveAction: для задач, що не повертають результат (сортування масиву на місці, мутація даних).

Ключові методи:

  • fork(): асинхронно поміщає підзадачу в локальну чергу поточного потоку.
  • join(): очікує завершення підзадачі та повертає результат.
  • invoke(): виконує задачу синхронно та повертає результат (точка входу).

Базовий приклад на Java 21: Паралельна сума масиву

import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.RecursiveTask;

public class ForkJoinSumDemo {

    public static class SumTask extends RecursiveTask<Long> {
        private static final int THRESHOLD = 10_000; // Поріг прямого обчислення
        private final long[] array;
        private final int start;
        private final int end;

        public SumTask(long[] array, int start, int end) {
            this.array = array;
            this.start = start;
            this.end = end;
        }

        @Override
        protected Long compute() {
            int length = end - start;
            // Базовий випадок: задача достатньо мала для послідовного рахунку
            if (length <= THRESHOLD) {
                long sum = 0;
                for (int i = start; i < end; i++) {
                    sum += array[i];
                }
                return sum;
            }

            // Крок розділення: ділимо масив навпіл
            int mid = start + length / 2;
            SumTask leftSubtask = new SumTask(array, start, mid);
            SumTask rightSubtask = new SumTask(array, mid, end);

            // Асинхронно відправляємо ліву половину в чергу
            leftSubtask.fork();

            // Праву половину рахуємо прямо в поточному потоці (ОПТИМІЗАЦІЯ!)
            long rightResult = rightSubtask.compute();

            // Очікуємо результат лівої половини
            long leftResult = leftSubtask.join();

            return leftResult + rightResult;
        }
    }

    public static void main(String[] args) {
        long[] numbers = new long[100_000];
        for (int i = 0; i < numbers.length; i++) numbers[i] = i;

        // Використання глобального спільного пулу
        ForkJoinPool pool = ForkJoinPool.commonPool();
        long total = pool.invoke(new SumTask(numbers, 0, numbers.length));
        System.out.println("Сума: " + total);
    }
}

🟡 Middle Level

Алгоритм Work-Stealing: Архітектура двосторонньої черги (Deque)

Кожен робочий потік (ForkJoinWorkerThread) прив’язаний до власної черги WorkQueue. Черга побудована як циклічний масив із двома вказівниками: top (голова) та base (хвіст).

                      Локальна WorkQueue потоку
                 base                                     top
             (Хвіст / FIFO)                         (Голова / LIFO)
          ┌────────────────────────────────────────────────────────┐
          │  Задача 1  │  Задача 2  │  Задача 3  │  Задача 4 (Top) │
          └────────────────────────────────────────────────────────┘
                 ▲                                        ▲
                 │                                        │
           Злодій (Thief):                          Власник потоку:
          CAS крадіжка з хвоста                    push/pop з голови
             (FIFO режим)                             (LIFO режим)

Чому власник працює за LIFO, а злодій краде за FIFO?

  1. Власник працює в LIFO-режимі (з голови):
    • Кеш-локальність (Cache Locality): найостанніша створена підзадача обробляє найменший зріз даних, який з величезною ймовірністю все ще перебуває в надшвидкому процесорному кеші L1/L2.
    • Дозволяє розгортати рекурсивне дерево вглиб (Depth-First Search), мінімізуючи глибину стека та споживання пам’яті.
  2. Злодій краде у FIFO-режимі (з хвоста):
    • У хвості черги лежать найраніші, найбільш великі підзадачі («верхні гілки дерева рекурсії»). Вкрасти одну велику задачу вигідніше, ніж сотню дрібних, оскільки злодій зможе далі ділити її у себе.
    • Усунення конкуренції: власник і злодій звертаються до протилежних кінців масиву через атомарні CAS-інструкції, зводячи блокування майже до нуля.

Золоте правило Fork/Join: fork() + compute()

Поширена помилка при написанні рекурсивних задач:

// АНТИПАТЕРН: витрачає 2 потоки марно!
left.fork();
right.fork();
long r1 = left.join();
long r2 = right.join();

// ЕТАЛОН: економить 1 потік пулу!
left.fork();
long r2 = right.compute(); // Виконується в поточному потоці!
long r1 = left.join();

Якщо виконати fork() для обох половин, поточний потік піде в блокуюче очікування на join(), а пул буде змушений задіяти інший потік із пулу для виконання right. Ідіома left.fork(); right.compute(); left.join(); змушує поточний потік відразу виконувати праву підзадачу без передачі керування.

Архітектура ForkJoinPool.commonPool()

У Java існує глобальний статичний пул ForkJoinPool.commonPool().

  • Рівень паралелізму за замовчуванням: дорівнює Runtime.getRuntime().availableProcessors() - 1.
  • Один потік резервується для обслуговування операційної системи та основного потоку застосунку.
  • Налаштовується через системний прапорець:
    -Djava.util.concurrent.ForkJoinPool.common.parallelism=N.

🔴 Senior Level

Проблема голодування пулу: Блокуючий I/O у commonPool

Оскільки ForkJoinPool.commonPool() є розділюваним синглтоном на всю JVM, будь-яка блокуюча операція паралізує роботу платформи:

// КАТАСТРОФА ДЛЯ ВСІЄЇ JVM:
CompletableFuture.supplyAsync(() -> {
    // Повільний мережевий виклик (БД або зовнішній мікросервіс)
    return httpClient.get("https://external-api.com/slow");
}); // За замовчуванням використовує commonPool()!

Наслідки:

  • Робочі потоки commonPool зависають в очікуванні сокетів.
  • Усі паралельні стріми застосунку (list.parallelStream()) у всіх інших сервісах та фонових джобах повністю зупиняються, оскільки пул позбавлений вільних потоків.
  • Правило Senior-інженера: commonPool призначений виключно для швидких CPU-bound задач без блокувань. Будь-який мережевий або дисковий I/O зобов’язаний передаватися в ізольований ThreadPoolExecutor або використовувати віртуальні потоки.

Компенсація блокувань: ForkJoinPool.ManagedBlocker

Якщо всередині ForkJoinPool абсолютно неминуча блокуюча операція (наприклад, очікування фази Phaser, захоплення блокування або читання), не можна просто викликати Thread.sleep() або lock.lock().

Необхідно використовувати інтерфейс ManagedBlocker:

public class ManagedLocker implements ForkJoinPool.ManagedBlocker {
    private final ReentrantLock lock;
    private boolean hasLock = false;

    public ManagedLocker(ReentrantLock lock) {
        this.lock = lock;
    }

    @Override
    public boolean block() {
        if (!hasLock) {
            lock.lock();
            hasLock = true;
        }
        return true;
    }

    @Override
    public boolean isReleasable() {
        return hasLock || (hasLock = lock.tryLock());
    }
}

// Виклик компенсації:
ForkJoinPool.managedBlock(new ManagedLocker(myLock));

Що робить managedBlock() всередині JVM:

Перед тим як робочий потік заблокується, ForkJoinPool тимчасово створює або активує резервний потік-компенсатор, підтримуючи цільовий рівень паралелізму пулу незмінним!

ForkJoinPool як планувальник Virtual Threads у Java 21

У Java 21 (Project Loom / JEP 444) архітектура ForkJoinPool стала фундаментом усієї платформи:

  • Віртуальні потоки (VirtualThread) не мають власних потоків ОС.
  • Роль планувальника віртуальних потоків (Scheduler) виконує внутрішній екземпляр ForkJoinPool у режимі FIFO (asyncMode = true).
  • Платформені потоки цього пулу виступають у ролі Carrier Threads (потоків-носіїв).
  • Коли віртуальний потік готовий до виконання, він поміщається як ForkJoinTask у чергу WorkQueue несучого пулу.
  • При виконанні блокуючого I/O віртуальний потік розмонтовується (unmount) зі стека Carrier Thread, дозволяючи потоку-носію негайно вкрасти та виконувати інший віртуальний потік.

🎯 Шпаргалка для інтерв’ю

1. 30-секундний есенс (Elevator Pitch)

ForkJoinPool — спеціалізований пул потоків для паралельних рекурсивних обчислень за алгоритмом Work-Stealing («крадіжка роботи»). Замість однієї спільної черги кожен потік володіє двосторонньою чергою (WorkQueue): потік-власник бере задачі з голови за принципом LIFO (максимізуючи кеш-локальність процесора), а вільні потоки крадуть великі задачі з хвоста за принципом FIFO. Лежить в основі Parallel Streams та CompletableFuture. У Java 21 спеціальний екземпляр ForkJoinPool служить низькорівневим планувальником віртуальних потоків (Virtual Threads).

2. 4 каверзних питання з глибокими відповідями

Питання 1: Чому потік-власник забирає задачі зі своєї черги за принципом LIFO, а потік-злодій краде за принципом FIFO?

Відповідь:

  1. LIFO для власника: остання додана в чергу підзадача є найбільш гранулярною та обробляє зріз даних, що щойно перебував у регістрах та кешах L1/L2 процесора. Виконання за LIFO зберігає локальність посилань (Cache Locality) та імітує природний рекурсивний стек викликів.
  2. FIFO для злодія: у хвості черги лежать найстаріші підзадачі — це верхні гілки дерева рекурсії з найбільшим обсягом роботи. Вкрасти одну велику задачу ефективніше, ніж здійснювати сотні дрібних крадіжок. Крім того, доступ до протилежних кінців масиву мінімізує конкуренцію за атомарні CAS-вказівники.

Питання 2: Чому конструкція left.fork(); right.fork(); left.join(); right.join(); вважається грубою помилкою продуктивності?

Відповідь: Тому що поточний робочий потік виконує fork() для обох половин і тут же засинає на left.join(). Він добровільно віддає виконання другої половини (right) іншим потокам пулу, породжуючи зайві перемикання контексту та накладні витрати на постановку в чергу.
Правильний патерн: left.fork(); rightResult = right.compute(); leftResult = left.join();. У цьому випадку праву підзадачу поточний потік рахує негайно сам, заощаджуючи системні ресурси пулу.

Питання 3: Яку проблему вирішує механізм ForkJoinPool.ManagedBlocker?

Відповідь: ForkJoinPool розрахований на безперервні CPU-обчислення без блокувань. Якщо потік пулу блокується звичайним способом (sleep, синхронний I/O, монітор), ефективний рівень паралелізму пулу падає (мінус одне ядро). Якщо заблокуються всі потоки, система повністю паралізується. Огортання блокуючого коду у ForkJoinPool.managedBlock() змушує пул динамічно створити тимчасовий потік компенсації (compensation thread) на час блокування, зберігаючи загальну кількість активних обчислювальних ядер незмінною.

Питання 4: Як ForkJoinPool пов’язаний із віртуальними потоками (Virtual Threads) у Java 21?

Відповідь: У Java 21 ForkJoinPool є системним планувальником (Scheduler) для всіх віртуальних потоків. За замовчуванням JVM створює закритий екземпляр ForkJoinPool, чиї потоки є потоками-носіями (Carrier Threads). Віртуальні потоки оформлюються у вигляді задач і виконуються потоками-носіями. Коли віртуальний потік зустрічає блокуючу операцію (мережа, монітор, паркування), рантайм зберігає його стек у купу та розмонтовує його, а потік-носій повертається у ForkJoinPool і виконує наступну задачу за алгоритмом work-stealing.

3. Типові помилки та Red Flags

❌ “Використання parallelStream() для виконання HTTP-запитів або запитів до бази даних.”
Правильно: parallelStream() використовує спільний пул ForkJoinPool.commonPool(). Блокування в мережевому I/O заблокує паралельні стріми в усьому застосунку. Для I/O необхідний виділений пул потоків або Virtual Threads.

❌ “Занадто дрібний або занадто великий поріг THRESHOLD.”
Правильно: Якщо ділити задачі до окремих елементів, накладні витрати на алокацію ForkJoinTask перевантажать Garbage Collector. Поріг має бути таким, щоб листова задача виконувалася послідовно за 100–500 мікросекунд.

❌ “Виклик ForkJoinPool.commonPool().shutdown().”
Правильно: Спроба зупинити commonPool() ігнорується рантаймом, але виклик shutdown() на спільних ресурсах порушує контракт і є поганим тоном.

4. Пов’язані питання