Тема 6
Операционные системы реального времени

В этой лекции будут рассмотрены такие вопросы как особенности ОСРВ, требования к ОСРВ и др. Но прежде приведем некоторые сведения из теории ОС вообще. В тексте будут использоваться следующие аббревиатуры: ОС - операционная система, ОСРВ - операционная система реального времени, ОСОН - операционная система общего назначения.

Операционные системы

С точки зрения программиста, разрабатывающего ОС, ОС - это система управления ресурсами (ЭВМ). Под "ресурсами" понимается процессорное время, оперативная память, устройства ввода-вывода, долговременного хранения данных и т.п. Ресурсы "предназначены" для использования прикладными программами. Задачей ОС является предоставление прикладным программам ресурсов таким образом, чтобы достигалась некая цель, например, достижение наибольшей эффективности использования ЭВМ, обеспечение наилучшей реактивности системы и пр.

С точки зрения программиста, разрабатывающего прикладные программы, ОС - это своего рода "черный ящик", воображаемая, абстрактная ЭВМ, а её (ОС) задачей является предоставление программисту удобных средств для работы с реальной аппаратурой. Например, для того, чтобы прочитать данные с накопителя на жестких дисках, программист использует ряд системных вызовов (например, в Unix - open(), read(), write(), close() и др.) с использованием абстракций "каталог", "файл" вместо того, чтобы "вручную" позиционировать головки привода накопителя, включать и выключать его двигатель и пр. Все эти низкоуровневые действия выполняет "по просьбе" прикладной программы ОС.

Мы остановимся здесь только на некоторых аспектах проектирования ОС. Во-первых, рассмотрим диаграмму состояний задач (процессов,нитей) в многозадачных средах:

На этой диаграмме показаны состояния процессов и переходы между этими состояниями. Состояние READY (ГОТОВА) - это состояние, когда задаче для продолжения работы не требуется ничего, кроме процессорного времени. Все задачи в этом состоянии образуют очередь. Когда планировщик задач выбирает какую-либо задачу из этой очереди, эта задача переходит в состояние RUNNING (ИСПОЛНЯЕТСЯ). Из этого состояния задача может перейти либо обратно в состояние READY (этот переход называется "вытеснение"), либо в состояние BLOCKED (ЗАБЛОКИРОВАНА). Это состояние также называют SLEEPING, WAITING, SUSPENDED. Это такое состояние, когда задаче для продолжения работы, помимо процессорного времени, требуется еще какой-то ресурс или данные.

Обратите внимание на переход, помеченный словом "SYSCALL". Это обращение к операционной системе, системный вызов. Совершая этот вызов, задача переходит из пользовательской фазы в системную фазу. При этом важно, может ли быть задача вытеснена только тогда, когда она находится в пользовательской фазе или же на возможности вытеснения не сказывается, в какой именно фазе работает задача.

Если вытеснение задачи возможно из любой фазы, тогда ядро ОС называют вытесняемым (англ. "preemptable", от "preempt", то есть "вытеснять"). В противном случае (вытеснение возможно только из пользовательской фазы) ядро ОС называют невытесняемым.

Во-вторых, уделим некоторое внимание проблемам, связанным с зависимостями между задачами. Как говорилось в Лекции 2, у задач могут иметь место 2 типа зависимостей - это ограничения на порядок исполнения и критические секции. Здесь мы будем говорить только о критических секциях. Напомним, что теория планировщиков, изложенная в предыдущих лекциях, базировалась на предположении, что все задачи независимы. На практике обычно имеет место обратное и это привносит определенные сложности в проектирование как ядер ОСРВ, так и приложений РВ.

Определение. Критическая секция - участок программного кода, в котором задача работает с каким-либо общим ресурсом.

Под словом "общий" подразумевается, что тот или иной ресурс используется не только данной задачей, но и другими. Примерами таких ресурсов могут выступать структуры данных в памяти, внешние устройства и др. (примеры...связанный список)

Во время исполнения критической секции задачу нельзя вытеснять, так как это может привести к нарушению целостности ресурса, неправильному функционированию устройств, получению неправильных результатов и прочим нежелательным последствиям. Точнее, нельзя давать управление задачам, которые используют этот же ресурс. Недопущение нахождения более чем одной задачи внутри критической секции обычно называют "синхронизацией", хотя, возможно, этот термин не совсем удачен. Среди средств синхронизации можно упомянуть следующие:

