Планирование в Go : Часть II - Go Scheduler

О чем будем говорить: перевод статьи

Перевод сделан автором сайта goxpert.ru

• Go использует планировщик для управления выполнением программ и распределением ресурсов.
• Планировщик учитывает тонкости работы операционной системы и аппаратного обеспечения.
• Go-планировщик позволяет превратить работу с вводом-выводом/блокировкой в работу, связанную с процессором.
• Использование Goroutines позволяет выполнять больше работы с течением времени, используя меньше потоков операционной системы.
• Планировщик Go помогает повысить эффективность работы с кэш-памятью и NUMA.
• Разработчикам важно понимать семантику Go-планировщика для принятия эффективных инженерных решений.

Введение

В первой части этой серии о планировании я объяснил аспекты планировщика операционной системы, которые, на мой взгляд, важны для понимания и оценки семантики Go scheduler. В этом посте я объясню на семантическом уровне, как работает Go scheduler, и сосредоточусь на поведении высокого уровня. Go scheduler - сложная система, и мелкие механические детали не важны. Важно иметь хорошую модель того, как все работает и как себя вести. Это позволит вам принимать более эффективные инженерные решения.

Запуск вашей программы

Когда ваша программа Go запускается, ей присваивается логический процессор (P) для каждого виртуального ядра, которое идентифицировано на хост-компьютере. Если у вас процессор с несколькими аппаратными потоками на физическое ядро (Гиперпоточность), каждый аппаратный поток будет представлен вашей программе Go как виртуальное ядро. Чтобы лучше понять это, взгляните на системный отчет для моего MacBook Pro.

Вы можете видеть, что у меня один процессор с 4 физическими ядрами. Чего в этом отчете нет, так это количества аппаратных потоков, приходящихся на одно физическое ядро. Процессор Intel Core i7 поддерживает технологию Hyper-Threading, что означает наличие 2 аппаратных потоков на каждое физическое ядро. Программа Go сообщит, что 8 виртуальных ядер доступны для параллельного выполнения потоков операционной системы.

Чтобы протестировать это, рассмотрим следующую программу:

Листинг 1

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

package main

import (
	"fmt"
	"runtime"
)

func main() {
    // NumCPU returns the number of logical
    // CPUs usable by the current process.
    fmt.Println(runtime.NumCPU())
}

Когда я запускаю эту программу на своем локальном компьютере, результатом вызова функции NumCPU() будет значение 8. Любой программе Go, которую я запускаю на своем компьютере, будет присвоено 8 баллов.

Каждому P назначается поток операционной системы (“M”). ‘M’ означает machine. Этот поток по-прежнему управляется операционной системой, и операционная система по-прежнему отвечает за размещение потока в ядре для выполнения, как описано в последнем сообщении. Это означает, что когда я запускаю программу Go на своем компьютере, у меня есть 8 потоков, доступных для выполнения моей работы, каждый из которых по отдельности подключен к P.

Каждой программе Go также задается начальная подпрограмма(назовем ее initial Goroutine или началная горутина) (“G”), которая является путем выполнения программы Go. Goroutine по сути является сопрограммой - корутиной, но это Go, поэтому мы заменяем букву “C“ на “G” и получаем слово Goroutine. Вы можете рассматривать Goroutines как потоки уровня приложения, и они во многом похожи на потоки операционной системы. Точно так же, как потоки операционной системы включаются и выключаются из контекста в ядре, рабочие программы включаются и выключаются из контекста в M.

Последняя часть головоломки - это очереди запуска. В планировщике Go есть две разные очереди запуска: глобальная очередь запуска (GRQ) и локальная очередь запуска (LRQ). Каждому P присваивается LRQ, который управляет программами, назначенными для выполнения в контексте P. Эти программы по очереди включаются и выключаются в зависимости от контекста. M, назначенный для этого P. GRQ предназначен для программ, которым еще не назначен P. Существует процесс перемещения Goroutines из GRQ в LRQ, который мы обсудим позже.

