Go under the hood
Go: Under the Hood

9.4 Цикл планирования

Предыдущие разделы подготовили материал: мы знаем, что такое G, M и P (9.3), и знаем, как M находит работу (9.2). Этот раздел запускает всё в движение — мы наблюдаем, как цикл планирования непрерывно выбирает горутины и выполняет их в рамках одного потока, и как он удерживает баланс между «позволить отдельной горутине чуть дольше занимать процессор» (пропускная способность и локальность) и «не позволить ни одной горутине оголодать» (справедливость).

Весь приведённый ниже код — сокращённые наброски, сохраняющие только каркас, важный для понимания архитектуры, и отбрасывающие побочные ветки, такие как GC, трассировка, профилирование и блокировка потоков. Полные определения можно сверить с runtime/proc.go; все версии ниже соответствуют go1.26.

9.4.1 Цикл, который никогда не возвращается

Планировщик Go основан на принципе «кооперативное выполнение до момента уступки»: выбранная горутина работает до тех пор, пока добровольно не уступит управление, не заблокируется или не будет вытеснена (9.7) — а не прерывается по истечении фиксированного кванта времени посредством прерывания от таймера, как это делает ядро ОС. После того как рабочий поток стартует из mstart, он в конечном счёте попадает в цикл планирования schedule и с этого момента крутится внутри него вплоть до завершения потока. В самом минимальном виде этот каркас представляет собой двухшаговый цикл:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

// Цикл планирования каждого M (набросок): выполняется на системном стеке g0, никогда не возвращается
func schedule() {
    // Найти готовый к выполнению G (полный порядок поиска описан в 9.2); если ни одного нет,
    // заблокироваться внутри findRunnable до появления работы
    gp, inheritTime, _ := findRunnable()

    // Переключиться на стек gp и начать его выполнение.
    // Управление возвращается сюда через mcall (см. ниже), а не через возврат из функции
    execute(gp, inheritTime)
}

findRunnable никогда не возвращает nil: если получить работу не удаётся, она переводит M в режим активного ожидания (spinning) или засыпает, блокируясь внутри себя до пробуждения — так что schedule не нуждается в ветке обработки ситуации «нечего делать». execute тоже никогда не возвращается: она совершает прыжок на стек пользовательского G, после чего стековый фрейм schedule переиспользуется. Для возврата управления в логику планирования используется переключение стека, описанное в 9.4.2.

flowchart TD
    MS[mstart: поток запускается] --> SC["schedule: выбирает G на g0"]
    SC --> FR["findRunnable: runnext/локальная → глобальная → сеть → кража"]
    FR -->|нашли| EX["execute: casgstatus → _Grunning"]
    FR -->|не нашли| PARK["активное ожидание / stopm, повтор после пробуждения"]
    PARK --> FR
    EX --> GOGO["gogo: переключается на стек G"]
    GOGO --> RUN["G выполняет пользовательский код"]
    RUN -->|блокировка / Gosched / вытеснение| MC["mcall: переключается обратно на g0, запускает колбэк"]
    MC --> SC
    RUN -->|функция завершается| GE["goexit → goexit0: возвращает G в gFree"]
    GE --> SC

Логика планировщика — schedule, findRunnable и другие функции — выполняется на выделенном системном стеке g0 (9.3), а не на стеке пользовательского G. Это обеспечивает чёткое разделение обязанностей: g0 занимается планированием, пользовательский G — работой. По этой же причине schedule никогда по-настоящему не возвращается: она выбирает G, совершает прыжок на его стек, а для возврата управления в логику планирования необходимо переключение стека из следующего раздела, а не обычный возврат из функции.

9.4.2 Два переключения: execute и mcall

В цикле планирования задействованы два переключения стека, работающие в противоположных направлениях. Вместе они составляют физическую реализацию машины состояний горутины из 9.3: машина состояний описывает, какие переходы возможны, а эти две подпрограммы — как именно переход происходит.

Прыжок с g0 на пользовательский G: после того как schedule выбирает G, она вызывает execute. Та переводит G в состояние _Grunning, привязывает его к текущему M, а затем вызывает ассемблерную подпрограмму gogo, которая загружает сохранённый контекст G (поля gobuf из 9.3: sp, pc, bp и другие) обратно в регистры. Управление оказывается на стеке пользовательского G, продолжаясь с того места, где он был последний раз переключён.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

