Лезем в сорцы компилятора — как работает goscheduler (Часть I)

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

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

Про перевод слова конкурренси

Первое правило параллелизма в го звучит так

Concurrency is not parallelism

— Andrew Gerrand, 16 January 2013

Замечательно. Мы все это слышали. Давайте теперь напишем это по-русски:


Параллелизм — это не конруренси… Звучит убого, давайте переведём concurrency на русский. Облом. Думаю, что слово согласованность подходит лучше других. Ладно, будем жить с этим словом дальше.

Часть первая, в которой мы издеваемся над операционной системой и получаем представление об ужасной жизни несчастных потоков исполнения, созданных через CreateThread.

Введение в многопоточность

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

Вот мы выполняем нашу программу, всё хорошо и прекрасно. Инструкции выполняются одна за другой, всё мирно и спокойно. Но, нам пришло в голову, что будет лучше, если мы запустим процесс чтения данных с диска в отдельном потоке. Для этого в Windows мы воспользуемся CreateThread ну или pthread_create в Linux.

Документация Майкрософт показывает следующее примечание:

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

Теперь мы можем читать данные с диска в отдельном потоке. Делов-то, создать основной поток выполнения программы и второй поток для записи данных. Разрабатываем дальше и решаем, что пора уже замахнуться на веб-сервер и переписать nginx.

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

Но это теория. Главный момент ограничений на практике состоит в том, что все эти ограничения в 2 гигабайта памяти и так далее, касаются 32х битных систем. Но мы-то давно знаем, что 64х завоевал весь мир.

Давайте проверим эти вещи на деле:

#include <iostream>
#include <windows.h>

DWORD WINAPI callable(LPVOID lpParam);

int main()
{
    for (int i = 0; i < 1000000; i++) {
        CreateThread(NULL, 0, callable, NULL, 0, NULL);
    }
    std::cin.get();
}

DWORD WINAPI callable(LPVOID lpParam) {
    std::cin.get();
    return NULL;
}

Пишем наипростейшую программу, которая просто стартует 1 миллион потоков. Каждый поток будет просить пользователя ввести какую-нибудь информацию, то есть, моментально блокироваться. Никакой нагрузки на процессор в потоке не будет.

Тестовый стенд, что бог послал, то и будем тестировать:



А сегодня нам был послан Intel Core i7 десятого поколения. Продвинутый мобильный процессор, более чем скромный по серверным меркам, но для тестов подойдёт.

Замечаем, что в данный момент операционная система работает с 3720 потоками.

Запускаем программу с отладчиком и видим, что Visual Studio Debugger невероятно замедляет процесс. После пяти минут работы программа создала только 20000 потоков и работает более или менее нормально, хотя система перестала быть отзывчивой и притормаживает.

Запускаем программу без отладчика. И первые 40000 потоков создаются за доли секунды. Дальше система начинает немного тормозить. Количество потоков вырастает до 150000 в течение пяти секунд. Система начинает тормозить ещё серьёзнее. Все восемь (четыре) ядра загружены на 100%. После этого мы не можем создавать более чем 2000 потоков в секунду, и система медленно тикает, пока счётчик количества потоков не доходит до 180000. Где-то в этом районе система полностью и безвозвратно останавливается. Виснет всё. Мышь не дышит, клавиатура не реагирует, система уходит в полный ступор.

К сожалению, скриншотов этого я показать не могу, так как все они почили вместе с системой, которую пришлось перезагрузить.

Памяти в 12 гигабайт вполне себе хватило для запуска этой программы. Но то, что нас убило, это переключение контекста процессора. Потоки, которые мы создавали, на самом деле ничего не делали.

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

Если вы хотите протестировать свою систему без компилирования программ на С++, то можете воспользоваться замечательной утилитой testlimit64 -t, написанной Марком Руссиновичем, который в этой области ещё как разбирается.

Вернёмся к написанию нашего сервера. Наш сервер будет подвержен DOS атакам. Мы не просто создаём миллионы потоков, мы загружаем их работой, так что жить будет сложнее. Завалить такой сервер можно будет с ноутбука. Так делать нельзя. Вместо того чтобы испытывать кремень процессора на прочность, мы последуем рекомендации Майкрософт и создадим пул потоков. Удобная вещь.

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

Практически любой фреймворк несёт в себе какое-то подобие Thread Pool в С# и Thread Pool в Java. (Ссылки содержат официальную документацию, если кому интересно, но читать это не обязательно)

Первые шаги

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

Так что убедитесь, что вы понимаете, что такое G, M и Р, прежде чем заныривать глубже. Нам предстоит препарировать суслика, тут поверхностным знанием не обойдёшься.