• Запрет прерываний. Используется (в ядре) только тогда, когда это совершенно необходимо и на короткое время. Не работает на машинах с более чем одним процессором (прерывание может обработано на другом процессоре)
• Семафоры. Используются в прикладных программах.
• Мьютексы. Аналог семафоров, используется при разработке многонитевых приложений.
• Спин-блокировки (spin-locks). Используются внутри ядер. В отличие от запрета прерываний, работоспособно и на SMP- машинах.

Особенности ОСРВ и их отличия от ОСОН

• ОСОН проектируются так, чтобы достигалось оптимальное ("справедливое") распределение ресурсов ЭВМ между задачами. При проектировании ОСРВ главное - реактивность системы.
• Применение ОСРВ подразумевает, помимо наличия ЭВМ, наличия внешнего по отношению к нему мониторируемого и/или управляемого объекта. Применяя ОСОН для каких-то целей, можно "обойтись" только ЭВМ.
• ОСОН (в комплекте с другим ПО) воспринимается (пользователями) как готовый продукт, готовый к использованию. ОСРВ - это всего лишь инструмент для создания программной части СРВ.
• Как правило, средства разработки ПО для данной программно-аппаратной платформы в мире ОСОН работают на этой же программно-аппаратной платформе. В мире ОСРВ ситуация зачастую иная. Например, средства разработки функционируют в среде Windows, а разрабатываемое ПО для СРВ будет работать на микроконтроллере под управлением QNX.

Параметры ОСРВ

• Время реакции системы на прерывание (interrupt latency)
• Время переключения контекстов (scheduling latency)
• Размер ядра системы
• Возможность исполнения (загрузки?) из ПЗУ

Первый параметр есть промежуток времени, который проходит с момента, когда на процессор поступил сигнал "запрос на прерывание" и до момента, когда начала исполняться первая инструкция обработчика прерывания. "Природа" этой величины такова. В коде ядра имеются участки, которые исполняют все задачи (критические секции); во время исполнения этих участков ОС запрещает все прерывания. Если в этот время возникнет какое-то прерывание от внешнего устройства, оно не будет обработано до тех пор, пока ОС не разрешит прерывание. Максимальный по длительности такой участок и определяет описываемую величину. Отметим, что так называемое "аппаратное время реакции на прерывание", которое представляет собой максимальную длительность исполнения инструкции процессором (тут следует помнить, что процессоры физически не могут отложить выполнение инструкции, они всегда выполняют ее до конца и во время ее исполнения не реагируют на прерывания), гораздо меньше, чем "время реакции на прерывания" ОС. Последняя величина на более или менее современных архитектурах составляет примерно 4-8 мксек. Если же оценить аппаратное время реакции на прерывание, то при тактовой частоте, скажем, 100 МГц (для микроконтроллеров это будет сильно завышено, а для ЭВМ - занижено) и самой "долгой" инструкции, требующей, скажем, 10 тактов, то получим 100 нсек, что примерно в 500 раз меньше, чем время реакции на прерывание ОС. Это связано с тем, что критические секции в коде ядра ОС могут составлять весьма значительное количество инструкций процессора.

По поводу второго параметра можно сделать следующие замечания

• Во-первых, на контексты нитей требуется меньшее количество информации, по сравнению с контекстами процессов. Поэтому переключение контекстов нитей происходит быстрее, чем переключение контекстов процессов. Это проявляется в требованиях, предъявляемых к ОСРВ (см. немного ниже)
• Во-вторых, различают монолитные ядра и микроядра (еще бывают экзоядра, а также гибридные ядра). Ядра первого типа содержат программный код для работы с любой аппаратурой и для выполнения любых мыслимых действий (например, драйверы устройств в таких ОС являются частью ядра вне зависимости от того, включены они в состав ядра при компиляции или же подгружены во время работы). Ядра второго типа содержат минимум кода. Поэтому они имеют небольшой размер (~10 Кб). Драйверы устройств, наряду с прочими компонентами, например, планировщиком задач в таких ОС оформлены в виде обычных прикладных программ, запускаемых как процессы или нити. Именно для такого рода ядер наиболее актуален данный параметр вследствие того, что, например, обращение к внешнему устройству требует, как минимум, двойного переключения контекстов, один раз от процесса, запрашивающего ту или иную операцию у драйвера, к процессу драйверу и второй раз - обратно. В монолитных же ядрах подобное обращение есть всего лишь системный вызов, поэтому передача управления какому-то еще процессу и обратно не требуется.

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

• Важность третьего и четвертого параметров обсуловлена тем, что зачастую ОСРВ является т.наз. "встроенной/встраиваемой системой" (англ. "built-in system"), а это означает ограниченность в ресурсах (прежде всего, объеме оперативной памяти), а также отстутствие накопителей на жестких магнитных или оптических дисках.