// Запустить gp на текущем M (набросок)
func execute(gp *g, inheritTime bool) {
    mp := getg().m

    mp.curg = gp                          // M и G ссылаются друг на друга
    gp.m = mp
    casgstatus(gp, _Grunnable, _Grunning) // переход в машине состояний: runnable → running
    gp.preempt = false
    gp.stackguard0 = gp.stack.lo + stackGuard
    if !inheritTime {
        mp.p.ptr().schedtick++            // счётчик увеличивается только при старте нового кванта;
                                          // унаследованные кванты не считаются (см. 9.4.3)
    }

    gogo(&gp.sched)                       // загрузить gobuf в регистры, прыгнуть на стек gp, никогда не возвращается
}

Хитрость gogo в том, что это «билет в один конец»: загрузив регистры, она выполняет прямой JMP на pc горутины, не оставляя кода для возврата в планировщик. При первом запуске нового G его pc указывает на пользовательскую функцию fn, а «адрес возврата» из fn был заранее установлен на goexit при построении стека в newproc1 (см. 9.4.4). Поэтому по return из fn управление естественным образом попадает в goexit — именно через эту точку входа управление возвращается обратно в рантайм.

Прыжок с пользовательского G обратно на g0: когда G должен уступить управление (Gosched, блокировка на канале, вытеснение или завершение функции), он в конечном счёте вызывает mcall. Та сохраняет текущий контекст в gobuf горутины, переключается на стек g0 и выполняет колбэк на g0:

1
2
3
4

// mcall(fn) (семантический набросок): сохранить контекст текущего G, переключиться на g0, выполнить fn(gp) на g0
//   1. сохранить pc/sp вызывающего в gp.sched
//   2. переключить SP на стек m.g0
//   3. вызвать fn(gp); fn не должна возвращаться (в конечном счёте она возвращается в schedule)

Конкретный колбэк зависит от причины уступки: добровольная уступка проходит через goschedImpl, которая заново ставит G в очередь и продолжает выполнение schedule; блокирующее ожидание проходит через park_m, которая переводит G в состояние _Gwaiting и затем входит в schedule; завершение выполнения проходит через goexit0. В любом из случаев по завершении колбэка управление возвращается в schedule, и цикл замыкается. Этот круговой маршрут и есть физическая реализация переходов горутины между состоянием «выполняется» и остальными состояниями.

sequenceDiagram
    participant g0 as g0 (стек планировщика)
    participant G as пользовательский G
    g0->>G: execute → gogo (загрузить gobuf, переключиться на стек G)
    Note over G: G выполняет пользовательский код
    G->>g0: mcall (сохранить контекст, переключиться обратно на стек g0)
    Note over g0: выполнить колбэк на g0<br/>goschedImpl / park_m / goexit0
    g0->>g0: вернуться в schedule, выбрать следующий G

9.4.3 Справедливость: никто не должен голодать

Кооперативное планирование несёт в себе неотъемлемый риск: если «наиболее удобный» G из локальной очереди всегда получает управление первым, некоторые G могут не получить его никогда. Для этого schedule устанавливает несколько клапанов справедливости, которые вместе не дают кооперативному планированию приводить к голоданию на практике.

Периодическая проверка глобальной очереди. Прежде чем обратиться к локальной очереди, каждые 61 тиков планирования findRunnable сначала извлекает G из глобальной очереди:

1
2
3
4
5
6
7

// клапан справедливости внутри findRunnable (набросок)
if pp.schedtick%61 == 0 && !sched.runq.empty() {
    lock(&sched.lock)
    gp := globrunqget()   // взять один G из глобальной очереди, минуя локальную
    unlock(&sched.lock)
    // ... если получили — вернуть его напрямую
}

