Go under the hood
Go: Under the Hood

9.1 Задача планирования и модель GMP

Достаточно написать go f() — и горутина начинает выполняться. За этой единственной строкой стоит самый сложный механизм рантайма Go: планировщик (шедулер). Он должен ответить на вопрос, который совсем не прост: каким образом десятки тысяч горутин могут поочерёдно использовать небольшое число ядер процессора, работая быстро и оставаясь при этом практически незаметными для пользователя. В этом разделе сначала формулируется задача, которую должен решить планировщик, описывается его общая структура и место среди других конкурентных рантаймов. Последующие разделы подробно рассматривают каждый компонент.

9.1.1 Три модели потоков и немного истории

Отображение «конкурентных задач» на «ресурсы исполнения процессора» исторически принимало три формы, и компромиссы, на которые они идут, определяют всё.

  • 1:1 (потоки ядра): каждый пользовательский поток соответствует одному потоку операционной системы. Это даёт истинный параллелизм, блокирующие системные вызовы прозрачно обрабатываются ядром, а реализация проста; цена — каждое создание и переключение потока требует перехода в ядро, и каждый поток должен резервировать стек размером в мегабайты. Этот путь выбрали NPTL в Linux, современная Windows и платформенные потоки Java.
  • N:1 (чисто пользовательские потоки, ранние «зелёные потоки»): множество пользовательских потоков размещается поверх единственного потока ОС. Переключение крайне дёшево, стеки малы; однако использовать несколько ядер невозможно, а один блокирующий системный вызов останавливает все потоки — и это фатальный недостаток модели.
  • M:N (гибридная / двухуровневая): MM пользовательских потоков мультиплексируются на NN потоков ядра. Это одновременно дёшево и параллельно, но требует двух взаимодействующих планировщиков — одного в пользовательском пространстве и одного в ядре, что и является источником сложности.

История делает здесь интересный поворот. В 1990-х на модель M:N возлагались большие надежды, и наиболее влиятельным предложением стали scheduler activations Андерсона и коллег (SOSP 1991): позволить ядру «уведомлять» планировщик пользовательского пространства в моменты блокировки и готовности, чтобы два планировщика кооперировались. Однако в итоге индустрия в основном отступила к модели 1:1. Когда Дреппер и Молнар проектировали NPTL для Linux (2005), они сформулировали причину прямо: M:N требует двух планировщиков, и без кооперации страдает производительность, тогда как стоимость внедрения необходимой инфраструктуры в ядро вместе с бременем поддержки оказалась слишком высока — «не в духе философии ядра Linux». Так Linux выбрал 1:1.

flowchart LR
    subgraph OS[Операционная система]
      M1[Поток M1]
      M2[Поток M2]
    end
    subgraph RT[Рантайм Go]
      direction TB
      P1["P1 · локальная очередь G G G"]
      P2["P2 · локальная очередь G G"]
      GQ["глобальная очередь G G G G"]
    end
    M1 --> P1
    M2 --> P2
    P2 -. кража половины при простое .-> P1
    P1 -. переполнение очереди .-> GQ
    GQ -. периодическое пополнение .-> P2

Go, тем не менее, вернулся к M:N. Причина, по которой ему удалось избежать ловушек прошлого, сводится к трём вещам, и все три находятся в руках самого рантайма: стек горутины мал и способен расти (начиная с нескольких килобайт), поэтому и создание, и переключение обходятся дёшево; рантайм знает каждую точку, в которой возможна блокировка, и может уступить исполнение до того, как она произойдёт; сетевой ввод-вывод обслуживается встроенным сетевым поллером (9.9), где заблокированная горутина приостанавливается, не удерживая поток. Проблему «блокирующего системного вызова», которая в своё время погубила модель N:1, Go решает внутри рантайма, не прибегая к механизму активаций со стороны ядра.

9.1.2 Модель GMP в общих чертах

Интерактивная диаграмма ниже приводит GMP в движение: каждый P содержит локальную очередь выполнения, M привязывается к P и запускает G из головы очереди, а когда локальная очередь некоторого P и глобальная очередь оказываются пустыми, он крадёт половину работы у другого P. Вы можете поставить на паузу, выполнить пошагово или вручную вызвать go func(), чтобы наблюдать за изменениями очередей и кражей работы.

Планировщик Go построен вокруг трёх абстракций, совокупно именуемых GMP.

  • G (goroutine): фрагмент конкурентно исполняемого пользовательского кода вместе со своим стеком и контекстом выполнения.
  • M (machine): поток операционной системы — сущность, которая непосредственно выполняет инструкции на процессоре.
  • P (processor): логический процессор, представляющий «ресурсы и разрешение, необходимые для выполнения кода Go». Число P задаётся параметром GOMAXPROCS и по умолчанию равно числу доступных ядер процессора.

