В предыдущей статье блога мы обсудили краткую историю системного вызова select(2). В ней делается вывод, что для эмуляции консолей, игр и нетривиальных TCP/IP-приложений было необходимо определенное мультиплексирование ввода-вывода.
Разработчики BSD (Berkeley Software Distribution) выбрали модель мультиплексирования select, и за ними последовали другие Unix-подобные системы. Но является ли select единственной моделью мультиплексирования?
Хорошее объяснение можно найти в старой редакции книги "The Design and Implementation of the FreeBSD Operating System. Дизайн и реализация операционной системы FreeBSD". В Google books она есть, вот сниппет:
Существуют четыре альтернативных варианта, которые позволяют избежать проблемы блокировки:
Перевести все дескрипторы в неблокирующий режим. [...]
Сделайте доступными все дескрипторы, представляющие интерес, для [отправки] сигнала, когда может быть выполнен ввод/вывод. [...]
Пусть система предоставит метод запроса о том, какие дескрипторы способны выполнить ввод-вывод [...].
Пусть процесс зарегистрирует в [операционной] системе все события, включая ввод-вывод для дескрипторов, которые он хочет отслеживать.
Вариант 1) является наивным. Идея в том, чтобы осуществить функцию busy-polling на неблокирующих дескрипторах. Для этого придется задействовать 100% ресурсов процессора. Такой подход не очень практичен.
Вариант 2) — это старая добрая модель асинхронного ввода/вывода SIGIO. В Linux она реализуется с помощью fcntl(F_SETSIG). С настроенным fcntl сигнал будет уведомлять ваш процесс об изменении возможности чтения/записи в дескрипторе. К сожалению, модель F_SETSIG в ее текущей реализации почти полностью бесполезна. (С реализацией F_SETSIG связано слишком много проблем, не стоит и начинать. Скажем лишь, что когда вы перехватываете сигнал SIGIO, то вам не предоставляется достоверная информация, показывающая дескриптор файла, на котором произошло событие.)
Вариант 3) — это модель, которая реализуется с помощью select(). Она проста, хорошо определена и легка для понимания. Используется системными вызовами poll и epoll.
Вариант 4) — самый интересный. Идея заключается в том, чтобы передать некоторое состояние ядру и сообщить ему, что именно мы хотим сделать с файловым дескриптором. Эту модель используют kqueue и Windows IOCP.
Каждая из этих четырех моделей мультиплексирования имеет свои недостатки, но я хотел бы сосредоточиться именно на третьем варианте: select.
Тяжеловес
Select() был впервые реализован 33 года назад, и для такого возраста он сохранился на удивление хорошо. К сожалению, он неисправен изначально.
Сломан не только системный вызов select(). Все технологии, наследующие его семантику, тоже сломаны! Это включает select, poll и, в меньшей степени, epoll.
Как правило, аргумент против select заключается в том, что API предписывает выполнять линейный обход дескрипторов файлов. Это так, но, это не самая большая проблема. Семантика select не позволяет ядру выполнять какие-либо оптимизации. Создание быстрой реализации select на стороне ядра невозможно.
Каждый раз, когда выполняется select(), ядро должно просмотреть переданные файловые дескрипторы, проверить их состояние и зарегистрировать обратные вызовы. Затем, когда происходит событие на любом из файловых дескрипторов, ядро должно снова осуществить итерацию, чтобы отменить регистрацию обратных вызовов. По сути, со стороны ядра вход и выход из select() — это тяжелая операция, требующая обращения ко многим указателям, вызывающая трэшинг кэша процессора, и обойти ее невозможно.
Epoll() — это решение Linux. С ее помощью разработчик может избежать постоянной регистрации и отмены регистрации файловых дескрипторов. Это делается путем явного управления регистрациями с помощью системного вызова epoll_ctl.
Но epoll не решает всех проблем.
Проблема «громоподобного стада»
Представьте себе дескриптор сокета, совместно используемый несколькими процессами операционной системы. Когда происходит какое-то событие, все процессы должны быть разбужены. Может показаться, что это надуманная проблема — зачем вам разделять дескриптор сокета? — но на практике это действительно происходит.
Допустим, вы запускаете HTTP-сервер, обслуживающий большое количество кратковременных соединений. Вам необходимо accept() (принять) как можно больше соединений в секунду. Выполнение accept() только в одном процессе, несомненно, будет перегружать процессор. Как это исправить?
Наивный ответ: давайте обеспечим общий доступ к дескриптору файла и позволим нескольким процессам вызывать accept() одновременно! К сожалению, это приведет к снижению производительности.
Для иллюстрации проблемы я написал два фрагмента кода.
Во-первых, это программа server.c. Она привязывается к TCP-порту 1025 и перед блокировкой на select несколько раз создает форки. Псевдокод:
sd = socket.socket()
sd.bind('127.0.0.1:1025')
sd.listen()
for i in range(N):
if os.fork() == 0:
break
select([sd])Для запуска 1024 форков, которые висят в select на одном связанном сокете:
$ ./server 1024
forks = 1024, dupes per fork = 1, total = 1024
[+] startedВторая программа client.c тривиальна. Она подключается к порту TCP, замеряя время. Чтобы лучше проиллюстрировать ситуацию, она выполняет неблокирующий вызов connect(2). Теоретически это всегда происходит молниеносно быстро.
Однако есть одна оговорка. Поскольку соединение происходит через обратный цикл (loopback) с локальным хостом, пакеты будут обрабатываться линейно, во время обработки ядром системного вызова connect.
На практике измерение длительности неблокирующего connect показывает время диспетчеризации ядра. Мы измерим, сколько времени потребуется ядру, чтобы:
создать новое соединение через loopback,
найти соответствующий дескриптор прослушивающего сокета на принимающей стороне,
поместить новое соединение в очередь на прием
и оповестить процессы, ожидающие этот прослушивающий сокет.
Стоимость последнего шага пропорциональна количеству процессов, ожидающих этот сокет. Вот график, показывающий, что длительность системного вызова connect растет линейно с числом процессов, ожидающих select на прослушивающем сокете:
Вызов неблокирующего connect() к прослушивающему сокету, который совместно используется 16k процессами, занимает 35 миллисекунд на моей машине.
Эти результаты ожидаемы. Ядру нужно выполнять линейно больше работы для каждого процесса, который необходимо разбудить, для каждого из файловых дескрипторов, которые процесс блокирует в select(). Это также верно для epoll().
Экстремальный эксперимент
Давайте доведем этот эксперимент до крайности. Посмотрим, что происходит, когда у нас в цикле select ожидает не один прослушивающий сокет, а тысяча. Чтобы усложнить работу ядра, мы тысячу раз скопируем связанный сокет TCP-порта 1025 с помощью dup(). Псевдокод:
sd = socket.socket()
sd.bind('127.0.0.1:1025')
sd.listen()
list_of_duplicated_sd = [dup(sd) for i in xrange(1019)]
for i in range(N):
if os.fork() == 0:
break
select([sd] + list_of_duplicated_sd)Это реализовано также в файле server.c:
marek:~$ ./server 1024 1019
forks = 1024, dupes per fork = 1019, total = 1043456
[+] startedНа графике будет показана линейная стоимость, но с гораздо большим постоянным коэффициентом:
График подтверждает очень высокую стоимость такой настройки. При 16k запущенных процессах, каждый из которых с прослушивающим сокетом дублирован 1019 раз (итого 16М файловых дескрипторов) ядру требуется целых 1,5 секунды, для выполнения локального неблокирующего connect().
Вот как все выглядит в консоли:
marek:~$ time nc localhost 1025 -q0
real 0m1.523s
marek:~$ strace -T nc localhost 1025 -q0
...
connect(3, {sa_family=AF_INET, sin_port=htons(1025), sin_addr=inet_addr("127.0.0.1")}, 16) = -1 EINPROGRESS (Operation now in progress) <1.390385>
...Такая настройка вызывает перегрузку машины. Наше единичное событие быстро переводит тысячи процессов Linux из "спящего" в состояние "готового к работе", в результате чего получаются интересные средние показатели нагрузки:
marek:~$ uptime
load average: 1388.77, 1028.89, 523.62Epoll exclusive на помощь
Это классическая проблема "громогласного стада". Она решается с помощью нового флага EPOLLEXCLUSIVE epoll_ctl. Он был добавлен совсем недавно в ядро 4.5. На странице руководства написано:
EPOLLEXCLUSIVE(начиная с Linux 4.5) устанавливает эксклюзивный режим пробуждения для файлового дескриптораepoll, присоединяемого к дескриптору таргет-файла, fd. Когда происходит пробуждение и несколько файловых дескрипторов epoll присоединяются к одному и тому же таргет-файлу с помощьюEPOLLEXCLUSIVE, один или несколько дескрипторов файловepollполучают событие с помощьюepoll_wait(2)
Вот соответствующий патч ядра:
Если я правильно понял код, он предназначен для улучшения среднего случая. Патч принципиально не решает проблему того, что диспетчеризация ядра требует затрат O(N) в зависимости от количества процессов/дескрипторов.
Подведение итогов
Я объяснил две проблемы с моделью мультиплексирования select().
Она тяжеловесна. Требует постоянной регистрации и отмены процессов из файловых дескрипторов, потенциально тысяч дескрипторов, тысячи раз в секунду.
Другой сложностью является масштабируемость совместного использования сокетов процессами. В традиционной модели ядро будит все процессы, висящие на сокете, даже если требуется передать только одно событие. Это приводит к проблеме “громогласного стада” и множеству бесполезных пробуждений процессов.
Linux решает первую проблему с помощью системного вызова epoll, а вторую — с помощью "пластыря" EPOLLEXCLUSIVE.
Я думаю, что реальным выходом из ситуации является фундаментальное переосмысление мультиплексирования сокетов. Вместо того, чтобы накладывать "пластыри" на "Вариант 3)" из книги Кирка МакКьюсика (Kirk McKusick), мы должны сосредоточиться на "Варианте 4)" — интерфейсы kqueue и IOCP.
Но это тема для другой статьи.
Совсем скоро состоится открытое занятие «Паттерн Entity-Component-System в играх на C». На этом уроке мы познакомимся с часто применяемым в игровых приложениях архитектурным шаблоном Entity/Component/System и рассмотрим его реализацию на языке C на примере опенсорсной библиотеки flecs. Также мы изучим код несложной игры, использующей flecs на практике. Регистрируйтесь по ссылке.