Это устраняет конкретный сценарий голодания: два G, взаимно пробуждающих друг друга, будут передавать управление в рамках локальной очереди, заполняя её и оставляя G из глобальной очереди ждать вечно. Принудительное обращение к глобальной очереди через фиксированный интервал разрушает эту монополию. Следует отметить, что используемый счётчик — schedtick, который увеличивается только при старте нового кванта (см. execute в 9.4.2); унаследованный через runnext квант не учитывается, поэтому «каждые 61» отсчитываются от запусков, действительно начинающих новый квант, а не от каждого переключения G. В комментарии к исходному коду сказано только «для обеспечения справедливости», не поясняя, почему именно 61; широко распространённое утверждение «61 — простое число, это позволяет избежать резонанса» является народной спекуляцией, и в данной книге мы принимаем лишь сам факт «61».

Ограничение runnext для предотвращения голодания. G, только что пробуждённый или только что порождённый оператором go, помещается в слот runnext своего P для первоочередного запуска и наследует остаток кванта текущего G (inheritTime, второе значение, возвращаемое runqget в 9.4.2). Это позволяет паре горутин «взаимодействие — затем выполнение» планироваться компактно как единица, что улучшает локальность кэша. Однако runnext можно использовать и во вред: два G, вызывающие runnext друг для друга, могут монополизировать процессор. Рантайм полагается на вытеснение по кванту со стороны sysmon (9.8) как на подстраховку. В исходном коде есть примечательная деталь: для платформ без sysmon (например, wasm) рантайм полностью отключает runnext:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

// runqput (набросок): поместить gp в локальную очередь; если next равно true — в слот runnext
func runqput(pp *p, gp *g, next bool) {
    if !haveSysmon && next {
        // runnext разделяет квант с текущим G (inheritTime).
        // Без вытеснения sysmon как подстраховки пара взаимно вызывающих runnext горутин
        // заморит голодом всех остальных, поэтому runnext здесь необходимо отключить.
        next = false
    }
    // ... если next равно true — CAS в pp.runnext; иначе — поставить в хвост; если очередь полна — перелить в глобальную
}

Это показательный момент с точки зрения архитектуры: справедливость — не один механизм, а результат совместной работы нескольких. runnext обеспечивает пропускную способность и локальность ценой потенциального взаимного голодания; эта цена компенсируется вытеснением со стороны sysmon; когда же этот механизм вытеснения исчезает, оптимизация, на него опирающаяся, должна быть также отключена.

Полный порядок выбора горутин по-прежнему соответствует описанному в 9.2, упорядоченному от наибольшей частоты попаданий к наименьшей и от наименьших затрат на синхронизацию к наибольшим:

flowchart LR
    A["runnext + локальная очередь<br/>(на P, без блокировок)"] --> B["глобальная очередь<br/>(требует sched.lock)"]
    B --> C["сетевой поллер netpoll<br/>(горутины с готовым I/O)"]
    C --> D["кража у других P<br/>(случайный P, украсть половину)"]
    D --> E["всё пусто: активное ожидание / stopm"]

Только когда все источники исчерпаны, поток переходит в режим активного ожидания (кратковременный busy-wait в расчёте на скорое появление работы) или засыпает через stopm. Сам по себе этот порядок «сначала локальная, затем глобальная, в конце — кража» является компромиссом между пропускной способностью и справедливостью: ранние шаги дёшевы и способствуют локальности, а более поздние гарантируют, что работа в итоге будет подхвачена каким-либо простаивающим M.

9.4.4 Рождение и смерть горутины

За пределами цикла находятся два конца.

Рождение. Оператор go f() компилятор транслирует в вызов newproc, который выполняет построение G на системном стеке:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

// newproc (набросок): точка приземления go f()
func newproc(fn *funcval) {
    gp := getg()
    pc := sys.GetCallerPC()
    systemstack(func() {
        newg := newproc1(fn, gp, pc, false, waitReasonZero) // см. ниже

        pp := getg().m.p.ptr()
        runqput(pp, newg, true) // next=true: поместить в runnext, чтобы новый G запустился первым и рядом

        if mainStarted {
            wakep() // если есть свободный P и спящий M — разбудить один, чтобы добавить параллелизм
        }
    })
}

В newproc1 и происходит фактическое построение G, и здесь воплощена философия «сначала переиспользование»: сначала берётся уже использованный G (вместе со стеком) из свободного списка gFree своего P, и только если там пусто — выделяется новый из кучи; затем обнуляется его контекст, sched.pc указывается на пользовательскую функцию, а «адрес возврата» из fn заранее устанавливается на goexit (именно поэтому в 9.4.2 G «естественно попадает в goexit» после прыжка gogo), и, наконец, G переводится в состояние _Grunnable. runqput(pp, newg, true) помещает только что порождённый G в runnext, позволяя типичному паттерну «порождение — затем выполнение» запускаться компактно; wakep затем будит M при наличии свободного параллелизма, как можно скорее превращая новый G в реальный параллелизм.

