Системы реального времени Лекция 2: Стандарты и расширения. Алгоритмы реального времени.

ОСРВ и обычные ОС: различия В ОСРВ делается горазд больший упор на организацию работы процессов в системе (более развитая система приоритетов, средства межпроцессного взаимодействия, синхронизации и т. п.)

ОСРВ и ВОС очень много… …наиболее распространенные: VxWorks, QNX, RTEMS, eCos, threadX, различные варианты embedded Linux (uClinux, LynxOS, HardHat, busybox)… И у каждой из них свои средства реализации многозадачности, синхронизации, межпроцессного взаимодействия…

Все они должны следовать некоему стандарту Чтобы обеспечить переносимость хотя бы программ высокого уровня для различных ОСРВ, ОСРВ должны следовать общему стандарту все распространенные ОСРВ следуют стандарту IEEE POSIX.1 (от Portable Operating System Interface) и (частично) расширению POSIX.1b (real-time extensions) Этот стандарт определяет все важнейшие параметры программного интерфейса операционной системы

Однако у каждой есть свои специальные средства …которые обычно являются расширением стандарта POSIX Стандарты не стоят на месте, и постепенно эти специальные средства также оказываются стандартизованными в том или ином виде Расширения стандарта POSIX.1 – POSIX.1a (POSIX core services, напр., fork()), POSIX.1b, POSIX.1c (thread extensions)

Характеристики времени выполнения алгоритма Для любого алгоритма есть две основные характеристики времени выполнения – среднее и максимальное время выполнения В обычных системах чаще всего оптимизируется среднее время выполнения алгоритма Для real-time алгоритмов важнее всего максимальное время выполнения

Максимальное время выполнения Важнейшим для ОСРВ является свойство алгоритма иметь конечное максимальное время выполнения Этим свойством обладают далеко не все алгоритмы Только такие алгоритмы могут использоваться в программном обеспечении систем реального времени

Временная сложность алгоритма основной параметр, характеризующий алгоритм; определяется как число шагов, выполняемых алгоритмом в худшем случае, обычно рассматривается как функция размера задачи, представленной входными данными Этот параметр не коррелирует с максимальным временем выполнения!

Временная сложность – от логарифмической до экспоненциальной Сложность: логарифмическая, линейная и полиномиальная, экспоненциальная… Пример 1: различные варианты сортировки списка (~n·log(n) vs ~n 2 ) Пример 2: поиск элемента в сбалансированному дереву (~sqrt(n)) Пример 3: поиск элемента в списке и хэш- таблице (~n) Пример 4: вычисление n! с помощью цикла (~n) и с помощью рекурсии (~ (n/e) n ).

NB: Реальное время выполнения Пусть у алгоритма А временная сложность больше, чем у алгоритма Б Не всегда и не при всех условиях реальное время выполнения у А выше, чем у Б… Пример: списки и хэш-таблицы vs деревья

NB: Реальное время выполнения - 2 …Поэтому в обычных программных системах часто используются теоретически более сложные, но в большинстве случаев более быстрые алгоритмы Но не в СРВ! – потому что для РВ важно максимальное время выполнения