Программные продукты и системы

Существуют два принципиально различных подхода к построению встроенных приложений (см. стр. 24-30 настоящ. ном. журн.): срабатывающие по событиями (событийные) и срабатывающие по времени (синхронные) системы [1]. Под срабатыванием здесь понимается некоторое явление, вызывающее инициализацию таких действий, как активация задач или передача сообщений. Эти два подхода к построению встроенных программных комплексов различаются механизмами запуска коммуникационных процессов и процессов выполнения задач. В случае событийных систем все такие процессы запускаются вследствие возникновения явлений (событий), расценивающихся как существенные изменения состояния системы. В случае синхронных систем запуски процессов осуществляются в предопределенные моменты времени.

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

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

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

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

Для разрешения этого противоречия в систему вводятся так называемые спорадические зада- чи [2], активизируемые (прямо или косвенно) событиями во внешней среде. Моменты активации спорадических задач не являются предопределенными, но их выполнение не должно препятствовать своевременному выполнению периодических задач. Поэтому на время исполнения спорадической задачи накладываются ограничения. Во-первых, это должны быть относительно короткие задачи (выполнение спорадической задачи не может требовать значительных ресурсов процессорного времени). Во-вторых, накладывается ограничение на минимальный интервал времени между соседними моментами активации одной и той же спорадической задачи (интервал спорадической задачи).

Задачи и экземпляры задач. В качестве примера разделения структур данных на статическую и динамическую составляющие можно указать статические и динамические поля в дескрипторах задач. Часть полей в дескрипторе задачи – константы (например, имя задачи, размер стека, адрес точки входа в корневую процедуру задачи, код приоритета). Другие поля хранят переменные значения (например, текущее состояние задачи, текущее положение вершины стека). Необходимо отметить, что различия между статической и динамической частями дескриптора задачи имеют и более глубокий смысл, чем простое проведение грани между дешевой постоянной и дорогостоящей оперативной памятью. При конструировании и анализе встроенных приложений необходимо учитывать различия между статической и динамической сторонами понятия задача.

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

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

Сама задача является объектом статическим и представляется в системе уникальным статическим дескриптором. Экземпляр задачи – объект динамический. Каждый экземпляр задачи представляется в системе собственным динамическим дескриптором. Конструкторы встроенных систем иногда не отдают себе отчета в различии этих понятий. Так, в операционной системе MCX11 блоки управления задачами (то есть дескрипторы задач) разделяются на две секции только для минимизации оперативной памяти, а не по причине сущностного различия между задачами и их экземплярами (факт, не упоминаемый в описании концепции MCX11).

Ниже используется модель множества задач синхронной системы, близкая к представленной в [2]. В описание модели входит следующее.

1. Встроенное приложение X = { t1, t2, …, tI, ..., tn } суть множество периодических и спорадических задач ti.

2. Каждая задача ti является статическим объектом. Тело задачи суть программа, представляющая алгоритм реализации возложенных на задачу функций. Задача представляется в системе дескриптором, содержащим ссылку на точку входа в тело соответствующего ей программного кода. Кроме того, статический дескриптор задачи может содержать ряд статических характеристик, отражающих особенности требований к процессу ее выполнения.

3. К основным статическим характеристикам периодической задачи ti относятся период pi ее выполнения (моменты активации экземпляров ti,1, ti,2, ti,3, … этой задачи разделены временными интервалами pi) и фаза fi (смещение момента активации экземпляра ti,1 этой задачи относительно начала выполнения статического графика).

4. Одной из статических характеристик спорадической задачи ti является значение параметра pi, характеризующего минимальный интервал между соседними моментами активации ее экземпляров ti,1, ti,2, ti,3, … (интервал спорадической задачи).

Таким образом, понятию задача соответствует представление о статических свойствах программы, представляющей некоторый алгоритм, и о статических свойствах ансамбля {ti,1, ti,2, ti,3, ...} экземпляров задачи. Дескриптор задачи является статически формируемой структурой, а дескриптор экземпляра задачи – динамически формируемой структурой. Для иллюстрации различия между этими типами дескрипторов заметим, например, что постоянное значение приоритета задачи не есть то же самое, что постоянное значение приоритета экземпляра задачи. Действительно, если задаче ti предписано постоянное значение приоритета, то все ее экземпляры ti,1, ti,2, ti,3, ... должны иметь этот приоритет. Требование постоянства приоритета экземпляра ti, j задачи является менее строгим: другим экземплярам той же задачи могут быть предписаны другие требования к значениям их приоритетов.

Построение статических графиков. Статические графики относятся к разряду наиболее важных системных структур для синхронных систем. Следует заметить, что при построении графиков функционирования надежных встроенных программных комплексов с предсказуемым поведением может возникнуть ряд проблем.