Смерть. Когда функция G завершается, управление попадает не к вызывающему, а на заранее установленный рантаймом goexit, который через goexit1 → mcall(goexit0) переключается обратно на g0, где goexit0 производит очистку:

1
2
3
4
5
6
7
8

// goexit0 (набросок): утилизировать завершившийся G на g0
func goexit0(gp *g) {
    casgstatus(gp, _Grunning, _Gdead) // переход в машине состояний: running → dead
    // ... очистить поля gp: defer, panic, метка, привязка к M и т.д.
    dropg()                            // развязать M и G
    gfput(pp, gp)                      // вернуть G (вместе со стеком) в gFree своего P для повторного использования
    schedule()                         // вернуться в цикл планирования, никогда не возвращается
}

G не освобождается, а помещается обратно в gFree, избегая повторного выделения структуры G и начального стека. Именно поэтому высокочастотное создание горутин остаётся дешёвым: начиная со второго вызова go f() рантайм в основном извлекает старый G из gFree и корректирует точку входа, а не строит его с нуля. Рождение берёт из gFree, смерть возвращает в gFree; оба конца симметрично разделяют один и тот же свободный список на уровне P — тот же приём «послойного снижения конкуренции», что и в кэше аллокатора на уровне P (12.2).

9.4.5 Эволюция архитектуры

Цикл не принял нынешнюю форму сразу; каждый из его клапанов соответствует усвоенному уроку из истории. Прослеживая нить эволюции, мы можем объяснить происхождение констант и ограничений, которые раньше казались произвольными.

flowchart LR
    A["до Go 1.0<br/>единая глобальная runq + одна большая блокировка"]
    A -->|"редизайн Вьюкова, 2012"| B["Go 1.1<br/>локальная очередь на P<br/>+ кража работы + spinning M"]
    B -->|"runnext + клапан 61"| C["добавлено постепенно<br/>оптимизация локальности + защита от голодания"]
    C -->|"proposal 24543"| D["Go 1.14<br/>асинхронное вытеснение по сигналу"]

Ранний планировщик (Go 1.0 и до него) имел лишь одну глобальную очередь запуска в паре с одной глобальной блокировкой. Каждому M для взятия или постановки G приходилось конкурировать за эту блокировку, что становилось узким местом по мере роста числа ядер. В своём проектном документе 2012 года Вьюков отправился именно от этой боли, предложив схему с локальной очередью на P, кражей работы и spinning M — всё это было реализовано в Go 1.1. Этот шаг заложил всю основу для 9.2 и данного раздела: локальная очередь делает подавляющее большинство операций взятия и постановки безблокировочными, кража гарантирует, что работа не зависнет на каком-то P, а spinning M на короткое время занимается активным ожиданием перед дорогостоящей операцией пробуждения нового потока — рассчитывая, что работа вот-вот появится.

Локальная очередь решила проблему конкуренции, но породила проблему справедливости, что привело к двум патчам из 9.4.3: слот runnext обеспечивает локальность для пары G «взаимодействие — затем выполнение», а проверка глобальной очереди каждые 61 тиков закрывает брешь, при которой взаимно пробуждающая себя пара G монополизирует локальную очередь. Эти патчи применялись постепенно, устраняя побочные эффекты после того, как схема с локальной очередью прижилась.

Последний недостающий элемент — вытеснение. Ранее оно было кооперативным и происходило только при проверке стека в прологе функции; плотный цикл без вызовов функций (например, for {}) мог вечно удерживать P, не уступая управление, замораживая даже STW на неопределённый срок. В Go 1.14 было введено асинхронное вытеснение по сигналу (proposal 24543): рантайм отправляет сигнал целевому потоку и принудительно перехватывает управление в безопасной точке. Это закрыло последнюю прореху в кооперативном планировании и стало именно той подстраховкой, на которую рассчитывает runnext из 9.4.3.