Требования к ОСРВ. Стандарт POSIX на ОСРВ

ОСРВ должны удовлетворять следующим требованиям:

• Ядро ОСРВ должно быть прерываемым
• ОСРВ должна предоставлять механизм нитей. Число уровней приоритетов не должно быть меньше, чем 256. Почему не 32 и не 100000...?
• ОСРВ должна предоставлять предсказуемые механизмы взаимодействия и синхронизации задач.
• В ОСРВ должна существовать система наследования приоритетов (см. по этому поводу ниже)
• В документации должны быть указаны параметры ОСРВ (время реакции на прерывание, время переключения контекстов, максимальные времена исполнения системных вызовов и т.п.)

Необходимость первого требования самоочевидна: поскольку ядро должно иметь возможность дать управление той задаче, которая больше всего в этом "нуждается", то оно должно иметь возможность вытеснять задачи независимо от того, в какой фазе, системной или пользовательской (см. рисунок выше), они работают в данный момент.

Инверсия приоритетов. Наследование приоритетов

Остановимся подробнее на 4-ом требовании. Для этого введем понятие "инверсии приоритетов". В простейшем случае под этим понимается следующая ситуация.

Прямая инверсия

Пусть у нас имеется две _зависимых_ задачи с разными приоритетами. Тогда может случиться так, что задача с более низким приоритетом, заняв общий ресурс, вынудит задачу с более высоким приоритетом ждать до тех пор, пока ресурс не освободится. Иными словами, из-за зависимости между задачами более приоритетная задача не может вытеснить менее приоритетную несмотря на свой более высокий приоритет. Из-за этого более приоритетная задача может пропустить свой крайний срок. Избежать прямой инверсии можно только одним единственным способом - сделать задачи независимыми.

Косвенная инверсия

Ситуация еще более усугубляется в случае, если еще имеется хотя бы одна задача с приоритетом, промежуточным между двумя данными и _независимая_ от них. Тогда эта третья среднеприоритетная задача может вытеснить низкоприоритетную в то время, когда она заняла ресурс, нужный также высокоприоритетной задаче. Получается, что третья задача не может быть вытеснена более приоритетной из-за того, что ожидает освобождения ресурса, используемого низкоприоритетной задачей, а эта последняя не может его освободить, так как вытеснена среднеприоритетной задачей.

В связи с этим нередко упоминают неприятную историю, произошедшую с марсоходом MarsPathFinder...

Для недопущения подобных ситуаций предлагаются так называемые механизмы "наследования приоритетов". Разработчики таких механизмов должны уделять внимание следующим вопросам:

• В какие момент времени должен меняться приоритет у задачи?
• Какой именно приоритет должен быть установлен в эти моменты?
• Каков может быть порядок занятия и освобождения ресурсов?

Почему эти вопросы важны, мы увидим из рассмотрения одной схемы наследования приоритетов, которая выглядит следующим образом:

Когда задача T1 пытается занять ресурс R, уже занятый к этому моменту менее приоритетной задачей T2, приоритет задачи T2 повышается до приоритета задачи Т1. Когда задача T2 освобождает ВСЕ ресурсы, ее приоритет становится равным первоначальному.

Именно такой механизм реализован во многих ОСРВ. Посмотрим, решает ли он проблему инверсии приоритетов. При этом будем придерживаться предположения, что чем меньше номер задачи, тем больше ее приоритет. Вот два возможных сценария развития событий, демонстрирующих недостатки приведенной схемы наследования приоритетов [Victor Yodaiken].

Пусть имеется 4 задачи, T1-T4, причем задачи Т1 и Т4 имеют общий ресурс В. События могли развиваться в следующей последовательности:

• T4 занимает ресурс A и затем ресурс B
• Т1 вытесняет Т4, блокируется на ресурсе В и передает свой приоритет задаче Т4
• Т4 освобождает ресурс В, при этом она продолжает работать с приоритетом задачи Т1, поскольку она еще не освободила ресурс А

Получается, что задача Т4 какое-то время будет "незаконно" иметь приоритет, превышающий приоритеты задач Т2 и Т3, что, является, по сути, инверсией приоритетов и может привести к тому, что задачи Т2 и Т3 не успеют отработать до своих крайних сроков.

Пусть опять имеется 4 задачи, причем Т4 и Т3 имеют общий ресурс А, а Т3 и Т1 имеют общий ресурс В. Может сложиться такая ситуация:

• Т4 занимает ресурс А
• Т3 вытесняет Т4, занимает ресурс В, затем блокируется на ресурсе А, при этом Т4 получает приоритет Т3
• Управление получает Т4
• Т1 вытесняет Т4, блокируется на ресурсе В, при этом Т3 получает приоритет Т1 "впустую", так как она блокирована на ресурсе А
• Управление получает задача Т2

