Как стать автором
Обновить

Work-stealing планировщик в Go

Время на прочтение 4 мин
Количество просмотров 19K
Автор оригинала: Jaana B. Dogan

Задача планировщика в Go — распределять запущенные горутины между потоками ОС, которые могут исполняться одним или большим количеством процессоров. В многопоточных вычислениях, возникли две парадигмы в планировании: делиться задачами (work sharing) и красть задачи (work stealing).


  • Work-sharing: Когда процессор генерирует новые потоки, он пытается мигрировать их на другие процессоры, в надежде, что они попадут к простаивающему или недостаточно нагруженному процессору.
  • Work-stealing: Недостаточно нагруженный процессор активно ищет потоки других процессоров и "крадет" некоторые из них.

Миграция потоков происходит реже при work stealing подходе, чем при work sharing. Когда все процессоры заняты, потоки не мигрируют. Как только появляется простаивающий процессор, рассматривается вариант миграции.


В Go начиная с версии 1.1 планировщик реализован по схеме work stealing и был написан Дмитрием Вьюковым. Эта статья подробно объясняет устройство work stealing планировщиков и как он устроен в Go.


Основы планирования


Планировщик Go выполнен по M:N схеме и может использовать несколько процессоров. В любой момент M горутин должны быть распределены между N потоками ОС, которые бегут на максимум GOMAXPROCS процессорах. В Go планировщике используется следующая терминология для горутин, потоков и процессоров:


  • G: горутина
  • M: поток ОС (M от Machine)
  • P: процессор

Далее у нас есть две очереди, специфичные для P. Каждый M должен быть назначен к своему P. P-ы могут не иметь M, если они заблокированы или ожидают окончания системного вызова. В любой момент может быть максимум GOMAXPROCS процессоров — P. В любой момент только один M может исполняться на каждый P. Больше M может создаваться планировщиком, если это требуется.



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


runtime.schedule() {
    // только 1/61 от всего времени, проверить глобальную очередь G
    // если не найдено, проверить локальную очередь
    // если не найдено, то:
    //   попытаться украсть у других P
    //   если не вышло, проверить глобальную очередь
    //   если всё равно не вышло,  поллить (poll) сеть
}

Как только готовая к исполнению G найдена, она исполняется, пока не будет заблокирована.


Заметка: Может показаться, что глобальная очередь имеет преимущество перед локальной, но регулярная проверка глобальной очереди критична для избежания M использования только горутин из локальной очереди.


"Кража" (Stealing)


Когда новая G создается или существующая G становится готовой к исполнению, она помещается в локальную очередь готовых к исполнению горутин текущего P. Когда P заканчивается исполнение G, он пытается вытащить (pop) G из своей очереди. Если список пуст, P выбирает случайным образом другой процессор (P) и пытается украсть половину горутин из его очереди.



В примере выше, P2 не может найти готовых к исполнению горутин. Поэтому он случайно выбирает другой процессор (P1) и крадёт три горутины в свою очередь. P2 теперь сможет их запустить и работа будет более равномерно распределена между процессорами.


Spinning потоки


Планировщик всегда хочет распределить как можно больше готовых к исполнению горутин на много M, чтобы использовать все процессоры, но, в тоже время, мы должны уметь приостанавливать (park) сильно прожорливые процессы, чтобы сохранять ресурсы CPU и энергию. И при этом, планировщик должен также уметь масштабироваться для задач, которые действительно требуют много вычислительной мощности процессора и большую производительность.


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


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


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

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


Простаивающие поток, назначенные на какой-либо P не блокируются, если есть другие M, не назначенные на P. Если создается новая горутина или блокируется M, планировщик проверяет и гарантирует, что есть хотя бы один зацикленный M. Это гарантирует, что все горутины могут быть запущены, если есть возможность и позволяет избежать излишних блокировок/разблокировок M.


Выводы


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


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


Ссылки



Если у вас есть предложения или комментарии, пишите @rakyll.

Теги:
Хабы:
+16
Комментарии 8
Комментарии Комментарии 8

Публикации

Истории

Работа

Go разработчик
122 вакансии

Ближайшие события

Московский туристический хакатон
Дата 23 марта – 7 апреля
Место
Москва Онлайн
Геймтон «DatsEdenSpace» от DatsTeam
Дата 5 – 6 апреля
Время 17:00 – 20:00
Место
Онлайн