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

Original author: Jaana B. Dogan
  • Translation

Задача планировщика в 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.

AdBlock has stolen the banner, but banners are not teeth — they will be back

More
Ads

Comments 8

    0

    Не смог понять, что значит зацикленный поток. Можно на котиках и собачках пояснить?

      +6

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

        +2
        Благодарю! Сегодня же всю команду ознакомлю с этим!
          0

          А, то есть, поток просто крутится и ничего не делает, пока не появится задача. И после ее выполнения не закрывается.

            –2

            Ну, упрощенно говоря, да. В оригинале, кстати, "spinning thread" как раз ближе к "крутящемуся" потоку.

        +3
        Сначала по качеству исходного текста и перевода:

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

        Непонятно, к чему «но», если вторая часть не противоречит первой. Надо было вводным сказать что-то вроде «Возможно, вас удивляет, что...»? Тут странность в исходном тексте.

        > Постоянное упреждение (preemption)

        Перевод как «упреждение» неадекватный, в данном контексте для preemption принятое и понятное слово — «вытеснение».

        > В любой момент M горутин должны быть распределены между N потоками ОС

        Конфликтует с последующим использованием M как системного треда (которых N, как раз по этой цитате). Лучше было бы заменить буквы, их, к счастью, достаточно :)

        По содержанию:

        Вообще не видно связи между выбором между work-sharing и work-stealing, и оптимизацией шедулера, точно так же как причин их жёстко противопоставлять друг другу.

        Work-stealing это метод, неизбежный всегда, потому что ситуация, когда стоят ждущие процессора задачи и процессор освобождается (а другие работают и не должны отвлекаться) — типична и происходит в реальной загруженной машине много раз в секунду. «Мы сделали work stealing» звучит, поэтому, примерно как «мы наконец-то включили мозг при написании шедулера». Это, конечно, хорошо, но вряд ли заслуживает особой публикации.

        Избавление от центрального мьютекса и lock-free — уже ближе к интересному (но тут популярное описание от самого Вьюкова было бы ценнее, эта тема — его давний конёк).

        А вот много других интересных особенностей тут явно упущено. Например, метод и качество определения факта, что M в блокирующем системном вызове или аналогичной библиотечной функции, и реакции на неё. Согласование этого с FFI. Есть ли деление на блокирующие и неблокирующие FFI вызовы, какая граница между ними? Планируют ли они просить scheduler activations, как поддержку от ядра ОС? Ещё, есть проблема (тут, например, она под номером 58) горутин, которые не отдают управление. Элементарно забить такими все GOMAXPROCS, или намеренно, или случайно при больших вычислениях. Собираются ли решать её?
          –2
          Перевод как «упреждение» неадекватный, в данном контексте для preemption принятое и понятное слово — «вытеснение».

          Точно! Спасибо, исправил.

          0

          Тема интересная, но перевод утерял множественное число много раз(поток вместо потоки, например). Выглядит как машинный перевод.

          Only users with full accounts can post comments. Log in, please.