На рисунке 2 представлено изображение всех этих компонентов вместе.

Сотрудничающий планировщик (Cooperating Scheduler)

Как мы обсуждали в первом посте, планировщик операционной системы(OS scheduler) является упреждающим планировщиком(preemptive scheduler). По сути, это означает, что вы не можете предсказать, что планировщик собирается делать в любой момент времени. Решения принимает ядро, и все недетерминировано. Приложения, работающие поверх ОС, не имеют никакого контроля над тем, что происходит внутри ядра с помощью планирования, если только они не используют примитивы синхронизации, такие как атомарные инструкции и мьютексные вызовы. Другими словами, можно сделать в вытесняющем режиме, что-то запланированное только при помощи примитивов синхронизации (атомики, мьютексы, семафоры(кстати, хорошая статья для с++ шников), вайтгрупы и т.д)

Планировщик Go является частью среды выполнения Go, а среда выполнения Go встроена в ваше приложение. Это означает, что планировщик Go выполняется в пространстве пользователя, над ядром. Текущая реализация Go scheduler - это не упреждающий планировщик(preemptive scheduler вытесняющий планировщик), а сотрудничающий(кооперативный) планировщик. Наличие сотрудничающего планировщика означает, что планировщику нужны четко определенные события пользовательского пространства, которые происходят в безопасных точках кода для принятия решений о планировании.

Что замечательного в совместном планировщике Go, так это то, что он выглядит и ощущается упреждающим(feels preemptive - похож на вытесняющий). Вы не можете предсказать, что будет делать планировщик Go. Это связано с тем, что принятие решений для этого взаимодействующего планировщика находится не в руках разработчиков, а в среде выполнения Go(runtime packege). Важно рассматривать Go scheduler как планировщик с вытеснением, а поскольку планировщик недетерминирован( non-deterministic), это не является большой натяжкой.

Состояния Горутин (Goroutine States)

Точно так же, как потоки, горутины имеют те же три состояния высокого уровня. Они определяют роль, которую планировщик Go выполняет в любой заданной горутины. Горутина может находиться в одном из трех состояний: Ожидание(Goroutine States), Возможность выполнения или Готовность к выполнению(Runnable) или Выполнение(Executing).

Ожидание(Waiting): Это означает, что горутина остановлена и ожидает чего-либо, чтобы продолжить. Это может быть по таким причинам, как ожидание операционной системы (системные вызовы system calls или syscall) или вызовы синхронизации(synchronization calls или synccall) (атомарные операции - atomi и мьютексы mutex). Эти типы задержек(latencies) являются основной причиной низкой производительности.

Готовность к выполнению (Runnable): Это означает, что горутине требуется время на M, чтобы она могла выполнить назначенные инструкции. Если у вас много рабочих горутин, которым нужно время, то им придется ждать дольше, чтобы получить время для выполнеия. Кроме того, индивидуальный промежуток времени, который получает любая конкретная горутина, сокращается по мере того, как все больше горутин соревнуются(compete) за время. Этот тип задержки планирования(scheduling latency) также может быть причиной низкой производительности( bad performance).

Выполнение(Executing): Это означает, что горутина была помещена в M и выполняет свои инструкции. Работа, связанная с приложением, выполняется. Это то, чего хотят все.

Переключение контекста (Context Switching)

Планировщику Go требуются четко определенные события пользовательского пространства, которые происходят в безопасных точках кода для контекстного переключения. Эти события и безопасные точки(safe points) проявляются в вызовах функций. Вызовы функций критически важны для работоспособности Go scheduler. Сегодня (с Go 1.11 или менее), если вы запускаете какие-либо жесткие циклы(tight loops), которые не выполняют вызовы функций, вы вызываете задержки в планировщике и сборку мусора. Критически важно, чтобы вызовы функций выполнялись в разумные сроки(reasonable timeframes).

