На современной серверной машине low-latency процесс работает на многозадачной операционной системе. Это может быть Solaris, чаще Linux, FreeBSD или Windows Server. Помимо нашего процесса в ОС работают еще и другие процессы, которым ОС тоже должна выделять машинное время. Собственно потому ОС и называется многозадачной.
В данной статье пойдет речь о том, как многозадачная операционная система и особенности ее архитектуры влияют на исполнение нашего процесса, и как мы можем побороть это влияние с целью достижения low-latency.
Переключение контекста (context switch)
Конкретный процесс работает определенное время до тех пор пока:
- не произойдет вызов операции ввода-вывода (i/o operation). Тогда процесс останавливается и ждет окончания — поступления данных. Это может быть ожидание очередной порции байтов из сети или загрузка с диска каких-то данных или страницы памяти (page fault), или окончания записи данных в систему вывода: это может быть запись данных в сеть или запись их на диск (page swap);
- не истечет выделенное ядром ОС время (time slice), после чего ядро приостанавливает исполнение процесса. Такое переключение происходит примерно каждые 20~50 миллисекунд.
В каждый конкретный момент времени процессор способен выполнять код только одного процесса (о многоядерных процессорах мы поговорим чуть позднее). За переключение процессов/потоков в современной многозадачной ОС отвечает специальный модуль ядра, который называется «планировщик» (scheduler).
Следуя определенным правилам он формирует очередь из ожидающих процессов/потоков и при окончании time slice одного процесса выбирает следующий процесс из очереди, выделяет ему определенный time slice и запускает его на исполнение. Для переключения процессов, надо:
- остановить процесс
- сохранить где-то его текущее состояние
- загрузить состояние следующего процесса
- начать исполнение следующего процесса с той точки, где он был недавно остановлен
Состояние процесса в конкретный момент времени называется «контекстом» (context). Это состояние описывается значениями регистров и счетчиков процессора в данный момент времени. Если эти все значения сохранить, а потом позже их загрузить, то процесс даже не поймет и не заметит, что его останавливали на какое-то время, он продолжит работать так, словно никакой остановки и не было. Этот процесс называется «переключением контекста» (context switch).
Переключаясь между процессами через определенные очень короткие промежутки времени, сохраняя и восстанавливая контекст каждого процесса, операционная система создает иллюзию у пользователя, что несколько процессов работают параллельно и одновременно, хотя на самом деле в каждый конкретный момент времени работает только один процесс. Так собственно и работает многозадачность в многозадачной операционной системе на однопроцессорной машине.
В Windows и Solaris потоки поддерживаются по-другому, поэтому речь о них идти не будет. В Linux, если наше приложение — многопоточное, каждый поток для операционной системы является отдельным особым процессом. Переключение между потоками приложения для Linux выглядит точно также, как переключение между обычными процессами с одной существенной разницей. Context switch между потоками одного приложения выполняется быстрее, чем context switch между двумя независимыми процессами. Это связано с тем, что все потоки одного приложения имеют доступ ко всей памяти данного процесса, следовательно при переключении контекста не надо менять контекст памяти, а достаточно только поменять контекст стека. На это тратится намного меньше времени. Так что, если в очереди на исполнение процессы в планировщике стоят так:
proc1:thread1
proc1:thread2
proc2:thread7
proc1:thread6
то переключение контекста proc1:thread1 -> proc1:thread2 осуществится быстрее, чем переключение proc2:thread7 -> proc1:thread6.
Переключение контекста на многоядерных и многопроцессорных машинах
Ушло в прошлое время одноядерных процессоров. Сейчас все процессоры выпускаются в многоядерном варианте. По сути в одном корпусе процессора вы получается сразу несколько CPU, которые могут выполнять код одновременно независимо друг от друга. Если одноядерному процессору надо было быстро переключаться между процессорами для создания иллюзии их параллельного одновременного исполнения, то на многоядерном процессоре в каждый конкретный момент времени может исполняться несколько процессов одновременно, параллельно, по-настоящему без всяких иллюзий.
Машины серверного класса имеют два и более процессоров для обеспечения надежности. Причем каждый процессор еще и является многоядерным. Например, 2х-процессорная машина с 2-мя 16 ядерными процессорами способна одновременно, параллельно выполнять 32 процесса/потока. А если на процессорах включена функция гиперпоточности — то 64 процесса/потока! 20 лет назад для достижения такого результата нам бы понадобилась машина с 64 процессорами класса Pentium. И 20 лет назад такая машина считалась бы суперкомпьютером, стоила бы миллионы американских долларов и доступна была бы только оборонке или богатому научному учреждению.
Планировщик
Пришествие многоядерных процессоров и многопроцессоных машин потребовало внесения изменений и в алгоритмы планировщика операционной системы. Теперь планировщику нужно планировать исполнение процессов так, чтобы одни ядра процессора не простаивали, в то время как другие — работают со 100% загрузкой.
С самой первой версии Linux 1991 года вплоть до версии 2.4 планировщик был прост, понятен и тривиален, но плохо масштабировался при большом количестве процессов и при работе на многопроцессорных машинах. В версии ядра 2.5 была предпринята попытка создания нового планировщика под названием O(1), который работал намного лучше, повторял в чем-то работу планировщиков других UNIX-систем, но все равно имел свои недостатки. В версии ядра 2.6 были предприняты попытки написать еще один планировщик, который бы работал лучше, чем O(1). Этот эксперимент завершился в версии ядра 2.6.23, когда был представлен планировщик Completely Fair Scheduler (или сокращенно CFS).
Перенос потока с одного ядра на другое
Планировщик может перебрасывать процесс/поток перед его новым запуском с одного ядра на другой, или даже с одного процессора на другой, если в машине несколько многоядерных процессоров.
Например, дана двухпроцессорная машина с двумя 16 ядерными процессорами. Нумерация ядер в Linux будет выглядеть так CPU0, … CPU7 — ядра первого процессора, CPU8 … CPU15 — ядра второго процессора. Скажем, наш главный процесс работает изначально на CPU0 (т.е. первом ядре первого процессора). Это процесс порождает 6 потоков. Обычно операционная система пытается каждый поток запустить на отдельном ядре, т.е. все 7 потоков (родительский и 6 порожденных) займут ядра с CPU0 до CPU6. Но потом планировщик будет останавливать эти потоки, чтобы дать на каждом ядре исполнится коду других потоков. Если мы посмотрим на наше приложение скажем через 15 минут, мы заметим, что наши потоки «разбрелись» по всем доступным ядрам процессора: родительский оказался на CPU5, а какой-то из порожденных потоков — на CPU15 (т.е. на последнем ядре второго процессора).
Как это скажется на производительности?
Ивалидация кэша
Каждое ядро процессора оснащено кэшем первого (L1) и второго уровней (L2), а сам процессор имеет общий кэш третьего уровня (L3), которым пользуются все ядра данного процессора. В кэше хранится копия данных, недавно извлеченная из памяти. Если процесс был остановлен планировщиком и потом запущен на другом ядре, кэши этого ядра не будут иметь этой копии данных, так как на этом ядре они еще не извлекались. А данные в кэше, оставшиеся от предыдущего потока, ему не нужны.
Первым делом поток обратится к кэшам за данными, не найдет их так и произойдет событие, которое называется cache miss процессов остановится, полезет в кэш L1, потом в кэш L2, потом в кэш L3, потом в память, извлечет из нее данные, поместит их в кэш, и только тогда продолжит исполнение процесса. На это требуется определенное время. Это все приведет к небольшой задержке. На графиках производительности это все будет выглядеть как jitter.
Если потом поток будет снова перенесен планировщиком на новое ядро, вся история повторится, это снова приведет к задержке. Так как переключение процессов на современных компьютерах происходит каждые 20-50 миллисекунд, мы будем каждые 20-50 миллисекунд получать задержку только по той причине, что планировщик запускает наш процесс всякий раз на каком-то другом ядре. Хорошо, если данные, с которыми предстоит процессу работать окажутся в кэше хотя бы третьего уровня (L3), тогда задержка будет несколько десятков наносекнуд, а если в памяти? А если в той странице памяти, которая отсутствует в физической памяти и должна быть прочитана с диска (page fault)?
Система предсказания переходов
Подсистема предсказания переходов (branch prediction) все еще может хранить информацию о предыдущих исполнениях этого потока. Значит, когда этот же поток снова начинает исполняться на этом же ядре, процессору не придется собирать эту информацию с нуля.
Affinity и Isolation
В полном идеале хорошо было бы, чтобы каждый конкретный поток не делил ядро с другим потоком, т.е. количество активных потоков было бы равно количеству выделенных для процесса ядер. Как минимум было бы хорошо, чтобы каждый поток работал на своем ядре и не переносился планировщиком на другое ядро. Для решения этой проблемы есть несколько инструментов.
Affinity
Первый инструмент называется affinity. Дословно — «приклеивание» процесса определенному ядру. Об этом приеме можно найти достаточно подробное описание в Википедии. Благодаря affinity планировщик точно знает, что данный процесс после «пробуждения» должен работать только на этом ядре или ядрах, и ни на каких других.
Например, вот как функция affinity выглядит в Windows 10. Обратите внимание, что так мы управляем affinity процесса, но не потоков этого процесса:
меню, в котором можно выбрать пункт Set affinity
На Linux привязки процесса к процессору можно добиться с помощью утилиты taskset. Более тонкая привязка какого-то потока к определенному ядру уже осуществляется:
- программно через JNI/C++: например, как это сделано в OpenHFT/ThreadAffinity
- с помощью утилит isocpu и cgroups.
Первый вариант предпочтительнее, так как при перезапуске процесса, не требуется выстраивать affinity вручную. С помощью конфигурационного файла можно определить affinity каждого потока и при запуске эти настройки автоматически «разбросают» потоки по ядрам.
Isolation
Второй инструмент — изоляция ядер (isolation). Мало приклеить процесс к определенному ядру, надо еще сообщить планировщику, чтобы он не запускал на этом ядре другие процессы, которые могут «загрязнить» кэши процесссора своими данными. На Linux изоляция процессора под определенную задачу осуществляется с помощью утилиты isolcpus.
На двухпроцессорной машине можно отвести все ядра одного процессора под low-latency приложение, а все сопутствующие сервисы и приложения операционной системы — запускать на втором процессоре. Так с помощью affinity и изоляции в полном распоряжении вашего low-latency приложения окажется 16 ядер одного процессора. Если в вашем приложении 16 потоков, то каждый поток беспрерывно будет исполняться на своем ядре и не будет приводить к переключению контекстов.
Paging и Page Fault
Процесс в память загружается не целиком, в памяти процесса в конкретный момент находится только несколько сегментов кода по 4 килобайта каждый. Если ваш код в процессе исполнения делает переход на часть кода, которого нет в этих страницах, происходит так называемый «page fault», исполнение программы приостанавливается, ядро дозагружает нужную страницу с диска и потом исполнение продолжается дальше.
Swapping
Если все работающие процессы не помещаются в памяти, операционная система запускает механизм свопа: останавливает неактивные процессы и выгружает из целиком на диск. В случае если процесс снова надо вернуть в память и выполнить его, происходит обратная операция: весь процесс загружается в память и продолжает свое исполнение как если бы он там все время находился. Выгрузка процесса на диск и загрузка его с диска в память — очень дорогие операции. Всякий, кто когда-либо работал, например с Windows, на маленьком объеме памяти помнит, как при переключении между задачами система буквально замирала, а жесткий диск неистово дёргался.
Paging и Swapping схожи друг с другом, но это разные функции.
Как это применить к производительности
Из вышесказанного можно сделать следующие выводы:
- уменьшить количество работающих процессов, отключить все ненужные процессы и понизить приоритет тех, которые отключить нельзя. В идеале low-latency приложение должно работать на машине одно, и не конкурировать с другими low-latency процессами за ресурсы.
- не допускать никакого свопа процессов, особенно нашего low-latency процесса — у операционной системы всегда должно быть достаточно свободной памяти для работы в течение всего операционного дня
- использовать оптимизированный планировщик операционной системы, который более эффективно планирует исполнение процессов, так как поставляемый по умолчанию — слишком общ. Разные планировщики по-разному определяют приоритеты процессов и по разному определяют, какой процесс должен исполняться следующим
- увеличить размеры страниц памяти, чтобы процесс загружал в память большие куски себя и не лез на диск за недостающими сегментами
- выделить для low-latency процесса определенное количество ядер и запретить другим процессам использовать эти ядра (process isolation)
- не позволять потокам процесса переходить с одного ядра на другой (affinity)
- писать на диск или в сеть только в самом крайнем случае, лучше всего делегировать это одному потоку, который исполняется на отдельном ядре и не мешает другим критическим потокам исполняться
Algo & DMA: технологии биржевой торговли 