Хабрахабр

[Из песочницы] Планирование в Go: Часть I — Планировщик ОС

Привет, Хабр! Представляю вашему вниманию перевод статьи «Scheduling In Go: Part I — OS Scheduler» автора Билла Кеннеди, о том, как работает внутренний планировщик Go.

Этот пост посвящен планировщику операционной системы. Это первый пост в серии из трех частей, который даст представление о механике и семантике, лежащей в основе планировщика в Go. Начнем!

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

Планировщик ОС

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

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

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

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

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

Выполнение инструкций

Счетчик команд (СК), также (instruction pointer) позволяет потоку отслеживать следующую команду для выполнения. В большинстве процессоров СК указывает на следующую инструкцию, а не на текущую.

image

Смотрите + 0x39 и + 0x72 в листинге 1. Если вы когда-либо видели трассировку стека из программы Go, вы могли заметить эти маленькие шестнадцатеричные числа в конце каждой строки.

Листинг 1

goroutine 1 [running]: main.example(0xc000042748, 0x2, 0x4, 0x106abae, 0x5, 0xa) stack_trace/example1/example1.go:13 +0x39 <- Здесь main.main() stack_trace/example1/example1.go:8 +0x72 <- И здесь

Эти числа представляют смещение значения СК от вершины соответствующей функции. Значение смещения + 0x39 для СК представляет следующую инструкцию, которую поток выполнил бы внутри примерной функции, если бы программа не запаниковала. Значение смещения СК 0 + x72 является следующей инструкцией внутри основной функции, если управление вернулось к этой функции. Что еще более важно, инструкция перед указателем сообщает вам, какая инструкция выполнялась.

Посмотрите на программу ниже в листинге 2, которая вызвала трассировку стека из листинга 1.

Листинг 2

// https://github.com/ardanlabs/gotraining/blob/master/topics/go/profiling/stack_trace/example1/example1.go
07 func main() {
08 example(make([]string, 2, 4), "hello", 10)
09 } 12 func example(slice []string, str string, i int) {
13 panic("Want stack trace")
14 }

Шестнадцатеричное число + 0x39 представляет смещение СК для инструкции внутри примерной функции, которая на 57 (основание 10) байтов ниже начальной инструкции для функции. В листинге 3 ниже вы можете увидеть objdump примера функции из двоичного файла. Найдите 12-ю инструкцию, которая указана внизу. Обратите внимание на строку кода над этой инструкцией — вызов паники.

Листинг 3