В результате получается, что задача Т2 не дает закончить задаче Т4 работу с ресурсом А, что мешает начать (и закончить) работу с этим ресурсом и с ресурсом В задаче Т3, что, в свою очередь, мешает задаче Т1, который нужен ресурс В. Опять таки, имеем инверсию приоритетов - задача Т2 не может быть вытеснена задачей Т1, несмотря на свой более низкий приоритет.

Имеются более сложные модификации механизма наследования приоритетов, но, к сожалению, общее наблюдение таково, что чем в большей степени улучшается этот механизм, тем все сложнее обнаружить в нем возможную логическую ошибку или ошибку в реализации. Поэтому вполне справедливо наследование приоритетов подвергается критике и предлагаются иные способы работы с общими ресурсами, например, атомарные операции (для случая недолгих критических секций) и, для случая длительных подход клиент-сервер, при котором все операции с ресурсом выполняет один специально отведенный для этого процесс, который мог бы упорядочивать запросы от клиентов в зависимости от их приоритета.

Рассмотрим теперь модификацию механизма наследования приоритетов, отличающегося от вышеприведенного тем, что

• Когда задача освобождает ресурс, ее приоритет становится равным приоритету, который она имела перед вхождением в критическую секцию.
• Наследование переносится не только на ту задачу, которая занимает ресурс, но и на все задачи, которые могут блокировать эту данную (англ. inheritance transitivity).

Во-первых, такая схема подразумевает, что критические секции не могут перекрываться - они должны быть вложенными. В противном случае механизм не будет работать должным образом. Для иллюстрации представим себе следующий сценарий развития событий. Пусть некоторая задача, имеющая приоритет π, занимает ресурс A, получая при этом приоритет π_A > π, затем занимает ресурс B, получая при этом приоритет π_B > π_A и затем освобождает ресурс A. Согласно правилу, после этого она будет иметь приоритет π, но все еще работает с ресурсом B и, по идее, должна иметь приоритет π_B > π. Таким образом, получается, что схема работает неправильно. В случае вложенных (не перекрывающихся) критических секций такая ситуация возникнуть не может. Под вложенностью понимается то, что освобождение ресурсов происходит в порядке, обратном тому, в каком они занимались. В сложных системах (много задач и много общих ресурсов) проверка того, что это условие соблюдается, может оказаться весьма нетривиальной.

Во-вторых, даже при строгом соблюдении вложенности критических секций рассматриваемая модификация механизма наследования приоритетов может привести к некорректному поведению системы. Пусть у нас имеется 4 задачи, T₁ с приоритетом π₁ и так далее. Нумерация задач - как ранее, то есть задача с бОльшим порядковым номером имеет меньший приоритет. Сценарий развития событий, ведущий к инверсии приоритетов:

• T₄ c приоритетом π₄ занимает ресурс А и затем ресурс B
• Задача T₂ вытесняет задачу T₄, блокируется на ресурсе B, передавая свой приоритет π₂ > π₄ задаче T₄
• Получает управление задача T₁ и блокируется на ресурсе А, передавая свой приоритет π₁ задаче T₄
• Если теперь задача T₄ освободит ресурс В, то она будет иметь приоритет, которая она имела до вхождения в крит. секцию, то есть π₄

Получается, что задача T₁ будет вынуждена ждать освобождения ресурса А задачей T₄, которая работает с приоритетом π₄, а не π₁, как должно было бы быть. Ситуация еще более ухудшится, если управление получит задача T₂ или же задача, которая вообще не использует ресурсы А и В.

Классификация ОСРВ

Различают следующие типы ОСРВ:

• Исполнительные СРВ (крайне неудачный термин, имхо). Различные среды разработки и исполнения, высокая реактивность. Пример - VxWorks.
• Ядра реального времени. Пример - OS9
• Unix РВ. Пример - LynxOS.
• Расширения РВ для Windows NT.
• Расширения РВ для клона Unix Linux. Примеры - RT Linux, KURT.

Краткий обзор наиболее распространенных коммерческих ОСРВ (LynxOS, pSOSystem, VxWorks, VRTX, QNX).

Все эти системы обладают следующим общими свойствами (за некоторыми исключениями):