Входные данные для построения статического графика должны включать информацию о количестве процессорного времени, необходимого для выполнения задачи. Можно указать два способа задания этого статического параметра. Во-первых, разработчик приложения может в явном виде указать значение этого параметра, беря на себя ответственность за его корректность. Другой путь возможен при наличии автоматического анализатора кода программы. Наиболее важным параметром, получаемым в ходе этого анализа, является наихудшее время выполнения программы (WCET – worst case execution time). Требования к качеству WCET анализа (ручного или автоматизированного) является одним из ключевых требований к разработке эффективных статических графиков. Если заданное дескриптором задачи значение WCET существенно превосходит истинное значение WCET, то истинная плотность загрузки процессора окажется существенно ниже ожидаемой (неэффективный график). В противоположном случае (недооценка истинного значения WCET) разработанный график может оказаться невыполнимым.

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

Общий период функционирования системы. Как было отмечено ранее, встроенные системы характеризуются жесткостью требований ко времени выполнения задач. Формально это выражается указанием способа вычисления предельного срока выполнения задачи. Наиболее простым и распространенным способом является указание длины временного интервала Di = ( tterm – tarrive ) между моментом активации экземпляра задачи tarrive и предельным сроком его завершения tterm (величину Di называют относительным сроком выполнения задачи).

Таким образом, в случае синхронных систем каждая задача ti характеризуется, по крайней мере, следующими статическими параметрами: периодом pi (для спорадической задачи – интервал pi), величиной требуемого процессорного времени ci для выполнения одного экземпляра задачи и относительным сроком Di выполнения задачи. При этом типичным является ограничение Di < pi; это означает, что очередной экземпляр задачи не может быть активирован раньше завершения предыдущего экземпляра этой задачи.

Встроенные приложения обычно содержат большое число периодических задач с различными периодами исполнения. Если каждая задача активируется строго периодически, то длина общего периода выполнения приложения (ESOP – entire system operation period) равна наименьшему общему кратному периодов pi выполнения всех задач.

При конструировании встроенного программного комплекса его разработчик задает номинальное значение периода pnom,i каждой из задач ti. В реально работающей системе номинальное значение периода не может быть выдержано с абсолютной точностью: действительное значение периода pact,i будет в большей или меньшей мере отклоняться от номинального значения. Как правило, разработчик приложения по умолчанию допускает такое отклонение. Требования к периоду выполнения задачи представляются более полно, если наряду с номинальным значением периода pnom,i указывается допуск di на отклонение актуального значения периода pact,i от номинального. Использование информации о значениях допусков на периоды выполнения задач может обеспечить существенное сокращение общего периода выполнения приложения.

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

Анализ опубликованных временных характеристик конкретных приложений [3,4] показывает, что разработчики по умолчанию пользуются именно этим правилом, хотя в литературе по данной тематике понятие ранжирования задач отсутствует. Например, в разработанной Германом Копецом спецификации сетевого окружения встроенной системы для управления электромобилем [5] периодам передачи сообщений в сети назначены значения из следующего ряда:

.                 (1)

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

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

 – степень ранга (poweri); p0 – базовый период.

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

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

counter mod poweri = 0.

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

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

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

Данный метод хорош тем, что на каждом базовом интервале активируется не более двух рангов. Таким образом, в отличие от первого метода реактивность системы перестает зависеть от числа рангов в приложении.

Система согласованных рангов. Более общим случаем системы двоичных рангов является система согласованных рангов. Она накладывает следующее ограничение на значения периодов активации рангов. Если P – множество всех периодов данного приложения, то для каждой отдельно взятой из него пары периодов pi и pj выполняется условие:

.                            (2)

Динамический планировщик для такой системы рангов с нулевыми смещениями реализуется практически с той же эффективностью, что и в случае двоичных рангов. Фактически алгоритм остается таким же, как и для двоичных рангов, с той лишь разницей, что последовательность двоичных сдвигов заменяется последовательностью целочисленных делений с остатком на nj. При этом активируются те ранги, для которых при соответствующем делении остаток был равен 0. Причем для данного варианта реализации статического графика условие (2) можно ослабить следующим образом. Если p0 – минимальный период в P, то:

.                        (3)

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

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

Список литературы

1. Kopetz H. Real-time Systems. Design principles for Distributed Embedded Applications. Kluwer Academic Publisher, Boston, 1997.

2. Chai S., Agrawala A. Scheduling Aperiodic and Sporadic Tasks in Hard Real-time Systems, Department of Computer Science, University of Maryland, 1997.

3. Bailey C.M., Burns A., Wellings A.J., Forsyth C.H. A Performance Analysis of a Hard Real-time System. Real-time Systems Research Group, Department of Computer Science, University of York, 1994.

4. Gerber R., Hang S. Slicing Real-time Programs for Enhanced Schedulability, Department of Computer Science, University of Maryland, 1995

5. Kopetz H. A Solution to an Automotive Control System Benchmark. Institute for Technical Informatics, Technical University, Vienna, Austria, research report 4/1994, Apr 1994

6. McConnell D., Lewis B., Cray L. Reengineering a Single Thread Embedded Missile Application onto a Parallel Processing Platform Using MetaH. - Real-Time Systems, v.14, no.1, Jan 1998.