9.2 Планирование с кражей работы

9.1 оставил нам вопрос: у каждого P есть собственная локальная очередь, а значит, работа неизбежно распределяется неравномерно. Одни P перегружены, другие простаивают. Как распределить нагрузку, не создавая центрального узкого места, — это основная трудность конкурентного планирования. Ответ Go — схема с тридцатилетней теоретической базой, воспроизводимая во всей отрасли: кража работы (work stealing).

Этот раздел несколько глубже остальных. Сначала мы проясним, что именно делает Go, затем проследим стоящую за этим теорию планирования (почему кража работы «доказуемо хороша»), далее рассмотрим различные воплощения этой идеи в системах вроде Cilk, Java и Rust и, наконец, остановимся на вопросах, которые остаются открытыми.

9.2.1 Раздача или кража

Перемещение задач между процессорами исторически следовало двум парадигмам. Раздача работы (work sharing): тот, кто порождает новую задачу, активно передаёт часть её простаивающему процессору. Кража работы (work stealing): инициативу проявляет простаивающий процессор — он крадёт задачи у других. Разница — в частоте миграций. Раздача работы может инициировать миграцию при каждом появлении новой задачи; кража работы мигрирует задачи лишь тогда, когда некоторый процессор действительно не имеет работы. Когда все процессоры заняты, «вору» негде действовать, и миграция естественным образом прекращается. Чем выше нагрузка, тем тише ведёт себя кража работы. В этом её фундаментальное преимущество перед раздачей, и оно подкреплено строгими оценками объёма коммуникаций (см. 9.2.4).

9.2.2 Порядок поиска работы в Go

M, привязанный к P и завершивший выполнение текущего G, не крадёт работу сразу. Вместо этого он ищет в порядке от ближнего к дальнему и от дешёвого к дорогому (функция рантайма findRunnable):

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


// findRunnable: M ищет следующий готовый к выполнению G (псевдокод)
func findRunnable() *g {
    if pp.schedtick%61 == 0 && !sched.runq.empty() { // 1. каждые 61 тик — проверка глобальной очереди для справедливости
        if gp := globrunqget(); gp != nil { return gp }
    }
    if gp := runqget(pp); gp != nil { return gp }     // 2. локальная очередь (включая runnext)
    if gp := globrunqget(); gp != nil { return gp }    // 3. глобальная очередь
    if gp := netpoll(); gp != nil { return gp }        // 4. сетевой поллер
    if gp := stealWork(); gp != nil { return gp }      // 5. кража половины у другого P
    stopm()                                            // 6. ничего нет: крутиться или засыпать
}

Три детали делают кражу эффективной. Ограниченная локальная очередь: каждая очередь P — это кольцевой буфер фиксированной длины (256 элементов), большинство операций постановки и извлечения выполняются без блокировок; при переполнении половина очереди перемещается в глобальную очередь (runqputslow) в качестве запасного механизма. Случайный разброс целей кражи: если бы каждый простаивающий P начинал красть с одной и той же стартовой позиции в фиксированном порядке, все «воры» столпились бы у одной цели. В Go каждый «вор» использует случайную начальную позицию и случайный шаг, взаимно простой с общим числом P, обходя псевдослучайную перестановку, покрывающую все P. Взаимная простота гарантирует отсутствие повторов и пропусков, а рандомизация устраняет эффект стада. Крутящиеся потоки (spinning threads): небольшому числу M разрешено находиться в состоянии активного ожидания (не более GOMAXPROCS, счётчик — sched.nmspinning), активно ища работу, а не засыпая немедленно, чтобы вновь ставший готовым G мог быть подхвачен быстро, без частых засыпаний и пробуждений потоков.

9.2.3 Необходимый минимум модели

Чтобы прояснить, в чём именно кража работы «хороша», нужна мерка. Абстрагируем параллельное вычисление в виде направленного ациклического графа (DAG): каждый узел — инструкция с единичным временем выполнения, каждое ребро — зависимость. Две величины характеризуют его:

Общий объём работы $T_1$ : полное число узлов, то есть время выполнения на одном процессоре;
Span (длина критического пути) $T_\infty$ : длина наибольшей цепочки зависимостей, то есть время выполнения на бесконечном числе процессоров.

Их отношение $T_1/T_\infty$ называется параллелизмом — это верхняя граница ускорения, которого вообще можно достичь. Время выполнения $T_P$ на $P$ процессорах не может быть меньше $\max(T_1/P,\ T_\infty)$ . Хороший планировщик должен делать $T_P$ как можно ближе к этой нижней границе.

9.2.4 Почему кража работы «доказуемо хороша»

Верхняя граница жадного планирования. Грэхем (1969) доказал, что любое жадное расписание, которое «никогда не оставляет процессор без работы без причины», не может слишком отклониться от оптимума:

T_P \le \frac{T_1 - T_\infty}{P} + T_\infty \le \frac{T_1}{P} + T_\infty.

Это также означает, что жадное расписание не более чем в $2 - 1/P$ раз хуже оптимального. Брент (1974) получил ту же форму $t + (q-t)/p$ для вычисления арифметических выражений. Эту оценку часто вольно называют «теоремой Брента», однако более общий и хронологически первый результат принадлежит Грэхему (list scheduling), что заслуживает упоминания.

Граница рандомизированной кражи работы. Жадная верхняя граница лишь утверждает: «не оставляйте процессоры без дела — и будет неплохо», но не говорит, как добиться этого распределённо. Блумоф и Лейзерсон (FOCS 1994; JACM 1999) доказали, что для полностью строгих вычислений (fork-join-вычислений, чьи рёбра соединения ведут только к родительскому потоку) рандомизированная кража работы достигает в ожидании

\mathbb{E}[T_P] = \frac{T_1}{P} + O(T_\infty),

требует памяти не более $S_1 \cdot P$ ( $S_1$ — память при последовательном исполнении) и порождает ожидаемый межпроцессорный обмен не более $O(P \cdot T_\infty \cdot S_{\max})$ . Три оценки вместе показывают: если само вычисление обладает достаточным параллелизмом ( $T_\infty \ll T_1$ ), кража работы может приблизиться к линейному ускорению при ограниченных затратах на память и коммуникации.

Суть доказательства (для заинтересованного читателя): каждому готовому узлу назначается геометрически убывающий потенциал в зависимости от его глубины в DAG, и суммарный потенциал уменьшается по мере продвижения вычисления. Лемма в стиле «шары в корзины» показывает, что когда $P$ процессоров совершают по одной случайной попытке кражи, постоянная доля попыток всегда попадает в голову непустой очереди, так что $\Theta(P)$ попыток достаточно для уменьшения потенциала на постоянный множитель. Потенциал может уменьшиться не более $O(T_\infty)$ раз вдоль критического пути, поэтому ожидаемое число успешных краж составляет $O(P \cdot T_\infty)$ . Распределение этих краж и времени простоя по $P$ процессорам даёт ровно $O(T_\infty)$ , что вместе с рабочим слагаемым $T_1/P$ даёт верхнюю границу. Оценки памяти и коммуникаций опираются на свойство «занятых листьев» (busy-leaves), которое обеспечивает полная строгость: каждая кража переносит лишь один кадр активации.

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

flowchart LR
    OWNER["владелец M"] -->|"push / pop снизу (LIFO, хорошо для локальности)"| BOT
    subgraph DQ["одна рабочая очередь (дек)"]
      direction TB
      TOP["вершина: более старые задачи"]
      BOT["дно: более новые задачи"]
    end
    THIEF["простаивающий вор M"] -->|"кража сверху (FIFO, забирает крупное подвычисление)"| TOP

Арора, Блумоф и Плакстон (SPAA 1998) предложили неблокирующий дек для кражи и расширили анализ на «мультипрограммную» среду (где операционная система не обязательно загружает все $P$ процессоров). Чейз и Лев (SPAA 2005) дополнительно предложили версию с растущим кольцевым массивом — наиболее распространённый на практике вариант. Необходимо устранить одну частую ошибку атрибуции: так называемый THE-протокол и принцип work-first происходят из Cilk-5 (Frigo, Leiserson, Randall, PLDI 1998), а не из ABP; вклад ABP — именно неблокирующий дек.

Стоит подчеркнуть: реализация Go — это не классический LIFO-дек. Локальная очередь Go — это FIFO-кольцевой буфер с дополнительным LIFO-слотом runnext, обеспечивающим локальность только что порождённого G (9.3); кража по-прежнему «крадёт половину». Это инженерия, переписывающая теорию.

9.2.5 Множество воплощений одной идеи

Кража работы — не изобретение Go. Идея восходит к работе Бёртона и Слипа (1981) о параллельном выполнении функциональных программ и к Multilisp Халстеда (1984), а в форму со строгими гарантиями и пригодную для инженерного применения её привёл проект Cilk в MIT. Затем она стала практически стандартным компонентом параллельных рантаймов, хотя компромиссы в каждой системе различаются:

Cilk / Cilk-5: прародитель fork-join, заложивший принцип work-first, THE-протокол и компиляцию с двумя клонами.
Intel TBB, Java ForkJoinPool (Doug Lea, 2000, по собственному определению «вариант Cilk-фреймворка кражи работы»), .NET TPL: все построены на кражи работы в стиле Cilk; при этом TPL намеренно использует «дублирующую очередь» вместо THE.
Rust Rayon: fork-join-параллелизм данных, построенный вокруг join(a, b); многопоточный async-рантайм Tokio явно заимствует алгоритм локальной очереди фиксированной длины у Go (LIFO-слот плюс глобальная очередь).