• соответствуют (по крайней мере, частично) стандарту POSIX на интерфейс прикладных программ, обеспечивающий функционирование в режиме реального времени, то есть:
  • обладают вытесняемым ядром
  • предоставляют вытесняющий динамический механизм планирования, основанный на использовании статических приоритетов задач (задачи, как правило, оформлены в виде нитей)
  • предоставляют механизмы синхронизации нитей, как правило, мьютексы
  • имеют, однако, и свой собственный API (то есть не по POSIX)
• являются модульными и масштабируемыми; ядро достаточно мало для того, чтобы поместиться в ПЗУ встраиваемых систем, при этом имеется возможность добавления средств ввода-вывода, управления файлами, сетевого взаимодействия (например, TCP/IP) и т.п.
• быстры и эффективны, что достигается за счет:
  • построения с примением концепции микроядра (как правило)
  • низких накладных расходов, например, на работу планировщика, переключение контекстов, операции блокировки и деблокировки мьютексов и т.п.
  • небольшого времени реакции на прерывание (несколько микросекунд)
  • тщательной оптимизации критических секций в ядре (то есть тех участков кода, которые работают без вытеснения)
• поддерживают 2-х этапную обработку прерываний; это означает, что обработка прерывания происходит в два этапа - сначала исполняется короткая ISR (interrupt service routine/подопрограмма обслуживания прерывания), затем она ставит в очередь на выполнение более длинную IHR (interrupt handling routing/подпрограмму обработки прерывания); первая из них выполняет минимально необходимые действия, вторая - более времяемкие действия, например, передачу данных от внешнего устройства.

Отметим, что данное свойство не является прерогативой ОСРВ. Аналогичные механизмы обработки прерываний имеются и в ядрах ОС общего назначения. Например, в ОС Linux подобный механизм носит название upper half/bottom half, то есть "нижняя" и "верхняя" "половины". "Нижней половине" соответствует понятие IHR, верхней - ISR. В ОС Windows имеется механизм отложенного вызова процедур (DPC). Подпрограмма, вызываемая с помощью этого механизма, аналогична IHR.

• обладают более или менее гибкими схемами планирования:
  • число приоритетов нитей - как минимум 32 (это требование POSIX); в некоторых ОСРВ это число равно 128 или 256.
  • для нитей с одинаковым уровнем приоритета, если таковые имеются, применяются такие политики планирования, как FIFO и RR (round robin, то есть "карусели").
  • однако, не поддерживают алгоритм EDF (возможно, в силу большей сложности его реализации по сравнению с планировщиками со статическими приоритетами)
• довольно высокое разрешение таймеров и счетчиков (номинальное - наносекунды, реальное - микросекунды)
• как правило, не содержат механизмов подкачки и защиты памяти; при этом зачастую задачи и ядро исполняются в едином адресном пространстве

Далее перечислены некоторые особенности каждой из этих ОСРВ.

LynxOS:

• ядро размером 28 Кб, обеспечивающее диспетчеризацию прерываний, планирование задач и механизмы их синхронизации
• имеется возможность добавления KPI (kernel plug-ins), за счет чего эту ОСРВ можно использовать как обычную ОС типа UNIX, в частности, для разработки приложений.
• поддерживает механизмы защиты памяти (при наличии MMU) и подкачки

pSOSystem:

• ОО система
• поддерживает работу на нескольких процессорах
• планирование задач возможно как на основе приоритетов, так и на основе заранее созданного расписания
• драйверы устройств работают в пользовательской фазе, при этом ядро не диспетчеризует прерывания

VRTX:

• имеются различные варианты ядер, ориентированные на системы разного масштаба; например, одна из модификаций, требующая до 8 Кб ПЗУ и 1 Кб ОЗУ, предназначена для сотовых телефонов и других подобных устройств
• является первой системой, сертифицированной соответствующими органами для использования в системах, критических по отношению к здоровью и жизни людей; использовалась в самолетах модели "Боинг MD-11"

VxWorks:

• использовалась на марсоходе "MarsPathFinder"
• одна из немногих ОСРВ, обладающая монолитным ядром
• свой собственный API весьма популярен и при этом достаточно мощен
• в обычной конфигурации работает только на одном процессоре, однако имеется возможность работы на многопроцессорных машинах
• при наличии MMU обеспечивает механизмы защиты памяти, при этом изначально все задачи исполняются в одном адресном пространстве, но задача может по своему желанию создать отдельное адресное пространство

QNX:

• высокая степень масштабируемости, от 12 Кб до полнофункциональной ОС, могущей работать на многопроцессорных сетевых архитектурах
• микроядро обеспечивает диспетчеризацию прерываний, передачу сообщений между задачами и планирование нитей
• функциональность расширяется с помощь т. наз. менеджеров ресурсов, работающих вне ядра.

Дата последней модификации: 2011-01-30