Связь между тремя сущностями в одном предложении: M должен сначала получить P, прежде чем сможет запустить G. Следовательно, число P устанавливает верхнюю границу параллельного исполнения кода Go в любой момент времени. Каждый P несёт собственную локальную очередь выполнения с готовыми к запуску G, а также существует общая для всех P глобальная очередь выполнения в качестве запасного варианта (см. диаграмму выше). Один шаг планирования, упрощённо, — это M, привязанный к P, берущий G из очереди для запуска; когда этот G уступает управление или вытесняется, M берёт следующий; когда локальная очередь пуста, он ищет работу в другом месте — так возникает кража работы (9.2).

Горутина — это стековая (stackful) корутина: она имеет собственный стек, может приостанавливаться из произвольно вложенных вызовов функций и может быть вытеснена. Это фундаментальное отличие от «бесстекового» (stackless) подхода, с которым мы сравним её ниже. Стеки Go сначала были реализованы как сегментированные; начиная с Go 1.3 они были заменены растущими непрерывными стеками (14 Управление стеком исполнения).

9.1.3 Разные ответы на одну задачу

«Как дёшево запускать огромное количество конкурентных единиц исполнения» — это задача, с которой сталкиваются все рантаймы нынешнего поколения, и GMP в Go — лишь один из ответов. Взгляд на то, что выбрали другие, делает позицию GMP яснее.

  • Erlang / BEAM: легковесные процессы, каждый из которых имеет собственную кучу и не разделяет мутабельного состояния; планировщик выполняет вытеснение по счётчику редукций (редукция — это приблизительно один вызов функции); на каждое ядро приходится один планировщик со своей очередью выполнения, дополненный миграцией процессов для балансировки нагрузки. Модель доводит принцип «изоляции» до предела.
  • Виртуальные потоки Java / Project Loom (JEP 444, Java 21, финализирован в 2023): виртуальный поток — это продолжение (continuation) плюс планировщик; он монтируется на платформенный «поток-носитель» (carrier thread) для выполнения и демонтируется при блокировке; в качестве планировщика используется FIFO work-stealing ForkJoinPool с параллелизмом, по умолчанию равным числу доступных ядер. По сути это M:N — именно та модель, которую Дреппер когда-то отверг для Linux и которая теперь возвращается в JVM.
  • GHC Haskell: легковесные потоки мультиплексируются на небольшое число «capabilities» (HEC), примерно равное числу ядер, в сочетании с кражей работы и par-искрами (Marlow и коллеги, ICFP 2009).
  • Rust async / .NET async: используют бесстековый (stackless) подход. Функция async fn компилируется в конечный автомат (Future), где приостановленное состояние хранится в перечислении (enum), а не в отдельном стеке, а управление осуществляется рантаймом наподобие Tokio.

Здесь выявляется ключевая ось проектирования: стековый (stackful) vs бесстековый (stackless). Горутины Go — стековые: ценой одного (растущего) стека на каждую горутину они получают возможность приостанавливаться на любой глубине вложенности и могут быть вытеснены. Rust/.NET async — бесстековые: отдельный стек не нужен, точки приостановки фиксируются на этапе компиляции, но именно поэтому планирование возможно только кооперативное: цикл без .await не может быть прерван рантаймом. Go выбрал стековый подход, и взамен получил именно ту возможность «вытеснять даже бесконечный цикл», которая описана в 9.7.

9.1.4 Откуда взялся P: от GM к GMP

P существовал не с самого начала. В планировщике до Go 1.1 были только G и M: все готовые к выполнению G находились в единственной глобальной очереди, защищённой одним глобальным мьютексом. В 2012 году Дмитрий Вьюков в документе Scalable Go Scheduler Design Doc выделил четыре проблемы этого GM-планировщика:

  1. единственный глобальный мьютекс и централизованное состояние — каждая операция, связанная с горутинами, вынуждена конкурировать за этот мьютекс;
  2. частая передача G между M, нарушающая локальность данных и увеличивающая накладные расходы на переключение;
  3. каждый M несёт ресурсы вроде кеша памяти (mcache), удерживая их даже при блокировке в системном вызове, когда код Go не выполняется, — это расходует память и ухудшает локальность;
  4. системные вызовы приводят к частым блокировкам и пробуждениям потоков.
flowchart LR
    subgraph A["GM (до Go 1.1)"]
      GA["глобальная очередь + единый глобальный мьютекс"] --> MA1[M]
      GA --> MA2[M]
    end
    subgraph B["GMP (начиная с Go 1.1)"]
      PB1["Локальная очередь P"] --> MB1[M]
      PB2["Локальная очередь P"] --> MB2[M]
    end
    A -->|"Документ Вьюкова, 2012"| B

