ПРОГРАММИРОВАНИЕ, 2011, No 4, с. 73-79
- ПАРАЛЛЕЛЬНОЕ ПРОГРАММИРОВАНИЕ -
УДК 681.3.06
ОПТИМИЗАЦИЯ БИБЛИОТЕКИ НИТЕЙ NPTL В СОСТАВЕ ОС LINUX ДЛЯ СИСТЕМ ЖЕСТКОГО РЕАЛЬНОГО ВРЕМЕНИ
© 2011 г. А.В. Федоров ЗАО „МЦСТ"
105066 Москва, ул. Нижняя Красносельская, д.35, стр.50, E-mail: alexvf@bk.ru Поступила в редакцию 20.01.2011
Библиотека NPTL полностью поддерживает нити POSIX - один из самых популярных интерфейсов для создания многопоточных приложений. Она постепенно перерабатывается с учетом требований систем реального времени, но на настоящее время подходит только для систем мягкого реального времени. В статье описываются причины, по которым библиотека не соответствует требованиям жесткого реального времени, и делается попытка их устранить.
1. ВВЕДЕНИЕ
В настоящее время отделением операционных систем ЗАО „МЦСТ" выполняется ряд проектов, ставящих целью адаптацию операционной системы Linux для использования в вычислительных комплексах (ВК) эльбрусовской серии, работающих в режиме жесткого реального времени. В этом контексте важное значение имеет адаптированная к реальному времени реализация нитей (threads) в пользовательском интерфейсе POSIX (Portable Operating System Interface for Unix). Все примитивы этого интерфейса можно разделить на две группы: первая отвечает за создание и завершение нитей, вторая - за их синхронное исполнение. В статье рассматриваться будет только вторая группа: в системах жесткого реального времени она имеет куда большее значение, потому что всю инициализацию возможно провести при старте системы, а вот от синхронизации нитей при параллельных вычислениях никуда не деться.
В процессе работы автором была проанализирована библиотека NPTL (Native Posix Thread Library) на предмет ее пригодности для систем жесткого реального времени. Этот анализ представляет наибольший интерес для читателя, он составляет основное содержание статьи. В начале дается обзор системного
вызова sys_futex, затем рассказывается о деталях реализации объектов синхронизации, и в конце приводится измерение эффективности проведенной оптимизации.
2. ОСОБЕННОСТИ РЕАЛИЗАЦИИ
ОБЪЕКТОВ СИНХРОНИЗАЦИИ В NPTL
Библиотека NPTL разработана специально для Linux, что дает возможность вносить в интерфейс ядра изменения, ориентированные на ее поддержку. Таким образом, в существующий только в Linux системный вызов sys_clone были внесены изменения, необходимые для создания эффективного механизма создания и завершения нитей, а для эффективной реализации любых объектов синхронизации (например, семафоров или условных переменных) был разработан системный вызов sys_futex, поддерживающий одноименный объект [1].
Конечно, самым простым решением было бы реализовать эти объекты полностью в адресном пространстве ядра и сделать системный вызов, который просто перенаправлял бы запросы приложения в ядро ОС. Более того, тогда можно было бы использовать уже имеющиеся в ядре реализации блокировок и семафоров, -достаточно просто сопоставить каждому пользовательскому объекту „истинный" объект
в ядре. Недостаток такого решения в том, что каждая операция будет использовать системный вызов, а это - дорогое удовольствие (потеря нескольких сотен тактов и стирание содержимого кэша процессора).
Для данной проблемы разработчиками NPTL было найдено простое решение. Роль любого объекта синхронизации - задержать исполнение одной нити до наступления какого-либо события, однако, если в какой-то момент приостанавливать исполнение нет необходимости, то нет ее и в системном вызове. На практике такая оптимизация реализуется хранением состояния объекта в переменной, находящейся в пользовательском пространстве и являющейся его частью, тогда состояние можно изменять без системных вызовов.
Такая переменная и называется фьютексом. Приложение проверяет состояние объекта, считав значение фьютекса, и, если не нужно блокироваться (например, когда закрывается открытый семафор) или будить ожидающие нити (когда открывается закрытый один раз семафор), просто записывает во фьютекс новое состояние. Чтобы не возникали состояния гонки, чтение и запись делаются одной атомарной инструкцией. Системный же вызов sys_futex вызывается либо для пробуждения ждущей нити (тогда он удаляет нить из очереди в ядре и помечает ее как готовую к исполнению), либо когда нужно блокироваться (тогда он добавляет нить в очередь, причем прямо перед добавлением значение фьютекса проверяется еще раз на тот случай, если оно успело измениться, и блокироваться уже не нужно). На его основе в NPTL реализуются блокировки и семафоры, а на их основе - все остальные объекты.
Именно из-за этой оптимизации в расшифровке слова futex (Fast Userspace MUTex) есть слово Fast.
3. ОБ УНИВЕРСАЛЬНОСТИ ИСПОЛЬЗОВАНИЯ ФЬЮТЕКСОВ
В системах жесткого реального должно быть гарантировано завершение операций за определенное время. Помимо этого, следует добиться улучшения следующих основных параметров:
1. Максимального времени исполнения операций.
2. Среднего времени исполнения операций.
3. Задержки между внешним событием и реакцией на него (для ОС она напрямую зависит от длины критических секций, защищенных спинлоками).
Под „операциями" здесь и далее будут пониматься функции, работающие с объектами синхронизации: блокировками, барьерами, условными переменными. (Еще в стандарте определены блокировки чтения-записи, но в системах реального времени они практически не используются из-за серьезных проблем с инверсией приоритетов - ситуацией, когда нить с приоритетом большим, чем у владельца, но меньшим, чем у ожидающей нити, занимает процессор и не дает владельцу освободить блокировку, тем самым блокируя и ожидающую нить [2].)
В библиотеке нити Р0Б1Х реализованы полностью, и уже многие годы идет их переработка с учетом требований систем реального времени. Однако эти изменения всегда тормозились из-за трений между пользователями, которым не нужна поддержка реального времени, и теми, кому она нужна, а поскольку первых большинство, внесение правок встречает препятствия. Из-за этого в библиотеке до сих пор остаются узкие места, однако даже если их устранить, есть более глобальная проблема: универсальность фьютексов, на основе которых сделана вся синхронизация.
Каким же образом универсальность оказывается недостатком? Реализовать барьеры и условные переменные только на фьютексах очень сложно, поэтому они были сделаны на основе блокировок, которые реализовать через фьютексы гораздо проще (в конце концов, недаром слово фьютекс" означает быстрая блокировка"). В итоге все объекты действительно оказываются основаны только на фьютексах, но такая иерархия (в противоположность реализации напрямую через спинлоки ядра) приводит к определенным проблемам в системах жесткого реального времени:
1. Внутренняя блокировка, защищающая состояние объекта, должна следовать протоколу защиты от инверсии приоритетов, что в настоящее время не сделано.
2. В ряде случаев увеличиваются задержки и накладные расходы, например, если при реализации напрямую" требуется один системный вызов, то в текущем варианте условных переменных, в худшем случае, нить сделает по системному вызову в начале и в конце двух критических секций и один вызов для собственно выполнения операции - итого пять вызовов, к тому же, даже если внутренняя блокировка объекта окажется свободна, ее захват и освобождение не бесплатны - это четыре лишние атомарные инструкции.
3. Проблема, указанная в предыдущем пункте, усугубляется особенностями исторического развития фьютексов и ядра Linux. Для защиты внутренних объектов ядра всегда использовались спинлоки, однако в системах реального времени это не годится: чтобы получить детерминированные задержки при работе со спинлоками, длина критических секций, которые они защищают, должна быть ограничена, потому что внутри таких секций задача не может быть вытеснена. Разработчики ядра не всегда заботятся об этом, и во многих случаях длина этих секций ничем явно не ограничена. Поэтому в патче для систем реального времени от Инго Молнара очень многие спинлоки в ядре были заменены на блокировки [3]. В результате этого барьеры и условные переменные в NPTL реализованы на основе пользовательских блокировок, которые реализованы на основе фьютексов, которые реализованы на основе блокировок ядра, которые, в свою очередь, реализованы на основе спинлоков ядра. Понятно, что такая длинная иерархия отрицательно влияет и на среднее, и на максимальное время исполнения операций.
4. Теряется возможность некоторых оптимизаций (подробней об этом будет сказано, при описании конкретных объектов).
Помимо этого, хотя вызов sys_futex и задумывался как универсальное средство, часть функциональности, нужной для конкретных объектов (например, атрибут устойчивости или протокол наследования приоритета для блокировок), реализовать только на уровне пользователя невозможно. В итоге, со временем, реализация фьютексов все больше усложнялась добавлением кода, предназначенного для решения специфических задач. А сам фьютекс все дальше уходил от первоначальной концепции описываемого несколькими небольшими правилами простого объекта синхронизации, и в настоящее время вызов sys_futex выглядит гораздо сложнее, чем когда появлялся.
Итого получаем две проблемы: реализация всех объектов через фьютексы и то, что библиотека изначально не ориентировалась на системы реального времени. Наиболее существенные аспекты второй проблемы рассматриваются в следующей главе.
4. О СООТВЕТСТВИИ №ТЬ ТРЕБОВАНИЯМ СИСТЕМ РЕАЛЬНОГО ВРЕМЕНИ
Инициализация объектов
Каждому объекту синхронизации ставится в соответствие очередь ждущих на нем нитей в ядре. В КРТЬ память для этой очереди выделяется и освобождается автоматически по мере необходимости, и хотя используется небольшой кэш, он не гарантирует полное отсутствие выделений памяти, которые могут занимать неопределенно долгое время. Такой подход упрощает использование фьютексов: нет нужды их инициализировать, и устраняется опасность утечки памяти. Это даже позволяет вообще не вызывать деструкторы для объектов.
Однако из-за неопределенности времени выделения памяти, инициал
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.