• Примечание: Есть предложение для версии 1.12, которое было принято для применения некооперативных методов вытеснения внутри Go scheduler, позволяющих вытеснять жесткие циклы(tight loops).

В ваших программах Go происходят четыре класса событий, которые позволяют планировщику принимать решения о планировании. Это не означает, что это всегда будет происходить в одном из этих событий. Это означает, что планировщик получает такую возможность.

• Использование ключевого слова go
• Сборка мусора (Garbage collection)
• Системные вызовы (System calls) например Netwokr Poller(asyc syscalls) или чтение файла
• Синхронизация и оркестровка (Synchronization and Orchestration)

Использование ключевого слова go

Ключевое слово go - это то, как вы создаете рабочие горутины. Как только новая рабочая горутина создана, это дает планировщику возможность принять решение о планировании.

Сборка мусора (Garbage collection - GC)

Поскольку GC запускается с использованием собственного набора горутин, для запуска этих горутин требуется время на M. Это приводит к тому, что GC создает большой хаос в планировании. Однако планировщик очень хорошо разбирается в том, что делает горутина, и использует этот интеллект для принятия разумных решений. Одним из разумных решений является переключение контекста горутины, которая хочет коснуться кучи(лезут в хип(heap)), с теми, которые не касаются кучи во время GC. Когда GC запущен, принимается множество решений о планировании.

Системные вызовы (System calls or syscalls)

Если горутина выполняет системный вызов(syscalls), который заставляет блокировать M, то иногда планировщик способен контекстно переключать(context-switching) горутину в состояние off(waiting) с M на новую горутину на ту же самой M. Однако иногда требуется новая M для продолжения выполнения гурутин, которые поставлены в очередь в P. Как это работает, будет объяснено более подробно в следующем разделе.

Синхронизация и оркестровка (Synchronization and Orchestration)

Если атомарный вызов, мьютекс или операция над каналом вызовут блокировку гурутины, то планировщик может переключить контекст для запуска новой горутины. Как только горутина снова сможет выполняться, ее можно повторно поставить в очередь и, в конечном итоге, снова переключить контекст на M.

Асинхронные системные вызовы (Asynchronous System Calls)

Когда ваша операционная система, в которой вы работаете, имеет возможность обрабатывать системный вызов асинхронно, для более эффективной обработки системного вызова можно использовать так называемый сетевой опросник (network poller - NP). Это достигается с помощью kqueue (macOS), epoll (Linux) или iocp (Windows) в соответствующих операционных системах.

Системные вызовы на основе сети могут обрабатываться асинхронно многими операционными системами, которые мы используем сегодня. Отсюда и название network poller, поскольку его основное назначение - обработка сетевых операций. Используя сетевой опросник NP для сетевых системных вызовов, планировщик может запретить горутинам блокировать M при выполнении этих системных вызовов. Это помогает сохранить M доступным для выполнения других горутин в LRQ(Local Run Queue) P без необходимости создавать новые Ms. Это помогает снизить нагрузку на операционную систему при планировании.

Лучший способ увидеть, как это работает, - это просмотреть пример.

Рисунок 3

На рисунке 3 показана наша базовая схема планирования. Goroutine-1(G1 горутина) выполняется на M, и еще 3 горутины ожидают в LRQ получения своего времени на M. Сетевой опросник(NetPoller) простаивает, ему нечего делать.

Рисунок 4

На рисунке 4 Goroutine-1(G1) хочет выполнить сетевой системный вызов, поэтому Goroutine-1(G1) перемещается в сетевой опросник и обрабатывается как асинхронный сетевой системный вызов. Как только Goroutine-1(G1) перемещается в сетевой опросник, M теперь доступен для выполнения другой гурутины из LRQ. В этом случае Goroutine-2(G2) переключается по контексту на M.

Рисунок 5

