До сих пор мы писали о параллелизме так, как будто единственный способ создавать параллельные приложения - это использовать потоки. Как и многое в жизни, это не совсем верно. В частности, другой стиль параллельного программирования часто используется как в приложениях на основе графического интерфейса пользователя [O96], так и в некоторых типах интернет-серверов [PDZ99]. Этот стиль, известный как параллелизм на основе событий (event-based concurrency), стал популярным в некоторых современных системах, включая серверные фреймворки, такие как node.js [N 13], но его корни находятся в системах C/UNIX, которые мы обсудим ниже.
Проблема, которую решает параллелизм на основе событий, двоякая. Во-первых, правильное управление параллелизмом в многопоточных приложениях может быть сложной задачей; как мы уже обсуждали, могут возникнуть отсутствующие блокировки, взаимоблокировки и другие неприятные проблемы. Вторая заключается в том, что в многопоточном приложении разработчик практически не контролирует то, что запланировано на данный момент времени; скорее, программист просто создает потоки, а затем надеется, что базовая ОС планирует их разумным образом для всех доступных процессоров. Учитывая сложность создания планировщика общего назначения, который хорошо работает во всех случаях для всех рабочих нагрузок, иногда операционная система будет планировать работу не оптимальным образом. И таким образом, мы имеем ...
СУТЬ ГЛАВЫ: КАК СОЗДАВАТЬ ПАРАЛЛЕЛЬНЫЕ СЕРВЕРЫ БЕЗ ПОТОКОВ
Как мы можем создать параллельный сервер без использования потоков и, таким образом, сохранить контроль над параллелизмом, а также избежать некоторых проблем, которые, по-видимому, преследуют многопоточные приложения?
33.1 Базовая идея: Event Loop (Цикл событий)
Базовый подход, который мы будем использовать, как указано выше, называется параллелизмом на основе событий. Подход довольно прост: вы просто ждете, пока что-то произойдет (т.е. “событие”); когда это произойдет, вы проверяете, к какому типу относится это событие, и выполняете небольшой объем работы, который для этого требуется (который может включать выдачу запросов ввода-вывода или планирование других событий для обработки в будущем и т.д.). Вот и все!
Прежде чем вдаваться в подробности, давайте сначала рассмотрим, как выглядит канонический сервер, основанный на событиях. Такие приложения основаны на простой конструкции, известной как цикл событий. Псевдокод для цикла событий выглядит следующим образом:
Это действительно так просто. Основной цикл просто ожидает, пока что-то будет сделано (путем вызова getEvents() в приведенном выше коде), а затем для каждого возвращаемого события обрабатывает их по одному за раз; код, который обрабатывает каждое событие, известен как обработчик событий (event handler). Важно отметить, что когда обработчик обрабатывает событие, это единственное действие, происходящее в системе; таким образом, решение о том, какое событие обрабатывать следующим, эквивалентно планированию. Такой явный контроль над планированием является одним из фундаментальных преимуществ подхода, основанного на событиях.
Но это обсуждение оставляет нас перед более важным вопросом: как именно сервер на основе событий определяет, какие события происходят, в частности, в отношении сетевого и дискового ввода-вывода? В частности, как сервер событий может определить, поступило ли для него сообщение?
33.2 Важное API: select() или (poll())
Имея в виду этот базовый цикл событий, далее мы должны рассмотреть вопрос о том, как получать события. В большинстве систем доступен базовый API с помощью системных вызовов select() или poll().
Эти интерфейсы просто позволяют программе делать следующее: проверить, есть ли какие-либо входящие операции ввода-вывода, на которые следует обратить внимание. Например, представьте, что сетевое приложение (например, веб-сервер) желает проверить, поступили ли какие-либо сетевые пакеты, чтобы обслужить их. Эти системные вызовы позволяют вам сделать именно это.
Возьмем, к примеру, select(). Страница руководства (на Mac) описывает API следующим образом:
Фактическое описание со страницы руководства: select() проверяет наборы дескрипторов ввода-вывода, адреса которых передаются в readfds, writefds и errorfds, чтобы увидеть, готовы ли некоторые из их дескрипторов к чтению, готовы к записи или ожидают выполнения исключительного условия соответственно. В каждом наборе проверяются первые дескрипторы nfds, т.е. проверяются дескрипторы от 0 до nfds-1 в наборах дескрипторов. При возврате select() заменяет заданные наборы дескрипторов подмножествами, состоящими из тех дескрипторов, которые готовы к запрошенной операции. select() возвращает общее количество готовых дескрипторов во всех наборах.
Пара моментов о select(). Во-первых, обратите внимание, что это позволяет вам проверить, могут ли дескрипторы быть прочитаны из, а также записаны в; первое позволяет серверу определить, что новый пакет прибыл и нуждается в обработке, в то время как второе позволяет службе знать, когда можно ответить (т.е. исходящая очередь не заполнена).
Во-вторых, обратите внимание на аргумент timeout. Одним из распространенных способов использования здесь является установка таймаута равным NULL, что приводит к блокировке select() на неопределенный срок, пока какой-либо дескриптор не будет готов. Однако более надежные серверы обычно указывают какой-либо тайм-аут; один из распространенных методов - установить тайм-аут равным нулю и, таким образом, использовать вызов select() для немедленного возврата.
Системный вызов poll() очень похож. Подробности см. на странице руководства по эксплуатации или на странице Стивенса и Раго [SR05].
В любом случае, эти базовые примитивы дают нам способ построить неблокирующий цикл событий, который просто проверяет наличие входящих пакетов, считывает из сокетов сообщения на них и отвечает по мере необходимости.
33.3 Использование select()
Чтобы сделать обсуждение более конкретным, давайте рассмотрим, как использовать select(), чтобы увидеть, в каких сетевых дескрипторах отображаются входящие сообщения. На рисунке 33.1 показан простой пример.
Этот код на самом деле довольно прост для понимания. После некоторой инициализации сервер переходит в бесконечный цикл. Внутри цикла он использует макрос FD ZERO(), чтобы сначала очистить набор файловых дескрипторов, а затем использует FD SET(), чтобы включить в набор все файловые дескрипторы от mind до maxFD. Этот набор дескрипторов может представлять, например, все сетевые сокеты, на которые обращает внимание сервер. Наконец, сервер вызывает функцию select(), чтобы увидеть, для какого из подключений доступны данные. Затем, используя функцию FD_ISSET() в цикле, сервер событий может видеть, в каком из дескрипторов данные готовы, и обрабатывать входящие данные.
Конечно, реальный сервер был бы более сложным, чем этот, и требовал бы дополнительной реализации логики для отправки сообщений, выполнения дискового ввода-вывода и многих других операций. Для получения дополнительной информации см. Stevens and Rago [SR05] для получения информации об API или Pai и др. или Уэлш и др. для получения хорошего обзора общего потока работы серверов, основанных на событиях [PDZ99, WCB01].
СОВЕТ: НЕ ИСПОЛЬЗУЙТЕ БЛОКИРУЮЩИЕ ВЫЗОВЫ НА СЕРВЕРАХ, ОСНОВАННЫХ НА СОБЫТИЯХ
Серверы, основанные на событиях, обеспечивают детальный контроль над планированием задач. Однако, чтобы сохранить такой контроль, никогда нельзя выполнять вызов, блокирующий выполнение вызывающего объекта; несоблюдение этого совета по дизайну приведет к блокировке сервера на основе событий, разочарованию клиентов и серьезным вопросам относительно того, читали ли вы когда-либо эту часть книги.
33.4 Почему проще? Не нужны блокировки
С одним процессором и приложением, основанным на событиях, проблем, обнаруживаемых в параллельных программах, больше нет. В частности, поскольку одновременно обрабатывается только одно событие, нет необходимости получать или снимать блокировки; сервер, основанный на событиях, не может быть прерван другим потоком, поскольку он явно однопоточный. Таким образом, ошибки параллелизма, распространенные в многопоточных программах, не проявляются в базовом подходе, основанном на событиях.
33.5 Проблема: блокирующие системные вызовы
Пока что программирование, основанное на событиях, звучит великолепно, не так ли? Вы программируете простой цикл и обрабатываете события по мере их возникновения. Вам даже не нужно думать о блокировке! Но есть проблема: что, если событие требует, чтобы вы выполнили блокирующие системный вызов?
Например, представьте, что от клиента на сервер поступает запрос на чтение файла с диска и возврат его содержимого запрашивающему клиенту (очень похоже на простой HTTP-запрос). Чтобы обслужить такой запрос, какому-либо обработчику событий в конечном итоге придется выполнить системный вызов open() для открытия файла, за которым следует серия вызовов read() для чтения файла. Когда файл будет считан в память, сервер, скорее всего, начнет отправлять результаты клиенту.
Вызовы open() и read() могут отправлять запросы ввода-вывода в систему хранения (когда необходимых метаданных или данных еще нет в памяти), и, таким образом, обслуживание может занять много времени. С сервером, основанным на потоках, это не проблема: в то время как поток, выдающий запрос ввода-вывода, приостанавливается (ожидая завершения ввода-вывода), другие потоки могут выполняться, что позволяет серверу добиваться прогресса. Действительно, это естественное перекрытие операций ввода-вывода и других вычислений - это то, что делает потоковое программирование вполне естественным и простым.
Однако при подходе, основанном на событиях, нет других потоков для запуска: только основной цикл событий. И это подразумевает, что если обработчик событий выдает блокирующий вызов, весь сервер будет делать именно это: блокировать всё до завершения вызова. Когда цикл событий блокируется, система простаивает и, таким образом, является огромной потенциальной тратой ресурсов. Таким образом, у нас есть правило, которому необходимо следовать в системах, основанных на событиях: блокирующие вызовы не разрешены.
33.6 Решение: Asynchronous I/O (Асинхронный Ввод/Вывод)
Чтобы преодолеть это ограничение, многие современные операционные системы внедрили новые способы отправки запросов ввода-вывода в дисковую систему, обычно называемые асинхронным вводом-выводом. Эти интерфейсы позволяют приложению выдавать запрос ввода-вывода и немедленно возвращать управление вызывающей стороне до завершения ввода-вывода; дополнительные интерфейсы позволяют приложению определять, завершены ли различные операции ввода-вывода.
Например, давайте рассмотрим интерфейс, предоставляемый на Mac (другие системы имеют аналогичные API). API вращаются вокруг базовой структуры, struct aiocb или блока управления AIO (AIO control block) в общепринятой терминологии. Упрощенная версия структуры выглядит следующим образом (см. страницы руководства для получения дополнительной информации):
Чтобы выполнить асинхронное чтение файла, приложение должно сначала заполнить эту структуру соответствующей информацией: файловым дескриптором считываемого файла (aio_fildes), смещением внутри файла (aio_offset), а также длиной запроса (aio_nbytes) и, наконец, целевая ячейка памяти, в которую должны быть скопированы результаты считывания (aio_buf).
После заполнения этой структуры приложение должно выполнить асинхронный вызов для чтения файла; на Mac этот API является просто асинхронным API чтения:
int aio_read(struct aiocb *aiocbp);
Этот вызов пытается выполнить ввод-вывод; в случае успеха он просто сразу возвращается, и приложение (т.е. сервер, основанный на событиях) может продолжить свою работу.
Однако есть еще один, последний кусочек головоломки, который мы должны разгадать. Как мы можем определить, когда ввод-вывод завершен, и, таким образом, что буфер (на который указывает aio_buff) теперь содержит запрошенные данные внутри него?
Необходим еще один, последний API. На Mac это упоминается (несколько сбивающе с толку) как aio_error(). API выглядит следующим образом:
int aio_error(const struct aiocb *aiocbp);
Этот системный вызов проверяет, завершен ли запрос, на который ссылается aiocbp. Если это так, процедура возвращает success (обозначается нулем); если нет, возвращается EINPROGRESS. Таким образом, для каждого невыполненного асинхронного ввода-вывода приложение может периодически опрашивать систему с помощью вызова aio_error(), чтобы определить, был ли указанный ввод-вывод завершен.
Одна вещь, которую вы, возможно, заметили, заключается в том, что проверять, завершен ли ввод-вывод, болезненно; если программа имеет десятки или сотни операций ввода-вывода, выданных в данный момент времени, должна ли она просто продолжать проверять каждый из них повторно, или сначала немного подождать, или ... ?
Чтобы устранить эту проблему, некоторые системы предоставляют подход, основанный на прерывании (interrupt). Этот метод использует сигналы (signals) UNIX для информирования приложений о завершении асинхронного ввода-вывода, тем самым устраняя необходимость повторного запроса системы. Эта проблема с опросом и прерываниями наблюдается и в устройствах, как вы увидите (или уже видели) в главе об устройствах ввода-вывода.
В системах без асинхронного ввода-вывода подход, основанный исключительно на событиях, не может быть реализован. Однако умные исследователи разработали методы, которые довольно хорошо работают на своем месте. Например, Пай и др. [PDZ99] описывает гибридный подход, в котором события используются для обработки сетевых пакетов, а пул потоков используется для управления незавершенным вводом-выводом. Подробнее читайте в их статье.
33.7 Другая проблема: менеджер состояний (state manager)
Другая проблема подхода, основанного на событиях, заключается в том, что такой код, как правило, сложнее в написании, чем традиционный код, основанный на потоках. Причина в следующем: когда обработчик событий выдает асинхронный ввод-вывод, он должен упаковать некоторое состояние программы для использования следующим обработчиком событий, когда ввод-вывод окончательно завершится; эта дополнительная работа не требуется в программах на основе потоков, поскольку состояние, необходимое программе, находится в стекe потока. Адья и др. называют эту работу ручным управлением стеком (manual stack management), и она является основополагающей для программирования на основе событий [A+02].
Чтобы конкретизировать этот момент, давайте рассмотрим простой пример, в котором потоковому серверу необходимо выполнить чтение из файлового дескриптора (fd) и, после завершения, записать данные, которые он прочитал из файла, в дескриптор сетевого сокета (sd). Код (игнорирующий проверку ошибок) выглядит следующим образом:
int rc = read(fd, buffer, size);
rc = write(sd, buffer, size);
Как вы можете видеть, в многопоточной программе выполнение такого рода работы является тривиальным; когда read() наконец возвращается, код сразу же знает, в какой сокет записывать, потому что эта информация находится в стеке потока (в переменных sd).
В системе, основанной на событиях, жизнь не так проста. Чтобы выполнить ту же задачу, мы бы сначала выполнили чтение асинхронно, используя вызовы AIO, описанные выше. Допустим, затем мы периодически проверяем завершение чтения с помощью вызова aio_error(); когда этот вызов сообщает нам, что чтение завершено, как сервер на основе событий узнает, что делать?
ЗАМЕТКА: СИГНАЛЫ UNIX
Огромная и увлекательная инфраструктура, известная как signals, присутствует во всех современных вариантах UNIX. В самом простом виде сигналы обеспечивают способ связи с процессом. В частности, сигнал может быть доставлен в приложение; это останавливает приложение от того, что оно делает для запуска обработчика сигнала, т.е. некоторого кода в приложении для обработки этого сигнала. По завершении процесс просто возобновляет свое предыдущее поведение.
Каждый сигнал имеет название, например HUP (отбой), INT (прерывание), SEGV (нарушение сегментации) и т.д.; подробности см. на странице руководства. Интересно, что иногда сигнализацию подает само ядро. Например, когда ваша программа сталкивается с нарушением сегментации, операционная система отправляет ей SIGSEGV (добавление SIG к именам сигналов является обычным явлением); если ваша программа настроена на перехват этого сигнала, вы действительно можете запустить некоторый код в ответ на это ошибочное поведение программы (что полезно для отладки). Когда сигнал отправляется процессу, не настроенному для обработки сигнала, применяется поведение по умолчанию; для SEGV процесс завершается. Вот простая программа, которая переходит в бесконечный цикл, но сначала настроила обработчик сигнала для перехвата SIGHUP:
void handle(int arg) {
printf("stop wakin’ me up...\n");
}
int main(int argc, char *argv[]) {
signal(SIGHUP, handle); while (1) ; // doin’ nothin’ except catchin’ some sigs
return 0;
}
Вы можете посылать ему сигналы с помощью инструмента командной строки kill (да, это странное и агрессивное название). Это приведет к прерыванию основного цикла while в программе и запуску кода обработчика handle():
prompt> ./main & [3] 36705
prompt> kill -HUP 36705 stop wakin’ me up...
prompt> kill -HUP 36705 stop wakin’ me up...
О сигналах можно узнать гораздо больше, настолько много, что одной главы, не говоря уже об одной странице, будет недостаточно. Как всегда, есть один отличный источник: Стивенс и Раго [SR 05]. Читайте дальше, если вам интересно.
Решение, описанное Адьей со товарищи. [A+02], заключается в использовании старой конструкции языка программирования, известной как продолжение (continuation) [FHK84]. Хотя это звучит сложно, идея довольно проста: в принципе, запишите необходимую информацию для завершения обработки этого события в некоторой структуре данных; когда событие произойдет (т.е. когда дисковый ввод-вывод завершится), найдите необходимую информацию и обработайте событие.
В данном конкретном случае решением было бы записать дескриптор сокета (sd) в какую-либо структуру данных (например, хэш-таблицу), индексируемую файловым дескриптором (fd). Когда дисковый ввод-вывод завершится, обработчик событий будет использовать дескриптор файла для поиска продолжения, которое вернет вызывающему значение дескриптора сокета. На этом этапе (наконец-то) сервер может выполнить последнюю часть работы по записи данных в сокет.
33.8 Что остаётся сложным при работе с событиями?
Есть несколько других трудностей, связанных с подходом, основанным на событиях, о которых мы должны упомянуть. Например, когда системы перешли с одного процессора на несколько, некоторая простота подхода, основанного на событиях, исчезла. В частности, чтобы использовать более одного центрального процессора, сервер событий должен запускать несколько обработчиков событий параллельно; при этом возникают обычные проблемы с синхронизацией (например, критические разделы), и необходимо использовать обычные решения (например, блокировки). Таким образом, в современных многоядерных системах простая обработка событий без блокировок больше невозможна.
Другая проблема подхода, основанного на событиях, заключается в том, что он плохо интегрируется с определенными видами системной деятельности, такими как подкачка страниц (paging). Например, если страница обработчика событий выходит из строя, она блокируется, и, таким образом, сервер не будет выполнять работу до тех пор, пока ошибка страницы не завершится. Несмотря на то, что сервер был сконструирован таким образом, чтобы избежать явной блокировки, этого типа неявной блокировки из-за сбоев страницы трудно избежать и, следовательно, может привести к большим проблемам с производительностью, когда он распространен.
Третья проблема заключается в том, что кодом, основанным на событиях, может быть трудно управлять с течением времени, поскольку точная семантика различных подпрограмм меняется [A+02]. Например, если процедура меняется с неблокирующей на блокирующую, обработчик событий, который вызывает эту процедуру, также должен измениться, чтобы приспособиться к ее новой природе, разделив себя на две части. Поскольку блокировка настолько губительна для серверов, основанных на событиях, программист всегда должен быть в курсе таких изменений в семантике API, используемых каждым событием.
Наконец, хотя асинхронный дисковый ввод-вывод теперь возможен на большинстве платформ, потребовалось много времени, чтобы добиться этого [PDZ99], и он никогда полностью не интегрируется с асинхронным сетевым вводом-выводом таким простым и единообразным способом, как вы могли бы подумать. Например, хотя хотелось бы просто использовать интерфейс select() для управления всеми текущими операциями ввода-вывода, обычно требуется некоторая комбинация select() для работы в сети и вызовов AIO для дискового ввода-вывода.
33.9 Выводы
Мы представили краткое введение в другой стиль параллелизма, основанный на событиях. Серверы, основанные на событиях, предоставляют управление планированием самому приложению, но делают это с определенными затратами из-за сложности и сложности интеграции с другими аспектами современных систем (например, подкачки). Из-за этих проблем ни один единый подход не стал лучшим; таким образом, и потоки, и события, вероятно, будут сохраняться как два разных подхода к одной и той же проблеме параллелизма в течение многих последующих лет. Прочтите несколько исследовательских работ (например, [A +02, PDZ99, vB +03, CB01]) или, еще лучше, напишите какой-нибудь событийный код, чтобы узнать больше.
Ссылки
[A+02] “Cooperative Task Management Without Manual Stack Management” by Atul Adya, Jon Howell, Marvin Theimer, William J. Bolosky, John R. Douceur. USENIX ATC ’02, Monterey, CA, June 2002. This gem of a paper is the first to clearly articulate some of the difficulties of event-based concurrency, and suggests some simple solutions, as well explores the even crazier idea of combining the two types of concurrency management into a single application!
[FHK84] “Programming With Continuations” by Daniel P. Friedman, Christopher T. Haynes, Eugene E. Kohlbecker. In Program Transformation and Programming Environments, Springer Verlag, 1984. The classic reference to this old idea from the world of programming languages. Now increasingly popular in some modern languages
[N13] “Node.js Documentation” by the folks who built node.js. Available: nodejs.org/api. One of the many cool new frameworks that help you readily build web services and applications. Every modern systems hacker should be proficient in frameworks such as this one (and likely, more than one). Spend the time and do some development in one of these worlds and become an expert.
[O96] “Why Threads Are A Bad Idea (for most purposes)” by John Ousterhout. Invited Talk at USENIX ’96, San Diego, CA, January 1996. A great talk about how threads aren’t a great match for GUI-based applications (but the ideas are more general). Ousterhout formed many of these opinions while he was developing Tcl/Tk, a cool scripting language and toolkit that made it 100x easier to develop GUI-based applications than the state of the art at the time. While the Tk GUI toolkit lives on (in Python for example), Tcl seems to be slowly dying (unfortunately).
[PDZ99] “Flash: An Efficient and Portable Web Server” by Vivek S. Pai, Peter Druschel, Willy Zwaenepoel. USENIX ’99, Monterey, CA, June 1999. A pioneering paper on how to structure web servers in the then-burgeoning Internet era. Read it to understand the basics as well as to see the authors’ ideas on how to build hybrids when support for asynchronous I/O is lacking.
[SR05] “Advanced Programming in the UNIX Environment” by W. Richard Stevens and Stephen A. Rago. Addison-Wesley, 2005. Once again, we refer to the classic must-have-on-your-bookshelf book of UNIX systems programming. If there is some detail you need to know, it is in here.
[vB+03] “Capriccio: Scalable Threads for Internet Services” by Rob von Behren, Jeremy Condit, Feng Zhou, George C. Necula, Eric Brewer. SOSP ’03, Lake George, New York, October 2003. A paper about how to make threads work at extreme scale; a counter to all the event-based work ongoing at the time.
[WCB01] “SEDA: An Architecture for Well-Conditioned, Scalable Internet Services” by Matt Welsh, David Culler, and Eric Brewer. SOSP ’01, Banff, Canada, October 2001. A nice twist on event-based serving that combines threads, queues, and event-based handling into one streamlined whole. Some of these ideas have found their way into the infrastructures of companies such as Google, Amazon, and elsewhere.