func example(slice []string, str string, i int) { 0x104dfa 065488b0c2530000000 MOVQ GS:0x30, CX 0x104dfa9 483b6110 CMPQ 0x10(CX), SP 0x104dfad 762c JBE 0x104dfdb 0x104dfaf 4883ec18 SUBQ $0x18, SP 0x104dfb3 48896c2410 MOVQ BP, 0x10(SP) 0x104dfb8 488d6c2410 LEAQ 0x10(SP), BP panic("Want stack trace") 0x104dfbd 488d059ca20000 LEAQ runtime.types+41504(SB), AX 0x104dfc4 48890424 MOVQ AX, 0(SP) 0x104dfc8 488d05a1870200 LEAQ main.statictmp_0(SB), AX 0x104dfcf 4889442408 MOVQ AX, 0x8(SP) 0x104dfd4 e8c735fdff CALL runtime.gopanic(SB) 0x104dfd9 0f0b UD2 <--- Здесь СК(+0x39)

Помните: СК указывает на следующую инструкцию, а не текущую. В листинге 3 приведен хороший пример инструкций на основе amd64, которые поток для этой программы Go выполняет последовательно.

Состояния потоков

Другим важным понятием является состояние потока. Поток может находиться в одном из трех состояний: Ожидание, Готовность или Выполнение.

Это может происходить по таким причинам, как ожидание аппаратного обеспечения (диск, сеть), операционной системы (системные вызовы) или вызовов синхронизации (атомарные, мьютексы). Ожидание: это означает, что поток остановлен и ожидает чего-то для продолжения. Эти типы задержек являются основной причиной плохой производительности.

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

Выполнение: Это означает, что поток размещен на ядре и выполняет свои машинные инструкции.

Типы работ

Поток может выполнять два типа работ. Первый называется CPU-Bound, а второй — IO-Bound.

Это работа, которая постоянно делает расчеты. CPU-Bound: это работа, которая никогда не создает ситуацию, когда поток может быть переведен в состояние ожидания. Поток, вычисляющий число Pi до N-й цифры, будет привязан к ЦП.

Это работа, которая заключается в запросе доступа к ресурсу по сети или выполнении системных вызовов в операционной системе. IO-Bound: это работа, которая заставляет потоки переходить в состояние ожидания. Я бы включил события синхронизации (мьютексы, атомарные), которые заставляют поток ждать как часть этой категории. Поток, которому необходим доступ к базе данных, будет IO-Bound.

Переключение контекста

Если вы работаете в Linux, Mac или Windows, вы работаете в операционной системе с вытесняющим планировщиком.

Невытесняющие (non-preemptive) алгоритмы основаны на том, что активному потоку позволяется выполняться, пока он сам, по собственной инициативе, не отдаст управление операционной системе для того, чтобы та выбрала из очереди другой готовый к выполнению поток.

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

Это означает несколько важных вещей.

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

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

ПК происходит, когда планировщик берет поток выполнения из ядра и заменяет его потоком из состояния готовности. Процесс прекращения выполнения процессором одной задачи с сохранением всей необходимой информации и состояния, необходимых для последующего продолжения с прерванного места, и восстановления и загрузки состояния задачи, к выполнению которой переходит процессор называется переключением контекста (ПК). Поток, который был извлечен, может вернуться в состояние готовности (если он все еще имеет возможность запуска) или в состояние ожидания (если был заменен из-за типа запроса IO-Bound). Поток, выбранный из очереди выполнения, переходит в состояние «Выполнение».

Величина задержки, возникающей во время ПК, зависит от различных факторов, но вполне разумно, чтобы она занимала от ~ 1000 до ~ 1500 наносекунд. ПК считается дорогостоящей операцией. По сути, ваша программа теряет способность выполнять большое количество инструкций во время переключения контекста. Учитывая, что аппаратное обеспечение должно быть в состоянии разумно выполнять (в среднем) 12 инструкций в наносекунду на ядро, переключение контекста может стоить от ~ 12k до ~ 18k инструкций задержки.

Как только поток переходит в состояние ожидания, его место занимает другой поток в состоянии готовности. Если у вас есть программа, ориентированная на работу, связанную с IO, то переключение контекста будет преимуществом. Это один из самых важных аспектов планирования. Это позволяет ядру всегда выполнять работу. Не позволяйте ядру бездействовать, если есть работа (потоки в состоянии «Готовность»).

Поскольку у потока всегда есть работа, переключение контекста останавливает эту работу. Если ваша программа ориентирована на работу с привязкой к ЦП, переключение контекста станет кошмаром производительности. Эта ситуация резко контрастирует с тем, что происходит с нагрузкой IO-Bound.

Меньше — больше

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

Если у вас есть 5 потоков, каждый поток получает 2 мс. Например, если вы определили период вашего планировщика равным 10 мс (миллисекунд), и у вас есть 2 потока, то каждый поток получает 5 мс каждый. Предоставление каждому потоку отрезка времени в 10 мкс (микросекунд) не работает, потому что вы потратите значительное количество времени на ПК. Однако что происходит, когда у вас есть 100 потоков?

В последнем сценарии, если минимальный интервал времени составлял 2 мс, а у вас 100 потоков, период планировщика необходимо увеличить до 2000 мс или 2 сек. Что вам нужно, так это ограничить, насколько короткими могут быть временные срезы. В этом простом примере все потоки запускаются один раз в течение 20 сек, если каждый поток использует свой временной интервал. Что, если было 1000 потоков, теперь вы смотрите на период планировщика 20 сек.

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

Меньше потоков в состоянии «Готовность» означает меньше затрат на планирование и больше времени, которое каждый поток получает с течением времени. Вот почему правило «Меньше значит больше». Это означает, что со временем будет выполняться меньше вашей работы. Чем больше потоков в состоянии «Готовность», тем меньше времени получает каждый поток.

Ищем баланс

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

В этой операционной системе использование пулов потоков IOCP (IO Completion Ports) было критически важным для написания многопоточного программного обеспечения. До написания кода на Go я написал код на C ++ и C # для NT. Как инженер, вам нужно было выяснить, сколько пулов потоков вам нужно, и максимальное количество потоков для любого данного пула, чтобы максимизировать пропускную способность для числа ядер, которые у вас есть.

Другими словами, 3 потока на ядро ​​минимизировали затраты времени на переключение контекста, максимально увеличив время выполнения на ядрах. При написании веб-сервисов, взаимодействующих с базой данных, магическое число 3 потока на ядро, ​​всегда обеспечивало наилучшую пропускную способность в NT. При создании пула потоков IOCP я знал, что нужно начинать минимум с 1 потока и максимум с 3 потоками на каждое ядро, идентифицированное на хост-компьютере.

Если я использовал 4 потока на ядро, это также занимало больше времени, потому что у меня было больше задержек при ПК. Если бы я использовал 2 потока на ядро, это заняло бы больше времени, чтобы выполнить всю работу, потому что у меня был простой, когда я мог выполнять работу. Баланс 3 потоков на ядро ​​по любой причине всегда казался магическим числом в NT.

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

Кэш процессора

Доступ к данным из основной памяти имеет такую ​​высокую стоимость задержки (от ~ 100 до ~ 300 тактов), что процессоры и ядра имеют локальные кэши для хранения данных близко к аппаратным потокам, которые в них нуждаются. Доступ к данным из кеша обходится намного дешевле (от 3 до 40 тактов) в зависимости от доступа к кешу. Сегодня одним из аспектов производительности является то, насколько эффективно вы можете передавать данные в процессор, чтобы уменьшить эти задержки доступа к данным. При написании многопоточных приложений, которые изменяют состояние, необходимо учитывать механику системы кеширования.

image

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

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

image

Когда Поток пытается получить доступ на чтение или запись к грязной строке кэша, доступ к основной памяти (от ~ 100 до ~ 300 тактовых циклов) необходим для получения новой копии строки кэша. Если один поток в данном ядре вносит изменения в свою копию строки кэша, то с помощью аппаратного обеспечения все остальные копии той же строки кэша должны быть помечены как грязные.

А как насчет системы с двумя физическими процессорами по 16 ядер в каждом? Может быть, на 2-ядерном процессоре это не имеет большого значения, но как быть с 32-ядерным процессором, на котором 32 потока работают параллельно, все получают и изменяют данные в одной строке кэша? Приложение будет перебирать память, а производительность будет ужасной, и, скорее всего, вы не поймете, почему. Это будет хуже из-за дополнительной задержки для связи между процессорами.

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

Итог

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

Теги
Показать больше

Похожие статьи

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»
Закрыть