На рисунке 5 сетевой опросник завершает асинхронный сетевой системный вызов, и Goroutine-1(G1) перемещается обратно в LRQ для P. Как только Goroutine-1(G1) может быть снова переключена по контексту на M, связанный с Go код, за который она отвечает, может выполняться снова. Большим преимуществом здесь является то, что для выполнения сетевых системных вызовов не требуется дополнительных Мс. Сетевой опросник имеет отделный поток операционной системы, и он обрабатывает эффективный цикл обработки событий (event loop)

Синхронные системные вызовы (Synchronous System Calls)

Что происходит, когда горутина хочет выполнить системный вызов, который не может быть выполнен асинхронно? В этом случае сетевой опросник не может быть использован, и горутина, выполняющая системный вызов, заблокирует M. Это прискорбно, но предотвратить это невозможно. Одним из примеров системного вызова, который нельзя выполнить асинхронно, являются системные вызовы на основе файлов(file-based system calls). Если вы используете CGO, могут возникнуть другие ситуации, когда вызов функций C также заблокирует M .

• Примечание: ОС Windows имеет возможность асинхронного выполнения системных вызовов на основе файлов. Технически при работе в Windows можно использовать сетевой опросник.

Давайте рассмотрим, что происходит с синхронным системным вызовом (например, файловым вводом-выводом), который вызывает блокировку M.

На рисунке 6 снова показана наша базовая схема планирования, но на этот раз Goroutine-1(G!) собирается выполнить синхронный системный вызов, который заблокирует M1.

На рисунке 7 планировщик может определить, что Goroutine-1(G1) вызвала блокировку M. На этом этапе планировщик отсоединяет M1 от P, при этом блокирующая Goroutine-1(G1) все еще подключена. Затем планировщик вводит новый M2 для обслуживания P. На этом этапе в LRQ можно выбрать Goroutine-2(G2) и включить M2 с контекстным переключением. Если M уже существует из-за предыдущей замены, этот переход выполняется быстрее, чем создание нового M.

На рисунке 8 системный вызов блокировки, выполненный Goroutine-1(G1), завершается. На этом этапе Goroutine-1(G1) может вернуться в LRQ и снова обслуживаться P. Затем M1 помещается сбоку для использования в будущем, если этот сценарий потребуется повторить

Кража работы (Work Stealing)

Еще одним аспектом планировщика является то, что он забирает работу. В нескольких областях это помогает поддерживать эффективность планирования. Во-первых, последнее, чего вы хотите, - это чтобы M переходил в состояние ожидания, потому что, как только это произойдет, ОС контекстно отключит M от ядра. Это означает, что P не может выполнить какую-либо работу, даже если есть горутина в работоспособном(runnable - готовая к работе) состоянии, пока M не будет снова переключено по контексту в ядре. Кража работы также помогает сбалансировать графики работы по всем логическим процессорам Ps, чтобы работа была лучше распределена и выполнялась эффективнее.

Давайте рассмотрим пример. Let’s run through an example.

На рисунке 9 у нас есть многопоточная программа Go с двумя P, обслуживающими четыре горутины каждая, и одной грутины(G9) в GRQ. Что произойдет, если один из P быстро выполнит все свои программы?

На рисунке 10 у P1 больше нет программ для выполнения. Но есть программы в состоянии выполнения, как в LRQ для P2, так и в GRQ. Это момент, когда P1 нужно украсть работу.
Правила для кражи работы следующие.

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

runtime.schedule() {
    // only 1/61 of the time, check the global runnable queue for a G.
    // только в одном 1 из 61 тиков проверяйте GRQ очередь на наличие G.
    // if not found, check the local queue.
    // если G не найдена, проверьте локальную очередь.
    // if not found,
    // если G не найдена в локальной, то
    //     try to steal from other Ps.
    //     попробуйте украсть у других Ps.
    //     if not, check the global runnable queue.
    //     если нет у Ps,то  опять проверьте GRQ очередь
    //     if not found, poll network.
    //      если нет в GPQ, то опросите сеть (NP)
}

