Разработка библиотеки нитей POSIX реального времени Магистерская диссертация Студент: Фёдоров Александр, 418 гр. Научный руководитель: Гилязов С.С.

Нити (threads) легковесные процессы, разделяющие ресурсы системы. POSIX.1c (он же IEEE c) интерфейс программирования приложений, определяющий создание и управление нитями. Альтернативы интерфейсу программирования приложений POSIX: OpenMP Intel Thread Building Blocks Boost.Threads

Цель работы Создание библиотеки нитей, совместимой со стандартом IEEE c и ориентированной на работу в системах реального времени.

Существующие библиотеки нитей POSIX: LinuxThreads (менеджер нитей, синхронизация на основе сигналов) NPTL (поддержка в ядре, синхронизация на основе futex'ов) В большинстве ОСРВ своя реализация (vxWorks, QNX, LynxOS, …) el_pthread (разработана для ОС Эльбрус, имеет лучшее время переключения контекста)

Чем хороша el_pthread? Тем, что... Очередь нитей в ядре инициализируется заранее Объекты синхронизации резидентируются в ОЗУ Тесная интеграция с ядром

Чем несовершенна el_pthread? Тем, что... Ограничена масштабируемость из-за одной хэшированной очереди для объектов синхронизации Ограничено соответствие POSIX Реализовано элементарное наследование приоритета Нельзя клонировать процесс Время переключения контекста, мкс

Требования систем реального времени: Быстрый вероятный путь исполнения операции Предсказуемое время исполнения операции Минимальное время реакции на внешние события Минимум накладных расходов, в том числе: Минимум системных вызовов Минимум переключений контекста

Средства обеспечения требований СРВ: Использование атомарных операций в пользовательском пространстве Использование ожидающих владельцев Ограничение длительности отключения прерываний Тесная интеграция библиотеки с ядром ОС

Мьютексы сериализуют выполнение участка кода. Типичное распределение вероятностей для их состояния: 80 % мьютекс свободен 15 % есть владелец 5 % есть другие нити в очереди С наибольшей вероятностью мьютекс свободен, важно оптимизировать этот случай. Используем атомарные операции вместо системных вызовов. Атомарная операция Свободен? Системный вызов Успех Да Нет Ядро Пользователь Реализация мьютексов

Порядок, в котором нити владеют мьютексом, может быть изменён на лету. Реализация мьютексов Захват Передача Захват Передача Освобождение Нить с высоким приоритетом Нить с низким приоритетом Без ожидающих владельцевС ожидающими владельцами Захват Передача Кража Освобождение Нить с высоким приоритетом Нить с низким приоритетом Передача

Реализация мьютексов Особенности реализации протокола наследования приоритета: Требуется наличие Thread Local Storage для оптимизации через атомарные операции Возможно образование цепочек наследования приоритета с циклами Нить 1 Нить 3Нить 4 Нить 2 Нить 5Нить 6 Мьютекс 1 Мьютекс 3 Мьютекс 2

Реализация условных переменных Условные переменные позволяют нитям ожидать выполнения условия. Использование спинлоков ядра ОС (повышает предсказуемость времени исполнения операций) Дублирование функциональности захвата и освобождения мьютексов в ядре (снижает накладные расходы) Для улучшения латентности прерывания периодически включаются При выполнении pthread_cond_broadcast() будится максимум одна нить (если мьютекс занят, будить нет необходимости)

Реализация барьеров Барьер блокирует исполнение нитей, пока их не наберётся заданное число. Использование спинлоков ядра ОС (аналогично условным переменным) Для улучшения латентности прерывания периодически включаются Используется алгоритм защиты от неограниченной инверсии приоритетов 1-я нить (высокий приоритет) Регистрируется на барьере Вытесняет 2-ю нить Будит 1-ю нить Блокируется на барьере 2-я нить (низкий приоритет) 3-я нить (средний приоритет) Механизм возникновения инверсии приоритетов на барьерах

Измеренное время переключения контекста с использованием условных переменных библиотек elpthread (новая) и el_pthread (старая): Влияние протокола взаимных блокировок Минимум, мксМаксимум, мкс PTHREAD_PRIO_NONE 3063 PTHREAD_PRIO_INHERIT 3776 PTHREAD_PRIO_PROTECT 4072

Создана библиотека нитей, реализующая все функции из IEEE Std с-2004 и двоично совместимая с NPTL Тестовым пакетом posixtestsuite подтверждено соответствие стандарту всех реализованных функций кроме read-write lock'ов Планируется дальнейшая работа над библиотекой (оптимизация адаптивных мьютексов, read-write lock'и, поддержка атрибута устойчивости мьютексов из стандарта 2008 г.) Итоги работы