Введение P адресует именно эти проблемы: локальные очереди означают, что большинство операций постановки в очередь и извлечения из неё больше не конкурируют за глобальный мьютекс; перенос ресурсов вроде mcache на P фиксирует их число на уровне GOMAXPROCS и улучшает локальность; отвязка и привязка M и P позволяет потоку, входящему в системный вызов, передать свой P другому M, чтобы тот продолжил работу. Этот GMP-планировщик появился в Go 1.1 (май 2013). Стоит отметить деталь: в заметках к выпуску Go 1.1 эта перестройка планировщика не описана напрямую; в разделе о производительности лишь упомянуто, что «более тесная связь рантайма и сетевых библиотек снижает число переключений контекста при сетевых операциях» — фактически это косвенное свидетельство появления встроенного сетевого поллера. Крупные внутренние перестройки порой происходят вот так тихо.

GOMAXPROCS — это число P. Начиная с Go 1.5 значение по умолчанию равно runtime.NumCPU() (ранее по умолчанию было 1); начиная с Go 1.25, при работе внутри контейнера с ограничением CPU, значение по умолчанию вычисляется как min⁡(CPU limit,core count)\min(\text{CPU limit}, \text{core count}) (с округлением вверх при дробном лимите), и рантайм периодически корректирует его динамически, чтобы избежать избыточного параллелизма в ограниченном контейнере из-за округления до числа ядер хост-машины. Обратите внимание: «1.25» здесь — номер версии Go, а не некий множитель.

9.1.5 Немного теории планирования

Этот подраздел предназначен для заинтересованного читателя; его пропуск не влияет на понимание последующего описания реализации.

Почему не существует «идеального» планировщика? Потому что реальный планировщик работает онлайн: он принимает решения на лету, не зная, когда появятся новые горутины и когда они заблокируются. Офлайн-планировщик, располагающий полной информацией о будущем, всегда может добиться лучшего результата, и разрыв между ними характеризуется коэффициентом конкурентоспособности (competitive ratio) — отношением стоимости онлайн-решения к офлайн-оптимуму в наихудшем случае. Это даёт нам чёткую формулировку: рантайм может быть «доказуемо неплохим», но не может быть «оптимальным».

Насколько же «неплох» онлайн-подход вроде кражи работы? Блумоф и Лейзерсон (JACM, 1999) доказали, что для вычисления с общим объёмом работы T1T_1 и длиной критического пути T∞T_\infty рандомизированная кража работы на PP процессорах завершается за ожидаемое время T1/P+O(T∞)T_1/P + O(T_\infty). T1/PT_1/P — это идеальное линейное ускорение, а O(T∞)O(T_\infty) — последовательный «хвост», который невозможно распараллелить далее. Эта оценка является теоретическим обоснованием того, почему Go, GHC, Erlang и Loom независимо друг от друга выбрали схему «одна очередь на ядро + рандомизированная кража работы». Полная формулировка, идея доказательства и границы применимости (результат нацелен на fork-join-вычисления; для произвольных горутин Go он служит лишь «мотивацией», а не строгой гарантией) подробно обсуждаются в 9.2.

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

  1. Thomas E. Anderson, Brian N. Bershad, Edward D. Lazowska, Henry M. Levy. “Scheduler Activations: Effective Kernel Support for the User-Level Management of Parallelism.” SOSP 1991 / ACM TOCS 10(1), 1992. https://doi.org/10.1145/146941.146944
  2. Ulrich Drepper, Ingo Molnar. The Native POSIX Thread Library for Linux. 2005. https://www.akkadia.org/drepper/nptl-design.pdf (аргументация в пользу модели 1:1)
  3. Dmitry Vyukov. Scalable Go Scheduler Design Doc. 2012. https://go.dev/s/go11sched
  4. Simon Marlow, Simon Peyton Jones, Satnam Singh. “Runtime Support for Multicore Haskell.” ICFP 2009. https://doi.org/10.1145/1596550.1596563
  5. OpenJDK. JEP 444: Virtual Threads. Java 21, 2023. https://openjdk.org/jeps/444
  6. Robert D. Blumofe, Charles E. Leiserson. “Scheduling Multithreaded Computations by Work Stealing.” JACM 46(5), 1999. https://doi.org/10.1145/324133.324234
  7. The Go Authors. Container-aware GOMAXPROCS. 2025. https://go.dev/blog/container-aware-gomaxprocs
  8. Erik Stenman. The BEAM Book (The Erlang Runtime System). https://github.com/happi/theBeamBook
  9. Russ Cox. runtime: clean up scheduler, 2008; things are much better now, 2009. https://github.com/golang/go/commit/96824000ed89d13665f6f24ddc10b3bf812e7f47 , https://github.com/golang/go/commit/fe1e49241c04c748d0e3f4762925241adcb8d7da (ранняя форма планировщика с единой глобальной блокировкой и единственной очередью — отправная точка эволюции, описанной в этом разделе)
  10. Dmitry Vyukov. runtime: improved scheduler, 2013. https://github.com/golang/go/commit/779c45a50700bda0f6ec98429720802e6c1624e8 (ключевой коммит, превративший проект go11sched в реализацию GMP)