Итак, основываясь на правилах, приведенных в листинге 2, P1 необходимо проверить P2 на наличие подпрограмм в своем LRQ и взять половину того, что он найдет.

Рисунок 11

На рисунке 11 половина горутин взята из P2, и теперь P1 может выполнять эти программы.

Что произойдет, если P2 завершит обслуживание всех своих горутин, а у P1 в LRQ ничего не останется?

Рисунок 12

На рисунке 12 P2 завершил всю свою работу, и теперь ему нужно немного украсть. Сначала он проверит LRQ P1, но не найдет никаких горутин. Затем он посмотрит на GRQ. Там он найдет Goroutine-9.

Рисунок 13

На рисунке 13 P2 крадет Goroutine-9(G9) из GRQ и начинает выполнять работу. Что замечательно во всей этой краже работы, так это то, что это позволяет Ms оставаться занятой и не простаивать. Такое воровство работы внутренне рассматривается как раскручивание M. У этого раскручивания есть и другие преимущества, которые Джей Би Ди хорошо объясняет в своем блоге о воровстве работы.

Практический пример (Practical Example)

Теперь, когда механика и семантика на месте, я хочу показать вам, как все это объединяется, чтобы позволить Go scheduler выполнять больше работы с течением времени. Представьте себе многопоточное приложение, написанное на C, где программа управляет двумя потоками операционной системы(two OS Threads), которые передают сообщения друг другу

Рисунок 14

На рисунке 14 показаны 2 потока(2 Threads T1 and T2), которые передают сообщение туда и обратно. Поток 1(T1) переключается по контексту на ядре 1(C1) и теперь выполняется(executing), что позволяет потоку 1(T1) отправить свое сообщение потоку 2(T2).

Примечание: Способ передачи сообщения не имеет значения. Важно состояние потоков по мере выполнения этой настройки.

Рисунок 15

На рисунке 15 показано, что после того, как поток 1(T1) завершит отправку сообщения, ему теперь нужно дождаться ответа. Это приведет к тому, что поток 1(T1) отключится от ядра 1(C1) по контексту и перейдет в состояние ожидания(waiting state). Как только поток 2(T2) получает уведомление о сообщении, он переходит в состояние, пригодное для выполнения(runnable state). Теперь ОС может выполнить переключение контекста и запустить поток 2(T2), выполняющийся на ядре, которым, оказывается, является ядро 2(C2). Затем поток 2(T2) обрабатывает сообщение и отправляет новое сообщение обратно в поток 1(T1).

Рисунок 16

На рисунке 16 потоки снова переключают контекст, когда сообщение от потока 2(T2) принимается потоком 1(T1). Теперь поток 2(T2) контекстно переключается из состояния выполнения(executing state) в состояние ожидания( waiting state), а поток 1(T1) контекстно переключается из состояния ожидания(waiting state) в состояние, пригодное для выполнения(runnable state), и, наконец, обратно в состояние выполнения(executing state), что позволяет ему обработать и отправить новое сообщение обратно.

Все эти переключения контекста и изменения состояния требуют времени для выполнения, что ограничивает скорость выполнения работы. Поскольку каждый потенциал переключения контекста требует задержки ~ 1000 наносекунд, и, надеюсь, аппаратное обеспечение выполняет 12 инструкций в наносекунду, вы видите более или менее 12 тысяч инструкций, не выполняющихся во время этих переключений контекста. Поскольку эти потоки также перемещаются между разными ядрами, вероятность возникновения дополнительной задержки из-за пропусков строк кэша(cache-line misses) также высока.

Давайте возьмем тот же пример, но вместо него используем Goroutines и Go scheduler.

Рисунок 17