9.4.6 Взгляд со стороны теории планирования

Обобщая несколько клапанов schedule, планировщик Go представляет собой гибрид «кооперативного выполнения до уступки + добровольной уступки + асинхронного вытеснения по сигналу как подстраховки». Он занимает среднее место на спектре архитектур планирования.

Чисто кооперативное планирование (ранние потоки пользовательского пространства, цикл событий Node в рамках одной задачи) обладает высокой пропускной способностью и дешёвым переключением, поскольку точка уступки определяется самой программой, без необходимости сохранять полный контекст прерывания; недостаток в том, что задача, не уступающая управления, может блокировать всё остальное, а справедливость целиком зависит от добросовестности программы. Чисто вытесняющее планирование по кванту (потоки ядра) справедливо и не зависит от кооперации задач, но требует дорогого переключения и непредсказуемых точек вытеснения, что неблагоприятно для локальности.

Go занимает позицию между этими двумя полюсами: по умолчанию оно достигает пропускной способности и локальности через кооперативную уступку (каналы, Gosched, проверка вытеснения в прологе функции) и кражу работы (9.2), а затем использует асинхронное вытеснение, управляемое sysmon примерно раз в 10 мс (9.7), как подстраховку справедливости, гарантируя, что даже чисто вычислительный G без точек уступки в конечном счёте будет переключён. Деталь из 9.4.3 — «нет sysmon — отключить runnext» — это и есть внутренняя логика данного гибрида, явно обнажённая: когда механизм вытеснения отсутствует, кооперативные оптимизации, опирающиеся на него как на подстраховку, также должны быть отключены.

Это перекликается с вытеснением по счётчику редукций в Erlang/BEAM. BEAM выделяет каждому процессу фиксированный бюджет редукций, уменьшая его на единицу при каждой операции, например при вызове функции, и вытесняет процесс, когда бюджет исчерпан. Обе системы балансируют «дешевизну кооперации» и «справедливость вытеснения», различаясь лишь расположением точки вытеснения: Go помещает её в проверку стека при вызове функции и в асинхронные сигналы, а BEAM — в подсчёт редукций. Подсчёт BEAM детерминирован и не зависит от реального времени, обеспечивая более равномерную гранулярность справедливости; вытеснение Go по сигналу срабатывает по реальному времени, имеет более лёгкую реализацию и естественнее вписывается в безопасные точки GC. Не существует «идеального» планирования (9.1 обсуждал нижнюю границу конкурентного отношения для онлайн-планирования); несколько клапанов schedule — это конкретный и взвешенный ответ Go на компромисс между пропускной способностью, задержкой и сложностью реализации.

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

  1. Dmitry Vyukov. Scalable Go Scheduler Design Doc, 2012. https://go.dev/s/go11sched (происхождение архитектуры кражи работы + spinning M)
  2. The Go Authors. runtime/proc.go (schedule, findRunnable, execute, mcall, goschedImpl, newproc, goexit0, runqput). go1.26. https://github.com/golang/go/blob/master/src/runtime/proc.go
  3. The Go Authors. runtime/asm_amd64.s (ассемблерные реализации gogo и mcall). https://github.com/golang/go/blob/master/src/runtime/asm_amd64.s
  4. Robert D. Blumofe, Charles E. Leiserson. Scheduling Multithreaded Computations by Work Stealing. JACM 46(5), 1999. https://doi.org/10.1145/324133.324234 (теоретическая основа кражи работы)
  5. Erik Stenman. The BEAM Book: Scheduling. https://blog.stenmans.org/theBeamBook/#CH-Scheduling (сравнение с вытеснением по счётчику редукций)
  6. Nimrod Aviram et al. / The Go Authors. Goroutine preemption (архитектура асинхронного вытеснения), Go 1.14. https://github.com/golang/proposal/blob/master/design/24543-non-cooperative-preemption
  7. Phil Hofer et al. runtime: scheduler is slow when goroutines are frequently woken. Go issue #18237, 2016. https://github.com/golang/go/issues/18237 (эмпирические измерения задержки пробуждения spinning M)
  8. Эта книга: 9.2 Стратегия планирования, 9.3 G, M, P и машина состояний, 9.7 Вытеснение, 9.8 Системный мониторинг.