Общие понятия. Крайние сроки.

Как уже говорилось, СРВ - это программно-аппаратный комплекс, осуществляющий мониторинг какого-то объекта и/или управление им в условиях временных ограничений. Возникающие на объекте события подлежат обработке в СРВ. Будем сопоставлять каждому типу события задачу.

Определение.ЗАДАЧА (TASK) - блок программного кода, ответственный за обработку тех или иных событий, возникающих на объекте управления.

Задача может быть "оформлена" в виде:

• Отдельного процесса
• Потока управления внутри процесса (нити, легковесного процесса)
• Обработчика прерывания/подпрограммы

Определение.РАБОТА ЗАДАЧИ (JOB) - процесс исполнения блока программного кода в ходе обработки события.

Аналогия...

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

• r (Release Time) - момент времени, когда возникает необходимость в передаче управления задаче; можно считать, что это момент события.
• d (Absolute Deadline) - абсолютный крайний срок, момент времени, к которому задача должна завершить очередную работу.
• s (Start Time) - момент времени, когда задача начала исполняться на процессоре
• с (Complition Time) - момент времени, когда задача закончила работу, обработав событие
• D (Relative Deadline) - относительный крайний срок. D = d - r
• e (Execution Time) - время исполнения задачи при выполнении ею очередной работы. e = c - s

Диаграмма ниже иллюстрирует эти параметры:

r s c d

* --------------- |

| | | |

| | | *

-+---+---+---+---+---+---+---+---+---+---+---+---+---+----> t (у.е.)

0 1 2 3 4 5 6 7 8 9 10 11 12 13

Определение.Крайний срок называется ЖЕСТКИМ (HARD), если он ОБЯЗАН быть соблюден, при этом в системе должна существовать возможность проверки того, был ли соблюден крайний срок или нет. Несоблюдение такого крайнего срока ведет к катастрофическим последствиям (авария, гибель людей и т.п.)

Определение.Крайний срок называется МЯГКИМ (SOFT), если _иногда_ его допустимо не соблюдать. Несоблюдение такого крайнего срока не ведет к катастрофическим последствиям, а лишь к некоторому снижению производительности, ухудшению качества обслуживания, повышению стоимости результатов, бесполезной трате времени и т.п.

Для количественного выражения "иногда" используют или вероятностный подход ("допустимо несоблюдение крайнего срока в 5% случаях"), или подход, основанный на введении т.наз. "функции полезности". При этом, если полезность завершения работы после крайнего срока обращается в нуль, мягкий крайний срок называют ЧЕТКИМ.

Определение.Система реального времени называется ЖЕСТКОЙ, если все крайние сроки, характеризующие эту систему - жесткие.

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

Определение.Система реального времени называется МЯГКОЙ, если хотя бы одиниз крайних сроков, характеризующих эту систему, является мягким.

В качестве примеров такого рода можно привести системы мультимедиа, системы связи (например, сотовой) и т.п. Отметим также, что иногда мягкие системы называют ГИБКИМИ.

Области применения СРВ:

· Системы управления технологическими процессами (например, управление реакторами на атомнымых электростанциях, переработка различных материалов/сырья и т.п.)

· Системы медицинского мониторинга и жизнеобеспечения

· Военные системы (системы наведения, разведки и пр.)

· Робототехника (например, конвейерная сборочная линия)

· Подсистемы транспортных средств (антиблокировка тормозов, управление зажиганием, автопилоты на самолетах)

· Системы сбора данных в научных исследованиях

· Системы охранной сигнализации

Примеры

· робот на конвейере

· самолет (система автоматического пилотирования)

· корабль (...)

· очередь в магазине

· мультимедиа-приложения, DSP

· сеть, системы связи (например, сотовой)

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

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

Классификация алгоритмов планирования (АП), применяемых в СРВ. Выделяют 2 класса АП:

· Алгоритмы со статическим расписанием (другие названия - off-line, static, clock-driven)

· Алгоритмы с динамическим расписанием (другие названия - on-line)

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

· Алгоритмы со статическими приоритетами

· Алгоритмы с динамическим приоритетами

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

Определение.Расписание называется корректным, если соблюдены все крайние сроки.

Определение.Набор задач {T_j} называется планируемым некоторым АП, если этот АП всегда дает корректное расписание для этого набора задач.

Определение.Оптимальным АП называется такой АП, который для ЛЮБОГО набора задач дает корректное расписание, если таковое вообще существует для данного набора задач.

Алгоритмы планирования со статическим расписанием

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

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

Динамические алгоритмы планирования с динамическими приоритетами

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

Далее мы рассмотрим 2 разновидности планировщиков с динамическими приоритетами:

• EDF (earliest deadline first) - приоритет задачам назначается по принципу "в каждый момент времени наивысший приоритет имеет та задача, у которой осталось меньше всего времени до крайнего срока".
• LLF (least laxity first) - приоритет задачам назначается по принципу "в каждый момент времени наивысший приоритет имеет задача с наименьшим запасом времени". Понятие запаса времени будет определено чуть позже.

При этом имеются 2 модификации алгоритма EDF:

• с вытесненением задач
• без вытеснения задач

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

Динамические алгоритмы планирования со статическими приоритетами

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

Существует 2 распространенных способа назначения приоритетов:

• RMS (rate monotonic scheduling). Правило назначения приоритетов таково: чем меньше период задачи, тем выше у нее приоритет. Иными словами, чем чаще (отсюда rate) задача переходит в состояние готовности, тем ее приоритет выше.
• DMS (deadline monotonic scheduling). В этом алгоритме приоритеты назначаются по немного другому правилу: чем меньше относительный крайний срок задачи, тем выше ее приоритет.

Ниже приведен пример расписания, составленного RMS-планировщиком для синхронной системы 3-х периодических задач со следующими параметрами:

• T₁(3, 0.5)
• T₂(4, 1)
• T₃(6, 2)

В соответствии с вышеприведенным правилом самый высокий приоритет имеет первая задача, а самый низкий - третья. В момент времени 0 имеется 3 готовых задачи, процессорное время получает первая. В момент времени 0.5 готовы 2 задачи (2 и 3), управление получает вторая. В момент времени 3 снова становится готовой первая задача, поэтому третья ею вытесняется. В момент времени 3.5 управление вновь получает третья задача как единственно готовая. В момент времени 4.0 готова только задача 2, она и получает управление. В момент времени 6 готовы 2 задачи (1 и 3), управление отдается первой. Далее работает третья задача, но в момент времени 8 она вытесняется второй. В момент 9 опять готова первая задача, она отрабатывает и, наконец, в момент 9.5 получает управление третья задача. Затем все повторяется сначала (при условии, разумеется, что число задач в системе остается неизменным).