Ладно, так и быть, я признаюсь, нет в мире ни одной статьи о планировщике в голанге, где не была бы показана вот эта картинка:



Ну вот, теперь статью можно считать полноценной.

Обязательно наличие треугольничков, квадратиков и кружочков. Не верите? Идите в гугл и ищите картинки по запросу go scheduler и вы увидите, что я не шучу:



Куда ни ткни, там эти треугольнички, квадратики и кружочки.

Мы посмотрим на все эти G, P и M, но попозже.

Но нам этого мало. Как на самом деле работает планировщик? Что же, ответить на этот вопрос не так-то просто. Давайте залезем в репозиторий go/golang и найдём там настоящий планировщик. src/runtime/proc.go. Вот где собака, суслик зарыт.

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

Именно теперь, у нас уже начинают вылезать интересные факты из жизни сусликов, которые мы и будем исследовать в этой статье.

Лезем глубже

И вот тут вот мы начинаем находить настоящие ответы на наши вопросы.

Почему планировщик в голанге такой прекрасный и хороший? В основу работы этого планировщика положено исследование Роберта Блюмфо и Чарлза Лисерсена под названием “Планирование многопоточных приложений на основе захвата работы”. (Я очень долго думал, как правильно перевести термин Work Stealing и остановился на Захвате Работы.)

Давайте посмотрим на некоторые моменты, описанные в этом документе.

Планирование выполнения это чрезвычайно сложный процесс. С точки зрения операционной системы минимальный блок выполнения — это поток. ОС не может регулировать количество потоков, создаваемых пользователем. Если пользователь хочет, то вот вам фотошоп с лайтрумом и спотифаем работают вместе, создавая армию в 1000 потоков. А если пользователь хочет, то вот вам сервер на линуксе, в котором после старта запускается и мирно спят 150 потоков, не нагружая процессор.

ОС должна распределить эти потоки по процессорам. А так как процессоров у нас обычно меньше, чем потоков, то приходится эти потоки запускать на определённое время, после чего снимать и запускать другие потоки.

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



Внезапно взято из публикации о том, как воровать деньги с криптокошельков… Ссылку не привожу.

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

А кеш у нас не один. Их на каждое ядро — четыре разных штуки. IL and DL это кеши инструкций и данных первого уровня. Дальше на ядре есть кеш второго уровня, и все ядра вместе делят кеш третьего уровня. Если вам очень хочется разобраться в работе кеша в i7, то рекомендую обратиться к официальной документации Интел. Это документ в 50 мегабайт и более чем в 5000 страниц. Информация о работе с кешем находится по всему документу. А если вам хочется почитать что-то за кружкой кофе с утра, то есть вот эта статья, где всё объясняется более понятным языком и намного более компактно.

При работе с кешем задержки будут становиться всё более и более серьёзными. Если верить Process Explorer, то в данный, ненагруженный, момент, моя ОС переключает контекст примерно 20,000 раз в секунду. А при запуске нашей программы-убиваки переключение контекста подскакивает до 700,000 раз в секунду.

Соответственно, операционная система, работая совместно с процессором, должна решить, как правильно выполнить все эти переключения контекста. Переключение контекста выполнения означает дополнительную нагрузку на процессор. А отсутствие переключения означает, что ваш медиаплеер будет лагать и выдавать музыку кусками, поскольку он не будет выполняться достаточно часто.

Для того чтобы выяснить, когда надо производить операцию переключения контекста, ОС использует планировщик задач. Если вы хотите окунуться в мир планировки задач в ОС Windows, то я рекомендую посмотреть на эту замечательную главу из книги Windows Internals, 5th edition (не самое последнее издание, но это есть в открытом доступе в интернете).

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

Кстати, в зависимости от этого же приоритета, процесс может даже и не закончит свой квант, ввиду наличия процесса с большим приоритетом.

Промежуточные итоги

Если вы пытаетесь написать многопоточное приложение, то создание потоков — это не решение ваших проблем. На самом деле, чем меньше потоков вы создадите, тем быстрее они будут выполняться.

Но среда выполнения golang это не операционная система. Это совсем другой уровень приложения. Это просто поток, который работает наравне с другими потоками в ОС.

В golang подход к планированию задач внутри среды исполнения строится на другом принципе, называемом захватом работы. Создаются очереди работы и процессоры, которым нечего делать, и которые будут подбирать эту работу.

В go у вас нет возможности получить доступ к механизму создания новых процессов напрямую. Вообще. Вы можете создавать только горутины, а они уже будут управляться средой выполнения. Как они будут управляться? Давайте посмотрим на это в следующей статье.