Go фундаментально отличается от линейки Cilk в одном отношении, которое необходимо пояснить: семейство Cilk — это планировщик fork-join DAG-задач, тогда как Go — планировщик горутин общего назначения в модели M:N. Горутины — это произвольные единицы исполнения, блокирующиеся на каналах, системных вызовах или сетевом вводе-выводе, с возможностью асинхронного вытеснения (9.7); они не образуют полностью строгий fork-join DAG. Поэтому красивая гарантия $T_1/P + O(T_\infty)$ из раздела 9.2.4 к Go не применима. Кража работы в Go — это эвристика балансировки нагрузки, заимствующая эту теорию, а не доказуемо оптимальный планировщик. Понимание этого предостерегает от некорректного применения выводов теории к горутинам.

9.2.6 Эволюция и открытые проблемы

Кража работы в самом Go тоже эволюционирует: в Go 1.1 она появилась вместе с GMP (документ Вьюкова 2012 года), в Go 1.5 у каждого P добавился слот runnext для улучшения локальности и задержки только что порождённого G, а управление крутящимися потоками неоднократно уточнялось.

Этот механизм далёк от «завершённого», и на переднем крае остаётся множество открытых проблем. Учёт NUMA: случайная кража не учитывает локальность памяти, и кража задачи на другой NUMA-узел оплачивается стоимостью удалённого доступа к памяти (9.11). Как ввести предпочтение локальности, сохранив оптимальность балансировки при случайной краже, — по-прежнему активная тема исследований. Противоречие между задержкой и пропускной способностью: LIFO-доступ локально плюс FIFO-кража благоприятны для пропускной способности и кеша, но могут голодать задачи, чувствительные к задержке; все латают это FIFO-слотами, счётчиками справедливости, вытеснением и подобными механизмами. Масштабируемость при большом числе ядер: глобальная очередь и некоординированная случайная кража создают конкуренцию и бесполезные попытки кражи при очень большом числе ядер; меры противодействия (парковка простаивающих потоков, пороги активного ожидания, иерархические очереди) носят в основном эвристический характер. Разрыв между теорией и практикой: чистая оценка $T_1/P+O(T_\infty)$ справедлива только для fork-join DAG, а как дать доказуемые гарантии для общего планирования, которое «блокируется, имеет ввод-вывод и допускает вытеснение», — вопрос в значительной мере открытый.

Дополнительная литература

R. L. Graham. “Bounds on Multiprocessing Timing Anomalies.” SIAM J. Applied Math., 17(2), 1969. https://doi.org/10.1137/0117039 (оценка 2-аппроксимации для жадного/списочного планирования)
Richard P. Brent. “The Parallel Evaluation of General Arithmetic Expressions.” Journal of the ACM, 21(2), 1974. https://doi.org/10.1145/321812.321815
Robert D. Blumofe and Charles E. Leiserson. “Scheduling Multithreaded Computations by Work Stealing.” FOCS 1994; Journal of the ACM, 46(5), 1999. https://doi.org/10.1145/324133.324234 (три оценки: время/память/коммуникации)
Nimar S. Arora, Robert D. Blumofe, C. Greg Plaxton. “Thread Scheduling for Multiprogrammed Multiprocessors.” SPAA 1998. https://doi.org/10.1145/277651.277678 (неблокирующий дек для кражи)
David Chase and Yossi Lev. “Dynamic Circular Work-Stealing Deque.” SPAA 2005. https://doi.org/10.1145/1073970.1073974
Matteo Frigo, Charles E. Leiserson, Keith H. Randall. “The Implementation of the Cilk-5 Multithreaded Language.” PLDI 1998. https://doi.org/10.1145/277650.277725 (принцип work-first, THE-протокол, компиляция с двумя клонами)
Doug Lea. “A Java Fork/Join Framework.” ACM Java Grande 2000. https://doi.org/10.1145/337449.337465
Daan Leijen, Wolfram Schulte, Sebastian Burckhardt. “The Design of a Task Parallel Library.” OOPSLA 2009. https://doi.org/10.1145/1640089.1640106
F. Warren Burton and M. Ronan Sleep. “Executing Functional Programs on a Virtual Tree of Processors.” FPCA 1981. (ранний источник идеи кражи работы)
Carl Lerche. Making the Tokio scheduler 10x faster, 2019. https://tokio.rs/blog/2019-10-scheduler (заимствование Tokio алгоритма локальной очереди Go)
Dmitry Vyukov. Scalable Go Scheduler Design Doc, 2012. https://go.dev/s/go11sched
Chris Hines et al. runtime: scheduler work stealing slow for high GOMAXPROCS. Go issue #28808, 2018. https://github.com/golang/go/issues/28808 (стоимость сканирования при краже при высоком параллелизме)