Work stealing: как планировщик балансирует ветви

Урок про алгоритм планирования, который делает fork-join эффективным без ручной балансировки.

Work stealing — стратегия планирования: у каждого ядра своя двусторонняя очередь задач; когда ядро простаивает, оно «крадёт» задачу с конца очереди другого, загруженного ядра.

Проблема балансировки в fork-join

Рекурсивное дерево задач неравномерно: одна ветвь может породить много мелких подзадач, другая — мало. Статически раздать задачи по ядрам заранее нельзя — мы не знаем форму дерева до выполнения. Нужна динамическая балансировка, которая сама подберёт работу простаивающим ядрам. Work stealing решает это элегантно и почти без накладных расходов в типичном случае.

Как устроена кража

У каждого ядра — собственная двусторонняя очередь (deque). Когда задача делает fork, ядро кладёт новую подзадачу в низ своей очереди и продолжает работать с вершиной. Своё ядро берёт задачи с низа (LIFO — последняя добавленная, она «горячая» в кэше). Когда чужое ядро простаивает, оно крадёт с верха чужой очереди (FIFO — самая старая, обычно самая крупная подзадача). Разные концы — не случайность: своё ядро работает с мелкими свежими задачами (хороший кэш), а вор забирает крупную старую (одна кража даёт много работы).

Очередь ядра A (deque):
  верх  [крупная старая задача]  <- отсюда крадут другие ядра
        [ ... ]
  низ   [свежая мелкая задача]   <- отсюда берёт само ядро A

# упрощённая модель: одна очередь работы, простаивающие воркеры крадут с верха
from collections import deque

work = deque([("крупная", 8), ("средняя", 4), ("мелкая1", 1), ("мелкая2", 1)])
workers = {0: 0, 1: 0}   # накопленное время на каждом воркере

step = 0
while work:
    # выбираем наименее загруженного воркера (он "простаивает")
    w = min(workers, key=workers.get)
    name, cost = work.popleft()   # крадёт с верха (крупную старую)
    workers[w] += cost
    step += 1
    print(f"шаг {step}: воркер {w} взял '{name}' (стоимость {cost}), нагрузка {workers[w]}")

print("итог нагрузка:", workers, "-> время =", max(workers.values()))

Вывод:

шаг 1: воркер 0 взял 'крупная' (стоимость 8), нагрузка 8
шаг 2: воркер 1 взял 'средняя' (стоимость 4), нагрузка 4
шаг 3: воркер 1 взял 'мелкая1' (стоимость 1), нагрузка 5
шаг 4: воркер 1 взял 'мелкая2' (стоимость 1), нагрузка 6
итог нагрузка: {0: 8, 1: 6} -> время = 8

Простаивающий воркер сам подбирает работу, выравнивая нагрузку (8 против 6 — близко). Без балансировки одно ядро могло бы получить всё, а второе простаивать.

Почему это эффективно

В типичном случае краж мало: каждое ядро занято своей очередью, обращений к чужим очередям почти нет. Кражи случаются только когда ядро действительно простаивает — то есть ровно тогда, когда они нужны. Теория (Blumofe и Leiserson) доказывает, что work stealing даёт почти оптимальное время выполнения и ограниченное число краж. Поэтому он стал стандартом: его используют Cilk, Java ForkJoinPool, Go-планировщик горутин, Rust Rayon, TBB.

Как работает под капотом

Двусторонняя очередь должна быть потокобезопасной: своё ядро и воры обращаются к разным концам, поэтому конфликты редки, но возможны (когда очередь почти пуста). Используют lock-free deque (алгоритм Chase-Lev), где операции push/pop своего ядра почти всегда без блокировок, а кража синхронизируется атомарной операцией. Это и делает work stealing дешёвым в общем случае.

Work stealing — красивый пример того, как децентрализация бьёт централизацию. Можно было бы поставить одного «диспетчера», который раздаёт работу всем ядрам, — но он быстро стал бы узким местом: все ядра толпились бы у единственной очереди, борясь за неё. Work stealing обходится без центра: у каждого ядра своя очередь, и общение возникает лишь когда ядро простаивает и идёт красть. В типичном случае краж почти нет, поэтому нет и борьбы за общий ресурс — система масштабируется на десятки ядер без деградации. Этот принцип «локально по умолчанию, координация только при необходимости» — рецепт масштабируемости далеко за пределами планировщиков.

Частые ошибки

• Думать, что work stealing создаёт большой overhead — кражи редки, в основном ядра работают со своими очередями.
• Брать задачи из своей очереди с того же конца, что и воры — теряется преимущество кэша и крупных краж.
• Применять без достаточного числа задач — если параллелизма мало, красть нечего.

Итоги

• Work stealing динамически балансирует fork-join: простаивающее ядро крадёт задачу у занятого.
• Своё ядро берёт с низа (горячий кэш), вор крадёт с верха (крупная старая задача).
• Кражи редки и происходят только при простое — отсюда высокая эффективность.
• Стандарт в Cilk, Java ForkJoinPool, Go, Rust Rayon, TBB.