На рисунке 17 показаны две горутины, которые взаимодействуют друг с другом, передавая сообщение взад и вперед. G1 переключается по контексту на M1, который, оказывается, запущен на ядре 1(С1), что позволяет G1 выполнять свою работу. Работа заключается в том, чтобы G1 отправил свое сообщение на G2.

Рисунок 18

На рисунке 18, как только G1 завершит отправку сообщения, ему теперь нужно дождаться ответа. Это приведет к контекстному отключению G1 от M1 и переводу в состояние ожидания(waiting state). Как только G2 получает уведомление о сообщении, он переходит в состояние, пригодное для выполнения(runnable state). Теперь планировщик Go может выполнить переключение контекста и запустить G2 на M1, который все еще работает на ядре 1(C1). Затем G2 обрабатывает сообщение и отправляет новое сообщение обратно на G1.

Рисунок 19

На рисунке 19 все снова переключается по контексту, когда сообщение, отправленное G2, принимается G1. Теперь контекст G2 - переключается из состояния выполнения в состояние ожидания(executing state to a waiting state), а контекст G1 - переключается из состояния ожидания в состояние, пригодное для выполнения(waiting state to a runnable state), и, наконец, обратно в состояние выполнения(executing state), что позволяет ему обработать и отправить новое сообщение обратно.

На первый взгляд кажется, что ничего не изменилось. Все те же переключения контекста и изменения состояния происходят независимо от того, используете ли вы потоки или горутины. Однако существует существенное различие между использованием потоков и горутинами, которое может быть неочевидным на первый взгляд.

В случае использования горутин для всей обработки используется один и тот же поток(M1 крутится на T1) операционной системы и ядро(C1). Это означает, что с точки зрения операционной системы поток(T1) операционной системы никогда не переходит в состояние ожидания; ни разу. В результате все те инструкции, которые мы потеряли из-за переключения контекста при использовании потоков(T), не теряются при использовании горутин.

По сути, Go превратил IO/Blocking work(работу по вводу-выводу/блокированию) в CPU-bound work (работу с привязкой к процессору) на уровне операционной системы(OS level). Поскольку все переключение контекста происходит на уровне приложения, мы не теряем те же ~ 12 тыс. инструкций (в среднем) на одно переключение контекста, которые мы теряли при использовании потоков(T). В Go те же самые переключения контекста обходятся вам в ~ 200 наносекунд или ~ 2,4 тыс. инструкций. Планировщик также помогает повысить эффективность кэш-памяти и NUMA. Вот почему нам не нужно больше потоков, чем у нас есть виртуальных ядер. В Go со временем можно выполнять больше работы, потому что планировщик Go пытается использовать меньше потоков(T) и делать больше в каждом потоке(T), что помогает снизить нагрузку на ОС и оборудование.

Заключение

Планировщик Go действительно поражает тем, как его дизайн учитывает тонкости работы операционной системы и аппаратного обеспечения. Возможность превращать работу ввода-вывода / блокировки в работу с привязкой к процессору на уровне операционной системы - это то, где мы получаем большой выигрыш в увеличении мощности процессора с течением времени. Вот почему вам не нужно больше потоков ОС, чем у вас виртуальных ядер. Вы можете разумно рассчитывать на выполнение всей вашей работы (с привязкой к процессору и вводу-выводу / блокировке) всего одним потоком ОС на виртуальное ядро. Это возможно для сетевых приложений и других приложений, которым не нужны системные вызовы, блокирующие потоки операционной системы.

Как разработчику, вам все еще необходимо понимать, что делает ваше приложение с точки зрения видов выполняемой вами работы. Вы не можете создавать неограниченное количество программ и ожидать потрясающей производительности. Меньше всегда значит больше, но, понимая семантику Go-scheduler, вы можете принимать более эффективные инженерные решения. В следующем посте я рассмотрю идею использования параллелизма консервативными способами для повышения производительности при сохранении баланса между сложностью, которую вам, возможно, потребуется добавить в код.